std::distance vs Iterator Subtraction in C++

You will learn how to convert an iterator position into an offset, why both expressions are efficient for std::vector, and why std::distance works with more iterator types. You will also learn the complexity and validity rules that determine which form is appropriate.

An iterator is an object that identifies a position in a container or range. To find an iterator's position relative to the beginning, calculate the number of steps from begin() to that iterator.

For a vector, both of these expressions produce that offset:

it - vec.begin();
std::distance(vec.begin(), it);

A std::vector has random-access iterators, which can jump directly to a position. Therefore, both operations take constant time, O(1), for a vector.

The important difference is generality:

• it - vec.begin() requires random-access iterators.
• std::distance(vec.begin(), it) works with many iterator categories, including iterators from std::list and std::forward_list.

For non-random-access iterators, std::distance may need to walk one element at a time, making it O(n). Iterator subtraction is not supported for those iterator types at all.

Both expressions return an iterator's difference_type, which is usually a signed integer-like type. It represents a distance or offset, not necessarily a container's unsigned size_type.

Think of iterators as ways of locating a house on a street.

• Iterator subtraction is like using house numbers on a perfectly numbered street: subtract house number 1 from house number 8 and immediately get 7. This only works on streets that support that numbering system.
• std::distance is like asking, “How many steps are there from this house to that house?” On a numbered street, the answer is immediate. On a winding path, you may need to walk and count each step.

A vector is the numbered street, so both approaches are fast. A linked list is the winding path, so only std::distance is generally available, and it may have to walk through nodes.

Use iterator subtraction when you specifically require random-access iterators, such as iterators from std::vector, std::deque, or std::array.

#include <cstddef>
#include <vector>

std::vector<int> values{10, 20, 30, 40};
auto it = values.begin() + 2;

std::vector<int>::difference_type index = it - values.begin();
// index is 2

Use std::distance when you want code that can also work with other iterator categories.

#include <iterator>
#include <list>

std::list<int> values{10, 20, 30, 40};
auto it = std::next(values.begin(), 2);

auto index = std::distance(values.begin(), it);
// index is 2

For a vector, the following are equivalent in result and asymptotic performance:

auto index1 = it - values.begin();
auto index2 = std::distance(values.begin(), it);

If an API requires std::size_t, convert only after you know the result cannot be negative:

std::size_t index = static_cast<std::size_t>(it - values.begin());

When it is a valid iterator in values at or after values.begin(), the conversion is safe.

Consider this vector traversal:

#include <iostream>
#include <iterator>
#include <vector>

int main() {
    std::vector<char> letters{'A', 'B', 'C'};

    for (auto it = letters.begin(); it != letters.end(); ++it) {
        auto index = std::distance(letters.begin(), it);
        std::cout << index << ": " << *it << '\n';
    }
}

Execution trace:

1. On the first iteration, it equals letters.begin() and points to 'A'.
2. The distance from begin() to itself is 0, so the program prints 0: A.
3. ++it moves to 'B'.
4. The distance from begin() to this position is 1, so it prints 1: B.
5. ++it moves to 'C'.
6. The distance is now 2, so it prints 2: C.
7. After the final increment, it == letters.end(), and the loop stops.

Because letters is a vector, std::distance uses a constant-time calculation here. Replacing the distance call with it - letters.begin() produces the same output.

Iterator distances are useful when an algorithm gives you an iterator but another part of the program needs a position.

• Search results: Convert the iterator returned by std::find into the index of a matching item in a vector.
• Parsing: Report the character offset where a parser found an invalid token.
• User interfaces: Turn a selected iterator in an in-memory list of rows into a row number.
• Data processing: Identify the position of a maximum or minimum element returned by an algorithm.
• Debugging and logs: Include an element offset in an error message.

Example with std::find:

#include <algorithm>
#include <iterator>
#include <vector>

std::vector<int> ids{42, 71, 99};
auto found = std::find(ids.begin(), ids.end(), 71);

if (found != ids.end()) {
    auto index = std::distance(ids.begin(), found);
    // index is 1
}

Always check for end() before dereferencing a search result. Computing the distance to end() is valid for a vector, but *found would be invalid when the value was not found.

In production C++ code, choose the expression that communicates the requirement of the code.

Generic algorithms

If a function accepts a general iterator type, prefer std::distance:

#include <iterator>

template <class Iterator>
auto offset_from_begin(Iterator first, Iterator current) {
    return std::distance(first, current);
}

This can work with vectors, lists, and other iterator-based ranges, although its cost depends on the iterator category.

Vector-specific code

When code explicitly works with a vector and performance-sensitive indexing is intended, subtraction is common and direct:

std::vector<int> values{4, 8, 15, 16};
auto it = std::find(values.begin(), values.end(), 15);

if (it != values.end()) {
    auto index = it - values.begin();
}

Avoid repeated linear distances

For a std::list, do not repeatedly call std::distance(begin, it) inside a traversal if you need a counter. Keep one yourself:

#include <cstddef>
#include <list>

std::list<int> values{10, 20, 30};
std::size_t index = 0;

for (auto it = values.begin(); it != values.end(); ++it, ++index) {
    // Use index and *it.
}

This keeps the full traversal O(n), rather than potentially turning it into O(n²).

Subtracting list iterators

std::list iterators are bidirectional, not random access. This does not compile:

#include <list>

std::list<int> values{1, 2, 3};
auto it = values.begin();
auto index = it - values.begin(); // Error: operator- is not supported

Use std::distance instead:

auto index = std::distance(values.begin(), it);

Assuming std::distance is always O(1)

For a vector, it is O(1). For a list or forward list, it is normally O(n). Avoid calculating it repeatedly in loops over non-random-access containers.

Mixing iterators from different containers

Do not subtract unrelated iterators:

std::vector<int> left{1, 2};
std::vector<int> right{3, 4};

auto bad = left.begin() - right.begin(); // Undefined behavior

Both iterators must refer to positions in the same underlying sequence or range.

Dereferencing end()

end() is a valid boundary position, but it does not point to an element:

auto it = values.end();
auto index = it - values.begin(); // Valid for a vector
// *it;                           // Invalid: never dereference end()

Using an unsigned type too early

Distances can be signed. Keep the result as difference_type or auto unless you have verified it is non-negative:

auto offset = it - values.begin();
if (offset >= 0) {
    auto index = static_cast<std::size_t>(offset);
}

Invalidating an iterator before using it

Operations such as push_back, insert, erase, or reallocation can invalidate vector iterators. Do not calculate an offset from an iterator after an operation that invalidated it.

std::vector::size() is also O(1), but it answers a different question: it gives the total number of elements, not the position of a particular iterator.

In modern range-based code, std::ranges::distance is a related C++20 facility. It can be used with iterators or ranges, but the same central idea remains: the cost depends on what the range or iterator category supports.

// Offset of an iterator within a vector
std::vector<int> values{1, 2, 3};
auto it = values.begin() + 1;

auto a = it - values.begin();              // 1; vector only
auto b = std::distance(values.begin(), it); // 1; more general

• Both forms are O(1) for std::vector.
• operator- requires random-access iterators.
• std::distance supports more iterator types.
• std::distance can be O(n) for lists and forward lists.
• The result type is usually Container::difference_type, which is signed.
• Use iterators from the same container/range only.
• Never dereference container.end().
• Check search results against end() before dereferencing.
• If you need positions during a list traversal, keep a separate incrementing counter.

Is std::distance slower than subtracting iterators for a vector?

No in asymptotic terms. For vector iterators, both are constant-time O(1). In normal optimized builds, std::distance is typically implemented using subtraction for random-access iterators.

Should I use std::distance or it - begin() with std::vector?

Use subtraction when the code is intentionally vector-specific and you want to state that random access is required. Use std::distance when you want the code to work with a broader set of iterator types.

Does std::distance work with std::list?

Yes. It counts through the list from the first iterator to the second iterator, which is generally O(n).

Why does it - begin() fail for a list?

A list stores elements as linked nodes rather than contiguous positions. Its iterators can move one step at a time, but cannot directly calculate the number of nodes between two positions.

What type does std::distance return?

It returns the iterator's difference_type, a signed integer-like type designed to represent distances between iterator positions.

Can I use the result as a vector index?

Yes, when the iterator is known to be in the vector and at or after begin(). Convert to std::size_t only if an unsigned index is required.

Is calculating the distance to end() valid?

Yes. For a vector, std::distance(vec.begin(), vec.end()) equals vec.size(). However, you must not dereference vec.end().

• Iterator categories — Explain which operations an iterator supports, including random access and bidirectional movement.
• std::vector iterators — Vector iterators support efficient indexing and subtraction.
• std::list iterators — List iterators demonstrate why some distances require traversal.
• std::find — Commonly returns an iterator that may need to be converted into an offset.
• Iterator invalidation — Explains when stored iterators become unsafe after container modifications.
• std::next and std::prev — Move iterators by a number of positions without requiring random access in every case.
• C++20 ranges — Provides range-oriented alternatives such as std::ranges::distance.