Can someone explain superfluous calls to filter functions when `std::views::reverse` is used?

I am trying to understand the sequence of calls to filter functions when passed through pipe operators (views/adapters). The result I see is not intuitive at all. While there might be reasons for it, I’d appreciate if someone can walk this through. As well if one can point to right documentation on cppreference.com.

#include <vector>
#include <ranges>
#include <iostream>

int main() {
    const auto vec = std::vector{1,2,3,4,5,6};
    auto filter = [](const auto f) {
        std::cout << "f = " << f << ", "; 
        return f % 2 == 0;
    };

    std::cout << std::endl;
    for (auto v : vec
        | std::views::reverse
        | std::views::filter(filter)
        | std::views::take(2)
        | std::views::reverse)
    {
        std::cout << std::endl << "v = [" << v << "]" << std::endl;
    }
}

Actual result:

f = 6, f = 5, f = 4, f = 3, f = 2, f = 3, f = 4, 
v = [4]
f = 3, f = 4, f = 5, f = 6, 
v = [6]
f = 5, f = 6, 

Expected result:

f = 6, f = 5, f = 4, f = 3, f = 2, f = 1, 
v = [4]
v = [6]

Here is the godbolt sample for code above. And here is some more code, I tried to break it down to understand. But nothing strikes out as obvious.

Answer

The range-based for loop in question can be rewritten to

auto&& range = vec
    | std::views::reverse
    | std::views::filter(filter)
    | std::views::take(2)
    | std::views::reverse;

auto begin = range.begin();
auto end = range.end();

for (; begin != end; ++begin) {
    auto v = *begin;
    std::cout << std::endl << "v = [" << v << "]" << std::endl;
}
  1. The initializer of range only builds the view. Nothing is outputted.
  2. range.begin() returns a reverse_iterator whose base() is an iterator to the end of the underlying view. In order to find the end of the underlying view, 5 calls to filter are made (corresponding to f = 6, f = 5, f = 4, f = 3, f = 2, ).
  3. range.end() returns a reverse_iterator whose base() is an iterator to the beginning of the underlying view. The beginning of filter_view has been cached. No call to filter is made.
  4. begin != end returns true.
  5. *begin decrements a copy of the underlying base iterator in order to access the first element of the reversed range. This results in the next 2 calls to filter (corresponding to f = 3, f = 4, ).
  6. The value of the first element is outputted. (v = [4])
  7. ++begin decrements the underlying base iterator. (f = 3, f = 4, )
  8. begin != end returns true.
  9. *begin decrements a copy of the underlying base iterator to access the second element. (f = 5, f = 6, )
  10. The value of the second element is outputted. (v = [6])
  11. ++begin decrements the underlying base iterator. (f = 5, f = 6, )
  12. begin != end returns false.

Leave a Reply

Your email address will not be published. Required fields are marked *