Member-Iterator auf eigene Klasse

[Nexus]

hustbaer schrieb:

Eine Intrusive-List ala Boost.Intrusive verwenden.
Dann kannst du wieder Zeiger speichern, da du jederzeit mit O(1) einen Zeiger in einen Iterator verwandeln kannst.

Ich wollte hier zwar kein Boost verwenden, aber das schaue ich mir auf jeden Fall mal an. Merci!

otze schrieb:

sonst hätte ich dir boost::graph vorgeschlagen

Danke, aber von Boost.Graph und seinem impliziten, über-abstrahierten und mies dokumentierten API habe ich vorerst genug. Mit LEMON habe ich persönlich bessere Erfahrungen gemacht. Ist zwar nicht endlos generisch, bietet dafür vernünftige Schnittstellen an.

[hustbaer]

Naja notfalls ist ne doppelt verkettete Liste auch schnell selbst implementiert

[Nexus]

Bisher bräuchte ich nur die Methoden push_back() , begin() , end() , erase() , remove_if() , empty() . Würde vielleicht sogar eine einfach verkettete Liste reichen.

Mühsam ist jedoch Speicherverwaltung. Bei Boosts Intrusive-Containern wird das ja extern geregelt, aber wie wird das in der Praxis gehandhabt? Läuft das nicht darauf hinaus, die Elemente in einem weiteren, besitzenden Container/Pool zu speichern?

Ist ein bisschen schade, dass so ein kleines "Problem" (d.h. auf den meisten Compilern ein Nicht-Problem) zu so viel Refactoring führt. Ich bin versucht, die zirkuläre Abhängigkeit einfach mit einer Indirektion (gewrappter Iterator) zu durchbrechen, aber ich fürchte, pro Iteratorkopie eine dynamische Speicheranforderung wird schnell teuer.

[Furble Wurble]

Nexus schrieb:

Ist ein bisschen schade, dass so ein kleines "Problem" (d.h. auf den meisten Compilern ein Nicht-Problem) zu so viel Refactoring führt

Ist denn wirklich schon geklärt, ob das Pattern UB oder ähnliches ist?

Beim CRTP ist's doch auch nicht anders...

Ich meine auch, vor kurzem hier schon einmal über diese Diskussion gestolpert zu sein...Ich hab das nicht weiter verfolgt, weil das einen "Standard-Lawyer" verlangt und meine Kompetenzen übersteigt.
Aber vielleicht solltest Du jemanden finden, der in den Ring steigt und sagt
"Das geht nicht, weil ABC". Bzw. "Das geht, weil XYZ" und anhand der Argumente in der folgenden Diskussion entscheiden, ob das Refactoring wirklich nötig ist...

Grüßle.
FW

PS: Ich denke es ist okay - eben wie beim CRTP.

[Nexus]

Jemand hatte auf Mac OS X mit Clang 4.0 Probleme mit ähnlichem Code. Wenn ich die Fehlermeldung richtig interpretiere, weil der Typ im STL-Container nicht vollständig war. Clang 3.0 (die Online-Version, mit der ich getestet habe) kompiliert den Beispielcode dieses Threads problemlos, ebenso die drei anderen Compiler. Aber ich frage nochmals nach, wie es mit Clang 4 und diesem Beispielcode aussieht.

Ich habe nur den Final Draft des C++11-Standards, dieser besagt:

C++ FDIS 2011 (n3290), §17.6.4.8/2 schrieb:

In particular, the effects are undefined [...] if an incomplete type (3.9) is used as a template argument when instantiating a template component, unless specifically allowed for that component.

Jetzt weiss ich nicht, ob das noch aktuell ist und ob es nicht irgendwo eine Klausel gibt, durch die der Fall "specifically allowed" wird.

[Kellerautomat]

Clang 4 gibts doch noch gar nicht.

[hustbaer]

Nexus schrieb:

Ich habe nur den Final Draft des C++11-Standards, dieser besagt:

C++ FDIS 2011 (n3290), §17.6.4.8/2 schrieb:

In particular, the effects are undefined [...] if an incomplete type (3.9) is used as a template argument when instantiating a template component, unless specifically allowed for that component.

Jetzt weiss ich nicht, ob das noch aktuell ist und ob es nicht irgendwo eine Klausel gibt, durch die der Fall "specifically allowed" wird.

Zieh dir den n3337. Der ist bis auf ein paar Fehlerkorrekturen mit dem Standard identisch.
n3337:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf
Änderungen gegenüber dem Standard:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3338.html

Davon abgesehen...
Das heisst ja bloss "manche Template-Klassen brauchen Argumente die vollständig sind ey, also passt da mal auf". Wenn bei std::list nicht dabeisteht dass sie auch mit unvollständigen Klassen funktionieren muss, dann muss sie halt nicht.

[Nexus]

Kellerautomat schrieb:

Clang 4 gibts doch noch gar nicht.

Du hast Recht, Apple scheint da anders zu zählen. clang -v auf Mac gab Folgendes aus, also eine Abwandlung von 3.1:

Apple clang version 4.0 (tags/Apple/clang-421.0.60) (based on LLVM 3.1svn)

hustbaer schrieb:

Zieh dir den n3337. Der ist bis auf ein paar Fehlerkorrekturen mit dem Standard identisch.

Danke!

[Nexus]

Interessant ist auch, Comeau Online kompiliert den folgenden Code nicht:

#include <list>

struct Triangle;
typedef std::list<Triangle>::iterator Iterator;

struct Triangle
{
    Iterator i;
};

int main() {}

Nimmt man das typedef in die Klasse, kompiliert der Code. Gilt die Klasse innerhalb ihrer Definition etwa schon als vollständiger Typ? Z.B. Grösse ist dann noch nicht bekannt.

Und vielleicht doch nochmal zu den Intrusive-Containern: Wie handhabt ihr die Speicherverwaltung der einzelnen Elemente?

[camper]

Nexus schrieb:

Gilt die Klasse innerhalb ihrer Definition etwa schon als vollständiger Typ?

n3337 schrieb:

9.2/2 A class is considered a completely-defined object type (3.9) (or complete type) at the closing } of the
class-specifier. Within the class member-specification, the class is regarded as complete within function
bodies, default arguments, exception-specifications, and brace-or-equal-initializers for non-static data members
(including such things in nested classes). Otherwise it is regarded as incomplete within its own class
member-specification.

Also nein.

[otze]

Es kann sein, dass das durchaus implementationsabhängig ist, ob das funktioniert.
Wenn der Iterator wie folgt implementiert ist:

template<class ListElement>
class ListIterator{
    ListElement* element;
public:
   //...
};

Dann muss ListElement zu dem Zeitpunkt nicht vollständig sein. Für die Methoden des Iterators gilt dann wahrscheinlich die zitierte Klausel aus dem Standard:
"Within the class member-specification, the class is regarded as complete within function
bodies, default arguments, exception-specifications, and brace-or-equal-initializers for non-static data members" also würde es in diesem Fall gar kein Problem geben.

Ich weiß aber nicht, wie es in diesem Fall sein würde:

template<class T>
class list{
    struct ListElement{
        T element;//hier muss T vollständig sein, oder?
    };
    class iterator{
        ListElement* element;
    public:
       //...
    };
};

Muss ListElement erzeugt werden, wenn list<T>::iterator aufgerufen wird?

[camper]

otze schrieb:

Ich weiß aber nicht, wie es in diesem Fall sein würde:

template<class T>
class list{
    struct ListElement{
        T element;//hier muss T vollständig sein, oder?
    };
    class iterator{
        ListElement* element;
    public:
       //...
    };
};

Muss ListElement erzeugt werden, wenn list<T>::iterator aufgerufen wird?

Jedenfalls nicht, wenn der //...-Teil es nicht erfordert.

Es könnte auch so aussehen:

template <typename T, typename A, bool trivial>
class list_base;

template <typename T, typename A>
class list_base<T,A,true>; // mit cleveren Optimierungen

template <typename T, typename A>
class list : list_base<T, A, is_trivial<T>::value>
{
...
};

Und schon klappt es gar nicht mehr mit unvollständigen Typen, unabhängig davon, weshalb das list-Template nun instantiiert wurde (man kann das auch gleich mit dem Default-Allokator so machen; dann wird auch klar, wieso nur wenige Klassentemplates solche expliziten Ausnahmen haben).

[hustbaer]

Klar kann es implementierungsabhängig sein.

Bzw... was den Allokator angeht weiss ich nicht. Müsste auch gehen, hab ich mir nicht so genau überlegt. Aber wenn wir mal annehmen dass der Allokator kein Problem macht...

Es sollte möglich sein std::list<T> so zu implementieren dass eine vollständige Definition von T überhaupt nicht nötig ist bis diverse Memberfunktionen instanziert werden die notwendigerweise eine vollständige Definition von T brauchen (wie z.B. push_back, weil da ja kopiert wird).

Wenn man unnötigen Overhead in Kauf nimmt ist es sogar sehr leicht: man schiebt eine Zwischenklasse für die Nodes ein die T nicht als Member enthält, dafür entweder eine virtual pure "get" Funktion hat die eine Referenz auf T zurückgibt, oder einen T* enthält.

Ganz ohne unnötigen Overhead wird es u.U. schwierig, bzw. evtl. sogar unmöglich. Um den Offset des T innerhalb der Node zu ermitteln braucht man das Alignment von T, und das ist erst bekannt wenn T vollständig ist. Man müsste also irgendwie über Umwege an den Offset bzw. den T* kommen. Und Umweg = normalerweise Overhead.

[camper]

hustbaer schrieb:

Klar kann es implementierungsabhängig sein.

Bzw... was den Allokator angeht weiss ich nicht. Müsste auch gehen, hab ich mir nicht so genau überlegt. Aber wenn wir mal annehmen dass der Allokator kein Problem macht...

Es sollte möglich sein std::list<T> so zu implementieren dass eine vollständige Definition von T überhaupt nicht nötig ist bis diverse Memberfunktionen instanziert werden die notwendigerweise eine vollständige Definition von T brauchen (wie z.B. push_back, weil da ja kopiert wird).

Wenn man unnötigen Overhead in Kauf nimmt ist es sogar sehr leicht: man schiebt eine Zwischenklasse für die Nodes ein die T nicht als Member enthält, dafür entweder eine virtual pure "get" Funktion hat die eine Referenz auf T zurückgibt, oder einen T* enthält.

Ganz ohne unnötigen Overhead wird es u.U. schwierig, bzw. evtl. sogar unmöglich. Um den Offset des T innerhalb der Node zu ermitteln braucht man das Alignment von T, und das ist erst bekannt wenn T vollständig ist. Man müsste also irgendwie über Umwege an den Offset bzw. den T* kommen. Und Umweg = normalerweise Overhead.

Ich denke bei list dürfte es möglich sein (sofern der Allokator vollständig ist), ohne Overhead unvollständige Typen zuzulassen.
Das wäre, denke ich, tatsächlich ein Vorschlag für eine nützliche Erweiterung wert, wenn sich mal jemand die Mühe macht, zu demonstrieren, welche Container und ggf. Iteratoren ohne Overhead (also auch ohne Ausschluss denkbarer Optimierungen) mit unvollständigem Valuetyp auskommmen könnten. Der Defaultallokator dürfte eigentlich auch recht unproblematisch sein, der ist ja sowieso austauschbar, kann also stateless implementiert werden.

Kein richtiger Container kann die Smallobjekt-Optimierung durchführen, weil Iteratoren bei swap stabil bleiben müssen. Alles andere was so einfällt, dürfte eigentlich kein Hindernis darstellen.

[hustbaer]

@camper
Du meinst jetzt nur die Instanzierung der Container-Klasse selbst...? Oder auch die Instanzierung von Memberfunktionen die T gar nicht wirklich verwenden sondern nur Zeiger/Referenzen darauf rumreichen?

Bei der Instanzierung von Memberfunktionen wie list<T>::back bzw. list<T>::iterator::operator * sehe ich nämlich ein kleines Problem, und zwar wie man ohne Overhead aus einem Node-Zeiger einen T-Zeiger macht (oder umgekehrt).

Oder hättest du diesbezüglich irgendeine Idee?

Irgendwie fällt mir keine wirklich gute Lösung ein.

Das beste was mir bisher eingefallen ist wäre überall nur T-Zeiger abzuspeichern (oder auch gleich char-Zeiger die auf ein T zeigen), und dann mit static_cast<Node*>(static_cast<char*>(t) - sizeof(Node)) einen Node* daraus zu basteln. Das wäre auf jeden Fall schonmal fummelig zu implementieren (viel placement new, Ausrechnen des nötigen Alignment).

Zusätzlicher Overhead würde dadurch bloss beim Zugriff auf das erste Node-Member entstehen (z.B. [Register + Offset] Adressierung statt einfach nur [Register]).
Dafür würde das Dereferenzieren eines Iterators sogar billiger, weil dort die Addition wegfällt.
Das ist zwar ein Tausch den ich für durchaus vertretbar halten würde, aber "kein zusätzlicher Overhead" kann man es auch nicht wirklich nennen.

BTW: garantiert der Standard dass ein Alignment-Requirement immer nur eine Zweierpotenz sein kann?

[camper]

hustbaer schrieb:

@camper
Du meinst jetzt nur die Instanzierung der Container-Klasse selbst...? Oder auch die Instanzierung von Memberfunktionen die T gar nicht wirklich verwenden sondern nur Zeiger/Referenzen darauf rumreichen?

Nur die Klasse selbst und ggf - soweit möglich - von Typen, die darin deklariert werden (wie z.B. iterator). Nur dass diese wird man in der Regel in der Klassendefinition direkt benötigen.

[camper]

hustbaer schrieb:

BTW: garantiert der Standard dass ein Alignment-Requirement immer nur eine Zweierpotenz sein kann?

n3337 schrieb:

3.11/4 Alignments are represented as values of the type std::size_t. Valid alignments include only those values
returned by an alignof expression for the fundamental types plus an additional implementation-defined set
of values, which may be empty. Every alignment value shall be a non-negative integral power of two.