Ch8.2: Range Categories

Overview

Ranges differ in what operations they support. Some can only be read once, some allow multiple passes, some allow backward movement, and some allow constant‑time jumps or direct access to memory addresses.

A clear way to understand these differences is to view range categories as a capability hierarchy. Each level includes everything from the previous one, plus additional abilities.

In this chapter, you will learn:

• the full range category hierarchy
• the readable chain from input_range to contiguous_range
• the separate writable branch output_range
• how to detect categories using if constexpr

1. The full range hierarchy

All range categories refine the base concept range. From there, the hierarchy splits into a readable chain and a separate writable branch:

range
│
├── input_range
│     │
│     ├── forward_range
│     │
│     ├── bidirectional_range
│     │
│     ├── random_access_range
│     │
│     └── contiguous_range
│
└── output_range   (separate writable branch)

This chapter focuses on the readable hierarchy (the left branch).

2. input_range

The smallest readable category. An input_range supports:

• reading elements once
• moving forward only
• single‑pass traversal

3. forward_range

A forward_range has all capabilities of an input_range and additionally supports:

• multiple passes over the same elements
• revisiting elements in the same order

A forward_range is also an input_range.

4. bidirectional_range

A bidirectional_range has all capabilities of a forward_range and additionally supports:

• moving backward as well as forward

A bidirectional_range is also a forward_range.

5. random_access_range

A random_access_range has all capabilities of a bidirectional_range and additionally supports:

• constant‑time jumps to any position
• indexing with r[i]

A random_access_range is also a bidirectional_range.

6. contiguous_range

A contiguous_range has all capabilities of a random_access_range and additionally guarantees that its elements occupy adjacent addresses in the program’s abstract address space.

When the range is not empty, and for any iterator it that refers to a real element (not end()), the following holds:

::std::to_address(it) + 1 == ::std::to_address(it + 1)

This expresses contiguity using iterators, without dereferencing.

A contiguous_range is also a random_access_range.

7. output_range (separate branch)

An output_range is the writable counterpart of an input_range. It allows writing elements but does not require reading from the range.

It is not part of the readable hierarchy. It forms its own branch under range.

Some ranges are readable only, some writable only, and some support both.

8. Detecting range categories with if constexpr

Range categories are compile‑time properties. You can detect them using if constexpr and the standard concepts.

void analyze_vector(::fast_io::vector& v)
{
    if constexpr(::std::ranges::contiguous_range<decltype(v)>)
        print("vector is a contiguous range\n");

    if constexpr(::std::ranges::random_access_range<decltype(v)>)
        print("vector is a random_access range\n");

    if constexpr(::std::ranges::bidirectional_range<decltype(v)>)
        print("vector is a bidirectional range\n");

    if constexpr(::std::ranges::forward_range<decltype(v)>)
        print("vector is a forward range\n");

    if constexpr(::std::ranges::input_range<decltype(v)>)
        print("vector is an input range\n");

    if constexpr(::std::ranges::output_range<decltype(v), int>)
        print("vector is an output range for int\n");
}

Because a contiguous_range satisfies all weaker readable categories, multiple lines will print.

9. Category summary for the ranges introduced so far

All ranges introduced so far behave as contiguous ranges:

• ::fast_io::vector
• ::fast_io::string
• ::fast_io::array
• ::fast_io::span
• ::fast_io::string_view
• ::fast_io::cstring_view
• ::fast_io::index_span
• C‑style arrays

Later chapters will introduce ranges that are not contiguous.

Key takeaways

• range is the root concept.
• The readable hierarchy goes from input_range up to contiguous_range.
• output_range is a separate writable branch.
• Each stronger readable category includes all weaker ones.
• Contiguous ranges guarantee adjacent addresses in the abstract address space.
• All ranges introduced so far are contiguous.