Was ist der effektivste Weg, um den Index eines Iterators eines std::Vektors zu ermitteln?

Question

Ich bin Iteration über einen Vektor und benötigen den Index der Iterator zeigt derzeit auf. AFAIK kann dies auf zwei Arten geschehen:

• it - vec.begin()
• std::distance(vec.begin(), it)

Was sind die Vor- und Nachteile dieser Methoden?

Answer 1

Ich würde bevorzugen it - vec.begin() genau aus dem gegenteiligen Grund, den Naveen angibt: Es ist also würde nicht kompilieren, wenn Sie den Vektor in eine Liste umwandeln. Wenn Sie dies bei jeder Iteration tun, könnten Sie leicht einen O(n)-Algorithmus in einen O(n^2)-Algorithmus verwandeln.

Eine andere Möglichkeit, wenn man während der Iteration nicht im Container herumspringt, wäre, den Index als zweiten Schleifenzähler zu behalten.

Anmerkung: it ist ein gebräuchlicher Name für einen Container-Iterator, std::container_type::iterator it; .

Answer 2

Ich würde bevorzugen std::distance(vec.begin(), it) da es mir ermöglicht, den Container ohne Codeänderungen zu ändern. Wenn Sie sich zum Beispiel für die Verwendung von std::list anstelle von std::vector die keinen Iterator für zufälligen Zugriff bietet, wird Ihr Code trotzdem kompiliert. Da std::distance die optimale Methode in Abhängigkeit von den Iterator-Eigenschaften auswählt, werden Sie auch keine Leistungseinbußen haben.

Answer 3

Wie UncleBens und Naveen gezeigt haben, gibt es für beides gute Gründe. Welches davon "besser" ist, hängt davon ab, welches Verhalten Sie wünschen: Wollen Sie ein zeitlich konstantes Verhalten garantieren, oder wollen Sie, dass es bei Bedarf auf die lineare Zeit zurückfällt?

it - vec.begin() benötigt konstante Zeit, aber die operator - ist nur für Iteratoren mit wahlfreiem Zugriff definiert, so dass der Code z. B. nicht mit Listen-Iteratoren kompiliert werden kann.

std::distance(vec.begin(), it) funktioniert bei allen Iterator-Typen, ist aber nur bei Iteratoren mit wahlfreiem Zugriff eine Operation mit konstanter Zeit.

Keines von beiden ist "besser". Verwenden Sie das, was Sie brauchen.

Answer 4

Ich mag das hier: it - vec.begin() denn für mich heißt es eindeutig "Abstand vom Anfang". Bei Iteratoren sind wir daran gewöhnt, in Begriffen der Arithmetik zu denken, daher ist die - Zeichen ist hier der deutlichste Indikator.

Answer 5

Wenn Sie Ihren Algorithmus bereits auf die Verwendung eines der folgenden Parameter beschränkt/hardcodiert haben std::vector::iterator y std::vector::iterator nur, dass es eigentlich egal ist, welche Methode Sie am Ende anwenden. Ihr Algorithmus ist bereits so ausgereift, dass es keinen Unterschied mehr macht, ob Sie die eine oder die andere Methode wählen. Sie tun beide genau das Gleiche. Es ist lediglich eine Frage der persönlichen Vorliebe. Ich persönlich würde die explizite Subtraktion verwenden.

Wenn Sie andererseits einen höheren Grad an Allgemeinheit in Ihrem Algorithmus beibehalten wollen, nämlich die Möglichkeit, dass er irgendwann in der Zukunft auf einen anderen Iterator-Typ angewendet werden kann, dann hängt die beste Methode von Ihrer Absicht ab. Es hängt davon ab, wie restriktiv Sie in Bezug auf den Iterator-Typ sein wollen, der hier verwendet werden kann.

• Wenn Sie die explizite Subtraktion verwenden, ist Ihr Algorithmus auf eine recht enge Klasse von Iteratoren beschränkt: Iteratoren mit wahlfreiem Zugriff. (Das ist es, was Sie jetzt von std::vector )

• Wenn Sie distance unterstützt Ihr Algorithmus eine viel breitere Klasse von Iteratoren: Eingabe-Iteratoren.

Natürlich ist die Berechnung distance für Iteratoren ohne Zufallszugriff ist im Allgemeinen eine ineffiziente Operation (während sie für Iteratoren mit Zufallszugriff genauso effizient ist wie die Subtraktion). Es liegt an Ihnen zu entscheiden, ob Ihr Algorithmus macht Sinn für Iteratoren mit nicht zufälligem Zugriff, was die Effizienz betrifft. Wenn der daraus resultierende Effizienzverlust so verheerend ist, dass Ihr Algorithmus völlig unbrauchbar wird, dann sollten Sie besser bei der Subtraktion bleiben, um die ineffizienten Verwendungen zu verbieten und den Benutzer zu zwingen, nach alternativen Lösungen für andere Iterator-Typen zu suchen. Wenn die Effizienz mit Nicht-Zufallszugriffs-Iteratoren noch in einem brauchbaren Bereich liegt, dann sollten Sie distance und dokumentieren die Tatsache, dass der Algorithmus besser mit Iteratoren mit wahlfreiem Zugriff funktioniert.