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, Feb 25 '20 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, Feb 25 '20 at 16:27
That's why I included a link to its official definition, where you can read all about it. — Sam Varshavchik, Feb 25 '20 at 16:29
I never liked erasing the elements of a container that's being iterated.. — Eric, Feb 25 '20 at 16:37
@Rixment: With good reason. We've got the [`remove-erase` pattern](https://stackoverflow.com/questions/39912/how-do-i-remove-an-item-from-a-stl-vector-with-a-certain-value) for that. — MSalters, Feb 25 '20 at 16:48

463035818_is_not_an_ai · Accepted Answer · 2020-02-25T16:39:13.677

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 '20 at 16:39

answered Feb 25 '20 at 16:29

463035818_is_not_an_ai

109,796
11
89
185

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! – errno_44 Feb 25 '20 at 16:30
@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. – François Andrieux Feb 25 '20 at 16:32
@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. – PaulMcKenzie Feb 25 '20 at 16:33
@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 – 463035818_is_not_an_ai Feb 25 '20 at 16:33
@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. – François Andrieux Feb 25 '20 at 16:34
_Why is C and C++ full of traps!_ C and C++ are not nanny languages. They both strive to be as performant as possible, which means the burden is on the programmer not to make mistakes, such as incrementing an iterator past end. There are other programming languages that provide a lot more safety nets to assist unwary programmers, but those come at a cost. C++ gives you enough rope to shoot yourself in the foot. – Eljay Feb 25 '20 at 17:40

MSalters · Answer 2 · 2020-02-25T16:49:47.100

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.

Iterating through a vector and erasing

2 Answers2