473,322 Members | 1,352 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

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
Jul 22 '05 #1
9 2500
Hunter Hou wrote:

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() ?

--
Russell Hanneken
eu*******@cbobk.pbz
Use ROT13 to decode my email address.
Jul 22 '05 #2
Hunter Hou wrote in news:cb********@netnews.proxy.lucent.com 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.
--
http://www.victim-prime.dsl.pipex.com/
Jul 22 '05 #3
Rob Williscroft wrote:

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.
Jul 22 '05 #4
Hunter Hou wrote:

Rob Williscroft wrote:

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


???

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
kb******@gascad.at
Jul 22 '05 #5
On Wed, 23 Jun 2004 16:20:07 +0800 in comp.lang.c++, "Hunter Hou"
<hy***@lucent.com> wrote,
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?

Jul 22 '05 #6
"Rob Williscroft" <rt*@freenet.co.uk> wrote in message
news:Xn**********************************@130.133. 1.4...
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
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- e-mail contact form
Jul 22 '05 #7
"Ivan Vecerina" <pl*****************@ivan.vecerina.com> wrote:
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.
--
<mailto:di***********@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting
Jul 22 '05 #8
"Dietmar Kuehl" <di***********@yahoo.com> wrote in message
news:5b**************************@posting.google.c om...
"Ivan Vecerina" <pl*****************@ivan.vecerina.com> wrote:
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.


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


Jul 22 '05 #9
Ivan Vecerina wrote in news:cb**********@newshispeed.ch in comp.lang.c++:
"Rob Williscroft" <rt*@freenet.co.uk> wrote in message
news:Xn**********************************@130.133. 1.4...
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).


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/
Jul 22 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: Kakarot | last post by:
I'm gona be very honest here, I suck at programming, *especially* at C++. It's funny because I actually like the idea of programming ... normally what I like I'm atleast decent at. But C++ is a...
3
by: Kevin King | last post by:
I have a question about an assignment I have. I need to count the number of comparisons in my merge sort. I know that the function is roughly nlog(n), but I am definately coming up with too many...
6
by: cylin | last post by:
Dear all, If I declared a map<int,string> MapA; How can I sort MapA by its data,i.e. string. for example: map<int,string> MapA; MapA=string("ccc"); MapA=string("bbb"); MapA=string("ddd");
4
by: Andreas Kasparek | last post by:
Hola! I'm preparing my master thesis about a XML Merge Tool implementation and was wondering if there is any open standard for XML diff regarding topics like: - is a diff result computed on...
8
by: ilikesluts | last post by:
Hi Group, I'm new to XML, here is my question: Would it be possible to write an algorithm that takes in two XML documents with the only condition being that they have the same root element? ...
5
by: uppe | last post by:
Hey everyone, I've just finished my implementation of the merge-sort algorithm in C, and I thought I could ask for some feedback. (One can always improve, they say) Right now, the code sorts...
9
by: rkk | last post by:
Hi, I have written a generic mergesort program which is as below: --------------------------------------------------------- mergesort.h ----------------------- void MergeSort(void...
7
by: mooon33358 | last post by:
I have a little problem with implementing a recursive merge sort I have to use a function mergesort that takes 3 arguments - an array, its size, and an help array(i.e mergesort(int array, int...
0
by: subramanian100in | last post by:
consider : template<class InIt1, class InIt2, class OutIt> OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt dest); Can the destination container already contain some...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.