Was ist der effektivste Weg, um den Index eines Iterators eines std :: vector zu erhalten?

438

Ich iteriere über einen Vektor und benötige den Index, auf den der Iterator gerade zeigt. AFAIK Dies kann auf zwei Arten geschehen:

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

Was sind die Vor- und Nachteile dieser Methoden?

Kairol
quelle

Antworten:

557

Ich würde es it - vec.begin()genau aus dem entgegengesetzten Grund bevorzugen , den Naveen angegeben hat: Es würde also nicht kompiliert, wenn Sie den Vektor in eine Liste ändern. Wenn Sie dies während jeder Iteration tun, können Sie leicht einen O (n) -Algorithmus in einen O (n ^ 2) -Algorithmus verwandeln.

Eine andere Option, wenn Sie während der Iteration nicht im Container herumspringen, besteht darin, den Index als zweiten Schleifenzähler beizubehalten.

Hinweis: itist ein gebräuchlicher Name für einen Container-Iterator std::container_type::iterator it;.

Onkel Bens
quelle
3
Einverstanden. Ich würde sagen, dass das Minuszeichen am besten ist, aber es wäre besser, einen zweiten Schleifenzähler beizubehalten, als std :: distance zu verwenden, gerade weil diese Funktion langsam sein könnte.
Steven Sudit
28
Was zum Teufel ist das it?
Steinfeld
32
@Steinfeld ist ein Iterator. std::container_type::iterator it;
Matt Munson
2
Das Hinzufügen eines zweiten Schleifenzählers ist eine so offensichtliche Lösung, dass es mir peinlich ist, dass ich nicht daran gedacht habe.
Mordred
3
@Swapnil std::listbietet keinen direkten Zugriff auf Elemente anhand ihrer Position. Wenn Sie dies nicht können list[5], sollten Sie dies nicht können list.begin() + 5.
José Tomás Tocino
135

Ich würde es vorziehen, std::distance(vec.begin(), it)da ich den Container ohne Codeänderungen ändern kann. Wenn Sie sich beispielsweise für die Verwendung entscheiden, std::listanstatt std::vectoreinen Iterator mit wahlfreiem Zugriff bereitzustellen, wird Ihr Code weiterhin kompiliert. Da std :: distance die optimale Methode in Abhängigkeit von den Iteratormerkmalen aufnimmt, treten auch keine Leistungseinbußen auf.

Naveen
quelle
50
Wenn Sie einen Container ohne Iteratoren mit wahlfreiem Zugriff verwenden, ist es am besten , solche Entfernungen nicht zu berechnen, da dies ineffizient ist
Eli Bendersky
6
@Eli: Ich stimme dem zu, aber in einem ganz besonderen Fall, wenn es wirklich erforderlich ist, wird dieser Code trotzdem funktionieren.
Naveen
9
Ich denke, der Code sollte sowieso geändert werden, wenn sich der Container ändert - eine std :: list-Variable mit dem Namen zu haben, vecist eine schlechte Nachricht. Wenn der Code so umgeschrieben wurde, dass er generisch ist und den Containertyp als Vorlagenparameter verwendet, können (und sollten) wir über den Umgang mit Iteratoren mit nicht wahlfreiem Zugriff sprechen ;-)
Steve Jessop
1
Und Spezialisierung für bestimmte Container.
ScaryAardvark
19
@SteveJessop: Einen Vektor namens zu haben, vecist auch eine ziemlich schlechte Nachricht.
Fluss Tam
74

Wie UncleBens und Naveen gezeigt haben, gibt es für beide gute Gründe. Welches "besser" ist, hängt davon ab, welches Verhalten Sie möchten: Möchten Sie ein Verhalten mit konstanter Zeit garantieren oder möchten Sie, dass es bei Bedarf auf die lineare Zeit zurückgreift?

it - vec.begin()nimmt konstante Zeit in operator -Anspruch, ist jedoch nur für Iteratoren mit wahlfreiem Zugriff definiert, sodass der Code beispielsweise mit Listeniteratoren überhaupt nicht kompiliert wird.

std::distance(vec.begin(), it) funktioniert für alle Iteratortypen, ist jedoch nur dann eine Operation mit konstanter Zeit, wenn sie für Iteratoren mit wahlfreiem Zugriff verwendet wird.

Keiner ist "besser". Verwenden Sie diejenige, die das tut, was Sie brauchen.

jalf
quelle
1
Ich bin in der Vergangenheit dem verfallen. Verwenden von std :: distance für zwei std :: map-Iteratoren und Erwarten von O (N).
ScaryAardvark
6
@ ScaryAardvark: Meinst du nicht, dass es O (1) ist?
Jalf
12

Ich mag dieses: it - vec.begin()weil es mir klar sagt "Distanz vom Anfang". Bei Iteratoren sind wir es gewohnt, arithmetisch zu denken, daher ist das -Vorzeichen hier der klarste Indikator.

Eli Bendersky
quelle
19
Es ist klarer, Subtraktion zu verwenden, um die Entfernung zu finden, als das Wort buchstäblich zu verwenden distance?
Travis Gockel
4
@Travis, für mich ist es. Es ist eine Frage des Geschmacks und der Gewohnheit. Wir sagen it++und nicht so etwas std::increment(it), nicht wahr? Würde das nicht auch als weniger klar gelten?
Eli Bendersky
3
Der ++Operator wird als Teil der STL-Sequenzen definiert, wie wir den Iterator inkrementieren. std::distanceberechnet die Anzahl der Elemente zwischen dem ersten und dem letzten Element. Die Tatsache, dass der -Bediener arbeitet, ist nur ein Zufall.
Travis Gockel
3
@ MSalters: und doch verwenden wir ++ :-)
Eli Bendersky
10

Wenn Sie Ihren Algorithmus bereits auf die Verwendung von a std::vector::iteratorund std::vector::iteratoronly beschränkt / fest codiert haben , spielt es keine Rolle, welche Methode Sie am Ende verwenden werden. Ihr Algorithmus ist bereits über den Punkt hinaus konkretisiert, an dem die Auswahl eines der beiden einen Unterschied machen kann. Beide machen genau das Gleiche. Es ist nur eine Frage der persönlichen Präferenz. Ich persönlich würde explizite Subtraktion verwenden.

Wenn Sie andererseits einen höheren Grad an Allgemeinheit in Ihrem Algorithmus beibehalten möchten, nämlich die Möglichkeit zuzulassen, dass er eines Tages auf einen anderen Iteratortyp angewendet wird, hängt die beste Methode von Ihrer Absicht ab . Dies hängt davon ab, wie restriktiv Sie in Bezug auf den hier verwendeten Iteratortyp sein möchten.

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

  • Wenn Sie verwenden distance, unterstützt Ihr Algorithmus eine viel breitere Klasse von Iteratoren: Eingabeiteratoren.

Natürlich ist die Berechnung distancefür Iteratoren mit nicht wahlfreiem Zugriff im Allgemeinen eine ineffiziente Operation (während sie für solche mit wahlfreiem Zugriff ebenso effizient ist wie die Subtraktion). Es liegt an Ihnen, zu entscheiden, ob Ihr Algorithmus für Iteratoren mit nicht wahlfreiem Zugriff in Bezug auf die Effizienz sinnvoll ist . Wenn der daraus resultierende Effizienzverlust so verheerend ist, dass Ihr Algorithmus völlig unbrauchbar wird, sollten Sie sich besser an die Subtraktion halten, um ineffiziente Verwendungen zu verhindern und den Benutzer zu zwingen, nach alternativen Lösungen für andere Iteratortypen zu suchen. Wenn die Effizienz mit Iteratoren ohne wahlfreien Zugriff immer noch im nutzbaren Bereich liegt, sollten Sie distancedie Tatsache verwenden und dokumentieren, dass der Algorithmus mit Iteratoren mit wahlfreiem Zugriff besser funktioniert.

Ameise
quelle
4

Laut http://www.cplusplus.com/reference/std/iterator/distance/ verwendet die Distanzmethode den Operator , da vec.begin()es sich um einen Iterator mit wahlfreiem Zugriff handelt- .

Die Antwort ist also aus Sicht der Leistung dieselbe, aber vielleicht ist die Verwendung distance()einfacher zu verstehen, wenn jemand Ihren Code lesen und verstehen müsste.

Stéphane
quelle
3

Ich würde die -Variante std::vectornur für verwenden - es ist ziemlich klar, was gemeint ist, und die Einfachheit der Operation (die nicht mehr als eine Zeigersubtraktion ist) wird durch die Syntax ausgedrückt ( distanceauf der anderen Seite klingt sie wie Pythonagoras auf der erste Lesung, nicht wahr?). Wie UncleBen hervorhebt, -fungiert es auch als statische Behauptung, falls vectorversehentlich auf geändert wird list.

Ich denke auch, dass es viel häufiger vorkommt - ich habe jedoch keine Zahlen, die dies beweisen. Hauptargument: it - vec.begin()ist im Quellcode kürzer - weniger Schreibarbeit, weniger Platzbedarf. Da es klar ist, dass die richtige Antwort auf Ihre Frage Geschmackssache ist, kann dies auch ein gültiges Argument sein.

Alexander Gessler
quelle
0

Hier ist ein Beispiel, um "alle" Vorkommen von 10 zusammen mit dem Index zu finden. Ich dachte, das wäre hilfreich.

void _find_all_test()
{
    vector<int> ints;
    int val;
    while(cin >> val) ints.push_back(val);

    vector<int>::iterator it;
    it = ints.begin();
    int count = ints.size();
    do
    {
        it = find(it,ints.end(), 10);//assuming 10 as search element
        cout << *it << " found at index " << count -(ints.end() - it) << endl;
    }while(++it != ints.end()); 
}
Srikanth Batthula
quelle