How to use c++11 move semantics to append vector contents to another vector?

Question

Consider this snippet:

class X;

void MoveAppend(vector<X>& src, vector<X>& dst) {
   dst.reserve(dst.size() + src.size());
   for (const X& x : src) dst.push_back(x);
   src.clear();
}

If we assume that class X implements move semantics, how can I efficiently implement MoveAppend?

Destrier

Answer 1

Just do:

#include <iterator>
#include <algorithm>

// ...

void MoveAppend(std::vector<X>& src, std::vector<X>& dst) 
{
    if (dst.empty())
    {
        dst = std::move(src);
    }
    else
    {
        dst.reserve(dst.size() + src.size());
        std::move(std::begin(src), std::end(src), std::back_inserter(dst));
        src.clear();
    }
}

If dst is empty, a move-assignment from src to dst will do the job - that will be as cheap as it can be, just "stealing" the array encapsulated by src so that dst will point to it afterwards.

If dst is not empty, elements appended to dst will be move-constructed from elements in src. After the call to std::move(), src will not be empty - it will contain "zombie" moved-from elements. That's why the call to clear() is still necessary.

Staphylorrhaphy

@ŁukaszLew: Is it guaranteed to not be empty? If it can possibly be empty, it might be a good idea to check that first. Then you can still do a simple move of the whole container, which will possibly be a lot cheaper. – Projectile

can you explain why this is better than dst.insert(end(dst), begin(src), end(src))? – Shier

@TemplateRex: That would copy-construct the new elements of dst from the corresponding elements of src. What the OP wants is moving – Staphylorrhaphy

But in practice, the ranged-insert avoid multiple push_back() and reallocation of capacity() calls, whereas the std::back_inserter() doesn't (unless preceded by a reserve(). So it's not clear if the move is even faster than the ranged-insert. – Shier

@TemplateRex: That entirely depends on the class being copied/moved. Also notice, that the call to reserve() is there. – Staphylorrhaphy

It is possible to use insert in tandem with move iterators. – Jolenejolenta

@Shier dst.insert(end(dst), make_move_iterator(begin(src)), make_move_iterator(end(src)));. – Circumsolar

Wouldn't the move still require copying elements in this case? – Taryn

@Taryn Moving is more efficient, if the items moved from one vector to the other vector contain internal state. Think for example of a vector of long strings, where moving just requires to move the pointers to the string contents and the length and allocation counters, while copying requires to copy all the contents of all the strings, too! – Headship

Answer 2

I would slightly prefer this to the accepted answer:

#include <vector>
#include <iterator>
#include <utility>

template <typename T>
typename std::vector<T>::iterator append(const std::vector<T>& src, std::vector<T>& dest)
{
    typename std::vector<T>::iterator result;

    if (dest.empty()) {
        dest = src;
        result = std::begin(dest);
    } else {
        result = dest.insert(std::end(dest), std::cbegin(src), std::cend(src));
    }

    return result;
}

template <typename T>
typename std::vector<T>::iterator append(std::vector<T>&& src, std::vector<T>& dest)
{
    typename std::vector<T>::iterator result;

    if (dest.empty()) {
        dest = std::move(src);
        result = std::begin(dest);
    } else {
        result = dest.insert(std::end(dest),
                             std::make_move_iterator(std::begin(src)),
                             std::make_move_iterator(std::end(src)));
    }

    src.clear();
    src.shrink_to_fit();

    return result;
}

Example:

#include <string>
#include <algorithm>
#include <iostream>

int main()
{
    const std::vector<std::string> v1 {"world", "!"};

    std::vector<std::string> v2 {" "}, v3 {"hello"}, v4 {};

    append(v1, v2); // copies
    append(std::move(v2), v3); // moves
    append(std::move(v3), v4); // moves

    std::copy(std::cbegin(v4), std::cend(v4), std::ostream_iterator<std::string> {std::cout});
    std::cout << std::endl;
}

Schumer

I think this is a much better answer, has overloads for lvalue and rvalue source, and uses std::vector::insert(). – Skier

Why do you "clean" the rvalue source? I think that is doing unsolicited extra work. – Skier

@Skier It's an interesting point - my view is that the caller would expect the capacity of the rvalue source to be zero after the call, which would not be the case otherwise. – Schumer

@Schumer caller shouldn't expect anything about the state of moved object. moved object is considered invalidated and should not be used in any way. – Supervisor

there shouldn't be 2 versions of this function. The source should be passed by value, not by const ref or by rvalue. If you pass the source by value, the caller can decide wether to move or copy. – Markley

@grisevg: Still, it's neighbourly. Same as how VS in debug fills uninitialised memory (whose contents are technically unspecified and unreliable) with things like 0xDEADBEEF, to be helpful to programmers doing debugging. In this case it's relatively little extra work even for release... though I concede it may be more than we'd like because it's still N destructor calls. – Pollux

Can this be reduced using perfect forwarding? – Minelayer

Should the dst argument not precede the src argument? Granted the OP supplied the argument order. Or am I hallucinating a standard convention that does not exist? My feeling: it's an analogue of +=, so dst should precede src in the argument list. – Muller

Answer 3

Just trying to improve slightly the answer of @Daniel: the function should not be defined twice, the source should be passed by value.

// std::vector<T>&& src - src MUST be an rvalue reference
// std::vector<T> src - src MUST NOT, but MAY be an rvalue reference
template <typename T>
inline void append(std::vector<T> source, std::vector<T>& destination)
{
    if (destination.empty())
        destination = std::move(source);
    else
        destination.insert(std::end(destination),
                   std::make_move_iterator(std::begin(source)),
                   std::make_move_iterator(std::end(source)));
}

Now the caller can decide whether to copy or move.

std::vector<int> source {1,2,3,4,5};
std::vector<int> destination {0};
auto v1 = append<int>(source,destination); // copied once
auto v2 = append<int>(std::move(source),destination); // copied 0 times!!

Never use && for arguments, unless you have to (for example: std::ifstream&&).

Markley

destiny is an interesting pick of name! – Pollux

I quite liked it! – Pollux

In this case there are two vector memory allocations: one to copy source and a second to extend the size of destination. If we specialize append function on const& and && (as in Daniel's answer) then we only do one vector memory allocation, to extend the size of destination – Bernardinabernardine

@Bernardinabernardine No, not having && doesn't mean the lvalue source cannot be a reference to an rvalue. When I move the source, there is no memory allocation. – Markley

@MFnx If the caller does not move in (append(src, dst)), taking by value will guarantee two vector allocations: one to copy from the caller into our by-value argument, and a second to extend the size of the destination vector (which then has its content populated by moving from the source vector). If the caller does move in (append(move(src), dst)), then there is only one allocation: extending the size of destination. – Bernardinabernardine

@Bernardinabernardine Exactly. So the caller can decide wether or not to copy (or wether or not to keep the original source). Elegant, and only 1 function is needed. – Markley

@MFnx what I've been trying to say is that in the case the caller wants to copy, having the function take the vector by value means 2 vector allocations, whereas taking the vector by const& means only 1 vector allocation. Hope this is clear now :) – Bernardinabernardine

I voted this answer up because it's elegant and answers the original question about moving the vector contents. But @Bernardinabernardine has a point, that the "copy" scenario results in allocating a temporary vector on the stack (whose elements are then moved by the function), whereas the pass-by-reference function allows it to copy the elements straight from the source. Therefore, when copying to a non-empty destination, this will use an extra allocation for that temporary vector (not the elements, just the container). – Kirt

Yes, there is that extra allocation, I had overseen that. Thanks for pointing that out. I wonder however if the compiler could optimize this (I'll have to look into it). – Markley

@mfnx: Compilers are rather naive about heap operations. Their optimizers don't "see", that allocating that space on the heap, then copying the vector contents to it, then moving from the copy, then deallocating the space on the heap again can be replaced by a direct copy from the original. – Headship

The comment // copied once in the answer is misleading. It should read: // copied once, but to the wrong place, and then moved again. – Headship

Could somebdy please vote this answer out of existence. Or delete it, since it's deeply and fundamentally wrong. – Muller