使用结构作为STL映射键的要求？

Question

我正在使用带有struct密钥的STL地图.这是地图的定义: std::map<Coord2<uint8_t>, MapTile> tile_;

定义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); }
}

我会因为比较而遇到地图问题吗？

Answer 1

这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值比较相等,这就是我们想要的.)

Answer 2

对于两个值,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.

定义元组的比较以进行词典比较,因此比较第一个元素,如果结果为真,则比较完成并返回true,否则对于每对元素,下一个元素以相同的方式进行比较.只要每个元素类型都有正确定义,这就可以确保正确的严格弱排序operator<.