Moving Elements from Std::Vector to Another One

Moving elements from std::vector to another one

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.

Moving elements from one vector to another using erase-remove paradigm

I think that generally the point of these algorithms, is that you are doing what you want to achieve by applying functions. Once the functions have side-effects, it seems like if anything the net result is maybe misleading, and it might just be better to do a for loop.

That said, remember that C++ is not Java. A vector<Foo> has to store Foo's, it just can't store references. However, there is still a problem with your whole idea.

myNewVec.push_back(x);

This line from your code will push a copy of x into your new vector. Because it's a copy, you don't have to worry about sharing references. Now, for integers, copies and moves are the same. But for complex objects (like, say, a vector), a move can be way, way faster than a copy. And the only vector is anyway getting rid of x, so we definitely want to move. So ideally we would change that line to:

myNewVec.push_back(std::move(x));

However, moving from an object clearly mutates it, and requires it not be const. The requirements for remove_if however require that the function object passed is a predicate. This, in turn means that:

The function object pred shall not apply any non-constant function through the dereferenced iterator.

http://en.cppreference.com/w/cpp/concept/Predicate

In other words, your function must accept the result of dereferencing the iterator, but is not supposed to mutate it. Because it is not supposed to mutate it, you can never move from the original object, but have to make a copy of it. Therefore, I don't think there is any conformant, efficient implementation of this idea for non-trivial types.

Here is a reasonable implementation:

template <class T, class F>
void transfer_if_not(std::vector<T>& old, std::vector<T>& new, F pred)
{
    auto part = std::partition(old.begin(), old.end(), pred);
    std::move(part, old.end(), std::back_inserter(new));
    old.erase(part);
}

This at least should not copy any elements. It will basically separate out the elements to stay and to leave in place in the original vector. Then efficiently move out the ones that are leaving. And then simply resize the array. As pointed out in the comments, this probably involves extra operations compared to what's optimal, but my sense is that the optimal version is not trivial to code up, and may involve tradeoffs (like more state), so it may not be a pure win.

Note that my algorithm accepts a vector specifically instead of iterators, because for other containers (say a linked list), this implementation is quite far from optimal.

Can I move the contents of one vector to the end of another?

You can use std::make_move_iterator, so that accesses to the iterator returns rvalue references instead of lvalue references:

a.insert(a.end(), std::make_move_iterator(b.begin()), std::make_move_iterator(b.end()));

How do I move-append one std::vector to another?

insert will work fine with std::move_iterator and std::make_move_iterator helper fucntion:

to.insert(to.end(),std::make_move_iterator(from.begin()),
    std::make_move_iterator(from.end()));

When appending one vector to another, why is moving the elements any cheaper than copying them?

Indeed, if copying and moving an element costs the same (is in your example with elements of type int), then there is no difference.

Moving only makes a difference for elements which themselves store their data on the heap, i.e. use allocated memory (for example if the elements are std::string or std::vector<something>). In this case, moving or copying the elements makes a (potentially huge) difference (provided the move constructor and operator=(value_type&&) are properly implemented/enabled), since a move merely copies the pointer to the allocated memory, while a copy is deep: it allocates new memory and copies all data, including recursive deep copies if applicable.

As to the costs associated with the data stored in std::vector, there are some costs if the appended elements exceed capacity. In this case, the whole vector will be resized, including moving all its elements. The reason for this is that std::vector, by specification, stores all its elements in a single array. If appending containers is a frequent operation in your code, you may want to consider other containers, such as std::list or std::deque.

C++ Moving elements from one vector to another

The std::vector<...> does have an insert() method. Actually, it has multiple overloaded insert() methods but all of them take an iterator indicating the position where to insert the passed value(s). If it is OK to append the value to the end, you can use push_back():

peerList.push_back(p);

How to move the first element of a vector to the end of another

Erasing while iterating is always messy. If you erase the current element, how can ++ work?

Instead try

while (!ToRun.empty()) // loop until empty
{
    ToRun.front()->dump(os);

    Completed.push_back(std::move(ToRun.front()));
    ToRun.erase(ToRun.begin());
}

or something similar

But that's gross when you stop and think about it. Every erase shifts the rest of the elements in ToRun back one slot adding a large amount of unnecessary iterating and copying.

for (auto & run: ToRun) // or old school iterator if you prefer
{
    run->dump(os);
    Completed.push_back(std::move(ToRun.front()));
}
toRun.clear();

clear executes only once and obliterates the whole container in one shot. Much cleaner. Just one iteration to make sure the destructors are called, and you don't destroy pointers. Winning!

will have the same effect (assuming this isn't multithreaded, and if it is you have serious concurrency issues).

Cheersandhth.-Alf also brings up the point that since ToRun appears to contain pointers, std::move is not necessary. All that is being moved is a pointer, and that's trivial effort.

STL vector: Moving all elements of a vector

Using C++11, it's as simple as:

A = std::move(B);

Now A contains the elements that were previously held by B, and B is now empty. This avoids copying: the internal representation is simply moved from B to A, so this is an O(1) solution.

As for C++03, as Prætorian states, you could swap the vectors. There is a specialization of the std::swap function, which takes std::vectors as its arguments. This effectively swaps the internal representation, so you end up avoiding creating copies of the elements held by them. This function works in O(1) complexity as well.

Moving the contents of one vector to another

Here’s a complete workflow of how to handle spawning and despawning enemies. Note that there are no pointers at all involved.

1. Spawning an enemy:

   if (if random_float_between_0_and_1() < 0.002)
       enemies.push_back(Enemy{arguments});
   

2. Despawning enemies; according to your comment below, should look something like this:

   auto last_iter = std::remove_if(enemies.begin(), enemies.end(), is_dead);
   enemies.erase(last_iter, enemies.end());
   

   Here, is_dead is a function that takes an Enemy const& and determines whether it collided with a player or the screen bounds:

   bool is_dead(Enemy const& enemy) {
       return outside_screen_area(enemy) or near_player(enemy);
   }
   

   The functions outside_screen_area and near_player should be straightforward for you to implement.

   To understand how the code above works, consult the documentations of std::remove and std::vector::erase.

Another thing: implement the function random_float_between_0_and_1 in terms of the standard library random library that ships with C++11. Don’t use std::rand or modulo operations on integer random numbers, they work badly (i.e. they’re not truly uniformly distributed and will give skewed results).

---

Related Topics