Dlaczego nie można usunąć ciąg z std :: set z std :: remove_if?

Question

Possible Duplicate:
remove_if equivalent for std::map

mam komplet strun:

set <wstring> strings; 
// ... 

I chcesz usunąć ciągi według orzecznika, np:

std::remove_if (strings.begin(), strings.end(), [](const wstring &s) -> bool { return s == L"matching"; }); 

Gdy próbuję tego, pojawia się następujący kompilatora błąd:

c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\algorithm(1840): error C2678: binary '=' : no operator found which takes a left-hand operand of type 'const std::basic_string<_Elem,_Traits,_Ax>' 

e rror wydaje się sugerować, że std::string nie ma konstruktora kopii o wartości wartości (który byłby nielegalny). Czy korzystanie z std::remove_if jest jakoś złe z std::set? Czy powinienem robić coś innego zamiast takiego, jak kilka iteracji set::find(), a następnie set::erase()?

Answer 1

std::remove_if (lub std::erase) działa poprzez ponowne przypisanie wartości członków zakresu. Nie rozumie, w jaki sposób organizuje dane lub jak usunąć węzeł z jego wewnętrznej struktury danych drzewa. Rzeczywiście, nie można tego zrobić, korzystając tylko z odniesień do węzłów, bez samego obiektu set.

Standardowe algorytmy mają przezroczystą (lub co najmniej konsekwentnie łatwą do zapamiętania) złożoność obliczeniową. Funkcja selektywnego usuwania elementów z set będzie miała postać O (N log N), ze względu na konieczność ponownego zrównoważenia drzewa, co nie jest lepsze niż wywołanie pętli my_set.remove(). Standard nie zapewnia tego, i to jest to, co musisz napisać. Z drugiej strony, naiwnie ręcznie kodowana pętla do usuwania elementów z pojedynczej jednostki vector to O (N^2), natomiast std::remove_if to O (N). Tak więc biblioteka zapewnia namacalną korzyść w tym przypadku.

Typowa pętla (C++ 03 style):

for (set_t::iterator i = my_set.begin(); i != my_set.end();) { 
    if (condition) { 
     my_set.erase(i ++); // strict C++03 
     // i = my_set.erase(i); // more modern, typically accepted as C++03 
    } else { 
     ++ i; // do not include ++ i inside for () 
    } 
} 

Edit (4 lata później!): i ++ wygląda podejrzanie tam. Co jeśli erase unieważnia i, zanim operator po inkrementacji może go zaktualizować? Jest to jednak w porządku, ponieważ jest to przeciążony operator++, a nie wbudowany operator. Funkcja bezpiecznie aktualizuje i w miejscu i , a następnie zwraca kopię oryginalnej wartości.

Answer 2

Komunikat o błędzie mówi

no operator found which takes a left-hand operand of type 'const std::basic_string<_Elem,_Traits,_Ax>'

Uwaga const. Kompilator jest poprawny, że std::wstring nie ma wartości operator=, którą można wywołać na obiekcie const.

Dlaczego ciąg znaków jest stały? Odpowiedź jest taka, że ​​wartości w std::set są niezmienne, ponieważ wartości w zbiorze są uporządkowane, a zmiana wartości może zmienić kolejność w zbiorze, unieważniając zestaw.

Dlaczego kompilator próbuje skopiować wartość zestawu?

std::remove_if (i std::remove) w rzeczywistości niczego nie kasują (ani nie mogą, ponieważ nie mają pojemnika, tylko iteratory). Co zrobić, to skopiować wszystkie wartości w przedziale, który nie dopasować kryterium do początku zakresu i zwraca iterator do następnego elementu po elementy pasujące do całości. Następnie należy ręcznie usunąć z zwróconego iteratora na koniec zakresu. Ponieważ zestaw zachowuje swoje elementy w porządku, niewłaściwe byłoby poruszanie dowolnymi elementami, więc nie można ich używać w zestawie (lub jakimkolwiek innym pojemniku asocjacyjnym).

Krótko mówiąc, trzeba używać pętlę std::find_if i set::erase, tak:

template<class V, class P> 
void erase_if(std::set<V>& s, P p) 
{ 
    std::set<V>::iterator e = s.begin(); 
    for (;;) 
    { 
    e = std::find_if(e, s.end(), p); 
    if (e == s.end()) 
     break; 
    e = s.erase(e); 
    } 
}