std::map::find()
函数需要operator==
吗?
这里有一个误解,map
并不使用operator==
,它并不是必需的。在map
里,当且仅当!(x < y) && !(y < x)
时,两个键x
和y
才被视为等价。
map
并不知道也不关心你是否已经实现了operator==
。即使你实现了,也不一定意味着所有相等的键都会根据operator==
相等。
这里的原因是,在C++依赖于排序(sorting)、映射(maps)、集合(sets)和二分搜索(binary searches)的任何地方,它都基于众所周知的、数学上严格可比较的概念“严格弱序”来进行。严格弱序也在标准中定义了。这里没有特别需要operator==
的情况,如果你查看这些标准函数的代码,你很少会看到同时执行这两个测试的语句,例如if (!(x < y) && !(y < x))
。
此外,这些都不一定基于operator<
。对于map
的默认比较器是std::less<KeyType>
,而它默认使用operator<
。但如果你针对KeyType
专门化了std::less
,那么就不需要定义operator<
。如果你为map指定了不同的比较器,那么它可能与operator<
或std::less<KeyType>
无关。因此,在上面我说的x < y
实际上是cmp(x,y)
,其中cmp
是严格弱序。
这种灵活性也是不把operator==
拖入其中的另一个原因。假设KeyType
是std::string
,并且你指定了实现某些区域特定、不区分大小写的排序规则的比较器。如果map
有时使用operator==
,那么它将完全忽略只有大小写不同的字符串应该被视为相同键的事实(或在某些语言中:其他在排序目的上被认为无关紧要的差异)。因此,等价比较也必须是可配置的,但只有一个“正确”的答案可以由程序员提供。这种情况并不好,你永远不希望你的API提供看起来像定制点而实际上不是的东西。
另外,这个概念是,一旦你排除了小于你要查找的键的树部分和键小于它的树部分,剩下的就是空的(没有匹配)或者有一个键(匹配)。所以,你已经使用了current < key
然后key < current
,除了等价性之外,没有其他选择。情况正是:
if (search_key < current_element)
go_left();
else if (current_element < search_key)
go_right();
else
declare_equivalent();
你所建议的是:
if (search_key < current_element)
go_left();
else if (current_element < search_key)
go_right();
else if (current_element == search_key)
declare_equivalent();
这显然是不必要的。事实上,更高效的建议是你提出的建议!