11

Regarding the answer provided here: How to call erase with a reverse iterator

The following results in a segmentation fault (upon ++it) when compiled in g++ 4.8.4 with -std=c++11. Am I misunderstanding the answer?

  std::map<int,int> testmap;
  testmap[0] = 1;
  for(auto it=testmap.rbegin(); it!=testmap.rend(); ++it) {
    testmap.erase( std::next(it).base() );
  }
Community
  • 1
  • 1
logidelic
  • 1,525
  • 15
  • 42
  • `it = decltype(it){testmap.erase( std::next(it).base() )};` instead of `++it`. – Jarod42 May 03 '16 at 13:28
  • Don't you need to use --it with reverse iterator? The answer you cite suggests so. – Thinkeye May 03 '16 at 13:34
  • 2
    @Thinkeye no : reverse iterators traverse forwards through a reversed view of the container. The answer decrements `it.base()` -- the "normal" iterator that corresponds to the reverse iterator. – Quentin May 03 '16 at 13:37
  • 1
    @logidelic `erase` invalidates the iterator you pass into it, and returns the one you should continue traversing from. – Quentin May 03 '16 at 13:39

2 Answers2

13

erase invalidates the iterator, so you have to reconstruct it from the return value of erase:

it = std::map<int,int>::reverse_iterator(testmap.erase( std::next(it).base() ));

Or with C++11:

it = decltype(it){testmap.erase( std::next(it).base() )};

Or with C++17:

it = std::reverse_iterator(testmap.erase( std::next(it).base() ));

Demo.

For completeness, here is what the corrected loop from the original question looks like (notice that the iterator increment has been removed from the for(...)):

for (auto rit = testmap.rbegin(); rit != testmap.rend(); /* empty */) {
    if (WE_WANT_TO_ERASE(rit)) {
        rit = decltype(rit){ testmap.erase(std::next(rit).base()) };
    } else {
        ++rit;
    }
}
Olivia Stork
  • 4,660
  • 5
  • 27
  • 40
Jarod42
  • 203,559
  • 14
  • 181
  • 302
  • 4
    Don't forget to skip `++it` if you `erase`, lest you skip an element. – Quentin May 03 '16 at 13:40
  • Thanks for this response... I believe that you are correct, but I'm surprised that in the other discussions people have suggested (unchallenged) that this is not necessary. (For example, http://stackoverflow.com/a/3808880/1072039 ) – logidelic May 03 '16 at 13:43
  • Um, doesn't reverse iterator of iterator point to the previous element or somesuch? (so reverse(end()) and reverse(begin()) form a range) – Yakk - Adam Nevraumont May 03 '16 at 16:38
  • @logidelic: in the other question, there is a `break` to end the loop, that may explain why that point has not been really discussed. – Jarod42 May 03 '16 at 16:48
  • @Yakk: I don't understand your point: `{reverse_iterator(v.end()), reverse_iterator(v.begin())}` is the range`{v.rbegin(), v.rend()}`. (and indeed its internal should point into a *valid* range `{ v.begin(), v.end()}`) – Jarod42 May 03 '16 at 16:54
  • @Jarod42 Hmm. I guess it works: `erase` points to the next element after the erased one, and the one before the next element is the next element in reverse iteration. – Yakk - Adam Nevraumont May 03 '16 at 17:19
2

After some use of this idiom, I think a modification to the loop in Jarod42's answer is in order to make things safer and maintain the typical for(;;) loop niceties:

for (auto it = testcont.rbegin(), nit = it; it != testcont.rend(); it = nit) {
    nit = next(it);

    // whatever... maybe a continue somewhere or maybe not

    if (WE_WANT_TO_ERASE(it)) {
        nit = decltype(it){ testcont.erase(std::next(it).base()) };
    }

    // whatever... maybe a continue somewhere or maybe not
}

Using the loop in the other answer is too dangerous. If one were to thoughtlessly add a continue; somewhere in the loop, without incrementing the iterator first, the result would be an infinite loop. Since, at first glace, this can look like a normal for(;;) loop, I believe that this is bound to happen sooner or later. Similarly, if there are branches in the loop, and if one of those branches neglects to increment the iterator, another bug is introduced. Finally, if you do an erase(), you need to be sure to continue before you increment the iterator or else you have yet another bug.

Using the modified loop above, the loop can be treated just like a normal for(;;) loop. The trick is to increment nit (the "next iterator") as the first line of the loop body. Then you don't have to worry. The only time you need to update nit is if you are doing an erase(). Everything else works as one would expect a for loop to work.

One final note: I originally asked the question with regard to maps, but this will work correctly for vector, list, etc, as well.

logidelic
  • 1,525
  • 15
  • 42