为何std::map需实现operator<？自定义对象键的比较疑问

首先先把你给出的示例代码修正补充一下（补充分号、构造函数实现，把String改为标准库的std::string），方便大家参考：

#include <string>
#include <map>
#include <iostream>

struct example{
 example( int id, std::string stuff) : id(id), stuff(stuff) {} 
 int id;
 std::string stuff;
 bool operator<( const example& rhs ) const;
};

bool example::operator<( const example& rhs ) const {
 if( id < rhs.id ) return true;
 if( rhs.id < id ) return false;
 if( stuff < rhs.stuff ) return true;
 if( rhs.stuff < stuff ) return false;
 return false;
}

接下来逐个解答你的疑问：

1. 为何std::map要求实现operator<运算符？是否因为其后台采用二分查找匹配键？ #

嘿，这个问题问到点子上了！std::map的底层实现是红黑树——一种自平衡的二叉搜索树。二叉搜索树的核心逻辑就是依赖元素的大小比较来维护树的结构：插入新节点时要找到合适的位置，查找节点时要顺着比较结果走左/右子树，这些操作都需要一个明确的“顺序规则”。

operator<就是默认用来定义这个规则的，它需要满足严格弱序（strict weak ordering）的要求。二分查找是红黑树查找操作的特性，但本质上是红黑树需要这个比较运算符来维持结构，保证所有操作都能在O(log n)的时间复杂度内完成。当然，你也可以不用operator<，给std::map传一个自定义的比较器（比如用std::less以外的函数对象），但默认情况下必须提供operator<。

2. 即便用二分查找，最终仍需判断对象是否相等，为何无需实现operator==？ #

这是std::map的一个巧妙设计：它并不直接依赖operator==来判断键是否相等，而是通过你提供的operator<来推导等价性。具体来说，对于两个键a和b，如果!(a < b) && !(b < a)，就认为它们是等价的（equivalent），在map里会被当作同一个键。

这种设计的好处是，你只需要维护一个比较规则（operator<），就能同时满足排序和等价判断的需求，避免了重复定义两个运算符可能带来的不一致问题。只要你的operator<符合严格弱序的要求，这种推导出来的等价关系就会满足等价性的三个条件：自反性、对称性、传递性。

3. 执行你给出的代码，程序如何识别新创建的example(1,"a")与map中首个条目为同一键？运行后会输出"hello"吗？ #

答案是：会输出"hello"！

原因就是刚才提到的等价性判断逻辑：你新创建的example(1,"a")和map里的example1，用你实现的operator<比较时，example1 < example(1,"a")会返回false（因为id和stuff都相等），反过来example(1,"a") < example1也返回false。所以std::map会判定这两个对象是等价的，也就是同一个键。

当你调用mymap[example(1,"a")]时，map会查找到对应的条目，返回它的值"hello"。这里不需要operator==，完全靠operator<的两次比较就完成了等价性判断。

内容的提问来源于stack exchange，提问作者theBigCheese88