Wird eine std :: list teuer?

Question

Ich frage mich, ob das Zurückgeben einer Liste, anstatt einen Zeiger auf eins zurückzugeben, im Hinblick auf die Leistung teuer war, denn wenn ich mich erinnere, hat eine Liste nicht viele Attribute (ist das nicht etwa 3 Zeiger? für die aktuelle Position, eine für den Anfang und eine für das Ende?).

Answer 1

Wenn Sie eine std::list nach Wert zurückgeben, wird nicht nur der Listenkopf kopiert, sondern ein Listenknoten pro Element in der Liste kopiert. Also ja, für eine große Liste ist es teuer.

Wenn die Liste in der Funktion erstellt wird, die sie zurückgibt, können Sie möglicherweise von der benannten Rückgabewertoptimierung profitieren, um eine unnötige Kopie zu vermeiden. Das ist jedoch spezifisch für Ihren Compiler. Es gilt nie, wenn die Liste zum Beispiel bereits vor dem Aufruf der Funktion existiert (zB wenn es sich um eine Elementvariable eines Objekts handelt).

Ein gängiges Idiom in C++, um die Rückgabe von Containern nach Wert zu vermeiden, ist die Verwendung eines Ausgabe-Iterators als Parameter. Also statt:

std::list<int> getListOfInts() { 
    std::list<int> l; 
    for (int i = 0; i < 10; ++i) { 
     l.push_back(i); 
    } 
    return l; 
} 

Sie tun:

template<typename OutputIterator> 
void getInts(OutputIterator out) { 
    for (int i = 0; i < 10; ++i) { 
     *(out++) = i; 
    } 
} 

Dann wird der Anrufer tut:

std::list<int> l; 
getInts(std::back_inserter(l)); 

Oft, wenn der Compiler inlining und Optimierung abgeschlossen ist, wird der Code ist mehr oder weniger identisch .

Der Vorteil davon ist, dass der Aufrufer nicht an eine bestimmte Sammlung gebunden ist - zum Beispiel kann er die Elemente zu einem Vektor anstatt einer Liste hinzugefügt haben, wenn das für die besonderen Umstände nützlicher ist. Wenn er nur jedes Element einmal sehen muss, anstatt alle zusammen, dann kann er Speicher sparen, indem er sie im Streaming-Modus verarbeitet, indem er einen eigenen Ausgabe-Iterator verwendet.

Die Nachteile sind die gleichen wie bei jedem Vorlagencode: Die Implementierung muss dem Aufrufer zum Zeitpunkt der Kompilierung zur Verfügung stehen, und Sie können am Ende viele "doppelten" Objektcode für mehrere Instanzen der Vorlage erhalten. Natürlich können Sie das gleiche Muster ohne Vorlagen verwenden, indem Sie einen Funktionszeiger (plus einen Benutzerdatenzeiger, falls gewünscht) als Parameter verwenden und ihn einmal mit jedem Element aufrufen oder indem Sie eine abstrakte Klasse von IntVisitor mit einem rein virtuellen Member definieren Funktion, und der Anrufer eine Instanz davon bereitstellen.

[Bearbeiten: T.E.D weist in einem Kommentar darauf hin, dass eine andere Möglichkeit, die Kopie ohne Verwendung von Vorlagen zu vermeiden, darin besteht, dass der Aufrufer eine Liste als Referenz übergibt. Dies funktioniert sicherlich, es gibt dem Anrufer weniger Flexibilität als das Template und ist daher nicht das von der STL verwendete Idiom. Es ist eine gute Option, wenn Sie den oben beschriebenen "Vorteil" nicht haben wollen. Eine der ursprünglichen Absichten hinter der STL besteht jedoch darin, "Algorithmen" (in diesem Fall was auch immer die Werte bestimmt) von "Containern" zu trennen (in diesem Fall die Tatsache, dass die Werte zufällig in einer Liste gespeichert sind, im Gegensatz zu einem Vektor oder einem Array oder einem Selbstsortier-Set oder einfach ausgedruckt, ohne sie zu speichern.]

Answer 2

Ich glaube, der Copy-Konstruktor wird aufgerufen.

Answer 3

Es kann teuer sein, da es jedes Element in der Liste kopiert. Noch wichtiger ist, dass es ein anderes Verhalten hat: Möchten Sie eine Kopie der Liste oder möchten Sie einen Zeiger auf die ursprüngliche Liste?

Answer 4

Wenn Sie als Wert zurückgeben, wird der Kopierkonstruktor aufgerufen und die Elemente werden nacheinander kopiert. Manchmal werden Sie durch die benannte Wertoptimierung gespeichert, auf die Onebyone hingewiesen hat.

Ihre wichtigsten Optionen, um die Kopie, um sicherzustellen, wird nicht stattfinden, sind:

• Pass in einer Liste von Referenz durch die Funktion ausgefüllt werden. Auf diese Weise teilen Sie der Funktion mit, wo die Daten abgelegt werden sollen, und es muss keine Kopie erstellt werden, da Sie sie an ihrem endgültigen Platz ablegen.
• Ordnen Sie eine Liste auf dem Heap zu und geben Sie sie zurück. Sie sollten es in einem intelligenten Zeiger wie einem std :: auto_ptr oder einem boost :: shared_ptr zurückgeben, um sicherzustellen, dass es gelöscht wird und ausnahmesicher ist.

Answer 5

Es (wie immer) abhängt. Der Kopierkonstruktor kann im folgenden Code durch den Rückgabecode aufgerufen werden oder nicht.

std::list<int> foo() { 
    std::list<int> bar; 
    // ... 
    return bar; 
}; 

Es kann nicht geltend gemacht werden, wenn der Compiler return value optimization gilt. Wenn der Kopierkonstruktor aufgerufen wird, ist es wahrscheinlich relativ zu einem Zeiger für größere Listen teurer, und wenn es nicht aufgerufen wird, ist es schneller, die gerade Liste zurückzugeben (weil es eine dynamische Zuordnung vermeidet)

Persönlich mache ich mir darüber keine Sorgen und gebe die gerade Liste zurück. Dann, nur wenn mein Profiler dies ein Problem sagt, betrachte ich Optimierungen.