Doppelt verkettete Liste als Ring
-
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.
-
Als erstes verstehe ich das mit rebind überhaupt nicht. (Ich kenne das template nicht mal.)
Außerdem finde ich, dass die list Klasse und nicht die node-Klasse für das Verketten zuständig sein sollte.
Dann hast du hier ja placement-new und einen expliziten Destruktor-Aufruf verwendet. Ist das erlaubt, sollte man hier nicht die allocate und deallocate Funktionen verwenden?
-
314159265358979 schrieb:
Als erstes verstehe ich das mit rebind überhaupt nicht. (Ich kenne das template nicht mal.)
Grob gesagt, die STL-Container übernehmen kein Template, sondern einen konkreten Typ, der in der Lage ist, den vorgegebenen Elementtyp zu verwalten. Da sie allerdings meistens keine reinen Objekte des Elementtyps speichern, sondern eigene Hilfsklassen (wie der node in eurem Beispiel), brauchen sie eine Möglichkeit, den Allokator nach seinem "Bruder" zu fragen:
template<typename T> class allocator { ... public: template<typename U> struct rebind { typedef allocator<U> type; }; ... }; template<typename T, typename Alloc = std::allocator<T> > class List { struct node {...}; typedef typename Alloc::rebind<node>::type NodeAlloc; //Verwendung von rebind<> ... };
-
Okay, das muss man wissen, danke
-
314159265358979 schrieb:
Außerdem finde ich, dass die list Klasse und nicht die node-Klasse für das Verketten zuständig sein sollte.
Warum?
314159265358979 schrieb:
Dann hast du hier ja placement-new und einen expliziten Destruktor-Aufruf verwendet. Ist das erlaubt, sollte man hier nicht die allocate und deallocate Funktionen verwenden?
construct kann in C++0x lediglich zum Kopieren verwendet werden und die Benutzung dieser Funktionen ist nicht vorgeschrieben (außer evtl. für Container, die tatsächlich mit Ts arbeiten).