Wrap algorithms in iterators

Hello dear readers. Today is Friday, and we have on-board intense review and analysis of new C ++, preferably taking into account C ++ 17. During this exciting lesson we came across the blog of Jacek Galovits (Jacek Galowicz). Of the relatively fresh materials, we especially liked the article posted under the cut.

It happens that you need to generate a range of numbers from an algorithm. Whether it is a range of numbers, simply arranged in ascending order, or only odd numbers, or just prime numbers, etc. Some operations can be optimized by memorizing the values ​​for calculating the next number, exactly as is done with Fibonacci numbers . In this article, I will tell you how to wrap such calculations in iterators so that powerful, beautifully encapsulated algorithms are obtained.

Fibonacci numbers

The number of Fibonacci numbers is widely known. The generation of these numbers is a classic example of recursion, but, at least in standard imperative languages, the iterative version is more powerful:
')

size_t fib(size_t n) { size_t a {0}; size_t b {1}; for (size_t i {0}; i < n; ++i) { const size_t old_b {b}; b += a; a = old_b; } return b; } 

Thus it is very easy to generate any Fibonacci number. But if to solve a problem, you need to generate all Fibonacci numbers up to a certain limit, this solution can no longer be called convenient. When calculating the Fibonacci number N and then N+1 , the contents of the variables a and b could be reused, since each Fibonacci number is the sum of the two previous numbers of the same series.

In this case, it would be convenient to have a class that controls a certain Fibonacci state in order to use it to quickly get exactly the next number.

Many of us would simply implement the fibonacci_number class with some next() method, current() method - and use it. This, of course, is good, but I propose to take another step and recall: after all, this is how iterators work. By implementing this functionality in the language of iterators, it can be used in combination with STL, greatly enhancing the readability of the code.

Iterators

What needs to be done to implement the simplest possible iterator?

This is what the C ++ compiler has for us if we want to iterate over the container class:

 for (const auto &item : vector) { /*   */ } 

Such a cycle declaration has existed since the days of C ++ 11. The compiler will make the following equivalent code from it:

 { auto it (std::begin(vector)); auto end (std::end(vector)); for (; it != end; ++it) { const auto &item (*it); /*   */ } } 

We look at the extended cycle - and see what needs to be implemented. First, we need to distinguish two types of objects: vector is an iterative range , and it is an iterator .

The iterated range must implement the begin() and end() functions. These functions return iterator objects.

Note: in the example code, it returns not vector.begin () and vector.end (), but std::begin(vector) and std::end(vector) . These STL functions do call vector.begin () and end (), but they are more versatile, that is, also applicable with raw arrays and automatically do what they need to get the initial and final iterators.

Here is what should be implemented in the class iterator :

• operator *, performing pointer dereference (pointers are also full iterators!)
• ++ operator (prefix) that increments the iterator to the next element
• the! = operator, necessary to check whether the loop should be completed — that is, whether it has reached the position indicated at the end .

To implement any algorithmically generated range, first we need to make an iterator, which, in essence, hides the variables and the algorithm itself in the implementation of operator++ . Then, the iterated class will simply provide the starting and ending iterators, thus providing C ++-style for loops.

 class iterator { // ...   ... public: //  iterator& operator++() { /*  */ return *this; } T operator*() const { /*     */ } bool operator!= const (const iterator& o) { /*   */ } } 

The simplest iterator in the world is countable; it simply wraps the integer variable, wraps it in operator ++, and returns an integer in operator* . operator!= then simply compare this number with a number from another iterator.
And now for the Fibonacci iterator.

Fibonacci iterator

 class fibit { size_t i {0}; size_t a {0}; size_t b {1}; public: constexpr fibit() = default; constexpr fibit(size_t b_, size_t a_, size_t i_) : i{i_}, a{a_}, b{b_} {} size_t operator*() const { return b; } constexpr fibit& operator++() { const size_t old_b {b}; b += a; a = old_b; ++i; return *this; } bool operator!=(const fibit &o) const { return i != oi; } }; 

With this iterator, it is already possible to iterate over Fibonacci numbers:

 fibit it; //       "i", //     ,   "i"   // 20,      const fibit end {0, 0, 20}; while (it != end) { std::cout << *it << std::endl; ++it; } //       STL: (  <iterator>) std::copy(it, end, std::ostream_iterator<size_t>{std::cout,"\n"}); 

For everything to be beautiful, as in C ++ 11, we need an iterable class:

 class fib_range { fibit begin_it; size_t end_n; public: constexpr fib_range(size_t end_n_, size_t begin_n = 0) : begin_it{fibit_at(begin_n)}, end_n{end_n_} {} fibit begin() const { return begin_it; } fibit end() const { return {0, 0, end_n}; } }; 

And now you can write ...

 for (const size_t num : fib_range(10)) { std::cout << num << std::endl; } 

... and display the first 10 Fibonacci numbers

What does the fibit_at function fibit_at ? This is the constexpr function constexpr , if possible, advances the Fibonacci iterator at compile time, so that it reaches the Fibonacci number that the user needs:

 constexpr fibit fibit_at(size_t n) { fibit it; for (size_t i {0}; i < n; ++i) { ++it; } return it; } 

For example, this function allows you to sort the numbers in the Fibonacci series from the hundredth to the hundred and fifth without needing to calculate the first 100 Fibonacci numbers at run time, since we can prepare the necessary starting position already at compile time.

When working with C ++ 17, fibit_at useless, since it can be replaced by std::next(fibit{}, n) , since in C ++ 17 STLstd::next is a function of constexpr .

To ensure that the 100th number in the Fibonacci series is already calculated when the compiler writes a binary program to disk, you can simply add a range to the constexpr variable:

 constexpr const fib_range hundred_to_hundredfive {105, 100}; for (size_t num : hundred_to_hundredfive) { //  - } 

We combine the Fibonacci iterator with STL algorithms

Suppose we need a vector with the first 1000 Fibonacci numbers. We have already wrapped the Fibonacci algorithm into a convenient iterator class, and now we can use it with any STL algorithm from the std:

 std::vector<size_t> fib_nums; fib_nums.resize(1000); constexpr const fib_range first1000 {1000}; std::copy(std::begin(first1000), std::end(first1000), std::begin(fib_nums)); 

Very nice and comfortable. However, the code as presented here will not compile because we did not specify an iterator label. This is done simply: let fibit explicitly inherit std::iterator<std::forward_iterator_tag, size_t> .

std::iterator , being the base for our fibit class, will simply add a few type definitions that will help the STL algorithms figure out what this iterator is. For iterators of a certain type in specific situations, there are other implementations of STL algorithms, whose performance is optimized (this is neatly hidden from the user!).

The std::forward_iterator means that we have an iterator, which can be simply advanced step by step - and it will only move forward, but not backward.

Results

Many algorithms that generate numeric ranges can be implemented as iterators, which is completely natural. In C ++, there is delicious syntactic sugar for iterators, making them organic interfaces for abstractions.

Together with the STL algorithms and any STL-compatible data structures, they make readable, powerful code that is easy to test and maintain.

The article talks about the iterator, and not the usual data pointer. The implementation of the algorithm is interesting because at the increment stage something more complicated is computed than the new position of the internal pointer to the next element. Interestingly, this way you can instantiate some iterated object that defines the range - and this requires serious calculations. But they will not be executed until someone specifically requests a result (and the code requesting the result does not even “know” which algorithm is implicitly executed, since this information is hidden behind a simple iterator interface).

This style is associated with lazy computing - this is a powerful and beautiful principle from purely functional programming languages.