c++ - 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== ？

Answer 1

operator== is inevitable for std::map::find()

这是你大错特错的地方。 map不使用 operator==根本不是"不可避免的"。两把 key x和 y如果 !(x < y) && !(y < x) 被认为是 map 的等价物.

map不知道也不关心你是否实现了operator== .即使你有，根据 operator==，顺序中的所有等效键也不一定相等。 .

所有这一切的原因是，无论 C++ 在何处依赖顺序(排序、映射、集合、二进制搜索)，它所做的一切都基于“严格弱顺序”这一​​易于理解的数学概念，这也被定义为在标准中。没有特别需要 operator== ，如果您查看这些标准函数的代码，您将不会经常看到类似 if (!(x < y) && !(y < x)) 的内容。两个测试都靠得很近。

此外，这些都不一定基于 operator< . map 的默认比较器是std::less<KeyType> ，默认情况下使用 operator< .但是如果你专门研究了std::less对于 KeyType那么你不需要定义 operator< , 如果您为 map 指定不同的比较器，那么它可能与 operator< 有任何关系，也可能没有关系。或 std::less<KeyType> .所以我说的x < y以上，真的是cmp(x,y) , 其中cmp是严格弱序。

这种灵 active 是不拖拽的另一个原因 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();

这显然是不需要的。事实上，您的建议效率较低!