Ich habe einen Containertyp "Spalte":
%Vor%Verwendung:
%Vor%Frage: Wie kann ich einen standardkonformen Direktzugriffs-Iterator (und möglicherweise einen erforderlichen Proxy-Referenztyp) für diese Art von Container erstellen?
Ich möchte std::algorithms für wahlfreie Zugriffsiteratoren mit meinem Typ verwenden, z. sort (Anmerkung: Zum Sortieren würde der Vergleich von einem benutzerdefinierten Funktor, beispielsweise einem Lambda, geliefert werden).
Insbesondere sollte der Iterator eine ähnliche Schnittstelle wie
bereitstellen %Vor%Hinweis 0: C ++ 11 / C ++ 14 ist zulässig.
Anmerkung 1: Es gibt ein altes Papier Ссылка wo ein ähnlicher Versuch unternommen wird. Ich war jedoch nicht in der Lage, ihren Ansatz mit Art zu arbeiten. Anforderungen wie defaultConstructible sind schwer zu erfüllen mit einem Proxy-Ansatz (warum std::sort erfordern Typen standardmäßig konstruierbar statt austauschbar ist, ist jenseits meines Verständnisses).
Hinweis 2: Ich kann Folgendes nicht tun:
%Vor% und dann std::algorithm verwenden.
Motivation: Leistung. Eine Cache-Zeile beträgt üblicherweise 64 Bytes, d. H. 8 Doppel. Wenn Sie in dieser einfachen Struktur über die Doubles iterieren, verschmutzen Sie eine Cache-Zeile mit einem String und einem Int. In anderen Fällen erhalten Sie möglicherweise nur eine doppelte Übertragung pro Cache-Zeile. Das heißt, Sie verwenden 1/8 der verfügbaren Speicherbandbreite. Wenn Sie mehrere Gb-Doubles iterieren müssen, verbessert diese einfache Entscheidung die Anwendungsleistung um den Faktor 6-7x. Und nein, ich kann das nicht aufgeben.
Bonus: Die Antwort sollte so allgemein wie möglich sein. Denken Sie darüber nach, Felder zum Containertyp hinzuzufügen / zu entfernen, indem Sie Elemente zu einer Struktur hinzufügen / entfernen. Sie möchten nicht jedes Mal, wenn Sie ein neues Mitglied hinzufügen, eine Menge Code ändern.
Ich denke, so etwas könnte standardkonform sein. Es verwendet einige C ++ 11-Funktionen, um die Syntax zu vereinfachen, könnte aber auch geändert werden, um C ++ 03 AFAIK zu entsprechen.
Getestet und funktioniert mit clang ++ 3.2
Vorwort:
%Vor% Die Iterator-Klassen: a value_type ( all_copy ), reference type ( all_reference ) und Iterator-Typ ( all_iterator ). Das Iterieren wird durchgeführt, indem drei Iteratoren (einer pro vector ) beibehalten und aktualisiert werden. Ich weiß jedoch nicht, ob das die performanteste Option ist.
Wie es funktioniert: std::iterator_traits definiert mehrere zugehörige Typen für einen Iterator:
[iterator.traits] / 1
iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::iterator_category
definiert sein als Differenztyp, Werttyp und Iteratorkategorie des Iterators. Zusätzlich die Typen
iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer
soll als Refe- renz- und Zeigertypen des Iterators definiert sein, dh für ein Iterator-Objekt a, den gleichen Typ wie der Typ von*abzw.a->bzw.
Daher können Sie eine Struktur ( all_reference ) einführen, die drei Referenzen als reference type enthält. Dieser Typ ist der Rückgabewert von *a , wobei a vom Typ Iterator ist (möglicherweise const -qualifiziert). Es muss ein anderes value_type vorhanden sein, da einige Standardbibliotheksalgorithmen wie sort eine lokale Variable erstellen möchten, die den Wert von *a temporär speichert (durch Kopieren oder Verschieben in die lokale Variable). In diesem Fall bietet all_copy diese Funktionalität.
Sie müssen es nicht in Ihren eigenen Schleifen verwenden ( all_copy ), wo es die Leistung beeinträchtigen könnte.
Es muss eine Vergleichsfunktion für std::sort geben. Aus irgendeinem Grund müssen wir alle drei zur Verfügung stellen.
Nun die Iterator-Klasse:
%Vor%Anwendungsbeispiel:
%Vor%Ausgabe:
1; j; 10, 0,9; i; 9, 0,8; h; 8, 0,7; g; 7, 0,6; f; 6, 0,5; e; 5, 0,4; d; 4, 0,3; c; 3 , 0,2; b; 2, 0,1; a; 1, 0,1; a; 1, 0,2; b; 2, 0,3; c; 3, 0,4; d; 4, 0,5; e; 5, 0,6; f; 6, 0,7; g; 7, 0,8; h; 8, 0,9; i; 9, 1; j; 10,
Wenn Sie wirklich an der Leistung interessiert sind und Ihren Container mit std::sort sortieren möchten, verwenden Sie die Überladung, mit der Sie ein benutzerdefiniertes Vergleichsobjekt bereitstellen können:
.. und sortieren Sie ein Array von Indizes in den Container. Hier ist wie:
Sie benötigen die folgenden Mitglieder in Ihrem Container:
%Vor%Definieren Sie anschließend das folgende Vergleichsobjekt:
%Vor%Und verwenden Sie es, um ein Array von Indizes zu sortieren:
%Vor%Das 'less' Mitglied des Containers steuert, in welche Sortierreihenfolge es gehen soll:
%Vor%Das sortierte Array von Indizes kann in weiteren Algorithmen verwendet werden - Sie können es vermeiden, die tatsächlichen Daten so lange herumzukopieren, bis Sie es brauchen.
Alle std -Algorithmen, die mit RandomAccessIterators arbeiten, haben Überladungen, mit denen Sie benutzerdefinierte Vergleichsobjekte angeben können, so dass sie auch mit dieser Technik verwendet werden können.