std :: map密钥要求(设计决策) [英] std::map Requirements for Keys (Design Decision)

问题描述

当我制作std::map<my_data_type, mapped_value>时，C ++对我的期望是my_data_type有自己的operator<.

When I make a std::map<my_data_type, mapped_value>, what C++ expects from me is that my_data_type has its own 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 也不大于，因此它们必须相等.

The reason is that you can derive operator> and operator== from operator<. b < a implies a > b, so there's operator>. !(a < b) && !(b < a) means that a is neither less than b nor greater than it, so they must be equal.

问题是:为什么C ++设计人员不要求明确定义operator==?显然，对于std::map::find()和从std::map删除重复项而言，operator==是不可避免的.为什么要执行5个操作并两次调用一个方法，以免强迫我显式实现operator==?

The question is: Why hasn't the C++ designer require operator== to be explicitly defined? Obviously, operator== is inevitable for std::map::find() and for removing duplicates from the std::map. Why implement 5 operations and call a method twice in order not to compel me to explicitly implement operator==?

推荐答案

operator==对于std::map::find()

这是您严重错误的地方. map根本不使用operator==，这不是不可避免的".如果!(x < y) && !(y < x)，则对于地图而言，两个键x和y被认为是等效的.

This is where you go badly wrong. map does not use operator== at all, it is not "inevitable". Two keys x and y are considered equivalent for the purposes of the map if !(x < y) && !(y < x).

map不知道或不在乎是否已实现operator==.即使有，也不必一定要按operator==顺序排列所有等效键.

map doesn't know or care whether you've implemented operator==. Even if you have, it need not be the case that all equivalent keys in the order are equal according to operator==.

所有这些的原因是，无论C ++依赖顺序(排序，映射，集合，二进制搜索)的任何地方，它所做的一切都基于众所周知的严格弱顺序"的数学概念，该概念也已定义在标准中.不需要特别使用operator==，并且如果您查看这些标准功能的代码，您将很少会看到像if (!(x < y) && !(y < x))这样的两个测试都关闭在一起的东西.

The reason for all this is that wherever C++ relies on orders (sorting, maps, sets, binary searches), it bases everything it does on the well-understood mathematical concept of a "strict weak order", which is also defined in the standard. There's no particular need for operator==, and if you look at the code for these standard functions you won't very often see anything like if (!(x < y) && !(y < x)) that does both tests close together.

此外，这些都不是必须基于operator<的. map的默认比较器是std::less<KeyType>，默认情况下使用operator<.但是，如果您为KeyType专门设置了std::less，则无需定义operator<，并且如果为映射指定其他比较器，则它可能与operator<或.因此，在上面我说过x < y的地方，实际上是cmp(x,y)，其中cmp是严格的弱阶.

Additionally, none of this is necessarily based on operator<. The default comparator for map is std::less<KeyType>, and that by default uses operator<. But if you've specialized std::less for KeyType then you needn't define operator<, and if you specify a different comparator for the map then it may or may not have anything to do with operator< or std::less<KeyType>. So where I've said x < y above, really it's cmp(x,y), where cmp is the strict weak order.

这种灵活性是为什么不将operator==拖到其中的另一个原因.假设KeyType为std::string，并且您指定了自己的比较器，该比较器实现了某种特定于语言环境的，不区分大小写的排序规则.如果map有时使用operator==，则将完全忽略这样的事实，即仅大小写不同的字符串应视为相同的键(或在某些语言中:具有其他差异，这些差异对于整理目的不重要).因此，相等比较也必须是可配置的，但是程序员只能提供一个正确"的答案.这不是一个好情况，您永远不希望您的API提供看起来像自定义点的东西，但实际上不是.

This flexibility is another reason why not to drag operator== into it. Suppose KeyType is std::string, and you specify your own comparator that implements some kind of locale-specific, case-insensitive collation rules. If map used operator== some of the time, then that would completely ignore the fact that strings differing only by case should count as the same key (or in some languages: with other differences that are considered not to matter for collation purposes). So the equality comparison would also have to be configurable, but there would only be one "correct" answer that the programmer could provide. This isn't a good situation, you never want your API to offer something that looks like a point of customization but really isn't.

此外，概念是，一旦您排除了小于要搜索的键的树的部分，并且排除了键小于它的树的部分，剩下的就是为空(找不到匹配项)，或者其中有一个键(找到匹配项).因此，您已经使用了current < key然后使用key < current，除了等效项外没有其他选择.情况恰好是

Besides, the concept is that once you've ruled out the section of the tree that's less than the key you're searching for, and the section of the tree for which the key is less than it, what's left either is empty (no match found) or else has a key in it (match found). So, you've already used current < key then key < current, leaving no other option but equivalence. The situation is exactly:

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

这显然是不需要的.实际上，这是您的建议，效率不高！

which is obviously not needed. In fact, it's your suggestion that's less efficient!

这篇关于std :: map密钥要求(设计决策)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！