std :: map,自定义比较器的设计约束

Question

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

问题是:我可以在==和!=运算符上转发,还是会打破严格的弱顺序？我被迫使用运营商<？

(一个和两个类确实有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 <
}

Answer 1

你不能依赖自相等或不等于因为这些不建立严格的弱顺序.如果切换左右参数,比较器返回值应该会改变.地图必须能够建立元素的排序,而不仅仅是能够区分两个元素是否相等.

非常重要的是,A < B是真的,然后B < A是假的.此外,如果A < B并且B < C都是真的,那么A < C也是如此.

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

¹ 正如@JohnDibling在评论中指出的那样,std::unordered_map不幸的是被命名.应该是,std::hash_map但显然该名称可能与hash_maps其他图书馆发生冲突.在任何情况下,目的都不是要有一个没有排序的地图,而是要有一个具有恒定时间查找的地图.

Answer 2

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

你没有必要直接实现比较器operator<,但你必须确保if operator()(A,B)返回true,然后operator()(B,A)也不返回true.