c+ stl sorted vector inplace union

Question

I'd like an efficient method for doing the inplace union of a sorted vector with another sorted vector. By inplace, I mean that the algorithm shouldn't create a whole new vector or other storage to store the union, even temporarily. Instead, the first vector should simple grow by exactly the number of new elements.

Something like:

void inplace_union(vector & A, const vector & B);

Where, afterwards, A contains all of the elements of A union B and is sorted.

std::set_union in <algorithm> wont work because it overwrites its destination, which would be A.

Also, can this be done with just one pass over the two vectors?

Edit: elements that are in both A and B should only appear once in A.

Answer 1

Yes, this can be done in-place, and in O(n) time, assuming both inputs are sorted, and with one pass over both vectors. Here's how:

Extend A (the destination vector) by B.size() - make room for our new elements.

Iterate backwards over the two vectors, starting from the end of B and the original end of A. If the vectors are sorted small → big (big at the end), then take the iterator pointing at the larger number, and stick it in the true end of A. Keep going until B's iterator hits the beginning of B. Reverse iterators should prove especially nice here.

Example:

A: [ 1, 2, 4, 9 ]
B: [ 3, 7, 11 ]

* = iterator, ^ = where we're inserting, _ = unitialized
A: [ 1, 3, 4, 9*, _, _, _^ ]   B: [ 3, 7, 11* ]
A: [ 1, 3, 4, 9*, _, _^, 11 ]  B: [ 3, 7*, 11 ]
A: [ 1, 3, 4*, 9, _^, 9, 11 ]  B: [ 3, 7*, 11 ]
A: [ 1, 3, 4*, 9^, 7, 9, 11 ]  B: [ 3*, 7, 11 ]
A: [ 1, 3*, 4^, 4, 7, 9, 11 ]  B: [ 3*, 7, 11 ]
A: [ 1, 3*^, 3, 4, 7, 9, 11 ]  B: [ 3, 7, 11 ]

Super edit: Have you considered std::inplace_merge? (which I may have just re-invented?)

Answer 2

I believe you can use the algorithm std::inplace_merge. Here is the sample code:

void inplace_union(std::vector<int>& a, const std::vector<int>& b)
{
    int mid = a.size(); //Store the end of first sorted range

    //First copy the second sorted range into the destination vector
    std::copy(b.begin(), b.end(), std::back_inserter(a));

    //Then perform the in place merge on the two sub-sorted ranges.
    std::inplace_merge(a.begin(), a.begin() + mid, a.end());

    //Remove duplicate elements from the sorted vector
    a.erase(std::unique(a.begin(), a.end()), a.end());
}