A Gentle Introduction to Ranges v3

layout: true
<div class="footer"><div class="flexcontainer"><span>.body[[https://pem-aachen.de](http://pem-aachen.de)]</span>
<span>.center[C++ User Group Aachen 2018]</span><span>.body[© 2018 Markus Werle ([github](http://github.com/daixtrose) [linkedin](https://www.linkedin.com/in/markus-werle-04305a12a/))]</span></div></div>

---

# A Gentle Introduction to Ranges v3

.accent[
### Say Goodbye to STL the Way You (Probably Don't) Know It
Duration: 1:07:42 (#NoEstimates)
]

]

---

# Hints

.split-50[
.column[
- You can download this talk **and** code samples in the form of unit tests
  - https://github.com/daixtrose/gentle-intro-to-ranges
- Published under MIT licence
 - Code for talk framework based on remark.js was stolen from [Kirk Shoop's Intro to RxCpp](https://github.com/kirkshoop/introductionToRxcpp) 
 - Please contribute fixes or [file an issue](https://github.com/daixtrose/gentle-intro-to-ranges/issues) if you find errors or know about improvements. 
]
.column[
![](images/QRCodeGitRepo.png)
 <br>
 <br>
 <br>
 <br>
]
]

---

# Disclaimer

- This is not "The Complete Guide", but 
  - just a gentle **introduction**
  - a **user's view** (sic!) on ranges
  - focus is more on getting the basic ideas (tutorial) 
]
.column[
![](images/QRCodeGitRepo.png)
]
]

---

# Where do we come from?

---

# Our Starting Point: STL

.split-60[
.column[
- STL is the recommended **C++** way to deal with sets and operations on sets
    - Provides Containers
    - Provides Algorithms
    - Provides Utilities
- STL is generic
- STL makes no compromise: performance first  
- STl requires educated users

> Hint: I am a great fan of the STL and encourage(d) its usage wherever possible.
]
.column[
![](images/EffectiveSTLCover.jpeg) 
]
]

---

# STL Requires Educated Users

**Example**: Scott Meyer's perfect version of a map search and update 
```c++
typename std::map<double>::iterator lb =			
    m.lower_bound(k);

if (lb != m.end() &&						
    !(m.key_comp()(k, lb->first))) {	
    lb->second = v;							
    return lb;								
}										
else {
    typedef typename 
        std::map<double>::value_type MVT;
    return m.insert(lb, MVT(k, v));
}									
```
]
.column[

![](images/EffectiveSTLCover.jpeg) 
 <br>
 <br>
 <br>
 <br>
 <br>
 <br>
 <br>

]
]

---

# A Short History of C++ Ranges

---

# STL: The Crisis

Andrei Alexandrescu: ["Iterators Must Go" (2009)](https://accu.org/content/conf2009/AndreiAlexandrescu_iterators-must-go.pdf), 
Video [here](https://archive.org/details/AndreiAlexandrescuKeynoteBoostcon2009)

## TL;DR:

- STL was built using a rigorous fundamental, academic, generic approach, but 
  - leads to counter-intuitive rules in some places
  - is hard to learn (and hard to remember) 
- Working with data streams is a mess.  
- Algorithms are NOT **composable**.
- Iterators 
  - are so complex, one needs 10 years of education and/or 
  - library help like [Boost.Iterator](https://www.boost.org/doc/libs/1_67_0/libs/iterator/doc/index.html) in order to get things right.

---

# Ranges

- Many attempts/proposals, e.g.
  - [Boost.Range](https://www.boost.org/doc/libs/1_67_0/libs/range/doc/html/index.html) Version 1 and 2
  - Eric Niebler: 3 (!) versions
  
> The rest of the talk deliberately ignores all other attempts 
> and gives an introduction to Eric Niebler's [ranges-v3](https://github.com/ericniebler/range-v3) for C++11/14/17

---

# Eric Niebler's Range-v3

- GitHub Repository at https://github.com/ericniebler/range-v3
- ISO Standard Proposal 
  - https://ericniebler.github.io/std/wg21/D4128.html
  - TS: https://www.iso.org/obp/ui/#iso:std:iso-iec:ts:21425:ed-1:v1:en
  - http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4651.pdf 
- [Explanations about iterators and why we need a sentinel](http://ericniebler.com/2015/02/03/iterators-plus-plus-part-1/)
- [Merging the Ranges TS](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0896r1.pdf) 
  (proposes to merge the Ranges TS into the working draft)

.split-50[
.column[
### October 2014
![](images/NieblerTweet1.PNG) 
]
.column[
### December 2017
![](images/NieblerTweet2.PNG) 
]
]

---

# What are Ranges?

---

# What are Ranges?

![](images/2017-05-07_Niebler_Tweets_1.PNG)

---

# What are Ranges?

![](images/2017-05-07_Niebler_Tweets_2.PNG)

---

# What are Ranges?

![](images/2017-05-07_Niebler_Tweets_3.PNG)

---

# What are Ranges?

```text
¯\_(ツ)_/¯    ¯\_(ツ)_/¯    ¯\_(ツ)_/¯    ¯\_(ツ)_/¯     ¯\_(ツ)_/¯

¯\_(ツ)_/¯    ¯\_(ツ)_/¯    ¯\_(ツ)_/¯    ¯\_(ツ)_/¯     ¯\_(ツ)_/¯

```

---

# What are Ranges?

> The C++ Ranges library is C#'s **LINQ** for C++ - Markus Werle

Ranges in C++ are what `IEnumerable<T>` is in C#. That's why they were also called Iterables.  
C# is a language I struggled with many times because of its unnecessary limitations due to bad language design (esp. generics are multiple inheritance) and 
its limited expressiveness, but 
.split-50[
.column[
### C# got some things right
- Lambdas
- Concurrency esp. `async/await` 
(see Steven Toub's [Concurrency in C# Cookbook](https://www.amazon.com/Concurrency-Cookbook-Asynchronous-Multithreaded-Programming/dp/1449367569)) and `CancellationToken`<br>
- LINQ (`*this` talk)  
- Reactive Extensions (`*this->next()` talk)  
]
.column[
### C++ gotta catch up
- C++17's **generic** lambdas .image-fixed-20[![](images/apply-1293741_960_720.png)]
- `std::async` flawed, but concurrency will evolve (I see a bright `<future>` here, with `coroutines` and more confusion) 
- Ranges converge soon into ISO C++ .image-fixed-20[![](images/apply-1293741_960_720.png)]
- RxCpp will converge during the next years
]
]

---

# What are Ranges?

> C++ Ranges are **Pure Monadic Goodness** - [Bartosz Milewski](https://bartoszmilewski.com/2014/10/17/c-ranges-are-pure-monadic-goodness/)

- **Functional Programming** curiously recurring all the time
- Milewski: A **monad** is an applicative functor with an additional ability, which can be expressed either as a way of flattening a doubly encapsulated object, or as a way of applying a functor factory to an encapsulated object.
- Simply said, it's all about  
  - functions/algorithms (operations on values or sets of values)
  - composition of functions
  - programming without side effects (helps a lot when dealing with concurrency)

---

# What are Ranges?

> Ranges are a contribution to making C++ easier to write and reason about

---

# Ranges by Example

---

# STL vs. Ranges: Transform (LINQ: Select, J*: Map)

```c++
typedef /* ... ? ... */ result_t;

std::vector<result_t> bar;

std::transform (
    `std::begin(foo)`, 
    `std::end(foo)`, 
    `std::back_inserter(bar)`,  
    [](auto const v) { 
        return 2 * v; 
    });
```
]
.column[
### Ranges Approach

```c++

// bar is `lazy` and `composable` 
auto bar =

foo `|` view::transform(

[](auto const v) { 
            return 2 * v; 
        });
```
]
]

---

# STL vs. Ranges: Composition

```c++
auto timesTwo = [](auto const v) { return 2 * v; };
auto plusTen = [](auto const v) { return v + 10; };
```

```c++
auto composition = [=](auto v) { 
    return plusTen(timesTwo(v)); 
});

std::transform (
    std::begin(foo), 
    std::end(foo), 
    std::back_inserter(bar),  
    composition);
```
]
.column[
### Ranges Approach

```c++
// Remember: `lazy`, 
// i.e. optimizer looks through 
auto bar = 
    foo 
    | view::transform(timesTwo)
    | view::transform(plusTen)
    ;
```
]
]

---

# STL vs. Ranges: Composition

```c++
auto timesTwo = [](auto const v) { return 2 * v; });
auto plusTen = [](auto const v) { return v + 10.0; });
```

```c++
auto composition = [](auto v) { 
    return plusTen(timesTwo(v)); 
});

std::transform (
    std::begin(foo), 
    std::end(foo), 
    std::back_inserter(bar),  
    composition);
```
]
.column[
### Ranges Approach (Composition to the Max)

```c++
// Remember: `lazy`, 
// i.e. optimizer looks through 
auto bar = 
    foo | view::transform(timesTwo);
    
auto baz = 
    bar | view::transform(plusTen);
```
]
]

---

# Switching back to STL

```c++
auto bar = 
    foo | view::transform(timesTwo)
    `| to_vector`
    ;
```

```c++
auto bar = 
    /* ... * / 
    | `to_`<std::list>();
```

```c++
auto bar = 
    /* ... * / 
    | to_<std::vector<`long`>>();
```
]
.column[
### Implicit 
```c++
std::vector<result_t> bar = 
    foo | view::transform(timesTwo)
    ;    
```

```c++

std::list<result_t> bar = 
    /* ... * / 
    ;
```

```c++
std::vector<long> bar = 
    /* ... * / 
    ;
```
]]

---

# Switching back to STL with Optimal Runtime Performance

Citation from [Casey Carter's Answer on Stack Overflow](https://stackoverflow.com/questions/47831026/replacing-data-with-range-v3):

```c++
auto b = a | ranges::view::transform(complexFun) | ranges::to_vector;
```

If you already have a destination vector whose capacity you want to reuse:

```c++
b.clear(); // Assuming b already contains junk
b `|=` ranges::action::push_back(a | ranges::view::transform(complexFun));
```

> In both cases, `range-v3` is smart enough to reserve capacity in the destination vector for 
> `ranges::size(a | ranges::view::transform(complexFun))` elements to avoid copies due to reallocation.

---

# Dual Interface: Chainable Pipe Operator vs. Regular Function Call

For most algorithms there exist two `ranges-v3` interfaces:

.split-50[
.column[
```c++
auto bar = foo 
    `|` view::transform(fn);
```
]
.column[
```c++
auto bar = 
    transform(foo, fn);
```
]]

<br>
Some algorithms are not available in the pipe (`|`) form:

```c++
// std::copy(std::begin(v), std::end(v), 
//     std::ostream_iterator<int>(std::cout, ' '));
ranges::copy(v, ranges::ostream_iterator<int>(std::cout, ' ')); 
```

---

# Make a Range out of a Container

```c++
std::vector<double> v;
auto rng = ranges::view::`all`(v);
```

This is useful e.g. for DEBUG output:

```c++
std::vector<double> v;                    
std::cerr << `(` v | ranges::view::`all` `)` << std::endl; 
```

---

# Group_By (LINQ: GroupBy) and Join (LINQ: SelectMany)

```c++
struct Person {
    std::string firstname;
    std::string surname;
    int year;
};

std::ostream & operator<<(std::ostream & os, Person const & person) {
    os << person.surname << ", " << person.firstname 
       << " was born in " << person.year; 
    return os;
}

std::vector<Person> people{
    { "Jared", "Kushner", 1981 }, { "Melania", "Trump", 1970 },
    { "Donald", "Trump", 1946 }, { "Ivana", "Trump", 1949 },
};
```

---

# Group_By (LINQ: GroupBy)

```c++
auto surname_is_equal = [](auto const & p1, auto const & p2) 
    { return p1.surname == p2.surname; };
            
auto groups = people | ranges::view::`group_by`(surname_is_equal);

for (auto const & group : groups) { 
    std::cout << "-------\n";
    copy(group, ostream_iterator<Person>(std::cout, "\n")); 
}
```

```
-------
Kushner, Jared was born in 1981
-------
Trump, Melania was born in 1970
Trump, Donald was born in 1946
Trump, Ivana was born in 1949
```

---

# Join (LINQ: SelectMany)

```c++
auto is_younger = [](auto const & p1, auto const & p2) 
    { return p2.year < p1.year; };

auto each_group_sorted_by_age = groups 
    | transform([`=`](auto g) { 
        `sort`(g, is_younger); // range-v3/issues/266: no view::sorted 
        return /* expensive copy of */ g; });

copy(`join`(each_group_sorted_by_age), 
    ostream_iterator<Person>(std::cout, "\n"));
```

```
--> sorted by age, then joined:
Kushner, Jared was born in 1981
Trump, Melania was born in 1970
Trump, Ivana was born in 1949
Trump, Donald was born in 1946
```

---

# Filtering - By Hand Using Yield_If (C#: Yield)

```c++
std::vector<int> numbers{1, 2, 3, 4, 5, 6};

auto is_odd = [](int i) { return i % 2 != 0; };

using ranges::view::for_each;
using ranges::yield_if;

// odd_numbers is a *lazy* expression, i.e. is_odd 
// will NOT be called in next statement 
auto odd_numbers = `for_each`(numbers, [=](int i) { 
    return `yield_if`(is_odd(i), i);
    });

// now that the expression gets evaluated, is_odd will be called
REQUIRE(ranges::equal(odd_numbers, std::vector<int>{1, 3, 5}));
```

---

# Filtering with Filter and Remove_If (LINQ: Where)

```c++
std::vector<int> numbers{1, 2, 3, 4, 5, 6};

using ranges::view::filter; // ambiguous, but meant positive.
using ranges::view::remove_if;
using ranges::not_fn;

auto is_odd = [](int i) { return i % 2 != 0; };

auto odd_numbers = numbers | `filter`(is_odd);
auto odd_numbers_alt = numbers | `remove_if`(`not_fn`(is_odd));
auto even_numbers = numbers | `remove_if`(is_odd);
```

---

# Set Operations

## Unique (LINQ: Distinct)

Removes duplicate values from a collection. In most libraries, finding duplicates requires a sorted container/enumerable. Same here:

```c++
std::vector<int> numbers{3, 1, 2, 3, 3, 4, 3, 5, 6};

using ranges::action::unique;
using ranges::action::sort;

numbers |= `sort | unique`; 
REQUIRE(equal(numbers, std::vector<int>{1, 2, 3, 4, 5, 6}));

// Instead of in-place treatment you can always explicitly request a copy 
auto numbers_sorted_and_unique = `numbers | copy` | sort | unique;  
```

---

# Set Operations

## Set Difference (LINQ: Except)

Returns the set difference, which means the elements of one collection that do not appear in a second collection.

```c++
std::vector<int> v1{1, 2, 3, 4};
std::vector<int> v2{3, 4, 5};

using ranges::view::set_difference;

auto v = set_difference(v1, v2);

using ranges::equal;
REQUIRE(equal(v, std::vector<int>{1, 2}));
```

---

# Set Operations

## Symmetric Set Difference

The symmetric difference finds the elements that are found in either of the ranges, but not in both of them

```c++
std::vector<int> v1{1, 2, 3, 4};
std::vector<int> v2{3, 4, 5};

using ranges::view::set_symmetric_difference;

auto v = set_symmetric_difference(v1, v2);

using ranges::equal;
REQUIRE(equal(v, std::vector<int>{1, 2, 5}));
```

---

# Set Operations

## Set Intersection (LINQ: Intersect)

Returns the set intersection, which means elements that appear in each of two collections.

```c++
std::vector<int> v1{1, 2, 3, 4};
std::vector<int> v2{3, 4, 5};

using ranges::view::set_intersection;

auto v = set_intersection(v1, v2);

using ranges::equal;
REQUIRE(equal(v, std::vector<int>{3, 4}));    
```

---

# Set Operations

## Set Union (LINQ: Union)

Returns the set union, which means unique elements that appear in either of two collections.

```c++
std::vector<int> v1{1, 2, 3, 4};
std::vector<int> v2{3, 4, 5};

using ranges::view::set_union;

auto v = set_union(v1, v2);

using ranges::equal;
REQUIRE(equal(v, std::vector<int>{1, 2, 3, 4, 5}));
```

---

# Partitioning

## Skip

```c++
// 'skip' is called 'drop' here
auto result = numbers | drop(3);
auto result = numbers | drop_exactly(3);
auto result = numbers | drop_while([](int i) { return i < 4; });
```

## Take

```c++
auto result = numbers | take(3);
auto result = numbers | take_exactly(3);
auto result = numbers | take_while([](int i) { return i < 4; });
```

---

# Generating Sequences

## Empty

C# has `IEnumerable.Empty` (the neutral element of addition). AFAIK ranges-v3 does not contain such a feature.

---

# Generating Sequences

## A Range of Numbers

Stolen from https://github.com/ericniebler/range-v3/blob/master/test/view/iota.cpp
```c++
view::ints | view::take(10)    // -> {0,1,2,3,4,5,6,7,8,9}
view::ints(0) | view::take(10) // -> {0,1,2,3,4,5,6,7,8,9}
view::ints(0,9)                // -> {0,1,2,3,4,5,6,7,8}

view::closed_indices(0,9)      // -> {0,1,2,3,4,5,6,7,8,9}

// l a z y  
auto chars = view::ints(std::numeric_limits<char>::min(),
                        std::numeric_limits<char>::max());
```

---

# Generating Sequences

## Generate

```c++
using ranges::view::generate;
using ranges::view::take;

auto rng = `generate`([`=`]() {
    // ... arbitrary calculation with side effects ... 
    return result;
    });

auto sequence = rng | take(10);
```

---

# Generating Sequences

## Repeat

```c++
using ranges::view::repeat; // i.e. repeat `forever` 
using ranges::view::take;

// {9, 9, 9, 9, 9, 9, 9, 9, 9, 9}
auto rng = view::repeat(9) | view::take(10);
```

---

# Accessing elements

## At

```c++
std::vector<int> vi{1,2,3,4};
CHECK(ranges::index(vi, 0) == 1);
CHECK(ranges::index(vi, 1) == 2);
// etc.

CHECK(ranges::at(vi, 0) == 1);
CHECK(ranges::at(vi, 1) == 2);
// etc.

// Does not compile if random access iterator not available
// std::list<int> li{1,2,3,4};   
// auto rng = li | ranges::view::all;
// CHECK(ranges::at(li, 0) == 1);
```

---

# Accessing elements

## First / First or Default

`AFAIK n.a.` probably use `*begin(rng)`

## Last / Last or Default

`AFAIK n.a.` probably use `*begin(rng | reverse)`

## Single

`AFAIK n.a.`

---

# Maps

Extract the values from a dictionary

```c++
std::map<int, std::wstring> m = 
    { {1, L"1"}, 
      {2, L"2"}, 
      {3, L"3"} };

auto keys = m | ranges::view::reverse | ranges::view::keys;
auto vals = m | ranges::view::reverse | ranges::view::values;
```

---

# Real World Examples

---

# What are Ranges?

> Ranges are a contribution to making C++ easier to write and reason about.

```c++

auto filteredAndInCartesianCoordinates = coordinates
        | remove_if(outsideOfReasonableRange)
        | remove_if(is_inf_or_nan)
        | transform(polarToCartesian)
        | reverse;
```

---

```c++
std::vector<PolarCoordinate>
selectNearestSegmentToAngleZero(
    std::vector<std::vector<PolarCoordinate>> const& segments)
{
    // ... using declaratives omitted ...
    auto average_angle = [](auto&& coordinates) {
        auto angles = coordinates 
            | `transform`([](auto pc) { return pc.angle; });
        auto sumOfAngles = `accumulate`(angles, 0.0);
        auto result = sumOfAngles 
            / static_cast<double>(`size`(coordinates));
        return result;
    };
    auto averageValuesAbs = segments 
        | `transform`(average_angle) // yields a range of average values 
        | `transform`([](auto v) { return std::abs(v); });
    auto index = `distance`(averageValuesAbs.begin(), 
        `min_element`(averageValuesAbs));

return segments[index];
}
```

---

# How I lost my reputation

---

## How I lost my reputation

```c++
std::vector<std::vector<PolarCoordinate>> segments; 
// ---------------------------- Variant 1 ----------------------------------
std::vector<PolarCoordinate> firstSegmentReversed = 
    segments[0] | `transform`(polarToCartesian) | `reverse`;
        
for (auto const& point : firstSegmentReversed) {
    std::cerr << point.first << ", " << point.second << std::endl;
}
// ---------------------------- Variant 2 ----------------------------------
auto segmentsReversedViaNestedTransform = segments
  | `transform`([](auto s) { 
      return s | `transform`(polarToCartesian) | `reverse`; 
    });

for (auto const& point : `*begin`(segmentsReversedViaNestedTransform)) {
    std::cerr << point.first << ", " << point.second << std::endl;
}

```

---

## How I lost my reputation

```c++
std::vector<std::vector<PolarCoordinate>> segments; 
std::vector<PolarCoordinate> firstSegmentReversed = 
        segments[0] | `transform`(polarToCartesian) | `reverse`;
            
for (auto const& point : firstSegmentReversed) {
    std::cerr << point.first << ", " << point.second << std::endl;
}
```
yields
```
2.0944, 29.96
2.08567, 29.96
2.07694, 29.96
2.06821, 29.96
2.05949, 29.96
```

---

## How I lost my reputation

```c++
auto segmentsReversedViaNestedTransform = segments
    | transform([](auto s) { 
        return s | transform(polarToCartesian) | reverse; });

for (auto const& point : *begin(segmentsReversedViaNestedTransform)) {
    std::cerr << point.first << ", " << point.second << std::endl;
}
```
yields
```
2.0944, 29.96
2.08567, 29.96
2.07694, 29.96
2.06821, 29.96
0, 29.96   <------ SOMETHING WRONG         
```

---

## How I lost my reputation

```c++
std::vector<std::vector<PolarCoordinate>> segments; 
auto broken_stuff = segments
  | transform([](auto s) { 
      return s | transform(polarToCartesian) | reverse; 
    });
```

Explanation by [@gnzlbg](https://github.com/gnzlbg):

> `[](auto s) { return s | reverse; }` creates a **dangling view**. 
> The inner vector will be copied into the `s` argument (the lambda stack frame), 
> and `| reverse` creates a view (that is, a pair of pointers) into this local vector. 
> The problem is that this vector will be destroyed on scope exit (freeing the memory), 
> so when the view is returned its pair of pointers into the vector will point 
> into freed memory.
> 
> When you try to iterate the view, you are basically dereferencing these pointers, 
> and that is undefined behavior: read after free.

---

## How I lost my reputation

```c++
std::vector<std::vector<PolarCoordinate>> segments; 
auto segmentsInCartesianCoordinates = segments
  | transform([](auto`&&` s) { 
      return s | transform(polarToCartesian) | reverse; 
    });
```

---

# Dangling References due to Views

```c++
auto doub = [](int i) -> int { return 2 * i; };

int main() {
  auto e = find_if( view::ints(1) | view::transform(doub), is_six );
  cout << "find-six: " << *e.get_unsafe() << endl;
}
```

Prefer this version:

```c++
auto doub = [](int i) -> int { return 2 * i; };

int main() {
  auto candidates = view::ints(1) | view::transform(doub);
  auto e = find_if( candidates, is_six );
  cout << "find-six: " << *e << endl;
}
```

---

# Closing Remarks

---

# Not in this Talk (Same Semantic as STL)

```
adjacent_find, all_of, any_of, binary_search, copy, copy_backward, 
copy_if, copy_n, count, count_if, equal, equal_range, fill, fill_n, 
find, find_end, find_first_of, find_if, find_if_not, for_each, 
for_each_n, generate, generate_n, heap_algorithm, inplace_merge, 
is_partitioned, is_sorted, is_sorted_until, lexicographical_compare, 
lower_bound, max, max_element, merge, min, min_element, minmax, 
minmax_element, mismatch, move, move_backward, none_of, nth_element, 
partial_sort, partial_sort_copy, partition, partition_copy, 
partition_point, permutation, remove, remove_copy, remove_copy_if, 
remove_if, replace, replace_copy, replace_copy_if, replace_if, 
reverse, reverse_copy, rotate, rotate_copy, sample, search, search_n, 
set_algorithm, shuffle, sort, stable_partition, stable_sort, 
swap_ranges, tagspec, transform, unique, unique_copy, upper_bound
```

---

# There's more to come.

> I see a great `std::future<std::ranges>` for `C++`.

## Next talk
.accent[
### Reactive Extensions: Ranges for Values Distributed in Time 
      
]

---

# Thank You for Your Attention

]