...

[Swordfish]

...

[Kellerautomat]

Du kannst dir deine Implementierung erheblich erleichtern, indem du die Liste als Ring implementierst und immer 1 Knoten hast. Damit fallen alle Sonderfaelle weg.
Ausserdem koenntest du alle Einfuegeoperationen bzw. Loeschoperationen ueber insert/erase implementieren.

[Sone]

Alle deine Konstruktoren sind nicht exception-safe.

[Swordfish]

...

[camper]

Der -- Operator deiner Iteratoen ist ein bisschen seltsam. Vor den Anfang zu iterieren ist normalerweise sowieso UB.
Hier ist eine Menge doppelter Code enthalten. Ich würde mir auch noch splice-Funktionen wünschen. Die problematischen Konstruktoren wurden schon angesprochen.

[Swordfish]

...

[Nathan]

Swordfish schrieb:

camper schrieb:

Vor den Anfang zu iterieren ist normalerweise sowieso UB.

UB heißt, der Iterator darf dann sonstwohin zeigen? Bei mir zeigt --list.begin() auf list.end() . Ist das ein Problem?

Wenn man sich drauf verlässt, dass das nicht definiert ist schon.

[nwp3]

Nathan schrieb:

Swordfish schrieb:

camper schrieb:

Vor den Anfang zu iterieren ist normalerweise sowieso UB.

UB heißt, der Iterator darf dann sonstwohin zeigen? Bei mir zeigt --list.begin() auf list.end() . Ist das ein Problem?

Wenn man sich drauf verlässt, dass das nicht definiert ist schon.

Das ist doch völlig in Ordnung. Nicht definiert heißt nicht, dass ein zufälliger Wert da stehen muss.
Als netter Mensch könntest du aber ein assert benutzen, dass das abfängt.

[Swordfish]

...

[Sone]

Swordfish schrieb:

UB heißt doch, die Implementierung darf machen was sie will?

So ist es. Der Standard legt in keinster Weise fest, was passiert, das heißt das.

Oder meinst du, der Iterator sollte in diesem Falle von -- einfach nicht bewegt werden? Oder std::out_of_range werfen?

Nein, man sollte diese Semantik am Besten gar nicht berücksichtigen. Tu' einfach so, als ob das nie passiert. Das ist auch am effizientesten.

P.S.: Wieso new/delete und kein Allokator?

[Swordfish]

...

[Kellerautomat]

Swordfish schrieb:

Kellerautomat schrieb:

Ausserdem koenntest du alle Einfuegeoperationen bzw. Loeschoperationen ueber insert/erase implementieren.

Du sagst "außerdem", d.h. jetzt, mit einer linearen Liste auch schon?

Ja. Implementiere alle Einfuege/Loeschfunktionen ueber die beiden hier:

iterator insert(const_iterator pos, const_reference value);
iterator erase(const_iterator pos);

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