ranges::view::transform produces an InputIterator preventing the use of std::prev

Question

Consider the following code, which uses the Ranges library from C++20:

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

int main()
{
    std::vector<int> v{0,1,2,3,4,5,6,7};

    auto transformed = std::ranges::views::transform(v, [](int i){ return i * i; });

    std::cout << *std::prev(std::end(transformed));
}

I was quite surprised to learn that (at least under GCC-10.3.0 and GCC-12.0.0) this code gets stuck in std::prev.

What happens is that since the lambda doesn't return an lvalue reference, the transformed range iterators are classified as input iterators (see the rules for iterator_category selection for views::transform). However, std::prev requires the iterator to be at least a bidirectional iterator, so I guess this code is actually UB. In libstdc++ applying std::prev to an input iterator leads to this function

template<typename _InputIterator, typename _Distance>
__advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
{
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_assert(__n >= 0);
    while (__n--)
        ++__i;
}

being called with __n == -1, which explains the observed behavior.

If we replace std::prev with manual iterator decrement, everything works fine. Switching to std::ranges::prev works, too.

Now, it is clearly nonsensical that I can't do std::prev on what is just a view over an std::vector. While a simple solution exists, I feel extremely worried about this unexpected interplay between old and new range manipulation parts of the standard library. So, my question is: is this a known problem, and should I really forget everything not in the std::ranges namespace when working with the new ranges, and rewrite all the existing code to make sure they work with the new ranges?

It's not actually clear whether std::prev requires a bidirectional iterator or not: cplusplus.github.io/LWG/issue3197 — Jonathan Wakely
– Jonathan Wakely, Commented Jul 12 at 8:57
I actually have good reasons to not enforce that it only works with Cpp17BidirectionalIterator types. I want std::prev to work with C++20 bidirectional iterators which don't meet Cpp17BidirectionalIterator reqs. The prototype patch at gcc.gnu.org/pipermail/gcc-patches/2025-July/689975.html fixes your transform example so it works. — Jonathan Wakely
– Jonathan Wakely, Commented Jul 18 at 18:15
With GCC trunk the example now runs and gives the expected results: wandbox.org/permlink/vCJTK1hJExegX0Kc — Jonathan Wakely
– Jonathan Wakely, Commented Aug 19 at 9:13

Nicol Bolas · Accepted Answer · 2021-07-17 13:30:09Z

16

It is not a random-access-iterator by C++17's reckoning. transform must return a value rather than a reference, and C++17's iterator categories don't allow that for anything above an InputIterator.

But this type is a std::random_access_iterator by C++20's rules, which allow proxy-like iterators on any iterator/range below contiguous.

std::prev is a pre-C++20 tool, so it works by pre-C++20 rules. If you need to work with C++20 rules, you have to use the C++20 equivalent: std::ranges::prev.

Now, it is clearly nonsensical that I can't do std::prev on what is just a view over an std::vector.

No, it is necessary. C++20's conceptualized iterator categories are less restrictive than those from previous C++ versions. This means that there are iterators that cannot be used in pre-C++20 code which can be used in C++20 ranges-based code.

This is why we have new functions for these things in the ranges namespace.

edited Jul 17, 2021 at 13:30

answered Jun 23, 2021 at 13:46

Nicol Bolas

481k66 gold badges861 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Timo Over a year ago

Do you, by any chance, know of a resource that summarizes the differences between the concepts and the old requirements? Maybe also with a rationale behind the changes.

lisyarus Over a year ago

@Timo Very interested in this as well, I'm a little worried about blindly changing all std::X to std::ranges::X in my codebase.

Nicol Bolas Over a year ago

@lisyarus: You shouldn't "blindly" do anything. You should do what makes sense for your code. If you're using C++20 ranges/iterators in some piece of code, then that code needs to use C++20 algorithms with them, as C++20 ranges/iterators may not work in older pre-C++20 code.

lisyarus Over a year ago

@NicolBolas Of course, this was an exaggeration. What I'm saying is that I didn't know about this incompatibilities between pre-C++20 iterators & C++20 ranges, and would like to see some comprehensive differences overview / migration guide (as opposed to, say, reading through the entire corresponding standard sections).

Caleth · Accepted Answer · 2021-06-23 13:44:57Z

5

Your transform returns a prvalue, so it can't be anything other than a InputIterator. That's one of the main reasons that the iterator categories have been changed in C++20.

If the return value of your operation is a reference, then you can.

answered Jun 23, 2021 at 13:44

Caleth

66k2 gold badges53 silver badges101 bronze badges

Collectives™ on Stack Overflow

ranges::view::transform produces an InputIterator preventing the use of std::prev

2 Answers 2

4 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related