如何定义运算符< 在满足严格弱排序的 n 元组上

Question

如何在 n 元组（例如 3 元组）上定义运算符<，使其满足严格弱排序概念？ 我知道 boost 库具有正确定义的 operator< 元组类，但由于某些原因我无法使用它。

Answer 1

严格弱排序

这是定义两个对象之间关系的数学术语。
它的定义是：

如果 f(x, y) 和 f(y, x) 都为假，则两个对象 x 和 y 是等价的。 请注意，对象始终（通过反自不变量）等于其自身。

就 C++ 而言，这意味着如果您有两个给定类型的对象，则与运算符 < 相比，您应该返回以下值。

X    a;
X    b;

Condition:                  Test:     Result
a is equivalent to b:       a < b     false
a is equivalent to b        b < a     false

a is less than b            a < b     true
a is less than b            b < a     false

b is less than a            a < b     false
b is less than a            b < a     true

如何定义等效/更少完全取决于对象的类型。

正式定义：
严格弱排序

计算机科学：
严格弱排序

它与运算符的关系：
比较器

---

作为旁注，我们可以手动实现严格的弱排序。 但我们可以简单地使用已为您实现的 std::tuple 来完成此操作。 您只需要创建一个元组而不复制对象。

struct S
{
     ThingA   a;
     ThingB   b;
};
bool operator<(S const& lhs, S const& rhs)
{
    return std::tie(lhs.a, lhs.b) < std::tie(rhs.a, rhs.b);
}

注意：这假设 thingA 和 thingB 本身已经实现了严格的弱排序。

我们也可以用同样的方式实现相等：

bool operator==(S const& lhs, S const& rhs)
{
    return std::tie(lhs.a, lhs.b) == std::tie(rhs.a, rhs.b);
}

再次注意：这假设 thingA 和 thingB 已经实现了相等。

Answer 2

if (a1 < b1)
  return true;
if (b1 < a1)
  return false;

// a1==b1: continue with element 2
if (a2 < b2)
  return true;
if (b2 < a2)
  return false;

// a2 == b2: continue with element 3
if (a3 < b3)
  return true;
return false; // early out

这对元素进行排序，a1 是最重要的，a3 是最不重要的。

这可以无限地继续下去，您也可以例如将其应用于 T 的向量，迭代 a[i] < 的比较。 a[i+1] / a[i+1] < 人工智能]。 该算法的另一种表达方式是“相等时跳过，然后比较”：

while (i<count-1 && !(a[i] < a[i+1]) && !(a[i+1] < a[i])
  ++i;
return i < count-1 && a[i] < a[i+1];

当然，如果比较成本很高，您可能希望缓存比较结果。

---

[编辑]删除了错误的代码

---

[编辑]如果不仅仅是 operator< 可用，我倾向于使用该模式

if (a1 != b1)
  return a1 < b1;

if (a2 != b2)
  return a2 < b2;

...

Answer 3

...一个非常老的问题的新答案，但现有答案错过了 C++11 的简单解决方案...

C++11 解决方案

C++11 及以后提供 std::tuple，您可以使用它来存储您的数据。 元组有一个匹配的运算符< 首先比较最左边的元素，然后沿着元组工作，直到结果明确。 这适合提供严格的弱排序，例如std::set 和 std::map。

如果您在其他变量中有数据（例如struct中的字段），您甚至可以使用std::tie() 创建一个引用元组，然后可以将其与另一个此类元组进行比较。 这样可以轻松地为用户定义的 class/struct 类型中的特定成员数据字段编写 operator<：

struct My_Struct
{
    int a_;
    double b_;
    std::string c_;
};

bool operator<(const My_Struct& lhs, const My_Struct& rhs)
{
    return std::tie(lhs.a_, lhs.b_, lhs.c_) < std::tie(rhs.a_, rhs.b_, rhs.c_);
}

Answer 4

您可以简单地使用三元素向量，它已经适当地具有运算符<()
定义的。 这样做的优点是它可以扩展到 N 元素，而您无需执行任何操作。

Answer 5

基本流程应遵循以下原则：如果第 K 个元素不同，则返回较小的元素，否则转到下一个元素。 下面的代码假设您没有有一个boost元组，否则您将使用get(tuple)并且一开始就不会出现问题。

if (lhs.first != rhs.first)
    return lhs.first < rhs.first;                
if (lhs.second != rhs.second)
    return lhs.second< rhs.second;
return lhs.third < rhs.third;

Answer 6

即使您不能使用 boost 版本，您也应该能够修改代码。 我从 std::pair 中删掉了这个 - 我猜 3 元组将是相似的。

return (_Left.first < _Right.first ||
        !(_Right.first < _Left.first) && _Left.second < _Right.second);

编辑：正如一些人指出的那样，如果您从标准库中窃取代码以在代码中使用，则应该重命名前面带有下划线的内容，因为这些名称是保留的。

Answer 7

请注意，有趣的是，始终返回 false 的运算符 满足 严格弱排序。