Comment fonctionne la fonction STL map :: find sans l'opérateur d'égalité?

Sous le capot, une carte STL est un arbre rouge-noir et utilise l'opérateur < de ses clés ou une comparaison fournie par l'utilisateur pour déterminer l'emplacement de l'insertion d'élément.Comment fonctionne la fonction STL map :: find sans l'opérateur d'égalité?

carte :: find() retourne l'élément correspondant à la clé fournie (si les correspondances sont présents)

Comment peut-il faire cela sans l'aide d'un opérateur d'égalité? Disons que ma carte contient les touches 1, 2, 3 et 4. En utilisant seulement <, je pouvais voir que la clé 2 devrait aller après 1, après 2, et avant 3. Mais je ne peux pas dire si 2 est la même chose que 2.

Je peux même voir/usr /include/c++/4.4.3/bits/stl_tree.h que find() utilise rien que la fonction de comparaison fournie par l'utilisateur:

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. Points bonus si vous pouvez me dire comment ma fonction de comparaison finit par être utilisé dans _M_impl._M_key_compare sans une boucle évidente.

Source

2010-07-13 Jim Hunziker