Iterator++

[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.