Search code examples
c++insertstdvectorerase

How to move the later half of a vector into another vector?


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);

Solution

  • 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.