Warum kann ich einen String nicht aus einem std :: set mit std :: remove_if entfernen?

Question

Possible Duplicate:
remove_if equivalent for std::map

Ich habe eine Reihe von Strings:

set <wstring> strings; 
// ... 

Ich wünsche Strings entfernen nach einem Prädikat, zum Beispiel:

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

Wenn ich dies versuchen, erhalte ich die folgenden Compiler Fehler:

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>' 

Die e Rrror scheint darauf hinzuweisen, dass std::string keinen Kopie-Konstruktor für Wert nach Wert hat (was illegal wäre). Ist es irgendwie schlecht, std::remove_if mit std::set zu verwenden? Sollte ich stattdessen etwas anderes machen, zB mehrere Iterationen von set::find() gefolgt von set::erase()?

Answer 1

std::remove_if (oder std::erase) funktioniert, indem die Werte der Mitglieder des Bereichs Neuzuordnung. Es versteht nicht, wie std::set Daten organisiert oder wie man einen Knoten aus seiner internen Baumstruktur entfernt. In der Tat ist es unmöglich, dies nur mit Bezug auf Knoten zu tun, ohne das set Objekt selbst zu haben.

Die Standardalgorithmen sind so entworfen, dass sie eine transparente (oder zumindest konsistent leicht zu merkende) Komplexität der Berechnungen haben. Eine Funktion zum selektiven Entfernen von Elementen aus einer set wäre O (N log N), aufgrund der Notwendigkeit, den Baum neu zu balancieren, was nicht besser ist als eine Schleife, die my_set.remove() aufruft. Also, der Standard bietet es nicht, und das ist es, was Sie schreiben müssen. Auf der anderen Seite wäre eine naiv handcodierte Schleife, um Elemente aus einer vector eins nach der anderen zu entfernen, 0 (N^2), wohingegen std::remove_if O (N) ist. Die Bibliothek bietet also in diesem Fall einen greifbaren Vorteil.

Eine typische Schleife (C++ 03-Stil):

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 () 
    } 
} 

bearbeiten (4 Jahre später!): i ++ sieht es verdächtig. Was, wenn erasei ungültig macht, bevor der Post-Inkrement-Operator es aktualisieren kann? Dies ist jedoch in Ordnung, weil es eine überladene operator++ und nicht der integrierte Operator ist. Die Funktion aktualisiert sicher i in-place und dann gibt eine Kopie des ursprünglichen Werts zurück.

Answer 2

Die Fehlermeldung sagt

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

Notiere die konst. Der Compiler ist korrekt, dass std::wstring kein operator= hat, das für ein const-Objekt aufgerufen werden kann.

Warum ist die Zeichenfolge const? Die Antwort lautet, dass die Werte in einer std::set unveränderlich sind, da die Werte in einer Menge geordnet sind und das Ändern eines Werts die Reihenfolge in der Menge ändern kann, wodurch die Menge ungültig wird.

Warum versucht der Compiler einen Wert der Menge zu kopieren?

std::remove_if (und std::remove) löschen Sie eigentlich nichts (noch können sie, weil sie nicht den Container haben, nur Iteratoren). Sie kopieren alle Werte in den Bereich nicht das Kriterium an den Anfang des Bereichs anpassen und einen Iterator an das nächste Element nach den übereinstimmenden Elementen zurückgeben. Sie sollten dann manuell vom zurückgegebenen Iterator bis zum Ende des Bereichs löschen. Da ein Satz seine Elemente in der richtigen Reihenfolge hält, wäre es falsch, Elemente zu verschieben, so dass remove_if nicht für einen Satz (oder einen anderen assoziativen Container) verwendet werden kann.

Kurz gesagt, Sie haben eine Schleife von std::find_if zu verwenden und set::erase, etwa so:

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); 
    } 
}