Welche ist effizienter und welche ist bequemer zu benutzen?Wird STL size() auf konstanter Komplexität oder Linear ausgeführt?
std::vector<int> V(Some Integers);
1)
for(int i=0 ; i<V.size() ; ++i){
std::cout<<V[i]<<" "; // print all integers
}
2)
int size=V.size();
for(int i=0 ; i<size ; ++i){
std::cout<<V[i]<<" "; // printing all integers
}
Das verwendete auf dem Behälter und C++ Standard abhängt. Zum Beispiel könnte std::set::size() in C++03 in bis zu linearer Komplexität arbeiten. Wie für C++14, size() alle häufig verwendeten Behälter (zumindest, vector, list, set, map, unordered_set, unordered_map, queue und deque) verläuft in konstanter Zeit.
Zusatz: Nebenbei, iterating von begin() bis end() ist in der Regel effizienter, und eine For-Range-Schleife mehr idiomatische verwenden. Auch +1. – Deduplicator
Die Ausnahme, die Sie suchen, ist ['std :: forward_list'] (http://en.cppreference.com/w/cpp/container/forward_list), die nicht' size() 'hat. – Deduplicator
Für diejenigen von euch, die neugierig sind, warum dies der Fall ist, in 23.1 'size()' ist nicht verpflichtet, konstante Komplexität zu haben, da es sagt "sollte haben" statt "soll". Willkommen in der Sprache Anwalt Hölle. –
size läuft normalerweise in konstanter Zeit. Die Hauptsorge ist, ob es läuft. Der Compiler könnte erkennen, dass nichts, was Sie tun, die Größe ändert, aber dies könnte fehlschlagen. In diesem Fall könnten Sie jede Iteration mit einem Funktionsaufruf versehen, der sogar in konstanter Zeit langsamer als ein einfacher ganzzahliger Vergleich sein könnte (oder nicht).
Wenn Sie einen komplexen Container haben (nicht ein Vektor, wo die Größe höchstwahrscheinlich schon eine einfache Variable ist), und Sie machen komplexe Dinge zu seinen Elementen (wo Sie die Größe nicht ändern, aber es gibt eine Chance der Compiler merkt es nicht), und Sie sind extrem zeitgebunden (Loop wird millionenfach ausgeführt), dann könnte es sinnvoll sein, die zweite Version zu verwenden.
Oder umzuformulieren: Optimierung nur, wenn es ein Flaschenhals ist und der Compiler nicht schlau genug ist. –
Ja könnte man dazu zusammenfassen :) –
'std :: vector :: size()' ist 'O (1)' (konstante) Komplexität. Ich würde erwarten, dass (1) und (2) beim Release-Build nicht unterscheidbar sind; Ein Optimierer sollte 'size()' -Aufrufe aus der Schleife hissen können. –
Aber Standard sagt nur, dass es von O (1) Komplexität ist. Es kann einen gespeicherten Größenwert zurückgeben oder eine "end-begin" -Zeigerdifferenz berechnen. Und wenn Sie 'inline' ausschalten (wie in Debug-Builds), wird der erste Weg Funktionen aufrufen. Der zweite Weg ist zuverlässiger, um schnell zu sein. – ilotXXI
Ich würde vorschlagen 'für (const auto & elem: V)'. Es ist nicht nur garantiert, die "Endbedingung" nur einmal zu bewerten. Es ist auch viel einfacher zu lesen. –