How does the STL map::find function work without the equality operator?

Under the hood, an STL map is a red-black tree, and it uses the < operator of its keys or a user-provided comparison to figure out the location for element insertion.

map::find() returns the element that matches the supplied key开发者_如何学JAVA (if any matches are present)

How can it do this without using an equality operator? Let's say my map has the keys 1, 2, 3, and 4 in it. Using only <, I could see that the key 2 should go after 1, after 2, and before 3. But I can't tell whether or not 2 is the same as 2.

I can even see in /usr/include/c++/4.4.3/bits/stl_tree.h that find() uses nothing but the user-supplied comparison function:

template<typename _Key, typename _Val, typename _KeyOfValue,
       typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue,
          _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
find(const _Key& __k)
{
  iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
  return (__j == end()
      || _M_impl._M_key_compare(__k,
                _S_key(__j._M_node))) ? end() : __j;
}

Cryptic. Bonus points if you can tell me how my comparison function ends up being used in _M_impl._M_key_compare without an obvious loop.

If (a < b) is false and (b < a) is false, then (a == b). This is how STL's find() works.

It uses !(a<b) && !(b<a)