71

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?

chema989
  • 3,962
  • 2
  • 20
  • 33
Benj
  • 31,668
  • 17
  • 78
  • 127
  • 1
    If you need to preallocate space in the vector, use `std::vector::reserve`, and keep `push_back`/`emplace_back`. – rubenvb May 23 '12 at 12:43
  • @rubenvb Yes I thought that would probably be the answer, it's just a shame there isn't a method as clean as `insert()` is. – Benj May 23 '12 at 12:46
  • That would be an optional optimization, only possible when the range is defined by random-access iterators. Don't count on it. – Ben Voigt May 23 '12 at 12:46
  • That's always true though when using `std::vector` no? – Benj May 23 '12 at 12:47
  • @Benj: `std::vector` iterators are random access, but the library might not include the optimization. And the question appears to ask about insertion into a vector from an arbitrary unspecified range, which might not have random-access iterators. – Ben Voigt May 23 '12 at 12:49

2 Answers2

107

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.

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
  • 5
    Excellent, didn't know about `make_move_iterator` – Benj May 23 '12 at 12:50
  • 5
    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. – Benj May 23 '12 at 13:11
  • Sorry for resurrecting this, and asking a question in comments, but what if the source and destination vectors are vector> ? 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? – Evgeny Danilenko Sep 27 '17 at 23:37
  • 1
    @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 Sep 29 '17 at 11:58
  • #include #include #include #include int main() { std::vector> src; src.emplace_back(std::make_unique(10)); std::vector> dst; dst.insert(dst.end(), std::make_move_iterator(src.begin()), std::make_move_iterator(src.end())); for (std::unique_ptr &p : dst) { std::cout << *p << '\n'; } std::cout << src.size() << ' ' << dst.size() << '\n'; } – Steve Jessop Sep 29 '17 at 12:06
  • Thank you for your reply. Yes its my bad, i was move a std::set> to std::vect> 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. – Evgeny Danilenko Sep 29 '17 at 18:11
  • 1
    @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. – Steve Jessop Sep 29 '17 at 18:18
  • what i don't get is why does it allow copying when the set is std::set then moving to std::vector is fine. which is what i ended up doing. – Evgeny Danilenko Sep 29 '17 at 19:16
44

  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.

sehe
  • 374,641
  • 47
  • 450
  • 633
  • The chances of this resizing the destination `vector` only once are very very slim. – Ben Voigt May 23 '12 at 12:46
  • 2
    Oh neat, didn't know about this form of `std::move`. Although I guess the `back_inserter` could still cause multiple resizes though. – Benj May 23 '12 at 12:48
  • @BenVoigt Why? I suppose it is up to the implementation. vector::reserve is your friend. Let me check the standard. – sehe May 23 '12 at 12:48
  • @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. – Ben Voigt May 23 '12 at 12:50
  • 4
    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. – Steve Jessop May 23 '12 at 12:51
  • 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. – Ben Voigt May 23 '12 at 12:53
  • @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. – Steve Jessop May 23 '12 at 13:02
  • @SteveJessop and @BenV - I see your point, I had a bit of a `derp` moment there. Will edit now – sehe May 23 '12 at 13:03
  • @SteveJessop mmm did you steal my answer just there? :) – sehe May 23 '12 at 13:04
  • @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 :-) – Steve Jessop May 23 '12 at 13:07
  • @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 – sehe May 23 '12 at 13:09
  • 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. – Steve Jessop May 23 '12 at 13:20
  • @SteveJessop nice observation, however, the OP was talking about two `vector`. In more general terms, yes, obviously class members are usually preferred over the free-function algorithms – sehe May 23 '12 at 13:28