Why does 'ranges::min/max/minmax' require the iterator to satisfy 'indirectly_copyable_storable'?

195 views Asked by At

I recently noticed that the following code doesn't work:

#include <ranges>
#include <algorithm>
#include <memory>
#include <iostream>

int main() {
  std::cout << *std::ranges::max(
    std::views::iota(0, 5) |
    std::views::transform([](int i) { return std::make_unique<int>(i); }),
    {},
    std::ranges::iter_move // another spelling of '[](auto&& p) { return *p; }'
  );
}

The reason is that the signature of ranges::max (the same goes for rangs::min/minmax) requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>:

template<input_range R, class Proj = identity,
         indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
  requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
  constexpr range_value_t<R>
    ranges::max(R&& r, Comp comp = {}, Proj proj = {});

indirectly_copyable_storable is a less well-known concept used to check whether the value_type of the iterator can be temporarily stored and reassigned ([alg.req.ind.copy]):

template<class In, class Out>
  concept indirectly_copyable_storable =
    indirectly_copyable<In, Out> &&
    indirectly_writable<Out, iter_value_t<In>&> &&
    indirectly_writable<Out, const iter_value_t<In>&> &&
    indirectly_writable<Out, iter_value_t<In>&&> &&
    indirectly_writable<Out, const iter_value_t<In>&&> &&
    copyable<iter_value_t<In>> &&
    constructible_from<iter_value_t<In>, iter_reference_t<In>> &&
    assignable_from<iter_value_t<In>&, iter_reference_t<In>>;

The first four indirectly_writable require that Out can be written by value_type with all four qualifiers (&, const&, &&, const&&), where Out is the artificial range_value_t<R>*, which is unique_ptr<int>* in the above example.

Its turns out that this requires the origin range's value_type must be copyable, so the constraint is not satisfied.

However, the implementation of ranges::max does not seem to require so many restrictions, which can be seen from the implementation of various compilers (taking MSVC-STL as an example):

range_value_t<_Rng> _Found(*_UFirst);
while (++_UFirst != _ULast) {
    if (_STD invoke(_Pred, _STD invoke(_Proj, _Found), _STD invoke(_Proj, *_UFirst))) {
        _Found = *_UFirst;
    }
}
return _Found;

We just construct the value and reassign it when the condition is met, that's it. I really don't see the part where we need to do:

range_value_t<_Rng>* _Out;
_Out = _Found;
_Out = std::as_const(_Found);

In other words, it seems that just check that the last two conditions of indirectly_copyable_storable it is enough (the value_type may also need to be movable).

So where did the four indirectly_writable come from? Why do ranges::min/max/minmax all require need such a complex indirectly_copyable_storable? What are the considerations behind this?


In addition to the ranges::max family, the only one that indirectly_copyable_storable is used in <algorithm> is ranges::unique_copy, which specifically for input_range. However, this concept still seems overconstrained in terms of its implementation. So maybe the real question is, how exactly does indirectly_copyable_storable come out?

0

There are 0 answers