Doppelt verkettete Liste als Ring
-
volkard schrieb:
314159265358979 schrieb:
Die Objekte direkt speichern geht doch auch und ist z.B. beim Implementieren von Iteratoren einfacher.
Ich brauche mehr Details.
Meine Implementierung:
class List { Node first; // Dummy-Node, VOR begin(), für rend() Node last; // Dummy-Node, Genau end() };Dadurch, dass hier immer 2 Nodes in der Liste sind, wird eine Leere Liste durch Verkettung der beiden Dargestellt.
Vorteile:
- Einfügen findet immer in der Mitte statt, dadurch keine Anfangs/End-Checks auf ungültige Zeiger.
- Iteratoren arbeiten immer auf Nodes. Bei einer Implementierung mit Zeigern und Anzahl an Nodes = Anzahl Elementen haben end() und rend() keine Nodes mehr. Hier muss getrickst werden.Welche Argumente sprechen nun gegen diese Implementierung? Klar, hier werden ein paar Byte mehr Speicher verbraucht. Aber dafür hat man bessere Performance.
-
314159265358979 schrieb:
volkard schrieb:
314159265358979 schrieb:
Die Objekte direkt speichern geht doch auch und ist z.B. beim Implementieren von Iteratoren einfacher.
Ich brauche mehr Details.
Meine Implementierung:
class List { Node first; // Dummy-Node, VOR begin(), für rend() Node last; // Dummy-Node, Genau end() };Nee:
template<typename Data> class List { struct Node { Node* prev; Node* pred; Data data;//Pfui! } Node first; // Dummy-Node, VOR begin(), für rend() Node last; // Dummy-Node, Genau end() };Aber Data hat keinen Standardkonstruktor UND Data hat ein static member Data::count, wo man jederzeit die Gesamtzahl der existierenden Data-Objekte abfragen kann, die geht um deine beiden Dummy-Objekte falsch.
Vorteile:
- Einfügen findet immer in der Mitte statt, dadurch keine Anfangs/End-Checks auf ungültige Zeiger.Du bist auf dem richtigen Weg. Aber EIN Dummy-Node reicht vollkommen aus, denn wir basteln einen Ring! Und dann mach das Problem noch weg, daß Dummy-Nodes Daten enthalten. Laß echte Nodes zum Beispiel von Dummy-Nodes erben.
- Iteratoren arbeiten immer auf Nodes. Bei einer Implementierung mit Zeigern und Anzahl an Nodes = Anzahl Elementen haben end() und rend() keine Nodes mehr. Hier muss getrickst werden.
Nö. Auch herkömmlich geht das sehr gut. end() kann ja schon {nullptr} sein.
Welche Argumente sprechen nun gegen diese Implementierung? Klar, hier werden ein paar Byte mehr Speicher verbraucht. Aber dafür hat man bessere Performance.
Wenn Du es richtig machst, wird kein Speicher verschwendet und für einen Container mit push-back/front und pop-back/front fallen ALLE Fallunterscheidungen weg. volkard mag sowas.
Aber das ist schon heftig getrickst, bis alles hübsch ist. Daher lieber erstmal bei der naiven Version bleiben. Und wenn man soweit ist, gerne die hübsche machen.
Aber so ein Zwischending, nee, das mag ich nicht.
-
volkard schrieb:
Aber Data hat keinen Standardkonstruktor
Das ist doch eine Anforderung an einen Typen, der in einem Standardcontainer gespeichert werden soll, oder?
volkard schrieb:
UND Data hat ein static member Data::count, wo man jederzeit die Gesamtzahl der existierenden Data-Objekte abfragen kann, die geht um deine beiden Dummy-Objekte falsch.
Okay, das ist ein Argument. Vielleicht ein char-Array + placement-new in Node mit geeignetem Konstruktor. Wird aber dann durch die Data-Node ja gelöst.
volkard schrieb:
Du bist auf dem richtigen Weg. Aber EIN Dummy-Node reicht vollkommen aus, denn wir basteln einen Ring!
Finde ich ziemlich unintuitiv zu implementieren, aber wäre ein Möglichkeit, stimmt. Wer fragt auch die Library-Schreiber, was sie wollen.
volkard schrieb:
Und dann mach das Problem noch weg, daß Dummy-Nodes Daten enthalten. Laß echte Nodes zum Beispiel von Dummy-Nodes erben.
Dann müsste ich ja einen dynamic_cast zum Downcasten verwenden, wenn ich mich nicht täusche? Oder reicht in diesem Fall der static_cast? Ich habe so selten solche Casts verwendet, schon wieder alles vergessen...
volkard schrieb:
Nö. Auch herkömmlich geht das sehr gut. end() kann ja schon {nullptr} sein.
Davon hätte ich nun aber gerne eine Implementierung.
volkard schrieb:
Wenn Du es richtig machst, wird kein Speicher verschwendet und für einen Container mit push-back/front und pop-back/front fallen ALLE Fallunterscheidungen weg. volkard mag sowas.
Das kann durchaus sein. Meine Version ist keinesfalls perfekt.
-
314159265358979 schrieb:
volkard schrieb:
Du bist auf dem richtigen Weg. Aber EIN Dummy-Node reicht vollkommen aus, denn wir basteln einen Ring!
Finde ich ziemlich unintuitiv zu implementieren, aber wäre ein Möglichkeit, stimmt. Wer fragt auch die Library-Schreiber, was sie wollen.
Mach es doch mal. Du wirst sehen, daß deine Ressentiments völlig unbegründet sind.
-
314159265358979 schrieb:
volkard schrieb:
Und dann mach das Problem noch weg, daß Dummy-Nodes Daten enthalten. Laß echte Nodes zum Beispiel von Dummy-Nodes erben.
Dann müsste ich ja einen dynamic_cast zum Downcasten verwenden, wenn ich mich nicht täusche? Oder reicht in diesem Fall der static_cast? Ich habe so selten solche Casts verwendet, schon wieder alles vergessen...
Schau in ein Buch und Du wirst herausfinden, daß Du für Downcasts (und hier liegt ein Downcast vor), dynamic_cast nehmen mußt. Aber Der Codex ist mehr eine Richtlinie und kein Gesetz. Hier reicht ausnahmsweise static_cast.
-
314159265358979 schrieb:
volkard schrieb:
Nö. Auch herkömmlich geht das sehr gut. end() kann ja schon {nullptr} sein.
Davon hätte ich nun aber gerne eine Implementierung.
Hab ich was übersehen?
class DoubleLinkedList { Node* begin,end; struct Iterator { Node* pos; Data& operator*() { return pos->data; } void operator++() { pos=pos->pred; } friend bool operator==(Iterator a,.Iterator b) { return a.pos==b.pos; } } Iterator begin() { return Iterator(begin); } Iterator end() { return Iterator(0); }Im Gegenzug hätte ich dann gerne Deine Liste zum Ring umgewandelt.
-
#include <utility> // std::move #include <iostream> template <typename T> class list { struct node_base { node_base* next; node_base* prev; node_base() : next(0) , prev(0) {} }; struct node : node_base { node(const T& data) : node_base() , data(data) {} T data; }; node_base anchor; void insert(node_base* pos, const T& value) { pos->prev->next = new node(value); pos->prev->next->next = pos; pos->prev->next->prev = pos->prev; pos->prev = pos->prev->next; } public: list() { anchor.next = &anchor; anchor.prev = &anchor; } void push_back(const T& value) { insert(&anchor, value); } void push_front(const T& value) { insert(anchor.next, value); } friend std::ostream& operator << (std::ostream& os, const list<T>& l) { os << '['; for(const typename list<T>::node_base* node = &l.anchor; node->next != &l.anchor; node = node->next) os << ' ' << static_cast<const typename list<T>::node*>(node)->data; return os << " ]"; } }; int main() { list<int> l; l.push_back(42); l.push_back(666); l.push_back(123); std::cout << l; }Ausgabe:
[ 1536264460 42 666 ]http://ideone.com/QBv3O
Naja fast
-
Ich hasse es, wenn ich Code von ideone erst hierher kopieren muß.
-
Wollte, dass man die Ausgabe sieht
Link nochmal dazu kopiert.
-
friend std::ostream& operator << (std::ostream& os, const list<T>& l) { os << '['; for(const typename list<T>::node_base* node = l.anchor.next; node != &l.anchor; node = node->next) os << ' ' << static_cast<const typename list<T>::node*>(node)->data; return os << " ]"; }begin() ist natürlich nach dem anchor, nämlich das erste gültige element.
und end() ist anchor, das dummy-element.
-
Ich weiß, dass der falsch iteriert
Wollte es gerade beheben.
-
Eventuell sowas für die Kosmetik. Deinen Verzeigerungscode Code konnte ich nicht flüssig lesen.
void insert(node_base* pos, const T& value) { node_base* newnode=new node(value);//knoten erzeugen newnode->prev=pos->prev;//knoten einstellen newnode->next=pos; newnode->prev->next=newnode;//ringbedingung reparieren newnode->next->prev=newnode; }
-
Bisher war das insert() die einzgie Funktion, die ich einmal geschrieben habe und nie wieder angesehen habe. Habe nie eine Methode gefunden, das schön zu formatieren. Deine ist aber gut, vielen Danke für den Tipp!
Hier nun die korrigierte Fassung:
#include <iostream> template <typename T> class list { struct node_base { node_base* next; node_base* prev; node_base() : next(0) , prev(0) {} }; struct node : node_base { node(const T& data) : node_base() , data(data) {} T data; }; node_base anchor; void insert(node_base* pos, const T& value) { node* new_node = new node(value); new_node->prev = pos->prev; new_node->next = pos; new_node->prev->next = new_node; new_node->next->prev = new_node; } public: list() { anchor.next = &anchor; anchor.prev = &anchor; } void push_back(const T& value) { insert(&anchor, value); } void push_front(const T& value) { insert(anchor.next, value); } friend std::ostream& operator << (std::ostream& os, const list<T>& l) { os << '['; for(const typename list<T>::node_base* node = l.anchor.next; node != &l.anchor; node = node->next) os << ' ' << static_cast<const typename list<T>::node*>(node)->data; return os << " ]"; } }; int main() { list<int> l; l.push_back(42); l.push_back(666); l.push_back(123); std::cout << l; }Hier mir Ausgabe: http://ideone.com/39StZ
Gibt es hier eigentlich keine Spoiler? Wären echt praktisch.
Edit: Von der falschen Seite kopiert, Code + Link ausgebessert.
-
314159265358979 schrieb:
Bisher war das insert() die einzgie Funktion, die ich einmal geschrieben habe und nie wieder angesehen habe. Habe nie eine Methode gefunden, das schön zu formatieren.
Böser 314159265358979!
void insert_between(node_base* prev, node_base* next, const T& value) {//Endlich Code, der offensichtlich richtig ist. node_base* newnode=new node(value); newnode->prev=prev; newnode->next=next; prev->next=newnode; next->prev=newnode; } void push_back(const T& value) {//Hier kommt der Ring-Charakter zum Tragen. Das hinteste Element ist anchor->prev, //also genau vor dem anchor. Eingefügt werden soll zwischen dem hintersten Element und dem end(). //end()==anchor. insert_between(anchor.prev, &anchor, value); } void push_front(const T& value) { insert_between(&anchor,anchor.next, value); }
-
node_base() : next(0)//müll , prev(0)//müllDas bringt doch nichts.
-
template <typename T> class list { struct node_base { node_base* next; node_base* prev; }; struct node : node_base { node(const T& data) : data(data) {} T data; }; node_base anchor; void insert_between(node_bast* left, node_base* right, const T& value) { node_base* new_node = new node(value); new_node->prev = left; new_node->next = right; left->next = new_node; right->prev = new_node; } public: list() { anchor.next = &anchor; anchor.prev = &anchor; } void push_back(const T& value) { insert_between(anchor.prev, &anchor, value); } void push_front(const T& value) { insert_between(&anchor, anchor.next, value); } friend std::ostream& operator << (std::ostream& os, const list<T>& l) { os << '['; for(const typename list<T>::node_base* node = l.anchor.next; node != &l.anchor; node = node->next) os << ' ' << static_cast<const typename list<T>::node*>(node)->data; return os << " ]"; } };Verbessert. Vielen Dank für die Hilfe! Kannst du mir zeigen, wie man hier einen Allokator einbauen kann?
Edit: Der Destruktor fehlt natürlich auch noch.
-
314159265358979 schrieb:
Kannst du mir zeigen, wie man hier einen Allokator einbauen kann?
Das will ich nicht.
Es ist häßlich. Du mußt den Trick mit rebind raffen, denn du willst ja nicht Ts erzeugen, sondern nodes.
-
Ich hab zwar keine Ahnung, was du mir damit sagen willst, aber es scheint zu funktionieren
#include <iostream> #include <memory> template < typename T, template <typename> class Allocator = std::allocator > class list { struct node_base { node_base* next; node_base* prev; }; struct node : node_base { node(const T& data) : data(data) {} T data; }; Allocator<node> allocator; node_base anchor; void insert_between(node_base* left, node_base* right, const T& value) { node* new_node = allocator.allocate(1); allocator.construct(new_node, value); new_node->prev = left; new_node->next = right; left->next = new_node; right->prev = new_node; } void erase(node_base* pos) { pos->prev->next = pos->next; pos->next->prev = pos->prev; allocator.destroy(static_cast<node*>(pos)); allocator.deallocate(static_cast<node*>(pos), 1); } public: list() { anchor.next = &anchor; anchor.prev = &anchor; } ~list() { clear(); } bool empty() { return anchor.next == &anchor; } void push_back(const T& value) { insert_between(anchor.prev, &anchor, value); } void push_front(const T& value) { insert_between(&anchor, anchor.next, value); } void pop_back() { erase(anchor.prev); } void pop_front() { erase(anchor.next); } void clear() { while(!empty()) pop_back(); } friend std::ostream& operator << (std::ostream& os, const list<T>& l) { os << '['; for(const typename list<T>::node_base* node = l.anchor.next; node != &l.anchor; node = node->next) os << ' ' << static_cast<const typename list<T>::node*>(node)->data; return os << " ]"; } }; int main() { list<int> l; l.push_back(11); l.push_back(22); l.push_back(33); l.push_back(44); std::cout << l; }Ausgabe:
[ 11 22 33 44 ]
-
Du meinst sicher sowas, oder?
#include <iostream> template <typename T> struct hugo; template <> struct hugo<double> { static const double value = 3.14; }; template <> struct hugo<char> { static const char value = 'P'; }; template <typename, typename> struct rebind; template < template <typename> class Class, typename T1, typename T2 > struct rebind<Class<T1>, T2> { typedef Class<T2> type; }; int main() { std::cout << rebind<hugo<double>, char>::type::value; }Ausgabe: P
-
Das Verlinken kann man noch eleganter haben:
struct node_base { node_base* next; node_base* prev; node_base() : next(this), prev(this) {} node_base(node_base* next) : next(next), prev(next->prev) { next->prev = this; prev->next = this; } ~node_base() { next->prev = prev; prev->next = next; } private: node_base(const node_base&); node_base operator=(const node_base&); }; template<typename T> struct node : node_base { node(node_base* next, const T& data) : node_base(next), data(data) {} T data; }; template < typename T, typename Allocator = std::allocator<T> > class list : private typename Allocator::template rebind<node<T> >::other // Höchstwahrscheinlich sowieso ein leeres Objekt, also müssen wir keinen Platz verschwenden { typedef node<T> node_type; typedef typename Allocator::template rebind<node_type>::other allocator; allocator& alloc() { return *this; } node_base anchor; void insert_before(node_base* right, const T& value) { void* new_node = alloc().allocate(1); new (node) node_type(right, value); } void erase(node_base* pos) { node_type* this_node = static_cast<node_type*>(pos); // ein static_cast nach der Zerstörung führt zu UB this_node->~node_type(); alloc().deallocate(this_node, 1); } public: list() : anchor() {} copy-ctor, copy-assignment, swap etc.Ein in das Listobjekt eingebtterer Dummynode hat einen kleinen Nachteil: Wenn Iteratoren angeboten werden wird der end-Itertoren bei swap ungültig - das kann u.U. unangenehm sein, meist dürften aber die Vorteile überwiegen.