Bản đồ STL :: tìm chức năng hoạt động như thế nào nếu không có toán tử bình đẳng?

Question

Dưới mui xe, bản đồ STL là một cây đỏ đen và sử dụng toán tử < của khóa hoặc so sánh do người dùng cung cấp để tìm ra vị trí chèn phần tử.

đồ :: tìm() trả về phần tử phù hợp với chìa khóa cung cấp (nếu có các trận đấu có mặt)

Làm thế nào nó có thể làm điều này mà không sử dụng một nhà điều hành bình đẳng? Giả sử bản đồ của tôi có các khóa 1, 2, 3 và 4 trong đó. Chỉ sử dụng <, tôi có thể thấy rằng khóa 2 nên đi sau 1, sau 2 và trước đó 3. Nhưng tôi không thể biết liệu 2 có giống nhau hay không. 2.

Tôi thậm chí có thể thấy trong/usr /include/c++/4.4.3/bits/stl_tree.h mà tìm() không sử dụng gì ngoài chức năng so sánh do người dùng cung cấp:

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

Bí ẩn. Điểm thưởng nếu bạn có thể cho tôi biết hàm so sánh của tôi sẽ được sử dụng như thế nào trong _M_impl._M_key_compare mà không có vòng lặp rõ ràng.

Answer 1

Nếu (a < b) là false và (b < a) là false, sau đó (a == b). Đây là cách hoạt động của STL's find().

Answer 2

Nó sử dụng !(a<b) && !(b<a)