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 correctness 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.

The readable iterator categories form a capability hierarchy: forward iterators meet input requirements, bidirectional iterators add reverse movement, random-access iterators add constant-time jumps, and contiguous iterators additionally guarantee adjacent storage. Output iterators model a writing role rather than another level of readable access.

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).

Advancing an iterator outside its valid range is not a bounds-checked operation. std::next(nums.end()), for example, is invalid. The caller must know that the requested destination is reachable.

Invalidation Rules

The past-the-end iterator deserves explicit attention. It does not refer to an element, so a rule that preserves references to elements does not necessarily preserve a previously saved end() iterator.

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;
});

The iterator returned by erase is the correct resumption point. Do not increment the erased iterator first, and do not use a previously cached end() when the operation may have invalidated it.

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.

Further Reading

• C++ working draft: iterator requirements
• C++ working draft: container requirements
• C++ working draft: deque modifiers