Walletfox.com

Why we can't chain views::split and views::reverse
(Range-v3, Concepts C++20)


This article addresses the general issue of why you cannot directly chain certain views from the Range-v3 library and explains why we occasionally resorted to use intermediate materialization, i.e. an intermediate conversion to an STL container, in the book Fully Functional C++ with Range-v3.

    auto s = std::string{"reverse view requires bidirectional range"};
    auto rng = s | views::split(' ') | views::reverse; // doesn't compile

In theory, from the point of view of an API user, there isn't a reason why we shouldn't be able to chain splitting and reversing. Nevertheless, in C++ high-level customarily interferes with low-level. In this case, the reason for this behavior lies within Concepts introduced by C++20.

Concepts are compile-time requirements on algorithms. To link it to our topic, views::reverse has stricter requirements on the range it acts on, than whatever views::split produces. views::reverse requires a BidirectionalRange while views::split produces at most a ForwardRange. See the scheme below, adjusted from Stepanov's and Rose's From Mathematics to Generic Programming.


To understand this, let's look at a possible implementation of the reverse template function. Notice the need for swapping and for the decrement operator (highlighted). The decrement operator is an additional requirement of the BidirectionalRange, ForwardRange has no such requirement. Hence, ForwardRange produced by views::split won't be accepted by views::reverse and the compiler. A nice overview of this topic can be found in Apache C++ Standard Library User's Guide.

template<class BidirIt>
void reverse(BidirIt first, BidirIt last)
{
    while ((first != last) && (first != --last)) {
        std::iter_swap(first++, last);
    }
}
Note: The presented mechanism is a possible eager STL implementation taken over from cppreference.com, but suffices for the purposes of demonstration.

Tagged: Range-v3