1

我一直在尝试为 std::map 容器定义一个自定义比较器。

问题是：我可以中继 == 和 != 运算符还是会破坏严格的弱顺序？我是否被迫使用 operator < ？

（一和二类确实正确定义了 operator!= 和 operator==）

typedef std::pair<One, Two> MapKey_t;
class cmp
{
    bool operator()(const MapKey_t& left, const MapKey_t& right) const
    { return left.first != right.first && right.first == right.second; }
}

typedef std::map<MapKey_t, Three*, cmp> MyMap_t;

由于左右切换不会改变比较器的返回值，这会起作用吗？

我并不真正关心如何将项目分类到容器中，但我不希望重复项成为其中的一部分。

更新：

我可以使用内存地址来获得严格的弱排序吗？

class cmp
{
    bool operator()(const MapKey_t& left, const MapKey_t& right) const
    { 
        if(left.first == right.first)
            if(left.second != right.second)
                return false; // This represents for me, functionally, a duplicate
            else
                // Can't use operator < there since left.second equals right.second but
                // functionally for me, this is not a duplicate and should be stored
                // what about memory address strict weak ordering ?
                return &left < &right;
        else
            return left.first < right.first; // There I can use operator <
}
4

3 回答 3

5

您不能依赖自一致的等于或不等于，因为它们没有建立严格的弱排序。如果切换左右参数，比较器返回值应该会改变。map 必须能够建立元素的排序，而不仅仅是能够区分两个元素是否相等。

非常重要的是，A < B是真的，然后B < A是假的。此外，如果A < B和B < C都为真，那么A < C也为真。

如果您不想或不能为您的类型建立严格的弱排序，那么您可以使用不需要它的映射：1，这是一个哈希映射。但是，这将要求您提供散列函数和相等比较。它还要求您的编译器支持 C++11。std::unordered_map

1 正如@JohnDibling 在评论中指出的那样，std::unordered_map不幸的是被命名了。应该是std::hash_map，但显然该名称可能与hash_maps其他库发生冲突。在任何情况下，我们的目的都不是要有一张无序的地图，而是要有一张具有恒定时间查找的地图。

于 2012-11-23T16:11:05.330 回答
5

您可能不关心地图中的事物是如何排序的，但地图确实如此。您上面提供的代码似乎没有正确实现严格的弱排序。正如您已经注意到的那样，operator()在所有情况下左右切换都不会改变结果，您的函数没有实现严格的弱排序。

您不必operator<直接实现比较器，但您必须确保如果operator()(A,B)返回true，则operator()(B,A)不会也返回true。

于 2012-11-23T16:12:57.433 回答
0

这是不可接受的，字符串弱排序意味着A < B并且B < A不应同时为真。std::map依靠它来建立键的顺序和相等性

于 2012-11-23T16:11:00.167 回答