Come funziona la funzione STL map :: find senza l'operatore di uguaglianza?

Sotto il cofano, una mappa STL è un albero rosso-nero e utilizza l'operatore < delle sue chiavi o un confronto fornito dall'utente per determinare la posizione per l'inserimento dell'elemento.Come funziona la funzione STL map :: find senza l'operatore di uguaglianza?

mappa :: find() restituisce l'elemento che corrisponde la chiave in dotazione (se eventuali partite sono presenti)

come può fare questo senza usare un operatore di uguaglianza? Diciamo che la mia mappa ha le chiavi 1, 2, 3 e 4 in essa. Usando solo <, ho potuto vedere che la chiave 2 dovrebbe andare dopo 1, dopo 2 e prima 3. Ma non posso dire se 2 è uguale a 2.

Posso persino vedere in/usr /include/c++/4.4.3/bits/stl_tree.h che find() utilizza nient'altro che la funzione di comparazione fornita dall'utente:

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. Punti bonus se puoi dirmi come la mia funzione di confronto finisce per essere utilizzata in _M_impl._M_key_compare senza un ciclo ovvio.

fonte

2010-07-13 Jim Hunziker