C++20-ranges: reuse of a filter view

user_15044781 0
Viewed 202

I do not understand the result of the following code (C++20 compiled with g++-10):

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

int main() {
    using namespace std;
    
    auto v = vector<int>{0,1,2,3,4,5,6,7};
    auto r = v | views::filter([](int n) {return n % 3 == 0;});
    ranges::generate(r,[]() { return 2; });
    auto s = v | views::filter([](int n) {return n % 3 == 0;});
    
    cout << "v: ";
    for(auto x: v) cout << x << " ";
    cout << "\n";

    cout << "r: ";
    for (auto x: r) cout << x << " " ;
    cout << "\n";

    cout << "s: ";
    for (auto x: s) cout << x << " " ;
    cout << "\n";
}

On my machine, the result is:

v: 2 1 2 2 4 5 2 7 
r: 2 
s:

I understand the first (v) and the third lines (s): in v, integers divisible by 3 are replaced by 2 (first line) and thus afterwards no integer is divisible by 3 anymore. Thus the third line is empty.

But why does the second line (r) display a unique value 2 and is different from the third line ???

If I replace the 2 by 3 in the ranges::generate then the result is normal:

v: 3 1 2 3 4 5 3 7 
r: 3 3 3 
s: 3 3 3

Maybe the reason is trivial but I did not find any reason in the documentation...

c++20 c++
1 Answers

You are violating [range.filter.iterator]/1:

Modification of the element a filter_­view​::​iterator denotes is permitted, but results in undefined behavior if the resulting value does not satisfy the filter predicate.

Your predicate here is elements divisible by 3, and you're modifying all of those to be 2 - which does not satisfy the predicate. That's undefined behavior. Don't do that.

In your followup example, you're modifying elements, but they still satisfy the predicate - so this is fine.

The reason this is the case is that filter has to cache its begin() iterator to satisfy the amortized O(1) constant requirement. What ends up happening is that during the generate, the filter looks for the first element that satisfies the predicate (which in this case is the very first element, the 0). That result is cached.

You then overwrite that value to 2, which is no longer divisible by 3, but the filter's begin() still refers to it. Which is why it gets printed.

When you create a new filter, that one doesn't have its begin() cached yet so there's no such issue.

user_20690640
Related