The Ranges Library in C++20: More Details
This post is a cross-post from www.ModernesCpp.com.
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:
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.
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.
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 = {});
When you study the two overloads, you notice that it takes a sortable range R (lines 2 and 4), either given by a begin iterator and end sentinel (line 1) or by a ranges::random_access_range (line 3). The iterator and the range must support random access. Additionally, the overloads take a predicate Comp, and a projection Proj. The predicate Comp uses by default ranges::less, and the projection Proj the identity std::identity. A projection is a mapping of a set into a subset. In C++20, std::ranges::sort does not support execution policies.
What's next?
In my next post, I analyze the overloads of std::ranges::sort deeper and write about projections and sentinels.
?
Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, Marko, G Prvulovic, Reinhold Dr?ge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Animus24, Jozo Leko, John Breland, Louis St-Amour, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Neil Wang, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschl?ger, Alessandro Pezzato, Evangelos Denaxas, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, Eduardo Velasquez, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Matthieu Bolt, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Ralf Holly, Juan Dent, George Liao, and Daniel Ceperley.
Thanks in particular to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, Ralf Abramowitsch, John Nebel, and Mipko.
My special thanks to Embarcadero
My special thanks to PVS-Studio
?
Mentoring Program
My new mentoring program "Fundamentals for C++ Professionals" starts on the 22nd of April. Get more information here: https://bit.ly/MentoringProgramModernesCpp.
Seminars
I'm happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.
Bookable (Online)
German
Standard Seminars (English/German)
Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.
New
Contact Me