Why do std range algorithms return std::ranges::dangling for rvalue arguments instead of... well, just working?

Question

Why do the C++ standard library's range algorithms like min_element return a std::ranges::dangling placeholder in case their argument container was an rvalue?

It could be totally possible to implement them in a way they would return an object holding a moved copy of that temporary container, so that nothing would dangle, along with the algorithm's main result (an iterator to the minimal element, in this case). Which could be quite convenient in some cases - e.g., when I receive a vector from some function call and want to immediately find the value of its minimal element.

So, why doesn't the C++ standard library do that?

Here's the illustration of my idea how such a "better min_element" that could handle both lvalue and rvalue arguments could be implemented:

#include <iterator>
#include <algorithm>
#include <type_traits>
#include <utility>

namespace better_std_ranges
{
    template<typename Range>
    constexpr auto min_element(Range& range)
    {
        using std::begin;
        using std::end;
        return std::min_element(begin(range), end(range));
    }

    template<typename Range>
    constexpr auto min_element(Range&& range)
    {
        static_assert(!std::is_reference_v<Range>, "wrong overload chosen");

        class _result_iterator_type // todo: inherit from some crtp base that will provide lacking operators depending on _underlying_iterator_type::iterator_category
        {
            using _underlying_iterator_type = std::decay_t<decltype(std::begin(std::declval<Range&>()))>;

        public:
            explicit constexpr _result_iterator_type(Range&& range) noexcept(std::is_nothrow_move_constructible_v<Range>)
            : _underlying_range{std::move(range)}
            , _underlying_iterator(::better_std_ranges::min_element(_underlying_range))
            {
            }

            using difference_type   = typename _underlying_iterator_type::difference_type;
            using value_type        = typename _underlying_iterator_type::value_type;
            using pointer           = typename _underlying_iterator_type::pointer;
            using reference         = typename _underlying_iterator_type::reference;
            using iterator_category = typename _underlying_iterator_type::iterator_category;

            constexpr decltype(auto) operator*() const
            {
                return *_underlying_iterator;
            }

            // todo: define other member functions that were not provided by the inheritance above

        private:
            Range _underlying_range;
            _underlying_iterator_type _underlying_iterator;
        };

        return _result_iterator_type{std::move(range)};
    }
}

#include <vector>
#include <iostream>

auto make_vector()
{
    return std::vector{100, 200, 42, 500, 1000};
}

int main()
{
    auto lvalue_vector = make_vector();
    auto lvalue_vector_min_element_iterator = better_std_ranges::min_element(lvalue_vector);
    std::cout << *lvalue_vector_min_element_iterator << '\n';

    auto rvalue_vector_min_element_iterator = better_std_ranges::min_element(make_vector());
    std::cout << *rvalue_vector_min_element_iterator << '\n';
}

Output:

42
42

@Enlico If you know how to do it simpler, that's great and I'm happy for you. I just wrote what I could to illustrate an idea of how this issue could be worked around. Actual code from the C++ standard library implementation usually looks even more complicated :) — Taras
– Taras, Commented Jan 29, 2021 at 15:22
@Taras, there's a lot of stuff in your code which maybe relevant to the idea that you have in your mind, but not to the question. One example, using difference_type = .... Writing a question according to How do I ask a good question? is your responsability, not mine. That being said, I'm happy someone was able to answer. — Enlico
– Enlico, Commented Jan 29, 2021 at 15:27
@Taras, yeah, you got your answer. Now I need mine, which is supposedly related, and I have to dig through all the irrelevant stuff to evaluate if this all even applies. Being helpful to people is what SO about. — vines
– vines, Commented Jul 19, 2023 at 9:35

Barry · Accepted Answer · 2021-01-28 21:33:06Z

15

There are two problems with this approach.

First, it breaks the semantics of the algorithm. The point of min_element (and any other algorithm that returns an iterator) is to return an iterator into the range. You're not doing that - you're returning an iterator into a different range. That really confuses the notion of what the return even means in this case. What would you even compare this iterator to? There's no corresponding .end()?

Second, the iterator model in C++ is based very strongly around the notion that iterators are cheap to copy. Every algorithm takes iterators by value and copies them around freely. Iterators are assumed to be light-weight and, importantly, non-owning. For forward iterators, copies of an iterator are assumed to be interchangeable.

Everything about this breaks if you suddenly have an iterator that has member std::vector<T> that it refers into. Copying iterators becomes very expensive. And now each distinct iterator copy is actually an iterator into a completely different range?

You can do a little bit better by having the iterator have a member std::shared_ptr<std::vector<T>> instead of a std::vector<T>. This way copies are much cheaper and no longer independent, so you have something closer to a legitimate iterator. But now you have to do an extra allocation (to create the shared pointer), you still have the issue where the iterator you're returning is into a different range than the algorithm was given, and you have the issue where the algorithm has very different semantics based on whether you provide an lvalue or rvalue range.

Basically, min_element on an rvalue range needs to either:

just return an iterator into the range, even if it will dangle
return some kind of wrapper around such a potentially-dangling iterator (this was the original Ranges design, dangling<I> could still let you get at the underlying I)
return some kind of type indicating that this doesn't work (the current design)
fail to compile entirely if usage would lead to dangling (what Rust would allow for)

I don't think there's another option here, really.

answered Jan 28, 2021 at 21:33

Barry

312k32 gold badges734 silver badges1.1k bronze badges

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

4 Comments

T.C. Over a year ago

We tried the last one too. It didn't work too well.

Barry Over a year ago

@T.C. Though, I don't understand the point of returning a useless type from an algorithm whose sole purpose is to return a value and has no other side effects?

T.C. Over a year ago

I think the predicate can have side effects as long as it doesn't change the elements or the result. Regardless, I don't really think it's worth the trouble having a mix of two systems of dangling iterator prevention when attempting to use the result as an iterator is ill-formed anyway.

Weijun Zhou Over a year ago

I think the type in OP's question (without modifying to shared_ptr) can be used as a return type in place of std::ranges::dangling, as long as it is made crystal clear that it is not an iterator itself and should not be used as one, and provides ways to access the underlying actual iterator and range. We already have plenty of specifically designed result types in std like in_out_result, so adding another one is acceptable. Although we still need to consider whether it is worth the effort or whether it makes things more perplexing.

Collectives™ on Stack Overflow

Why do std range algorithms return std::ranges::dangling for rvalue arguments instead of... well, just working?

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related