How to move the later half of a vector into anothe

Question

I have a vector and I would like to efficiently break out the second half of the vector into another vector using STL algorithms. Here is one way I see to do this, but expect there are more efficient and succinct answers, or at the least, one that uses the stl algorithms:

std::vector<Entry> &entries = someFunction();
int numEntries = entries.size();

// Assume numEntries is greater than or equal to 2.

std::vector<Entry> secondEntries;
std::vector<Entry>::iterator halfway = entries.begin() + numEntries / 2;
std::vector<Entry>::iterator endItr  = entries.end() 

// Copy the second half of the first vector in the second vector:
secondEntries.insert(secondEntries.end(), halfway, endItr);

// Remove the copied entries from the first vector:
entries.erase(halfway, endItr);

Answer 1

Taking a step back, keep in mind to make sure that you're working with iterators with your own algorithms, and not (necessarily) containers. So if you have this:

void foo(const std::vector<Entry>& v) { /* ... */ }

And now you're stuck in this situation:

std::vector<Entry> entries = someFunction();

// have to split entries! make more containers? :(
foo(first_half(entries));
foo(second_half(entries));

Consider using iterators instead:

// or a template, if it doesn't hurt
void foo(std::vector<Entry>::const_iterator first, 
         std::vector<Entry>::const_iterator second) { /* ... */ }

So now you denote ranges and not containers:

std::vector<Entry> entries = someFunction();

// easy to split entries! :)
auto middle = entries.begin() + entries.size() / 2;
foo(entries.begin(), middle);
foo(middle + 1, entries.end());

This limits the number of unnecessary containers and allocations you make.

---

With that out of the way, in C++11 you can do this (rest is the same):

// *Move* the second half of the first vector in the second vector:           
secondEntries.insert(secondEntries.end(),
                        std::make_move_iterator(halfway),
                        std::make_move_iterator(endItr));

If Entry has a move constructor, the move_iterator adapter will ensure that it is used during the insertion (if it doesn't a normal copy is made). In C++03, what you have is probably best.

Answer 2

There are several other ways of performing this task for example by using copy algorithm and an insert iterator.

But algorithmic the complexity of these actions will always be O(n) due to the nature of the vector container. Vector is not a list that allows moving big chunks of data from one container to another in a O(1) (constant) time. Depending on the particular STL implemenation one way can be 10-20% better than the other, but unlikely it will be more than that.

If data type of your container allows move semantics and you have these language features available, this will definitely help. But this is more about handling data object in the container rather than the container itself.

Answer 3

std::move can do a better job if you have access to a c++11 compiler and moveable objects.

Note that you still need to erase them from the first vector.