Overview of C++20: Ranges
Posts in "Overview of C++20"
π Disclaimers:
- The idea of this overview is self-education.
- The main goal - keep it simple and short.
❗ There is no guarantee that below theoretical and practical parts are correkt and up-to-date π
Introduction
Looking back at the advantages of the iterator pattern - easy, robust, efficient, flexible. It is better than directly manipulating the underlying data
structures, but still not as elegant as you would like it to be. How often have you written begin and end by now? Probably not enough yet to be fed up with it, but enough to get the point - it is needlessly tedious. And that is where C++20's ranges come in.
#include <algorithm>
#include <iostream>
#include <vector>
#include <range/v3/action/sort.hpp>
#include <range/v3/algorithm/copy.hpp>
#include <range/v3/view/all.hpp>
int main()
{
{ // Before
std::vector<int> data{2, 5, 4, 1, 3};
std::sort(begin(data), end(data));
std::copy(begin(data), end(data), std::ostream_iterator<int>(std::cout, " "));
}
std::cout << std::endl;
{ // Now
std::vector<int> data{2, 5, 4, 1, 3};
ranges::action::sort(data);
std::cout << ranges::views::all(data);
}
}
// >_ 1 2 3 4 5
// [1,2,3,4,5]So what is the range? Range is an object referring to a sequence of elements. It is a powerful extra layer of abstraction on top of iterators that provides a nicer and easier to read syntax.
Ranges library is based on 3 main components:
- Views
- Actions
- Algorithms
C++20's ranges are based on the range-v3 library from Eric Niebler. Only a small part of that library (the core part) was adopted into C++20. Thus, all below
theoretical and practical parts will be based on range-v3 library.
If you want to test current examples, please use Wandbox or Godbolt with the latest GCC or Clang + -std=c++20.
Views
Views are ranges with
- "lazy evaluation" (means that transformation is applied at the moment you request element(s), not when the view is created);
- non-owning and non-mutating of elements;
- constant time for moving, destruction, and copying (if copying is at all possible).
Enough theory π We need more practice. Let's split a string to the vector of words using ranges:
#include <iostream>
#include <string>
#include <range/v3/algorithm.hpp>
#include <range/v3/view.hpp>
int main()
{
const std::string input = "What is a Bitcoin? Bitcoin is a decentralized digital currency - "
"is a type of money that is completely virtual.";
std::stringstream sin{input};
auto words = ranges::getlines(sin, ' ')
| ranges::views::transform([](const auto &word) { // "Bitcoin?"
return ranges::views::all(word) // ['B','i','t','c','o','i','n','?']
| ranges::views::trim(std::not_fn(::isalpha)) // ['B','i','t','c','o','i','n']
| ranges::views::transform(::tolower) // ['b','i','t','c','o','i','n']
| ranges::to<std::string>; // "bitcoin"
})
| ranges::views::filter([](const auto &word) {
return !word.empty(); }) // because " - " is an empty string after transforming
| ranges::to_vector;
std::cout << ranges::views::all(words) << std::endl;
}
// >_ [what,is,a,bitcoin,bitcoin,is,a,decentralized,digital,currency,is,a,type,of,money,that,is,completely,virtual]
Also, note that only two includes are used - algorithm.hpp and view.hpp. They contain all headers for appropriate submodules. I make use of them for simplicity in some examples. In real project you should include what you use!
Actions
Actions are ranges which are
- eagerly evaluated;
- mutating the data in place;
- can be composed as views.
Continuing the previous example, let's sort the resulting words and apply few more actions:
#include <iostream>
#include <string>
#include <range/v3/action.hpp>
#include <range/v3/algorithm.hpp>
#include <range/v3/view.hpp>
int main()
{
const std::string input = "What is a Bitcoin? Bitcoin is a decentralized digital currency - "
"is a type of money that is completely virtual.";
// auto words = ...
const auto filtered = std::move(words)
| ranges::actions::sort
| ranges::actions::unique
| ranges::actions::remove_if([](const auto &word) { return word.size() < 5; });
std::cout << ranges::views::all(filtered) << std::endl;
}
// >_ [bitcoin,completely,currency,decentralized,digital,money,virtual]
Algorithms
There is nothing complex here! Ranges library has all the STL algorithms with overloads that accept ranges, in addition to the familiar overloads that take iterators.
#include <iostream>
#include <range/v3/algorithm/for_each.hpp>
#include <range/v3/numeric/accumulate.hpp>
#include <range/v3/view/iota.hpp>
#include <range/v3/view/transform.hpp>
void Print(const int n) {
std::cout << n << ' ';
}
int main()
{
const auto sequence = ranges::views::ints(1, 11)
| ranges::views::transform([](const auto i) { return i * i; });
ranges::for_each(sequence, Print);
std::cout << std::endl << ranges::accumulate(sequence, 0);
}
// >_ 1 4 9 16 25 36 49 64 81 100
// 385
Projection
Ranges algorithms support an extra feature called projection. In short, this allows us to modify the values coming from the container and/or pass those projected values to the algorithm.
Let's assume we have a simple Employee class:
class Employee
{
public:
Employee(const std::string &name, const uint16_t age)
: m_name{name}
, m_age{age}
{}
auto getName() const noexcept { return m_name; }
auto getAge() const noexcept { return m_age; }
private:
std::string m_name;
uint16_t m_age;
};
Also, there is a list of employees what must be sorted by age. We can do it by using at least 3 methods:
#include <iostream>
#include <vector>
#include <range/v3/algorithm/for_each.hpp>
#include <range/v3/action/sort.hpp>
class Employee{ /* ... */ };
void Print(const Employee &employee) {
std::cout << employee.getName() << ", " << employee.getAge() << " y.o.\n";
};
int main()
{
std::vector<Employee> employees = {{"Jason", 30}, {"Julia", 25}, {"John", 20}};
// 1. OK (C++17):
// std::sort(begin(employees), end(employees), [](const Employee &one, const Employee &another) {
// return one.getAge() < another.getAge();
// });
// 2. Good (C++20):
// ranges::sort(employees, std::less<>{}, [](const Employee &employee) { return employee.getAge(); });
// 3. Perfect (C++20):
ranges::sort(employees, std::less<>{}, &Employee::getAge);
ranges::for_each(employees, Print);
}
// >_ John, 20 y.o.
// Julia, 25 y.o.
// Jason, 30 y.o.The optional projection parameter can be a pointer to a (parameterless) member function, or to a (public) member variable.
Advanced Example
In the last example we are going to write a program that prints the calendar for 2021:
#include <iostream>
#include <string>
#include <vector>
#include <range/v3/algorithm.hpp>
#include <range/v3/action.hpp>
#include <range/v3/view.hpp>
bool IsLeap(const int year) {
return (year % 400 == 0) || (year % 4 == 0 && year % 100 != 0);
}
int FirstWeekdayOf(const int year) {
return (1 + 5 * ((year - 1) % 4) + 4 * ((year - 1) % 100) + 6 * ((year - 1) % 400)) % 7;
}
const auto kMonths = {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
int main()
{
using namespace ranges;
constexpr int year = 2021;
const auto firstWeekday = FirstWeekdayOf(year); // 5 which is Fri, because Sun is 0
auto daysPerMonth = views::ints(1, 8) // [1,2,3,4,5,6,7]
| views::cycle | views::take(12) // [1,2,3,4,5,6,7,1,2,3,4,5]
| views::transform([](auto n) { return n % 2 + 30; }) // [31,30,31,30,31,30,31,31,30,31,30,31]
| to_vector;
daysPerMonth[1] -= IsLeap(year) ? 1 : 2; // [31,28,31,30,31,30,31,31,30,31,30,31]
const auto firstWeekdaysPerMonth = views::concat(
views::single(firstWeekday),
daysPerMonth
| views::partial_sum(std::plus<>{}) // [31,59,90,120,151,181,212,243,273,304,334,365]
| views::drop_last(1) // [31,59,90,120,151,181,212,243,273,304,334]
| views::transform([firstWeekday](auto n) {
return (firstWeekday + n) % 7; }) // [1,1,4,6,2,4,0,3,5,1,3]
); // [5,1,1,4,6,2,4,0,3,5,1,3]
for (const auto [month, days, firstWeekday] : views::zip(kMonths, daysPerMonth, firstWeekdaysPerMonth)) {
// {Jan, 31, 5}, {Feb, 28, 1}, {Mar, 31, 1}, ...
std::cout << '\n' << month << "\n Sun Mon Tue Wen Thu Fri Sat\n";
std::cout << (views::repeat_n(' ', 4 * firstWeekday) | to_string);
auto weeks = views::zip(
views::ints(1, days + 1), // [1,2,3,4,5,...,27,28,29,30,31]
views::ints(firstWeekday, firstWeekday + days) // [5,6,7,8,9,...,31,32,33,34,35]
| views::transform([](auto weekday) { return weekday % 7; }) // [5,6,0,1,2,...,1,2,3,4,5,6,0]
) | views::group_by([](auto lhs, auto rhs) {
return get<1>(lhs) < get<1>(rhs); }); // [
// [{1,5},{2,6}],
// [{3,0},{4,1},{5,2},{6,3},{7,4},{8,5},{9,6}]
// ...
// ]
for (auto week : weeks) {
for (const auto [day, weekday] : week) {
std::cout << ((day < 10) ? " " : " ") << day;
}
std::cout << "\n";
}
}
}
// >_ Jan
// Sun Mon Tue Wen Thu Fri Sat
// 1 2
// 3 4 5 6 7 8 9
// 10 11 12 13 14 15 16
// 17 18 19 20 21 22 23
// 24 25 26 27 28 29 30
// 31
//
// Feb
// Sun Mon Tue Wen Thu Fri Sat
// 1 2 3 4 5 6
// 7 8 9 10 11 12 13
// 14 15 16 17 18 19 20
// 21 22 23 24 25 26 27
// 28
//
// ...
Summary
It is definitely an elegant and major feature that brings C++ to the next level πͺ It only remains for us to wait a bit when all ranges components will be merged into the standard library.
Sources
- A little bit of code [C++20 Ranges]
- A Plan for C++23 Ranges
- Range-v3 User Manual
- CppCon 2019: Jeff Garland “From STL to Ranges: Using Ranges Effectively”
- Horton I., Van Weert P. - Beginning C++20. From Novice to Professional, 6th edition - 2020; Chapter 20, Ranges and Views
Comments
Post a Comment