Usuwanie z kontenerów STL

2009-05-15 14:30

Teoretycznie najlepszym sposobem na usuwanie elementów z pojemników STL jest posłużenie się idiomem eraseremove:

  1. v.erase (remove_if(v.begin(), v.end(), ToBeDeleted), v.end());

W praktyce bywa on dość kłopotliwy jeśli stosowany predykat (tutaj oznaczony jako funktor ToBeDeleted) musi być napisany specjalnie do tego celu. Zresztą gra często nie jest warta świeczki, bo implementacje algorytmów w rodzaju remove to w środku często nic innego, jak zwykłe pętle.

No a pętle możemy przecież napisać sobie sami, prawda?… Otóż nieprawda – zwłaszcza jeśli wcześniej nie pomyślimy przez chwilę. Łatwo bowiem wyprodukować coś takiego:

  1. // źle!
  2. for (vector<Object>::iterator it = v.begin(); it != v.end(); ++it)
  3.     if (ToBeDeleted(*it)) v.erase(it);

Z poprawnością ma to niewiele wspólnego. Jeśli bowiem natrafimy na element do usunięcia, to po dokonaniu tego (w nagłówku pętli) zinkrementujemy iterator, który na ów usunięty element wcześniej pokazywał. W ten sposób możemy pominąć element następny, bo go zwyczajnie “przeskoczymy”. Odpowiednik powyższej pętli używający zwykłego licznika i operatora [] jest zresztą obarczony identycznym problemem.
Jak więc usuwać? Umiejętnie, rzecz jasna :) Skoro po skasowaniu jednego elementu pozostałe przesuną się o jedno miejsce do tyłu, nie powinniśmy zawsze bezmyślnie przechodzić dalej. Trzeba to robić tylko wtedy, gdy dany element zostawiliśmy w spokoju:

  1. for (vector<Object>::iterator it = v.begin(); it != v.end(); /* bez ++it! */ )
  2.     if (ToBeDeleted(*it)) it = v.erase(it);    else ++it;

To w sumie całkiem oczywiste, jeśli chwilę się nad tym zastanowić. Bowiem – w przeciwieństwie do dodawania – usuwanie elementów z kontenerów wymaga właśnie chwili zastanowienia :]

Tags: ,
Author: Xion, posted under Programming »


11 comments for post “Usuwanie z kontenerów STL”.
  1. Liosan:
    May 15th, 2009 o 14:53

    Jeśli nie zależy nam na kolejności elementów w strukturze (a często tak jest), możemy to jeszcze usprawnić, zamieniając erase() na pop_back():

    for (unsigned int i = 0; i < v.size(); ){
    if (ToBeDeleted(v[i]))
    if (i == v.size()-1)
    v.pop_back();
    else
    v[i] = v.pop_back();
    else
    i++;
    }

    Trochę bardziej skomplikowane, ale chyba warto :) Zwłaszcza, jeśli obiekt pamięta swój indeks w tejże strukturze (a czasem jest to wygodne, by szybko usuwać jeden element).

  2. Malcom:
    May 16th, 2009 o 1:10

    boost::bind, std::tr1::bind i po klopocie z predykatem, jesli nie jest bardzo skomplikowany ;p

  3. SirMike:
    May 16th, 2009 o 12:49

    Było o tym erase w “perełkach” :) Od tamtego czasu nigdy nie zdarzyło mi się zapomnieć.

    Poza tym predykaty są świetne jesli w kodzie czesto korzystamy z podobnych pojemników i musimy zrobić coś na zasadzie “usuń z kontenera i zrób x->Release()”.

  4. zwierzak:
    May 16th, 2009 o 13:48

    A nie łatwiej tak:
    for (vector::iterator it = v.rbegin(); it != v.rend(); ++it)
    if (ToBeDeleted(*it)) v.erase(it);

    Przechodzenie tego wstecz rozwiązuje ten problem.

  5. Aithne:
    May 16th, 2009 o 15:10

    Predykat? Polski orzecznik nie istnieje?

  6. Xion:
    May 16th, 2009 o 22:43

    Za słownikiem języka polskiego PWN:

    predykat
    1. jęz. «w semantyce: wyrażenie opisujące cechę wyróżnionego przedmiotu albo relację między wyróżnionymi przedmiotami; też: treść tego wyrażenia»
    2. jęz. «w składni: orzeczenie»
    3. «w logice tradycyjnej: część zdania, w której się coś orzeka o podmiocie; w logice współczesnej: wyrażenie opisujące jakąś właściwość lub relację»

    orzecznik
    jęz. «nieczasownikowa część orzeczenia imiennego»

    Jak widać ‘predykat’ ma trzy znaczenia, z których to użyte w poście jest najbliższe pierwszemu. ‘Orzecznik’ co najwyżej jest związany z drugim znaczeniem, które tutaj kompletnie nas nie obchodzi.

    Troll is a troll, Q.E.D.

  7. Aithne:
    May 17th, 2009 o 13:22

    http://www.intercon.pl/~sektor/cbx/appendix/naming.html

  8. Xion:
    May 17th, 2009 o 17:22

    Jakoś autorzy słownika PWN są dla mnie “trochę” większym autorytetem niż autor jakiegoś kursu internetowego.

  9. Aithne:
    May 17th, 2009 o 23:14

    No dobra, mój słownik z kolei stwierdza, że ‘predykat’ nie istnieje…

  10. Aithne:
    May 17th, 2009 o 23:25

    A zresztą, co się tam będziemy kłócić – nazwijmy to po imieniu – predicate. Polski w programowaniu jest chyba dla pajacy.

  11. Reg:
    May 24th, 2009 o 15:16

    Usuwanie elementu z kolekcji STL za pomocą iteratora podczas przechodzenia elementów w pętli jest fajne, o ile metoda erase zwraca iterator do następnego elementu.

    Jest na przykład taki detal, że standard STL określa std::set::erase jako zwracający void, ale Microsoft w swojej implementacji zwraca iterator.

Comments are disabled.
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.