6

The C++ reference clearly state that calling std::vector::erase(it) on iterator will invalidate all iterators pointing to and after the erased element. http://en.cppreference.com/w/cpp/container/vector/erase

I do understand why such iterators became non-dereferenceable after the erase call, but i am curious why they need to became invalid, what implementation details require it?

For instance standard says that std::vector must be implemented with elements stored contiguously and that elements can be accessed not only through iterators, but also using offsets on regular pointers to elements so it seems logical that iterators for such container will probably be implemented as pointers - but then how pointers could became invalidated?

Yatima
  • 200
  • 6

4 Answers4

9

One of the principles on which the conceptual idea of iterator is built, is as follows: as long as iterator remains non-aliased, dereferenceable and non-modified, it should refer to the same entity. In other words, dereferencing the same iterator multiple times should yield the same value. Algorithms that use iterators may rely on that.

What you proposing would result in an iterator that would "magically" change the value it refers to even though the iterator itself remains unchanged. This is not acceptable within the conceptual idea of iterator.

On the second thought, what I said above is obviously flawed in a sense that we can always apply some modifying operation to the vector that shifts elements around (e.g. std::random_shuffle). Such operation would not invalidate any iterators, but would easily change the values the iterators refer to. How is that different from element shifting triggered by erase? It isn't.

AnT stands with Russia
  • 312,472
  • 42
  • 525
  • 765
  • I see, - this is exactly what i was looking for, - thank you @AnT ! As follow up question: does this mean that it might be still legal to decrement or de-referene such invalidated iterators or that is always will be considered to be undefined behavior? – Yatima Dec 01 '16 at 00:04
  • @Feng Shu: Dereferencing or moving an invalidated iterator is always undefined behavior. It is probably possible to make an effort to allow this for `std::vector` iterators specifically, but it doesn't seem to be worth it. The primary purpose of iterator concept is to serve as an abstract uniform intermediary between algorithms and data sequences. For which reason trying to specify something that would only apply to a very narrow specific subset of iterators (vector iterators) would not be of much value for the concept. – AnT stands with Russia Dec 01 '16 at 00:31
  • 1
    re `std::random_shuffle` and how it different from `erase`: it could be argued that shuffling is just changing values of elements in container but leaving it geometry unchanged so in that sense all iterators after `std::random_shuffle()` is still point to exactly the same container elements (but such elements changed values). While in `erase()` case function change container geometry so old iterators is no longer pointing to the same logical elements and thats why iterators invalided... – Yatima Dec 01 '16 at 20:32
  • I have difficulty in understanding what "invalid" actually means too, when I read this post https://stackoverflow.com/questions/6438086/iterator-invalidation-rules about some invalidation rules . From your description(sorry I just want to make sure), are you saying that if the iterator no longer "points" to the same value, then it's considered to be "invalid" too? – Rick Dec 10 '19 at 02:21
  • Btw, do you agree with @Marshall Clow 's [explanation](https://stackoverflow.com/a/40900279/5983841) on the meaning of "invalidated", which is `"invalidated" can mean "no longer points to what it used to", not just "may not point to any valid element"` ? – Rick Dec 10 '19 at 02:24
5

"invalidated" can mean "no longer points to what it used to", not just "may not point to any valid element"

consider (uncompiled code):

vector<int> v = {0, 1, 2, 3, 4, 5};
vector<int>::iterator iter = v.begin() + 3;  // "points to" 3
assert(*iter == 3);
v.erase(v.begin());

At this point, iter has been invalidated. It no longer "points to" the same element that it did before.

Marshall Clow
  • 15,972
  • 2
  • 29
  • 45
  • Hmm, i was under impression that any attempts to use `invalidated` iterators lead to undefined behavior. Are you implying that this is not the case? If so, could you please point to any reference material that state this? – Yatima Dec 01 '16 at 00:02
  • 1
    No, you are correct. Once they've been invalidated, you have no guarantees. It `*iter` *might* have the value `4`. It might not. it might crash your program. – Marshall Clow Dec 01 '16 at 00:07
2

std::vector must be implemented with elements stored contiguously

This is the reason. If you erase an element inside the vector, the elements, at the least, must be shifted. You could, not with debug protection:

std::vector< int > test= {1,2,3,4,5,6,7};
auto it= test.begin( ) + 2;
test.erase( it );
std::cout << *it << std::endl;

And it will likely print '4'. But there is no guaranty. What if the vector reallocs? What if you erase test.begin( ) + 6 ? If you change the size of a vector, it can be moved.

More Info

Community
  • 1
  • 1
lakeweb
  • 1,859
  • 2
  • 16
  • 21
  • 5
    `std::vector` is not allowed to realloc on `erase` until it is empty. (Obviously, if reallocation were possible, it would invalidate all iterators, including the ones pointing before the erased one.) The OP seems to be perfectly aware of this point. – AnT stands with Russia Nov 30 '16 at 23:25
  • But still all iterators after the erased element will point to wrong elements because the elements are shifted. – Dragos Pop Nov 30 '16 at 23:34
  • Hi @AnT I didn't know that was a rule. I've always assumed not to trust where a vector would be if the size changes. Thanks. – lakeweb Dec 01 '16 at 00:09
0

I simply see no reason for the iterators to become invalid with the point where I begin to erase the elements. vector::erase( ... ) does use the assignment-opetor, so the objects in the vector are never invalidated. If I would do the same with my own code ...

template<typename T>
void vector_erase( vector<T> &v, typename vector<T>::iterator first, typename vector<T>::iterator last )
{
    typename vector<T>::iterator shiftOld,
                                 shiftNew;
    for( shiftOld = last, shiftNew = first; shiftOld != v.end(); ++shiftOld, ++shiftNew )
        *shiftNew = move( *shiftOld );
    v.resize( shiftNew - v.begin() );
}

... the iterators would be valid until the point where I cut the vector.

Bonita Montero
  • 2,817
  • 9
  • 22
  • I'm not clear what the point of contention is. The standard says iterators at or after the erasure become invalidated. So, yes, iterators pointing to items before the erasure remain valid. Are you specifically asking about the one that was at the beginning of the erasure? – Adrian McCarthy Apr 01 '19 at 17:17