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 erase-remove:

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:

// źle!
for (vector<Object>::iterator it = v.begin(); it != v.end(); ++it)
    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:

for (vector<Object>::iterator it = v.begin(); it != v.end(); /* bez ++it! */ )
    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 :]

  • RSS
  • Facebook
  • Twitter
  • Wykop
  • Reddit
  • del.icio.us
  • Google Bookmarks
Tagi: ,
Autor: Xion w Programowanie »


Możesz śledzić komentarze do tej notki poprzez kanał RSS 2.0.
Możesz przejść do końca i zostawić komentarz. Śledzenie notek (trackback) jest aktualnie wyłączone.


11 komentarze/y do notki “Usuwanie z kontenerów STL”.
  1. Liosan:
    Maj 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:
    Maj 16th, 2009 o 1:10

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

  3. SirMike:
    Maj 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:
    Maj 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:
    Maj 16th, 2009 o 15:10

    Predykat? Polski orzecznik nie istnieje?

  6. Xion:
    Maj 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:
    Maj 17th, 2009 o 13:22

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

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

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

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

    No dobra, mój słownik z kolei stwierdza, że 'predykat' nie istnieje...

  10. Aithne:
    Maj 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:
    Maj 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.

Dodaj komentarz

Znaki nowej linii dodawane są automatycznie.
Do wstawiania kodu użyj [code][/code], a do wzorów (w LaTeX-u) [tex][/tex].
Dozwolne tagi HTML:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 



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