[C++] Übergeben von Std-Algorithmus-Iteratorparametern nach Wert und Verweis


Answers

Bei bestimmten billig zu kopierenden Typen ist die Übergabe nach Wert tatsächlich schneller als die Weitergabe als Referenz. Herkömmliche Weisheit aus Tutorials usw. besagt, dass durch Bezugnahme schneller ist, aber dies gilt nicht notwendigerweise für billig zu kopierende Typen.

Wie übergibt man ein Objekt nach Wert? Sie erstellen eine Kopie davon, dh Sie nehmen den Wert und schieben ihn für den Funktionsaufruf auf den Stapel. Und wie kommst du als Referenz? Sie schieben die Speicheradresse auf den Stack, und dann muss die aufgerufene Funktion alles abrufen, was sich an dieser Adresse befindet. Jetzt können Optimierung und Caching ins Spiel kommen, um den Speicher viel billiger zu machen, aber Sie werden immer noch nicht billiger, als den exakten Wert vom Stapel zu nehmen. Was bei Iteratoren oft so einfach ist wie ein Zeiger. Welches ist ein Wort lang und so sehr billig zu kopieren.

Beachten Sie auch, dass Sie eine Const-Referenz übergeben möchten. Das bedeutet, dass es in der aufgerufenen Funktion sowieso kopiert werden müsste, damit es geändert werden kann (z. B. Inkrementieren in einer Schleife).

Question

Ich frage mich, warum in vielen Template-Algorithmen in der STL die Argumente nicht durch Referenz, sondern durch Wert übergeben werden. Hier ist ein Beispiel aus dem Header <iterator >:

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance (InputIterator first, InputIterator last);

Wenn ich zwei Iteratoren an diese Funktion übergebe, werden sie kopiert. Meine naiven Gedanken sind, dass es besser wäre, diese Iteratoren mit const-reference zu übergeben, um das Kopieren der Iterator-Objekte zu vermeiden:

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance (const InputIterator &first, const InputIterator &last);

Man könnte sagen, dass Iteratoren im Allgemeinen sehr kleine Objekte sind und dass das Kopieren nicht teuer ist. Aber auch noch: billiges Kopieren wäre teurer als gar kein Kopieren.

Was ist der Grund, dass in der STL-Version die Iteratoren nach Wert übergeben werden?

Vielen Dank!




Die meisten Algorithmen modifizieren ihre Argumente. Zum Beispiel könnte die distance wie folgt implementiert werden 1 :

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance (InputIterator first, InputIterator last) {
    typename iterator_traits<InputIterator>::difference_type result{};
    while (first++ != last)
        ++result;
    return result;
}

Dies funktioniert natürlich nicht, wenn Sie first als const Referenz übergeben werden.

Und es funktioniert auch nicht, wenn Sie es als non const Verweis übergeben, da in den meisten aufrufenden Kontexten die Objekte des Aufrufers nicht geändert werden können (z. B. wenn Sie das Ergebnis von container.begin() an die Funktion übergeben).

Natürlich könnten Sie immer noch const referenzieren, eine Kopie in der Funktion erstellen und diese dann ändern. An diesem Punkt hätten wir nichts gewonnen.

In Verbindung mit der C ++ - Standardempfehlung, dass Iteratoren leichte Typen sein sollten, die billig zu kopieren sein sollten, ist es einfacher und in den meisten Fällen effizienter , sie nach Wert zu übergeben:

Aber auch noch: billiges Kopieren wäre teurer als gar kein Kopieren.

Nicht wahr. Sie müssen auch die Referenz kopieren (die im Fall eines nicht inlinierten Funktionsaufrufs als Zeiger implementiert wird). Und dann müssen Sie den Zeiger dereferenzieren , der auch Overhead hinzufügt. Verglichen mit einer geraden Kopie, die in vielen Fällen so billig wie das Kopieren eines Zeigers sein kann und keinen Dereferenzierungsaufwand verursacht.

1 Natürlich wäre eine echte Implementierung für Random-Access-Iteratoren optimiert, um eine konstante anstelle einer linearen Laufzeit zu haben. Die obige Implementierung dient nur zur Veranschaulichung.