How does the == operator for multimaps behave ?

[Nikhil.S.Ketkar]

Hi,

How does the == operator for multimap in STL behave ? I was under the
impression that this is supposed to properly compare multimaps for
equality. It seems that what it actually does is just check if each
member in location L in one multimap is equal to the the member in
location L in the other multimap. The documentation on
http://www.sgi.com/tech/stl/Multimap.html says "Tests two multimaps
for equality. This is a global function, not a member function." and
nothing more.

Am I missing something ?
I have added an illustrative program with output.

Thanks,
Nikhil

#include <iostream>
#include <map>

int main(int argc, char *argv)
{
int numbers[] = {1,2,3,4,5};

std::multimap<int, int> a;
a.insert(std:air<int, int>(numbers[0], numbers[2]));
a.insert(std:air<int, int>(numbers[0], numbers[4]));
a.insert(std:air<int, int>(numbers[1], numbers[3]));
a.insert(std:air<int, int>(numbers[2], numbers[2]));
a.insert(std:air<int, int>(numbers[2], numbers[4]));


std::multimap<int, int> b;
b.insert(std:air<int, int>(numbers[0], numbers[2]));
b.insert(std:air<int, int>(numbers[0], numbers[4]));
b.insert(std:air<int, int>(numbers[1], numbers[3]));
b.insert(std:air<int, int>(numbers[2], numbers[2]));
b.insert(std:air<int, int>(numbers[2], numbers[4]));


std::cout << "Multimap a and b were found to be ";
if (a == b)
std::cout << "equal.\n";
else
std::cout << "unequal.\n";

std::multimap<int, int> c;
c.insert(std:air<int, int>(numbers[0], numbers[4]));
c.insert(std:air<int, int>(numbers[0], numbers[2]));
c.insert(std:air<int, int>(numbers[1], numbers[3]));
c.insert(std:air<int, int>(numbers[2], numbers[2]));
c.insert(std:air<int, int>(numbers[2], numbers[4]));

std::cout << "Multimap a and c were found to be ";
if (a == c)
std::cout << "equal.\n";
else
std::cout << "unequal.\n";

return 0;
}

// Output
//------------------------------------------------------------------------------
// Multimap a and b were found to be equal.
// Multimap a and c were found to be unequal.
//------------------------------------------------------------------------------

 

[Erik Wikström]

Hi,

How does the == operator for multimap in STL behave ? I was under the
impression that this is supposed to properly compare multimaps for
equality. It seems that what it actually does is just check if each
member in location L in one multimap is equal to the the member in
location L in the other multimap.

Yes, it checks if the two multimaps are equal, and two multimaps are
equal if all the contained elements are equal. Perhaps you wanted to
check for identity, if two references/pointers to multimaps referes to
the same multimap? In that case compare the addresses of the objects
referred to.

 

[Kai-Uwe Bux]

Hi,

How does the == operator for multimap in STL behave ? I was under the
impression that this is supposed to properly compare multimaps for
equality.
Yes.

It seems that what it actually does is just check if each
member in location L in one multimap is equal to the the member in
location L in the other multimap.

Well, that is how "equality" is defined for containers. If you think there
is a difference, maybe you want to explain what you mean by "properly
equal" (as opposed to just "equal").

Anyway, table 65 (Container requirements) defines the semantics of "==" for
all containers as

a == b
if and only if
a.size() == b.size() and equal( a.begin(), a.end(), b.begin(), b.end() )

The documentation on
http://www.sgi.com/tech/stl/Multimap.html says "Tests two multimaps
for equality. This is a global function, not a member function." and
nothing more.

Am I missing something ?
I have added an illustrative program with output.

Thanks,
Nikhil

#include <iostream>
#include <map>

int main(int argc, char *argv)
{
int numbers[] = {1,2,3,4,5};

std::multimap<int, int> a;
a.insert(std:air<int, int>(numbers[0], numbers[2]));
a.insert(std:air<int, int>(numbers[0], numbers[4]));
a.insert(std:air<int, int>(numbers[1], numbers[3]));
a.insert(std:air<int, int>(numbers[2], numbers[2]));
a.insert(std:air<int, int>(numbers[2], numbers[4]));


std::multimap<int, int> b;
b.insert(std:air<int, int>(numbers[0], numbers[2]));
b.insert(std:air<int, int>(numbers[0], numbers[4]));
b.insert(std:air<int, int>(numbers[1], numbers[3]));
b.insert(std:air<int, int>(numbers[2], numbers[2]));
b.insert(std:air<int, int>(numbers[2], numbers[4]));


std::cout << "Multimap a and b were found to be ";
if (a == b)
std::cout << "equal.\n";
else
std::cout << "unequal.\n";

std::multimap<int, int> c;
c.insert(std:air<int, int>(numbers[0], numbers[4]));
c.insert(std:air<int, int>(numbers[0], numbers[2]));
c.insert(std:air<int, int>(numbers[1], numbers[3]));
c.insert(std:air<int, int>(numbers[2], numbers[2]));
c.insert(std:air<int, int>(numbers[2], numbers[4]));

std::cout << "Multimap a and c were found to be ";
if (a == c)
std::cout << "equal.\n";
else
std::cout << "unequal.\n";

return 0;
}

// Output
//------------------------------------------------------------------------------
// Multimap a and b were found to be equal.
// Multimap a and c were found to be unequal.
//------------------------------------------------------------------------------

This output is correct.

BTW: what is the motivation to use such an indirect way of specifying the
elements of the maps (by using the array "numbers")?



Best

Kai-Uwe Bux

 

[Nikhil.S.Ketkar]

Thanks. That makes it quite clear.


The way I thought about it is that a multimap is a many-to-many
function and that equality of multimap implies that the functions are
identical. That is if I have two sets X = {1,2,3} and Y = {2,3,4} and
two functions from X to Y, say A = {1->2, 2->3, 3->4} and B = {1->2, 3-

4, 2->3}, A is equal to B as the order does not matter, only the

mapping.

The example is just something I made up to make my question clear, I
was actually comparing two multimaps representing many-to-many
functions on two sets. I guess I will have to write that on my own.


Thanks again,
Nikhil

 

[Kai-Uwe Bux]

Thanks. That makes it quite clear.


The way I thought about it is that a multimap is a many-to-many
function and that equality of multimap implies that the functions are
identical.

That is correct from a practical point of view. How did you run into
violations of that notion?

That is if I have two sets X = {1,2,3} and Y = {2,3,4} and
two functions from X to Y, say A = {1->2, 2->3, 3->4} and B = {1->2, 3-
mapping.

Well, as long as you don't provide your own comparison predicate, the
multimap will be sorted in ascending order. So, in your example, B will
simply not happen since the multimap _will_ store the argument-value pairs
in the order

1->2 2->3 3->4

It will _not_ store the pairs in order of insertion.

Therefore, only the mapping matters as long as the order defaults to the one
given by std::less. Only if you provide your own comparison predicates, you
can tweak the ordering of std::multimap.



Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

That is correct from a practical point of view. How did you run into
violations of that notion?


Well, as long as you don't provide your own comparison predicate, the
multimap will be sorted in ascending order. So, in your example, B will
simply not happen since the multimap _will_ store the argument-value pairs
in the order

1->2 2->3 3->4

It will _not_ store the pairs in order of insertion.

Therefore, only the mapping matters as long as the order defaults to the
one given by std::less. Only if you provide your own comparison
predicates, you can tweak the ordering of std::multimap.

Oops: correction.

The multimap is only sorted by keys. If you use the same key twice, then the
order of insertion does matter. Sorry for the confusion. The example drove
me in that direction.


Anyway, as a fix, you could use:

std::map< key_type, std::set< mapped_type > >

which models multivalued functions as set-valued functions.


Best

Kai-Uwe Bux