Effizienz vector::erase

[__Stefan__]

Weiss ich jetzt nicht. Aber mit resize() sollte es wohl am schnellsten gehen, wenn's am Ende ist.

[Ad aCTa]

> Weiss ich jetzt nicht.

Dann antworte doch nicht. Die Komplexität von pop_back ist konstant, die von erase linear. Siehe:
http://www.cplusplus.com/reference/stl/vector/pop_back/
http://www.cplusplus.com/reference/stl/vector/erase/

[pumuckl]

Nimm das was den sprechendsten (= am leichtesten zu lesenden und zu verstehenden) Code ergibt. Wenns denn wirklich performancekritisch ist (oder werden sollte), dann hast du ja eh schon einen Profiler zur Hand und kannst eben durchtesten welche der drei Möglichkeiten die effektivste ist.

[Fellhuhn]

Äh, konstant * Anzahl Elemente ist auch linear.

[pumuckl]

Ad aCTa schrieb:

Dann antworte doch nicht. Die Komplexität von pop_back ist konstant, die von erase linear. Siehe:

Ja, weil pop_back genau ein Element entfernt, erase aber mehrere. Mehrmals pop_back ist aber auch linear, es geht hier nur um die unterschiedlichen Faktoren...

[l'abra d'or]

Stefan schrieb:

Weiss ich jetzt nicht. Aber mit resize() sollte es wohl am schnellsten gehen, wenn's am Ende ist.

Auch wenn es so wäre (bezweifle dass es schneller als pop_back ist, wohl implementierungsabhängig) Du versaust dir damit die ganze Optimierung! Denn std::vector denkt mit, wenn Elemente angehangen werden. Da das ein komplettes Umkopieren des internen Arrays verlangt (das ist RICHTIG teuer) reserviert std::vector mehr Elemente, als eigentlich notwendig sind. Im intern verwendeten Array sind also die letzten Elemente meist leer. Mit deinem resize() baust du indirekt ein ziemliches Perfomanceloch.

1. Die vorher getätigten überdimensionierten Reservierungen waren für die Katz
2. Ein künftiges push_back() darf gleich kräftig umkopieren.

Ich denke das sollte an Argumenten gegen ein resize() reichen, wenn es ein pop_back genauso gut tut.

[__Stefan__]

Es geht hier um das Entfernen von >1 objekten am Ende eines Vectors.
Vielleicht hätte ich nichts schreiben sollen, da ich den C++ Standard nicht auswendig kenne. Aber es ist doch eine bekannte Tatsache dass eine Vector beim Verkleinern keinen Speicherplatz freigibt. da würde ich annehmen dass das resize() nur die Änderung eines Integers, der Grösse, bedeutet. Effizienter geht das löschen mehrerer Elemente wohl kaum.

[pumuckl]

l'abra d'or schrieb:

[...]Mit deinem resize() baust du indirekt ein ziemliches Perfomanceloch.[...]

Falsch. Ein std::vector wird NIE den reservierten Speicherbereich verkleinern und unnötig umkopieren, außer man swapt ihn mit einem anderen std::vector der einen kleineren Bereich reserviert hat, wobei dann allerdings nur die internen Pointer umgehängt werden. Ohne Umkopieren und Neureservieren von kleineren Speicherblöcken.
Das ist deshalb auch die einzige Möglichkeit, überdimensionierte Reservierungen wieder loszuwerden: indem man den vector mit einer Kopie seiner selbst swapt:

std::vector<T> myVec;
myVec.reserve(LOTS_OF_T);
/* ... */

myVec.swap(std::vector<T>(myVec));

Der temporäre vector kopiert den Inhalt, ohne die riesen-reservierung mitzunehmen. Die beiden vectoren haben dann unterschiedlichen reservierten Bereich, gleichen Inhalt, werden geswapt, und der temporäre vector nimmt den größeren Block gleich mit ins Grab.

http://www.gotw.ca/gotw/054.htm

[l'abra d'or]

Stefan schrieb:

da würde ich annehmen dass das resize() nur die Änderung eines Integers, der Grösse, bedeutet.

Da nimmst du aber vollkommen falsch an! Wenn bei nem resize die neue Größe kleiner ist als die aktuelle (also die Anzahl der gespeicherten Objekte) dann müssen die Objekte zerstört werden. Nur einen integer neu setzen würde ein ziemliches Memoryleak bedeuten, ich hoffe das ist dir klar.
Ansonsten steht das auch hier:
http://www.cplusplus.com/reference/stl/vector/resize/

Notice that this function changes the actual content of the vector by inserting or erasing elements from the vector; It does not only change its storage capacity.

[l'abra d'or]

@pumuckl: Danke, das ist natürlich logisch, jetzt wo ich es lese. Schneller sein sollte es aber nicht.

[Shade Of Mine]

l'abra d'or schrieb:

@pumuckl: Danke, das ist natürlich logisch, jetzt wo ich es lese. Schneller sein sollte es aber nicht.

erase ist die effizienteste lösung.
n mal pop_back aufzurufen ist im besten fall gleich schnell wie ein erase, wahrscheinlich aber langsamer. (da du konstanten overhead hast, den du bei erase eben nur 1mal und nicht Nmal hast (und bei resize hast du den overhead auch nur 1mal, auch wenn es etwas mehr overhead ist))

mal abgesehen davon dass erase genau für solche situationen existiert.

[__Stefan__]

Erase existiert wohl eher dazu, Elemente mitten aus dem vector zu löschen. Jedenfalls muss dann immer noch überprüft werden, ob danach noch Elemente runtergeswapt werden müssen, um die eventuelle Lücke zu schliessen. Da ist der Overhead wohl doch grösser als bei resize().

[pumuckl]

Stefan schrieb:

da würde ich annehmen dass das resize() nur die Änderung eines Integers, der Grösse, bedeutet.

Nicht ganz. Die Destruktoren der gelöschten Elemente werden in jedem Fall aufgerufen. Was bei PODs natürlich keinen Unterschied macht. Das hat also in der Hinsicht keinen Vorteil gegenüber erase(). Dafür aber einen anderen, und damit sollte resize() besser sein als erase():

erase() nicht nur fürs Ende des vectors gemacht, daher muss zumindest noch ein Vergleich des end-iterators mit dem übergebenen (end-iterator) her, um festzustellen dass da genau 0 Elemente hinter sind, die noch nach vorn kopiert werden müssen. Im generellen Fall müssen nämlich alle Elemente hinter dem letzten zu löschenden erst nach vorn verschoben werden und danach erst werden die letzten N Elemente gelöscht. Dieser Vergleich entfällt beim resize;

Pseudocode:

erase(first, last)
{
  diff = last-first;  

  while (last != end())
    *first++ = *last++;

  while (first != end())
  {
    first-> ~T();
    ++first;
  }

  size -= diff;
}

resize(n)
{
  if (n > size)
  {
    /* egal fuer uns... */
  }
  else
  {
    for (it= begin()+n; it != end(); ++it)
    {
      it->~T();
    }
  }

  size = n;
}

[Shade Of Mine]

pumuckl schrieb:

erase() nicht nur fürs Ende des vectors gemacht,

guter punkt

PS:
Code der libstdc++

iterator erase(iterator __first, iterator __last)
  {
    if (__last != end())
      std::copy(__last, end(), __first);
    _M_erase_at_end(__first.base() + (end() - __last));
    return __first;
  }

finde ich schön gelöst

PPS: der vollständigkeit halber:

void resize(size_type __new_size, value_type __x = value_type())
  {
    if (__new_size < size())
      _M_erase_at_end(this->_M_impl._M_start + __new_size);
    else
      insert(end(), __new_size - size(), __x);
  }

PPPS:
was ich erschreckend aber auch wieder typisch finde: keine asserts. *brr*