Warum nehmen alle <algorithm> -Funktionen nur Bereiche an, keine Container?

49

Es gibt viele nützliche Funktionen in <algorithm>, aber alle arbeiten mit "Sequenzen" - Paaren von Iteratoren. Wenn ich zB einen Container habe und darauf laufen möchte std::accumulate, muss ich schreiben:

std::vector<int> myContainer = ...;
int sum = std::accumulate(myContainer.begin(), myContainer.end(), 0);

Wenn alles, was ich vorhabe, ist:

int sum = std::accumulate(myContainer, 0);

Welches ist ein bisschen lesbarer und klarer, in meinen Augen.

Jetzt sehe ich, dass es Fälle geben kann, in denen Sie nur Teile eines Containers bearbeiten möchten. Daher ist es auf jeden Fall nützlich, die Möglichkeit zu haben , Bereiche zu passieren. Aber zumindest nach meiner Erfahrung ist das ein seltener Sonderfall. Normalerweise möchte ich ganze Container bearbeiten.

Es ist einfach , eine Wrapper - Funktion zu schreiben , die einen Behälter und Anrufe nehmen begin()und end()auf mich, aber solche Komfortfunktionen sind nicht in der Standard - Bibliothek enthalten.

Ich würde gerne die Gründe für diese Wahl des STL-Designs erfahren.

tödliche Gitarre
quelle
7
Bietet die STL in der Regel Convenience-Wrapper, oder folgt sie der älteren C ++ - Richtlinie, nach der Sie sich jetzt selbst erschießen müssen?
Kilian Foth
2
Um es festzuhalten: Anstatt einen eigenen Wrapper zu schreiben, sollten Sie die Algorithmus-Wrapper in Boost.Range verwenden. in diesem Fallboost::accumulate
ecatmur

Antworten:

40

... es ist auf jeden Fall nützlich, die Möglichkeit zu haben, Entfernungen zu überwinden. Aber zumindest nach meiner Erfahrung ist das ein seltener Sonderfall. Normalerweise möchte ich ganze Container bearbeiten

Es mag nach Ihrer Erfahrung ein seltener Sonderfall sein , aber in Wirklichkeit ist der gesamte Container der Sonderfall, und der willkürliche Bereich ist der allgemeine Fall.

Sie haben bereits bemerkt, dass Sie den gesamten Containerfall über die aktuelle Schnittstelle implementieren können, aber nicht umgekehrt.

Der Bibliotheksschreiber hatte also die Wahl, zwei Schnittstellen im Vorfeld zu implementieren oder nur eine, die noch alle Fälle abdeckt.


Es ist einfach, eine Wrapper-Funktion zu schreiben, die einen Container entgegennimmt und darin begin () und end () aufruft. Solche praktischen Funktionen sind jedoch nicht in der Standardbibliothek enthalten

Richtig, zumal die kostenlosen Funktionen std::beginund std::endjetzt enthalten sind.

Nehmen wir also an, die Bibliothek bietet die Bequemlichkeitsüberladung:

template <typename Container>
void sort(Container &c) {
  sort(begin(c), end(c));
}

Jetzt muss auch die äquivalente Überladung bereitgestellt werden, indem ein Vergleichs-Funktor verwendet wird, und wir müssen die Äquivalente für jeden anderen Algorithmus bereitstellen.

Aber wir haben zumindest jeden Fall abgedeckt, in dem wir mit einem vollen Container arbeiten wollen, oder? Nicht ganz. Erwägen

std::for_each(c.rbegin(), c.rend(), foo);

Wenn wir Container rückwärts verarbeiten möchten , benötigen wir eine andere Methode (oder ein Methodenpaar) pro vorhandenem Algorithmus.


Der bereichsbezogene Ansatz ist also im einfachen Sinne allgemeiner:

  • es kann alles, was die Vollcontainerversion kann
  • Der Gesamtcontainer-Ansatz verdoppelt oder verdreifacht die Anzahl der erforderlichen Überladungen, ist jedoch immer noch weniger leistungsfähig
  • Die bereichsbasierten Algorithmen sind auch zusammensetzbar (Sie können Iteratoradapter stapeln oder verketten, obwohl dies in funktionalen Sprachen und Python häufiger vorkommt).

Es gibt natürlich noch einen anderen triftigen Grund: Es war bereits eine Menge Arbeit, die STL zu standardisieren, und das Aufblasen mit Convenience-Wrappern, bevor sie weit verbreitet war, würde die begrenzte Ausschusszeit nicht besonders belasten. Bei Interesse finden Sie hier den technischen Bericht von Stepanov & Lee

Wie in den Kommentaren erwähnt, bietet Boost.Range einen neueren Ansatz, ohne dass Änderungen am Standard erforderlich sind.

Nutzlos
quelle
9
Ich glaube nicht, dass irgendjemand, einschließlich OP, vorschlägt, für jeden einzelnen Sonderfall eine Überladung hinzuzufügen. Auch wenn "ganzer Container" seltener war als "ein beliebiger Bereich", ist es definitiv weitaus häufiger als "ganzer Container, umgekehrt". Beschränken Sie es auf f(c.begin(), c.end(), ...)und vielleicht nur auf die am häufigsten verwendete Überlastung (wie auch immer Sie das bestimmen), um zu verhindern, dass sich die Anzahl der Überlastungen verdoppelt. Außerdem sind Iteratoradapter vollständig orthogonal (wie Sie bemerken, funktionieren sie in Python einwandfrei, dessen Iteratoren sehr unterschiedlich funktionieren und nicht über die meiste Leistung verfügen, über die Sie sprechen).
3
Ich bin damit einverstanden, dass der gesamte Container weitergeleitet wird, aber ich wollte darauf hinweisen, dass es sich um eine viel kleinere Untergruppe möglicher Verwendungen handelt als die vorgeschlagene Frage. Insbesondere, weil nicht zwischen Gesamtcontainer und Teilcontainer gewählt wird, sondern zwischen Gesamtcontainer und Teilcontainer, möglicherweise umgekehrt oder anderweitig angepasst. Und ich denke, es ist fair anzunehmen, dass die wahrgenommene Komplexität der Verwendung von Adaptern größer ist, wenn Sie auch Ihre Algorithmusüberladung ändern müssen.
Nutzlos
23
Beachten Sie die Containerversion würde für alle Fälle , wenn die STL ein Range - Objekt angeboten; zb std::sort(std::range(start, stop)).
3
Im Gegenteil: Die zusammensetzbaren Funktionsalgorithmen (wie Map und Filter) nehmen ein einzelnes Objekt, das eine Sammlung darstellt, und geben ein einzelnes Objekt zurück. Sie verwenden sicherlich nichts, was einem Paar von Iteratoren ähnelt.
Svick
3
Ein Makro könnte dies tun: #define MAKE_RANGE(container) (container).begin(), (container).end()</ jk>
Ratschenfreak
21

Es stellte sich heraus, dass es einen Artikel von Herb Sutter zu diesem Thema gibt. Grundsätzlich liegt das Problem in der Mehrdeutigkeit der Überladung. Angesichts der folgenden:

template<typename Iter>
void sort( Iter, Iter ); // 1

template<typename Iter, typename Pred>
void sort( Iter, Iter, Pred ); // 2

Und das Folgende hinzufügen:

template<typename Container>
void sort( Container& ); // 3

template<typename Container, typename Pred>
void sort( Container&, Pred ); // 4

Wird es schwer zu unterscheiden 4und 1richtig machen.

Konzepte, wie sie vorgeschlagen, aber letztendlich nicht in C ++ 0x enthalten sind, hätten das gelöst, und es ist auch möglich, sie mit zu umgehen enable_if. Für einige Algorithmen ist dies überhaupt kein Problem. Aber sie haben sich dagegen entschieden.

Nachdem ich nun alle Kommentare und Antworten hier gelesen habe, denke ich, dass rangeObjekte die beste Lösung sind. Ich denke, ich werde einen Blick darauf werfen Boost.Range.

tödliche Gitarre
quelle
1
Die Verwendung von nur einem typename Iterscheint für eine strenge Sprache zu entenartig zu sein. Ich würde zB template<typename Container> void sort(typename Container::iterator, typename Container::iterator); // 1und template<template<class> Container, typename T> void sort( Container<T>&, std::function<bool(const T&)> ); // 4etc. bevorzugen (was vielleicht das Mehrdeutigkeitsproblem lösen würde)
Vlad
@Vlad: Leider funktioniert dies nicht für einfache alte Arrays, da keine T[]::iteratorverfügbar sind. Außerdem muss der richtige Iterator kein verschachtelter Typ einer Sammlung sein, sondern muss nur definiert werden std::iterator_traits.
Firegurafiku
@firegurafiku: Nun, Arrays sind mit einigen grundlegenden TMP-Tricks leicht zu spezifizieren.
Vlad
11

Grundsätzlich eine Altentscheidung. Das Iteratorkonzept basiert auf Zeigern, Container werden jedoch nicht auf Arrays modelliert. Da Arrays außerdem schwer zu übergeben sind (für die Länge wird im Allgemeinen ein nicht typisierter Vorlagenparameter benötigt), sind für eine Funktion häufig nur Zeiger verfügbar.

Aber im Nachhinein ist die Entscheidung falsch. Wir wären mit einem Range-Objekt besser dran gewesen, das entweder aus begin/endoder konstruiert werden kann begin/length. jetzt haben wir _nstattdessen mehrere Algorithmen mit Suffix.

MSalters
quelle
5

Wenn Sie sie hinzufügen, erhalten Sie keinen Strom (Sie können bereits den gesamten Container durch Aufrufen .begin()und sich .end()selbst ausführen), und der Bibliothek, die ordnungsgemäß spezifiziert, von den Anbietern zu den Bibliotheken hinzugefügt, getestet, gewartet, usw. usw.

Kurz gesagt, es ist wahrscheinlich nicht vorhanden, da es sich nicht lohnt, einen Satz zusätzlicher Vorlagen zu verwalten, um Benutzern mit ganzen Containern die Eingabe eines zusätzlichen Funktionsaufrufparameters zu ersparen.

Michael Kohne
quelle
9
Es würde mir zwar keine Macht einbringen - aber am Ende auch nicht std::getlineund immer noch ist es in der Bibliothek. Man könnte sogar sagen, dass erweiterte Kontrollstrukturen mir keine Macht verschaffen, da ich alles nur mit ifund machen kann goto. Ja, unfairer Vergleich, ich weiß;) Ich denke, ich kann die Lasten der Spezifikation / Implementierung / Wartung irgendwie verstehen, aber es ist nur eine winzige Hülle, über die wir hier sprechen, also ..
lethal-guitar
Ein winziger Wrapper kostet nichts für den Code, und vielleicht macht es keinen Sinn, in der Bibliothek zu sein.
ebasconp
-1

Mittlerweile ist http://en.wikipedia.org/wiki/C++11#Range-based_for_loop eine nette Alternative zu std::for_each. Beachten Sie, keine expliziten Iteratoren:

int a[5] = {1, 2, 3, 4, 5};
for (auto &i: a) { i *= 2; }

(Inspiriert von https://stackoverflow.com/a/694534/2097284 .)

Camille Goudeseune
quelle
1
Es wird nur für diesen Teil von <algorithm>gelöst, nicht für alle tatsächlich benötigten Algen beginund endIteratoren - aber der Vorteil kann nicht überbewertet werden! Als ich 2009 zum ersten Mal C ++ 03 ausprobierte, scheute ich mich vor Iteratoren zurück, weil es sich um Schleifen handelte, und glücklicherweise oder nicht, erlaubten meine damaligen Projekte dies. Der Neustart auf C ++ 11 im Jahr 2014 war ein unglaubliches Upgrade, die Sprache C ++ sollte es immer gewesen sein, und jetzt kann ich nicht mehr ohne auto &it: them:)
underscore_d