c++ - 在与多个字段进行比较时提供严格的排序

Question

如何在具有大量可比较字段的对象之间提供严格的排序？

假设您有两个对象 x 和 y 需要比较，每个对象都有 3 个字段 (a, b,c)

bool less(x, y)
  return x.a < y.a || x.b < y.b || x.c < y.c

很好，但这提供了弱排序。如果 x.a < y.a 和 y.b < x.b，less(x,y) 为真，less(y, x) 也为真。

我习惯了写作

bool less(x, y)
  return x.a < y.a || (x.a == y.a && x.b < y.b)

但是一旦涉及的字段数量增加，它就会变得非常丑陋。

bool less(x, y)
  return x.a < y.a || 
        (x.a == y.a && x.b < y.b) ||
        (x.a == y.a && x.b == y.b && x.c < y.c) ||
        (x.a == y.a && x.b == y.b && x.c == y.c && x.d < y.d);

有人有更好看的算法吗？

Answer 1

如果您使用的是 C++11 或更高版本，可以使用一个很好的技巧来获得 SWO，而无需手写。您可以使用 std::tuple , 打包你的成员(member)和事实 std::tuple工具 operator<作为字典顺序。

所以你可以这样写

struct foo {
    int x, y, z;

    bool operator<(const foo& rhs) const {
        return std::tie(x, y, z) < std::tie(rhs.x, rhs.y, rhs.y);
    }
};

和结构foo将按字典顺序按 x、y、z 进行比较。这个要写的还是很多，大家可以稍微改进一下

struct foo {
    int x, y, z;

    auto tied() const {
        return std::tie(x, y, z);
    }

    bool operator<(const foo& rhs) const {
        return tied() < rhs.tied();
    }
};

如果你有很多成员，这可以节省很多输入，但它假定 C++14(对于 C++11，你必须手写出 tied 的返回类型)。