...

[haifaik]

Sone schrieb:

Jeder sollte das schon einmal gemacht haben.

klar. Meine letzte war vor etwa einem Jahr.

Dann sollte sie ja diesmal richtig sein.

Sone schrieb:

Dann zeige mir, wie man (ohne Performance-Verlust und mit weniger Code, was ja anscheinend das Ziel ist) dasselbe erreicht wie im Code unten.

Dann mach du erstmal deine Implementierung ohne Performance-Verlust.

struct Node
        {
                Node *prev,
                     *next;

                pointer data; // WTF?

Die zusätzliche Indirektion bringt hier nichts und schadet nur. Warum ein Pointer?

struct node {
  node *next, // vorwärtsiterieren ist im Zweifelsfall wichtiger als
       *prev; // rückwärtsiterieren
  T data; 
}

Ausserdem sehe ich überall new/delete. Wenn du Allocator willst, dann musst du den auch verwenden.
Tipp: "Du musst den Allocator rebinden" (Zitat von Kellerautomat, Seite 2)

[the daily lol]

Sone hat doch mal zugegeben das er nur für die Lolz proggt, also bewußt schlecht, damit andere darüber lolen können.

[haifaik]

Sone schrieb:

Dann zeige mir, wie man (ohne Performance-Verlust und mit weniger Code, was ja anscheinend das Ziel ist) dasselbe erreicht wie im Code unten.

Prinzipiell: http://ideone.com/NMRpbG
Weniger Code ist nur ein Nebeneffekt, hauptsächlich geht es um die Vorzüge von RAII: Fehlerfreies Ressourcenmanagement.

(Beispiel: dein Code sigsevt)

[Sone]

haifaik schrieb:

struct Node
        {
                Node *prev,
                     *next;
 
                pointer data; // WTF?

Die zusätzliche Indirektion bringt hier nichts und schadet nur. Warum ein Pointer?

struct node {
  node *next, // vorwärtsiterieren ist im Zweifelsfall wichtiger als
       *prev; // rückwärtsiterieren
  T data; 
}

Ausserdem sehe ich überall new/delete. Wenn du Allocator willst, dann musst du den auch verwenden.
Tipp: "Du musst den Allocator rebinden" (Zitat von Kellerautomat, Seite 2)

Nein, nein, nein. Genau deswegen ja eben nicht. Die Idee ist, dass ich die Node bequem selbst allokieren kann. Das einzige, wofür der Allokator zuständig ist, ist das Element selbst - und das alloziere ich separat. Wofür soll ich noch extra einen zweiten Allokator halten? So finde ich das besser. Und der User hat auch alles was er will - von der Node, diesen drei Zeigern und nicht mehr, und wie die alloziert wird, weiß er nichts und nichts.

camper schrieb:

template<typename Value,
         typename Alloc = std::allocator<Value>>
class List : ListAlloc<Value, Alloc>
{
    using base = typename List::base;

?

Na gut, das ist tatsächlich ein bisschen typedef -Geschlurkse.

typedef iterator const const_iterator;

wirklich?

Als ob ich eine extra Klasse für const_iterator schreibe, das ist doch der Overkill. Was ist an meiner iterator-Version, die ja für die const-Version entsprechende Überladungen hat, so falsch?

haifaik schrieb:

(Beispiel: dein Code sigsevt)

Das war nur ein kleiner Flüchtigkeitsfehler! Ich habe im Makro was vergessen, da waren zwei, drei Zeichen falsch. Kann doch mal passieren. So geht es: http://ideone.com/P6IBYq
(Findest du den Unterschied?)

Tatsächlich ist meine Version noch nicht komplett Exception-Safe. In den einen catch-Block bei emplace musste noch was rein, ein delete. http://ideone.com/rJ4sOr

Da wäre RAII tatsächlich ganz handy.

[Jester]

Sone schrieb:

Nein, nein, nein. Genau deswegen ja eben nicht. Die Idee ist, dass ich die Node bequem selbst allokieren kann. Das einzige, wofür der Allokator zuständig ist, ist das Element selbst - und das alloziere ich separat.

Genau, warum einen new-aufruf pro insertion wenn man auch zwei haben kann. Ist ja nicht so dass die allokation bei listen ein botleneck wäre... Oh wait.

[Sone]

Jester schrieb:

Sone schrieb:

Nein, nein, nein. Genau deswegen ja eben nicht. Die Idee ist, dass ich die Node bequem selbst allokieren kann. Das einzige, wofür der Allokator zuständig ist, ist das Element selbst - und das alloziere ich separat.

Genau, warum einen new-aufruf pro insertion wenn man auch zwei haben kann. Ist ja nicht so dass die allokation bei listen ein botleneck wäre... Oh wait.

Oh! Das stimmt. Das habe ich jetzt nicht gesehen. :kopf->tisch:
Gut, ab zum refactoring :sigh:

[camper]

Sone schrieb:

typedef iterator const const_iterator;

wirklich?

Als ob ich eine extra Klasse für const_iterator schreibe, das ist doch der Overkill. Was ist an meiner iterator-Version, die ja für die const-Version entsprechende Überladungen hat, so falsch?

List<int> l;
List<int>::const_iterator x = l.end();
List<int>::iterator y = x;

findest du es ok, dass diese Initialisierung funktioniert?

[haifaik]

Sone schrieb:

Jester schrieb:

Sone schrieb:

Nein, nein, nein. Genau deswegen ja eben nicht. Die Idee ist, dass ich die Node bequem selbst allokieren kann. Das einzige, wofür der Allokator zuständig ist, ist das Element selbst - und das alloziere ich separat.

Genau, warum einen new-aufruf pro insertion wenn man auch zwei haben kann. Ist ja nicht so dass die allokation bei listen ein botleneck wäre... Oh wait.

Oh! Das stimmt. Das habe ich jetzt nicht gesehen. :kopf->tisch:
Gut, ab zum refactoring :sigh:

Geschwindigkeit ist nur einer der Gründe (z.B. neben enier grösseren Anzahl allocs kommt auch grösserer Speicherverbrauch, grössere Speicherverstückelung und langsamere Iterierungszeit wegen erhöhter Anzahl Speichersprünge hinzu).

An AllocatorAwareContainer is a Container that holds an instance of an Allocator and uses that instance to allocate and deallocate memory in all of its member functions.

Du *darfst* gar nicht new/delete verwenden, wenn du allocator-aware sein möchtest.

Davon abgesehen musst du auch nur genau einen Allocator halten, den auf node rebindeten.

@const_iterator: Mach iterator als Template über value_type, dann kann der einmal const und einmal non-const sein.

[Sone]

Ok, hier die (viel) bessere Version: http://ideone.com/2jXHS8
Hätte nicht so stur sein sollen. Jetzt gibt es auch eine const_iterator -Klasse.
Außerdem ist jetzt mStart der Knoten vor dem ersten Element, was auch einige unnötige Abfragen und drumherum-Blödsinn vermeidet.
Und natürlich kein Zeiger mehr in Node.
Das Erzeugen von Nodes ist in

template<typename... Args>
    Node* _alloc_make_node( NodeBase* prev, NodeBase* next, Args&&... args )
    {
        Node* node = allocator_traits::allocate( mAllocator, 1 );

        try
        {
            allocator_traits::construct( mAllocator, node, prev, next, std::forward<Args>(args)... );
        }
        catch(...)
        {
            allocator_traits::deallocate( mAllocator, node, 1 );
            throw;
        }

        return node;
    }

ausgelagert. Nodes mit Elementen sind Node - NodeBase ist die Basisklasse, in der keine Daten enthalten sind, sondern nur der Zeiger auf die nächste oder vorige NodeBase . mStart und mEnd sind NodeBase s

Edit:

@const_iterator: Mach iterator als Template über value_type, dann kann der einmal const und einmal non-const sein.

Ja, so geht es schöner.

[haifaik]

Sone schrieb:

template<typename... Args>
    Node* _alloc_make_node( NodeBase* prev, NodeBase* next, Args&&... args )
    {
        Node* node = allocator_traits::allocate( mAllocator, 1 );
 
        try
        {
            allocator_traits::construct( mAllocator, node, prev, next, std::forward<Args>(args)... );
        }
        catch(...)
        {
            allocator_traits::deallocate( mAllocator, node, 1 );
            throw;
        }
 
        return node;
    }

=>

template<typename... Args> 
Node* _alloc_make_node( NodeBase* prev, NodeBase* next, Args&&... args ) 
{ 
  auto dealloc = [&](){allocator_traits::deallocate( mAllocator, node, 1 );};
  std::unique_ptr<Node, decltype(dealloc)> node(allocator_traits::allocate( mAllocator, 1 ), dealloc);
  allocator_traits::construct( mAllocator, node, prev, next, std::forward<Args>(args)... ); 
  return node.release();
}

[haifaik]

Sone schrieb:

if( prev )
            prev->next = node;
        if( next )
            next->prev = node;

Mein Code hat da keine ifs.

[Sone]

haifaik schrieb:

Sone schrieb:

if( prev )
            prev->next = node;
        if( next )
            next->prev = node;

Mein Code hat da keine ifs.

Meiner auch nicht. Wo hast du das her?
Edit: Ah, ich sehe. Bei der _notify-Version. Gut, das wahr tatsächlich absichtlich - aber nicht nötig.

[camper]

struct const_iterator : std::iterator<std::bidirectional_iterator_tag,
                                              value_type const,
                                          difference_type,
                                              const_pointer,
                                              const_reference>

Das soll sicher value_type ohne const sein.

Der intern verwendete Allocator ist nicht Teil des Interfaces. Es müssen also zwei Allocatorobjekte gespeichert werden (sinnvollerweise nutzt man hier EBO aus, wenn möglich).

[haifaik]

camper schrieb:

Der intern verwendete Allocator ist nicht Teil des Interfaces. Es müssen also zwei Allocatorobjekte gespeichert werden (sinnvollerweise nutzt man hier EBO aus, wenn möglich).

Wieso zwei? Man braucht doch nur den internen allocator<node<T>> , der allocator<T> ist unnütz.

Sone schrieb:

struct NodeBase {...} mStart, mEnd;
mutable NodeBase mStart, mEnd;

Da ist zu viel Code, als dass ich Lust habe durchzugucken, aber mir wird nicht klar, weshalb du 4 Member brauchst bzw. 2 Member möchtest. mStart ist irgendwie sinnlos.

[camper]

haifaik schrieb:

camper schrieb:

Der intern verwendete Allocator ist nicht Teil des Interfaces. Es müssen also zwei Allocatorobjekte gespeichert werden (sinnvollerweise nutzt man hier EBO aus, wenn möglich).

Wieso zwei? Man braucht doch nur den internen allocator<node<T>> , der allocator<T> ist unnütz.

Stimmt, aber get_allocator muss eine Kopie zurückgeben.

[Sone]

Sone schrieb:

struct NodeBase {...} mStart, mEnd;
mutable NodeBase mStart, mEnd;

Da ist zu viel Code, als dass ich Lust habe durchzugucken, aber mir wird nicht klar, weshalb du 4 Member brauchst bzw. 2 Member möchtest. mStart ist irgendwie sinnlos.

Nein, nein. Das war wieder ein Flüchtigkeitsfehler. mStart und mEnd in der abgeleiteten Klasse fliegen raus.

Edit: Ja, gefixt: http://ideone.com/2jXHS8

[Sone]

camper schrieb:

haifaik schrieb:

camper schrieb:

Der intern verwendete Allocator ist nicht Teil des Interfaces. Es müssen also zwei Allocatorobjekte gespeichert werden (sinnvollerweise nutzt man hier EBO aus, wenn möglich).

Wieso zwei? Man braucht doch nur den internen allocator<node<T>> , der allocator<T> ist unnütz.

Stimmt, aber get_allocator muss eine Kopie zurückgeben.

Das dachte ich auch gerade. So gibt man ja AFAICS den Zugriff auf Node frei... das geht ja nicht. Dann muss also ein unbenutzter Allokator gehalten und zurückgegeben werden?

[haifaik]

camper schrieb:

Stimmt, aber get_allocator muss eine Kopie zurückgeben.

Schlüsselwort "Kopie". Zum Glück ist es ein requirement, dass es einen entsprechenden Kopierkonstruktor vom rebindeten Allocator gibt.

[haifaik]

Sone schrieb:

mStart ist irgendwie sinnlos.

Edit: Ja, gefixt: http://ideone.com/2jXHS8

mStart ist immer noch unnötig.

[Sone]

haifaik schrieb:

Sone schrieb:

mStart ist irgendwie sinnlos.

Edit: Ja, gefixt: http://ideone.com/2jXHS8

mStart ist immer noch unnötig.

Willst du einen Zeiger auf die NodeBase vor dem ersten Element als next -Zeiger in mEnd speichern? Der kleine "Zirkel"-Trick?