Warum sind Standard-Iteratorbereiche [Anfang, Ende] anstelle von [Anfang, Ende]?

204

Warum definiert der Standard end()als eins nach dem Ende anstatt am tatsächlichen Ende?

Hündchen
quelle
19
Ich vermute, "weil das der Standard sagt" wird es nicht schneiden, oder? :)
Luchian Grigore
39
@LuchianGrigore: Natürlich nicht. Das würde unseren Respekt vor den (Menschen hinter) dem Standard untergraben. Wir sollten erwarten, dass es einen Grund für die vom Standard getroffenen Entscheidungen gibt.
Kerrek SB
4
Kurz gesagt, Computer zählen nicht wie Menschen. Aber wenn Sie neugierig sind, warum Menschen nicht wie Computer zählen, empfehle ich The Nothing that Is: Eine Naturgeschichte von Null, um einen detaillierten Blick auf die Schwierigkeiten zu werfen, die Menschen hatten, als sie herausfanden, dass es eine Zahl gibt, die eins weniger ist als eines.
John McFarlane
8
Da es nur einen Weg gibt, "letzten" zu generieren, ist er oft nicht billig, weil er real sein muss. "Du bist vom Ende der Klippe gefallen" zu generieren ist immer billig, viele mögliche Darstellungen reichen aus. (nichtig *) "ahhhhhhh" wird gut tun.
Hans Passant
6
Ich schaute auf das Datum der Frage und für eine Sekunde dachte ich, Sie machten Witze.
Asaf

Antworten:

286

Das beste Argument ist das von Dijkstra selbst :

  • Sie wollen , dass die Größe des Bereichs ein einfaches Unterschied zu Ende  -  beginnen ;

  • Das Einschließen der Untergrenze ist "natürlicher", wenn Sequenzen zu leeren degenerieren, und auch, weil die Alternative (mit Ausnahme der Untergrenze) die Existenz eines "Eins-vor-dem-Anfang" -Sentinelwerts erfordern würde.

Sie müssen immer noch begründen, warum Sie anfangen, bei Null anstatt bei Eins zu zählen, aber das war nicht Teil Ihrer Frage.

Die Weisheit hinter der Konvention [Anfang, Ende] zahlt sich immer wieder aus, wenn Sie einen Algorithmus haben, der sich mit mehreren verschachtelten oder iterierten Aufrufen von bereichsbasierten Konstruktionen befasst, die sich auf natürliche Weise verketten. Im Gegensatz dazu würde die Verwendung eines doppelt geschlossenen Bereichs zu einzelnen und äußerst unangenehmen und verrauschten Codes führen. Betrachten Sie zum Beispiel eine Partition [ n 0 , n 1 ) [ n 1 , n 2 ) [ n 2 , n 3 ). Ein weiteres Beispiel ist die Standard-Iterationsschleife for (it = begin; it != end; ++it), die end - beginZeiten ausführt. Der entsprechende Code wäre viel weniger lesbar, wenn beide Enden inklusive wären - und stellen Sie sich vor, wie Sie mit leeren Bereichen umgehen würden.

Schließlich können wir auch ein gutes Argument dafür liefern, warum das Zählen bei Null beginnen sollte: Mit der halboffenen Konvention für Bereiche, die wir gerade festgelegt haben, wenn Sie einen Bereich von N Elementen erhalten (z. B. um die Mitglieder eines Arrays aufzulisten), dann 0 ist der natürliche "Anfang", so dass Sie den Bereich als [0, N ) schreiben können , ohne umständliche Offsets oder Korrekturen.

Kurz gesagt: Die Tatsache, dass wir die Zahl 1in bereichsbasierten Algorithmen nicht überall sehen, ist eine direkte Folge und Motivation für die Konvention [Anfang, Ende].

Kerrek SB
quelle
2
Das typische C für eine Schleife, die über ein Array der Größe N iteriert, ist "für (i = 0; i <N; i ++) a [i] = 0;". Jetzt können Sie das nicht direkt mit Iteratoren ausdrücken - viele Leute haben Zeit damit verschwendet, <aussagekräftig zu machen. Es ist jedoch fast genauso offensichtlich, "für (i = 0; i! = N; i ++) ..." zu sagen. Daher ist es praktisch, 0 zu beginnen und N zu beenden.
Krazy Glew
3
@ KrazyGlew: Ich habe nicht absichtlich Typen in mein Loop-Beispiel eingefügt. Wenn Sie an beginund endals ints mit Werten 0bzw. denken N, passt es perfekt. Es ist wohl der !=Zustand, der natürlicher ist als der traditionelle <, aber das haben wir erst entdeckt, als wir über allgemeinere Sammlungen nachdachten.
Kerrek SB
4
@KerrekSB: Ich stimme zu, dass "wir nie herausgefunden haben, dass [! = Besser ist], bis wir anfingen, über allgemeinere Sammlungen nachzudenken." IMHO, das ist eines der Dinge, für die Stepanov Anerkennung verdient - als jemand, der versucht hat, solche Vorlagenbibliotheken vor der STL zu schreiben. Ich werde jedoch darüber streiten, dass "! =" Natürlicher ist - oder vielmehr, dass! = Wahrscheinlich Fehler eingeführt hat, die <fangen würden. Denken Sie nach (i = 0; i! = 100; i + = 3) ...
Krazy Glew
@KrazyGlew: Ihr letzter Punkt ist etwas unangebracht, da die Sequenz {0, 3, 6, ..., 99} nicht die Form hat, nach der das OP gefragt hat. Wenn Sie dies wünschen, sollten Sie eine ++inkrementierbare Iteratorvorlage schreiben step_by<3>, die dann die ursprünglich angekündigte Semantik aufweist.
Kerrek SB
@KrazyGlew Auch wenn <irgendwann einen Fehler verbergen würde, ist es trotzdem ein Fehler . Wenn jemand verwendet, !=wann er verwenden sollte <, dann ist es ein Fehler. Übrigens ist dieser Fehlerkönig bei Unit-Tests oder Behauptungen leicht zu finden.
Phil 1970
80

Tatsächlich ist eine Menge iteratorbezogener Dinge plötzlich viel sinnvoller, wenn man bedenkt, dass die Iteratoren nicht auf die Elemente der Sequenz zeigen, sondern dazwischen , wobei die Dereferenzierung auf das nächste Element direkt darauf zugreift. Dann macht der Iterator "one past end" plötzlich Sinn:

   +---+---+---+---+
   | A | B | C | D |
   +---+---+---+---+
   ^               ^
   |               |
 begin            end

Zeigt offensichtlich beginauf den Anfang der Sequenz und endauf das Ende derselben Sequenz. Die Dereferenzierung begingreift auf das Element zu A, und die Dereferenzierung endmacht keinen Sinn, da kein Elementrecht vorhanden ist. Auch das Hinzufügen eines Iterators iin der Mitte ergibt

   +---+---+---+---+
   | A | B | C | D |
   +---+---+---+---+
   ^       ^       ^
   |       |       |
 begin     i      end

und Sie sehen sofort, dass der Bereich der Elemente von beginbis idie Elemente enthält Aund Bwährend der Bereich der Elemente von ibis enddie Elemente Cund enthält D. Dereferenzierung igibt das Element rechts davon, das ist das erste Element der zweiten Sequenz.

Sogar das "Off-by-One" für Reverse-Iteratoren wird auf diese Weise plötzlich offensichtlich: Das Umkehren dieser Sequenz ergibt:

   +---+---+---+---+
   | D | C | B | A |
   +---+---+---+---+
   ^       ^       ^
   |       |       |
rbegin     ri     rend
 (end)    (i)   (begin)

Ich habe die entsprechenden nicht-umgekehrten (Basis-) Iteratoren in Klammern unten geschrieben. Sie sehen, der umgekehrte Iterator von i(den ich benannt habe ri) zeigt immer noch zwischen den Elementen Bund C. Aufgrund der Umkehrung der Reihenfolge befindet sich das Element jetzt Brechts davon.

Celtschk
quelle
2
Dies ist meiner Meinung nach die beste Antwort, obwohl ich denke, dass es besser veranschaulicht werden könnte, wenn die Iteratoren auf Zahlen zeigen und die Elemente zwischen den Zahlen liegen (die Syntax foo[i]) ist eine Abkürzung für das Element unmittelbar nach der Position i). Wenn ich darüber nachdenke, frage ich mich, ob es für eine Sprache nützlich sein könnte, separate Operatoren für "Element unmittelbar nach Position i" und "Element unmittelbar vor Position i" zu haben, da viele Algorithmen mit Paaren benachbarter Elemente arbeiten und sagen: " Die Gegenstände auf beiden Seiten der Position i "können sauberer sein als" Die Gegenstände an den Positionen i und i + 1 ".
Supercat
@supercat: Die Zahlen sollten nicht die Iteratorpositionen / -indizes angeben, sondern die Elemente selbst. Ich werde die Zahlen durch Buchstaben ersetzen, um das klarer zu machen. In der Tat würde mit den angegebenen Zahlen begin[0](unter der Annahme eines Iterators mit wahlfreiem Zugriff) auf das Element zugegriffen werden 1, da 0meine Beispielsequenz kein Element enthält.
Celtschk
Warum wird das Wort "begin" anstelle von "start" verwendet? "Beginnen" ist schließlich ein Verb.
user1741137
@ user1741137 Ich denke, "begin" soll die Abkürzung für "begin" sein (was jetzt Sinn macht). "Anfang" ist zu lang, "Anfang" klingt nach einer guten Passform. "start" würde mit dem Verb "start" in Konflikt stehen (wenn Sie beispielsweise eine Funktion start()in Ihrer Klasse definieren müssen, um einen bestimmten Prozess zu starten oder was auch immer, wäre es ärgerlich, wenn sie mit einem bereits vorhandenen in Konflikt steht).
Fareanor
74

Warum definiert der Standard end()als eins nach dem Ende anstatt am tatsächlichen Ende?

Weil:

  1. Es vermeidet eine spezielle Behandlung für leere Bereiche. Ist für leere Bereiche begin()gleich end()&
  2. Dies macht das Endkriterium für Schleifen, die über die Elemente iterieren, einfach: Die Schleifen werden einfach fortgesetzt, solange sie end()nicht erreicht werden.
Alok Speichern
quelle
64

Weil dann

size() == end() - begin()   // For iterators for whom subtraction is valid

und Sie müssen keine unangenehmen Dinge wie tun

// Never mind that this is INVALID for input iterators...
bool empty() { return begin() == end() + 1; }

und Sie werden nicht versehentlich fehlerhaften Code wie schreiben

bool empty() { return begin() == end() - 1; }    // a typo from the first version
                                                 // of this post
                                                 // (see, it really is confusing)

bool empty() { return end() - begin() == -1; }   // Signed/unsigned mismatch
// Plus the fact that subtracting is also invalid for many iterators

Außerdem: Was würde find()zurückkehren, wenn end()auf ein gültiges Element verwiesen würde ?
Haben Sie wirklich wollen , ein anderes Mitglied genannt , invalid()die eine ungültige Iterator zurück ?!
Zwei Iteratoren sind schon schmerzhaft genug ...

Oh, und siehe diesen verwandten Beitrag .


Ebenfalls:

Wenn das endvor dem letzten Element wäre, wie würdest du insert()am wahren Ende sein?!

user541686
quelle
2
Dies ist eine stark unterschätzte Antwort. Die Beispiele sind prägnant und direkt auf den Punkt gebracht, und die "Also" wurden von niemand anderem gesagt und sind die Art von Dingen, die im Nachhinein sehr offensichtlich erscheinen, mich aber wie Enthüllungen treffen.
underscore_d
@underscore_d: Danke !! :)
user541686
Übrigens, falls ich wie ein Heuchler aussehe, weil ich nicht positiv gestimmt habe, liegt das daran, dass ich es bereits im Juli 2016 getan habe!
underscore_d
@underscore_d: hahaha ich habe es nicht mal bemerkt, aber danke! :)
user541686
22

Das Iterator-Idiom von halb geschlossenen Bereichen [begin(), end())basiert ursprünglich auf der Zeigerarithmetik für einfache Arrays. In dieser Betriebsart hätten Sie Funktionen, denen ein Array und eine Größe übergeben wurden.

void func(int* array, size_t size)

Das Konvertieren in halbgeschlossene Bereiche [begin, end)ist sehr einfach, wenn Sie über folgende Informationen verfügen:

int* begin;
int* end = array + size;

for (int* it = begin; it < end; ++it) { ... }

Es ist schwieriger, mit vollständig geschlossenen Bereichen zu arbeiten:

int* begin;
int* end = array + size - 1;

for (int* it = begin; it <= end; ++it) { ... }

Da Zeiger auf Arrays in C ++ Iteratoren sind (und die Syntax dies ermöglicht), ist das Aufrufen viel einfacher std::find(array, array + size, some_value)als das Aufrufen std::find(array, array + size - 1, some_value).


Plus, wenn Sie mit halbgeschlossenen Bereichen arbeiten, können Sie die verwenden können !=Betreiber für den End-Zustand zu überprüfen, becuase (wenn Ihr Betreiber korrekt definiert ist) <bedeutet !=.

for (int* it = begin; it != end; ++ it) { ... }

Bei vollständig geschlossenen Bereichen ist dies jedoch nicht einfach. Du steckst fest <=.

Die einzige Art von Iterator, die C ++ unterstützt <und >Operationen ausführt, sind Iteratoren mit wahlfreiem Zugriff. Wenn Sie <=für jede Iteratorklasse in C ++ einen Operator schreiben müssten, müssten Sie alle Ihre Iteratoren vollständig vergleichbar machen, und Sie hätten weniger Auswahlmöglichkeiten für die Erstellung weniger leistungsfähiger Iteratoren (z. B. der bidirektionalen Iteratoren std::listoder der Eingabeiteratoren) die funktionieren iostreams), wenn C ++ vollständig geschlossene Bereiche verwendet.

Ken Bloom
quelle
8

Wenn der end()Zeiger nach dem Ende zeigt, ist es einfach, eine Sammlung mit einer for-Schleife zu iterieren:

for (iterator it = collection.begin(); it != collection.end(); it++)
{
    DoStuff(*it);
}

Mit end()Hinweis auf das letzte Element, würde eine Schleife komplexe:

iterator it = collection.begin();
while (!collection.empty())
{
    DoStuff(*it);

    if (it == collection.end())
        break;

    it++;
}
Anders Abel
quelle
0
  1. Wenn ein Container leer ist , begin() == end().
  2. C ++ - Programmierer tendieren dazu, unter Schleifenbedingungen !=anstelle von <(weniger als) zu verwenden, daher end()ist es praktisch , auf eine Position außerhalb des Endes zu zeigen.
Andreas DM
quelle