Skip to content

Ranges, views and pipes

[Ranges – basic example]
[More on using pipe operator]
[Algorithms of the range library]
[sort: simplifications with use of ranges]
[iota: an infinite number factory]

Ranges – basic example

Situation: You have several baskets each containing any number of colored stones. You are interested on those baskets containing a minimum number of red stones. The algorithms to find those baskets use the concept of ranges.

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

enum class Color {RED, GREEN, BLUE, YELLOW};

struct Basket
{
    int id = 0;
    std::vector<Color> coloredStones;
};
using Baskets = std::vector<Basket>;

// We have 5 baskets each containing some colored stones
Baskets myBaskets{
    {.id = 1, .coloredStones = {Color::RED, Color::GREEN, Color::RED} },
    {.id = 2, .coloredStones = {Color::BLUE, Color::GREEN, Color::RED} },
    {.id = 3, .coloredStones = {Color::YELLOW, Color::BLUE, Color::RED, Color::RED} },
    {.id = 4, .coloredStones = {Color::YELLOW, Color::YELLOW, Color::RED, Color::BLUE} },
    {.id = 5, .coloredStones = {Color::RED, Color::GREEN, Color::RED, Color::RED} },
};

Basic function to check a single basket:

// Result containing counted values
struct BasketResult
{
    int id = 0;
    int numRedStones = 0;
};

BasketResult CountRedStones(const Basket& basket)
{
    return { basket.id,
        std::count_if(basket.coloredStones.begin(), basket.coloredStones.end(),
            [](Color color) {return color == Color::RED; }) };
}

Here is the complete function to find the baskets:

auto FindBasketsWithRedStones(const Baskets & allBaskets, int minimumNumberOfRedStones)
{
    return allBaskets
        | std::views::transform(CountRedStones) // generates BasketResults with counted results
        | std::views::filter([minimumNumberOfRedStones](const BasketResult& basketResult) {
            return basketResult.numRedStones >= minimumNumberOfRedStones; });
}

The main program putting all together:

int main()
{
    // Find the baskets containing at least the given number of red stones
    auto basketResults2 = FindBasketsWithRedStones(myBaskets, 2);
    auto basketResults3 = FindBasketsWithRedStones(myBaskets, 3);

    // ATTENTION: Because of lazy evaluation CountRedStones() has NOT YET been called here!

    std::cout << "Baskets containing at least 3 red stones:\n";
    for (auto r : basketResults3)
    {
        std::cout << r.id << "-" << r.numRedStones << " (r has type " << typeid(r).name() << ")\n";
    }

    std::cout << "\nbasketResults3 has type " << typeid(basketResults3).name() << "\n";

    std::cout << "\nBaskets containing at least 2 red stones:\n";
    for (auto r : basketResults2)
    {
        std::cout << r.id << "-" << r.numRedStones << "\n";
    }

    // ATTENTION: Because of lazy evaluation iterating a second time over the
    // same results causes a second search, i.e. CountRedStones() will be called again here!
    std::cout << "\nSecond iteration triggering new search:\n";
    for (auto r : basketResults2)
    {
        std::cout << r.id << "-" << r.numRedStones << "\n";
    }
}

Here is the program’s output:

Baskets containing at least 3 red stones:
5-3 (r has type struct BasketResult)

basketResults3 has type class std::ranges::filter_view<class std::ranges::transform_view<class std::ranges::ref_view<class std::vector<struct Basket,class std::allocator<struct Basket> > const >,struct BasketResult (__cdecl*)(struct Basket const &)>,class `__cdecl FindBasketsWithRedStones(class std::vector<struct Basket,class std::allocator<struct Basket> > const &,int)'::`2'::<lambda_1> >

Baskets containing at least 2 red stones:
1-2
3-2
5-3

Second iteration triggering new search:
1-2
3-2
5-3

Description

  • the pipe operator “|” uses a function’s output range as input range for the next function
    (instead of nested calls “f(g(h(someData)))” you can simply write “someData | h | g | f”)
  • “transform” calls CountRedStones for each basket of the container and generates result objects
  • “filter” selects those results which fulfill some criterion
  • transform and filter are views operating on the range with lazy evaluation
  • Lazy evalution: the result of the function FindBasketsWithRedStones() is not just a vector of calculated BasketResults but a view (see the complex type within program output). The calculation will be delayed until the results are used for output. Possible disadvantage: A second usage of the results repeats the whole calculation!
  • this is an example of functional programming (no state, no side effects, decomposing a problem into functions)

Functional programming in a nutshell

  • Functions shall be pure, i.e. they do not change some state and they always have the same result when they are called with the same input data.
  • Advantage: easier to parallelize, no need to synchronize access to some shared state
  • Higher-order functions take other functions as arguments, these functions can be regular functions, function objects (classes with operator()()) or lambdas. A function returning a function is also a high-order function.
  • Currying (named after Haskell Curry): split a function taking several arguments into several functions each taking a single argument.
  • Folding: combining a collection of values to a reduced number of results (in most cases a single result). Example: std::accumulate
  • Head recursion: execute the recursive call before processing the result at the current step, needs big stack size depending on the number of recursions
  • Tail recursion: process result of current step before the recursive call, may be optimized with a compiler’s option for Tail Call Optimization (TCO), the stack size can remain the same size independent of the number of recursive calls.
  • Using functional programming the whole application can be decomposed into a big assembly line of functions.

Examples for views

  • std::views::filter
    Returns the elements that satisfy the predicate
  • std::views::transform
    converts/changes each element
  • std::views::reverse
    iterates in reverse order
  • std:views::elements
    uses the n-th element of tuples
  • std::views::keys
    uses the first element of pair-like values
    e.g. std:views::keys(someMap) returns the keys stored in the map
  • std::views::values
    uses the second element of pair-like values
    e.g. std:views::values(someMap) returns the values stored in the map
  • std::views::take
    returns the first N elements
  • std::views::drop
    skip the first N elements

More on using pipe operator

Some helper methods used within the following example:

#include <algorithm>
#include <iostream>
#include <numeric> // iota
#include <ranges>
#include <vector>

class NumGenerator;
using Numbers = std::vector<int>;
using NumGeneratorSp = std::shared_ptr<NumGenerator>;
using NumGenerators = std::vector<NumGeneratorSp>;

// Demo class providing a vector of numbers.
// The member function GetNumbers() will be used within range/pipe examples below. 
class NumGenerator
{
public:
	NumGenerator(int in_numEntries, int in_startVal)
		:
		m_numEntries(in_numEntries),
		m_startVal(in_startVal)
	{}

	Numbers GetNumbers() const
	{
		Numbers nums(m_numEntries);
		// Fill with increasing numbers starting with m_startVal
		std::ranges::iota(nums, m_startVal);
		return nums;
	}

private:
	int m_numEntries{};
	int m_startVal{};
};

// Generate a vector of three different number generators
NumGenerators MakeNumGenerators()
{
	return {
		std::make_shared<NumGenerator>(4, 0),
		std::make_shared<NumGenerator>(2, 20),
		std::make_shared<NumGenerator>(3, 100)
	};
}

// Streaming a vector with enclosing "[..]" brackets
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec)
{
	os << "[";
	MyUtils::join(vec, os, ",");
	os << "]";
	return os;
}

Several examples using pipe operator:


auto multiplyWith2 = [](int i) {return i * 2; };
auto dividableBy4 = [](int i) {return i % 4 == 0; };

auto nums1 = MakeNumGenerators()                           // {spNumGen1, spNumGen2, spNumGen3}
	| std::views::transform(&NumGenerator::GetNumbers) // {{0,1,2,3}, {20,21}, {100,101,102}}
	| std::ranges::to<std::vector>();                  // => vector containing 3 vectors of int
std::cout << "nums1=" << nums1 << std::endl;

auto nums2 = MakeNumGenerators()
	| std::views::transform(&NumGenerator::GetNumbers)
	| std::views::join                                 // {0,1,2,3,20,21,100,101,102}
	| std::ranges::to<std::vector>();                  // => flat vector containing int
std::cout << "nums2=" << nums2 << std::endl;

auto nums3 = MakeNumGenerators()
	| std::views::transform(&NumGenerator::GetNumbers)
	| std::views::join_with(-10)                       // {0,1,2,3,-10,20,21,-10,100,101,102}
	| std::ranges::to<std::vector>();
std::cout << "nums3=" << nums3 << std::endl;

auto nums4 = MakeNumGenerators()
	| std::views::transform(&NumGenerator::GetNumbers)
	| std::views::join_with(-10)                       // {0,1,2,3,-10,20,21,-10,100,101,102}
	| std::views::transform(multiplyWith2)             // {0,2,4,6,-20,40,42,-20,200,202,204}
	| std::ranges::to<std::vector>()                   // reverse needs preceding conversion to vector
	| std::views::reverse                              // {204,202,200,-20,42,40,-20,6,4,2,0}
	| std::views::filter(dividableBy4)                 // {204,200,-20,40,-20,4,0}
	| std::ranges::to<std::vector>();
std::cout << "nums4=" << nums4 << std::endl;

Output:

nums1=[[0,1,2,3],[20,21],[100,101,102]]
nums2=[0,1,2,3,20,21,100,101,102]
nums3=[0,1,2,3,-10,20,21,-10,100,101,102]
nums4=[204,200,-20,40,-20,4,0]

Algorithms of the range library

  • the ranges library provides an additional version of the STL algorithms with the following properties:
  • lazy, can be called on infinte data streams (e.g. iota)
  • operate directly on the container (no begin()/end() needed)
  • can be composed using pipe symbol |
  • see also https://en.cppreference.com/w/cpp/algorithm/ranges

sort: simplifications with use of ranges

Instead of calling

std::vector<int> myVec{-4,3,2,5};
std::sort(myVec.begin(), myVec.end());

you can simply write

std::ranges::sort(myVec);

For complex types containing several fields you can use projection to sort with respect to a specific field:

struct Person
{
    std::string name;
    std::string town;
    int age;
};

std::vector<Person> persons = { {"Myers", "London", 57}, {"Meier", "Munic", 46},
                                {"Toscanini", "Milano", 34}};

std::ranges::sort(persons, {}, &Person::name); // ascending by name
std::ranges::sort(persons, std::ranges::greater(), &Person::town); // descending by town
std::ranges::sort(persons, {}, &Person::age); // ascending by age

Most range algorithms support projections.

iota: an infinite number factory

  • std::views::iota(1000)
    retuns an infinite number sequence 1000,1001,1002,…
  • std::views::iota(1000,2000)
    returns the numbers 1000, 1001, 1002, .. ,1999
  • std::views::iota(1000) | std::views:filter([](int i){return i %2 = 0;}) | std::views::take(15)
    returns the 15 even numbers starting with 1000; because of lazy evaluation the infinite number factory iota is asked for the next number only a limited number of times.
  • create a vector of 10 ints 21..30:
    std::vector<int> v(10);
    std::ranges::iota(v,21);