A simple merge could be
/* THE MERGE FUNCTION
* Appends vector b to a
* Call by constant reference for better performance
*/
vector<int> merge(const vector<int>& a, const vector<int>& b) {
// Initialise the result vector
vector<int> result;
// Push back the elements of a
for (auto& n : a)
result.push_back(n);
// Push back the elements of b
for (auto& n : b)
result.push_back(n);
return result;
}
Although the performance boost is marginal for small vectors a and b, the advantage of passing by constant reference would be more noticeable if you're - say - working with two vectors having a few thousand elements each. This is also the reason the foreach loops use auto& n instead of auto n. The time that would've been spent copying stuff into the local variables for the function can be saved by using a reference. At the same time, to safeguard against accidental changes, the arguments are both made const. I have a pretty fast rig, but with a vector a of size 1000 and b of size 2500, I get a running time of 586.998 milliseconds without the &s and 531.03 milliseconds with the &s.
Interestingly, you can templatise the whole thing to generalise it to any type. The only constraint is that both a and b should be vectors of the same type (comments omitted for brevity).
template <typename T>
vector<T> merge(const vector<T>& a, const vector<T>& b) {
vector<T> result;
for (auto& n : a)
result.push_back(n);
for (auto& n : b)
result.push_back(n);
return result;
}
An interleaved merge would mean you'd have to iterate by indices and push back the element at the current index. Assuming the vectors are both the same size:
template <typename T>
vector<T> merge(const vector<T>& a, const vector<T>& b) {
vector<T> result;
int size = a.size(); // Also b.size
for (int i = 0; i < size; ++i) {
result.push_back(a.at(i)); // ith element of a
result.push_back(b.at(i)); // ith element of b
}
return result;
}
There is a problem when the vectors are of different sizes. In that case, you interleave until you have elements in both vectors, and dump the rest of the values from the larger vector in after that. The logic thus goes
- Interleave as much as you can
- Dump the remaining elements from the larger vector
/* THE MERGE FUNCTION
* Interleaved merge
* Call by constant reference for better performance
*/
template <typename T>
vector<T> merge(const vector<T>& a, const vector<T>& b) {
vector<T> result; // result vec
// sizes
int sizeA = a.size();
int sizeB = b.size();
// Could make this block another function min(a, b)
int interleavedSize = (sizeA > sizeB) ? sizeB : sizeA; // the smaller of a and b
int i = 0; // we need this to persist outside the loop
// At the end of this loop, i is the smaller of sizeA and sizeB
for (i = 0; i < interleavedSize; ++i) {
result.push_back(a.at(i)); // ith element of a
result.push_back(b.at(i)); // ith element of b
}
if (i == sizeA) // b is the larger vector
for (; i < sizeB; ++i) // dump the remaining elements of b
result.push_back(b.at(i));
else if (i == sizeB) // a is the larger vector
for (; i < sizeA; ++i) // dump the remaining elements of a
result.push_back(a.at(i));
return result;
}
