4

Here is my (simplified) attempt to implement a ranges::min_element version that would work for both lvalue and rvalue arguments:

#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';
}

The output is

42
42

Surely it lacks some implementation details, but the idea must be clear: if an input range is an rvalue, the return value can store a moved copy of it. Thus it must be totally possible for std::ranges algorithms to work with rvalue arguments.

My question is: why does the standard go the opposite way and just prohibit using rvalue ranges with its algorithms by introducing that strange std::ranges::dangling placeholder?

6
  • 3
    I think you could simplify the examle. A lot.
    – Enlico
    Jan 28, 2021 at 21:22
  • 1
    Related: stackoverflow.com/questions/58400325/…
    – AndyG
    Jan 28, 2021 at 21:24
  • @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
    Jan 29, 2021 at 15:22
  • 3
    @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
    Jan 29, 2021 at 15:27
  • 2
    @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
    Jul 19 at 9:35

1 Answer 1

12

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.

4
  • We tried the last one too. It didn't work too well.
    – T.C.
    Jan 28, 2021 at 23:22
  • 4
    @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?
    – Barry
    Jan 28, 2021 at 23:32
  • 1
    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.
    – T.C.
    Jan 28, 2021 at 23:41
  • 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. Nov 17 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.