本の虫

著者:江添亮
ブログ: http://cpplover.blogspot.jp/
メール: boostcpp@gmail.com
Twitter: https://twitter.com/EzoeRyou
GitHub: https://github.com/EzoeRyou

アマゾンの江添のほしい物リストを著者に送るとブログ記事のネタになる

筆者にブログのネタになる品物を直接送りたい場合、住所をメールで質問してください。

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:

Eric Niebler – Eric Niebler

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.