CODEWITHSUNDEEP
c++sortingstlc++11move-semantics
masrtis
masrtis

Reputation: 1310

Is it standard C++ to call move() with an output iterator that has been moved previously?

While brushing up on algorithm design and learning C++11 at the same time, I came up with the following implementation for heap sort:

template <typename It, typename Comp>
void heapSort(It begin, It end, Comp compFunc, std::random_access_iterator_tag)
{
    std::make_heap(begin, end, compFunc);
    std::sort_heap(begin, end, compFunc);
}

template <typename It, typename Comp, typename IterCat>
void heapSort(It begin, It end, Comp compFunc, IterCat)
{
    typedef typename It::value_type value_type;

    std::vector<value_type> randomAccessContainer;
    randomAccessContainer.reserve(std::distance(begin, end));
    std::move(begin, end, std::back_inserter(randomAccessContainer));

    heapSort(std::begin(randomAccessContainer), std::end(randomAccessContainer), compFunc, std::random_access_iterator_tag());
    std::move(std::begin(randomAccessContainer), std::end(randomAccessContainer), begin);
}

Is it standard C++ to first move from [begin, end) into a new container, and then move from that container back into [begin, end)?

Upvotes: 2

Views: 305

Answers (2)

Andy Prowl
Andy Prowl

Reputation: 126412

Is it standard C++ to first move from [begin, end) into a new container, and then move from that container back into [begin, end)?

I was initially confused by your use of the word "standard", and edited the question so that it was asking whether this was "legal". The answer to that question would be: "Yes, it is perfectly legal". After the elements in the original range are moved from, they are still in a valid (even though unspecified) state.

Hence, the second call to std::move() will just move-assign elements, and the type of those elements shall have a move-assignment operator without pre-conditions. As long as this is the case, I see no problem with that.

After editing your question, though, I started to wonder whether you actually wanted to ask if this is "standard", meaning "common practice", which is why I restored the original wording.

The answer to this question is "Partly". You would normally initialize your temporary vector by using a couple of move iterators rather than invoking std::move:

std::vector<value_type> randomAccessContainer(
    std::make_move_iterator(begin),
    std::make_move_iterator(end)
    );

Apart from this, your implementation seems correct to me.

Upvotes: 2

sehe
sehe

Reputation: 392893

No it isn't.

I can see how you'd need it to be a random access container if it wasn't already. In that case prefer std::make_move_iterator:

std::vector<value_type> randomAccessContainer(
     std::make_move_iterator(begin), 
     std::make_move_iterator(end));

In all other cases, you'd want to be sorting in-place. (Unless you need "no effects" on exception, maybe)

Upvotes: 0

Related Questions