How to check whether elements of a range should be moved?

Question

There's a similar question: check if elements of a range can be moved?

I don't think the answer in it is a nice solution. Actually, it requires partial specialization for all containers.

---

I made an attempt, but I'm not sure whether checking operator*() is enough.

// RangeType

using IteratorType = std::iterator_t<RangeType>;
using Type = decltype(*(std::declval<IteratorType>()));

constexpr bool canMove = std::is_rvalue_reference_v<Type>;

---

Update

The question may could be split into 2 parts:

1. Could algorithms in STL like std::copy/std::uninitialized_copy actually avoid unnecessary deep copy when receiving elements of r-value?
2. When receiving a range of r-value, how to check if it's a range adapter like std::ranges::subrange, or a container which holds the ownership of its elements like std::vector?

template <typename InRange, typename OutRange>
void func(InRange&& inRange, OutRange&& outRange) {
    using std::begin;
    using std::end;
    std::copy(begin(inRange), end(inRange), begin(outRange));
    // Q1: if `*begin(inRange)` returns a r-value,
    //     would move-assignment of element be called instead of a deep copy?
}

std::vector<int> vi;
std::list<int> li;
/* ... */
func(std::move(vi), li2);
// Q2: Would elements be shallow copy from vi?
// And if not, how could I implement just limited count of overloads, without overload for every containers?
// (define a concept (C++20) to describe those who take ownership of its elements)

Q1 is not a problem as @Nicol Bolas , @eerorika and @Davis Herring pointed out, and it's not what I puzzled about. (But I indeed think the API is confusing, std::assign/std::uninitialized_construct may be more ideal names)

@alfC has made a great answer about my question (Q2), and gives a pristine perspective. (move idiom for ranges with ownership of elements)

---

To sum up, for most of the current containers (especially those from STL), (and also every range adapter...), partial specialization/overload function for all of them is the only solution, e.g.:

template <typename Range>
void func(Range&& range) { /*...*/ }

template <typename T>
void func(std::vector<T>&& movableRange) {
    auto movedRange = std::ranges::subrange{
        std::make_move_iterator(movableRange.begin()),
        std::make_move_iterator(movableRange.end())
    };

    func(movedRange);
}

// and also for `std::list`, `std::array`, etc...

Answer 1

I understand your point. I do think that this is a real problem.

My answer is that the community has to agree exactly what it means to move nested objected (such as containers). In any case this needs the cooperation of the container implementors. And, in the case of standard containers, good specifications.

I am pessimistic that standard containers can be changed to "generalize" the meaning of "move", but that can't prevent new user defined containers from taking advantage of move-idioms. The problem is that nobody has studied this in depth as far as I know.

As it is now, std::move seem to imply "shallow" move (one level of moving of the top "value type"). In the sense that you can move the whole thing but not necessarily individual parts. This, in turn, makes useless to try to "std::move" non-owning ranges or ranges that offer pointer/iterator stability.

Some libraries, e.g. related to std::ranges simply reject r-value of references ranges which I think it is only kicking the can.

Suppose you have a container Bag. What should std::move(bag)[0] and std::move(bag).begin() return? It is really up to the implementation of the container decide what to return.

It is hard to think of general data structures, bit if the data structure is simple (e.g. dynamic arrays) for consistency with structs (std::move(s).field) std::move(bag)[0] should be the same as std::move(bag[0]) however the standard strongly disagrees with me already here: https://en.cppreference.com/w/cpp/container/vector/operator_at And it is possible that it is too late to change.

Same goes for std::move(bag).begin() which, using my logic, should return a move_iterator (or something of the like that).

To make things worst, std::array<T, N> works how I would expect (std::move(arr[0]) equivalent to std::move(arr)[0]). However std::move(arr).begin() is a simple pointer so it looses the "forwarding/move" information! It is a mess.

So, yes, to answer your question, you can check if using Type = decltype(*std::forward<Bag>(bag).begin()); is an r-value but more often than not it will not implemented as r-value. That is, you have to hope for the best and trust that .begin and * are implemented in a very specific way.

You are in better shape by inspecting (somehow) the category of the range itself. That is, currently you are left to your own devices: if you know that bag is bound to an r-value and the type is conceptually an "owning" value, you currently have to do the dance of using std::make_move_iterator.

I am currently experimenting a lot with custom containers that I have. https://gitlab.com/correaa/boost-multi However, by trying to allow for this, I break behavior expected for standard containers regarding move. Also once you are in the realm of non-owning ranges, you have to make iterators movable by "hand".

I found empirically useful to distinguish top-level move(std::move) and element wise move (e.g. bag.mbegin() or bag.moved().begin()). Otherwise I find my self overloading std::move which should be last resort if anything at all.

In other words, in

template<class MyRange>
void f(MyRange&& r) {
   std::copy(std::forward<MyRange>(r).begin(), ..., ...);
}

the fact that r is bound to an r-value doesn't necessarily mean that the elements can be moved, because MyRange can simply be a non-owning view of a larger container that was "just" generated.

Therefore in general you need an external mechanism to detect if MyRange owns the values or not, and not just detecting the "value category" of *std::forward<MyRange>(r).begin() as you propose.

I guess with ranges one can hope in the future to indicate deep moves with some kind of adaptor-like thing "std::ranges::moved_range" or use the 3-argument std::move.