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.
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].
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 |+---+---+---+---+^^||beginend
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.
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:
Es vermeidet eine spezielle Behandlung für leere Bereiche. Ist für leere Bereiche begin()gleich
end()&
Dies macht das Endkriterium für Schleifen, die über die Elemente iterieren, einfach: Die Schleifen werden einfach fortgesetzt, solange sie end()nicht erreicht werden.
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(){returnbegin()==end()+1;}
und Sie werden nicht versehentlich fehlerhaften Code wie schreiben
bool empty(){returnbegin()==end()-1;}// a typo from the first version// of this post// (see, it really is confusing)bool empty(){returnend()-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 ...
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.
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.
Antworten:
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)
, dieend - begin
Zeiten 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
1
in bereichsbasierten Algorithmen nicht überall sehen, ist eine direkte Folge und Motivation für die Konvention [Anfang, Ende].quelle
begin
undend
alsint
s mit Werten0
bzw. denkenN
, 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.++
inkrementierbare Iteratorvorlage schreibenstep_by<3>
, die dann die ursprünglich angekündigte Semantik aufweist.!=
wann er verwenden sollte<
, dann ist es ein Fehler. Übrigens ist dieser Fehlerkönig bei Unit-Tests oder Behauptungen leicht zu finden.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:
Zeigt offensichtlich
begin
auf den Anfang der Sequenz undend
auf das Ende derselben Sequenz. Die Dereferenzierungbegin
greift auf das Element zuA
, und die Dereferenzierungend
macht keinen Sinn, da kein Elementrecht vorhanden ist. Auch das Hinzufügen eines Iteratorsi
in der Mitte ergibtund Sie sehen sofort, dass der Bereich der Elemente von
begin
bisi
die Elemente enthältA
undB
während der Bereich der Elemente voni
bisend
die ElementeC
und enthältD
. Dereferenzierungi
gibt 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:
Ich habe die entsprechenden nicht-umgekehrten (Basis-) Iteratoren in Klammern unten geschrieben. Sie sehen, der umgekehrte Iterator von
i
(den ich benannt haberi
) zeigt immer noch zwischen den ElementenB
undC
. Aufgrund der Umkehrung der Reihenfolge befindet sich das Element jetztB
rechts davon.quelle
foo[i]
) ist eine Abkürzung für das Element unmittelbar nach der Positioni
). 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 ".begin[0]
(unter der Annahme eines Iterators mit wahlfreiem Zugriff) auf das Element zugegriffen werden1
, da0
meine Beispielsequenz kein Element enthält.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).Warum definiert der Standard
end()
als eins nach dem Ende anstatt am tatsächlichen Ende?Weil:
begin()
gleichend()
&end()
nicht erreicht werden.quelle
Weil dann
und Sie müssen keine unangenehmen Dinge wie tun
und Sie werden nicht versehentlich fehlerhaften Code wie schreiben
Außerdem: Was würde
find()
zurückkehren, wennend()
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
end
vor dem letzten Element wäre, wie würdest duinsert()
am wahren Ende sein?!quelle
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.Das Konvertieren in halbgeschlossene Bereiche
[begin, end)
ist sehr einfach, wenn Sie über folgende Informationen verfügen:Es ist schwieriger, mit vollständig geschlossenen Bereichen zu arbeiten:
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 Aufrufenstd::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!=
.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 Iteratorenstd::list
oder der Eingabeiteratoren) die funktioniereniostreams
), wenn C ++ vollständig geschlossene Bereiche verwendet.quelle
Wenn der
end()
Zeiger nach dem Ende zeigt, ist es einfach, eine Sammlung mit einer for-Schleife zu iterieren:Mit
end()
Hinweis auf das letzte Element, würde eine Schleife komplexe:quelle
begin() == end()
.!=
anstelle von<
(weniger als) zu verwenden, daherend()
ist es praktisch , auf eine Position außerhalb des Endes zu zeigen.quelle