396 lines
14 KiB
Markdown
396 lines
14 KiB
Markdown
## Ranges
|
||
<!-- .slide: data-background="#ccc" -->
|
||
|
||
Let's start with simple example:
|
||
|
||
```C++
|
||
int main() {
|
||
auto const ints = {0, 1, 2, 3, 4, 5};
|
||
auto even = [](int i) { return 0 == i % 2; };
|
||
auto square = [](int i) { return i * i; };
|
||
|
||
for (int i : ints | std::views::filter(even) | std::views::transform(square)) {
|
||
std::cout << i << ' ';
|
||
}
|
||
}
|
||
```
|
||
<!-- .element: class="fragment fade-in" -->
|
||
|
||
```C++
|
||
0 4 16
|
||
```
|
||
<!-- .element: class="fragment fade-in" -->
|
||
<!-- .slide: style="font-size: 0.93em" -->
|
||
___
|
||
<!-- .slide: data-background="#ccc" --><!-- .slide: data-background="#ccc" -->
|
||
|
||
## New iterators
|
||
|
||
* <!-- .element: class="fragment fade-in" --> <code>std::ranges::input_range</code>: specifies a range whose iterator type satisfies input_iterator (can iterate from begin to end at least once)
|
||
* <!-- .element: class="fragment fade-in" --> <code>std::ranges::output_range</code>: specifies a range whose iterator type satisfies output_iterator
|
||
* <!-- .element: class="fragment fade-in" --> <code>std::ranges::forward_range</code>: specifies a range whose iterator type satisfies forward_iterator (can iterate from begin to end more than once)
|
||
* <!-- .element: class="fragment fade-in" --> <code>std::ranges::bidirectional_range</code>: specifies a range whose iterator type satisfies bidirectional_iterator (can iterate forward and backward more than once)
|
||
* <!-- .element: class="fragment fade-in" --> <code>std::ranges::random_access_range</code>: specifies a range whose iterator type satisfies random_access_iterator (can jump in constant time to an arbitrary element with the index operator [])
|
||
* <!-- .element: class="fragment fade-in" --> <code>std::ranges::contiguous_range</code>: specifies a range whose iterator type satisfies contiguous_iterator (elements are stored consecutively in memory)
|
||
|
||
<!-- .slide: style="font-size: 0.95em" -->
|
||
___
|
||
<!-- .slide: data-background="#ccc" --><!-- .slide: data-background="#ccc" -->
|
||
|
||
## Improvements for iterators
|
||
|
||
Whenever we iterate through value, we need to check if we reach the end. But We can provide an optimization, which avoids comparing `it != end`. We can do this by passing `std::unreachable_sentinel`. This sentinel always returns `false` when compared, that's why the compiler can optimize the process. **but be careful** if you provide wrong input, like searching numbers which don't exist in acontainer you got `Segmentation fault`.
|
||
|
||
```C++
|
||
int main() {
|
||
std::vector<int> vec = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
|
||
std::ranges::shuffle(vec, std::mt19937(std::random_device()()));
|
||
std::cout << *std::ranges::find(vec.begin(), std::unreachable_sentinel, 5) << '\n';
|
||
// change this for 10 and you got Segmentation fault
|
||
}
|
||
```
|
||
<!-- .slide: style="font-size: 0.95em" -->
|
||
|
||
see <a href="https://eel.is/c++draft/unreachable.sentinel">unreachable.sentinel</a>
|
||
<!-- .element: class="fragment fade-in" -->
|
||
___
|
||
<!-- .slide: data-background="#ccc" --><!-- .slide: data-background="#ccc" -->
|
||
|
||
## More improvements - predicates
|
||
|
||
Whenever you wanted to sort structure based on the class member you need to provide a special comparator:
|
||
|
||
```C++
|
||
struct Student {
|
||
int index_;
|
||
std::string name_;
|
||
double average_;
|
||
};
|
||
|
||
int main() {
|
||
std::vector<Student> students{{.index_ = 123456, .name_ = "Jordan", .average_ = 4.53},
|
||
{.index_ = 654321, .name_ = "Michael", .average_ = 4.51},
|
||
{.index_ = 246892, .name_ = "John", .average_ = 4.56},
|
||
{.index_ = 743561, .name_ = "Jane", .average_ = 4.44},
|
||
{.index_ = 811111, .name_ = "Anna", .average_ = 4.46}};
|
||
|
||
std::sort(begin(students), end(students), [](const auto& lhs, const auto& rhs){
|
||
return lhs.average_ < rhs.average_;
|
||
});
|
||
|
||
for (const auto& [index, name, average] : students) {
|
||
std::cout << "student: " << name << " | index: " << index << " | avergae: " << average << '\n';
|
||
}
|
||
/* student: Jane | index: 743561 | avergae: 4.44
|
||
student: Anna | index: 811111 | avergae: 4.46
|
||
student: Michael | index: 654321 | avergae: 4.51
|
||
student: Jordan | index: 123456 | avergae: 4.53
|
||
student: John | index: 246892 | avergae: 4.56 */
|
||
}
|
||
```
|
||
<!-- .slide: style="font-size: 0.74em" -->
|
||
___
|
||
<!-- .slide: data-background="#ccc" --><!-- .slide: data-background="#ccc" -->
|
||
|
||
Now you can write it much faster!:
|
||
|
||
```C++
|
||
struct Student {
|
||
int index_;
|
||
std::string name_;
|
||
double average_;
|
||
};
|
||
|
||
int main() {
|
||
std::vector<Student> students{{.index_ = 123456, .name_ = "Jordan", .average_ = 4.53},
|
||
{.index_ = 654321, .name_ = "Michael", .average_ = 4.51},
|
||
{.index_ = 246892, .name_ = "John", .average_ = 4.56},
|
||
{.index_ = 743561, .name_ = "Jane", .average_ = 4.44},
|
||
{.index_ = 811111, .name_ = "Anna", .average_ = 4.46}};
|
||
|
||
// container, comparator, projection
|
||
std::ranges::sort(students, {}, &Student::average_);
|
||
|
||
for (const auto& [index, name, average] : students) {
|
||
std::cout << "student: " << name << " | index: " << index << " | avergae: " << average << '\n';
|
||
}
|
||
}
|
||
```
|
||
<!-- .slide: style="font-size: 0.80em" -->
|
||
|
||
All magic is done by the new parameter `projection`. It points to address to member and use it to provide a comparison: `std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it))`
|
||
<!-- .element: class="fragment fade-in" -->
|
||
___
|
||
<!-- .slide: data-background="#ccc" --><!-- .slide: data-background="#ccc" -->
|
||
|
||
## View
|
||
|
||
Here is a quote from Eric Nieblers range-v3 implementation which is the base for the C++20 ranges: "Views are composable adaptations of ranges where the adaptation happens lazily as the view is iterated." In other words: `view` is not an owner of range. So we don't need to copy/move elements, only perform some action. Only exception is a `std::views::single` which owns the single element it is viewing.
|
||
<!-- .element: class="fragment fade-in" -->
|
||
|
||
Let's use `Foo` which prints whenever we create/ copy/ move or delete him.
|
||
<!-- .element: class="fragment fade-in" -->
|
||
|
||
<div class="multicolumn">
|
||
<div class="col">
|
||
|
||
```C++
|
||
int main() {
|
||
auto even = [](const auto& el) { return !(el.id() % 2); };
|
||
std::vector<Foo> vec {Foo{1}, Foo{2}, Foo{3}, Foo{4}};
|
||
|
||
std::cout << "Start algorithm\n";
|
||
for (const auto& foo : vec
|
||
| std::views::filter(even)
|
||
| std::views::drop_while([](const auto& el){ return el.id() < 4; })) {
|
||
std::cout << "foo: " << foo << '\n';
|
||
}
|
||
}
|
||
```
|
||
We don't make any copy!
|
||
</div>
|
||
<!-- .element: class="fragment fade-in" -->
|
||
<div class="col">
|
||
|
||
```C++
|
||
C'tor id: 1
|
||
C'tor id: 2
|
||
C'tor id: 3
|
||
C'tor id: 4
|
||
Copy C'tor id: 1
|
||
Copy C'tor id: 2
|
||
Copy C'tor id: 3
|
||
Copy C'tor id: 4
|
||
D'tor id:4
|
||
D'tor id:3
|
||
D'tor id:2
|
||
D'tor id:1
|
||
Start algorithm
|
||
foo: 4
|
||
D'tor id:1
|
||
D'tor id:2
|
||
D'tor id:3
|
||
D'tor id:4
|
||
```
|
||
</div>
|
||
<!-- .element: class="fragment fade-in" -->
|
||
<!-- .slide: style="font-size: 0.74em" -->
|
||
___
|
||
<!-- .slide: data-background="#ccc" --><!-- .slide: data-background="#ccc" -->
|
||
|
||
## View (2)
|
||
|
||
This is also usefull to create `range loop` which iterate reversed:
|
||
|
||
```C++
|
||
int main() {
|
||
std::vector<Student> students{{.index_ = 123456, .name_ = "Jordan", .average_ = 4.53},
|
||
{.index_ = 654321, .name_ = "Michael", .average_ = 4.51},
|
||
{.index_ = 246892, .name_ = "John", .average_ = 4.56},
|
||
{.index_ = 743561, .name_ = "Jane", .average_ = 4.44},
|
||
{.index_ = 811111, .name_ = "Anna", .average_ = 4.46}};
|
||
|
||
std::ranges::sort(students, {}, &Student::average_);
|
||
|
||
for (const auto& [index, name, average] : std::views::reverse(students)) {
|
||
std::cout << "student: " << name << " | index: " << index << " | avergae: " << average << '\n';
|
||
}
|
||
/*
|
||
student: John | index: 246892 | avergae: 4.56
|
||
student: Jordan | index: 123456 | avergae: 4.53
|
||
student: Michael | index: 654321 | avergae: 4.51
|
||
student: Anna | index: 811111 | avergae: 4.46
|
||
student: Jane | index: 743561 | avergae: 4.44
|
||
*/
|
||
}
|
||
```
|
||
<!-- .slide: style="font-size: 0.80em" -->
|
||
___
|
||
<!-- .slide: data-background="#ccc" --><!-- .slide: data-background="#ccc" -->
|
||
|
||
## View (3)
|
||
|
||
We can also create `range loop` which iterates only through the first/last `k` elements:
|
||
|
||
```C++
|
||
int main() {
|
||
std::vector<Student> students{{.index_ = 123456, .name_ = "Jordan", .average_ = 4.53},
|
||
{.index_ = 654321, .name_ = "Michael", .average_ = 4.51},
|
||
{.index_ = 246892, .name_ = "John", .average_ = 4.56},
|
||
{.index_ = 743561, .name_ = "Jane", .average_ = 4.44},
|
||
{.index_ = 811111, .name_ = "Anna", .average_ = 4.46}};
|
||
|
||
std::ranges::sort(students, {}, &Student::average_);
|
||
|
||
for (const auto& [index, name, average] : std::views::reverse(students) | std::views::drop(3)) {
|
||
std::cout << "student: " << name << " | index: " << index << " | avergae: " << average << '\n';
|
||
}
|
||
/* student: Anna | index: 811111 | avergae: 4.46
|
||
student: Jane | index: 743561 | avergae: 4.44 */
|
||
|
||
for (const auto& [index, name, average] : std::views::reverse(students) | std::views::take(3)) {
|
||
std::cout << "student: " << name << " | index: " << index << " | avergae: " << average << '\n';
|
||
}
|
||
/* student: John | index: 246892 | avergae: 4.56
|
||
student: Jordan | index: 123456 | avergae: 4.53
|
||
student: Michael | index: 654321 | avergae: 4.51 */
|
||
}
|
||
```
|
||
<!-- .slide: style="font-size: 0.80em" -->
|
||
|
||
___
|
||
<!-- .slide: data-background="#ccc" --><!-- .slide: data-background="#ccc" -->
|
||
|
||
## std::map
|
||
|
||
```C++
|
||
int main() {
|
||
std::map<int, std::string> map{{1, "One"}, {2, "Two"}, {3, "Three"}, {4, "Four"}};
|
||
auto odd = [](const auto& el) { return el % 2; };
|
||
|
||
for (auto el : std::views::keys(map) | std::views::filter(odd)) {
|
||
std::cout << el << ' ';
|
||
}
|
||
std::cout << '\n';
|
||
|
||
for (const char c : map | std::views::values | std::views::join) {
|
||
std::cout << c << ' ';
|
||
}
|
||
}
|
||
```
|
||
<!-- .element: class="fragment fade-in" -->
|
||
|
||
```C++
|
||
1 3
|
||
O n e T w o T h r e e F o u r
|
||
```
|
||
<!-- .element: class="fragment fade-in" -->
|
||
<!-- .slide: style="font-size: 0.74em" -->
|
||
___
|
||
<!-- .slide: data-background="#ccc" --><!-- .slide: data-background="#ccc" -->
|
||
|
||
## C++23 and further
|
||
|
||
Ranges library based on `Ranges V3`. Unfortunately, in C++20 there is a lack of useful things like creating cycles or zip functions. In C++23 there will be a few more operations like `zip` or `join_with`:
|
||
|
||
```C++
|
||
int main() {
|
||
auto x = std::vector{1, 2, 3, 4};
|
||
auto y = std::list<std::string>{"α", "β", "γ", "δ", "ε"};
|
||
auto z = std::array{'A', 'B', 'C', 'D', 'E', 'F'};
|
||
|
||
/* 1 α A
|
||
2 β B
|
||
3 γ C
|
||
4 δ D */
|
||
for (const auto& [num, grec, alpha] : std::views::zip(x, y, z)) {
|
||
std::cout << num << ' ' << grec << ' ' << alpha << '\n';
|
||
}
|
||
|
||
std::map<int, std::string> map{{1, "One"}, {2, "Two"}, {3, "Three"}, {4, "Four"}};
|
||
auto ends_with_e = [](const auto& el) { return el.back() == 'e'; };
|
||
const auto joined = std::views::values(map) | std::views::filter(ends_with_e) | std::views::join_with(' ');
|
||
/* Two Four */
|
||
for (const auto& el : joined) {
|
||
std::cout << el;
|
||
}
|
||
}
|
||
```
|
||
<!-- .slide: style="font-size: 0.74em" -->
|
||
___
|
||
<!-- .slide: data-background="#ccc" --><!-- .slide: data-background="#ccc" -->
|
||
|
||
## actions (C++23)
|
||
|
||
There is a proposal to extend ranges in C++23 to allow easy convert range to container (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p1206r6.pdf)
|
||
|
||
```C++
|
||
int main() {
|
||
std::map<int, std::string> map{
|
||
{1, "Hello"}, {2, "Abcd"}, {3, "Hello"}, {4, "Aaa"}, {5, "Ala"}, {6, "Abcd"}};
|
||
|
||
// Since C++23
|
||
for (const auto& el : map
|
||
| std::views::values
|
||
| std::ranges::to<std::vector> // Since C++23
|
||
| std::ranges::sort
|
||
| std::ranges::unique) {
|
||
std::cout << el << '\n';
|
||
}
|
||
}
|
||
```
|
||
|
||
```C++
|
||
Aaa
|
||
Abcd
|
||
Ala
|
||
Hello
|
||
```
|
||
<!-- .element: class="fragment fade-in" -->
|
||
<!-- .slide: style="font-size: 0.88em" -->
|
||
___
|
||
<!-- .slide: data-background="#ccc" --><!-- .slide: data-background="#ccc" -->
|
||
|
||
## actions (C++26)
|
||
|
||
In C+26 we should get also `operator|=`.
|
||
|
||
<div>
|
||
Before C++26
|
||
|
||
```C++
|
||
int main() {
|
||
std::vector<std::string> vec{"Hello", "Abcd", "Hello", "Aaa", "Ala", "Abcd"};
|
||
|
||
std::ranges::sort(vec);
|
||
auto ret = std::ranges::unique(vec);
|
||
vec.erase(ret.begin(), ret.end());
|
||
}
|
||
```
|
||
</div>
|
||
<!-- .element: class="fragment fade-in" -->
|
||
<div>
|
||
In C++26
|
||
|
||
```C++
|
||
int main() {
|
||
std::vector<std::string> vec{"Hello","Abcd", "Hello", "Aaa", "Ala", "Abcd"};
|
||
vec |= std::ranges::sort | std::ranges::unique;
|
||
}
|
||
```
|
||
</div>
|
||
<!-- .element: class="fragment fade-in" -->
|
||
<!-- .slide: style="font-size: 0.88em" -->
|
||
___
|
||
<!-- .slide: data-background="#ccc" --><!-- .slide: data-background="#ccc" -->
|
||
|
||
## Exercise 1
|
||
|
||
Open project `searcher` and implement function `searchFiles` which returns all files containing `keyWord`.
|
||
|
||
Possible output:
|
||
<!-- .element: class="fragment fade-in" -->
|
||
```C++
|
||
"C:\\Users\\mateusz\\Documents\\Nokia2022\\Basic\\Course_part1\\exercises\\searcher/files\\fileA.hpp"
|
||
"C:\\Users\\mateusz\\Documents\\Nokia2022\\Basic\\Course_part1\\exercises\\searcher/files\\fileC.hpp"
|
||
```
|
||
<!-- .element: class="fragment fade-in" -->
|
||
___
|
||
<!-- .slide: data-background="#ccc" --><!-- .slide: data-background="#ccc" -->
|
||
|
||
## Exercise 2
|
||
|
||
Open project `students`:
|
||
|
||
* implement function `filterStudents`,
|
||
* Student should be disqualified whether his average is below `minAvergae`,
|
||
* Write an algorithm that prints students using ranges (do not implement friend operator<<)
|
||
|
||
Output:
|
||
<!-- .element: class="fragment fade-in" -->
|
||
```C++
|
||
Name: Jane | index: 743561 | average: 4.44
|
||
Name: Tom | index: 811111 | average: 4.36
|
||
Name: Mike | index: 811111 | average: 4.45
|
||
```
|
||
<!-- .element: class="fragment fade-in" -->
|