2

I'm using an STL map with a struct for a key. This is the definition of the map: std::map<Coord2<uint8_t>, MapTile> tile_;

The definition of the struct:

template <typename T>
struct Coord2
{
    T x;
    T y;

    bool operator<(const Coord2<T> &coord) const { return (x < coord.x || y < coord.y); }
    bool operator>(const Coord2<T> &coord) const { return (x > coord.x || y > coord.y); }
}

Will I experience issues with the map because the comparison?

4

3 回答 3

14

这operator<不适合与 C++ 标准库的关联容器一起使用。

比较器必须提供严格的弱排序，而您的则没有。考虑以下证明其不一致的操作数：

a = { x = 1, y = 0 }
b = { x = 0, y = 1 }

给定这些输入a < b == true和b < a == true，但是b != a。

这种类型的正确比较可能是：

if (x < coord.x)
    return true;

if (coord.x < x)
    return false;

return y < coord.y;

（当然可以以更紧凑的方式编写这个正确的代码，但是我已经调试了由错误实现的严格弱排序引起的足够多的错误，我强烈建议在比较中非常明确，以便清楚它是正确的. 通过这个实现，很明显，我们只y在值比较相等时才比较值x，这就是我们想要的。）

于 2012-06-07T16:42:55.640 回答
13

对于两个值，James 的答案是理想的，对于更多的成员，它会变得复杂，因此对多个值实现严格的弱排序的一种简单方法是创建这些值的元组并比较元组：

 return boost::tie(x, y, z) < boost::tie(coord.x, coord.y, coord.z);

为此，您需要做的就是让每个成员成为 LessThanComparable，然后在每个表达式#include <boost/tuple/tuple_comparison.hpp>中以相同的顺序列出成员。tie

在 C++11 中，您可以改为#include <tuple>使用std::tie。

元组比较被定义为进行字典比较，因此比较第一个元素，如果结果为真，则比较完成并返回真，否则对于每对元素以相同的方式比较下一个元素。只要每个元素类型都有正确定义的operator<.

于 2012-06-07T16:54:09.250 回答
2

先说一句：你不需要operator>，因为无论如何std::map只会使用。operator<

但是，您operator<不适合密钥，因为它没有定义严格的弱排序。std::map事实上，它甚至没有实现严格的偏序，因为它违反了传递性和反对称：考虑以下定义：

coord p = { 2, 2 };
coord q = { 0, 4 };
coord r = { 1, 1 };

也不p < q返回true因为2 < 4，q < r返回true因为0 < 1，但是p < r返回false。因此违反了传递性。

此外，不仅p < q返回 true，而且q < p，因为0 < 2. 换句话说，根据您的运营商的说法，每个p和q都将被认为比另一个小。

于 2012-06-07T16:53:14.153 回答