c++language-lawyerstd-rangesc++23

C++23: Is it valid to modify the elements of a `zip_view`?


I am trying to figure out under which circumstances a modifying access to an element of a C++23 range (resp. view) is allowed by the standard.

For example, consider this rather elegant version of sorting two vectors in parallel by the values in one of the vectors:

std::vector<size_t> keys{…};
std::vector<Foobar> values{…};

auto zip = std::ranges::views::zip(keys, values);
std::ranges::sort(zip, [](const auto & lhs, const auto & rhs) {
    return std::get<0>(lhs) < std::get<0>(rhs);
});

This seems to work with the three major compilers resp. library implementations (see Godbolt here). However, that does of course not mean that it's allowed by the standard.

It is clear that there must be views which do not allow modifying their elements. Take for example the std::transform_view - what would it even mean to modify one of its elements?

I'm not sure how the standards specifies which views may have their elements modified and which may not. There is the concept std::ranges::output_range, which in my eyes is the best candidate. However, std::zip_view does not model output_range, if I read cppreference correctly.

So, is my nice vector-sorting thingy above forbidden by the standard and I'm just lucky that the compilers/library implementations still allow it?


Solution

  • In general, it is always valid to modify the elements of any particular view - except in very particular cases (see below). You've gotten a couple answers already, but let me just note this one:

    Take for example the std::transform_view - what would it even mean to modify one of its elements?

    Consider something like:

    struct Point { int x; int y; };
    
    // let's say points is some mutable range of Point
    for (int& x : points | views::transform(&Point::x)) {
        ++x;
    }
    

    That's perfectly valid. We're increasing the x coordinate by one in each Point. There's nothing about transform's requirements that this violates - transform requires only that the callable be "equality-preserving". This means that f(elem) gives the same value every time you call it on a given value. So something like [](Point){ return rand(); } would violate the semantic requirements, but [](Point& p) -> int& { return p.x; } is totally fine, as is mutating the resulting p.x.

    Put differently, if this kind of mutation were bad, then that would basically mean that any mutation were bad. And we're definitely allowed to do something like ++*it; in a loop.


    The only case where you are not allowed to (or should at least take care) when mutating elements is for views::filter. This is, fundamentally, a very peculiar adapter - because the combination of laziness, multipass, and mutation could lead to very strange behavior. This is because in the transform example above, we're mutating p.x but we're not changing whether p is in the range at all. But with views::filter (and only views::filter), a mutation could actually remove an element! See my blog mutation through a filter for more info, but the gist of it is that even mutating through a filter is only bad if (a) your mutations move elements out of the range (if all of your mutations are predicate-preserving then there can't be any issues) and (b) you're making multiple passes through the range (either explicitly, like actually writing two for loops, or implicitly, like using algorithms that themselves make multiple passes).


    Outside of filter, mutation is fair game. Indeed, one of the biggest benefits of the C++ iterator model is precisely that you can actually write this:

    std::ranges::sort(std::views::zip(keys, values));
    

    And making that work, especially in such a way as to reject attempts that are nonsensical, was why we had to make these tuple changes.