Iterating through a vector and erasing

Question

It is obvious for many that this code will produce a segment fault.

#include <iostream> #include <string> #include <vector> int main() { std::vector<int> ints; ints.push_back(5); std::vector<int>::iterator it; for(it = ints.begin(); it != ints.end(); ++it){ std::cout << *it; it = ints.erase(it); } }

If we remove the ++it and add a condition to erase, we can avoid this error. But what is the actual cause of the issue? In our loop we say, for the start of the iterator, until it reaches the end, incrementing by one, print out the value and then erase it. Is it because the ++it is called at the "end" when, in this condition, we've already removed the next (only) value?

It most certainly does. Undefined behavior means anything can happen, including demons flying out of your nose. That's exactly how that term originated, to drive home the point. It's a certainty you will never forget this turn of words, and you will always be mindful of it. — Sam Varshavchik
– Sam Varshavchik, Commented Feb 25, 2020 at 16:26
@errno_44 On the last iteration ints.erase(it); returns ints.end(). The for loop then tries to ++ that iterator which is not allowed. — François Andrieux
– François Andrieux, Commented Feb 25, 2020 at 16:27
I never liked erasing the elements of a container that's being iterated.. — Eric
– Eric, Commented Feb 25, 2020 at 16:37

463035818_is_not_an_ai · Accepted Answer · 2020-02-25 16:39:13Z

2

Is it because the ++it is called at the "end" when, in this condition, we've already removed the next (only) value?

Yes.

std::erase returns an iterator to the element after the one that was erased.

Consider a vector with only a single element, then your loop is basically:

it = ints.begin(); std::cout << *it; it = ints.erase(it); // it == ints.end() ++it; // boom //if (it != ints.end()) // more boom

See here: Is it allowed to increment an end iterator? - No.

Such problems are one reason to prefer the erase-remove-idiom rather than a hand-written loop to erase elements.

edited Feb 25, 2020 at 16:39

answered Feb 25, 2020 at 16:29

463035818_is_not_an_ai

128k11 gold badges116 silver badges240 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

errno_44 Over a year ago

Thanks. Shouldn't the purpose of an iterator be to mask the work for the user (ie me). If I ++ on a iterator, but it's at the end already, why doesn't it just.. not do anything? Why is C and C++ full of traps!

François Andrieux Over a year ago

@errno_44 Because protecting the developers from traps sometimes has a cost. In this case, iterators would have to perform additional checks. And C++ has a core belief that it should not force overhead if it can be avoided. If you want such protections, you can write your own iterator and use that instead.

PaulMcKenzie Over a year ago

@errno_44 -- Because C++ is not going to do extra work to keep you safe. C++ is a language where you are supposed to only pay for what you use. You decide to use no error checking on your part, that's your business.

463035818_is_not_an_ai Over a year ago

@errno_44 that would mean that each increment would have to do an additional check. And if you think about it, that wouldnt even help in general, because what if your loop does not go till end but only till begin() + n ? In that case you wouldnt have UB but your code would still be wrong and checking for increment of end would not help

François Andrieux Over a year ago

@errno_44 Note that in some library implementations, iterators will provide protection against most common traps but only in debug builds. These protections will not change the behavior of the iterator. Instead, they will warn you of problems by triggering break points or otherwise signalling the problem.

|

MSalters · Accepted Answer · 2020-02-25 16:49:47Z

Your assumption is mistaken. Let me quote the relevant part:

In our loop we say, for the start of the iterator, until it reaches the end, incrementing by one, print out the value and then erase it.

That description swaps the two bold parts, and it is important. The increment is done before the check if it reached the end. That's wrong when erasing the last element. In that case, your iterator is already at the end, and you still increment it before checking if it reached the end.

Collectives™ on Stack Overflow

Iterating through a vector and erasing

2 Answers 2

6 Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Linked

Related