Moving elements from std::vector to another one

Question

How can I move some elements from first vector to second, and the elements will remove from the first?
if I am using std::move, the elements not removed from first vector.
this is the code I wrote:

   move(xSpaces1.begin() + 7, xSpaces1.end(), back_inserter(xSpaces2));

Solution 1

The std::move lets you move the objects, as opposed to copying them, allowing for a potentially faster execution speed. The savings may be even greater when you move a range of values. However, when you do move a range from a container, the container still holds the places that were once occupied by these values.

You need to resize the container manually to remove these placeholders if you want to get rid of them (you don't have to, in case you would prefer reusing these container spots for other elements). One way to do it is to call vector::erase on the same range that you moved out of the container.

Solution 2

Resurrecting an old thread, but I am surprised that nobody mentioned std::make_move_iterator combined with insert. It has the important performance benefit of preallocating space in the target vector:

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

As others have pointed out, first vector v1 is now in indeterminate state, so use erase to clear the mess:

v1.erase(v1.begin() + 7, v1.end());

Solution 3

std::move and std::copy operate on elements, not containers. You have to mutate the container separately. For example, to move the first 17 elements of v1 into a new vector v2:

std::vector<Foo> v1, v2;
// populate v1 with at least 17 elements...
auto it = std::next(v1.begin(), 17);
std::move(v1.begin(), it, std::back_inserter(v2));  // ##
v1.erase(v1.begin(), it);

After line ##, the first 17 elements of v1 are still there, but they've been "moved-from", so they're in an indeterminate state.

Solution 4

You can't move elements from one vector to another the way you are thinking about; you will always have to erase the element positions from the first vector.

If you want to change all the elements from the first vector into the second and vice versa you can use swap.

If you want to move the same amount of elements between two vectors, you can use swap_ranges

View more solutions

Comments

[Ivaylo Strandjev]

Won't just swap member of vector suffice here?

[Kerrek SB]

@IvayloStrandjev: depends on what you want to do... if you want to move a segment from the middle of the first vector, I don't see how swapping would be advantageous.

[WhozCraig]

@IvayloStrandjev Swap with what? You're filling a hole; not exchanging gifts. Or I don't understand the concept (hell, at this wee hour without my caffeine its a miracle I understand Kerrek's post). Edit: OK. I see your post. now I understand both concepts.

[alestanis]

@R.MartinhoFernandes Edited to be clearer. The OP was asking for one operation to do what he has to do in two operations, the second one always being erasing from the first vector.

[Dave S]

Another option (instead of std::move) is to use std::make_move_iterator and vector.assign()

[Ivaylo Strandjev]

@WhozCraig yes, I missed the part that he only needed to exchange a subvector. Still I will keep my answer as it suggests an option not mentioned elsewhere.

[Gabriel]

good answer; but take care the initial vector is inan indeterminate state, since the move assignement constructor has been called, an the initial objects have been ripped the guts out to quote scott meyers

[PHcoDer]

I am getting courrpted doubly linked list error by using this. Also I used all the three parameters being passed to std::move separately and they all worked well.

[Kerrek SB]

@PHcoDer: Are you sure you don't have overlapping ranges?

[Adrian]

Doesn't std::back_inserter() use the push_back() function of the v2? In which case, will this not result in an unnecessary copy?

[Kerrek SB]

@Adrian: Why would push_back result in copies? We're using move iterators, whose whole point is to move.

[Adrian]

Nm, didn't realise that push_back() had a move operation.

[Adrian]

Wouldn't it be prudent to reserve the number of added values so that it doesn't have to reallocate all the time, or potentially over allocating, depending on allocation scheme?

[Kerrek SB]

@Adrian: It sure would!

[Adrian]

One last thing. You say that the elements in v1 would be in an indeterminate state. However, they would have to be in a valid state, so it's not exactly indeterminate, is it?

[Kerrek SB]

@Adrian: "Valid but indeterminate" is the way it's usually phrased. It means you cannot assume any particular value, hence you can only call member functions that have no preconditions. Typically you would of course reassign or destroy such objects.

[Adrian]

One more last thing. Is there a way to move consecutive items of one vector into another, but not at the end? Or would I have to do a std::rotate() afterwards?

[Bar]

You think it might be possible to optimize this further if the subvector to be inserted is an r-value? (returned from a function, only purpose is to be added to the bigger vector)

[Miljen Mikic]

@Bar std::make_move_iterator produces std::move_iterator whose purpose is to convert the value returned by the underlying iterator into an rvalue. If the subvector is already an rvalue, I don't think it brings the additional optimization.

[Miral]

A useful extension of this is that if you want to construct a new vector containing only the subset of items being removed from the original vector, you can do it at construction time, with std::vector<T> v2(std::make_move_iterator(v1.begin() + 7), std::make_move_iterator(v1.end())); immediately followed by the matching v1.erase. And, of course, the initial iterator could be the result of std::remove_if, to extract all items matching a predicate.

[Mandeep Singh]

@MiljenMikic Could you point to any documentation or any source that proves that "It has important performance benefit of preallocating space in the target vector"?

[Miljen Mikic]

@MandeepSingh See cplusplus.com/reference/vector/vector/insert, specifically the complexity part: Linear on the number of elements inserted (copy/move construction) plus the number of elements after position (moving). Additionally, if InputIterator in the range insert (3) is not at least of a forward iterator category (i.e., just an input iterator) the new capacity cannot be determined beforehand and the insertion incurs in additional logarithmic complexity in size (reallocations). However, v1.begin() returns random access iterator, so the new capacity can be determined.

[rubenvb]

@Gabriel the vector isn't in an indeterminate state, but the moved-from objects are, unless specified specifically for that type of object (e.g. unique_ptr/shared_ptr both specify being reset after being moved-from).

[gsarret]

The important question is whether this avoids allocating more memory than needed. Judging by "the important performance benefit of preallocating", it doesn't avoid. That is, it first allocates new chunk of memory (if needed), copies elements from v1 to v2, and then leaves v1 in indeterminate state (until v1.erase call). Correct?

[Miljen Mikic]

@gsarret It probably allocates a bit more than needed (this is an implementation detail, though), but the point with preallocating is that there is no reallocating happening as the new elements are being moved into the target vector. Of course, this speeds up the whole thing dramatically. It is pretty much the same behavior as if you are inserting many elements into a std::vector instance with and without calling the reserve function beforehand; the performance difference is enormous.

[gsarret]

@miljen-mikic yes, thank you! I understand that. I was wondering if there's a way to move elements from one vector to the other without allocating additional memory. But I believe this is impossible because of the contiguous-memory requirement. In that case, a list would more suitable, I guess.

[Miljen Mikic]

@gsarret Yes, vector internally works as a resizable array, and it keeps data in contiguous memory, so this is impossible.