STL - STL map::find 函数在没有相等运算符的情况下如何工作？

Question

在幕后，STL 映射是一棵红黑树，它使用其键的 < 运算符或用户提供的比较来确定元素插入的位置。

map::find() 返回与提供的键匹配的元素(如果存在任何匹配)

不使用相等运算符如何做到这一点？假设我的 map 中有键 1、2、3 和 4。仅使用 <，我可以看到键 2 应该在 1 之后、2 之后和 3 之前。但我不知道 2 是否与 2 相同。

我什至可以在/usr/include/c++/4.4.3/bits/STL_tree.h 中看到 find() 只使用用户提供的比较函数:

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;
}

神秘。如果您能告诉我我的比较函数最终如何在 _M_impl._M_key_compare 中使用，则可以获得加分。没有明显的循环。

Answer 1

如 (a < b)是 false和 (b < a)是 false ，然后 (a == b) .这就是STL的find()作品。