Intervals in C ++, part 2: Infinite intervals
In the previous post, we tried to shove intervals with delimiters in the STL, and made sure that the result leaves much to be desired. Now we will try to do it at infinite intervals in order to come to a similar conclusion. But this exercise will direct us to the concept of super-intervals, which will include intervals with limiters, and infinite, and pairs of iterators resembling STLs.
The need for infinite intervals to justify a little more difficult. C ++ programmers rarely encounter infinities. In other languages, it happens all the time. In Haskell, you can create an infinite list of integers by simply typing [1 ..]. This is just a “lazy list”, elements in which are created on demand. All infinite intervals are lazy.
What can it be needed for? Suppose in an algorithm that builds a new list of N first elements of another. Or you want to “glue” an endless list with a finite one. Then you get the final list of pairs of items. This is a completely normal practice.
')
It would be cool to have support for endless lists in a general library.
You can think of infinite intervals as intervals with delimiters, where the constraint condition always returns false. Remembering this, we realize an infinite list of integers, starting with a given number, and ending with "never."
With this list you can do the following:
iota_range - direct interval; that is, its iterators are based on the ForwardIterator model. They contain an integer and a boolean value, which indicates whether the iterator is signal. The iterator begin is not signal, but end is signal. Therefore, they will never be equal, and we will count integers for ages.
However, when working with such an interval, you find out that something is working as expected, but something flies into hyperspace and does not return. A simple example: std :: distance. You should be smart enough not to do the following:
It is less obvious that you should never, in general, ever, transfer such an interval to any binary search algorithm — binary_search, lower_bound, upper_bound, and equal_range. Although iota_range is a sorted direct interval. Binary algorithms divide intervals, and the division of an infinite interval at the output should give an infinite interval. It will take a long time to wait.
Readers of the previous post may have been jarred by the implementation of iota_range :: iterator :: equal. Since iota_range should never stop in its iterations, the termination condition must be constant. Instead, we do the following:
Two checks where they should be zero! Last time, I showed that this leads to undesirable effects in the generated code.
In addition to the problem with infinite loops, there is another one that, unfortunately, exists in the STL. Take my favorite whipping boy std :: istream_iterator. This is an input iterator, so you need to associate a difference_type with it. In the book Elements of Programming, Alexander Stepanov (the father of STL and Generic Programming) talks about it this way:
DistanceType returns an integer type large enough to measure any application sequence of a valid parser.
For istream_iterator, the difference_type will be std :: ptrdiff_t. Consider this code:
The code is valid and logical. He pulls out the characters from the istream, counts them, and gets rid of them. Imagine that sin receives characters from the network, and this code works for several days, receiving billions of characters. What happens if ptrdiff_t is not large enough for the result? Answer: undefined behavior. In practice, it is rubbish, but in principle, anything.
It confuses me a little. The iterator difference_type should be large enough to contain the gap between any two iterators. Since the input streams, in principle, have no boundaries, there is no signed integer large enough for them. We have to admit that the validity of the istream_iterator increment operation is limited by the size of the difference_type, or that the difference_type is set incorrectly.
Infinite intervals are a useful thing, but they have a problem with the way they are currently defined in the STL. Infinite intervals could be forbidden, but the problem is even greater than that. And some of the problems exist today. It is hard to fix the overflow problem of the difference_type in STL (except for asking people to be careful), but you can think about whether the new interface for intervals will not help us.
So far, all the problems that I encountered at intervals with a pair of iterators on the STL principle:
In the next post I will describe the basics of the concept of my new library of intervals, which beats the root of all these problems. Do not switch.
Once again, a small gift to get to the end. Five more tickets with a 30% discount on promotional code Infinite Ranges
UPD: As a fair note, VoidEx corrected the passage about zip. Thank!
Other articles of the cycle
Intervals in C ++, part 1: Intervals with limiters
Intervals in C ++, part 3: we represent incrementors (Iterable)
Intervals in C ++, part 4: to infinity and beyond
Infinite intervals
The need for infinite intervals to justify a little more difficult. C ++ programmers rarely encounter infinities. In other languages, it happens all the time. In Haskell, you can create an infinite list of integers by simply typing [1 ..]. This is just a “lazy list”, elements in which are created on demand. All infinite intervals are lazy.
What can it be needed for? Suppose in an algorithm that builds a new list of N first elements of another. Or you want to “glue” an endless list with a finite one. Then you get the final list of pairs of items. This is a completely normal practice.
')
It would be cool to have support for endless lists in a general library.
Infinite intervals / in STL
You can think of infinite intervals as intervals with delimiters, where the constraint condition always returns false. Remembering this, we realize an infinite list of integers, starting with a given number, and ending with "never."
struct iota_range { private: int i_; public: using const_iterator = struct iterator : boost::iterator_facade< iterator, int const, std::forward_iterator_tag > { private: bool sentinel_; int i_; friend class boost::iterator_core_access; friend struct iota_range; iterator(int i) : sentinel_(false), i_(i) {} bool equal(iterator that) const { return sentinel_ == that.sentinel_ && i_ == that.i_; } void increment() { ++i_; } int const & dereference() const { return i_; } public: iterator() : sentinel_(true), i_(0) {} }; constexpr explicit iota_range(int i = 0) : i_(i) {} iterator begin() const { return iterator{i_}; } iterator end() const { return iterator{}; } constexpr explicit operator bool() const { return true; } }; With this list you can do the following:
// Spew all the ints. WARNING: THIS NEVER ENDS! for( int i : iota_range() ) std::cout << i << 'n'; iota_range - direct interval; that is, its iterators are based on the ForwardIterator model. They contain an integer and a boolean value, which indicates whether the iterator is signal. The iterator begin is not signal, but end is signal. Therefore, they will never be equal, and we will count integers for ages.
What happened on the way to infinity
However, when working with such an interval, you find out that something is working as expected, but something flies into hyperspace and does not return. A simple example: std :: distance. You should be smart enough not to do the following:
iota_range iota; // Oops! auto dist = std::distance(iota.begin(), iota.end()); It is less obvious that you should never, in general, ever, transfer such an interval to any binary search algorithm — binary_search, lower_bound, upper_bound, and equal_range. Although iota_range is a sorted direct interval. Binary algorithms divide intervals, and the division of an infinite interval at the output should give an infinite interval. It will take a long time to wait.
Speed ​​performance
Readers of the previous post may have been jarred by the implementation of iota_range :: iterator :: equal. Since iota_range should never stop in its iterations, the termination condition must be constant. Instead, we do the following:
bool equal(iterator that) const { return sentinel_ == that.sentinel_ && i_ == that.i_; } Two checks where they should be zero! Last time, I showed that this leads to undesirable effects in the generated code.
Possible infinite intervals
In addition to the problem with infinite loops, there is another one that, unfortunately, exists in the STL. Take my favorite whipping boy std :: istream_iterator. This is an input iterator, so you need to associate a difference_type with it. In the book Elements of Programming, Alexander Stepanov (the father of STL and Generic Programming) talks about it this way:
DistanceType returns an integer type large enough to measure any application sequence of a valid parser.
For istream_iterator, the difference_type will be std :: ptrdiff_t. Consider this code:
std::istream& sin = ...; std::istream_iterator<char> it{sin}, end; std::ptrdiff_t dis = std::distance(it, end); The code is valid and logical. He pulls out the characters from the istream, counts them, and gets rid of them. Imagine that sin receives characters from the network, and this code works for several days, receiving billions of characters. What happens if ptrdiff_t is not large enough for the result? Answer: undefined behavior. In practice, it is rubbish, but in principle, anything.
It confuses me a little. The iterator difference_type should be large enough to contain the gap between any two iterators. Since the input streams, in principle, have no boundaries, there is no signed integer large enough for them. We have to admit that the validity of the istream_iterator increment operation is limited by the size of the difference_type, or that the difference_type is set incorrectly.
Preliminary conclusion
Infinite intervals are a useful thing, but they have a problem with the way they are currently defined in the STL. Infinite intervals could be forbidden, but the problem is even greater than that. And some of the problems exist today. It is hard to fix the overflow problem of the difference_type in STL (except for asking people to be careful), but you can think about whether the new interface for intervals will not help us.
So far, all the problems that I encountered at intervals with a pair of iterators on the STL principle:
- spacing with limiters and infinite spans generate bad code,
- they have to model weaker concepts than they could,
- they are difficult to use
- it's very simple to transfer an infinite interval to an algorithm that doesn't digest it,
- intervals that can be infinite or very large can cause an overflow in difference_type.
In the next post I will describe the basics of the concept of my new library of intervals, which beats the root of all these problems. Do not switch.
Once again, a small gift to get to the end. Five more tickets with a 30% discount on promotional code Infinite Ranges
UPD: As a fair note, VoidEx corrected the passage about zip. Thank!
Other articles of the cycle
Intervals in C ++, part 1: Intervals with limiters
Intervals in C ++, part 3: we represent incrementors (Iterable)
Intervals in C ++, part 4: to infinity and beyond
Source: https://habr.com/ru/post/264473/
All Articles