Ch8.1: Ranges & Range‑Based Algorithms

Overview

A range is any object that provides a beginning and an end. All containers introduced so far — ::fast_io::vector, ::fast_io::string, ::fast_io::array, ::fast_io::span, ::fast_io::string_view, ::fast_io::cstring_view, ::fast_io::index_span, and C‑style arrays — are contiguous ranges.

A range‑based algorithm is an operation that works on an entire range at once. Instead of writing loops manually, you can call functions such as sorting, searching, reversing, copying, or counting.

In this chapter, you will learn:

• what a range is
• how to call range‑based algorithms
• how algorithms work uniformly across containers
• how to customize algorithms with comparators

1. What is a range?

A range is defined by two iterators:

• a beginning iterator
• an ending iterator

Examples of ranges you already know:

::fast_io::vector<int> v{1, 2, 3};
int a[3]{4, 5, 6};
::fast_io::span<int> s{a, 3};
::fast_io::string str{"abc"};
::fast_io::string_view sv{"hello"};

All of these are valid ranges.

2. Sorting a range

The simplest example is sorting:

::fast_io::vector<int> v{3, 1, 2};

::std::ranges::sort(v);   // ascending

To sort in reverse order, use ::std::ranges::greater:

::std::ranges::sort(v, ::std::ranges::greater{});

This works for any range, including C‑style arrays:

int a[5]{5, 1, 4, 3, 2};
::std::ranges::sort(a, ::std::ranges::greater{});

3. Concept‑constrained comparators (<functional>)

C++20 provides standardized comparison function objects in <functional> that work naturally with range algorithms:

• std::ranges::equal_to — x == y
• std::ranges::not_equal_to — x != y
• std::ranges::less — x < y
• std::ranges::less_equal — x <= y
• std::ranges::greater — x > y
• std::ranges::greater_equal — x >= y
• std::compare_three_way — x <=> y

These are concept‑checked, reusable, and avoid generating extra code.

4. Using lambdas as comparators

You can use a lambda as a comparator:

::std::ranges::sort(v, [](int a, int b) noexcept {
    return a > b;
});

Always mark comparator lambdas noexcept. If a comparator throws, the C++ standard requires the program to terminate.

5. Lambdas are clearly not zero‑overhead

Each lambda expression is a unique type, and the compiler generates separate code for each one, even if they look identical:

::std::ranges::sort(v,  [](int a, int b) noexcept { return a > b; });
::std::ranges::sort(v1, [](int a, int b) noexcept { return a > b; });
::std::ranges::sort(v2, [](int a, int b) noexcept { return a > b; });

These three lambdas look the same but produce three different comparator objects and three separate code paths. This increases:

• binary size
• instruction cache pressure
• cold‑start time
• update time
• network transfer size (WASM/PWA)

This overhead becomes much worse when lambdas appear inside templates (which we will introduce later), because templates instantiate separately for each distinct lambda type.

If a standard comparator such as ::std::ranges::greater{} works, you should always prefer it over writing a new lambda.

6. Searching a range

int a[5]{10, 20, 30, 40, 50};

auto it = ::std::ranges::find(a, 30);

if (it != ::std::ranges::end(a)) {
    // found
}

7. Reversing a range

::fast_io::string s{"hello"};

::std::ranges::reverse(s);   // "olleh"

8. Copying a range

int a[3]{1, 2, 3};
int b[3]{};

::std::ranges::copy(a, b);

9. Counting elements

::fast_io::vector<int> v{1, 2, 2, 3};

std::size_t n = ::std::ranges::count(v, 2);  // n = 2

10. Using ::std::ranges::begin and ::std::ranges::end

These functions work for all ranges, including C‑style arrays:

int a[3]{10, 20, 30};

auto first = ::std::ranges::begin(a);
auto last  = ::std::ranges::end(a);

Key takeaways

• A range is defined by a beginning and an end.
• All fast_io containers and C‑style arrays are contiguous ranges.
• Range‑based algorithms operate on entire ranges.
• Algorithms do not depend on container type.
• <functional> provides reusable, concept‑checked comparators.
• std::ranges::greater is preferred over writing a lambda.
• Lambdas are not zero‑overhead because each one generates new code.
• Templates make lambda bloat much worse.
• Comparator lambdas must be noexcept.
• std::ranges::begin and std::ranges::end work for all ranges.