1

I am trying to understand the concept of iterator invalidation in vectors. From some of the reading I have done I have found that if a vector contains say 7 elements and you delete the element on the 5th index then the iterators from 5th element onwards become invalidated. This is because all the elements after the 5th index would need to move up one slot. This makes sense to me however I am a bit confused between the following two cases

    std::vector<foo> vec {foo{1},foo{2}};              //foo is a simple class
    foo* ptr = &vec[0];                                //Case 1
    std::vector<foo>::iterator it = vec.begin() + 1;   //Case 2

Is it safe to say that for a STL container if an iterator becomes invalidated then a pointer becomes invalidated too ? For instance if it becomes invalidated will ptr be invalid too ? If not could you give a case in which an iterator becomes invalidated but a pointer remains valid ? I am currently interested in vectors , maps and deques.

Update: So I wrote a little code and experimented

std::vector<foo> vec {foo{1},foo{2},foo{3}};
foo* ptr = &vec[1];
std::vector<foo>::iterator it = vec.begin() + 1;
std::cout << "Before : " <<  ptr->a << "\n";
vec.erase(vec.begin() + 1); //Remove the second element
std::cout << "Iterator value : " << it->a << "\n";
std::cout << "After : " <<  ptr->a << "\n";

The result was 

Before : 2
Iterator value : 3
After : 3

I am surprised why the vector did not mention that the iterator was invalid since this was the iterator obtained before an element was removed.

James Franco
  • 4,516
  • 10
  • 38
  • 80
  • Those vector operations invalidate all pointers, iterators and references to objects in the vector – M.M Sep 26 '15 at 04:57
  • You can reason out most rules about invalidation by thinking about how the container must manage its buffer, buffers or objects, and applying the rule that the standard is designed to allow efficient implementations. – Cheers and hth. - Alf Sep 26 '15 at 04:59
  • Re pointers, the standard uses the phrase "iterators and references", which for any practical interpretation includes pointers. That does not mean that all such pointers become *invalid pointers*. With an erase of a single item at index `i`, the pointers `&v[i]`, `&v[i+1]`, up to and including the now last item, simply refer to objects with possibly changed values (moved up one slot, as you phrase it). The vector's buffer is guaranteed contiguous, so as long as at least one pointer into it remains valid as pointer, the others (within the new size) must also be valid as pointers. – Cheers and hth. - Alf Sep 26 '15 at 05:05
  • @Cheersandhth.-Alf so does that mean if I have a pointer to the 2nd element in a container having 3 elements in total and I also have an iterator pointing also to the 2nd element. Now If I remove the second element the iterator to the elements 2 and 3rd will become invalid however the pointer will simply point to the new element (which will be the 3rd) ? – James Franco Sep 26 '15 at 05:23
  • @JamesFranco: In the formal-pedantic you're right, because it's possible to create a perverse implementation of `vector` that keeps track of iterators and do Unholy Things to them (it can't keep track of pointers). But in practice, it's the same for the iterators as for the pointers. They're formally invalidated, which means that they no longer point to objects with the same values as before, but they still refer to the very same objects. Note however that `erase` of one item causes the item formerly at the end, to be destroyed. There are special rules for such objects, dead but with storage. – Cheers and hth. - Alf Sep 26 '15 at 05:31
  • if the iterator in my above example was invalidated wasnt the program suppose to crash when I did `it->a` after removing the element – James Franco Sep 26 '15 at 05:32
  • @JamesFranco: No. It's formally UB, but this particular UB is of the innocent kind that can be predicted. No sane implementation of vector will keep track of iterators or endow with information and checking that just serves to make the access blow up, because that has big costs and no benefit. – Cheers and hth. - Alf Sep 26 '15 at 05:34

1 Answers1

1

Different containers behave differently when you remove an item.

From http://en.cppreference.com:

std::vector::erase

Invalidates iterators and references at or after the point of the erase, including the end() iterator.

std::map::erase

References and iterators to the erased elements are invalidated. Other references and iterators are not affected.

std::deque::erase

All iterators and references are invalidated, unless the erased elements are at the end or the beginning of the container, in which case only the iterators and references to the erased elements are invalidated.

R Sahu
  • 204,454
  • 14
  • 159
  • 270
  • I just updated my answer could you tell me why iterator did not get invalidated ? – James Franco Sep 26 '15 at 05:31
  • @JamesFranco, that's one of the unfortunate things of UB. Some times the code behaves in a sane manner. But it could easily be different in different compiler, different optimization flags, etc. – R Sahu Sep 26 '15 at 05:38
  • what does UB stand for ? – James Franco Sep 26 '15 at 05:41
  • @JamesFranco: It _did_. But whatever behaviour you were relying on happening when you attempted to use an invalidated iterator (you didn't say what that was), _don't_: anything can happen when you break the contract and use an invalid iterator! – Lightness Races in Orbit Sep 26 '15 at 21:53