Undefined behaviour on std::prev for transform-view

Question

Consider the following code (click here for godbolt):

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

int main() {
    auto v = std::vector<short>{1, 2};
    auto view = v | std::views::transform([] (auto i) { return static_cast<int>(i); });
    auto it = view.begin() + 1;
    auto prev_it = std::ranges::prev(it); //this one is fine
    //auto prev_it = std::prev(it); //this one dies with an infinite loop

    return *prev_it;
}

Main question: Calling std::prev instead of std::ranges::prev on the iterator makes gcc run into an infinite loop. This means there’s a compiler bug or the code calling std::prev invokes undefined behaviour – which one is it?

---

Some thoughts on the latter: std::prev requires a LegacyBidirectionalIterator, whereas std::ranges::prev requires the concept bidirectional_iterator. From my understanding, the only difference between these two is (taken from the description of bidirectional_iterator):

Unlike the LegacyBidirectionalIterator requirements, the bidirectional_iterator concept does not require dereference to return an lvalue.

If this indeed means that calling std::prev invokes undefined behaviour: Do basically all non-ranges algorithms invoke undefined behaviour when called with iterators of the new kind, as LegacyForwardIterator and forward_iterator share the same difference? Could the constraints for the old algorithms not be relaxed to the new iterator-kind, to avoid exactly this, as that would be still backwards-compatible?

Answer 1

This means there’s a compiler bug or the code calling std::prev invokes undefined behaviour – which one is it?

The latter, although libstdc++ should be able to detect this failure and diagnose it better as it does if you ask it to.

The issue here is that given:

auto view = v | std::views::transform([] (auto i) { return static_cast<int>(i); });

view's iterators are C++20 random access iterators, but because their reference type is a prvalue int, they can only be C++17 input iterators. That's just the way the pre-C++20 iterator model worked: forward iterator required a true reference.

std::ranges::prev uses the C++20 iterator categories, std::prev uses the C++17 (or really C++98) iterator categories. And std::prev requires BidirectionalIterator. It's unspecified to what extent the library needs to try to validate that the iterator is indeed bidirectional, but prev(it, n) is specified as advance(it, -n); return it; and advance(it, n) for non-bidirectional iterators will just loop until it hits n... which for negative n will clearly never happen.

That said, if you're using Ranges, you should be using std::ranges::meow instead of std::meow in all cases, because of this iterator category difference. This case is pretty dramatic since it's "works" vs "infinite loop", but note that std::next(it, 100) would be a loop that increments it 100 times while std::ranges::next(it, 100) would return it + 100, so even when they both "work" it's still a significant difference.