Was ist der Unterschied zwischen einem Sentinel- und einem End-Iterator?

Question

Beim Lesen von Eric Niebler's range proposal,
Ich bin auf den Begriff Sentinel als Ersatz für den End-Iterator gestoßen.
Ich habe eine schwierige Zeit, die Vorteile von Sentinel über einen End-Iterator zu verstehen.
Kann jemand ein klares Beispiel dafür liefern, was sentintel an die Tabelle bringt, was mit Standard-Iteratorpaaren nicht möglich ist?

„A Sentinel ist eine Abstraktion eines past-the-End-Iterator. Sentinels sind Regular Typen, die verwendet werden können, um das Ende eines Bereichs zu bezeichnen. Ein Sentinel und ein Iterator ist ein Bereich zu bezeichnen EqualityComparable Ein Sentinel bezeichnet ein Element, wenn ein Iterator gleich dem Sentinel vergleicht und ich auf dieses Element zeige. " - N4382

Ich denke, Sentinels funktionieren als Funktionen bei der Bestimmung des Endes eines Bereichs, anstatt nur die Position?

Answer 1

Sentinel ermöglicht dem End-Iterator einfach einen anderen Typ.

Die zulässigen Operationen für einen UI-Iterator sind begrenzt, dies spiegelt sich jedoch nicht in seinem Typ wider. Es ist nicht in Ordnung * ein .end() Iterator, aber der Compiler wird Sie lassen.

Ein Sentinel hat keine unäre Dereferenz, oder ++, unter anderem. Es ist im Allgemeinen so beschränkt wie die schwächsten Iteratoren, die nach dem End-Iterator liegen, aber zur Kompilierungszeit durchgesetzt werden.

Es gibt eine Belohnung. Oft ist es einfacher, den Endzustand zu erkennen, als ihn zu finden. Mit einem Sentinel kann == senden "zu erkennen, ob das andere Argument über das Ende hinaus ist" zur Kompilierzeit anstelle der Laufzeit.

Das Ergebnis ist, dass ein Code, der früher langsamer war als das C-Äquivalent, jetzt auf die Geschwindigkeitsstufe C kompiliert, z. B. durch Kopieren einer nullterminierten Zeichenfolge unter Verwendung von std::copy. Ohne Sentinels musstest du entweder scannen, um das Ende vor der Kopie zu finden, oder Iteratoren mit einem Bool-Flag mit der Aufschrift "Ich bin der Endwächter" (oder gleichwertig) übergeben und es unter == überprüfen.

Es gibt andere ähnliche Vorteile beim Arbeiten mit zählbasierten Bereichen.Darüber hinaus werden einige Dinge wie zip-Bereiche leichter auszudrücken (die End-Zip-Sentinel könnte beide Quellen Sentinels halten, und die Rückgabe gleich, wenn entweder Sentinel tut: Zip Iteratoren entweder nur den ersten Iterator vergleichen oder beide vergleichen). Ein anderer Weg darüber nachzudenken besteht darin, dass Algorithmen dazu neigen, nicht den vollen Reichtum des Iterator-Konzepts für den als den letzten Iterator übergebenen Parameter zu verwenden, und dieser Iterator wird in der Praxis sehr unterschiedlich gehandhabt. Sentinel bedeutet, dass der Aufrufer diese Tatsache ausnutzen kann, was wiederum dem Compiler ermöglicht, sie leichter auszunutzen.

---

Ein zip Bereich ist, was Sie bekommen, wenn Sie mit zwei oder mehr Bereiche, und „zip“ sie zusammen wie ein Reißverschluss beginnen. Der Bereich liegt nun über Tupel der einzelnen Bereichselemente. Durch Fortschreiten eines Zip-Iterators wird jeder der "enthaltenen" Iteratoren und dito für Dereferenzierung und Vergleich vorangetrieben.

Answer 2

Sentinels und End-Iteratoren sind ähnlich, da sie das Ende eines Bereichs markieren. Sie unterscheiden sich darin, wie dieses Ende erkannt wird; entweder testen Sie den Iterator selbst oder Sie testen den Datenwert im Iterator. Wenn Sie bereits Tests an den Daten durchführen, kann ein Sentinel Ihren Algorithmus ohne weitere Tests "kostenlos" beenden lassen. Dies kann den Code vereinfachen oder beschleunigen.

Eine sehr häufige Sentinel ist das Null-Byte, das verwendet wird, um das Ende einer Zeichenfolge zu markieren. Es ist nicht erforderlich, einen separaten Iterator für das Ende der Zeichenfolge beizubehalten. Dieser kann festgelegt werden, wenn Sie mit den Zeichen der Zeichenfolge selbst arbeiten. Der Nachteil dieser Konvention ist, dass eine Zeichenfolge kein Nullzeichen enthalten kann.

Beachten Sie, dass ich diese Antwort vor dem Lesen des Vorschlags in der Verknüpfung geschrieben habe; Dies ist die klassische Definition eines Sentinels, die möglicherweise nicht mit der dort vorgeschlagenen Definition übereinstimmt.

Answer 3

Die zentrale Motivation für die Einführung einer Sentinel ist, dass es viele Iterator-Operationen gibt, die unterstützt werden, aber normalerweise nie für den End-Iterator end() benötigt werden. Zum Beispiel gibt es kaum einen Punkt bei der Dereferenzierung über *end(), beim Inkrementieren über ++end() und so weiter (*).

Im Gegensatz dazu ist die wichtigste Verwendung von end() nur um es zu vergleichen mit einem Iterator it, um zu signalisieren, ob it am Ende der Sache ist es nur iteriert. Und wie bei der Programmierung üblich, schlagen unterschiedliche Anforderungen und unterschiedliche Anwendungen einen neuen Typ vor.

Die range-v3-Bibliothek macht diese Beobachtung zu einer Annahme (die durch ein Konzept implementiert wird): sie führt einen neuen Typ für end() ein und erfordert nur, dass sie mit dem entsprechenden Iterator gleichwertig ist - aber nicht benötigt die üblichen Iterator-Operationen). Dieser neue Typ von end() heißt Sentinel.

Der Hauptvorteil hier ist die gewonnene Abstraktion und bessere Trennung von Belangen, auf deren Grundlage der Compiler möglicherweise eine bessere Optimierung durchführen kann. Im Code ist die Grundidee dieses (diese nur zur Erklärung und hat nichts mit dem Range-v3-Bibliothek zu tun):

struct my_iterator; //some iterator 
struct my_sentinel 
{ 
    bool is_at_end(my_iterator it) const 
    { 
     //here implement the logic when the iterator is at the end 
    } 
}; 

auto operator==(my_iterator it, my_sentinel s) //also for (my_sentinel s, my_iterator it) 
{ 
    return s.is_at_end(it); 
} 

die Abstraktion sehen? Jetzt können Sie implementieren jede überprüfen Sie in der is_at_end Funktion, zB:

• Anschlag nie (get eine unendliche Reihe)
• Stopp nach N Schritten (um einen gezählten Bereich zu erhalten)
• stoppen, wenn ein \0 ist aufgetreten, dh *it = '\0' (für Schleifen über C-Strings)
• aufhören, wenn es 12 Uhr ist (zum Mittagessen), und so weiter.

Außerdem Leistung in Bezug auf, in der Lage ist die Verwendung der Kompilierung-Informationen in der Prüfung zu machen (zum Beispiel denken Sie an den N oben als Kompilierung-Parameter). In diesem Fall könnte der Compiler möglicherweise in der Lage sein, den Code besser zu optimieren.

---

(*) Beachten Sie, dass dies nicht bedeutet, dass für diese Art von Operationen im Allgemeinen keine Verwendung besteht.Zum Beispiel kann --end() an einigen Stellen nützlich sein, siehe z.B. this question. Es ist jedoch scheinbar möglich, die Standardbibliothek ohne diese zu implementieren - das hat die Bibliothek von range-v3 getan.