why no merge without sorting in STL

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

re: why no merge without sorting in STL

Hunter Hou wrote:[color=blue]
>
> 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.[/color]

Maybe you want list.splice() ?

--
Russell Hanneken
eunaarxra@cbobk.pbz
Use ROT13 to decode my email address.

re: why no merge without sorting in STL

Hunter Hou wrote in news:cbbe7o$772@netnews.proxy.lucent.com in
comp.lang.c++:
[color=blue]
> 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.[/color]

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.
--
http://www.victim-prime.dsl.pipex.com/

re: why no merge without sorting in STL

Rob Williscroft wrote:
[color=blue]
>
> 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" )
> );
> }
>[/color]
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.

re: why no merge without sorting in STL

Hunter Hou wrote:[color=blue]
>
> Rob Williscroft wrote:
>[color=green]
> >
> > 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" )
> > );
> > }
> >[/color]
> 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[/color]

???

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.

--
Karl Heinz Buchegger
kbuchegg@gascad.at

re: why no merge without sorting in STL

On Wed, 23 Jun 2004 16:20:07 +0800 in comp.lang.c++, "Hunter Hou"
<hyhou@lucent.com> wrote,[color=blue]
>I looked at list.merge() and merge() algorithm, both require sorted
>sequenece.[/color]

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?

re: why no merge without sorting in STL

"Rob Williscroft" <rtw@freenet.co.uk> wrote in message
news:Xns9511611D6D3BEukcoREMOVEfreenetrtw@130.133. 1.4...[color=blue]
> vector< int > a, b;
> a.push_back( 1 );
> b = a;
> a.push_back( 2 );
>
> copy( a.begin(), a.end(), back_inserter( b ) );[/color]
~~~~
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
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- e-mail contact form

re: why no merge without sorting in STL

"Ivan Vecerina" <please_use_web_form@ivan.vecerina.com> wrote:[color=blue]
> As a rule of thumb, member functions should be preferred
> to using a general algorithm (+ the back_inserter adapter here).[/color]

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.
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting

re: why no merge without sorting in STL

"Dietmar Kuehl" <dietmar_kuehl@yahoo.com> wrote in message
news:5b15f8fd.0406240216.6780f9ab@posting.google.c om...[color=blue]
> "Ivan Vecerina" <please_use_web_form@ivan.vecerina.com> wrote:[color=green]
> > As a rule of thumb, member functions should be preferred
> > to using a general algorithm (+ the back_inserter adapter here).[/color]
>
> 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.[/color]

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...
[color=blue]
> 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.[/color]

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

re: why no merge without sorting in STL

Ivan Vecerina wrote in news:cbdrp6$7bi$1@newshispeed.ch in comp.lang.c++:
[color=blue]
> "Rob Williscroft" <rtw@freenet.co.uk> wrote in message
> news:Xns9511611D6D3BEukcoREMOVEfreenetrtw@130.133. 1.4...[color=green]
>> vector< int > a, b;
>> a.push_back( 1 );
>> b = a;
>> a.push_back( 2 );
>>
>> copy( a.begin(), a.end(), back_inserter( b ) );[/color]
> ~~~~
> 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).
>[/color]

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.
--
http://www.victim-prime.dsl.pipex.com/