The overview of C++20 Range view
The latest C++ draft at the time of writing incorporated The One Ranges Proposal.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/n4791.pdf
So what is a Range, anyway? The C++ Standard Comittee member, Eric Niebler, summarised it well in this article:
Actually, he summarised it all too well to the point that his code became almost unreadable to an average C++ programmer. One might say, it's practically useless. So this article serves as a quick tutorial for the Range view.
Range is a beefed up Iterator. Just like the Iterator was modeled after a pointer, the Range was modeled after a pair of iterators [begin, end).
The immediate benefit of the Range is the ability to pass a container object directly to your favorite algorithm and it just works. This is because the Containers satisfy the concept of Range.
std::vector v = {1,2,3,4,5} ;
std::ranges::for_each( v,
[]( auto x )
{ std::cout << x ; }
) ;
Or, as its name suggests, Range-based for.
for ( auto x : v )
std::cout << x ;
"But Range-based for has existed since C++11! It was already there!" You might say. Well the C++11's Range-based for didn't have the originally intended power. This is because the Concepts didn't make it into the C++11. Those good-for-nothing standard commitee members couldn't agree on whether The Concept map shall be implicitly generated or not. The same bunch of idiots who couldn't accept char8_t until C++20, blubbing: "but char is the suitable type for representing contiguous raw bytes" blah blah blah.
Now that the Concepts are there, we can finally embrace the full power of Range-based for.
The Range library has a View. A View is a range adaptor. A View is a Range plus extra constraints(some additional members etc).
Suppose we would like to iterate over the aforementioned vector, but backwards.
The C++17 Range-based for is rather useless for this very very simple task. We have to fallback to the C++98 era reverse iterator.
std::for_each( rbegin(v), rend(v),
[]( auto i )
{
std::cout << i ;
} ) ;
Although we have a lambda expression, it doesn't save much of the ugliness.
In C++20, you can simply use reverse_view.
for ( auto i : v | reverse )
std::cout << i ;
Yes. That's it. This very simple, and actually readable code prints "54321". Don't worry. There is absolutely no performance penalty, at all! In this regard, C++ is better than Haskell.
Now, suppose that you would like to iterate over 1 to n. The n is a runtime value, so creating a vector object is rather inefficient.
std::vector<int> v ;
int n ;
std::cin >> n ;
for ( int i = 1 ; i != n+1 ; ++i )
v.push_back(i) ;
Fortunately, C++20 has a iota_view. iota(a, b) creates a range of integers in the interval \(a \leq n < b\) .
int n = 10 ;
for ( auto i : iota( 1, n ) | reverse )
std::cout << i ;
Now, this code prints "987654321".
There are a certainly a lot of numbers. Assume, we would like to get rid of the even numbers so that we only deal with odd numbers. We can use filter_view for that.
for ( auto i : iota(1, 10)
| filter( [](auto x){ return x % 2 == 1 ; } )
)
std::cout << i ;
This prints "13579".
filter(rule) drops elements x whenever the function rule(x) returns false.
Now let's suppose that we have a function is_prime(n) which returns true if n is probably a prime number. I won't go into details on how we can implement is_prime. If you wish to know, search for the Miller–Rabin test.
This code prints all the prime numbers between 1 and 1000.
for ( auto i : iota(1, 1001)
| filter( is_prime )
)
std::cout << i << ', ' ;
This works. But what if you only want the first 10 prime numbers? We can use take_view for that. take(n) takes n elements from the range.
for ( auto i : iota(1)
| filter( is_prime )
| take ( 10 )
)
std::cout << i << ', ' ;
This prints "2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ".
You may have noticed that the code above passes only one argument to iota_view. iota(n) creates a range starting from n and incrementing it indefinitely. That means that if you write a code like this,
for ( auto i : iota(1) )
std::cout << i << '\n' ;
it would print numbers until it overflows and even continues printing overflowed numbers. It's an infinite loop. It never stops.
take_view can stop the execution of such infinite loops by taking n elements from the corresponding range.
for ( auto i : iota(1) | take(10) )
std::cout << i << '\n' ;
This code prints 1 to 10 and stops the loop.
We can use iota_view to write an index loop. Suppose that we would like to iterate over integers from 0 to 100. Traditionally, we would write something like this:
for ( int i = 0 ; i != 101 ; ++i )
... ;
This works. But frankly, I don't want to write the kind of code where I have to manually initialize a variable, check for the loop terminating condition, and increment the variable, all by myself. What I really want is to iterate over an integer range from a to b. You see, I can achieve this just by specifying a and b. You can achieve this with iota(a, b+1).
for ( auto i : iota( 1, 101 ) )
std::cout << i ;
Speaking of an index loop, have you ever heard of the FizzBuzz problem? It goes like this: "Print natural numbers 1 to 100. But for numbers that are multiples of 3, print Fizz instead of that number. For multiples of 5, print Buzz instead. For numbers that are multiples of both 3 and 5, print FizzBuzz."
We have already seen how to write an index loop from 1 to 100. Let's write a function fizzbuzz(n) which takes a number n and returns a string it should print to.
auto fizzbuzz = []( auto n ) -> std::string
{
if ( n % 15 == 0 )
return "FizzBuzz" ;
else if ( n % 3 == 0 )
return "Fizz" ;
else if ( n % 5 = 0 )
return "Buzz" ;
else
return std::to_string(n) ;
}
Now that we have written the function fizzbuzz, we can use transform_view to transform each element in the range into a corresponding string it should print to.
for ( auto msg : iota( 1, 101 )
| transform( fizzbuzz )
)
std::cout << msg << '\n' ;
Isn't this fantastic?
Finally, you can combine as many views as you like. You can iota it, filter it, transform it, take it, then reverse it.
for ( auto i : iota(1)
| filter(filter_rule)
| transform(transfrom_rule)
| take(n)
| reverse
)
std::cout << i << '\n' ;
You can add even more views after the reversal if you really want.
All the standard library's views can be used either through piping function objects
for ( auto n : iota(1, 100) | filter(rule) | reverse )
std::cout << n ;
or as a _view class.
iota_view i( 1, 100 ) ;
filter_view f( i, rule ) ;
reverse_view r( f ) ;
for ( auto n : r )
std::cout << n ;
Both codes do the same thing. Basically, "A | B(args)" corresponds to a view object of "B_view( A, args )".
There are other views such as split_view which splits the range into a range of a range separated by a specific value.
auto str = "quick brown fox" ;
std::vector< std::string > words ;
for ( auto word : str | split(' ') )
words.emplace_back( begin(word), end(word) ) ;
After the execution, the words become {"quick", "brown", "fox"}
Another example is join_view which flattens a range of a range to a range.
std::string flat ;
for ( auto c : words | join )
flat.push_back(c) ;
The flattened result is "quickbrownfox".
All the example code above assumes that we use the following using declarations.
using namespace std::ranges ;
using namespace std::ranges::view ;
So how do we write a view? Well, that's rather difficult if you want to write a standard library quality view. But let's try.
Let's write a drop_view which drops n elements from a range.
for ( auto i : iota(0, 10) | drop(5) )
std::cout << i ;
This code prints "56789".
Here is the implementation.
template < InputRange V >
requires View<V>
class drop_view : public view_interface< dropVieww<V> >
{
V base_ = V() ;
iterator_t<V> iter = begin(base_) ;
iter_difference_t<iterator_t<V>> count_ ;
public :
drop_view() = default ;
constexpr drop_view( V base, iter_difference_t<iterator_t<V>> count )
: base_(base), iter( std::next( begin(base_), count ) ), count_(count)
{ }
template < ViewableRange R >
requires Constructible< R, all_view<R> >
constexpr drop_view( R && base, iter_difference_t<iterator_t<V>> count )
: base_(std::forward<R>(base)), iter( std::next( begin(base_), count ) ), count_(count)
{ }
constexpr V base() const
{ return base_ ; }
constexpr auto begin()
{ return iter ; }
constexpr auto begin() const
{ return iter ; }
constexpr auto end()
{ return end(base_) ; }
constexpr auto end() const
{ return end(base_) ; }
constexpr auto size()
requires SizedRange<V>
{ return size(base_) - count_ ; }
constexpr auto size() const
requires SizedRange<const V>
{ return size(base_) - count_ ; }
template < Range R >
drop_view( R &&, iter_difference_t<iterator_t<V>> )
-> drop_view< all_view<R> > ;
} ;
// I'm not 100% sure this is the correct way to implement range adaptor object.
// If my interpretation of the draft is correct, it should be.
struct drop_range_adaptor_closure_object
{
std::size_t count ;
drop_range_adaptor_closure_object( std::size_t count )
: count(count)
{ }
template < ViewableRange R >
constexpr auto operator( R && r )
{
return drop_view( std::forward<R>(r), count ) ;
}
} ;
struct drop_range_adaptor_object
{
template < ViewableRange R >
constexpr auto operator () ( R && r, iter_difference_t<iterator_t<R>> count )
{
return drop_view( std::forward<R>(r), count ) ;
}
constexpr auto operator () ( std::size_t count )
{
return drop_range_adaptor_closure_object( count ) ;
}
} drop ;
template < ViewableRange R >
constexpr auto operator | ( R && r, drop_range_adaptor_closure_object a )
{
return a(std::forward<R>(r)) ;
}
Phew, that's Eric Niebler-level of boilerplateness. I think we need to wait for the metaclass to eliminate the boilerplate code. Hopefully, we can have the metaclass within another decade.