运算符<和严格弱序

Question

如何operator<在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

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

形式定义:
严格弱排序

计算机科学:
严格的弱序

它与运营商的关系:
比较器

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] <a [i]的比较.该算法的另一种表达方式是"跳过时相等,然后进行比较":

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<T...>,您可以使用它来存储您的数据. tuples有一个匹配operator<,最初比较最左边的元素,然后沿着元组工作,直到结果清楚.这适用于提供例如和期望的严格弱序.std::setstd::map

如果你有一些其他变量中的数据(例如a中的字段struct),你甚至可以std::tie()用来创建一个引用元组,然后可以将它们与另一个这样的元组进行比较.这样可以轻松地operator<为用户定义的class/ struct类型中的特定成员数据字段编写:

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

基本流程应该是这样的:如果Kth元素不同,则返回较小的其他元素转到下一个元素.下面的代码假设你没有一个boost元组,否则你会使用get<N>(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;