Autor Wątek: STL, usuwanie bieżącego elementu w pętli  (Przeczytany 5268 razy)

.Xentix

  • Gość
# Październik 21, 2009, 13:05:53
Cześć, mam pytanie dotyczące usuwania elementu z vectora w STL. Mianowicie w jaki sposób usunąć bieżący element w pętli, tak żeby wszystko działało poprawnie. Próbowałem kilku różnych sposobów i za każdym razem po usunięciu iterator zaczynał wskazywać na jakieś przypadkowe miejsce w pamięci. Myśle, że kawałek kodu poniżej dobrze zobrazuje i co mi konkretnie chodzi.

vector<T> xxx;

vector<T>::iterator it;
for(it=xxx.begin();it!=xxx.end();it++)
   {
   xxx.erase(it);
   }

Proszę o pomoc, z góry dzięki.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline bies

  • Użytkownik

# Październik 21, 2009, 13:15:46
Prosta odpowiedź: vector::erase() zwraca iterator elementu za usuwanym.
Poprawna odpowiedź: poszukaj informacji nt. idiomu erase-remove.

.Xentix

  • Gość
# Październik 21, 2009, 13:35:51
Dzięki, już działa poprawnie, niedoczytałem o wartości zwracanej przez funkcje erase, jeszcze raz dzięki.

Offline bies

  • Użytkownik

# Październik 21, 2009, 14:07:15
Dzięki, już działa poprawnie, niedoczytałem o wartości zwracanej przez funkcje erase, jeszcze raz dzięki.
Czyli zignorowałeś poprawną odpowiedź. Wrócisz do niej jak się okaże, że swobodne używanie vector::erase() działa za wolno. ;D

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Październik 21, 2009, 17:02:18
Cytuj
vector<T> xxx;

vector<T>::iterator it;
for(it=xxx.begin();it!=xxx.end();it++)
   {
   xxx.erase(it);
   }
Najpoprawniejsza odpowiedź: ;)
xxx.clear();

Offline bies

  • Użytkownik

# Październik 21, 2009, 18:05:58
Hmm, nie zawsze (vector::clear() nie musi zwolnić pamięci). Czasami lepiej:
xxx.swap(vector<T>());

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Październik 21, 2009, 18:12:21
Hmm, nie zawsze (vector::clear() nie musi zwolnić pamięci). Czasami lepiej:
xxx.swap(vector<T>());
1. Oryginalny "kod" tym bardziej pamięci nie zwolni.
2. Pamięć koniec końców i tak zwolni destruktor. Jeżeli z jakichś powodów nadal wektor jest trzymany, to pewnie nadal mamy zamiar go używać (np. budowac znowu listę czegoś w następnej klatce), więc trzymając pamięć oszczędzamy potencjalnie sporo allokacji.

Offline Xion

  • Redaktor
    • xion.log

# Październik 21, 2009, 18:31:54
Jeśli koniecznie chcesz to zrobić w pętli, to:
vector<T> xxx;

vector<T>::iterator it;
for(it=xxx.begin();it!=xxx.end();)
   {
   if (usunac(it)) it = xxx.erase(it); else ++it;
   }
(zakładam, że część elementów usuwasz, a część nie, bazując na jakimś warunku - jeśli chcesz wywalić wszystkie, to rzeczywiście clear() lub pokazany wyżej swap-trick są o wiele lepsze).

Offline Uszz

  • Użytkownik

# Październik 21, 2009, 19:17:26
Skoro w dyskusji pojawił się wątek iteratora zwracanego przez erase to chciałbym zwrócić uwagę, iż nie dla każdego kontenera to zadziała. Np dla std::map metoda erase nie zwraca iteratora [1], co oczywiście nie przeszkadza vs [2]  :D. Można się naciąć przy pracy z różnymi kompilatorami.

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Październik 21, 2009, 22:00:24
Dla wektora naturalne jest indeksowanie elementów liczbą całkowitą i ja tak lubię to robić. Niestety brakuje w wektorze metod, które wspierałyby np. usuwanie elementu wg indeksu, co wymaga zastosowania brzydkiej konstrukcji begin()+indeks. Ja to robię tak:

for (size_t i = 0; i < wektor.size(); )
{
  if (ElementDoUsuniecia(wektor[i]))
    wektor.erase(wektor.begin()+i);
  else
    i++;
}

A do tyłu tak:

for (size_t i = wektor.size(); i--; )
  if (ElementDoUsuniecia(wektor[i]))
    wektor.erase(wektor.begin()+i);

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Październik 21, 2009, 23:39:11
Cytuj
Ja to robię tak:
A ja tak: ;)
for(int i=0;i<vec.size();i++)
    if(should_be_deleted(vec[i]))
    {
        vec[i--] = vec.back();
        vec.pop_back();
    }

A jeżeli zaraz posypią się głosy, że mieszam kolejność elementów, to w takich sytuacjach robię tak:
int d = 0;
for(int i=0;i<vec.size();i++)
    if(!should_be_deleted(vec[i]))
        vec[d++] = vec[i];
vec.resize(d);

Offline bies

  • Użytkownik

# Październik 21, 2009, 23:58:27
Ja jestem zbyt leniwy na pisanie tego całego kodu. Odpowiednio bez zachowania kolejności i z zachowaniem:vec.erase(remove(vec.begin(), vec.end(), should_be_deleted), vec.end());
vec.erase(stable_partition(vec.begin(), vec.end(), not1(ptr_fun(should_be_deleted)), vec.end());
ptr_fun() potrzebne jest tylko wtedy gdy should_be_deleted to funkcja a nie funktor.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Październik 22, 2009, 04:01:57
Cytuj
vec.erase(remove(vec.begin(), vec.end(), should_be_deleted), vec.end());
vec.erase(stable_partition(vec.begin(), vec.end(), not1(ptr_fun(should_be_deleted)), vec.end());
Jestem zbyt leniwy na zapamiętanie tego całego makaronu (a potem przechodzenia za jakiś czas przez taki kod), a także na pisanie funkcji/funktorów jeżeli całość sprawdzenia to prosty warunek, który można wstawić gdzie trzeba. Poza tym Twoje lenistwo nie jest aż tak grubo opłacalne. ;)


for(int i=0;i<vec.size();i++)if(should_be_deleted(vec[i])){vec[i--]=vec.back();vec.pop_back();}
vec.erase(remove(vec.begin(),vec.end(),should_be_deleted),vec.end());

int d=0;for(int i=0;i<vec.size();i++)if(!should_be_deleted(vec[i]))vec[d++]=vec[i];vec.resize(d);
vec.erase(stable_partition(vec.begin(),vec.end(),not1(ptr_fun(should_be_deleted)),vec.end());

Offline bies

  • Użytkownik

# Październik 22, 2009, 12:18:09
To jest lenistwo innego poziomu. Ja wiem co robią stable_partition() i remove(). Pisząc ręcznie musiałbym pamiętać jak to robią. ;D

Offline naleth

  • Użytkownik

# Październik 22, 2009, 17:07:41
Wydaje mi się jednak, iż jeśli chce się usunąć elementy na podstawie predykatu, dodatkowo nie mieszając kolejności elementów nieusuwanych, to należy użyć std::remove_if (Remove_if is stable, meaning that the relative order of elements that are not removed is unchanged. ).

Funkcja std::remove porównuje z wartością (nie używa predykatu). Natomiast std::stable_partition dodatkowo gwarantuje, iż będzie zachowana kolejność elementów w tym przypadku usuwanych, co jest zbędne.

To oznacza, iż ekwiwalentem tego kodu:
int d = 0;
for(int i=0;i<vec.size();i++)
    if(!should_be_deleted(vec[i]))
        vec[d++] = vec[i];
vec.resize(d);
jest
vec.erase(remove_if(vec.begin(), vec.end(), should_be_deleted), vec.end());

Chyba nie ma natomiast funkcji w stl, która by realizowała wariant najszybszy (podany przez Krzyśka K), który może kompletnie zamieszać elementami:
for(int i=0;i<vec.size();i++)
    if(should_be_deleted(vec[i]))
    {
        vec[i--] = vec.back();
        vec.pop_back();
    }