Warum Iteratoren anstelle von Array-Indizes verwenden?

239

Nehmen Sie die folgenden zwei Codezeilen:

for (int i = 0; i < some_vector.size(); i++)
{
    //do stuff
}

Und das:

for (some_iterator = some_vector.begin(); some_iterator != some_vector.end();
    some_iterator++)
{
    //do stuff
}

Mir wurde gesagt, dass der zweite Weg bevorzugt wird. Warum genau ist das so?

Jason Baker
quelle
72
Der zweite Weg ist bevorzugt , ist , dass Sie ändern some_iterator++zu ++some_iterator. Nach dem Inkrementieren wird ein unnötiger temporärer Iterator erstellt.
Jason
6
Sie sollten auch end()in die Deklarationsklausel einbringen .
Leichtigkeitsrennen im Orbit
5
@Tomalak: Jeder, der eine C ++ - Implementierung mit einer ineffizienten Implementierung verwendet, vector::endhat wahrscheinlich schlimmere Probleme als die Frage, ob sie aus Schleifen gehisst wird oder nicht. Persönlich bevorzuge ich Klarheit - wenn es ein Anruf findin der Kündigungsbedingung wäre, würde ich mir allerdings Sorgen machen.
Steve Jessop
13
@Tomalak: Dieser Code ist nicht schlampig (naja, das Post-Inkrement vielleicht), er ist prägnant und klar, soweit C ++ - Iteratoren Prägnanz zulassen. Durch Hinzufügen weiterer Variablen wird der kognitive Aufwand für eine vorzeitige Optimierung erhöht. Das ist schlampig.
Steve Jessop
7
@Tomalak: Es ist verfrüht, wenn es kein Engpass ist. Ihr zweiter Punkt erscheint mir absurd, da der richtige Vergleich nicht zwischen it != vec.end()und it != end, sondern zwischen (vector<T>::iterator it = vec.begin(); it != vec.end(); ++it)und liegt (vector<T>::iterator it = vec.begin(), end = vec.end(); it != end; ++it). Ich muss die Zeichen nicht zählen. Ziehen Sie auf jeden Fall das eine dem anderen vor, aber die Nichtübereinstimmung anderer mit Ihrer Präferenz ist nicht "schlampig", sondern eine Präferenz für einfacheren Code mit weniger Variablen und daher weniger Überlegungen beim Lesen.
Steve Jessop

Antworten:

210

Die erste Form ist nur dann effizient, wenn vector.size () eine schnelle Operation ist. Dies gilt beispielsweise für Vektoren, nicht jedoch für Listen. Was planen Sie auch innerhalb des Loop-Körpers? Wenn Sie wie in auf die Elemente zugreifen möchten

T elem = some_vector[i];

Dann gehen Sie davon aus, dass der Container operator[](std::size_t)definiert wurde. Dies gilt wiederum für Vektoren, jedoch nicht für andere Container.

Die Verwendung von Iteratoren bringt Sie der Containerunabhängigkeit näher . Sie machen keine Annahmen über die Direktzugriffsfähigkeit oder den schnellen size()Betrieb, sondern nur, dass der Container über Iteratorfunktionen verfügt.

Sie können Ihren Code mithilfe von Standardalgorithmen weiter verbessern. Je nachdem , was Sie erreichen wollen, können Sie Gebrauch machen möchten std::for_each(), std::transform()und so weiter. Wenn Sie einen Standardalgorithmus anstelle einer expliziten Schleife verwenden, vermeiden Sie, das Rad neu zu erfinden. Ihr Code ist wahrscheinlich effizienter (vorausgesetzt, der richtige Algorithmus wird ausgewählt), korrekt und wiederverwendbar.

wilhelmtell
quelle
8
Außerdem haben Sie vergessen, dass Iteratoren beispielsweise ausfallsicher sein können, sodass Sie bei gleichzeitiger Änderung der Struktur, auf die Sie zugreifen, davon erfahren. Sie können das nicht nur mit einer ganzen Zahl machen.
Marcin
4
Das verwirrt mich: "Dies gilt zum Beispiel für Vektoren, aber nicht für Listen." Warum? Jeder mit einem Gehirn behält eine size_tMitgliedsvariable im Auge size().
GManNickG
19
@GMan - In fast allen Implementierungen ist size () für Listen genauso schnell wie für Vektoren. Für die nächste Version des Standards muss dies zutreffen. Das eigentliche Problem ist die Langsamkeit der Rücknahme nach Position.
Daniel Earwicker
8
@GMan: Zum Speichern der Listengröße muss das Aufteilen und Spleißen von Listen O (n) anstelle von O (1) sein.
5
In C ++ 0x muss die Elementfunktion size()für alle Container, die sie unterstützen, eine konstante zeitliche Komplexität aufweisen, einschließlich std::list.
James McNellis
54

Es ist Teil des modernen C ++ - Indoktrinationsprozesses. Iteratoren sind die einzige Möglichkeit, die meisten Container zu iterieren. Sie verwenden sie daher auch mit Vektoren, um sich in die richtige Denkweise zu versetzen. Im Ernst, das ist der einzige Grund, warum ich es tue - ich glaube nicht, dass ich jemals einen Vektor durch eine andere Art von Container ersetzt habe.


Wow, das wird nach drei Wochen immer noch abgelehnt. Ich denke, es lohnt sich nicht, ein bisschen frech zu sein.

Ich denke, der Array-Index ist besser lesbar. Es entspricht der in anderen Sprachen verwendeten Syntax und der für altmodische C-Arrays verwendeten Syntax. Es ist auch weniger ausführlich. Effizienz sollte eine Wäsche sein, wenn Ihr Compiler gut ist, und es gibt kaum Fälle, in denen es sowieso darauf ankommt.

Trotzdem benutze ich immer noch häufig Iteratoren mit Vektoren. Ich glaube, der Iterator ist ein wichtiges Konzept, deshalb fördere ich es, wann immer ich kann.

Mark Ransom
quelle
1
C ++ - Iteratoren sind auch konzeptionell schrecklich kaputt. Bei Vektoren wurde ich gerade erwischt, weil der Endzeiger akut end + 1 (!) Ist. Für Streams ist das Iteratormodell nur surreal - ein imaginäres Token, das es nicht gibt. Ebenso für verknüpfte Listen. Das Paradigma macht nur für Arrays Sinn und dann nicht viel. Warum brauche ich zwei Iterator-Objekte, nicht nur ein ...
Tuntable
5
@aberglas sie sind überhaupt nicht kaputt, du bist einfach nicht an sie gewöhnt, weshalb ich befürworte, sie zu benutzen, auch wenn du nicht musst! Halboffene Bereiche sind ein gängiges Konzept, und Sentinels, auf die niemals direkt zugegriffen werden soll, sind ungefähr so ​​alt wie die Programmierung selbst.
Mark Ransom
4
Schauen Sie sich die Stream-Iteratoren an und überlegen Sie, was == pervers gemacht wurde, um das Muster anzupassen, und sagen Sie mir dann, dass die Iteratoren nicht kaputt sind! Oder für verknüpfte Listen. Selbst für Arrays ist es eine kaputte Idee im C-Stil, eine nach dem Ende angeben zu müssen - ein Zeiger auf das Niemals-Niemals. Sie sollten wie Java oder C # oder die Iteratoren einer anderen Sprache sein, wobei ein Iterator (anstelle von zwei Objekten) und ein einfacher Endtest erforderlich sind.
Tuntable
53

weil Sie Ihren Code nicht an die bestimmte Implementierung der some_vector-Liste binden. Wenn Sie Array-Indizes verwenden, muss es sich um eine Art Array handeln. Wenn Sie Iteratoren verwenden, können Sie diesen Code für jede Listenimplementierung verwenden.

Kreuzer
quelle
23
Die std :: list-Schnittstelle bietet absichtlich keinen Operator [] (size_t n), da dies O (n) wäre.
MSalters
33

Stellen Sie sich vor, some_vector wird mit einer verknüpften Liste implementiert. Um dann ein Element an der i-ten Stelle anzufordern, müssen i-Operationen ausgeführt werden, um die Liste der Knoten zu durchlaufen. Wenn Sie nun im Allgemeinen den Iterator verwenden, bemüht er sich nach besten Kräften, so effizient wie möglich zu sein (im Fall einer verknüpften Liste wird ein Zeiger auf den aktuellen Knoten beibehalten und in jeder Iteration weiterentwickelt, wobei nur ein Iterator erforderlich ist Einzeloperation).

Es bietet also zwei Dinge:

  • Abstraktion der Verwendung: Sie möchten nur einige Elemente iterieren, es ist Ihnen egal, wie es geht
  • Performance
Asterit
quelle
1
"Es wird einen Zeiger auf den aktuellen Knoten beibehalten und ihn weiterentwickeln [gutes Zeug zur Effizienz]" - Ja, ich verstehe nicht, warum die Leute Probleme haben, das Konzept der Iteratoren zu verstehen. Sie sind konzeptionell nur eine Obermenge von Zeigern. Warum den Offset eines Elements immer wieder berechnen, wenn Sie nur einen Zeiger darauf zwischenspeichern können? Nun, das ist es, was Iteratoren auch tun.
underscore_d
27

Ich werde hier der Anwalt der Teufel sein und keine Iteratoren empfehlen. Der Hauptgrund dafür ist, dass der gesamte Quellcode, an dem ich von der Entwicklung von Desktop-Anwendungen bis zur Spieleentwicklung gearbeitet habe, weder Iteratoren verwendet werden musste. Die ganze Zeit, in der sie nicht benötigt wurden, und zweitens machen die versteckten Annahmen und das Durcheinander von Code und das Debuggen von Albträumen, die Sie mit Iteratoren bekommen, sie zu einem Paradebeispiel dafür, sie nicht in Anwendungen zu verwenden, die Geschwindigkeit erfordern.

Selbst vom Standpunkt der Wartung aus sind sie ein Chaos. Es liegt nicht an ihnen, sondern an all dem Aliasing, das hinter den Kulissen stattfindet. Woher weiß ich, dass Sie keine eigene virtuelle Vektor- oder Array-Liste implementiert haben, die etwas völlig anderes als die Standards tut? Weiß ich, welcher Typ derzeit zur Laufzeit ist? Haben Sie einen Operator überladen? Ich hatte keine Zeit, Ihren gesamten Quellcode zu überprüfen. Zur Hölle, weiß ich überhaupt, welche Version der STL Sie verwenden?

Das nächste Problem, das Sie mit Iteratoren haben, ist die undichte Abstraktion, obwohl es zahlreiche Websites gibt, die dies mit ihnen ausführlich besprechen.

Entschuldigung, ich habe und habe noch keinen Punkt in Iteratoren gesehen. Wenn sie die Liste oder den Vektor von Ihnen weg abstrahieren, sollten Sie tatsächlich bereits wissen, mit welchem ​​Vektor oder welcher Liste Sie sich befassen, wenn Sie dies nicht tun, dann werden Sie sich in Zukunft nur auf einige großartige Debugging-Sitzungen einstellen.

Tschad
quelle
23

Möglicherweise möchten Sie einen Iterator verwenden, wenn Sie dem Vektor Elemente hinzufügen / entfernen möchten, während Sie darüber iterieren.

some_iterator = some_vector.begin(); 
while (some_iterator != some_vector.end())
{
    if (/* some condition */)
    {
        some_iterator = some_vector.erase(some_iterator);
        // some_iterator now positioned at the element after the deleted element
    }
    else
    {
        if (/* some other condition */)
        {
            some_iterator = some_vector.insert(some_iterator, some_new_value);
            // some_iterator now positioned at new element
        }
        ++some_iterator;
    }
}

Wenn Sie Indizes verwenden würden, müssten Sie Elemente im Array nach oben / unten mischen, um die Einfügungen und Löschungen zu verarbeiten.

Brian Matthews
quelle
3
Wenn Sie Elemente in die Mitte des Containers einfügen möchten, ist ein Vektor möglicherweise zunächst keine gute Wahl für den Container. Natürlich kommen wir zurück zu dem Grund, warum Iteratoren cool sind. Es ist trivial, zu einer Liste zu wechseln.
Wilhelmtell
Das Iterieren über alle Elemente ist im std::listVergleich zu a jedoch ziemlich teuer std::vector, wenn Sie die Verwendung einer verknüpften Liste anstelle von a empfehlen std::vector. Siehe Seite 43: ecn.channel9.msdn.com/events/GoingNative12/GN12Cpp11Style.pdf Nach meiner Erfahrung std::vectorist a schneller als a, std::listselbst wenn ich alles durchsuche und Elemente an beliebigen Positionen entferne.
David Stone
Die Indizes sind stabil, daher sehe ich nicht, welches zusätzliche Mischen für Einfügungen und Löschungen erforderlich ist.
Musiphil
... Und mit einer verknüpften Liste - die hier verwendet werden sollte - wäre Ihre Schleifenanweisung for (node = list->head; node != NULL; node = node->next)kürzer als Ihre ersten beiden Codezeilen zusammen (Deklaration und Schleifenkopf). Also sage ich noch einmal - es gibt keinen großen grundsätzlichen Unterschied in der Kürze zwischen der Verwendung von Iteratoren und der Nichtverwendung von Iteratoren - Sie haben immer noch die drei Teile einer forAnweisung erfüllt , selbst wenn Sie whileFolgendes verwenden : Deklarieren, Iterieren, Überprüfen der Beendigung.
Ingenieur
16

Trennung von Bedenken

Es ist sehr schön, den Iterationscode vom Kernanliegen der Schleife zu trennen. Es ist fast eine Designentscheidung.

In der Tat bindet Sie das Iterieren nach Index an die Implementierung des Containers. Wenn Sie den Container nach einem Start- und Enditerator fragen, wird der Schleifencode für die Verwendung mit anderen Containertypen aktiviert.

Außerdem sagenstd::for_each Sie der Sammlung, was zu tun ist, anstatt sie nach ihren Interna zu fragen

Der 0x-Standard wird Verschlüsse einführen, die die Verwendung dieses Ansatzes erheblich vereinfachen. Schauen Sie sich die Ausdruckskraft von z. B. Rubys [1..6].each { |i| print i; }...

Performance

Aber vielleicht ist ein viel übersehenes Problem, dass die Verwendung des for_eachAnsatzes die Möglichkeit bietet, die Iteration parallelisieren zu lassen - die Intel-Threading-Blöcke können den Codeblock über die Anzahl der Prozessoren im System verteilen!

Hinweis: Nachdem ich die algorithmsBibliothek entdeckt hatte, und insbesondere foreach, habe ich zwei oder drei Monate lang lächerlich kleine 'Helfer'-Operator-Strukturen geschrieben, die Ihre Mitentwickler verrückt machen werden. Nach dieser Zeit kehrte ich zu einem pragmatischen Ansatz zurück - kleine Schleifenkörper verdienen foreachnichts mehr :)

Ein Muss für Iteratoren ist das Buch "Extended STL" .

Die GoF haben am Ende des Iterator-Musters einen winzigen kleinen Absatz, der über diese Art der Iteration spricht. Es wird als "interner Iterator" bezeichnet. Schauen Sie auch hier vorbei .

xtofl
quelle
15

Weil es objektorientierter ist. Wenn Sie mit einem Index iterieren, gehen Sie davon aus:

a) dass diese Objekte geordnet sind
b) dass diese Objekte durch einen Index erhalten werden können
c) dass das Indexinkrement jedes Element trifft
d) dass dieser Index bei Null beginnt

Mit einem Iterator sagen Sie "Gib mir alles, damit ich damit arbeiten kann", ohne zu wissen, was die zugrunde liegende Implementierung ist. (In Java gibt es Sammlungen, auf die über einen Index nicht zugegriffen werden kann.)

Mit einem Iterator müssen Sie sich auch keine Sorgen mehr machen, dass die Grenzen des Arrays überschritten werden.

Zyniker
quelle
2
Ich denke nicht, dass "objektorientiert" der richtige Begriff ist. Iteratoren sind im Design nicht "objektorientiert". Sie fördern die funktionale Programmierung mehr als die objektorientierte Programmierung, da sie die Trennung der Algorithmen von den Klassen fördern.
Wilhelmtell
Außerdem helfen Iteratoren nicht, das Überschreiten von Grenzen zu vermeiden. Standardalgorithmen tun dies, Iteratoren allein jedoch nicht.
Wilhelmtell
Fair genug @wilhelmtell, ich denke offensichtlich aus Java-zentrierter Sicht darüber nach.
Zyniker
1
Und ich denke, dass es OO fördert, weil es Operationen an Sammlungen von der Implementierung dieser Sammlung trennt. Eine Sammlung von Objekten sollte nicht unbedingt wissen, mit welchen Algorithmen sie arbeiten sollen.
Zyniker
Tatsächlich gibt es Versionen der STL, die Iteratoren überprüft haben, was bedeutet, dass sie eine Art Ausnahme außerhalb der Grenzen auslösen, wenn Sie versuchen, etwas mit diesem Iterator zu tun.
Daemin
15

Eine weitere nette Sache bei Iteratoren ist, dass sie es Ihnen besser ermöglichen, Ihre Konstantenpräferenz auszudrücken (und durchzusetzen). Dieses Beispiel stellt sicher, dass Sie den Vektor in der Mitte Ihrer Schleife nicht ändern:


for(std::vector<Foo>::const_iterator pos=foos.begin(); pos != foos.end(); ++pos)
{
    // Foo & foo = *pos; // this won't compile
    const Foo & foo = *pos; // this will compile
}
Pat Notz
quelle
Das sieht vernünftig aus, aber ich bezweifle immer noch, dass dies der Grund dafür ist const_iterator. Wenn ich den Vektor in der Schleife ändere, mache ich das aus einem Grund, und in 99,9% der Fälle ist das Ändern kein Zufall, und im Übrigen ist es nur ein Fehler wie jede Art von Fehler im Code des Autors muss beheben. Da es in Java und vielen anderen Sprachen überhaupt kein const-Objekt gibt, haben Benutzer dieser Sprachen jedoch nie ein Problem ohne const-Unterstützung in diesen Sprachen.
Neevek
2
@neevek Wenn das nicht der Grund dafür ist const_iterator, was um alles in der Welt könnte der Grund sein?
underscore_d
@underscore_d, ich frage mich auch. Ich bin kein Experte in diesem Bereich, es ist nur so, dass die Antwort für mich nicht überzeugend ist.
neevek
15

Abgesehen von all den anderen hervorragenden Antworten ... ist es intmöglicherweise nicht groß genug für Ihren Vektor. Wenn Sie stattdessen die Indizierung verwenden möchten, verwenden Sie Folgendes size_typefür Ihren Container:

for (std::vector<Foo>::size_type i = 0; i < myvector.size(); ++i)
{
    Foo& this_foo = myvector[i];
    // Do stuff with this_foo
}
Pat Notz
quelle
1
@ Pat Notz, das ist ein sehr guter Punkt. Während der Portierung einer STL-basierten Windows-Anwendung auf x64 musste ich mich mit Hunderten von Warnungen befassen, um einem int size_t zuzuweisen, was möglicherweise zu Kürzungen führen kann.
bk1e
1
Ganz zu schweigen von der Tatsache, dass die Größentypen nicht signiert und int signiert sind. Sie haben also nicht intuitive, fehlerversteckende Konvertierungen, die nur zum Vergleich int imit ausgeführt werden myvector.size().
Adrian McCarthy
12

Ich sollte wahrscheinlich darauf hinweisen, dass Sie auch anrufen können

std::for_each(some_vector.begin(), some_vector.end(), &do_stuff);

MSalters
quelle
7

STL-Iteratoren sind meistens vorhanden, damit die STL-Algorithmen wie sort sortnerunabhängig sein können.

Wenn Sie nur alle Einträge in einem Vektor durchlaufen möchten, verwenden Sie einfach den Indexschleifenstil.

Es ist weniger tippend und für die meisten Menschen einfacher zu analysieren. Es wäre schön, wenn C ++ eine einfache foreach-Schleife hätte, ohne mit Template-Magie über Bord zu gehen.

for( size_t i = 0; i < some_vector.size(); ++i )
{
   T& rT = some_vector[i];
   // now do something with rT
}
'
Jeroen Dirks
quelle
5

Ich denke nicht, dass es für einen Vektor einen großen Unterschied macht. Ich bevorzuge es, einen Index selbst zu verwenden, da ich ihn für besser lesbar halte und Sie einen wahlfreien Zugriff ausführen können, z. B. 6 Elemente vorwärts springen oder bei Bedarf rückwärts springen.

Ich möchte auch einen Verweis auf das Element in der Schleife wie folgt machen, damit es nicht viele eckige Klammern um den Ort gibt:

for(size_t i = 0; i < myvector.size(); i++)
{
    MyClass &item = myvector[i];

    // Do stuff to "item".
}

Die Verwendung eines Iterators kann gut sein, wenn Sie glauben, dass Sie den Vektor irgendwann in der Zukunft durch eine Liste ersetzen müssen, und er sieht für STL-Freaks auch eleganter aus, aber ich kann mir keinen anderen Grund vorstellen.

Adam Pierce
quelle
Die meisten Algorithmen arbeiten nacheinander einmal mit jedem Element eines Containers. Natürlich gibt es Ausnahmen, in denen Sie eine Sammlung in einer bestimmten Reihenfolge oder Weise durchlaufen möchten, aber in diesem Fall würde ich mich bemühen, einen Algorithmus zu schreiben, der in die STL integriert ist und mit Iteratoren funktioniert.
Wilhelmtell
Dies würde die Wiederverwendung fördern und spätere Fehler vermeiden. Ich würde diesen Algorithmus dann wie jeden anderen Standardalgorithmus mit Iteratoren aufrufen.
Wilhelmtell
1
Ich brauche nicht einmal Voraus (). Der Iterator hat die gleichen Operatoren + = und - = wie ein Index (für vektor- und vektorähnliche Container).
MSalters
I prefer to use an index myself as I consider it to be more readablenur in einigen Situationen; In anderen Fällen werden Indizes schnell sehr unordentlich. Diesand you can do random access ist überhaupt keine Besonderheit von Indizes: siehe en.cppreference.com/w/cpp/concept/RandomAccessIterator
underscore_d
3

Das zweite Formular gibt an, was Sie genauer tun. In Ihrem Beispiel interessiert Sie der Wert von i eigentlich nicht - alles, was Sie wollen, ist das nächste Element im Iterator.

Colen
quelle
3

Nachdem ich etwas mehr über das Thema dieser Antwort gelernt habe, stelle ich fest, dass es ein bisschen zu einfach war. Der Unterschied zwischen dieser Schleife:

for (some_iterator = some_vector.begin(); some_iterator != some_vector.end();
    some_iterator++)
{
    //do stuff
}

Und diese Schleife:

for (int i = 0; i < some_vector.size(); i++)
{
    //do stuff
}

Ist ziemlich minimal. Tatsächlich scheint mir die Syntax, Schleifen auf diese Weise zu machen, zu wachsen:

while (it != end){
    //do stuff
    ++it;
}

Iteratoren entsperren einige ziemlich leistungsfähige deklarative Funktionen, und in Kombination mit der STL-Algorithmusbibliothek können Sie einige ziemlich coole Dinge tun, die außerhalb des Bereichs der Array-Indexverwaltung liegen.

Jason Baker
quelle
Die Wahrheit ist, wenn alle Iteratoren so kompakt wären wie Ihr letztes Beispiel, hätte ich sofort ein kleines Problem mit ihnen. Das ist natürlich gleich for (Iter it = {0}; it != end; ++it) {...}- Sie haben die Erklärung einfach weggelassen -, also unterscheidet sich die Kürze nicht wesentlich von Ihrem zweiten Beispiel. Trotzdem +1.
Ingenieur
3

Die Indizierung erfordert eine zusätzliche mulOperation. Zum Beispiel vector<int> vkonvertiert der Compiler v[i]in &v + sizeof(int) * i.

Marc Eaddy
quelle
Wahrscheinlich kein wesentlicher Nachteil gegenüber Iteratoren in den meisten Fällen, aber es ist eine gute Sache, sich dessen bewusst zu sein.
Nobar
3
Wahrscheinlich für isolierte Einzelelementzugriffe. Aber wenn wir über Schleifen sprechen - wie es das OP war - dann bin ich mir ziemlich sicher, dass diese Antwort auf einem imaginären nicht optimierenden Compiler basiert. Jeder halbwegs anständige hat ausreichend Gelegenheit und Wahrscheinlichkeit, das zu zwischenspeichern sizeofund es nur einmal pro Iteration hinzuzufügen, anstatt jedes Mal die gesamte Offset-Berechnung erneut durchzuführen.
underscore_d
2

Während der Iteration müssen Sie nicht wissen, wie viele Elemente verarbeitet werden sollen. Sie brauchen nur das Element und Iteratoren tun solche Dinge sehr gut.

Sergey Stolyarov
quelle
2

Bisher hat noch niemand erwähnt, dass ein Vorteil von Indizes darin besteht, dass sie nicht ungültig werden, wenn Sie an einen zusammenhängenden Container wie anhängen std::vector, sodass Sie dem Container während der Iteration Elemente hinzufügen können.

Dies ist auch mit Iteratoren möglich, Sie müssen jedoch aufrufen reserve() und daher wissen, wie viele Elemente Sie anhängen werden.

danpla
quelle
1

Einige gute Punkte bereits. Ich habe ein paar zusätzliche Kommentare:

  1. Unter der Annahme, dass es sich um die C ++ - Standardbibliothek handelt, impliziert "vector" einen Direktzugriffscontainer, der die Garantien eines C-Arrays (Direktzugriff, Speicherlayout für Contiguos usw.) bietet. Wenn Sie 'some_container' gesagt hätten, wären viele der oben genannten Antworten genauer gewesen (Containerunabhängigkeit usw.).

  2. Um Abhängigkeiten von der Compileroptimierung zu beseitigen, können Sie some_vector.size () im indizierten Code wie folgt aus der Schleife verschieben:

    const size_t numElems = some_vector.size ();
    für (size_t i = 0; i 
  3. Iteratoren immer vorinkrementieren und Postinkremente als Ausnahmefälle behandeln.

for (some_iterator = some_vector.begin (); some_iterator! = some_vector.end (); ++ some_iterator) {// do stuff}

Also vorausgesetzt und indexierbar std::vector<> wie ein Container , gibt es keinen guten Grund, einen anderen vorzuziehen und den Container nacheinander zu durchlaufen. Wenn Sie häufig auf ältere oder neuere Elementindizes verweisen müssen, ist die indizierte Version angemessener.

Im Allgemeinen wird die Verwendung der Iteratoren bevorzugt, da Algorithmen diese verwenden und das Verhalten durch Ändern des Iteratortyps gesteuert (und implizit dokumentiert) werden kann. Array-Positionen können anstelle von Iteratoren verwendet werden, aber der syntaktische Unterschied wird auffallen.

user22044
quelle
1

Ich benutze keine Iteratoren aus dem gleichen Grund, aus dem ich foreach-Anweisungen nicht mag. Bei mehreren inneren Schleifen ist es schwierig genug, globale / Mitgliedsvariablen zu verfolgen, ohne sich auch alle lokalen Werte und Iteratornamen merken zu müssen. Was ich nützlich finde, ist, zwei Sätze von Indizes für verschiedene Anlässe zu verwenden:

for(int i=0;i<anims.size();i++)
  for(int j=0;j<bones.size();j++)
  {
     int animIndex = i;
     int boneIndex = j;


     // in relatively short code I use indices i and j
     ... animation_matrices[i][j] ...

     // in long and complicated code I use indices animIndex and boneIndex
     ... animation_matrices[animIndex][boneIndex] ...


  }

Ich möchte Dinge wie "animation_matrices [i]" nicht einmal mit einem zufälligen "anim_matrix" -benannten Iterator abkürzen, weil Sie dann nicht klar sehen können, von welchem ​​Array dieser Wert stammt.

AareP
quelle
Ich sehe nicht, wie Indizes in diesem Sinne besser sind. Sie könnten Iteratoren leicht verwenden und nur eine Konvention für ihre Namen wählen: it, jt, ktetc. oder auch nur weiter zu verwenden i, j, ketc. Und wenn Sie wissen müssen , um genau das, was ein Iterator darstellt, dann wie etwas zu mir for (auto anim = anims.begin(); ...) for (auto anim_bone = anim->bones.begin(); ...) anim_bone->wobble()wären kräftiger als ständig wie indizieren zu müssen animation_matrices[animIndex][boneIndex].
underscore_d
Wow, es fühlt sich wie vor Ewigkeiten an, als ich diese Meinung schrieb. Heutzutage werden sowohl foreach- als auch c ++ - Iteratoren verwendet, ohne viel zu kriechen. Ich denke, die jahrelange Arbeit mit fehlerhaftem Code erhöht die Toleranz, so dass es einfacher ist, alle Syntaxen und Konventionen zu akzeptieren ... solange es funktioniert und solange man nach Hause gehen kann, weißt du;)
AareP
Haha, tatsächlich habe ich mir nicht wirklich angesehen, wie alt das vorher war! Etwas anderes, an das ich beim letzten Mal irgendwie nicht gedacht habe, war, dass wir heutzutage auch die bereichsbasierte forSchleife haben, was die iteratorbasierte Methode noch präziser macht.
underscore_d
1
  • Wenn Sie gerne in der Nähe des Metalls sind / den Implementierungsdetails nicht vertrauen, verwenden Sie keine Iteratoren.
  • Wenn Sie während der Entwicklung regelmäßig einen Sammlungstyp gegen einen anderen austauschen, verwenden Sie Iteratoren.
  • Wenn Sie sich nur schwer daran erinnern können, wie verschiedene Arten von Sammlungen iteriert werden (möglicherweise werden mehrere Typen aus verschiedenen externen Quellen verwendet), verwenden Sie Iteratoren, um die Mittel zu vereinheitlichen, mit denen Sie über Elemente gehen. Dies gilt beispielsweise für das Wechseln einer verknüpften Liste mit einer Array-Liste.

Das ist wirklich alles. Es ist nicht so, dass Sie im Durchschnitt mehr oder mehr an Kürze gewinnen, und wenn Kürze wirklich Ihr Ziel ist, können Sie jederzeit auf Makros zurückgreifen.

Ingenieur
quelle
1

Wenn Sie Zugang zu haben C ++ 11 - Funktionen, dann können Sie auch eine Verwendung bereichsbasierte forSchleife zur Iteration über dem Vektor (oder einen anderen Behälter) wie folgt:

for (auto &item : some_vector)
{
     //do stuff
}

Der Vorteil dieser Schleife besteht darin, dass Sie direkt über die itemVariable auf Elemente des Vektors zugreifen können, ohne das Risiko einzugehen, dass ein Index durcheinander gebracht wird oder beim Dereferenzieren eines Iterators ein Fehler gemacht wird. Darüber hinaus autoverhindert der Platzhalter, dass Sie den Typ der Containerelemente wiederholen müssen, wodurch Sie einer containerunabhängigen Lösung noch näher kommen.

Anmerkungen:

  • Wenn Sie den Elementindex in Ihrer Schleife benötigen und der operator[]für Ihren Container vorhanden ist (und für Sie schnell genug ist), gehen Sie besser Ihren ersten Weg.
  • Eine bereichsbasierte forSchleife kann nicht zum Hinzufügen / Löschen von Elementen zu / aus einem Container verwendet werden. Wenn Sie das tun möchten, halten Sie sich besser an die Lösung von Brian Matthews.
  • Wenn Sie die Elemente in Ihrem Container nicht ändern möchten, sollten Sie das Schlüsselwort constwie folgt verwenden : for (auto const &item : some_vector) { ... }.
hupen
quelle
0

Noch besser als "der CPU sagen, was zu tun ist" (zwingend erforderlich) ist "den Bibliotheken sagen, was Sie wollen" (funktional).

Anstatt also Schleifen zu verwenden, sollten Sie die in stl vorhandenen Algorithmen lernen.

Cyber ​​Oliveira
quelle
0

Für die Unabhängigkeit der Container

all2one
quelle
0

Ich verwende immer einen Array-Index, da viele meiner Anwendungen so etwas wie "Miniaturbild anzeigen" erfordern. Also habe ich so etwas geschrieben:

some_vector[0].left=0;
some_vector[0].top =0;<br>

for (int i = 1; i < some_vector.size(); i++)
{

    some_vector[i].left = some_vector[i-1].width +  some_vector[i-1].left;
    if(i % 6 ==0)
    {
        some_vector[i].top = some_vector[i].top.height + some_vector[i].top;
        some_vector[i].left = 0;
    }

}
Krirk
quelle
0

Beide Implementierungen sind korrekt, aber ich würde die 'for'-Schleife bevorzugen. Da wir uns entschieden haben, einen Vektor und keinen anderen Container zu verwenden, ist die Verwendung von Indizes die beste Option. Die Verwendung von Iteratoren mit Vektoren würde den Vorteil verlieren, dass sich die Objekte in fortlaufenden Speicherblöcken befinden, was den Zugriff erleichtert.

Messias
quelle
2
"Die Verwendung von Iteratoren mit Vektoren würde den Vorteil verlieren, dass sich die Objekte in fortlaufenden Speicherblöcken befinden, was den Zugriff erleichtert." [Zitat benötigt]. Warum? Denken Sie, dass ein Inkrement eines Iterators zu einem zusammenhängenden Container nicht als einfache Ergänzung implementiert werden kann?
underscore_d
0

Ich hatte das Gefühl, dass keine der Antworten hier erklärt, warum ich Iteratoren als allgemeines Konzept für die Indizierung in Containern mag. Beachten Sie, dass der größte Teil meiner Erfahrung mit Iteratoren nicht aus C ++ stammt, sondern aus übergeordneten Programmiersprachen wie Python.

Die Iterator-Schnittstelle stellt weniger Anforderungen an die Verbraucher Ihrer Funktion, sodass die Verbraucher mehr damit anfangen können.

Wenn Sie nur in der Lage sein müssen, vorwärts zu iterieren, kann der Entwickler nicht nur indizierbare Container verwenden, sondern auch jede Klasse, die implementiert operator++(T&), operator*(T)und operator!=(const &T, const &T).

#include <iostream>
template <class InputIterator>
void printAll(InputIterator& begin, InputIterator& end)
{
    for (auto current = begin; current != end; ++current) {
        std::cout << *current << "\n";
    }
}

// elsewhere...

printAll(myVector.begin(), myVector.end());

Ihr Algorithmus funktioniert für den Fall, dass Sie ihn benötigen - er iteriert über einen Vektor -, kann aber auch für Anwendungen nützlich sein, die Sie nicht unbedingt erwarten:

#include <random>

class RandomIterator
{
private:
    std::mt19937 random;
    std::uint_fast32_t current;
    std::uint_fast32_t floor;
    std::uint_fast32_t ceil;

public:
    RandomIterator(
        std::uint_fast32_t floor = 0,
        std::uint_fast32_t ceil = UINT_FAST32_MAX,
        std::uint_fast32_t seed = std::mt19937::default_seed
    ) :
        floor(floor),
        ceil(ceil)
    {
        random.seed(seed);
        ++(*this);
    }

    RandomIterator& operator++()
    {
        current = floor + (random() % (ceil - floor));
    }

    std::uint_fast32_t operator*() const
    {
        return current;
    }

    bool operator!=(const RandomIterator &that) const
    {
        return current != that.current;
    }
};

int main()
{
    // roll a 1d6 until we get a 6 and print the results
    RandomIterator firstRandom(1, 7, std::random_device()());
    RandomIterator secondRandom(6, 7);
    printAll(firstRandom, secondRandom);

    return 0;
}

Der Versuch, einen Operator in eckigen Klammern zu implementieren, der etwas Ähnliches wie dieser Iterator ausführt, wäre erfunden, während die Iteratorimplementierung relativ einfach ist. Der Operator in eckigen Klammern hat auch Auswirkungen auf die Funktionen Ihrer Klasse - die Sie auf einen beliebigen Punkt indizieren können -, deren Implementierung möglicherweise schwierig oder ineffizient ist.

Iteratoren eignen sich auch zur Dekoration . Benutzer können Iteratoren schreiben, die einen Iterator in ihren Konstruktor aufnehmen und dessen Funktionalität erweitern:

template<class InputIterator, typename T>
class FilterIterator
{
private:
    InputIterator internalIterator;

public:
    FilterIterator(const InputIterator &iterator):
        internalIterator(iterator)
    {
    }

    virtual bool condition(T) = 0;

    FilterIterator<InputIterator, T>& operator++()
    {
        do {
            ++(internalIterator);
        } while (!condition(*internalIterator));

        return *this;
    }

    T operator*()
    {
        // Needed for the first result
        if (!condition(*internalIterator))
            ++(*this);
        return *internalIterator;
    }

    virtual bool operator!=(const FilterIterator& that) const
    {
        return internalIterator != that.internalIterator;
    }
};

template <class InputIterator>
class EvenIterator : public FilterIterator<InputIterator, std::uint_fast32_t>
{
public:
    EvenIterator(const InputIterator &internalIterator) :
        FilterIterator<InputIterator, std::uint_fast32_t>(internalIterator)
    {
    }

    bool condition(std::uint_fast32_t n)
    {
        return !(n % 2);
    }
};


int main()
{
    // Rolls a d20 until a 20 is rolled and discards odd rolls
    EvenIterator<RandomIterator> firstRandom(RandomIterator(1, 21, std::random_device()()));
    EvenIterator<RandomIterator> secondRandom(RandomIterator(20, 21));
    printAll(firstRandom, secondRandom);

    return 0;
}

Obwohl diese Spielzeuge banal erscheinen mögen, ist es nicht schwer vorstellbar, Iteratoren und Iteratordekoratoren zu verwenden, um leistungsstarke Dinge mit einer einfachen Oberfläche zu erledigen - beispielsweise das Dekorieren eines Nur-Vorwärts-Iterators von Datenbankergebnissen mit einem Iterator, der beispielsweise ein Modellobjekt aus einem einzelnen Ergebnis erstellt . Diese Muster ermöglichen eine speichereffiziente Iteration unendlicher Mengen und mit einem Filter wie dem oben beschriebenen eine möglicherweise verzögerte Auswertung der Ergebnisse.

Ein Teil der Leistungsfähigkeit von C ++ - Vorlagen besteht darin, dass Ihre Iteratorschnittstelle, wenn sie auf C-Arrays mit fester Länge angewendet wird, in einfache und effiziente Zeigerarithmetik zerfällt , was sie zu einer wirklich kostengünstigen Abstraktion macht.

Marcus Harrison
quelle