STL map, iterator und erase

1x Contest-Sieger

26.10.2010, 14:04

STL map, iterator und erase

Hi,
Ich beschäftige mich zur Zeit mit OGRE und OIS (eine recht gut passende input-bibliothek für OGRE). Das Problem ist, dass OIS z.B. beim drücken einer maustaste nur maximal eine "stelle" darüber informieren kann. Wenn man jetzt aber zwei verschiedene Objekte informieren will, braucht man eine Art Inputmanager, der als empfänger dient, und dann an alle anderen "stellen", die auch informiert werden wollen, eigenständig informiert.

Intern gelöst ist dieser Inputmanager (gefunden in einem OGRE-wiki-artikel) mit einer std::map. Man hat methoden wie addKeyListener(...), removeKeyListener(...) um "zuhörer" hinzuzufügen oder zu löschen. die methode keyPressed(...) wird bei einem echten tastendruck aufgerufen und sie selbst ruft wiederum dann die methode aller listener auf. Soweit so gut.

Hier vielleicht mal die keyPressed methode:

C-/C++-Quelltext

bool InputManager::keyPressed(const OIS::KeyEvent& evt) {
    std::map<std::string, OIS::KeyListener*>::iterator itKeyListener = m_keyListeners.begin();
    std::map<std::string, OIS::KeyListener*>::iterator itKeyListenerEnd = m_keyListeners.end();
    for (; itKeyListener != itKeyListenerEnd; ++itKeyListener) {
        if (!itKeyListener->second->keyPressed(e))
            break;
    }
}

Das Problem hierbei ist jetzt, dass während des iterierens über die map die keyPressed(e) methode der einzelnen zuhörer bestimmte zuhörer löschen oder hinzufügen kann. Dummerweise ist es relativ wahrscheinlich, dass sich der zuhörer selbst löscht. Konsequenz ist, dass der iterator der dann gerade auf das element zeigt, nicht mehr gültig ist und die schleife das programm zum abstürzen bringt.

Irgendwie fällt mir hier keine Lösung ein, wie ich über alle elemente iterieren kann, auch wenn währenddessen welche gelöscht werden können. Ein grund hierfür ist auch, dass die erase-methode der map keinen iterator auf das nächste element zurückliefert. Wieso nicht? Und wie kann ich das problem lösen?

Zum Seitenanfang

5x Contest-Sieger

Wohnort: Bielefeld

26.10.2010, 15:05

Hi,
normalerweise gibt man in der Situation jedem Element ein bool ShouldBeDeleted Member und löscht dann seperat in einer eigenen Schleife alle, die das auf true gesetzt haben.

Ansonsten bietet erase unter VS sehr wohl einen Rückgabewert, ist halt nur nicht vom Standard vorgeschrieben.
Falls du auch die anderen Compiler unterstützen möchtest geht aber auch ein map.erase(it++);

Ciao
Helmut

Sei stets geduldig gegenüber Leuten, die nicht mit dir übereinstimmen. Sie haben ein Recht auf ihren Standpunkt - trotz ihrer lächerlichen Meinung. (F. Hollaender)

Zum Seitenanfang

1x Contest-Sieger

26.10.2010, 15:34

Ich benutze kein VS (auch wenn ich VS 2010 Ultimate lizenz hab

). Ich weiß nicht, ich beschränk mich nicht gern nur auf Windows. Und auch wenns makefile projekte unterstützt und ich gcc nutzen könnte, irgendwie hab ich keine lust drauf

Zitat

map.erase(it++);

Das hab ich gesucht, denn auch wenn ich in einer seperaten schleife die elemente lösche, hab ich ja das gleiche problem und müsste ansonsten die schleife ja immer wieder von vorne beginnen lassen bis irgendwann kein element mehr gelöscht wird... und das wäre ja mal nen ziemlicher effizienzkiller

Edit: danke

Zum Seitenanfang

1x Contest-Sieger

26.10.2010, 19:54

OK, jetzt antworte ich auch mal auf mich selbst

Hab es jetzt mal mit der zusätzlichen shouldBeDeleted variable versucht (hat ne weile gedauert, da ich keine neue klasse schreiben wollte und stattdessen mal boost::tuple ausprobiert habe

). Funktioniert soweit auch, der iterator bleibt gültig und das programm stürtzt nicht mehr ab.

problem ist jetzt aber, dass dummerweise, wenn ich in der schleife wieder einen neuen listener hinzufüge, die schleife dafür auch nochmal durchläuft. auch wenn ich vor der schleife
m_keyListeners.end();
nur 1 mal ausführe, speichere und dann damit vergleiche. Da habe ich mir wohl den container wieder wie eine liste vorgestellt und dachte, dass er dann auch nur bis zu dem "ende" läuft, zu dem es "gemessen" wurde

Normalerweise würde ich sagen, dass die sofortige hinzunahme (also das "verschieben" des endes) eigentlich sinnvoll ist. In meinem Fall ist es aber total unerwünscht

Jemand einen Tipp, wie man das am besten lösen könnte? Mit dem problem sollten sich ja denke ich einige hier schonmal auseinandergesetzt haben... danke schonmal im voraus

Zum Seitenanfang

5x Contest-Sieger

Wohnort: Bielefeld

26.10.2010, 20:03

Verstehe irgendwie dein Problem nicht. Kannst du mal Code posten?

Sei stets geduldig gegenüber Leuten, die nicht mit dir übereinstimmen. Sie haben ein Recht auf ihren Standpunkt - trotz ihrer lächerlichen Meinung. (F. Hollaender)

Zum Seitenanfang

1x Contest-Sieger

26.10.2010, 21:57

Nunja, am code hat sich nicht so viel geändert:

C-/C++-Quelltext

bool InputManager::keyPressed(const OIS::KeyEvent &evt) {
std::map<std::string, RemovableKeyListener>::iterator itKeyListener = m_keyListeners.begin();
std::map<std::string, RemovableKeyListener>::iterator itKeyListenerEnd = m_keyListeners.end();
for (; itKeyListener != itKeyListenerEnd; ++itKeyListener) {
    if (!boost::tuples::get<0>(itKeyListener->second)->keyPressed(e))
        break;
}

return true;
}

Statt einer

	Quellcode
1	std::map<std::string, OIS::KeyListener*>

benutze ich jetzt eine

	Quellcode
1	std::map<std::string, RemovableKeyListener>

mit

	Quellcode
1	typedef boost::tuple<OIS::KeyListener*, bool> RemovableKeyListener;

Wenn die schleife oben jetzt z.B. in ihrem eigentlich letzten durchgang ist und keyPressed(e) nichts macht, bricht sie korrekterweise ab, wie gewollt. wenn sie allerdings im letzten durchgang ist (im letzten vor dem aufruf von keyPressed(e)) und keyPressed(e) jetzt einen neuen listener hinzufügt, bricht die schleife nicht ab, sondern der iterator wird noch einmal erhöht und das event wird an den gerade hinzugefügten listener gesendet. das will ich nicht.

Eine möglichkeit wäre es, dem tupel noch einen bool wert hinzuzufügen, z.B. canGetEvents, was ich beim hinzufügen mit false initialisiere, in der obigen schleife dann abfrage und danach (wie im anfangsproblem ganz oben) dann in einer seperaten schleife auf true setze. damit sollte dann das auch um einen "zyklus" versetzt laufen. Aber irgendwie find ich die lösung nicht wirklich schön.

Ich dachte mir, für das korrekte durchlaufen eines containers, während elemente hinzugefügt und gelöscht werden können, gäbe es vielleicht schon einen tollen trick.

Edit: ein kleiner nachtrag noch... kann mir mal jemand die syntax da oben boost::tuples::get<0>(t) erklären? irgendwie kann ich es nicht so ganz nachvollziehen... ist get eine klasse?

Zum Seitenanfang

5x Contest-Sieger

Wohnort: Bielefeld

26.10.2010, 22:16

Du könntest von m_keyListeners lokal eine Kopie machen, um keyPressed aufzurufen. Das löst dann auch gleich das erste Problem ohne bool Variable, ist aber natürlich etwas verschwenderisch.

Der Iterator von end() wird übrigens ungültig, sobald der Container vergrößert oder verkleinert wird. Dass das nicht klappte war also zu erwarten

Ciao
Helmut

Sei stets geduldig gegenüber Leuten, die nicht mit dir übereinstimmen. Sie haben ein Recht auf ihren Standpunkt - trotz ihrer lächerlichen Meinung. (F. Hollaender)

Zum Seitenanfang

1x Contest-Sieger

26.10.2010, 22:36

hhmm ja so eine temporäre kopie wäre wirklich sehr komfortable

Da die map ja eigentlich nur pointer hält sollte eine kopie nicht sooo aufwändig sein (ich denke auch, dass der normalfall wohl so etwa 2-3 elemente sind). Allerdings kann ich nicht wirklich einschätzen, ob das ein problem für die performance werden könnte. Die methode sollte eigentlich nur sehr selten (eben bei menschlichem input

) aufgerufen werden.

Meinst du, ich sollte den variablenkram da wieder wegmachen und es mit einer lokalen variable versuchen, oder den kram dalassen und noch um eine variable erweitern?

Zum Seitenanfang

5x Contest-Sieger