Odstranění prvků vyhovujících predikátu z STL map

[Quiark]

Zdravím, dneska jsem narazil na problém s touto "triviální" úlohou. Mám std::map<int, MujObjekt>. Chtěl bych z ní vyhodit všechny záznamy, kde instance mého objektu splňuje jistý predikát. Jak na to ve standardním C++ ?

Jeden přístup by byl asi takovýto:

[MD]

Jen tak, co me v rychlosti napada: Nemel bys tam dat tomu erase primo iterator (tedy i) a ne klic? Pak by to melo smazat a vratit iterator na nasledujici prvek.

Edit: Nejsem si vubec jist jestli se to da takhle v cyklu prochazet a mazat. Ten strom se muze pri deletu preorganizovat a pak by ti mohly nektere objekty utect (dostat se pred iterator a ty bys je preskocil). Pokud tohle nekdo vite, tak me to docela zajima. V MSDN u erase samozrejme nic nepisou.

Edit2: MSDN: Note that this return type does not conform to the C++ standard.
_________________
- play with objects - www.krkal.org -

[Quiark]

To je stejná situace:
http://www.cplusplus.com/reference/stl/map/erase.html

EDIT: V MSDN píšou, že ta jejich verze erase vrací iterátor za vymazaný prvek, tak by to mohlo jít.
_________________
Mám strach

[Marek]

Linked list se mi tady zdá vhodnější. Jinak ten erase s iterátorem by měl být celkem snadno implementovatelný. Především se mi nelíbí to, že ten tvůj algoritmus má složitost O(nlogn) (erase s klíčem), když by mohl mít jen O(n) (erase s iterátorem). V případě, že parametr je opravdu klíč, pak bys musel udělat find na hledanej prvek s klíčem, udělat ++iterator na další prvek a smazat ten nalezený. Pokud mažeš přímo podle iterátoru, stačí si jen zapamatovat následující prvek. Mazání během procházení tady nevadí, pokud se to udělá opatrně. Kód na požadované erase:

[Quiark]

No tu map<> tam asi z nějakého důvodů mám, žejo Tahle operace se dělá jednou za uherský rok, takže mě rychlost tolik netíží. A je pravda, že udělat it + 1 před smazáním mě mohlo napadnout (jinak ano, iterátor mám k dispozici, do toho kódu nahoře jsem to napsal blbě). Pokud map<> používá standardní binární vyhledávací strom s uspořádáním podle <, potom by přeskládání nemělo vadit, protože pořadí prvků je pořád stejné.
_________________
Mám strach

[MD]

operace plus ++ na iteratoru jde na nejblizsi vyzsi prvek (jsou serazene), je to tak?
Pak by preskakovani prvku bylo nelogicke.
_________________
- play with objects - www.krkal.org -

[Tringi]

Z dokumentace:

[Quiark]

Super
_________________
Mám strach