...

[Swordfish]

...

[Nathan]

Wozu braucht man die überhaupt?
Wenn man festlegen will, wie der Speicher angefordert wird, kann man doch für eigene Typen operator new überladen...?

[Kellerautomat]

Swordfish schrieb:

Sone schrieb:

Wieso new/delete und kein Allokator?

Apropos Allocator: der Standardtyp dafür ist ja std::allocator< T > ... Somit kann/soll(?) ich ihn nicht benutzen, um die Nodes anzulegen, sondern nur für die T s?

Du musst den Allocator rebinden:

template <typename T, typename Allocator = std::allocator<T>>
struct list
{
    typedef typename Allocator::template rebind<node>::other node_allocator_type;

    ...
};

[Ethon]

Nathan schrieb:

Wozu braucht man die überhaupt?
Wenn man festlegen will, wie der Speicher angefordert wird, kann man doch für eigene Typen operator new überladen...?

Verschiedene Container haben unterschiedliche optimale Allokationsstrategien.
Manchmal will man Speicher vom Heap, manchmal aus einer Arena, dann aus einem dynamischen Pool ...

[Nathan]

Ethon schrieb:

Nathan schrieb:

Wozu braucht man die überhaupt?
Wenn man festlegen will, wie der Speicher angefordert wird, kann man doch für eigene Typen operator new überladen...?

Verschiedene Container haben unterschiedliche optimale Allokationsstrategien.
Manchmal will man Speicher vom Heap, manchmal aus einer Arena, dann aus einem dynamischen Pool ...

OK, das klingt logisch.

[camper]

Swordfish schrieb:

Habe eben begonnen alle ctors á la

explicit list_t( size_type n )
:	head(),
	tail(),
	length()
{
	if( !n )
		return;

	node_t * first_new_node;
	
	try {
		first_new_node = new node_t();
	
	} catch( std::bad_alloc ) {
	
		throw;
	
	} catch( ... ) {
	
		delete first_new_node;
		throw;
	}
	
	node_t * current_new_node = first_new_node;
	node_t * last_new_node = first_new_node;
	
	for( size_type i = n; --i; ) {
	
		try {
			current_new_node->next = new node_t();
		
		} catch( ... ) {
		
			if( !current_new_node->next ) {
			
				current_new_node = first_new_node->next;
			
				while( current_new_node ) {
			
					node_t *next_new_node = current_new_node->next;
					delete current_new_node;
					current_new_node = next_new_node;
				}
			
				delete first_new_node;

				throw;
			}
		}
		
		current_new_node->next->prev = current_node;
		last_new_node = current_new_node = current_new_node->next;
	}

	head = first_new_node;
	tail = last_new_node;
	length = n;
}

umzuschreiben, damit nichts mehr leckt. . o O ( Vielleicht sollt ich mir doch mal Smartpointer anseh'n )

Keine gute Idee. catch(...) throw;-Orgien sind fehleranfällig, und schwer zu lesen. Warum nicht einfach eine Basisklasse/Member verwenden, die fürs Aufräumen zuständig ist?

Swordfish schrieb:

camper schrieb:

Der -- Operator deiner Iteratoen ist ein bisschen seltsam.

Hm. Warum seltsam?

Hatte falsch gelesen. Wenn ein Iteratoreninterface benötigt wird, ist ein Dummyknoten empfehlenswert. Das geht auch noch völlig ohne Overhead, schließlich enthält das Listobjkekt ja bereits eine halben Knoten.

[lool]

Seit 8 Jahren im Forum und beschäftigt sich noch mit solch einfachen Sachen

[Sone]

lool schrieb:

Seit 8 Jahren im Forum und beschäftigt sich noch mit solch einfachen Sachen

Dann schreib' du mal eine std::list -Implementation. Ich habe mich heute auch dran gesetzt, das macht viel Spaß. Und es ist nicht einfach, es elegant, effizient und ordentlich zu machen.
P.S.: AFAIK hatte Swordfish doch eine längere Pause?

[haifaik]

Sone schrieb:

lool schrieb:

Seit 8 Jahren im Forum und beschäftigt sich noch mit solch einfachen Sachen

Dann schreib' du mal eine std::list -Implementation. Ich habe mich heute auch dran gesetzt, das macht viel Spaß. Und es ist nicht einfach, es elegant, effizient und ordentlich zu machen.

Jeder sollte das schon einmal gemacht haben. Mit dem Zirkel-Trick und mit Exception-Safety. Unterstützung für std::allocator muss nicht sein ("std STL allocators are painful to work with and lead to code bloat and sub-optimal performance"), entweder nimmt man sein eigenes Allocator-Design oder gar nichts.

Es spricht nichts dagegen, wenn Anfänger wie Sone eine std::list implementieren. Aber nach acht Jahren ist das eigentlich überfällig, das sehe ich genauso wie lool. Ich finde die Reaktion witzig, wie der Hinweis auf Exception-Safety sofort zu try/catch geführt hat. try/catch(...)+rethrow lässt sich immer zu RAII umformen. Sollte auch fast immer gemacht werden.

[Sone]

haifaik schrieb:

Sone schrieb:

lool schrieb:

Seit 8 Jahren im Forum und beschäftigt sich noch mit solch einfachen Sachen

Dann schreib' du mal eine std::list -Implementation. Ich habe mich heute auch dran gesetzt, das macht viel Spaß. Und es ist nicht einfach, es elegant, effizient und ordentlich zu machen.

Jeder sollte das schon einmal gemacht haben.

klar. Meine letzte war vor etwa einem Jahr.

Unterstützung für std::allocator muss nicht sein ("std STL allocators are painful to work with and lead to code bloat and sub-optimal performance"), entweder nimmt man sein eigenes Allocator-Design oder gar nichts.

EASTL-Fan?
Es geht mir nicht darum, eine schöne Implementierung zu schreiben, sondern eine möglichst zu std::list äquivalente. Ich habe (AFAIK) nur wenige, kleine Änderungen zu std::list in meinem vorläufigen Extrakt.
(Nehme ich ein eigenes Design werde ich früher oder später auf allocator_traits zurückgreifen, weil auch std::allocator verfügbar sein soll. Und dann ist ein eigenes Design auch bescheuert. Darüber hinaus habe ich mich mit Allokatoren noch nicht viel beschäftigt und sehe deswegen - als Sturkopf - nicht ein, wieso den das STL-Allokator-Design so hässlich und schmerzbringend sein soll)

try/catch(...)+rethrow lässt sich immer zu RAII umformen.

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

Hier wäre dann eine (unvollständige) Version meiner Implementierung: http://ideone.com/rJ4sOr
(Schade, die Formatierung ist wieder hinüber.)

[camper]

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

?

typedef iterator const const_iterator;

wirklich?

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