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也不大于b,所以它们必须相等.

问题是:为什么C++设计器不需要operator==明确定义？显然,从中删除重复operator==是不可避免std::map::find()的std::map.为什么要实现5次操作并调用方法两次才能强迫我明确实现operator==？

Answer 1

operator== 是不可避免的 std::map::find()

这是你出错的地方.map根本不用operator==,它不是"不可避免的".如果是两个键x并且y被认为是等效于地图的目的!(x < y) && !(y < x).

map不知道或不关心你是否已实施operator==.即使你有,也不一定是订单中所有等价键都相等的情况operator==.

所有这一切的原因在于,无论C++依赖于订单(排序,地图,集合,二进制搜索),它都将其所做的一切都基于"严格弱秩序"的易于理解的数学概念,这也是标准中定义的. .没有特别需要operator==,如果你看一下这些标准函数的代码,你就不会经常看到类似的东西if (!(x < y) && !(y < x)),两个测试都是紧密相连的.

此外,这些都不一定基于operator<.默认比较器为mapis std::less<KeyType>,默认情况下使用operator<.但是,如果你已经专门std::less为KeyType,那么你不需要定义operator<,如果你指定的地图不同的比较那么它可能会或可能不会有什么关系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();

这显然不需要.事实上,你的建议效率较低!