Is there a standard way of moving a range into a vector?

Question

Consider the following program which inserts a range of elements into a vector:

vector<string> v1;
vector<string> v2;

v1.push_back("one");
v1.push_back("two");
v1.push_back("three");

v2.push_back("four");
v2.push_back("five");
v2.push_back("six");

v1.insert(v1.end(), v2.begin(), v2.end());

This efficiently copies the range, allocating enough space in the target vector for the entire range so that a maximum of one resize will be required. Now consider the following program which attempts to move a range into a vector:

vector<string> v1;
vector<string> v2;

v1.push_back("one");
v1.push_back("two");
v1.push_back("three");

v2.push_back("four");
v2.push_back("five");
v2.push_back("six");

for_each ( v2.begin(), v2.end(), [&v1]( string & s )
{
    v1.emplace_back(std::move(s));
});

This performs a successful move but doesn't enjoy the benefits that insert() has with regard to preallocating space in the target vector, so the vector could be resized several times during the operation.

So my question is, is there an insert equivalent which can move a range into a vector?

Solution 1

You use a move_iterator with insert:

v1.insert(v1.end(), make_move_iterator(v2.begin()), make_move_iterator(v2.end()));

The example in 24.5.3 is almost exactly this.

You'll get the optimization you want if (a) vector::insert uses iterator-tag dispatch to detect the random-access iterator and precalculate the size (which you've assumed it does in your example that copies), and (b) move_iterator preserves the iterator category of the iterator it wraps (which is required by the standard).

On an obscure point: I'm pretty sure that vector::insert can emplace from the source (which is irrelevant here, since the source is the same type as the destination, so an emplace is the same as a copy/move, but would be relevant to otherwise-identical examples). I haven't yet found a statement that it's required to do so, I've just inferred it from the fact that the requirement on the iterator pair i,j passed to insert is that T be EmplaceConstructible from *i.

Solution 2

1. std::move algorithm with preallocation:

   #include <iterator>
   #include <algorithm>
   
   v1.reserve(v1.size() + v2.size()); // optional
   std::move(v2.begin(), v2.end(), std::back_inserter(v1));
   

2. The following would be more flexible yet:

   v1.insert(v1.end(), 
        std::make_move_iterator(v2.begin()), 
        std::make_move_iterator(v2.end()));
   

   Steve Jessop provided background information on precisely what it does and probably how it does so.

Comments

[Ben Voigt]

The chances of this resizing the destination vector only once are very very slim.

[Benj]

Oh neat, didn't know about this form of std::move. Although I guess the back_inserter could still cause multiple resizes though.

[sehe]

@BenVoigt Why? I suppose it is up to the implementation. vector::reserve is your friend. Let me check the standard.

[Benj]

Excellent, didn't know about make_move_iterator

[Ben Voigt]

@sehe: back_inserter doesn't know a-priori how many times it will be invoked. std::move can find out, but there isn't any way for it to know the destination is inserting into a vector.

[Steve Jessop]

I don't think the first one realistically can reallocate only once: move can see that you have a random access iterator, so it can work out the size required, but it only sees a back_insert_iterator, not the underlying vector, so it has no way to reserve space. It would require an incredibly tortuous overload of std::move to catch this case.

[Ben Voigt]

Though I guess it's possible for back_insert_iterator to provide some member besides operator* and operator++, some sort of preallocate that can be detected using SFINAE. That would be a little more maintainable than overloading std::move specifically for back_insert_iterator into a vector, yet still unlikely.

[Steve Jessop]

@Ben Voigt: slight quibble, move can't detect preallocate on its destination iterator and call it, because some user-defined iterator might have a totally unrelated preallocate function (duck-typing gone bad). It could detect __preallocate, though, so this isn't a barrier. I agree with you that detecting an easter-egg feature on the iterator is better than detecting the type like I suggested.

[sehe]

@SteveJessop and @BenV - I see your point, I had a bit of a derp moment there. Will edit now

[sehe]

@SteveJessop mmm did you steal my answer just there? :)

[Steve Jessop]

@sehe: I was independently typing the same thing at the same time. But I did steal your green tick, because your make_move_iterator code appeared as soon as I submitted mine which means you were first. Normally I delete when that happens, but on this occasion I was certain and you were only guessing, so I figured my answer did add something :-)

[sehe]

@SteveJessop It's ok. I wasn't guessing, actually, but move semantics have tripped me up often enough to not want to make false claims. I was busy with other things, so I couldn't verify

[Benj]

Hmm, I've discovered that it's also possible to use make_move_iterator to turn std::copy_if into the equivalent of a std::move_if. That's very handy.

[Steve Jessop]

I don't want to seem petty, but I think the back_inserter code also relies for maximum efficiency on the fact that in this case, the source and destination containers are both of string. The OP's example code uses emplace_back, and although back_insert_iterator can move the source (it has an rvalue overload of operator= that calls the rvalue overload of push_back on the container), it can't emplace from it (it never calls emplace_back). So I think it requires an additional conversion when the source type is different. C++11, it's a different world.

[sehe]

@SteveJessop nice observation, however, the OP was talking about two vector<string>. In more general terms, yes, obviously class members are usually preferred over the free-function algorithms

[Evgeny Danilenko]

Sorry for resurrecting this, and asking a question in comments, but what if the source and destination vectors are vector<unique_ptr<T>> ? applying the make_move_iterator on the 1st argument wont work and without it an error about copying raises. how should i go about it?

[Steve Jessop]

@Evgeny: Works for me, so I've probably misunderstood what you mean. I suggest you ask a new question including the code that doesn't work for you.

[Steve Jessop]

#include <iostream> #include <iterator> #include <memory> #include <vector> int main() { std::vector<std::unique_ptr<int>> src; src.emplace_back(std::make_unique<int>(10)); std::vector<std::unique_ptr<int>> dst; dst.insert(dst.end(), std::make_move_iterator(src.begin()), std::make_move_iterator(src.end())); for (std::unique_ptr<int> &p : dst) { std::cout << *p << '\n'; } std::cout << src.size() << ' ' << dst.size() << '\n'; }

[Evgeny Danilenko]

Thank you for your reply. Yes its my bad, i was move a std::set<unique_ptr<T>> to std::vect<unique_ptr<T>> using the vect.insert(vect.end(), make_move_itr(set.begin()), make_move_itr(set.end())) because set contains const items, i couldnt move them out. I still haven't found a way.

[Steve Jessop]

@EvgenyDanilenko: Yes, a const unique_ptr is pretty intractable. Can't copy it and can't move it. AFAIK it will take its referand with it to the grave, although it might be I've missed some clever trick.

[Evgeny Danilenko]

what i don't get is why does it allow copying when the set is std::set<T*> then moving to std::vector<T*> is fine. which is what i ended up doing.