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

[smooth_op]

Also die Beschreibungen zu den Methoden hab ich von sgi.com.
Dort heisst es zu dieser splice Methode:

position must be a valid iterator in *this, and x must be a list that is distinct from *this. (That is, it is required that &x != this.) All of the elements of x are inserted before position and removed from x. All iterators remain valid, including iterators that point to elements of x. [3] This function is constant time.

Hatte das so verstanden, dass man mit insert/erase arbeiten kann.
Was wäre eine geschicktere Alternative?
Hauptsächlich interessieren mich jedoch die Fragen, die ich oben gestellt habe, weil meine Methoden selbst ja funktionieren. Jedenfalls wenn ich Version 1 benutze und mir die Iteratoren mit begin()/end() vor der for-Schleife anlege.

[unskilled]

Also ich würde es IMMER so machen, dass man erst überträgt und dann löscht... Sollte so gar schneller sein...

Ich hab aber kein Plan von der Definition/Anwendung einer splice-Funktion - hab auch noch nie davon gehört ^^ Also halte dich da mal besser an camper ^^
Aber falls ich das nicht falsch verstehe, sollst du nicht die Objekte an sich kopieren sondern einfach nur den letzten Eintrag umbiegen... Das würde auch Sinn machen - von wegen

This function is constant time.

That is, it is required that &x != this.

also doch nen assert ()...

Also quasi so (ungetestet, soll dir nur verdeutlichen, wie das gemeint ist):

template <class T>
  bool /*ok*/ mylist <T>::splice (const iterator pos, mylist <T> &other) //nothrow
    {
      assert (*this != other); //hat den vorteil, dass es beim release nicht mehr überprüft wird - aber der algorithmus an sich sollte sich ja zwischen debug und release nicht ändern ^^

      Tentry <T> *temp; // vll mit 0 / NULL / nullptr initialisieren, aber wird hier echt nicht gebraucht...
      try
        {
          temp = new Tentry <T>;
        }
        catch (std::bad_alloc) //die exception an sich brauchen wir nicht - ist ja klar, was sie uns sagen will ^^
          {
            return false;
          }

      this->last.next = other.first;
      other.first.prev = this->last.next;
      this->size += ohter.size;

      other.first = temp;
      return true;
    }

bb

[smooth_op]

Hi (un)skilled,

danke, jetzt hab ich verstanden was camper meinte. Dann löse ich es am Besten über eine eigene link(mylistelem<T>*beg, mylistelem<T>*end)-Methode, welche sich um die Verzeigerung kümmert und ich in den splice-Methoden benutze.

Wenn nun noch jemand zu den übrigen Fragen Stellung beziehen könnte, wäre ich wunschlos glücklich

[unskilled]

Hmm... Stell die doch noch mal ^^

[smooth_op]

Hehe okay.

Wieso iteriert folgendes korrekt:

iterator beg(other.begin()), end(other.end());
    for( ; beg != end; ++beg) {...}

und dies hier nicht:

for(iterator iter(other.begin()); iter != other.end(); ++ iter) {...}

Und wenn es mit den ausgeführten insert/erase Operationen zusammen hängt, wieso mache ich mir die Iteratoren dann mit der ersten Version nicht kaputt??

Dann interessiert mich noch, wann man bei einem erase-Aufruf den Return-Wert benutzt und wann nicht. Du hast das in deinem ersten Bsp. auch verwendet.
Macht man das vlt, wenn nicht sowieso mit ++iter in der Schleife weitergeschaltet wird?!

Um mal von dem splice wegzukommen, das Problem taucht auch bei vielen anderen Operationen auf.
Beispielsweise remove:

template <typename T>
void mylist<T>::remove( T const &val)
{
	//for(iterator iter(this->begin()); iter != this->end(); ++iter)
	//	if(*iter == val) this->erase(iter);

	iterator beg(this->begin()), end(this->end()); 
	for( ; beg != end; ++beg)
	{
		if(*beg == val) this->erase(beg);
	}
}

Hier ist die alte, fehlerhafte Lösung auskommentiert.

Wenn was nicht verständlich ist, einfach fragen.

[unskilled]

smooth_op schrieb:

Dann interessiert mich noch, wann man bei einem erase-Aufruf den Return-Wert benutzt und wann nicht. Du hast das in deinem ersten Bsp. auch verwendet.
Macht man das vlt, wenn nicht sowieso mit ++iter in der Schleife weitergeschaltet wird?!

naja... Es sieht ja so aus:

iter
    |
    v
.---------.
| element |
| next ------>  <element, next, ...>
| ...     |
'---------'

du löschst das element (mit erase) und willst DANACH noch den zeiger next haben...

iter
    |
    v
???????????
???????????
???????????  [kein zeiger mehr da] <element, next, ...>
???????????
???????????

Das kann niemals gut gehen...

Wenn du erase nutzt, dann darfst du ++ nicht verwenden und MUSST den rückgabewert nutzen... Wenn du beides nimmst, hast du logischerweise nur jedes zweite element gelöscht (#1 gelöscht, iter wird auf neues #1 gesetzt (das alte #2) und dann um eins erhöht -> (altes) #3)

und ++ macht ja nichts anderes, als next aufzurufen... und anscheind optimiert der compiler bei deiner einen variante anders als bei der anderen... außerdem bleibt noch immer die ausrede, dass es undefiniertes verhalten hervorruft, ungültige zeiger (und damit auch iteratoren) zu nutzen...

Um noch mal zu dem zweiten bildchen zu kommen:
du hast also keine chance mehr, nach dem erase an das nächste element zu kommen (ok, das ist falsch, das geht noch über das vorige (vom gelöschten aus gesehen)prev->next - aber nicht all zu bequem und performant ^^)... deshalb gibt dir erase das nächste element wieder aus bzw einen iterator auf das nächste element...

ok?

bb

edit:
zu der fkt an sich noch mal:

template <typename T>
  bool /*ok*/ mylist<T>::remove (T const &val) //nothrow - kommt aber nat darauf an, ob erase ne exception werfen darf bzw könnte
    {
      for(iterator iter (this->begin()), end (this->end()); iter != end; ++iter)
        {
          if (*iter == val)
            {
              erase (iter); //hier brauchen wir den returnwert mal nicht
              return true;
            }
        }
      return false;
    }

je nach geschmack kann man das auch mit if (*iter != val) continue; lösen... und darunter dann das erase aufrufen...

btw fällt mir da gerade ma wieder ne frage ein:

erase (iter); //hier brauchen wir den returnwert mal nicht
//castet man bei so was eigtl noch auf void? also so was:
(void)erase (iter);

[smooth_op]

Nice Pics

Also ist es deiner Meinung nach nur Zufall, das meine erase Varianten korrekt funktionieren, weil undefiniert? Das macht mich jetzt fertig.
Deine remove-Methode kommt meiner nicht ganz gleich, weil ich alle Vorkommen "value" löschen möchte.
Ich habs mal versucht zu übertragen, aber damit läuft er nicht mehr durch meine Tests.

iterator beg(this->begin()), end(this->end()); 
	while(beg != end)
	{
		if(*beg == val) beg = this->erase(beg);
		else
			++beg;
	}

Zu deiner Frage. Glaube nicht das ein cast notwendig ist, habs in so einem Fall noch nie gesehen.

[unskilled]

Zu deiner Frage. Glaube nicht das ein cast notwendig ist, habs in so einem Fall noch nie gesehen

Nötig ist er auch nicht... Aber "damals" war das mal in ^^

iterator iter (begin ());
while (iter != end ()) //die funktion aufrufen
  {
    if (*iter == val) //ich würd das umdrehen - fände das logischer ^^ also if (a != b) ++a else erase ()
      iter = erase (iter);
    else
      ++iter;
  }

warum schreibst du statt iter (für iterator) immer beg? beg stimmt genau einmal - ganz am anfang...
Auch das this-> jedes mal nervt eher als alles andere ^^

bb

[smooth_op]

Ich benutze beg, genauso wie first, weil ich verdeutlichen möchte, dass es sich um den Anfang eines definierten Range handelt. Dass er das nach einmaligem inkrementieren nicht mehr ist, stört mich jetzt nicht wirklich. Btw. arbeitet die cplusplus-Reference auch mit diesen Begriffen.
Wegen dem this werde ich aber in Zukunft Rücksicht auf dich nehmen

Zu meiner Remove. Ob jetzt so herum logischer oder nicht, er läuft nicht mehr durch und wirft eine out_of_range exceptions (* on bad iterator). Wieso?

Hier noch ein Bsp, was eigentlich nicht klappen dürfte, es aber dennoch tut, obwohl ich den iterator first mit der erase-Methode lösche und first nicht aktualisiere?!

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

	iterator iter; // Tmp-Iter fuer Return
	for( ; first != last; ++first) iter = erase(first);		

	return iter; 
}

Wenn ich sie nun umschreibe, gibts eine endlos-Schleife!

typename mylist<T>::iterator mylist<T>::erase(iterator first, iterator last)
{
	if(!head_ || !first.current_) return iterator();

	while(first != last) first = erase(first);

	return first; 
}

Ich weiss nicht, was ich falsch mache. Da es hier sicher ein paar STL-Fans gibt, würd ich mich über einer Erklärung freuen.

Viele Grüsse,
smooth

[camper]

smooth_op schrieb:

Ich weiss nicht, was ich falsch mache. Da es hier sicher ein paar STL-Fans gibt, würd ich mich über einer Erklärung freuen.

Ich nehme an, dass du durchaus weißt, was falsch ist. Dass das erste Beispiel bei dir möglicherweise "funktioniert", ist letztlich unerheblich. Die erste Varianten resultiert in undefiniertem Verhalten - und undefiniert heißt eben nicht "funktioniert nicht", sondern dass keine bestimmte Aussage in irgendeiner Hinsicht möglich ist.

Das Problem mit dem zweiten Beispiel liegt woanders - ich würde vermuten, dass irgendeine elementare Funktion bei dir fehlerhaft implementiert ist. Der if-Teil darin ergibt übrigens nicht viel Sinn.
Grundsätzlich kann man bzgl. der Parameter voraussetzen, dass
[first,last) eine Sequenz ist, und sowohl first als auch last in [begin(),this->end()] liegen.

[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