Doppelt verkettete Liste als Ring

CStoll

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<>
  ...
};

314159265358979

Okay, das muss man wissen, danke

camper

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).

volkard

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.

camper

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.

volkard

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.

camper

volkard schrieb:

Mir will scheinen, ich würde mir damit erkaufen, daß ich gelegentlich Laufzeitnachteile gegen C-Code hätte.

*hust* premature ... *hust*

camper

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);
        }

?

volkard

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.

camper

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
};

volkard

Erkläre mir mal, wie swap funktioniert. Und löst sich swap in 12 Zeigerzuweisungen auf?

camper

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

volkard

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.

volkard

camper schrieb:

Wenn ich Performance brauche schreibe ich sowieso nicht meine eigene Liste

Komisch. Ich mache es nur wegen der Performance.

camper

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?

volkard

Ich kann besser damit leben, wenn die Verknüpfungslogik in der Liste liegt und nicht in den Knoten.
Kleine Helferlein kann man in die nodes schubsen, aber keine Verantwortung und keine Automatismen mit den Nachbarn.

void base_node::relink(node& n)
    {
        prev->next=this;
        next->prev=this;
    }

void swap(list& a,list& b)
    {
        swap(a.dummy,b.dummy);
        a.relink();
        b.relink();
    }

Das wird doch fast automatisch hübsch so.

Oder

void swap(list& a,list& b)
    {
        base_node t=a.dummy;
        a.dummy.insert_between(b.prev,b.next);
        b.dummy.insert_between(t.prev,t.next);
    }

camper

volkard schrieb:

Ich kann besser damit leben, wenn die Verknüpfungslogik in der Liste liegt und nicht in den Knoten.

Ultimativ ist es eine Design- oder Vorstellungsfrage ob man akzeptiert das ein Ring aus Knoten eben eine separate Abstraktion ist (wesentliche Eigenschaft: jeder einzelne Knoten identifiziert den gesamten Ring), und eine Liste (wesentlich: hat Anfang und Ende) etwas anderes darstellt und den Ring aber zu Implementationszwecken nutzen kann.
Abgesehen davon schreibt jeder seine doppelt verketteten listen so wie du es tust: da lernt man nichts mehr.

void base_node::relink(node& n)
    {
        prev->next=this;
        next->prev=this;
    }

void swap(list& a,list& b)
    {
        swap(a.dummy,b.dummy);
        a.relink();
        b.relink();
    }

Das gefällt.

void swap(list& a,list& b)
    {
        base_node t=a.dummy;
        a.dummy.insert_between(b.prev,b.next);
        b.dummy.insert_between(t.prev,t.next);
    }

Das nicht. Das ist ein Mißbrauch der Innereien von insert_between, immerhin wird damit allerdings klar, wieso überhaupt zwei Argumente gebraucht werden.

314159265358979

camper schrieb:

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.
...

Kompliment, sehr elegant, auch wenn ich mir die Ringlogik nochmal durch den Kopf gehen lassen muss

Dinge, die mir unklar/aufgefallen sind:

friend void splice(list_iterator pos, list_iterator i) { splice(pos, i, i++); }

Du übergibst hier 2 mal i, wobei du i im Ausdruck veränderst. Ich bin mir nicht sicher, aber ist das nicht UB?

typedef typename Allocator::template rebind<node_type>::other allocator;

Warum muss hier 'template' stehen?

list& operator=(const list& rhs)                     { return *this = list(rhs); }
    list& operator=(list&& rhs)                          { swap(rhs); return *this; }

Die beiden könntest du einfacher haben:

list& operator = (list other) { swap(other); return *this; }

~list()                                              { while( !empty() ) pop_back(); }

Hier wäre es möglicherweise schneller, zu iterieren, node für node deallozieren und dann den Dummy zu richten.

Ansonsten bin ich froh, dass ich nicht der einzige bin, der so viele Funktionen in eine einzige Zeile schreibt

volkard

camper schrieb:

Abgesehen davon schreibt jeder seine doppelt verketteten listen so wie du es tust: da lernt man nichts mehr.

Stimmt wohl. Deine Techniken haben (waonders?) absolut ihre Berechtigung, geübt haben sollte man sie.

Sobald die Knoten schlau genug sind, selber sterben zu können, will man zum Beispiel

delete poeserFeind;
//in Wirklichkeit delete this;, aber ich will's man nicht total übertreiben

statt

welt.feinde.remove(poeserFeind);
//oder
poeserFeind.getOwningContainer().remove(poeserFeind);
//oder
declytype(poeserFeind)::remove(poeserFeind);//ganz bitter

Man hat schon schnell den Bedarf an schlauen Knoten.
Ich brauche gerne

unwichtigeListe.pushBackAndRemoveFromOldList(jetztUnwichtigerKandidat);

also

jetztUnwichtigerKandidat.unlink();//Jetzt ist er ein kleiner Kreis allein
unwichtigeListe.pushBack(jetztUnwichtigerKandidat);//oder sliceBack?, der Unterschied 
                                       //zwischen Knoten und Listen verschwimmt mir vor den Augen

Mhhm, vielleicht wäre es gut, einen Typen zu basteln, der definiert, daß ein Knoten freistehend ist und danglink enden hat.

unwichtigeListe.pushBack(jetztUnwichtigerKandidat.unlink());

Müß das wohl mal einbauen und schauen, wie es sich macht.

camper

314159265358979 schrieb:

Dinge, die mir unklar/aufgefallen sind:
friend void splice(list_iterator pos, list_iterator i) { splice(pos, i, i++); }
Du übergibst hier 2 mal i, wobei du i im Ausdruck veränderst. Ich bin mir nicht sicher, aber ist das nicht UB?

der ++-Operator hier ist kein eingebauter, sondern ein Funktionsaufruf, damit besteht kein Problem.

314159265358979 schrieb:

typedef typename Allocator::template rebind<node_type>::other allocator;
Warum muss hier 'template' stehen?

Weil rebind ein abhängiger Name ist, ohne template würde das ganze als Ausdruck angesehen werden, mit dem <-Operator (könnte ja sein, dass irgendein Typ ein Member rebind hat, dass tatsächlich ein Objekt darstellt...).

314159265358979 schrieb:

list& operator=(const list& rhs)                     { return *this = list(rhs); }
    list& operator=(list&& rhs)                          { swap(rhs); return *this; }

Die beiden könntest du einfacher haben:

list& operator = (list other) { swap(other); return *this; }

Stimmt, allerdings würde das im Movefall zum Aufruf des Movekonstruktors führen. Da dieser ebenfalls mit swap arbeitet, würde swap im Endeffekt sogar zweimal aufgerufen werden (ok... gelegentlich bin ich auch an Performance interessiert).

314159265358979 schrieb:

~list()                                              { while( !empty() ) pop_back(); }
Hier wäre es möglicherweise schneller, zu iterieren, node für node deallozieren und dann den Dummy zu richten.

Das macht bei intelligenten Knoten keinen Unterschied. Falls diese Implementation langsam ist, dann primär im Destruktor und zu einem geringeren Teil bei swap.