STL Help for a newbie

[Deepak]

Hello,
I am working on a project where I am using the STL's "map"
datastructure inside a class that just acts as a container for the map
and manages it. The map a Key class to integers. The Key class just
has two variables of user defined types. I had implemented the key
comprarer structure that map requires like so:

struct KeyComparer
{
bool operator() (const Key & k1, const Key & k2) const
{
return ((k1.getA() < k2.getA()) &&
(k1.getB() < k2.getB()));
}
};


What i am finding is that whenever i use the maps internal functions
such as find(..) or insert(...) it doesnt work.
I have overloaded the '<', '==', and '=' operators, have copy
constructors/assignment operators defined.

It seems like the find() is just comparing one of the two components
of Key and therefore does not do the correct comparison even though i
defined the comparer.
The insert seems like it just doesnt insert beyond the first entry.
I would really appreciate if someone could provide me with insight as
to how to tackle this problem. Any help is appreciated.
Sincerely,
D

 

[John Harrison]

Hello,
I am working on a project where I am using the STL's "map"
datastructure inside a class that just acts as a container for the map
and manages it. The map a Key class to integers. The Key class just
has two variables of user defined types. I had implemented the key
comprarer structure that map requires like so:

struct KeyComparer
{
bool operator() (const Key & k1, const Key & k2) const
{
return ((k1.getA() < k2.getA()) &&
(k1.getB() < k2.getB()));
}
};


What i am finding is that whenever i use the maps internal functions
such as find(..) or insert(...) it doesnt work.

Your comparator is wrong. It doesn't do a less than comparison. What you
probably want is this

struct KeyComparer
{
bool operator() (const Key & k1, const Key & k2) const
{
return k1.getA() < k2.getA() || (!(k2.getA() < k1.getA()) && k1.getB() <
k2.getB()));
}
};

When you have a pair of keys then the combined key is less than if the first
key is less than, OR if the first key is equal AND the second key is less
than.

Your comparotor simply doesn't do anything like a less than comparison so
map gets confused.

john

 

[David Fisher]

Your comparator is wrong. It doesn't do a less than comparison.

[snip]

Simple example of why the comparison function is incorrect (assuming integer
values and the existence of a Key(int a, int b) constructor):

Key(1, 5) < Key(5, 1) returns false
Key(5, 1) < Key(1, 5) returns false

If A < B is false, and A > B is false, and A does not equal B, then there is
a problem ...

David Fisher
Sydney, Australia

 

[John Harrison]

Your comparator is wrong. It doesn't do a less than comparison.

[snip]

Simple example of why the comparison function is incorrect (assuming integer
values and the existence of a Key(int a, int b) constructor):

Key(1, 5) < Key(5, 1) returns false
Key(5, 1) < Key(1, 5) returns false

If A < B is false, and A > B is false, and A does not equal B, then there is
a problem ...

Whether Key(1, 5) equals Key(5, 1) is up to the OP (although I suspect its
not what the OP intended). In itself this isn't an error. But consider this

Key x(1, 3);
Key y(3, 1);
Key z(2, 4);

Here we have x < y is false, and y < x is false, which implies x == y
Also we have y < z is false, and z < y is false, which implies y == z
But x < z, so we have x== y and y == z but x < z. That is an error because
it breaks the rule that equality must be transitive.

john

 

[Deepak]

Great Thanks guys. I understand the issue. Its rather clear now.
I hope this change solves my problems.
Thanks to google groups.
Regards

Deepak wrote:
struct KeyComparer
{
bool operator() (const Key & k1, const Key & k2) const
{
return ((k1.getA() < k2.getA()) &&
(k1.getB() < k2.getB()));
}
};


What i am finding is that whenever i use the maps internal functions
such as find(..) or insert(...) it doesnt work.

Your comparator is wrong. It doesn't do a less than comparison.

[snip]

Simple example of why the comparison function is incorrect (assuming integer
values and the existence of a Key(int a, int b) constructor):

Key(1, 5) < Key(5, 1) returns false
Key(5, 1) < Key(1, 5) returns false

If A < B is false, and A > B is false, and A does not equal B, then there is
a problem ...

Whether Key(1, 5) equals Key(5, 1) is up to the OP (although I suspect its
not what the OP intended). In itself this isn't an error. But consider this

Key x(1, 3);
Key y(3, 1);
Key z(2, 4);

Here we have x < y is false, and y < x is false, which implies x == y
Also we have y < z is false, and z < y is false, which implies y == z
But x < z, so we have x== y and y == z but x < z. That is an error because
it breaks the rule that equality must be transitive.

john

 

[Deepak]

John
From your explanation was this what you meant?
struct KeyComparer
{
bool operator() (const Key & k1, const Key & k2) const
{
return k1.getA() < k2.getA() || ((k2.getA()== k1.getA()) && k1.getB() <
k2.getB()));
}
};


You suggested a slightly different comparison operator?
Deepak

 

[John Harrison]

John
From your explanation was this what you meant?
struct KeyComparer
{
bool operator() (const Key & k1, const Key & k2) const
{
return k1.getA() < k2.getA() || ((k2.getA()== k1.getA()) && k1.getB()
<
k2.getB()));
}
};


You suggested a slightly different comparison operator?
Deepak

They should be the same, mine only uses operator< while yours assumes that
Key has both operator< and operator==.

john