2

For a vector v in STL, is it safe to store v.end() (eg. vector::iterator) for later use? Will I be guaranteed that when I later use the stored iterator, it will still point at the same location?

Consider the following vector v:
1, 2, 3, 4, 5

I now store away std::vector<int>::iterator it = v.end(). Later, I push in 2 new elements into the vector, after which it looks like:
1, 2, 3, 4, 5, 6, 7.

Can I now be assured that *it == 6?

lwxted
  • 2,419
  • 2
  • 16
  • 22

2 Answers2

6

No.

After you push something into a std::vector the end() iterator is always invalidated.

All other iterators are valid unless

the new container size is greater than the previous capacity

However there are containers whose iterators do not get invalidated after pushing. Refer to the excellent answers to this question.

If you want to remember the locations within a vector using iterators while pushing new elements, you can ensure that the new size is not greater than the old capacity using the reserve() member.

std::vector<int> numbers = {1,2,3};
numbers.reserve(4);
int capacity = numbers.capacity();  // capacity >= 4
std::vector<int>::iterator pos = numbers.begin() + 2 // any iterator before
                                                     // the point of insertion
numbers.push_back(4); // new size is 4, old capacity is >= 4, 
                      // therefore pos is still valid.
Community
  • 1
  • 1
Martin Drozdik
  • 12,742
  • 22
  • 81
  • 146
  • Thanks, then it is that the only way to remember locations with in a vector would be to remember the location using array index, if I'm to push extra elements into a vector? – lwxted Mar 06 '14 at 18:05
  • 1
    @lwxted Exactly. Either that or use a `std::list` whose iterators do not get invalidated after pushing extra elements. – Martin Drozdik Mar 06 '14 at 18:07
  • 3
    In C++11 iterators are only invalidated if the new size is greater than the old capacity. – Brian Bi Mar 06 '14 at 18:08
  • 1
    @BrianBi: but iterators after the insertion point are also invalidated regardless, right? And the end iterator is after any insertion point. – Steve Jessop Mar 06 '14 at 18:21
  • @SteveJessop before editing the answer claimed that all iterators were invalidated, full stop. – Brian Bi Mar 06 '14 at 18:30
  • @MartinDrozdik: Your statement about iterator invalidation is almost but not quite the opposite of truth. One too many negations? And also forgot edge cases? – Mooing Duck Mar 06 '14 at 18:40
  • @MooingDuck I just realized that the question is not as trivial as it first seemed. Please, could you tell me where is the mistake? I read that the past-the-end iterator is always invalidated after a call to push_back from here http://en.cppreference.com/w/cpp/container/vector/push_back – Martin Drozdik Mar 06 '14 at 18:47
  • 1
    @MartinDrozdik: The past the end iterator _is_ always, invalidated, that part is right. It's the _next_ statement about the rest of the iterators that's backwards. – Mooing Duck Mar 06 '14 at 19:02
1

§ 23.3.6.5/1 [vector.modifiers]

Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.

It's not stated explicitly, but this means that all iterators, references at and after the insertion point are invalidated. This includes the end iterator. This section is specifically about insert/push_back, but is still more or less accurate when it comes to erases and such as well.

§ 23.3.6.3/5 [vector.capacity]

Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. It is guaranteed that no reallocation takes place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the value of capacity().

Mooing Duck
  • 64,318
  • 19
  • 100
  • 158