Why the superfluous calls to filter functions when `std::views::reverse` is used?

user_11057988 0
Viewed 236

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.

c++20 c++
2 Answers

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.
user_46725880

As mentioned in one of comments - the std::views objects are applied lazily on every iterator incrementattion. So doing something like this:

auto view = vec
        | std::views::reverse
        | std::views::filter(filter)
        | std::views::take(2)
        | std::views::reverse

effectivelly does not perform any computations on the range. Only when you iterate over the range the logic within the views is applied. This has some pros - no computations are made when no one uses the data. The drawbacks are like the one you mentioned - counterintuitive number and order of calls and often increased big O complexity.

user_34149000
Related