C++20 Contiguous vs Random Access Iterator Concepts

In C++20, the introduction of concepts formalized iterator categorization within the type system, creating an explicit distinction between std::random_access_iterator and std::contiguous_iterator. While both iterator categories allow constant-time arbitrary navigation across elements, contiguous iterators enforce an additional strict guarantee: the underlying elements must be stored adjacent to one another in physical memory. This article explores how C++20 classifies contiguous iterators as a refinement of random-access iterators, the syntactic and semantic guarantees involved, and why this distinction matters in modern C++.

The Random Access Iterator Concept

The std::random_access_iterator concept defines iterators that can traverse sequences bidirectionally in constant time (\(O(1)\)). To satisfy this concept, an iterator type must support arithmetic operations such as addition and subtraction with integers, relational comparisons (<, <=, >, >=), and subscripting (operator[]).

Types satisfying std::random_access_iterator can access any element at offset n directly. However, they do not guarantee that those elements reside sequentially in contiguous memory addresses. A canonical example is std::deque::iterator, which provides constant-time indexed access across multiple allocated memory chunks, but fails to maintain a single unbroken memory layout.

The Contiguous Iterator Concept

The std::contiguous_iterator concept strictly refines std::random_access_iterator. An iterator satisfying this concept possesses all the navigation capabilities of a random-access iterator, but adds a crucial memory layout requirement: the elements it visits must be stored contiguously in memory.

Formally, C++20 specifies that for a dereferenceable contiguous iterator i and an integral offset n such that i + n is valid, the following relationship must hold true:

*(i + n) is equivalent to *(std::to_address(i) + n)

The function std::to_address obtains a raw pointer to the element referenced by the iterator. Because the elements are physically adjacent, advancing the iterator by n steps yields the exact same memory address as advancing a raw pointer by n element sizes.

Additionally, C++20 introduced the std::contiguous_iterator_tag, which allows legacy type-tag dispatching mechanisms to differentiate contiguous iterators from standard random-access iterators.

Key Differences and Comparison

Feature	`std::random_access_iterator`	`std::contiguous_iterator`
Complexity for offset operations	\(O(1)\)	\(O(1)\)
Subscript syntax (`it[n]`)	Supported	Supported
Physical memory layout	Can be fragmented (e.g., segmented buffers)	Strictly contiguous
Raw pointer equivalence	Not guaranteed	Guaranteed via `std::to_address`
Standard Container Examples	`std::deque`	`std::vector`, `std::array`, `std::string`, `std::span`, raw pointers

Why the Distinction Matters

Prior to C++20, algorithms could not reliably detect whether a generic random-access range was contiguous in memory without using traits or container-specific assumptions. The introduction of std::contiguous_iterator provides two major benefits:

Low-Level Interoperability: Algorithms can safely extract a raw pointer (std::to_address(it)) to pass contiguous blocks of memory directly to C-style APIs, operating system system calls, or hardware buffers.
Algorithm Optimizations: Standard library algorithms like std::copy, std::fill, and serialization functions can automatically detect contiguous storage and dispatch to vectorized memory instructions (such as std::memmove or SIMD intrinsics) without sacrificing type safety.