Multiple successive merges with STL's merge

D

Digital Puer

I would like to merge together several STL integer vectors using STL's
merge() function. What is the best way to do this while avoiding
unnecessary vector copying?

Is the following a good approach?



vector<vector<int> > data; // already filled up properly with integers
vector<int> result; // temp space
vector<int> result2; // temp space

result = data.at(0); // unnecessary copying?

for (int i = 0; i < data.size(); i++)
{
result2.resize(result.size() + data.at(i).size()); // is this needed?

merge(result.begin(), result.end(), data.at(i).begin(),
data.at(i).end(), result2.begin());

result = result2; // unnecessary copying?

}

return result;
 
D

Dietmar Kuehl

Digital said:
Is the following a good approach?

Well, not really...
vector<vector<int> > data; // already filled up properly with integers
vector<int> result; // temp space

OK, you need one vector with the final result.
vector<int> result2; // temp space

.... but you don't need a second temporary vector at this level.
result = data.at(0); // unnecessary copying?

.... nor do need to copy it here. I would start by merging the
first two vectors to initialize 'result' and then process all
others in the loop. In addition, I would only 'reserve()' sufficient
space instead of resizing the vector. Finally, I would 'swap()' the
temporary result instead of copy assigning it:

if (1 == data.size())
result = data[0]; // OK - there is only one vector...
else if (2 <= data.size()
{
result.reserve(data[0].size() + data[1].size());
std::merge(data[0].begin(), data[0].end(),
data[1].begin(), data[1].end(),
std::back_inserter(result));

for (std::vector<int>::size_type idx = 2; idx < data; ++idx)
{
std::vector<int> tmp;
tmp.reserve(result.size() + data[idx].size());
stsd::merge(result.begin(), result.end(),
data[idx].begin(), data[idx].end(),
std::back_inserter(tmp));
tmp.swap(result);
}
}

BTW, I think your loop actually merges the first sequence twice
which is probably an error. This is avoided with my code, too.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top