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

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

我通常这样做：

bool operator< (type x, type y) {
    if (x.a < y.a) return true;
    if (x.a > y.a) return false;

    if (x.b < y.b) return true;
    if (x.b > y.b) return false;

    return x.c < y.c;
}

这提供了硬排序并扩展了您所关心的尽可能多的元素，而不会增加每个元素的开销。

Answer 2

如果您使用的是 C++11 或更高版本，可以使用一个很好的技巧来获得 SWO，而无需手写。您可以使用 std::tuple 来打包您的成员，并且 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);
    }
};

和 struct 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，你必须写出 return 类型 tied 手动）。

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

Provide strict ordering during comparison with multiple fields

c++

language-agnostic

algorithm

boolean-logic