...

[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?

[haifaik]

Sone schrieb:

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

Exakt.

[camper]

haifaik schrieb:

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.

Wohl eher "Pseudo-Kopie" Der Standard verwendet in diesem Absatz 23.2.1/7 einen ziemlich weitgefassten Kopie-Begriff. Normalerweise ist eine Kopie eines Objektes ja ein Objekt des gleichen Typs wie des Ausgangsobjektes.

So wie es gemeint ist, macht es nat. auch viel mehr Sinn, danke für den Hinweis.

@Sone: wieso mutable?

[Sone]

#define DEFINE_OP( class, mem, ch ) \
    class& operator ch() noexcept \
    { \
        p = p->mem; \
        return *this; \
    }

#define DEFINE_POST_OP( class, ch ) \
    class operator ch(int) noexcept \
    { \
        auto rval = *this; \
        ch*this; \
        return rval; \
    }

private:

	template<typename cv_value_t>
	struct iterator_base : std::iterator<std::bidirectional_iterator_tag,
	                                cv_value_t,
                                    difference_type>
	{
	private:

		using base = std::iterator<std::bidirectional_iterator_tag,
	                               cv_value_t,
                                   difference_type>;

		friend class List;

		NodeBase* p;

		iterator_base( NodeBase* p ) noexcept :
			p{p} {}

	public:

	    iterator_base() noexcept :
	        iterator_base{nullptr} {}

		iterator_base( iterator_base<typename std::remove_cv<cv_value_t>::type> const& it ) noexcept:
			p{it.p} {}

		typename base::reference operator*() noexcept { return static_cast<Node*>(p)->data; }
		typename base::pointer operator->() noexcept { return &static_cast<Node*>(p)->data; }

		DEFINE_OP( iterator_base, next, ++ )
		DEFINE_OP( iterator_base, prev, -- )
		DEFINE_POST_OP( iterator_base, ++ )
		DEFINE_POST_OP( iterator_base, -- )

		/// Vergleichs-Operatoren als Member: der operator!= hat bei der globalen Version irgendwie nicht funktioniert. Macht hier sowieso keinen Unterschied.
		template<typename cv_value_t_other>
		bool operator==( iterator_base<cv_value_t_other> other ) const noexcept { return p == other.p; }
		template<typename cv_value_t_other>
		bool operator!=( iterator_base<cv_value_t_other> other ) const noexcept { return !(*this == other); }
	};

#undef DEFINE_POST_OP
#undef DEFINE_OP

public:

	typedef iterator_base<value_type> iterator;
	typedef iterator_base<value_type const> const_iterator;

(Funktioniert)
?

camper schrieb:

@Sone: wieso mutable?

Mach mal ohne. Wenn das List-Objekt selbst const ist, dann wird bei einer Rückgabe in bspw. begin() &mStart ja zu einem const_iterator konvertiert. const_iterator akzeptiert aber im Konvertierungskonstruktor nur Zeiger auf non- const NodeBase s. Wenn ich aber den Pointee-Typ in iterator_base mit const qualifiziere, dann führt das dazu, dass in erase und anderen Funktionen, die einen const_iterator annehmen, ...

iterator erase( const_iterator it )
    {
        auto rval = it.p->next;

        it.p->prev->next = it.p->next;
        it.p->next->prev = it.p->prev;

        _alloc_destroy_node( static_cast<Node*>(it.p) ); // ... hier ein Fehler auftritt. Dann muss da ein const_cast rein, denn die _alloc-Funktionen nehmen ja keine solchen Zeiger. Und da ist mir persönlich mutable lieber.

        --mSize;

        return rval;
    }