Iterators: capability categories, ranges, and validity

A category is a contract on what algorithms may do

An input iterator supports reading and advancing, but it may have single-pass semantics, as with stream input. Copying such an iterator does not copy an independently replayable data source. A forward iterator adds a multi-pass guarantee. A bidirectional iterator adds decrement. A random-access iterator supports constant-time jumps and distance. An output iterator describes write capability; that is a separate capability axis, not "a higher rank than input."

A contiguous iterator requires, on top of random access, that elements correspond to contiguous memory locations. Ordinary vector iterators meet the contiguous requirement. deque promises only random access. list is bidirectional. The example states these requirements with C++20 concepts. Do not identify a category through sizeof, some implementation's internal field, or the fact that an iterator "looks like a pointer."

Half-open ranges and algorithm cost

Most algorithms take [first,last): first points at the first element and last is an excluded boundary. An empty range may have first equal to last, but end must not be dereferenced, and advancing must not pass a valid boundary. Two iterators from different containers usually cannot form one range, even when the element types match and the addresses look nearby.

std::distance is constant time for random-access iterators and must walk step by step on ordinary list iterators. std::next gives a uniform spelling; it does not magically turn a linear operation into a constant one. Modern ranges allow the iterator and the sentinel to have different types, replacing the assumption that "every end looks the same" with capability constraints. The range itself must still be valid.

Valid, dereferenceable, and still the same business element

Iterator invalidation is decided by the container and the specific modification, not by how high the category ranks. Reallocation of a vector invalidates all iterators; insertion into a list does not. A valid iterator is not necessarily dereferenceable: end is the usual counterexample. After a sort the position may still be valid and yet hold a different value, so business identity and storage position have to be kept apart.

When erasing while traversing, take the successor with it = container.erase(it); increment only when nothing was erased. The example deletes even numbers and checks the result, avoiding ++ on an invalidated iterator after erasure. Repeated single erase on a vector can become quadratic. Batch filtering is a better fit for erase-remove. The loop shows the validity protocol, not the best performance on every container.

Pitfalls

• A const_iterator only restricts modification of the element through that iterator. It does not guarantee that the container will not change, and it does not make an invalidated iterator valid again.
• "The iterator is still valid," "the iterator may be dereferenced," and "the iterator still names the original business record" are three different claims.

Minimum C++20 · complete program · Download .cpp

#include <cassert>
#include <deque>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>

int main() {
    static_assert(std::contiguous_iterator<std::vector<int>::iterator>);
    static_assert(std::random_access_iterator<std::deque<int>::iterator>);
    static_assert(!std::contiguous_iterator<std::deque<int>::iterator>);
    static_assert(std::bidirectional_iterator<std::list<int>::iterator>);
    static_assert(!std::random_access_iterator<std::list<int>::iterator>);

    std::vector<int> values{1, 2, 3, 4, 5};
    for (auto it = values.begin(); it != values.end();) {
        if (*it % 2 == 0) {
            it = values.erase(it);
        } else {
            ++it;
        }
    }
    assert((values == std::vector<int>{1, 3, 5}));
    std::list<int> nodes{4, 8, 12};
    auto a = nodes.begin();
    auto b = a;
    ++b;
    assert(*a == 4 && *b == 8);
    assert(std::distance(nodes.begin(), nodes.end()) == 3);
    std::cout << values[0] << ' ' << values[1] << ' ' << values[2] << '\n';
}

Compile locally

g++ -std=c++20 -Wall -Wextra -Wpedantic -pthread stl-iterators.cpp -o example && ./example

Expected result

1 3 5

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

A function first calls distance on an input-iterator range to compute a length, then walks the same source to read every value. Can it be used with istream_iterator? How should the interface be fixed?

Check the sources

• Working draft [iterator.concepts]: iterator capabilities by category
• Working draft [iterator.concept.forward]: the multi-pass guarantee
• Working draft [vector.modifiers]: position after erase

Drafts and official chapters change. The version mark is only the example’s minimum.