Dummy Knoten

frage 2.7.1.9 schrieb:

Warum brauchst du überhaupt einen Dummy-Knoten als erstes Element? Es gibt doch kein prev. Warum hast du nicht einfach nur nen Pointer auf der erste Element um es zu erkennen?

Hm, das ist eine gute Frage. Wenn du, Shade, sowieso immer weißt wann es sich um einen Dummy-Knoten handelt und wann nicht, warum brauchst du diese dann überhaupt?

Shade Of Mine

Nachdenklicher Leser schrieb:

Hm, das ist eine gute Frage. Wenn du, Shade, sowieso immer weißt wann es sich um einen Dummy-Knoten handelt und wann nicht, warum brauchst du diese dann überhaupt?

Das steht nicht zur debatte.
es ist technisch die beste mir bekannte loesung hier mit einem dummy objekt zu arbeiten.

ich ueberlege die ganze zeit ob man da was mit makros und templates bauen kann dass die downcasts versteckt. die sehen naemlich so haesslich aus

ernst gemeinte frage: wieso ist der knoten dummy?

wenn du eine liste hast, was anscheinend der fall ist, bedeutet das, dass du einen knoten ohne inhalt hast, aber trotzdem eine instanz von value_type im knoten existiert. dafür gibt es keine lösung mit nur einer struktur.

ohne jeden kontext ist es aber schwer, eine antwort zu schreiben. du musst uns also wahrscheinlich mehr information geben, was genau du dann mit dem knoten machst und wieso er nötig ist.

und vielleicht beschimpfst du nicht leute, die dir helfen wollen. das sollte nicht die art eines moderators sein. (das sollte niemandes art sein...)

Shade Of Mine

sorry, ich hatte erwartet dass vernuenftige antworten kommen...

der dummy knoten ist notwendig. punkt. aus. schluss.

dummy knoten sind generell etwas das oefters auftritt. das sollte eigentlich nicht verwundern.

die frage war eigentlich ganz simpel:
gibt es eine moeglichkeit dummy knoten zu erstellen ohne dauernd downcasts noetig zu haben, bzw. diese downcasts zu verstecken?

einfache frage - schwere antwort, keine frage. aber bisher gab es nicht einen post der sinnvoll und on topic war... aber das hatte ich ehrlich gesagt nicht erwartet. es war mehr die leise hoffnung dass jemand das problem irgendwann mal eleganter geloest hatte.

unskilled

Sollen die dummy-knoten denn unabhängig davon auftreten können, ob das element vll das letzte oder erste der liste/.... ist?

wenn nicht (und so fern du eine doppelt verkettete liste hast), könntest du ja einfach this->next auf this zeigen lassen oder das gleiche halt mir prev... aber is nat auch doof, wenn man jedes ma so was überprüfen muss...

also wie wärs mit so was?

{Müll (ab hier edit)}

omg - hab ich ma wieder nur die hälfte gelesen... sry... Vll geht es ja so (kein Plan, aber wenn ich eh scho mist geschrieben hab, warum dann nicht gleich bissl mehr? ^^):

#include <iostream>

struct node_base_base
 {
  node_base_base *next;

  node_base_base (node_base_base *_next) : next (_next) {}

  virtual ~node_base_base () {}
 };

template <bool is_dummy>
 struct node_base : node_base_base
  {
   bool IsDummy () const {return is_dummy;}

   node_base (node_base_base *_next) : node_base_base (_next) {}

   virtual ~node_base () {}
  };

template <class T, bool IsDummy = true> //dummy
 struct node : node_base <IsDummy>
  {
   node (node_base_base *_next) : node_base (_next) {}

   virtual ~node () {}
  };

 template <class T>
  struct node <T, false> : node_base <false>
  {
   T value;

   node (const T &_value, node_base *_next = NULL) : value (_value), node_base (_next) {}

   virtual ~node () {}
  };

int main ()
{
node <int> * first_element (0);
for (node_base_base *a (first_element); a != 0; a = a->next)
  {
    if (!static_cast <node <int> *> (a)->IsDummy ())
      std::cout << static_cast <node <int, false> *> (a)->value << std::endl;
  }
}

naja - ist vll nicht die allerschönste Lösung, aber

pumuckl

Ich halte die Fragen/Antworten zum Teil für durchaus vernünftig. Nach dem was du in der Fragestellung offenbarst besteht ein Dummyknoten bisher bei dir nur aus einem nicht genutzten value_type und einem Pointer auf einen Knoten, die frage warum du statt des Dummys also nicht nur einen simplen Pointer verwendest ist also berechtigt, denn für die Leser hier ist nicht ersichtlich, warum du den zusätzlichen Speicherverbrauch und die zusätzliche Indirektion nicht einfach sparst - dafür mag es Gründe geben, allerdings musst du zugeben dass die den Lesern nicht offensichtlich sind. Und "steht nicht zur Debatte" oder "beste mir bekannte Lösung" oder "punkt.aus.schluss" sind keine gültgen Gründe für eine Designentscheidung.
Du verlangst offenbar Antworten, die etwas berücksichtigen was du offenbar nicht preisgeben willst. Unter solchen Umständen kann dir keiner wirklich helfen.

@topic:
bei kleinen value_types fällt die extra Speicherbelegung nicht ins Gewicht, und wenn du nur wenige (oder einen) der dummy-nodes brauchst würd ichs einfach sein lassen mir darüber gedanken zu machen - vorausgesetzt der value_type hat einen default-Ctor. Bei großen value_types lohnt es evtl statt einer direkten Speicherung der Werte auch dafür pointer zu verwenden. der dummy-node hat dann halt einen null-pointer.
Den overhead bei den dummies ganz zu vermeiden geht nicht, du müsstest wohl verschiedene node-klassen haben die auf das jeweils nächste Element gleichartig zugreifen können. Polymorphie und virtuelle zugriffsfunktionen fürs nächste Element wären die Konsequenz, damit handelst du dir aber erstens für jedes Objket die Speicherkosten für einen vptr ein sowie bei jedem entlanghangeln die zusätzliche Indirektion über den vptr, soviel zum Thema overhead vermeiden.

Da du allerdings schreibst dass der dummy-node nur als erstes auftritt, wird das einfachste und effektivste eben doch sein, bei Bedarf zu casten oder den Zugriff über den ternäen operator zu regeln. Wenn du ganz fancy werden willst könntest du eventuell irgendwie die short-cirquit-operatoren einsetzen die in den meisten Fällen zünden und eben nur beim Spezialfall in den alternativen Ausführungszweig gehen.

Nach dem was du oben geschrieben hast handelt es sich aber nur um Schönheits-OPs (zugegeben, casts sind nicht besonders attraktiv, aber manchmal eben nötig), und es scheint fraglich, ob es sich lohnt, da Zeit und Hirnschmalz reinzustecken - da was zu optimieren bringt vermutlich so wenig Zeit dass die Datenstruktur schon sehr extrem angestrengt werden müsste um den Aufwand bei der Programmierung aufzuwiegen

Tachyon

Shade Of Mine schrieb:

sorry, ich hatte erwartet dass vernuenftige antworten kommen...

der dummy knoten ist notwendig. punkt. aus. schluss.

dummy knoten sind generell etwas das oefters auftritt. das sollte eigentlich nicht verwundern.

die frage war eigentlich ganz simpel:
gibt es eine moeglichkeit dummy knoten zu erstellen ohne dauernd downcasts noetig zu haben, bzw. diese downcasts zu verstecken?

einfache frage - schwere antwort, keine frage. aber bisher gab es nicht einen post der sinnvoll und on topic war... aber das hatte ich ehrlich gesagt nicht erwartet. es war mehr die leise hoffnung dass jemand das problem irgendwann mal eleganter geloest hatte.

Nichts für ungut, aber mit den bestehenden Informationen sind der Großteil der Antworten hier durchaus sinnvoll. Vielleicht hättest Du konkret sagen sollen, dass ein Dummyknoten unerlässlich ist, anstatt hier jeden, der versucht zu helfen zu beleidigen.

Die Art und Weise, wie Du Dich hier aufführst, zeigt wirklich eine grenzenlose (und mit Sicherheit nicht gerechtfertigte) Arroganz. Für jemanden, der hier Moderator ist, finde ich solch ein Verhalten wirklich ziemlich daneben.

Zum Thema:
Vielleicht könnte man einen Dummy repräsentieren, indem man einen Pointer, anstatt einer Referenz übergibt, und dür Dummies überigbt man Null-Pointer. Das wäre auch etwas optimaler, was den Speicherbedarf betrifft, vor allem, wenn es sich um große "Value-Typen" handelt.

camper

Shade Of Mine schrieb:

aber ist das die standard variante oder gibt es etwas huebscheres ohne downcasts?

Bisher habe ich in der Hinsicht immer nur Handgemachtes gesehen, ohne dass der Schwerpunkt auf Eleganz gelegt wurde. Wenn wir "Node" nicht als komplette Objektbeschreibung sondern nur als Spezifikation eines Interfaces betrachten, kommen wir weiter. Denn zwar kann ein Objekt eines bestimmten keine "optionalen" Member haben, wohl aber können wir Memberfunktionen definieren, die nicht in jedem Falle etwas brauchbares produzieren. Das könnte dann z.B. so aussehen:

template<typename T>
    struct node;
    struct node_base
    {
        node_base* next;

        node_base(node_base* next = 0)
        : next( next )
        {}
        template<typename T>
        T& data() { return static_cast< node< T >* >( this )->data_; }
        template<typename T>
        const T& data() const { return static_cast< const node< T >* >( this )->data_; }
    };
    template<typename T>
    struct node : node_base
    {
        node(const T& v = T(), node_base* next = 0)
            : node_base( next ), data_( v )
        T data_;
    };

Der ins Containerobjekt eingebettete Dummyknoten ist dann schlicht nur ein node_base und im client-code sind keine zusätzlichen Casts notwendig. Nützlich wird das vor allem dann, wenn wir spezielleren Anforderungen genügen wollen. z.B. könnten wir die verzögerte Konstruktion der Werte unterstützen. Ist unser T (exceptionfrei) move- bzw. copy-konstruierbar können wir dann ohne Overhead Einfügeoperationen formulieren, die die starke Garantie bieten.

template<typename T>
class doubly_linked_list
{
private:
    struct node
    {
        node* next;
        node* prev;
        struct nolink_tag {};
        node(node* next, node* prev, nolink_tag)
            : next( next ), prev( prev )
        {}
        node(node* next, node* prev)
            : next( next ), prev( prev )
        {
            relink();
        }
        template<typename... Args>
        node(node* next, node* prev, Args&&... args)
            : next( next ), prev( prev )
        {
            construct( args... );
            relink();
        }
        void link()
        {
            prev->next = this;
            next->prev = this;
        }
        void unlink()
        {
            prev->next = next;
            next->prev = prev;
        }
        static constexpr size_t total_alignment()
        {
            return max( alignof( node ), alignof( T ) );
        }
        static constexpr size_t data_offset()
        {
            return ( sizeof( node ) + total_alignment() - 1 ) / total_alignment() * total_alignment();
        }
        T& data()
        {
            return *reinterpret_cast< T* >( reinterpret_cast< char* >( this ) + data_offset() );
        }
        const T& data() const
        {
            return const_cast< node& >( *this ).data();
        }
        template<typename... Args>
        void construct(Args&&... args)
        {
            new( static_cast< void* >( addressof( data() ) ) T( forward< Args >( args )... );
        }
        void destroy()
        {
            data().~T();
        }
        static void* operator new(size_t size)
        {
            assert( size == sizeof( node ) );
            return ::new char[ data_offset() + sizeof( T ) ];
        }
        static void operator delete(void* p)
        {
            delete [] static_cast< char* >( p );
        }
    private:
        node(node&);
        void operator=(node&);
        static void* operator new[](size_t);
        static void operator delete[](void*);
    };
public:
    typedef T value_type;
    class iterator
    {
        node* node_ptr();
        /* ... */
    };
    class const_iterator { /* ... */ };
    doubly_linked_list()
        : dummy( &dummy, &dummy, node::nolink_tag() )
    {}
...
    template<typename InputIterator>
    void insert(iterator where, InputIterator first, InputIterator last)
    {
        typedef typename iterator_traits< InputIterator >::difference_type diff_t;
        if ( const diff_t dist = distance( first, last ) )
        {
            diff_t i = 0;
            try
            {
                node* dest = new node( where.node_ptr(), where.node_ptr()->prev );
                for ( ; ++i != dist; )
                    new node( where.node_ptr(), where.node_ptr()->prev );
                for ( ; first != last; ++first, --i )
                {
                    dest->construct( *first );
                    dest = dest->next;
                }
            }
            catch ( ... )
            {
                for ( ; i-- != 0; )
                {
                    node* p = where.node_ptr()->prev;
                    p->unlink();
                    delete p;
                }
                throw;
            }
        }
    }
private:
    node dummy;
};

Das Interface node ist hier immer noch im Wesentlichen identisch zum ursprünglichen mit node_base.

Hast du bereits in Betracht gezogen das value_type Attribut in ein boost::optional zu verpacken, oder scheidet diese Lösung aus?

Bzw. suchst du überhaupt eine konkrete Lösung oder interressiert es dich einfach nur wie man das von dir vorgegebene Problem mit den vorgegebenen Rahmenbedingungen möglichst elegant lösen kann?

Shade Of Mine

@Camper:
nett nett, sowas in der Art habe ich gesucht.
danke.
manchmal hat man ein brett vor dem kopf - das hätte mir auch einfallen könne. simpel aber elegant

@die anderen:
der dummy knoten steht nicht zur debatte - das ist eine themenverfehlung wer den weghaben will. ich brauche ihn und das ist einfach so.

Ist das wirklich die Standardvorgehensweise, oder nur was selber ausgedachtes? Ein reinterpret cast auf einen Pointer der irgendwo in den Knoten zeigt, sieht mir mehr nach low level C style gehacke aus, als nach schöner Standardlösung.

camper

nicht wirklich oder schrieb:

Ist das wirklich die Standardvorgehensweise, oder nur was selber ausgedachtes? Ein reinterpret cast auf einen Pointer der irgendwo in den Knoten zeigt, sieht mir mehr nach low level C style gehacke aus, als nach schöner Standardlösung.

Da verwechselst du was.
1. die ursprüngliche Frage zielte auf ein "schönes" und handliches Interface ab.
2. der vorgestellte Code-Entwurf dient gerade dazu, dass es möglich ist, dieses Interface einfach und sauber zu halten, auch wenn die Innereien mal etwas komplizierter werden: das ist, was Eleganz ausmacht.
3. "low level C" ist ein wichtiger Bestandteil von C++. So wenig, wie es sinnvoll es, in C++ im Allgemeinen einen C-Stil beizubehalten (einfach weil C++ bessere Abstraktionsmittel zur Verfügung stellt), ist eine Position gerechtfertigt, die C-Stil völlig verbietet, ohne mögliche Alternativen zu untersuchen.
4. der gezeigte Code ist eine mögliche Lösung für ein spezifisches Problem. Ich würde nie soweit gehen, diese als einzig Möglichkeit hinzustellen. Jede hinreichend komplexe Stück Code stellt ohnehin immer nur einen Kompromiss dar. Bezogen auf diese Prämissen denke ich aber, das er relativ sauber gehalten ist (der Fokus ist auf Standardkonformität gerichtet, unter Annahme bestimmter Erweiterungen durch den nächsten Standard und somit auch Portabilität).
5. wie ich bereits geschrieben habe, ist mir keine echete "Standardvorgehensweise" bekannt. Für ein echtes Pattern ist es inhaltlich zu dünn, für ein Idiom wiederum eher zu komplex.