erase, insert- Methoden und die Iteratoren. Verständnissproblem!

unskilled

Poste doch einfach mal, was erase genau macht... wenn deine liste während des vorgangs rumkopieren darf, dann ist es z.bsp. klar, dass end dann nicht mehr mit end () übereinstimmt...

bb

smooth_op

@camper
Ja, dank unskilled ist mir klar, wieso ich mir die Position merken muss. Aber es leuchtet nicht ein, wieso die "verbesserten" Varianten noch nicht wollen.
Wg den if-Abfragen: Wenn es keinen head_ gibt, kann es auch nichts zu löschen geben. Wozu sollte man dann irgendwas auswerten, temp. Iteratoren anlegen etc., wenn man die Funktion doch sofort wieder verlassen kann? Whatever, das sind Feinheiten und die interessieren mich momentan eher wenig.

@unskilled
erase sollst du kriegen, mmn korrekt. Aber was weiss ich schon

template <typename T>
typename mylist<T>::iterator mylist<T>::erase(iterator pos)
{
	if(!pos.current_ || !head_) return iterator(); 

	mylistElem<T> *elem(pos.current_), *nextelem(pos.next_);

	if(elem == head_) head_ = head_->next_; if(!head_) tail_ = head_;
	if(elem == tail_) tail_ = tail_->prev_;	if(!tail_) head_ = tail_;

	elem->unlink_(); // hier wird ausgehängt (Verzeigerung aktualisieren)
	delete elem;
	elem = 0;

	--size_;

	if(!nextelem) 
		return end();
	else
	{
		iterator iter;
		iter.current_ = nextelem;
		iter.prev_ = nextelem->prev_;
		iter.next_ = nextelem->next_;
		return iter;
	}
}

camper

Wie sieht der Vergleichsoperator des Iterators aus und wie die end-Funktion der Liste?
Nachdem ich die erase-Funktion gesehen habe, kann ich bereits ahnen, was mit dem end()-iterator passiert, wenn das letzte Element einer Liste gelöschte wird.

smooth_op

template <typename T>
bool mylist<T>::iterator::operator==(iterator const &other) const throw()
{
	return (prev_ == other.prev_ && current_ == other.current_
	&& next_ == other.next_);
}

template <typename T>
typename mylist<T>::iterator mylist<T>::end() throw()
{
	iterator iter;
	iter.current_ = iter.next_ = 0;
	iter.prev_ = tail_;
	return iter;
}

So und nu lass mich an deinen Vermutungen teilhaben

camper

List-Iteratoren sind stabil bei allen List-Operationen, die die Elemente, auf die diese Iteratoren verweisen, nicht verändern. Insbesondere gilt für den End-Iterator, dass dieser sich während der gesamten Lebensdauer eines List-Objekts nicht verändert (außer evtl. bei swap). Diese Eigenschaft hat dein end-Iterator aber nicht. Betrachte

list.erase(list.begin(),list.end())

Der Iterator, der nach dem Löschen des letzten Elements zurückgegeben wird, ist nicht glich dem ursprünglichen Funktionsargument.

Schlimmer noch, offenbar duplizieren deine Iteratoren die Link-Information der Knoten, auf die sie zeigen. Das darf du nicht tun, da sich diese Informationen ändern können, ohne dass der Iterator das mitbekommt.

MyList<int> list;
MyList<int>::iterator end = list.end();
list.push_back(1);
--end; // sollte jetzt auf das eingefügte Element zeigen

Spätestens an dieser Stelle wird der Vorteil von Ringlisten mit dummy-Element deutlich, mit diesen erreicht man das Verhalten auf triviale Weise.

smooth_op

Danke für die Erläuterung.
Ich fürchte jedoch, ich kann dir nicht ganz folgen. Wenn das letzte Element der Liste gelöscht wird, gibts end() als Return. Da end() immer gleich aussieht, sollte das doch passen.
Die Sache ist, ich habe hier einen 2600-Zeilen langen Testtreiber, der größtenteils vom Prof stammt und wirklich jedes Detail der Liste checked.
So etwas markantes müsste also eigentlich auffallen.
An welcher Stelle würdest du anpacken?

smooth_op

Ich hab mittlerweile übringes meine splice gepimped.
So sollte es im Sinne der STL sein, oder?

template <typename T>
void mylist<T>::splice(iterator pos, mylist<T> &other)
{

	if(this == &other) return;

	mylistElem<T> *frst(other.head_), *lst(other.tail_);
	frst->unlink_(lst);    // hier wird frst bis einschliesslich lst ausgehaengt

	if(!head_) // Liste noch leer
	{
		head_ = frst; head_->prev_ = 0;
		tail_ = lst;	tail_->next_ = 0;	
	}
	else if(pos.current_) // Innerhalb der Liste
	{
		pos.current_->link_(frst, lst, false); // vor!! pos.current_ plazieren
	}
	else // am Ende anheangen
	{
		tail_->link_(frst, lst, true); // hinter!! aktuellem tail_ plazieren
	}

	if(!frst->prev_) head_ = frst; head_->prev_ = 0;
	if(!lst->next_) tail_ = lst; tail_->next_ = 0;

	size_ += other.size_;
	other.head_ = other.tail_ =  0;
	other.size_ = 0;

}

camper

smooth_op schrieb:

Danke für die Erläuterung.
Ich fürchte jedoch, ich kann dir nicht ganz folgen. Wenn das letzte Element der Liste gelöscht wird, gibts end() als Return. Da end() immer gleich aussieht, sollte das doch passen.

schau dir einfach einmal

MyList<int> list;
MyList<int>::iterator end1 = list.end();
list.push_back(1);
MyList<int>::iterator end2 = list.end();
assert(end1==end2);
--end1;
assert(list.erase(end1)==end2);

an.

Die Sache ist, ich habe hier einen 2600-Zeilen langen Testtreiber, der größtenteils vom Prof stammt und wirklich jedes Detail der Liste checked.
So etwas markantes müsste also eigentlich auffallen.
An welcher Stelle würdest du anpacken?

Der bloße Zeilenumfang sagt wenig aus, worauf es ankommt, ist doch, was getestet wird. Einige Dinge solltest du auch selbst testen - zum Beispiel die Gültigkeit von Argumenten zumindest beim Debuging. Den Anwender freut es, wenn er die fehlerhafte Anwendung deiner Liste mit einer entsprechenden Fehlermeldung quittiert bekommt an Stelle von merkwürdigem Verhalten.
Das würde auch in deinem Fall helfen. Ich bin einigermaßen sicher, dass das Inkrementieren eines end-Iterators einfach übergangen wird, anstatt mit Programmabbruch quittiert zu werden - obwohl das bei dieser Implementation trivial zu erkennen ist. Dann würde dein ursprünglicher Code keine Endlosschleife, sondern einen Programmabbruch produzieren. Weil dein end-Iterator nicht stabil ist, kann die Abbruch-Bedingung first==last in der erase-Funktion niemals erfüllt sein, wenn das Ende der zu löschenden Sequenz mit dem Ende des Containers übereinstimmt. Bei der Version, die eigentlich undefiniert ist, "funktioniert" es dagegen aus dem Grunde, dass das Inkrementieren auf noch unveränderten gelöschten Daten (also den alten Link-Informationen) beruht.

unskilled

warum hältst du so an deinem

if(this == &other) return;

fest und nimmst nicht die

assert (this != &other);

-Variante?

Ich seh da nur Vorteile drin - aber kA...

bb

smooth_op

Hallo die Herren,

@unskilled
weil ich momentan noch an ganz anderen Fronten kämpfe. Wenn alles so passt, wie es soll, kann ich mich um solche Feinheiten kümmern. Wurde aber zur Kenntniss genommen

@camper
Du hast das alles schon sehr richtig analysiert. In deinem Beispiel zeigt bei mir vom ersten end()-Iterator alles auf 0, weil es noch keine Elemente gibt. Der zweite end()-Iterator besitzt einen Vorgänger, nämlich das bei tail_ neu eingefügte-Element, daher sind sie ungleich.
Auch mit der Tatsache dass das letzte Element einer Sequenz Probleme bereitet, liegst du richtig. Habe folgendes bei meiner remove-Methode versucht:

remove...

template <typename T>
void mylist<T>::remove( T const &val)
{
	iterator beg(begin());
	while(beg != end())
	{
		if(*beg == val) beg = erase(beg);
		else
			++beg;
	}
}

Test läuft durch:

mylist<string> v;
v.push_back("Januar"); v.push_back("Februar"); v.push_back("Maerz");
//v.push_back("Januar");
v.remove("Januar");
mylist<string>::iterator iter(v.begin());
for( ; iter != v.end(); ++iter)
	{
          if(*iter == "Januar") break;
	}
assert(iter == v.end());
}

Wenn man das letzte Januar, welches dem Suchwort entspricht, wieder einkommentiert, kracht es.

Ich bin mir leider immer noch nicht sicher, an welcher Stelle ich anpacken soll?
Ist es das end(), welches erase im Falle des letzten Elements zurück gibt, oder das Inkrementieren der Iteratoren, oder doch was ganz anderes?!
Hab auch eine Debug-Session hinter mir, aber ich werd einfach nicht schlau daraus

camper

Ich stelle es einfach nochmal fest:
Link-Informationen (also die Frage, wer Vorgänger bzw. Nachfolger eines Knotens ist) haben im Iterator nichts verloren. Denn diese Information kann sich unabhängig vom Iterator ändern. Zudem sind zwei Iteratoren, die auf das gleiche Element verweisen, gleich; somit haben diese Informationen auch nichts im Vergleichsoperator zu suchen.
Alles worauf sich der Iterator verlassen kann und muss, ist, dass solange der Iterator gültig ist, Zeiger bzw. Referenzen auf den jeweiligen Knoten oder das List-Objekt selber gültig sind. Das sind folglich die einzigen Informationen, die du in deinem Iterator speichern darfst.
Daraus folgt aber auch zwingend, dass der Inhalt des end-Iterators kein einfacher Null-Zeiger sein kann, denn man kann end dekrementieren und das Ergebnis ist ja dann abhängig von der konkreten Liste, zu der der Iterator gehört.
Du hast also im Prinzip die Wahl zwischen einer Implementation, die zwei Zeiger speichert: einen auf den Knoten, den anderen auf das List-Objekt selber (diese Version erlaubt intensives Überprüfen und ist somit für checked Iteratoren geeignet); oder du benutzt eine Ringliste mit Dummyknoten - dann genügt ein einziger Zeiger und der End-Iterator zeigt dann auf diesen Dummy (diese Version ist offensichtlich erheblich effizienter, da Iteratorfunktionen trivial werden). Mit ein bisschen Geschick, kann man dieses Dummy-Objekt in die Liste einbetten (damit hat man dann automatisch wieder die nothrow-Garantie für die Defaultkonstruktion einer Liste)- das ist an sich das, was alle Implementationen der Standardbibliothek tun. Wir hatten vor kurzem bereits eine Diskussion, die dieses Thema berührt: Dummy Knoten.

Du wirst nicht darum herum kommen, deinen Iterator grundlegend zu überarbeiten.

smooth_op

Wenn der Iterator aber keine Kenntnisse vom Vorgänger und Nachfolger hat, wie kann er sich dann über die Liste bewegen?

Der Konstruktor sieht wie folgt aus:

template <typename T>
mylist<T>::iterator::iterator() throw() : prev_(0), current_(0), next_(0) {}

Mittels begin() und end() setze ich ihn dann entweder als Startpunkt oder als one-off-the-end-Punkt und er kann sich durch die Liste hangeln.
So wurde uns das gezeigt, deshalb wundert mich, dass das Prinzip falsch sein soll.

Ich werde deine Posts nochmal durchgehen und danach meine Liste im Detail und hoffe das Problem doch noch zu entdecken.

Danke bisher!

camper

smooth_op schrieb:

Wenn der Iterator aber keine Kenntnisse vom Vorgänger und Nachfolger hat, wie kann er sich dann über die Liste bewegen?

Indem er den Knoten befragt, auf den er zeigt (wenn er denn auf einen Knoten zeigt, den end-Iterator musst du ggf. anders behandeln, indem das Listenobjekt selbst befragt wird).