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

9

Ich habe eine Reihe von Zeichenfolgen:

%Vor%

Ich möchte Zeichenfolgen gemäß einem Prädikat entfernen, z. B .:

%Vor%

Wenn ich das versuche, bekomme ich den folgenden Compilerfehler:

%Vor%

Der Fehler scheint darauf hinzudeuten, 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 benutzen? Sollte ich stattdessen etwas anderes machen, zB mehrere Iterationen von set::find() gefolgt von set::erase() ?

    
Benj 21.06.2012, 15:34
quelle

2 Antworten

19

std::remove_if (oder std::erase ) funktioniert, indem die Werte der Mitglieder des Bereichs neu zugewiesen werden. Es versteht nicht, wie std::set Daten organisiert oder wie ein Knoten aus seiner internen Baumstruktur entfernt wird. In der Tat ist es unmöglich, nur Referenzen auf Knoten zu verwenden, ohne das set -Objekt selbst zu haben.

Die Standardalgorithmen sind so konzipiert, dass sie eine transparente (oder zumindest durchwegs leicht zu merkende) Komplexität der Berechnungen aufweisen. Eine Funktion zum selektiven Entfernen von Elementen aus set wäre O (N log N), da der Baum neu gewuchtet werden muss, 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.

Andererseits wäre eine naiv handkodierte Schleife, um Elemente aus einem vector eins nach dem anderen zu entfernen, O (N ^ 2), während std::remove_if O (N) ist. Die Bibliothek bietet also in diesem Fall einen greifbaren Vorteil.

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

%Vor%

Bearbeiten (4 Jahre später!): i ++ sieht dort verdächtig aus. Was passiert, wenn erase i ungültig macht, bevor der Post-Inkrement-Operator sie aktualisieren kann? Dies ist jedoch in Ordnung, da es sich um einen überladenen operator++ handelt und nicht um den integrierten Operator. Die Funktion aktualisiert i vor Ort sicher und dann gibt eine Kopie ihres ursprünglichen Wertes zurück.

    
Potatoswatter 21.06.2012, 15:37
quelle
9

Die Fehlermeldung sagt

  

kein Operator gefunden, der einen linken Operanden vom Typ ' const akzeptiert   std :: basic_string & lt; _Elem, _Traits, _Ax & gt; '

Beachten Sie die Konstante. Der Compiler ist korrekt, dass std::wstring kein operator= hat, das für ein konstantes Objekt aufgerufen werden kann.

Warum ist die Zeichenkette konstant? Die Antwort ist, dass die Werte in 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 tatsächlich nichts (auch nicht, weil sie nicht den Container haben, sondern nur Iteratoren). Sie kopieren alle Werte in dem Bereich, in denen nicht mit dem Kriterium am Anfang des Bereichs übereinstimmt, und geben einen Iterator an das nächste Element nach den übereinstimmenden Elementen zurück. 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, irgendwelche Elemente zu verschieben, sodass remove_if nicht für einen Satz (oder einen anderen assoziativen Container) verwendet werden kann.

Kurz gesagt, Sie müssen eine Schleife von std::find_if und set::erase verwenden, also:

%Vor%     
ymett 21.06.2012 16:02
quelle

Tags und Links