Doppelt verkettete Liste als Ring
-
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).
-
camper schrieb:
314159265358979 schrieb:
Außerdem finde ich, dass die list Klasse und nicht die node-Klasse für das Verketten zuständig sein sollte.
Warum?
Mindestens wegen der Namen. insert geht ja fast. insert_after oder insert_before geht. Oder mein insert_between. Aber bei diesem Konstruktor muß schon ein Kommentar her, was der außer der Konstruktion noch bewirkt.
Und doch habe ich ein schlechtes Gefühl, daß die Konstruktion eines nodes die Nachbarnodes verändet.
Im kokreten Fall kann man den Exception-Hammer auspacken:void insert_between(Node* prev,Node* next,T const& data) { Node* newnode=new Node(prev,next,data);//might throw prev->next=newnode; next->prev=newnode; }Das wäre auch lösbar, wenn die Rückverzeigerung nicht in base_node, sondern erst in node passieren würde. Aber das wäre auch seltsam, weil die Verzeigerung ja eigentlich unabhängig von den Nutzdaten ist. Man hat sofort Lust, sie dann doch noch runterzuschubsen in base_node.
-
volkard schrieb:
Im kokreten Fall kann man den Exception-Hammer auspacken:
void insert_between(Node* prev,Node* next,T const& data) { Node* newnode=new Node(prev,next,data);//might throw prev->next=newnode; next->prev=newnode; }Das wäre auch lösbar, wenn die Rückverzeigerung nicht in base_node, sondern erst in node passieren würde. Aber das wäre auch seltsam.
Aber nein: das Ganze funktioniert ja gerade dann wenn Exceptions auftreten mit T: die Basisklasse mit den Zeigern ist ja schon fertig konstruiert, also wird auch der Destruktor aufgerufen.
Überhaupt sehe ich das genau anders herum: node_base ist für die low-level Aspekte des Verlinkens zuständig, list kümmert sich um Werte. Die Exceptionkeule funktioniert nämlich auch anders herum: in der ursprünglichen Variante mit insert_between muss man schon kommentieren, warum die Verlinkung erst nach der Zuweisung von data passieren darf.
Kommen Exceptionsin Spiel muss sowieso noch ein bisschen getan werden, um keine Speicherlöscher zu produzieren:
void insert(node_base* right, const T& value) { node_type* new_node = alloc().allocate(1); try { new (static_cast<void*>(node)) node_type(right, value); } catch ( ... ) { alloc().deallocate(new_node, 1); throw; } }wobei das noch nicht schön ist.
-
camper schrieb:
Basisklasse mit den Zeigern ist ja schon fertig konstruiert, also wird auch der Destruktor aufgerufen.
Stimmt, der Destruktor verbindet ja die beiden Nachbarn wieder.
Also keine technischen Argumente dagegen. Es gefällt mir einfach nicht so supi. Mir will scheinen, ich würde mir damit erkaufen, daß ich gelegentlich Laufzeitnachteile gegen C-Code hätte.