Probleme mit löschen bestimmter std::list Elemente

Nexus

std::advance() benutzt intern auch eine Schleife. Du solltest dir vor Augen halten, dass sich der Rechenaufwand proportional zum Offset verhält (O(n)). Wenn du also 243055 als Argument übergibst, muss der Iterator 243055 Mal inkrementiert werden. Im Gegensatz zu operator+= bei Random-Access-Iteratoren, wo das in konstanter Zeit läuft.

Von daher solltest du dir auch überlegen, wenn du oft mittels Index auf eine Liste zugreifen willst, eher einen anderen Containertypen, zum Beispiel Vector oder Deque zu nehmen.

varginator

Danke für die Antworten,

der Grund warum ich std::list verwende ist, weil ich eine Liste brauche, in der ich auch Elemente aus der Mitte löschen kann und dass dann die Liste verkleinert wird.

Eigentlich könnte ich es auch mit std::vector machen und dann die Elemente verschieben, weil es ist mir egal, in welcher Reihenfolge die Elemente vorkommen.

Oder habt ihr einen anderen Lösungsvorschlag?

Gruß Simon

Firefighter

http://www.cplusplus.com/reference/stl/vector/erase/

std::vector verschiebt seine elemente automatisch sobald du in der Mitte rauslöschst.

C++ Referenz schrieb:

Because vectors keep an array format, erasing on positions other than the vector end also moves all the elements after the segment erased to their new positions, which may not be a method as efficient as erasing in other kinds of sequence containers (deque, list).

This invalidates all iterator and references to elements after position or first.

pumuckl

varginator schrieb:

Eigentlich könnte ich es auch mit std::vector machen und dann die Elemente verschieben, weil es ist mir egal, in welcher Reihenfolge die Elemente vorkommen.

Wenn das wirklich egal ist es nicht weiter schwer, Elemente aus einem vector in konstanter Zeit zu löschen:

#include <algorithm>
#include <vector>

template <class T>
typename std::vector<T>::iterator unrodered_erase(std::vector<T>& vec, typename std::vector<T>::iterator pos)
{
  std::vector<T>::iterator back = end()-1;
  if(pos == back)
  {
    vec.pop_back();
    return vec.end();
  }
  std::iter_swap(pos, back);
  vec.pop_back();
  return ++pos;
}

template <class T>
typename std::vector<T>::iterator unrodered_erase(std::vector<T>& vec, 
    typename std::vector<T>::iterator first, typename std::vector<T>::iterator last)
{
  while (first != last && last != vec.end())
    first = unordered_erase(vec, first);
  if (first != last)
  {
    vec.erase(first, last);
    return vec.end();
  }
  return last;
}

(ungetestet)

varginator

Danke für die weiteren Antworten,

ich habe nicht gewusst (und auch garnicht darüber nachgedacht), dass die Elemente bei std::vector dann einfach verschoben werden.

Was währe eigentlich schneller, den Iterator hochzählen, oder die Vektor-Elemente verschieben?

Gruß Simon

pumuckl

varginator schrieb:

Was währe eigentlich schneller, den Iterator hochzählen, oder die Vektor-Elemente verschieben?

Ich weiß nicht, ob ich die Frage richtig verstehe, aber einen Iterator hochzuzählen ist selbstverständlich schneller als N Elemente um eine Position nach vorne zu verschieben. Mit Iteratorhochzählen ists aber nicht getan, da dann ein Loch im vector entstehen würde. Bei der von mir geposteten Lösung wird das zu löschende Element mit dem letzten vertauscht, das geht in konstanter Zeit, danach wird das dann letzte Element gelöscht - auch konstante Zeit. Allerdings weiß ich nicht ob das so sinnvoll für deine Anwendung ist. Du hast zwar gesagt dass die Ordnung deiner Elemente egal ist, andererseits willst du indizierten Zugriff. Das beißt sich, denn du weißt ja dann nicht unbedingt was sich am gegebenen Index befindet. Wenn du vorher immer suchen musst, um den Index herauszufinden ist vector wiederum auch nicht gut geeignet, da die Suche dort O(n) dauert. Wenn dein Suchkritetrium immer nach den selben Attributen geht wäre evtl. set noch eine Möglichkeit.

varginator

Hallo pumuckl,

danke für die erneute Antwort,
in meinem Programm wird folgendes gemacht:

Schleife, die alle Elemente einer Liste (std::vector oder halt std::list) durchgeht und Funktionen mit ihnen aufruft ...
Wenn die Funktion dann halt einen bestimmten Wert zurückgibt, dann soll dieses Element aus der Liste entfernt werden (was mir grad auffält: evtl. gibts dann Probleme beim zählen, aber darum kümmere ich mich später)

Also ist es eigentlich egal, in welcher Reihenfolge die Elemente stehen.

Gruß Simon

jencas

Sowas macht man eigentlich mit erase() und remove_if():

Instruktives Beispiel (ungetestet):

struct odd : public std::unary_function<int, bool> // für not1(),...
{
    bool operator() (int i) {return i % 2 != 0;}
}

int main()
{
  ...
  vector<int> vi;
  ...
  // alle ungeraden entfernen
  vi.erase(remove_if(vi.begin(), vi.end(), odd()), vi.end()); 
  ...
}

pumuckl

varginator schrieb:

Schleife, die alle Elemente einer Liste (std::vector oder halt std::list) durchgeht und Funktionen mit ihnen aufruft ...
Wenn die Funktion dann halt einen bestimmten Wert zurückgibt, dann soll dieses Element aus der Liste entfernt werden (was mir grad auffält: evtl. gibts dann Probleme beim zählen, aber darum kümmere ich mich später)

Dafür brauchst du aber dein += das du am Anfng erwähnt hast überhaupt nicht. Du kannst mit einem Iterator durchgehen und die Elemente bei Bedarf löschen. Die erase()-Methoden der list<>-Container liefern einen iterator der auf das jeweils nächste Element zeigt. Also sinngemäß:

std::list<AskMe>::iterator iter = askMeList.begin();
std::list<AskMe>::iterator enditer = askMeList.end();
while (iter != enditer)
{
  if (iter->mustBeDeleted())
    iter = askMeList.erase(iter);
  else
    ++iter;
}

Du solltest dir allerdings auch mal std::erase_if anschauen.

void removeAllThatMustBeDeleted()
{
  struct MustBeDeleted 
  { 
    bool operator() (AskMe& askme) {return askme.mustBeDeleted();} 
  };

  askMeList.erase(
    std::remove_if(askMeList.begin(), askMeList.end()), 
    askMeList.end()
  );
}

Nexus

pumuckl schrieb:

Du solltest dir allerdings auch mal std::erase_if anschauen.

Jetzt hatte ich schon Angst, ich hätte eine wichtige Funktion der Standardbibliothek nicht gekannt.
Aber anfangs war ich auch ein wenig verwirrt. Remove, Erase, Delete... Man gewöhnt sich dran. Schlimmer finde ich die Inkonsistenzen bei Find, Search und deren STL-Algorithmen-Derivaten (sorry für OffTopic).

std::remove_if() würde ich aber bei Listen nicht unbedingt verwenden. Mit Listen will man teilweise Kopien vermeiden, die aber durch Iterator-Algorithmen wie remove_if() wieder nötig werden. Natürlich ist das eher allgemein gesehen, aber oft sprechen die Gründe für eine Liste dagegen. Ich habe mir vor Kurzem zwei Templates geschrieben, da bei mir oft die Situation vorlag, dass Objekte in Listen aufgrund von gewissen Memberfunktionen entfernt werden sollten. Natürlich könnte man das ein wenig einengen, zum Beispiel auf const -Memberfunktionen mit Rückgabetyp bool und keinen Parametern. Oder ausweiten auf freie Funktionen und Funktionsobjekte. boost::bind hilft einem da sicher.

// vor allem std::deque und std::vector
template <typename Container, typename MemberFn>
void RemoveIf(Container& Ctr, MemberFn Condition)
{
	Ctr.erase(std::remove_if(Ctr.begin(), Ctr.end(), boost::mem_fn(Condition)), Ctr.end());
}

// Überladung für std::list
template <typename ElementType, typename MemberFn>
void RemoveIf(std::list<ElementType>& Ctr, MemberFn Condition)
{
	for (std::list<ElementType>::iterator i = Ctr.begin(); i != Ctr.end(); )
	{
		if ( ((*i).*Condition)() )	// Memberfunktionsaufruf für vom Iterator referenziertes Element
			i = Ctr.erase(i);
		else
			++i;
	}
}

Und diese funktionale Programmierung erlaubt eine sehr elegante Anwendung. Keine Iterationen mehr im Code, keine mühsamen Schleifen.

RemoveIf(Cars, &Car::IsDemolished);

Ich hatte letztens auch einen Fall, an dem ich relativ lange debuggen musste. Es kam in meinem Projekt eine std::list vor. Ich hatte nicht eine Liste gewählt, weil ich die typische Eigenschaft des konstanten Einfügens/Löschens in der Mitte benötigte, sondern weil Zeiger auf die Listen gültig bleiben mussten. Es dauerte eine entsprechende Zeit, bis ich gemerkt hatte, dass remove_if() das Konzept über den Haufen warf. Seit da habe ich die Überladung.