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.
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());
}
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?)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With