Re: multimap question
Ben wrote:
Hi,
Is there any use for the multimap equality comparison operator, apart
from testing literal object identity? Running the following code in VC
7.1
std::multimap<int, int> m1;
m1.insert(std::make_pair(1, 1));
m1.insert(std::make_pair(1, 2));
std::multimap<int, int> m2;
m2.insert(std::make_pair(1, 2));
m2.insert(std::make_pair(1, 1));
bool res = m1 == m2;
gives res == false, which means that multimaps are insertion order
dependent.
This kind of rules out comparing then unless you know the insertion
order was stable, which is often unlikely to be the case.
One solution would be to use a multiset instead of a multimap. In that
way the the container would use both the key and the value when
ordering its contents.
One drawback with combining the key and the value for storage in a
multiset is that searching by the key alone is no longer directly
supported. Nonetheless, by specifying a key type that has two
variations: one for storage and another - less specified - type for
searching, it is possible use the multiset as if it were a multimap -
and also be certain that containers with identical contents will
compare as equal.
The implementation below uses double-dispatched virtual function calls
to overloaded operators in order to ensure that if either operand in a
key comparison is a partial key type, then only the key portion of the
stored values is considered. Note that the sample implementation below
has tried to favor elegance over efficiency - no doubt the overhead of
the key comparisons could be reduced.
#include <iostream>
#include <set>
using std::pair;
// combines key with value
struct KeyValue : public std::pair<int, int>
{
KeyValue(int one, int two ) : pair<int, int>(one, two){}
virtual
bool operator<(const KeyValue& rhs) const
{
return not( rhs >= *this);
}
virtual
bool operator>=( const KeyValue& rhs) const
{
return first < rhs.first ? false :
first > rhs.first ? true :
second < rhs.second ? false :
true;
}
};
// for searches on key value alone
struct PartialKey : public KeyValue
{
PartialKey(int i) : KeyValue(i, 0) {}
virtual
bool operator<(const KeyValue& rhs) const
{
return first < rhs.first;
}
virtual
bool operator>=(const KeyValue& rhs) const
{
return first >= rhs.first;
}
};
int main()
{
std::multiset<KeyValue> m1;
m1.insert( KeyValue(1, 1));
m1.insert( KeyValue(1, 2));
std::multiset<KeyValue> m2;
m2.insert( KeyValue(1, 2));
m2.insert( KeyValue(1, 1));
bool res = m1 == m2;
std::cout << "m1 == m2 is ";
std::cout << std::boolalpha << res;
std::cout << std::endl;
// use a partial key to count all values
// whose first member is equal to 1
int keyCount = m2.count( PartialKey(1));
std::cout << "count of Key 1 in m2: " << keyCount << "\n";
}
Output:
m1 == m2 is true
count of Key 1 in m2: 2
Greg
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]