Verhalten eines Iterators, wenn der Eintrag auf den er Zeigt, aus der STL Map gelöscht wird?

K3il3

Heyho,

ich hab momentan folgendes Problem:

Ich habe zwei Maps. Ich möchte jeden Eintrag in der einen Map löschen, wenn ein Eintrag mit dem selben Key in der anderen Map vorhanden ist. Dazu gehe ich in einer Schleife durch alle Einträge der ersten Map und suche nach einen Eintrag in der zweiten Map, der den selben Key hat.
Hier mal ein Bsp:

#include <map>
using namespace std;

int main()
{
   map<int, int> erste;
   map<int, int> zweite;

   ...

   map<int, int> :: iterator iter;
   iter = erste.begin();
   while (iter != erste.end())
   {
      map<int, int> :: iterator iter2;
      iter2 = zweite.find(iter->first);
      if (iter2 != zweite.end()
      {
         erste.erase(iter);             // hier liegt das Problem
      }
      iter++;
   }
   return 0;
}

Nun war ich mir nicht sicher, wohin der Iterator iter zeigt, wenn der Eintrag, auf den er eigentlich zeigt, gelöscht wird.
Darauf hin hab ich nen Kollegen gefragt, er meinte, dass iter mit dem Löschen des Eintrages ungültig wird. Das selbe hab ich auch in einem englischen Forum gefunden.

Also umgehe ich das Problem momentan folgender Maßen:

#include <map>
using namespace std;

int main()
{
   map<int, int> erste;
   map<int, int> zweite;

   ...

   map<int, int> :: iterator iter;
   iter = erste.begin();
   while (iter != erste.end())
   {
      map<int, int> :: iterator iter2;
      iter2 = zweite.find(iter->first);
      if (iter2 != zweite.end()
      {
         map<int, int> :: iterator iter3;
         iter--;
         iter3 = iter;
         iter++;
         erste.erase(iter);
         iter = iter3; 
      }
      iter++;
   }
   return 0;
}

Somit habe ich nach dem Löschen wieder ein Iterator auf dem vorgänger Element, welcher dann automatisch auf das nächste Element incrementiert wird.
Allerdings finde ich diese Lösung absolut unschön (von den Variablennamen mal abgesehen). Habt ihr ne elegantere Möglichkeit dieses Problem zu umgehen?

Gruß K3il3

map<int, int> :: iterator iter;
   iter = erste.begin();
   while (iter != erste.end())
   {
      map<int, int> :: iterator iter2 = zweite.find(iter->first);
      if (iter2 != zweite.end()
         iter = erste.erease(iter);
      else
         iter++;
   }

K3il3

hmm,

laut dieser Referenz ist die Funktion erase() der Map eine void Funktion, somit wird doch kein neuer Iterator zurückgegeben?

http://www.sgi.com/tech/stl/Map.html

In dieser Referenz steht auch, dass erase() ne void Funktion ist. Glaube also nicht, dass deine Lösung funktioniert.

http://www.cppreference.com/cppmap/erase.html

Bitte nur Lösungen anbieten von denen man weiss, dass sie funktionieren! Und wenn möglich, noch ein kleinen Kommentar zu der Lösung geben. Danke

K3il3 schrieb:

In dieser Referenz steht auch, dass erase() ne void Funktion ist. Glaube also nicht, dass deine Lösung funktioniert.

ok, hab ich mit der intuitiven lösung wohl daneben gelegen.

Bitte nur Lösungen anbieten von denen man weiss, dass sie funktionieren! Und wenn möglich, noch ein kleinen Kommentar zu der Lösung geben. Danke

vielen dank für die belehrung. wird nicht wieder vorkommen.

queer_boy

warum durchläufst du nicht die zweite map und löscht alles in der ersten, was du dort findest?

for (map<int,int>::iterator i = zweite.begin(); i != zweite.end(); ++i)
{
  erste.erase(i->first);
}

andernfalls sei noch gesagt, dass erase bei maps nur den aktuellen iterator invalidiert, alle anderen aber unberührt lassen muss. d.h. du brauchst eine kopie des iterators, bevor du ihn inkrementierst. in C++ gibt es dafür sogar einen eigenen operator:

if (iter2 != zweite.end())
{
 erste.erase(iter++); //erstelle eine kopie von iter (die wird invalidiert) und 
//bevor sie invalidiert wird, zeigt iter schon auf das nächste element.
} else ++iter;

PS. nicht nur eine stilfrage: initialisiere deine iteratoren gleich gleich bei ihrer definition (RAII):

map<int,int>::iterator i = erste.find(...)

macht den code auch übersichtlicher.

@das mobvieh: du hast einfach assoziative container mit sequenzcontainern verwechselt, bei denen funktioniert erase nämlich so.

K3il3

Danke für die Lösung.
Man muss bei der 2. Variante allerdings aufpassen, dass man den iter in der Schleife nicht noch mal incrementiert, ohne abzusichern dass er durch dein increment nicht bei erste.end() steht. Ansonsten kann es zu bösen Fehlern kommen.

Gruß

queer_boy

K3il3 schrieb:

Danke für die Lösung.
Man muss bei der 2. Variante allerdings aufpassen, dass man den iter in der Schleife nicht noch mal incrementiert, ohne abzusichern dass er durch dein increment nicht bei erste.end() steht. Ansonsten kann es zu bösen Fehlern kommen.

Gruß

ja. die inkrementierung aus der schleife raus, für die wird in dem if/else block gesorgt.

K3il3

ja schon, aber es kann ja immernoch vorkommen, dass man an einer anderen stelle in der schleife incrementiert.

z.b.

#include <map>
using namespace std;

int main()
{
   map<int, int> erste;
   map<int, int> zweite;

   ...

   map<int, int> :: iterator iter;
   iter = erste.begin();
   while (iter != erste.end())
   {
      map<int, int> :: iterator iter2;
      iter2 = zweite.find(iter->first);
      if (iter2 != zweite.end()
      {
         erste.erase(iter++);             
      }else iter++;

      ... 

      <tu das>
      <tu jenes>

      ...

      iter++;
   }
   return 0;
}

Wenn dann der Schleifenkopf das iter wieder mit erste.end() vergleichen will, wird es höchst wahrscheinlich krachen.

Somit bleibt immer ein Restrisiko. Man muss sich also ganz genau überlegen, ob man diese Lösung anwendet.

Th

Pro Schleife darfst du natürlich nur genau 1x den Iterator inkrementieren (aber dies gilt ja für jede Schleife).

pumuckl

Da maps wunderbar sortiert sind kann man doch gleich stl-algorithmen verwenden:

int main() {
  std::map<int, int> erste;
  std::map<int, int> zweite;

  std::map<int, int> tmp(erste); //kopie von erste
  std::map<int,int>::iterator last_of_sequence = 
    std::set_difference(erste.begin(), erste.end(), zweite.begin(), zweite.end(), tmp.begin(), erste.value_comp()); //kopiert alle Werte aus erste, die nich in zweite enthalten sind, an den Anfang von tmp
  tmp.erase(last_of_sequence, tmp.end()); //lösche den rest von tmp
  erste.swap(tmp); //vertausche den inhalt von tmp und erste - erste enhält jetzt nurnoch das was nicht in zweite drin war.
}

oder noch einfacher:

int main() {
  std::map<int, int> erste;
  std::map<int, int> zweite;
  std::map<int,int>::iterator last_of_sequence = 
    std::set_difference(erste.begin(), erste.end(), zweite.begin(), zweite.end(), erste.begin(), erste.value_comp());
  erste.erase(last_of_sequence, erste.end());
}

Bin aber nicht sicher ob das vom Standard garantiert ist, das set_difference entsprechend sicher arbeitet.

queer_boy

pumuckl schrieb:

Da maps wunderbar sortiert sind kann man doch gleich stl-algorithmen verwenden:

int main() {
  std::map<int, int> erste;
  std::map<int, int> zweite;

  std::map<int, int> tmp(erste); //kopie von erste
  std::map<int,int>::iterator last_of_sequence = 
    std::set_difference(erste.begin(), erste.end(), zweite.begin(), zweite.end(), tmp.begin(), erste.value_comp()); //kopiert alle Werte aus erste, die nich in zweite enthalten sind, an den Anfang von tmp
  tmp.erase(last_of_sequence, tmp.end()); //lösche den rest von tmp
  erste.swap(tmp); //vertausche den inhalt von tmp und erste - erste enhält jetzt nurnoch das was nicht in zweite drin war.
}

oder noch einfacher:

int main() {
  std::map<int, int> erste;
  std::map<int, int> zweite;
  std::map<int,int>::iterator last_of_sequence = 
    std::set_difference(erste.begin(), erste.end(), zweite.begin(), zweite.end(), erste.begin(), erste.value_comp());
  erste.erase(last_of_sequence, erste.end());
}

map sortiert allerdings selbst.
Bin aber nicht sicher ob das vom Standard garantiert ist, das set_difference entsprechend sicher arbeitet.

ich bin immer noch nicht sicher, warum mein erster lösungsvorschlag auf soviel skepsis stößt.

pumuckl

queer_boy schrieb:

ich bin immer noch nicht sicher, warum mein erster lösungsvorschlag auf soviel skepsis stößt.

Skepsis nicht. dein Vorschlag funktioniert wunderbar, ich hab nur eine Alternative aufgezeigt. Welche von beiden performanter ist, hängt vermutlich von der Größe der beiden Maps und der zu löschenden Schnittmenge ab.

queer_boy

sorry, das war auch in richtung des OPs gemeint: er sollte doch einen hinweis genau darauf geben, was du angesprochen hast.