Search code examples
c++arraysvectorsplitruntime

c std::vector splitting into two

Is there an easy and run-time efficient way to take a std::vector<> in c++ and split it in half into two other vectors?

Because right now I'm doing this:

std::vector<> v1, v2;
for(int i = 0; i < vector.size(); i++)
{
    if(i < vector.size()/2) v1.push_back(vector[i]);
    else v2.push_back(vector[i]);
}

which runs in O(n) time and this is an operation I have to perform quite frequently. So is there a better way?

Solution

  • If you really need 2 vectors, and you can't use GMan's suggestion in the comments:

    // where v1 is your original vector
std::vector<T> v2(
    std::make_move_iterator(v1.begin() + v1.size()/2),
    std::make_move_iterator(v1.end()));
v1.erase(v1.begin() + v1.size()/2, v1.end());

    It's still O(n), but you can't do any better than that.

    If you need to keep the original vector separate:

    std::vector<T> v2(v1.begin(), v1.begin() + v1.size()/2),
               v3(v1.begin() + v1.size()/2, v1.end());