Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

find

map

stl

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 (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.

like image 463
Jim Hunziker Avatar asked Jul 13 '10 19:07

Jim Hunziker


2 Answers

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

like image 150
TreDubZedd Avatar answered Feb 07 '23 04:02

TreDubZedd


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

like image 39
Yogesh Arora Avatar answered Feb 07 '23 04:02

Yogesh Arora