The Ranges Library in C++20: More Details

Contents[Show]

Thanks to the ranges library, working with the Standard Template Library (STL) is much more comfortable and powerful. The algorithms of the ranges library are lazy, can work directly on the container, and can easily be composed. But there is more to it:

 

TimelineCpp20

Before I make my deep dive into the ranges library in C++20. I want to recap in a few sentences the three main features of the ranges: The algorithms of the ranges can directly operate on the container, evaluate their arguments lazily, and can be composed. 

Direct on the Container

The classical algorithms of the Standard Template Library (STL) are sometimes a little inconvenient. They need a begin and an end iterator. This is often more than you want to write.

// sortClassical.cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main()  {

    std::vector<int> myVec{-3, 5, 0, 7, -4};
    std::sort(myVec.begin(), myVec.end());     // (1)
    for (auto v: myVec) std::cout << v << " "; // -4, -3, 0, 5, 7

}

 

Wouldn't it be nice if std::sort (line 1) could be executed on the entire container? Thanks to the ranges library, this is possible in C++20.

 

// sortRanges.cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main()  {

    std::vector<int> myVec{-3, 5, 0, 7, -4};
    std::ranges::sort(myVec);                  // (1)
    for (auto v: myVec) std::cout << v << " "; // -4, -3, 0, 5, 7

}

 

std::ranges::sort (line 1) operates directly on the container

Lazy Evaluation

std::views::iota is a range factory for creating a sequence of elements by successively incrementing an initial value. This sequence can be finite or infinite. The elements of the range factory are only created when needed.
 
// lazyRanges.cpp

#include <iostream>
#include <ranges>

int main() {
                                    
    
    std::cout << "\n";

    for (int i: std::views::iota(1'000'000, 1'000'010)) {     // (1)
        std::cout << i << " ";  
    }

    std::cout << "\n\n";
                                         
    for (int i: std::views::iota(1'000'000)                   // (2)
                | std::views::take(10)) {
        std::cout << i << " ";  
    }

    std::cout << "\n\n";

    for (int i: std::views::iota(1'000'000)                  // (3)
                | std::views::take_while([](auto i) { return i < 1'000'010; } )) {
        std::cout << i << " ";  
    }

    std::cout << "\n\n";

}

 

The small program shows the difference between creating a finite data stream (line 1), and an infinite data stream (lines 2, and 3). When you create an infinite data stream, you need a boundary condition. Line (2) uses the view std::views::take(10), and line 3 the view std::views::take_while. std::views::take_while requires a predicate. This is an ideal fit for a lambda expression:  [](auto i) { return i < 1'000'010; }. Since C++14, you can use single quotes as separators in integer literals: 1'000'010. All three std::views::ranges calls produce the same numbers.

lazyRanges

I already used the pipe operator (|) in this example for function composition. Let's go one step further.

Function Composition

The following program primesLazy.cpp creates the first ten prime numbers starting with one million.

// primesLazy.cpp

#include <iostream>
#include <ranges>


bool isPrime(int i) {
    for (int j=2; j*j <= i; ++j){
        if (i % j == 0) return false;
    }
    return true;
}

int main() {
                                        
    std::cout << '\n';
                                         
    auto odd = [](int i){ return i % 2 == 1; };

    for (int i: std::views::iota(1'000'000) | std::views::filter(odd) 
                                            | std::views::filter(isPrime) 
                                            | std::views::take(10)) {
        std::cout << i << " ";  
    }

    std::cout << '\n';

}

 

You have to read the function composition from left to right: I create an infinite data stream starting with 1'000'000 (std::views::iota(1'000'000)) and apply two filters. Each filter needs a predicate. The first filter let the odd element pass (std::views::filter(odd)), and the second filter let the prime numbers pass (std::views::filter(isPrime)). To end the infinite data stream, I stop after 10 numbers (std::views::take(10)).  Finally, here are the first ten prime numbers starting with one million.

primesLazy

You may ask: Who starts the processing of this data pipeline? Now, it goes from right to left. The data sink (std::views::take(10)) want to have the next value and ask, therefore, its predecessor. This request goes on until the range-based for-loop as the data source can produce one number.

This was my short recap. When you want to read more about the ranges library, read my previous posts:

Now, it's time to write about something new.

std Algorithms versus std::ranges Algorithms

The algorithms of the algorithm library and the memory libray have ranges pendants. They start with the namespace std::ranges. The numeric library does not have a ranges pendant. Now, you may have the question: Should I use the classical std algorithm or the new std::ranges algorithm.

Let me start with a comparison of the classical std::sort and the new std::ranges::sort. First, here are the various overloads of std::sort and std::ranges::sort.

 

template< class RandomIt >
constexpr void sort( RandomIt first, RandomIt last );

template< class ExecutionPolicy, class RandomIt >
void sort( ExecutionPolicy&& policy,
           RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr void sort( RandomIt first, RandomIt last, Compare comp );

template< class ExecutionPolicy, class RandomIt, class Compare >
void sort( ExecutionPolicy&& policy,
           RandomIt first, RandomIt last, Compare comp );

 

std::sort has four overloads in C++20. Let's see what I can deduce from the names of the function declarations. All four overloads take a range, given by a begin and end iterator. The iterators must be a random access iterators. The first and third overloads are declared as constexpr and can, therefore, run at compile time. The second and fourth overload require an execution policy. The execution policy lets you specify if the program should run sequential, parallel, or vectorized.
 
Additionally, the last two overloads lines 8 and 11 let you specify the sorting strategy. Compare has to be a binary predicate. A binary predicate is a callable that takes two arguments and returns something convertible to a bool
 
I assume my analysis reminded you of concepts. But there is a big difference. The names in the std::sort do not stand for concepts but only for documentation purposes. In std::ranges::sort the names are concepts.
 
template <std::random_access_iterator I, std::sentinel_for<I> S,
         class Comp = ranges::less, class Proj = std::identity>
requires std::sortable<I, Comp, Proj>
constexpr I sort(I first, S last, Comp comp = {}, Proj proj = {});

template <ranges::random_access_range R, class Comp = ranges::less, 
          class Proj = std::identity>
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
constexpr ranges::borrowed_iterator_t<R> sort(R&& r, Comp comp = {}, Proj proj = {});
 

Comments   

0 #1 Alastair 2022-05-23 10:34
The last two code segments are the same, but the text sounds like they should be different.
Quote

Mentoring: Fundamentals for C++ Professionals

English Books

Course: Modern C++ Concurrency in Practice

Course: C++ Standard Library including C++14 & C++17

Course: Embedded Programming with Modern C++

Course: Generic Programming (Templates)

Course: C++ Fundamentals for Professionals

Interactive Course: The All-in-One Guide to C++20

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 8615

Yesterday 5357

Week 8615

Month 58962

All 9999209

Currently are 152 guests and no members online

Kubik-Rubik Joomla! Extensions

Latest comments