set<int> - iterator und erase

[Gast221212]

Hallo, warum funktioniert das nicht:

set<int> vicinity;

vicinity.insert(3);
vicinity.insert(12);
vicinity.insert(43);
vicinity.insert(11);
vicinity.insert(5);
vicinity.insert(9);
...

// Iterator vicinity.end() wird nie erreicht, warum?
for (set<int>::iterator it = vicinity.begin(); it != vicinity.end(); it++) {
  if (*it < 10) {
    vicinity.erase(it)
    // Jetzt muss ich ja auch eins zurückgehen, oder???
    it--;
  }
}

[Ponto]

Nach dem erase ist dein Iterator ungültig und kann nicht verwendet werden.

Du willst hier sowas machen:

if ( *vicinity.begin() < 10)
   vicinity.erase(vicinity.begin(), vicinity.lower_bound(10));

[Gast221212]

Ponto schrieb:

Nach dem erase ist dein Iterator ungültig und kann nicht verwendet

Danke, das ist ja schon mal der Grund, warum es nicht geht, aber ich will eigentlich sowas machen

if(do_some_nasty_tests_with(*it))
  // Weg mit dem it...

sollte dann eigentlich so gehen:

it = vicinity.begin();
int size = vicinity.size();
for (i = 0; i < size; i++) {
  if (...) {
    vicinity.erase(it+i);
    i--;
    size--;
  }
}

werd's mal so testen...

[Gast221212]

noch besser:

wer einen Blick in's Manual wirft wird schneller schlauer:

erase...
...
Both return an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists.

also dann:

for (set<int>::iterator it = vicinity.begin(); it != vicinity.end(); ) {
  if (*it < 10) {
    it = vicinity.erase(it)
  } else {
    it++;
  }
}

geht - Danke an Ponto -, Thread kann geschlossen werden!

[Ponto]

Es ist eventuell besser, wenn du dein Programm so entwirfst, dass du direkt ganze Ranges löschen kannst. Das ist schneller, als den ganzen set zu scannen.

[Ponto]

Gast221212 schrieb:

noch besser:

wer einen Blick in's Manual wirft wird schneller schlauer:

erase...
...
Both return an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists.

also dann:

for (set<int>::iterator it = vicinity.begin(); it != vicinity.end(); ) {
  if (*it < 10) {
    it = vicinity.erase(it)
  } else {
    it++;
  }
}

geht - Danke an Ponto -, Thread kann geschlossen werden!

Davon steht nichts im Standard. Laut Standard gibt erase(iterator postion) von std::set<T> void zurück. Das erase() macht aber sonst keine iteratoren kaputt. So dass du dir einfach den nächsten vormerken kannst.

[Gast221212]

Ponto schrieb:

direkt ganze Ranges löschen kannst

Klar, aber

if(do_some_nasty_tests_with(*it))

optimieren kann man das ganze dann immernoch wenns läuft...

[ssm]

set<int>::iterator it = vicinity.begin(), end = vicinity.end();
while(it != end)
{
  if (*it < 10) 
  { 
    //magic:
    vicinity.erase(it--);
  } 
}

[ChrissiB]

ssm: kann es da nicht Probleme geben? Ich habe es seit ein paar Tagen auch so gemacht wie du es gezeigt hast, bis mir einer gesagt habe, dass das möglicherweise nicht gehen könnte. (okay, gehen schon, halt nen dummes Verhalten :)) D.h. erase() kann nicht nur den momentanen Iterator ungültig machen, sondern auch den, der auf das nächte Element zeigt oder weitere. Der inkrementierte Iterator würde daher dann ins Nichts zeigen. Die Lösung wäre dann der Rückgabewert, da dieser den nächsten gültigen Iterator zurückliefert. Ich weiß nicht, ob das stimmt, so wurde es mir auf alle Fälle gesagt. Was meinst du dazu, stimmt das oder nicht? Ich selbst weiß es nicht, da ich mir noch nie eine erase() Implementierung angeschaut habe.

[Ben04]

Nein ssm so geht das nicht, das Problem ist, dass da erstens ein ++it irgendwo fehlt und zweitens was wenn das erste Objekt gelöscht wird?

Was klappt ist folgendes:

set<int>::iterator it = vicinity.begin(), end = vicinity.end();
while(it != end)
{
  set<int>::iterator next = it;
  ++next;
  if(*it < 10)
    vicinity.erase(it);
  it = next;
}

Und das klappt auch nur bei Containern die nur den gelöschten Iterator invalid machen.

[ssm]

ChrissiB schrieb:

ssm: kann es da nicht Probleme geben? Ich habe es seit ein paar Tagen auch so gemacht wie du es gezeigt hast, bis mir einer gesagt habe, dass das möglicherweise nicht gehen könnte. (okay, gehen schon, halt nen dummes Verhalten :)) D.h. erase() kann nicht nur den momentanen Iterator ungültig machen, sondern auch den, der auf das nächte Element zeigt oder weitere. Der inkrementierte Iterator würde daher dann ins Nichts zeigen.

das ja ist blödsinn

23.1.2 Associative containers §8
The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements

ich hab doch einen Fehler gemacht, soll so sein:

[cpp]set<int>::iterator it = vicinity.begin();
while(it != vicinity.end())
{
if (*it < 10)
{
//magic:
vicinity.erase(it++);
}
else
{
++it;
}
} [/cpp]

[ssm]

Ben04 schrieb:

Und das klappt auch nur bei Containern die nur den gelöschten Iterator invalid machen.

das klappt bei allen Containern, die Associative sind 23.1.2 §8