Usuwanie z kontenerów STL
2009-05-15 14:30Teoretycznie 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 :]
-
Liosan:
May 15th, 2009 o 14:53Jeś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).
-
Malcom:
May 16th, 2009 o 1:10boost::bind, std::tr1::bind i po klopocie z predykatem, jesli nie jest bardzo skomplikowany ;p
-
SirMike:
May 16th, 2009 o 12:49Był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()”.
-
zwierzak:
May 16th, 2009 o 13:48A 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.
-
Aithne:
May 16th, 2009 o 15:10Predykat? Polski orzecznik nie istnieje?
-
Xion:
May 16th, 2009 o 22:43Za 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.
-
Aithne:
May 17th, 2009 o 13:22http://www.intercon.pl/~sektor/cbx/appendix/naming.html
-
Xion:
May 17th, 2009 o 17:22Jakoś autorzy słownika PWN są dla mnie “trochę” większym autorytetem niż autor jakiegoś kursu internetowego.
-
Aithne:
May 17th, 2009 o 23:14No dobra, mój słownik z kolei stwierdza, że ‘predykat’ nie istnieje…
-
Aithne:
May 17th, 2009 o 23:25A zresztą, co się tam będziemy kłócić – nazwijmy to po imieniu – predicate. Polski w programowaniu jest chyba dla pajacy.
-
Reg:
May 24th, 2009 o 15:16Usuwanie 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.
Recent posts
