C++ Iterators and Invalidation

3 minute read

Published:

Overview

Iterators provide a common traversal interface across STL containers. The same syntax works for contiguous containers such as vector, node-based containers such as list, and tree-based containers such as map.

The main interview risks are:

  • Confusing end() with the last element.
  • Using an algorithm that requires a stronger iterator category.
  • Continuing to use an iterator after it has been invalidated.

Common Includes

#include <algorithm>
#include <iterator>
#include <list>
#include <map>
#include <vector>

Half-Open Ranges

STL algorithms work on half-open ranges: [begin, end).

std::vector<int> nums = {10, 20, 30};

auto first = nums.begin();                // points to 10
auto last = nums.end();                   // one past 30

for (auto it = first; it != last; ++it) {
  int value = *it;
}

end() is not dereferenceable. It is a sentinel used for comparison.

Iteration Patterns

Explicit iterator:

for (auto it = nums.begin(); it != nums.end(); ++it) {
  *it += 1;
}

Const iterator:

for (auto it = nums.cbegin(); it != nums.cend(); ++it) {
  int value = *it;
}

Reverse iterator:

for (auto it = nums.rbegin(); it != nums.rend(); ++it) {
  int value = *it;
}

Range-based loop:

for (const auto& value : nums) {
  // read without copying
}

for (auto& value : nums) {
  value *= 2;
}

Iterator Categories

Not all iterators support the same operations.

CategoryExamplesSupports
Forwardforward_list++it
Bidirectionallist, map, set++it, --it
Random accessvector, deque, arrayit + n, it[n], ordering comparisons

This is why std::sort works on vector but not on list.

std::vector<int> v = {3, 1, 2};
std::list<int> l = {3, 1, 2};

std::sort(v.begin(), v.end());            // OK
// std::sort(l.begin(), l.end());         // does not compile

l.sort();                                 // OK

Iterator Helpers

Use iterator helpers instead of assuming pointer arithmetic works.

std::list<int> nums = {10, 20, 30, 40, 50};

auto it = nums.begin();
std::advance(it, 3);                      // it points to 40

auto next_it = std::next(it);             // points to 50, it unchanged
auto prev_it = std::prev(it);             // points to 30, it unchanged

int dist = static_cast<int>(std::distance(nums.begin(), it));

For list, these operations walk nodes and are O(n). For vector, they are O(1).

Invalidation Rules

ContainerInvalidated by insertInvalidated by erase
vectorAll iterators if reallocated; otherwise at/after insert positionAt/after erased position
dequeUsually all iteratorsUsually all iterators
listNothingOnly erased element
map, set, multisetNothingOnly erased element
unordered_map, unordered_setAll iterators if rehashedOnly erased element

For vector, reallocation also invalidates pointers and references to elements.

Erase While Iterating

Wrong:

std::vector<int> nums = {1, 2, 3, 4, 5};

for (auto it = nums.begin(); it != nums.end(); ++it) {
  if (*it % 2 == 0) {
    nums.erase(it);                       // it is invalid after erase
  }
}

Correct:

for (auto it = nums.begin(); it != nums.end();) {
  if (*it % 2 == 0) {
    it = nums.erase(it);                  // next valid iterator
  } else {
    ++it;
  }
}

C++20:

std::erase_if(nums, [](int x) {
  return x % 2 == 0;
});

Checklist

  • Treat [begin, end) as the default STL range shape.
  • Never dereference end().
  • Use const auto& to avoid unnecessary copies in range loops.
  • Use std::next and std::prev when the container is not random-access.
  • After erase, use the iterator returned by erase.
  • Re-check iterator validity after container growth, especially for vector and unordered_map.

Leave a Comment

You May Also Enjoy