why no merge without sorting in STL

[Hunter Hou]

Folks,

I am just curious why standard library doesn't provide a "merge" operation
without sorting, because sometimes I don't require sorting, just merge.


I looked at list.merge() and merge() algorithm, both require sorted
sequenece.
Thanks,
Hunter

 

[Russell Hanneken]

I am just curious why standard library doesn't provide a "merge" operation
without sorting, because sometimes I don't require sorting, just merge.

I looked at list.merge() and merge() algorithm, both require sorted
sequenece.

Maybe you want list.splice() ?

 

[Rob Williscroft]

Hunter Hou wrote in in
comp.lang.c++:

Folks,

I am just curious why standard library doesn't provide a "merge"
operation without sorting, because sometimes I don't require sorting,
just merge.


I looked at list.merge() and merge() algorithm, both require sorted
sequenece.

Isn't this just an *append* operation:

#include <iostream>
#include <ostream>
#include <iterator>
#include <vector>
#include <algorithm>


int main()
{
using namespace std;

vector< int > a, b;
a.push_back( 1 );
b = a;
a.push_back( 2 );

copy( a.begin(), a.end(), back_inserter( b ) );

copy(
b.begin(), b.end(),
ostream_iterator< int >( cout, "\n" )
);
}


Rob.

 

[Hunter Hou]

Isn't this just an *append* operation:

#include <iostream>
#include <ostream>
#include <iterator>
#include <vector>
#include <algorithm>


int main()
{
using namespace std;

vector< int > a, b;
a.push_back( 1 );
b = a;
a.push_back( 2 );

copy( a.begin(), a.end(), back_inserter( b ) );

copy(
b.begin(), b.end(),
ostream_iterator< int >( cout, "\n" )
);
}

Yes. This is a solution, but don't know if it's as efficient as merge if
STL provide .

Since merge without sorting is more general, this is still an intriguing
question.

 

[Karl Heinz Buchegger]

Yes. This is a solution, but don't know if it's as efficient as merge if
STL provide .

Since merge without sorting is more general

???

A merge operation in computing is usually defined as:
merge 2 sorted sequences into 1 sorted sequence

Since merge has to take this into account, it has to do much
more the just simple appending (to answer your fear about efficiency).
While the above is just some data movement, merge also has to compare
items in order to keep the sequence sorted.

So merge does a completely different thing to what you seem to want.

 

[David Harmon]

On Wed, 23 Jun 2004 16:20:07 +0800 in comp.lang.c++, "Hunter Hou"

I looked at list.merge() and merge() algorithm, both require sorted
sequenece.

Merge takes two sorted sequences and produces a sorted sequence.
That's what it does, it's a special purpose tool. If you don't want
sorted sequences, then you want something other than merge, probably
something that is actually much simpler.

What do you want to accomplish?

 

[Ivan Vecerina]

vector< int > a, b;
a.push_back( 1 );
b = a;
a.push_back( 2 );

copy( a.begin(), a.end(), back_inserter( b ) );

~~~~
Just a comment about this idiom, which I see too often.
While a smart compiler+library implementation would be
able to optimize the above call, the following is likely
to be more efficient, and is IMHO more explicit:
b.insert( b.end(), a.begin(), a.end() );

As a rule of thumb, member functions should be preferred
to using a general algorithm (+ the back_inserter adapter here).

Regards,
Ivan

 

[Dietmar Kuehl]

As a rule of thumb, member functions should be preferred
to using a general algorithm (+ the back_inserter adapter here).

I disagree, especially when it comes to generic code: the non-member
functions are the way to go. The library should generally provide
specialized version of the general algorithms wehre feasible - although,
admittedly, most don't. The problem with member function is that they
tend to more restrictive than the non-member algorithms and are thus
unsuitable for generic code. For example, to use 'back_inserter()' with
some object, it merely needs a 'push_back()' operation. This may be a
suitable way to fill data into a custom container. Actually, I'd even
prefer if 'push_back()' were a non-member which would forward be
specialized to forward to suitable member functions.

 

[Ivan Vecerina]

I disagree, especially when it comes to generic code: the non-member
functions are the way to go. The library should generally provide
specialized version of the general algorithms wehre feasible - although,
admittedly, most don't. The problem with member function is that they
tend to more restrictive than the non-member algorithms and are thus
unsuitable for generic code. For example, to use 'back_inserter()' with
some object, it merely needs a 'push_back()' operation.

Really, is it better to use "copy(....,back_inserter(a))" rather than
"a.insert( a.end(), ... )" just because copy is a non-member function ?

The portability argument doesn't really favor the use of push_back,
since all sequence containers are required to provide an insert(p,i,j)
member function, while push_back() is an optional feature (§23.1.1).

And as far as I know, few library implementations (do you know
an example?) actually specialize algorithms on back_inserter...

This may be a
suitable way to fill data into a custom container. Actually, I'd even
prefer if 'push_back()' were a non-member which would forward be
specialized to forward to suitable member functions.

Philosophically, I totally agree with this. I would prefer a standard
library with more non-member functions...

But I prefer to explicitly perform an insertion, than to distort the use
of 'copy' -- which to me suggests that items are being overwritten.
Among two non-member functions, I would still choose 'insert'
( unless of course an "append" algorithm was available )

Kind regards,
Ivan

 

[Rob Williscroft]

Ivan Vecerina wrote in in comp.lang.c++:

~~~~
Just a comment about this idiom, which I see too often.
While a smart compiler+library implementation would be
able to optimize the above call, the following is likely
to be more efficient, and is IMHO more explicit:
b.insert( b.end(), a.begin(), a.end() );

As a rule of thumb, member functions should be preferred
to using a general algorithm (+ the back_inserter adapter here).

Yep I agree, this was my thinking (if it can be called that):

The OP says they want "merge" but actually they want "append".

A quick double-check later there is no std::append, so how
would it be writen ?

... some typing ...

hit [Send].

.

Rob.