question on merge algorithm

[subramanian100in]

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 elements ? If so,
will they also be taken into account for doing the sorting and
merging ? Or, should the destination container have just enough space
to hold the result of the merge( that is, it should not contain any
elements) ?

The reason for asking this question is the following:

#include <cstdlib>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iterator>
#include <utility>

using namespace std;

void print(const pair<const int, int>& arg)
{
cout << arg.first << " " << arg.second << endl;
return;
}

int main()
{
typedef pair<int, int> p_type;

multiset<p_type> c1;

c1.insert(make_pair(0, 2));
c1.insert(make_pair(0, 0));
c1.insert(make_pair(0, 1));
c1.insert(make_pair(2, 3));

vector<p_type> c2;

c2.push_back(make_pair(0, -2));
c2.push_back(make_pair(1, 2));
c2.push_back(make_pair(2, 2));

multimap<int, int> c3;

c3.insert(make_pair(5, 0));
c3.insert(make_pair(0, 0));
c3.insert(make_pair(3, 2));
c3.insert(make_pair(0, -1));
c3.insert(make_pair(1, -1));

merge(c1.begin(), c1.end(), c2.begin(), c2.end(), inserter(c3,
c3.begin()));

for_each(c3.begin(), c3.end(), print);

return EXIT_SUCCESS;
}

The output with
g++ -std=c++98 -pedantic -Wall -Wextra x.cpp
is
0 -2
0 0
0 1
0 2
0 0
0 -1
1 -1
1 2
2 2
2 3
3 2
5 0

The second pair (0, 0) in the output should have come before the pair
(0, 1) and
the pair (0, -1) in the output should have come after the pair (0,
-2). Am I correct or wrong ?

Kindly clarify.

Thanks
V.Subramanian

 

[Frank Birbacher]

Hi!

The second pair (0, 0) in the output should have come before the pair
(0, 1) and
the pair (0, -1) in the output should have come after the pair (0,
-2). Am I correct or wrong ?

The multimap only orders keys, that is the first part of the pair. It
does not specify the order of values at all (the second part of the
pair). So you cannot expect the values to be sorted. You would need a
multiset<p_type> for that.

Regards,
Frank

 

[subramanian100in]

Hi!



The multimap only orders keys, that is the first part of the pair. It
does not specify the order of values at all (the second part of the
pair). So you cannot expect the values to be sorted. You would need a
multiset<p_type> for that.

Regards,
Frank

According to the output, the two input sequences are sorted as per the
(key,value) pairs. So I expected that, while inserting the merged
sequence into the destination container, the elements in the
destination container will also be sorted as per (key, value) pair
along with the merged output sequence. Is my understanding correct ?

Is it better to keep the destination container empty(that is, with no
elements) with sufficient space to hold the merged output so that the
above problem doesn't arise at all ? Advice needed on what is done in
such situations.

Kindly explain.

Thanks
V.Subramanian

 

[Kai-Uwe Bux]

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 elements ?
Sure.


If so, will they also be taken into account for doing the sorting and
merging ?

The merge algorithm will not pay any attention to stuff it cannot see. What
happens upon writing to the output-iterator depends on the semantics of
that iterator. A back-inserter will just append.

Or, should the destination container have just enough space
to hold the result of the merge( that is, it should not contain any
elements) ?

The tarted sequence needs to have enough space for whatever gets inserted.
So, in addition to the elements already there, you need enough space for
the new elements. Now, with standard inserters, there is no problem as the
standard containers grow if needed.

The reason for asking this question is the following:

#include <cstdlib>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iterator>
#include <utility>

using namespace std;

void print(const pair<const int, int>& arg)
{
cout << arg.first << " " << arg.second << endl;
return;
}

int main()
{
typedef pair<int, int> p_type;

multiset<p_type> c1;

c1.insert(make_pair(0, 2));
c1.insert(make_pair(0, 0));
c1.insert(make_pair(0, 1));
c1.insert(make_pair(2, 3));

vector<p_type> c2;

c2.push_back(make_pair(0, -2));
c2.push_back(make_pair(1, 2));
c2.push_back(make_pair(2, 2));

multimap<int, int> c3;

c3.insert(make_pair(5, 0));
c3.insert(make_pair(0, 0));
c3.insert(make_pair(3, 2));
c3.insert(make_pair(0, -1));
c3.insert(make_pair(1, -1));

merge(c1.begin(), c1.end(), c2.begin(), c2.end(), inserter(c3,
c3.begin()));

for_each(c3.begin(), c3.end(), print);

return EXIT_SUCCESS;
}

The output with
g++ -std=c++98 -pedantic -Wall -Wextra x.cpp
is
0 -2
0 0
0 1
0 2
0 0
0 -1
1 -1
1 2
2 2
2 3
3 2
5 0

The second pair (0, 0) in the output should have come before the pair
(0, 1) and
the pair (0, -1) in the output should have come after the pair (0,
-2). Am I correct or wrong ?

Wrong.

What happens here is unrelated to the merge algorithm since you insert the
elements into a multimap, which then decided autonomously where to insert
the element. With regard to the output, you just observed that a multimap
makes no guarantees as to the order in which elements with identical keys
are stored: neither does it guarantee that they are ordered by value nor
does it guarantee that they are ordered by time of insertion.


Best

Kai-Uwe Bux

 

[Frank Birbacher]

Hi!

According to the output, the two input sequences are sorted as per the
(key,value) pairs. So I expected that, while inserting the merged
sequence into the destination container, the elements in the
destination container will also be sorted as per (key, value) pair
along with the merged output sequence. Is my understanding correct ?

No. The multiset/map containers do not keep ordering at all. If you need
to preserve the value order you need to use a different container.

set/map do not have a "push_back" method for that reason: you cannot
push a value to the end of a map. You can only "insert" it. The new
location for the inserted element is determined by the implementation of
the map.

To make you understand a little better: the map is (usually) implemented
as a balanced binary tree. The housekeeping of the tree, the insertion
and deletion algorithms on such trees, all of that destroys the order of
inserted elements.

Is it better to keep the destination container empty(that is, with no
elements) with sufficient space to hold the merged output so that the
above problem doesn't arise at all ? Advice needed on what is done in
such situations.

The state of the output container does not affect the problem. A
multimap will not keep the value order, regardless if its empty,
partially filled, or holds half of your memory.

An empty multimap won't help at all.

You need a set<pair<int, int> >.

Frank