Warum Iteratoren anstelle von Array-Indizes verwenden?

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?

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.

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.

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.

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.

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

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.

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.

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 .

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.

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
}

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
}

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

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

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
}
'

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.

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.

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.

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

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.

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.

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.

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.

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.

• 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.

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) { ... }.

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.

Für die Unabhängigkeit der Container

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;
    }

}

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.

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.