std::map und remove_if() geht das?

PhilippM

Servus,

ich möchte selektiv Einträge aus einer map löschen. Bisher mache ich das so:

for (std::map<int, std::string>::iterator i = m_map.begin(), e = m_map.end(); i != e; )
{
    if (condition)
        m_map.erase(i++);
    else
        ++i;
}

Weil ich gelesen habe, remove_if() würde bei maps nicht gehen, da maps die Reihenfolge verändern.
Stimmt das?

Ist obiger Weg sicher(er)?

Gruß,
Phil

audacia

remove_if() dürfte bei std::map<> gar nicht erst compilieren, da für std::map<Key, Val> der value_type des Iterators std::pair <const Key, Val> ist - demnach kann der Key eines Elements nicht verändert werden. Das ist auch gut so - sonst würdest du das Gleichgewicht der Baumstruktur, über die std::map<> implementiert ist, durcheinanderbringen.

PhilippM

So in etwa hatte ich das auch Erinnerung.

Also ist obiger weg der richtige? Irgendwie hab ich beim iterator-rumschieben Bauchschmerzen.

Nexus

Das ist nicht gut, da der Iterator nach dieser Operation ungültig sein kann.

m_map.erase(i++);

Mach stattdessen

i = m_map.erase(i);

Badestrand

Nexus schrieb:

Das ist nicht gut, da der Iterator nach dieser Operation ungültig sein kann.
m_map.erase(i++);
Mach stattdessen
i = m_map.erase(i);

Und das ist nicht gut, weil map::erase void zurückgibt (Ich weiß selbst aber grad auch nicht, warum. Invalidiert "erase" die Iteratoren nicht? Hier steht leider auch nix dazu)

Nexus

Oh, stimmt, ich hatte das aus sequentiellen Containern noch so in Erinnerung.

Hm. Laut unserem STL-Artikel (Tabelle unten) werden Iteratoren bei einer std::map nie invalidiert. Ist eigentlich nachvollziehbar, wenn man bedenkt, dass die einzelnen Elemente wie in einer verketteten Liste nur über Zeiger gespeichert sind.

Edit: Das hab ich vor langer Zeit sogar mal gewusst. Ich habe es bei Maps seither kaum noch benötigt...

Badestrand

Cool, ok! Hab grad getestet, map.erase(x++) scheint ok zu sein, also x danach valide. map.erase(x); ++x; dagegen weniger. Obiger Code müsste dann eigentlich funktionieren.

edit: Btw: Schon merkwürdig, was man manchmal nicht weiß. Gestern hab ich erst erfahren, dass es "auto" auch schon vor C++0x gab (natürlich mit anderer bzw ohne Bedeutung)!

Nexus

Badestrand schrieb:

map.erase(x); ++x; dagegen weniger.

Ist auch nicht besonders erstaunlich, dass gelöschte Elemente keinen gültigen Iterator mehr haben.

Badestrand

Nexus schrieb:

Badestrand schrieb:

map.erase(x); ++x; dagegen weniger.

Ist auch nicht besonders erstaunlich, dass gelöschte Elemente keinen gültigen Iterator mehr haben.

Wollte nur das "nie" beim "werden nie invalid" prüfen

PhilippM

Badestrand schrieb:

Cool, ok! Hab grad getestet, map.erase(x++) scheint ok zu sein, also x danach valide. map.erase(x); ++x; dagegen weniger. Obiger Code müsste dann eigentlich funktionieren.

Alles klar, vielen Dank euch. Wieder ein //!< @todo Eintrag weniger

rean

Badestrand schrieb:

map.erase(x++) scheint ok zu sein,

Wenn man sich mal den tollen Artikel von pumuckl anschaut wird auch klar warum:

pumuckl schrieb:

3.10 operator++, --

Semantik: a++ : Postinkrement, erhöht den Wert von a um eins und gibt den Wert von a vor der Erhöhung zurück. Im Gegensatz dazu gibt das Präinkrement ++a den Wert von a nach der Erhöhung zurück. Analog operator-- als Post- bzw. Prädekrement (Erniedrigung).
Übliche Deklaration:
X& X::operator++(); //Praeinkrement
const X X::operator++(int); //Postinkrement
Die Deklaration der Dekrementoperatoren geschieht analog. Die Angabe eines formalen int-Parameters für die Postfix-Operatoren dient lediglich der Unterscheidung, das Argument darf nicht ausgewertet werden. Die Notwendigkeit unterschiedlicher Rückgabetypen als Referenz bzw. eigenes Objekt entstehen aus der Semantik und der entsprechenden Implementierung der Operatoren. Das Postinkrement gibt ein konstantes Objekt zurück, da es unsinnig wäre, das temporäre Rückgabeobjekt zu ändern.
Übliche Implementierung:
Der Präinkrementoperator wird implementiert, indem die relevanten Attribute entsprechend verändert werden und anschließend eine Referenz auf *this zurückgegeben wird.
Der Postinkrementoperator wird meist mittels des Präinkrements implementiert, seine Semantik macht es im Normalfall nötig dass vor der Erhöhung eine Kopie gemacht wird, die am Ende zurückgegeben wird:
X X::operator++(int)
{
  X tmp(*this); //Kopier-Konstruktor
  ++(*this); //Inkrement
  return tmp; //alten Wert zurueckgeben
}

Der Postinkrement macht in dem Beispiel map.erase( x++ ); also nichts anderes als das was man normalerweise von Hand machen würde:

std::map<foo,bar>::iterator tmp = x;
map.erase( x );
x = ++tmp;

Nur viel kürzer und schöner