std::map键的要求（设计决策）

Question

当我制作一个std::map<my_data_type，mapped_value>时，C++要求我的my_data_type有自己的operator<。

struct my_data_type
{
    my_data_type(int i) : my_i(i) { }

    bool operator<(const my_data_type& other) const { return my_i < other.my_i; }

    int my_i;
};

原因在于您可以从 operator< 派生出 operator> 和 operator==。 b < a 意味着 a > b，所以有了operator>。 !(a < b) && !(b < a) 意味着 a 既不小于 b 也不大于它，因此它们必须相等。

问题是：为什么C++设计者没有要求显式定义operator==？很明显，operator== 对于std::map::find()和从std::map中移除重复项是必不可少的。为什么要实现5个操作并调用两次方法才能不强制我显式实现operator==呢？

- OmarOthman

---

很抱歉，您的许多假设和断言并不完全正确或基于事实。 - Kerrek SB

顺便问一下，那个构造函数能用吗？看起来像是语义错误。 - supertopi

[@supertopi] 你说得对。我已经编辑过了，抱歉犯错了。 - OmarOthman

Answer 1

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();

这显然是不必要的。事实上，更高效的建议是你提出的建议！

- Steve Jessop

---

[@Steve] "如果你查看这些标准函数的代码，你很少会看到像if (!(x < y) && !(y < x))这样同时执行两个测试的情况". 那么std::map::find和去重是如何定义的呢？我知道我可以查看代码，但我的意思是：概念是什么？相等性必须被定义（以任何形式）来实现这两个功能，而已经完成的工作比依赖于明确定义的相等性函数要低效。这是我想要被说服的主要观点。 - OmarOthman

@Omar：这个概念是，一旦你排除了树中小于你要搜索的关键字的部分和关键字小于它的部分，剩下的要么为空（没有找到匹配项），要么就有一个关键字（找到匹配项）。 - Steve Jessop

Answer 2

你的假设是不正确的。下面是真正发生的事情：

std::map是一个类模板，它接受四个模板参数：键类型K，映射类型T，比较器Comp和分配器Alloc（当然，这些名称无关紧要，仅限于本答案）。对于本讨论而言，重要的是可以使用对象Comp comp;来调用两个键引用comp(k1, k2)，其中k1和k2是K const &，结果是一个布尔值，该布尔值实现了严格弱排序。

如果您没有指定第三个参数，则Comp是默认类型std::less，并且此（无状态）类将二进制操作实现为k1 < k2。无论这个<运算符是K的成员，还是自由函数，还是模板，或者其他。

这也就结束了故事。比较器类型是实现有序映射所需的唯一数据。相等性定义为!comp(a, b) && !comp(b,a)，并且根据此相等性定义，地图仅存储一个唯一键。

没有理由对键类型提出额外的要求，也没有逻辑上的理由要求用户定义的operator==和operator<必须完全兼容。它们都可以独立存在，并提供完全不同和不相关的目的。

好的库会对最小必要要求进行约束，并提供尽可能大的灵活性，这正是std::map所做的。

- Kerrek SB

---

“相等”被定义为……也许在这里使用“等价”会更恰当。 - Andrew Durward

这一切都很好，但我的主要观点是：不需要 operator== 是 不够高效 的！这是我的主要问题（你最后的陈述 部分地 回答了这个问题，但我仍然不太满意，因为几乎所有的 C++ 设计决策都是基于效率的（除了与 C 的向后兼容性）。） - OmarOthman

@Omar：这是一个错误的假设，正如Tom Whittock的回答所示。 - Xeo

Answer 3

为了在地图中找到元素，我们已经遍历到了元素，树搜索已经测试过<e，这将返回false。

因此，无论是调用 == e还是调用 <i，都意味着同样的事情，考虑到在树中找到的前提条件。由于我们已经必须有一个，所以我们不依赖于，因为那将增加关键概念的需求。

- Tom Whittock

Answer 4

比较运算符之所以需要，是因为 map 的实现方式是作为二叉搜索树，使得您可以在O(log n)时间内查找、插入和删除元素。为了构建这个树，必须为键集定义一个严格弱序。这就是为什么只需要一个操作符定义的原因。

- jupp0r

---

谓词定义的排序需要是严格弱序，但不一定是全序。 - Andrew Durward

Answer 5

你有一个错误的假设：

!(a < b) && !(b < a) 意味着a既不小于b也不大于它，所以它们必须相等。

这意味着它们是等价的，但不一定是相等的。您可以自由地实现operator<和operator==，使得两个对象可以等价但不相等。

为什么C++设计者没有要求显式定义operator==？

为了简化可用作键的类型的实现，并允许您为没有重载运算符的类型使用单个自定义比较器。唯一的要求是您提供一个比较器（operator<或自定义函数对象），该比较器定义了部分排序。您的建议将需要额外的工作来实现相等比较，并且需要额外的限制，即要求等价对象比较相等。

- Mike Seymour