Iterator++

[Gast]

Hallo Leute,
Hand auf's Herz, mir gehen explizite Iterator-Paare auf den Sack. Nicht nur, dass man ständig zwei Iteratoren hinschreiben muss bei jedem Algorithmus, nein, man braucht auf 6 (!) Funktionen um "standardkonform" Sequenzen aus seinen Objekten anbieten zu können. Darum bin ich irgendwann dazu übergegangen mir eine "sequence"-Template-Klasse zu basteln, die einfach ein Iteratorpaar nimmt, sowie die Standardalgorithmen zu wrappen, sodass man überall statt der einzelnen Iteratoren auch eben ganze Sequenzen verwenden kann. Damit bin ich aber schon bei 9 Methoden für eine Sequenz. Ich bin die Tage auf boost::range gestoßen, was wohl so ziemlich genau das ist, was ich hier per Hand mache, plus noch tausend viel bessere Sachen, die ich so nicht in endlicher Zeit (wenn überhaupt) hinbekäme.
Ich denke nun darüber nach, Iteratoren in meinem Code komplett durch boost::ranges zu ersetzen, aber das ist natürlich ein Unterfangen, bei dem man sich sicher sein sollte, dass das Resultat gut ist.

Drum wollte ich mal fragen, ob irgendjemand den Weg schon gegangen ist und ob es zu irgendwelchen Problemen kommen könnte, die ich derzeit nicht absehen kann.

Viele Grüße,
Deci

[volkard]

Hab mich damals von
http://www.slideshare.net/rawwell/iteratorsmustgo
erleuchten lassen.

Rausgekommen war, daß viele Algorithmen *deutlich angenehmer* im Aufruf wurden. Viele Klassen wurden *deutlich schöner* im Schreiben.

Manche Sachen habe ich in meinem kleinen Köpchen nicht gescheit hingekriegt, wie den Schreib-Puffer, der irgendwie zwei Ranges ist, von Anfang bis zur Schreib-Position und von der Schreib-Position bis zum Ende; der Sender sieht die hintere Range, der Empfänger die vordere. Und innendrin sind es doch nur drei Zeiger. Muss mal schauen, was die boost-Leute da inzwischen herausgefunden haben. Ist das nur *ein* Sonderfall, den man elend erschießen kann, oder erwächst da eine ganze Welt von Sonderfällen? (Was die boostler ja auch nicht stören würde, die hauen das durch und freuen sich ein Loch ins Knie über 2500 neue vollkommen nichtintuitive Konzepte und Klassen.)

Aber langsam panne wurde es dann, als ich feststellt, daß ich die ganz starke Tendenz dazu entwickelte, daß ich Ranges innerhalb der Klassen ständig über Iteratoren implementierte. Hab mein Projekt dahingehend abgebrochen.

Hab mir noch nicht überlegt, wie die Lamdas da jetzt Einfluß haben. Baumtraversierung mit schlankem Iterator benötigt ja einen ansonsten vollkommen unsinnigen Up-Zeiger, was mir so whr tut, wie damals, daß C++ kein for each hatte. Fette Iteratoren (mit einem Stack/Queue als Member) beheben das Problem, eröffnen aber auch ganz neue. Könnte sein, daß fette Ranges das Problem beheben und bei weitem nicht so weh tun wie fette Iteratoren. Könnte sein, daß wegen der Lamdas das ganze Thema vom Tische ist.

[Gast]

Hrmmm, Dein Beispiel könnte man ja zumindest noch ohne dabei komplizierter zu werden, als herkömmlich mit Iteratorern, über eine range + 1 range_iterator umsetzen, oder nicht?
Und dass man Ranges "intern" über Iteratoren umsetzt liegt ja hauptsächlich daran, dass so ziemlich alles ein Iterator ist, wenn man mal darüber nachdenkt. Ist ja ein ziemlich genereller Begriff. Ich kann daran direkt nichts schlechtes erkennen.
Nur soweit ich das sehe, hat Andrej ja gedanklich auch einen etwas extremeren Ansatz als die boost::ranges gewählt. Vielleicht habe ich da aber auch noch nicht den klaren Blick drauf

Was mir schwer fällt ist herauszulesen, ob Du wieder auf Iteratoren zurückgerudert bist und ob du überhaupt boost::ranges ausprobiert hast, oder ob du versucht hast Andrejs Slides selber umzusetzen?

Viele Grüße,
Deci

[volkard]

Decimad schrieb:

Was mir schwer fällt ist herauszulesen, ob Du wieder auf Iteratoren zurückgerudert bist und ob du überhaupt boost::ranges ausprobiert hast, oder ob du versucht hast Andrejs Slides selber umzusetzen?

Habs selber versucht. boost::ranges habe ich nicht ausprobiert.

Hrmmm, Dein Beispiel könnte man ja zumindest noch ohne dabei komplizierter zu werden, als herkömmlich mit Iteratorern, über eine range + 1 range_iterator umsetzen, oder nicht?

Dann hätte ich einen der beiden an sich gleichberechtigten Bereiche zu stark bevorzugt.

[Gast]

Dann muss ein split_iterator her, der selbst nicht dereferenzierbar ist, aber einen linken und rechten Nachbarn anbietet, hrmmmhrmmm

Aber ehrlich, irgendwo wird immer ein Bereich bevorzugt, wenn sie aneinander angrenzen, finde ich, weil es eben keine gebrochen rationalen Zeiger gibt in modernen PCs.

[volkard]

Decimad schrieb:

Dann muss ein split_iterator her, der selbst nicht dereferenzierbar ist, aber einen linken und rechten Nachbarn anbietet, hrmmmhrmmm

Oki, die Gleichberechtigung ist da. Aber es trifft die Lage nicht.
Besser eine double_range, wo eine automatisch wächst, wenn die andere schrumpft und umgekehrt, weil sie sich irgendwie Speicher teilen.

Decimad schrieb:

Aber ehrlich, irgendwo wird immer ein Bereich bevorzugt, wenn sie aneinander angrenzen, finde ich, weil es eben keine gebrochen rationalen Zeiger gibt in modernen PCs.

Falscher Film.

[Gast]

Vielleicht ein shared_iterator und zwei ranges? Aber dann wird der Zustand der Ranges "von außen" verändert, das ist wohl auch nicht so gut. Dann würde ich die Range+iterator bevorzugen und das ganze so kapseln, dass man von außen halt 2 Ranges sieht, bei der sich die eine vergrößert, wenn die andere kleiner wird. Entweder es werden Proxy-Ranges rausgegeben, oder aber man verwendet so einen shared_iterator und kann deshalb zwei echte Ranges verwenden und rausgeben.

[otze]

volkard schrieb:

Hab mich damals von
http://www.slideshare.net/rawwell/iteratorsmustgo
erleuchten lassen.

leider ignoriert das range conzept den "kleinen" Fakt, dass das iterator interface stärkere Garantien anbietet:

vgl:

template<class Iterator>
sort(Iterator begin, Iterator end);

template<class Range>
sort(Range& range);

std::vector<int> vec;
sort(vec.begin();vec.end());
sort(vec);

was ist der Unterschied? der erste Aufruf garantiert, dass nur die elemente von vec geändert werden. Beim zweiten Aufruf besteht die Möglichkeit, dass sort so implementiert ist, dass statt einer in-place permutation ein copy&swap eingesetzt wird. Unabhängig davon ob das passiert oder nicht bedeutet das, dass man davon ausgehen muss, dass nach einem Aufruf von sort(vec) alle iteratoren/ranges auf vec invalidiert sind. Oder es ist irgendwo extern dokumentiert, aber die Funktionssignatur gibt das nicht mehr her.

das range conzept würde mehr Sinn machen, wenn es eine art "strukturelles const" in C++ gäbe, was zwar veränderung von elementen erlaubt, aber nicht swap/insert/push_back...

template<class Range>
sort(Range struct const& range);//schade, dass es das nicht gibt..

[Nexus]

Decimad schrieb:

Ich denke nun darüber nach, Iteratoren in meinem Code komplett durch boost::ranges zu ersetzen, aber das ist natürlich ein Unterfangen, bei dem man sich sicher sein sollte, dass das Resultat gut ist.

Boost.Range ist sicher nicht schlecht, aber ich würde das Ganze nicht zu radikal angehen. D.h. nicht auf Biegen und Brechen alle Iteratoren aus Programmen verbannen, sondern schauen wo der Umstieg sinnvoll ist. Und vielleicht auch rückblickend schauen, wo sich der Code tatsächlich vereinfacht hat und wo er lediglich "zerboostelt" worden ist.

Was ich etwas schade finde, ist dass ich vor 1.5 Jahren zwei Bugreports für Boost.Range eingereicht habe, und die bis heute nicht beachtet wurden. Erwarte also nicht zu aktive Entwicklung.

otze schrieb:

leider ignoriert das range conzept den "kleinen" Fakt, dass das iterator interface stärkere Garantien anbietet:

Ja, ich habe sowieso etwas Mühe mit Boosts Tendenz, alles über Templateparameter und implizite Concepts zu lösen. Die Schnittstelle hat dann in vielen Fällen null Aussagekraft, und die Dokumentation ist auch nicht immer fähig, das zu kompensieren. Bei Boost.Graph sieht man z.B. die Auswüchse, verglichen mit LEMON ist die Bibliothek extrem benutzerunfreundlich. Manchmal ist maximale Generizität eben nicht alles...

otze schrieb:

das range conzept würde mehr Sinn machen, wenn es eine art "strukturelles const" in C++ gäbe, was zwar veränderung von elementen erlaubt, aber nicht swap/insert/push_back...

Scheint mir ein viel zu spezifisches Sprachmittel zu sein. Mit Concepts wäre dieses Problem behoben. Davon abgesehen kann man sich auch eine Klasse wie Range<int> basteln, die ein paar Garantien gibt und von Iteratoren abstrahiert. Ist meiner Meinung nach benutzerfreundlicher und flexibler, aber man nimmt einen Performanceoverhead in Kauf. Ich habe solche Type-Erased Ranges hier vorgestellt.

[otze]

Nexus schrieb:

otze schrieb:

das range conzept würde mehr Sinn machen, wenn es eine art "strukturelles const" in C++ gäbe, was zwar veränderung von elementen erlaubt, aber nicht swap/insert/push_back...

Scheint mir ein viel zu spezifisches Sprachmittel zu sein. Mit Concepts wäre dieses Problem behoben. Davon abgesehen kann man sich auch eine Klasse wie Range<int> basteln, die ein paar Garantien gibt und von Iteratoren abstrahiert. Ist meiner Meinung nach benutzerfreundlicher und flexibler, aber man nimmt einen Performanceoverhead in Kauf. Ich habe solche Type-Erased Ranges hier vorgestellt.

Komisch, also ich sehe den Nutzen eines struct-const jeden Tag. Zumal die Konzept Lösung zu einer wilden Wucherung von Konzepten führen würde, weil das Problem eben nicht nur auf Ranges beschränkt ist. (vektoren...matrizen etc...)

[Nexus]

otze schrieb:

Komisch, also ich sehe den Nutzen eines struct-const jeden Tag.

Ich halte ein separates Sprachmittel für massiven Overkill. Es würde vieles unnötig verkomplizieren. Man hätte 3 CV-Qualifizierer, Typen wie const T* und struct const T* werden inkompatibel, man müsste const_cast und mutable mit neuer Bedeutung versehen, man bräuchte neue Type-Traits, neue Konvertierungs- und Überladungsregeln sowie Struct-Const-Correctness.

Es gibt vieles, was ab und zu nützlich wäre, aber trotzdem ist es in den wenigsten Fällen sinnvoll, etwas direkt als Sprachmittel einzuführen. C++ ist inzwischen derart komplex, dass man nicht annähernd die Implikationen auf bestehende Sprach- und Bibliotheksmittel abschätzen kann, ohne den Standard äusserst gut zu kennen. Viele Konsequenzen zeigen sich dennoch erst in der Praxis, momentan lernen wir C++11 erst kennen. Auf der anderen Seite ist C++ mächtig genug, um vieles als Bibliotheksfeature einzubauen -- schau alleine mal in Boost, wie viele C++11-Features schon in C++03 implementiert wurden (Lambda, Move, Typeof, Foreach, ListOf). Sind natürlich Kompromisse, aber die Möglichkeiten sind schon erstaunlich.

struct const ist einfach viel zu spezifisch, um die Komplexität zu rechtfertigen. Es macht genau für Klassen mit Container-Semantik Sinn. Dafür kannst du dir auch ein Interface schreiben, das eben nur Zugriff auf die Elemente zulässt.

[krümelkacker]

otze schrieb:

das range conzept

Ich möchte an dieser Stelle nur darauf hinweisen, dass das Boost'sche Range Konzept anders ist als das von Alexandrescu. Es gibt also nicht "das Range Konzept". Beim Boost'schen Range-Konzept unterscheidet man nicht zwischen Wert- und Referenzsemantik. Die Kopierbarkeit eines Range-Objekts und die Semantik dieses Vorgangs ist auch nicht Teil des Konzepts. Ranges werden immer per Referenz entgegen genommen. Alexandrescu's Range-Konzept hat immer Referenz-Semantik. Range-Objekte sind bei ihm ähnlich leichtgewichtig wie Iteratoren und eine Kopie einer Range bezieht sich auf dieselben Elemente.

otze schrieb:

würde mehr Sinn machen, wenn es eine art "strukturelles const" in C++ gäbe, was zwar veränderung von elementen erlaubt, aber nicht swap/insert/push_back...

template<class Range>
sort(Range struct const& range);//schade, dass es das nicht gibt..

Damit kann ich leider nichts anfangen. Was verstehst du unter "strukturellem const"? Was ist "Range" hier? Handelt es sich um ein "Alexandrescu-Range"? Falls ja: Inwiefern ist bei so etwas ein "strukturelles const" nötig wenn wir bei Iteratoren ohne auskommen?

[Shade Of Mine]

otze schrieb:

leider ignoriert das range conzept den "kleinen" Fakt, dass das iterator interface stärkere Garantien anbietet:

vgl:

template<class Iterator>
sort(Iterator begin, Iterator end);

template<class Range>
sort(Range& range);

std::vector<int> vec;
sort(vec.begin();vec.end());
sort(vec);

was ist der Unterschied? der erste Aufruf garantiert, dass nur die elemente von vec geändert werden. Beim zweiten Aufruf besteht die Möglichkeit, dass sort so implementiert ist, dass statt einer in-place permutation ein copy&swap eingesetzt wird. Unabhängig davon ob das passiert oder nicht bedeutet das, dass man davon ausgehen muss, dass nach einem Aufruf von sort(vec) alle iteratoren/ranges auf vec invalidiert sind. Oder es ist irgendwo extern dokumentiert, aber die Funktionssignatur gibt das nicht mehr her.

template<class Range>
sort(Range range);

loest das Problem.
Wozu muss die Range per non const reference uebergeben werden?

[Nexus]

krümelkacker schrieb:

Ich möchte an dieser Stelle nur darauf hinweisen, dass das Boost'sche Range Konzept anders ist als das von Alexandrescu.

Hat Alexandrescu eigentlich mehr dazu gesagt als Iterators Must Go, evtl. sogar eine Beispielimplementierung bereitgestellt?

krümelkacker schrieb:

Damit kann ich leider nichts anfangen. Was verstehst du unter "strukturellem const"? Was ist "Range" hier?

Soweit ich ihn verstehe: struct const heisst, nur die Elemente dürfen verändert werden, nicht die Struktur des Containers (z.B. Anzahl der Elemente). Eben nur der Zugriff, den auch Iteratoren haben. Range ist wahrscheinlich ein normaler Template-Parameter.

Shade Of Mine schrieb:

template<class Range>
sort(Range range);
loest das Problem.

Ja, nur führt der Aufruf sort(vec) zu einer Kopie und sortiert den Original-Container nicht. Schöne "Lösung"

[Shade Of Mine]

Nexus schrieb:

Ja, nur führt der Aufruf sort(vec) zu einer Kopie und sortiert den Original-Container nicht. Schöne "Lösung"

OK. von welcher Art von Ranges reden wir hier?

[krümelkacker]

Nexus schrieb:

Hat Alexandrescu eigentlich mehr dazu gesagt als Iterators Must Go, evtl. sogar eine Beispielimplementierung bereitgestellt?

Er hat einiges gesagt innerhalb der ca 60 Minuten. Das, was ihn an Iteratoren gestört hat, ist, dass sie "dumm" seien und selbst nicht wüssten, ob man sie z.B. ohne Probleme inkrementieren könne. Sie seien dazu unpraktisch, weil man immer zwei von ihnen für eine Sequenz bräuchte, was u.a. auch die Komposition schwieriger mache. Er schlug deswegen ein anderes Konzept vor, was weniger fehleranfällig, praktischer und ausreichend mächtig sei (er habe alle STL-Algorithmen auf Basis seines Range-Konzepts implementieren können). Beispiele werden natürlich auch gezeigt. Ich fand das interessant, aber auch leider nicht komplett überzeugend. Einige im Publikum (mich eingeschlossen) waren nicht ganz überzeugt davon, das das Konzept mächtig genug ist, dass man komplett ohne Iteratoren auskommen kann. Solche Ranges sind auf Basis von Iteratoren schon implementierbar. Andersherum aber nicht. Das macht es IMHO etwas schwieriger, dafür zu argumentieren, dass sein Range-Konzept mächtig genug ist.

Nexus schrieb:

krümelkacker schrieb:

Damit kann ich leider nichts anfangen. Was verstehst du unter "strukturellem const"? Was ist "Range" hier?

Soweit ich ihn verstehe: struct const heisst, nur die Elemente dürfen verändert werden, nicht die Struktur des Containers (z.B. Anzahl der Elemente). Eben nur der Zugriff, den auch Iteratoren haben.

Aha. Dann werden ihm die "Alexandrescu-Ranges" sicher gefallen. Denn die können die "Struktur eines Containers" genauso wenig verändern, wie Iteratoren.

Nexus schrieb:

Shade Of Mine schrieb:

template<class Range>
sort(Range range);
loest das Problem.

Ja, nur führt der Aufruf sort(vec) zu einer Kopie und sortiert den Original-Container nicht. Schöne "Lösung"

In Alexandrescu's Range-Welt, würde man das so aufrufen:

sort(meinvector.all());

also statt begin/end ein all anbieten, was ein Range-Objekt liefert, welches ähnlich wie Iteratoren auch per Wert übergeben werden kann; denn es hat immer Referenzsemantik. Nach diesem Modell sind Container keine Ranges.