Doppelt verkettete Liste als Ring
-
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.
-
volkard schrieb:
Mir will scheinen, ich würde mir damit erkaufen, daß ich gelegentlich Laufzeitnachteile gegen C-Code hätte.
*hust* premature ... *hust*
-
Hm. Wie gefällt
template <typename Allocator> void* operator new(std::size_t n, Allocator& alloc) { assert( n == sizeof( typename Allocator::value_type ) ); return alloc.allocate(1); } template <typename Allocator> void opertator delete(void* p, Allocator& alloc) { alloc.deallocate(static_cast<typename Allocator::value_type*>(p), 1); } ... void insert(node_base* right, const T& value) { new (alloc()) node_type(right, value); }?
-
Das placement new/delete gefällt gut.
Fein, daß gcc es inzwischen schafft. Bis neulich hat er das placement delete nicht ausgeführt, wenn es ein template war.
-
Habe das Ganze mal zu einer vollständigen Klasse zusammengesetzt, das Ganze kompiliert, ist aber sonst ungetested).
Aus list ausgelagert, wird schnell deutlich, dass es bei Ringlisten tatsächlich eine einzige modifizierende Operation gibt, die alle anderen erschlägt.
Nur der wirklich interessante Code hat im Folgenden mehrere (=2) Zeilen bekommen; alles andere ist ziemlich trivial.
Vielleicht hat ja mal jemand Lust, eine zweite Liste mit integriertem Link zu schrieben und macht ein paar Benchmark. Ich bezweifle eher, dass es da signifikante Performanceunterschiede gibt.#include <new> #include <cstddef> #include <iterator> #include <algorithm> #include <type_traits> class ring_node { public: ring_node() : next(this), prev(this) {} explicit ring_node(ring_node* next) : next(this), prev(this) { intersect(this, next); } ~ring_node() { intersect(this, next); } friend void intersect(ring_node* a, ring_node* b) { std::swap(a->prev->next , b->prev->next); std::swap(a->prev, b->prev); } ring_node* next; ring_node* prev; private: ring_node(const ring_node&); ring_node& operator=(const ring_node&); }; template <typename T> class list_node : public ring_node { public: list_node(ring_node* next, const T& data) : ring_node(next), data(data) {} T data; template <typename Allocator> static list_node* make(Allocator& alloc, ring_node* next, const T& value) { return new (alloc) list_node(next, value); } template <typename Allocator> static void unmake(Allocator& alloc, list_node* node) { node->~list_node(); operator delete(node, alloc); } private: template <typename Allocator> static void* operator new(std::size_t n, Allocator& alloc) { return alloc.allocate(1); } template <typename Allocator> static void operator delete(void* p, Allocator& alloc) { return alloc.deallocate(static_cast<list_node*>(p), 1); } }; template <typename T> class list_iterator : public std::iterator<std::bidirectional_iterator_tag, T> { public: list_iterator() {} list_iterator(const list_iterator<typename std::remove_const<T>::type>& other) : node(other.node) {} T& operator*() const { return static_cast<list_node<T>*>(node)->data; } T* operator->() const { return &**this; } list_iterator& operator++() { node = node->next; return *this; } list_iterator operator++(int) { return ++list_iterator(*this); } list_iterator& operator--() { node = node->prev; return *this; } list_iterator operator--(int) { return --list_iterator(*this); } bool operator==(const list_iterator& other) const { return node == other.node; } bool operator!=(const list_iterator& other) const { return !( *this == other ); } friend void splice(list_iterator pos, list_iterator first, list_iterator last) { intersect(last.node, pos.node); intersect(last.node, first.node); } friend void splice(list_iterator pos, list_iterator i) { splice(pos, i, i++); } private: list_iterator(ring_node* node) : node(node) {} ring_node* node; friend class list_iterator<const T>; template <typename, typename> friend class list; }; template <typename T, typename Allocator = std::allocator<T> > class list : private Allocator::template rebind<list_node<T> >::other { public: typedef T value_type; typedef list_node<T> node_type; typedef typename Allocator::template rebind<node_type>::other allocator; typedef list_iterator<T> iterator; typedef list_iterator<const T> const_iterator; typedef T& reference; typedef const T& const_reference; typedef T* pointer; typedef const T* const_pointer; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; list() {} list(const list& other) { std::copy(other.begin(), other.end(), std::back_inserter(*this)); } list(list&& other) { swap(other); } list& operator=(const list& rhs) { return *this = list(rhs); } list& operator=(list&& rhs) { swap(rhs); return *this; } ~list() { while( !empty() ) pop_back(); } iterator begin() { return dummy.next; } const_iterator begin() const { return dummy.next; } const_iterator cbegin() const { return dummy.next; } iterator end() { return &dummy; } const_iterator end() const { return &dummy; } const_iterator cend() const { return &dummy; } bool empty() const { return begin() == end(); } size_type size() const { return std::distance( begin(), end() ); } iterator insert(iterator pos, const T& value) { return node_type::make(alloc(), pos.node, value ); } iterator push_back(const T& value) { return insert(end(), value); } iterator push_front(const T& value) { return insert(begin(), value); } iterator erase(iterator pos) { return node_type::unmake(alloc(),static_cast<node_type*>(pos++.node)), pos; } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } T& front() { return *begin(); } const T& front() const { return *begin(); } T& back() { return *--end(); } const T& back() const { return *--end(); } void swap(list& other) { intersect(&dummy,&other.dummy); intersect(dummy.next,other.dummy.next); } friend void swap(list& a, list& b) { a.swap(b); } friend void splice(iterator pos, list& x) { splice(pos, x.begin(), x.end()); } private: allocator& alloc() { return *this; } mutable ring_node dummy; // Faulheitshack, damit list_iterator<const T> als const_iterator verwendet werden kann };
-
Erkläre mir mal, wie swap funktioniert. Und löst sich swap in 12 Zeigerzuweisungen auf?
-
volkard schrieb:
Erkläre mir mal, wie swap funktioniert.
Dazu erklär ich am besten was intersect tut:
Für zwei beliebige Knoten a,b werden deren Vorgänger ausgetauscht. Interessanterweise ist das für beliebige Knoten eine nützliche Operation:
Falls a == b: es passiert nichts
Falls a und b zum gleichen Ring gehören: der Ring wird an den Stellen a und b aufgeschnitten und zerfällt in 2 Teilstücke.
Falls a und b nicht zum gleichen Ring gehören, werden die einzel Ringe aufgeschnitten und die Endstücke verbunden.
Diese Operation ist offenbar kommutativ und selbstinvers.swap verknüpft nun die beiden Node-Ringe per intersect 2mal., wobei einmal vor und einmal nach dem dummy Knoten geschnitten wird. Beim ersten Mal erhält man einen einzelnen Ring, der beide Listen enthält, beim zweiten Mal zerfällt das Ganze wieder, aber die dummies sind gewandert (oder der Rest des Rings je nach Betrachtungsweise). Das gleiche Prinzip wird für splice verwendet.
volkard schrieb:
Und löst sich swap in 12 Zeigerzuweisungen auf?
swap benutzt intersect 2 mal, intersect benutzt 2 zeiger-swaps, jeder Zeigerswap zerfällt in 3 Zuweisungen beim Dreieckstausch; also ja.
Ich sehe keine Möglichkeit das besser zu machen (außer dass man evtl. Sonderbehandlungen für leere Listen einführen könnte) solange der Dummyknoten ins Listobjekt eingebettet wird.Edit: Nein, wenn man es per Hand macht könnte man auf 10 Zuweisungen kommen, wenn indem man ausnutzt, dass a->prev->next == a und a->next->prev == a.
In jedem Fall ging es mir hier sowieso mehr um Eleganz als um absolut maximale Performance bis zum letzten Takt. Wenn ich Performance brauche schreibe ich sowieso nicht meine eigene Liste
-
Die Bedeutung von intersect muß ich mir ausdrucken und unters Kopfkissen legen.
Ich habe den Eindruck, daß 10 Zeigerzuweisungen reichen, wenn ich klassisch vorgehe.
edit: 10, hab mich verguckt.
-
camper schrieb:
Wenn ich Performance brauche schreibe ich sowieso nicht meine eigene Liste
Komisch. Ich mache es nur wegen der Performance.
-
volkard schrieb:
Die Bedeutung von intersect muß ich mir ausdrucken und unters Kopfkissen legen.
Gute Idee. Die Erleutung ist mir gestern beim Schäfchenzählen gekommen.
Ich habe den Eindruck, daß 9 Zeigerzuweisungen reichen, wenn ich klassisch vorgehe.
Wie, es müssen schließlich 8 Zeiger geändert werden?