Re: C++ merge
Ivan Novick <ivan@0x4849.net> wrote:
Hi,
Given 2 (large) sequences of sorted data, is there an efficient way in
C++ to merge the sequences.
This seems to be the available option:
std::merge(names1.begin(), names1.end(), names2.begin(), names2.end(),
std::back_inserter(result));
But it appears to allocate new memory for a third list and copy the
data. I would like to be able to merge without allocating new memory
and copying the data.
Thank you,
Ivan
In order to merge you must copy something at least under the hood:)
If you don't want to copy the type being merged then perhaps if they
are stored std::list<T,A>'s then a third list can be constructed by
splicing from one of the original lists into the third. Only the list
ptrs [internal ones] change and its simple to write something like;
/*
merge A amd B returning result in A.
not no copy of user data only internals of std;:list
change.
*/
template <class T,class A,class Pred = std::less<T> >
void merge(std::list<T,A> &X,std::list<T,A> &Y,Pred pred)
{
std::list<T,A> C;
while(!A.empty() && !B.empty())
{
if(pred(A.front(),B.front())
{
C.splice(C.end(),A,A.begin());
}
else
{
C.splice(C.end(),B,B.begin());
}
}
C.splice(C.end(),A);
C.splice(c.end(),B);
A.swap(C);
}
list is handy for large objects that don't need random access.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]