electrikAdic

Hi,

I have an object X in which I've overloaded operator== and operator<. I am using X as the key into a map.

The implementation for Visual Studio's stl find looks like this:

iterator find(const key_type& _Keyval)
{ // find an element in mutable sequence that matches _Keyval
iterator _Where = lower_bound(_Keyval);

return (_Where == end()
|| _DEBUG_LT_PRED(this->comp,
_Keyval, _Key(_Where._Mynode()))
end() : _Where);
}}


Basically, take the lower_bound, and then do an equality comparison. lower_bound, calls my overloaded operator<....which is what I expect it to do. However the equality comparison doesn't call my operator==.

Is find() broken and only doing a lower_bound Or am I missing something

-Terry



Re: Visual C++ Language possible bug in std::map::find?

Holger Grund

I don't see any problems with that code (except that I don't think the identifier comp is reserved to the implementation). Where do you see an equality comparison of your object type in this code snippet

I only see one == which is obviously on the iterator, so your type is not involved there.

Unless there's some really odd naming _DEBUG_LT_PRED does a less than comparision with the container's comparer.

The implementation doesn't call operator== and neither should it. It just does a lower_bound and then compares the key of the element with the key provided. If these are identical (implied by ! key<lower_bound) then everything's fine.

-hg





Re: Visual C++ Language possible bug in std::map::find?

Anders Dalvander

The implementation of std::map::find look good.
It's probably X :: operator< that doesn't conform to the strict weak ordering concept. http://www.sgi.com/tech/stl/StrictWeakOrdering.html

All other comparison operators can be implemented in terms of an operator< that conforms to the strict weak ordering concept, see below for example.

struct foo
{
int a, b, c, d;
};

bool operator<(const foo& lhs, const foo& rhs)
{
if (lhs.a < rhs.a)
return true;
if (rhs.a < lhs.a)
return false;

if (lhs.b < rhs.b)
return true;
if (rhs.b < lhs.b)
return false;

if (lhs.c < rhs.c)
return true;
if (rhs.c < lhs.c)
return false;

if (lhs.d < rhs.d)
return true;
if (rhs.d < lhs.d) // the last comparison can be removed,
return false; // as we return false no matter what.

return false;
}

bool operator>(const foo& lhs, const foo& rhs)
{
return rhs < lhs;
}

bool operator<=(const foo& lhs, const foo& rhs)
{
return !(rhs < lhs);
}

bool operator>=(const foo& lhs, const foo& rhs)
{
return !(lhs < rhs);
}

bool operator==(const foo& lhs, const foo& rhs)
{
return !(lhs < rhs) && !(rhs < lhs);
}

bool operator!=(const foo& lhs, const foo& rhs)
{
return lhs < rhs || rhs < lhs;
}





Re: Visual C++ Language possible bug in std::map::find?

einaros

This boils down to the difference between equality and equivalence. Equivalence is reached if neither values proceeds the other, and that rules out the use of operator==.