3. Doppelt verkettete Liste als Ring

Doppelt verkettete Liste als Ring

  • V

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

    0
  • C
    Mod

    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 🙂

    0
  • V

    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.

    0
  • V

    camper schrieb:

    Wenn ich Performance brauche schreibe ich sowieso nicht meine eigene Liste 🙂

    Komisch. Ich mache es nur wegen der Performance.

    0
  • C
    Mod

    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?

    0
  • V

    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);
    }
    0
  • C
    Mod

    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.

    0
  • 3

    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 😉

    0
  • V

    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.

    0
  • C
    Mod

    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.

    0
  • C

    camper schrieb:

    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.

    Auch wenn es eine Funktion ist, ist nicht definiert, in welcher Reihenfolge die Parameter von splice() ausgewertet werden.

    0
  • V

    camper schrieb:

    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,

    Mir hat es auch nicht gefallen, aber konnte es nicht so auf den Punkt bringen. Ich muß echt mehr mit anderen Programmierern über meinen Code sprechen. Ach, was. Wer muß das nicht?

    camper schrieb:

    immerhin wird damit allerdings klar, wieso überhaupt zwei Argumente gebraucht werden.

    Sie sollten eigentlich nicht nur für die Zweckentfremdung gebraucht werden. Das entsprcht meinem ersten Gedanken, wenn ich auf den auf Paier gemalten Ring schaue: push_back heißt dür mich direkt, daß ich den neuen Knoten zwischen dem Vorgänger des dummies und dem dummy einfüge. Es heißt nicht so direkt, daß ich den neuen Knoten vor dem dummy oder gar hinter dem Vorgänger des dummies einfüge.

    0
  • C
    Mod

    CStoll schrieb:

    camper schrieb:

    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.

    Auch wenn es eine Funktion ist, ist nicht definiert, in welcher Reihenfolge die Parameter von splice() ausgewertet werden.

    Stimmt. War zu faul, next und prev-Funktionen zu benutzen. Also nochmal

    #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);
    }
    friend ring_node* prev(ring_node* node)                      { return node->prev; }
    friend ring_node* next(ring_node* node)                      { return node->next; }
private:
    ring_node* next;
    ring_node* prev;
    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 = next(node); return *this; }
    list_iterator operator++(int)                          { return next(node); }
    list_iterator& operator--()                            { node = prev(node); return *this; }
    list_iterator operator--(int)                          { return prev(node); }
    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, std::next(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 next(&dummy); }
    const_iterator begin() const                         { return next(&dummy); }
    const_iterator cbegin() const                        { return next(&dummy); }
    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*>(std::next(pos).node)), pos; }
    void pop_back()                                      { erase(std::prev(end())); }
    void pop_front()                                     { erase(begin()); }

    T& front()                                           { return *begin(); }
    const T& front() const                               { return *begin(); }
    T& back()                                            { return *std::prev(end()); }
    const T& back() const                                { return *std::prev(end()); }

    void swap(list& other)
    {
        intersect(&dummy,&other.dummy);
        intersect(next(&dummy),next(&other.dummy));
    }
    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
};

    Jetzt wäre noch zu überlegen, ob man intersect irgendwie so in atomische Operationen zerlegen kann, dass eine lock-freie Liste daraus wird.
    Und vielleicht noch einen besseren Namen dafür finden (crossover, trade_links ... ? )

    0
  • V

    Bevor die Liste die Weltherrschaft erringt, möchte ich anregen, daß wir next nur für einfach verkettete Listen benutzen und für doppelt verkettete prev/pred.

    0
  • 3

    volkard schrieb:

    Bevor die Liste die Weltherrschaft erringt, möchte ich anregen, daß wir next nur für einfach verkettete Listen benutzen und für doppelt verkettete prev/pred.

    Wofür steht denn pred? prev und next passt doch.

    0
  • V

    314159265358979 schrieb:

    Wofür steht denn pred? prev und next passt doch.

    predecessor oder so.

    0
  • C
    Mod

    Mit

    friend void intersect(ring_node* a, ring_node* b)
    {
        std::swap(a->prev, b->prev);
        a->prev->next = a;
        b->prev->next = b;
    }

    kann die Weltherrschaft übernommen werden. 5 Zuweisungen, mithin 10 für swap oder splice.

    0
Anmelden zum Antworten