C++ 运算符<和严格弱排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/979759/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Operator< and strict weak ordering
提问by Konstantin
How to define operator<on n-tuple (for example on 3-tuple) so that it satisfy strict weak orderingconcept ? I know that boost library has tuple class with correctly defined operator<but for some reasons I can't use it.
如何定义operator<n 元组（例如 3 元组）使其满足严格的弱排序概念？我知道 boost 库具有正确定义的元组类，operator<但由于某些原因我不能使用它。
采纳答案by peterchen
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
This orders the elements by a1 being most siginificant and a3 least significant.
这按照 a1 最重要和 a3 最不重要对元素进行排序。
This can be continued ad infinitum, you could also e.g. apply it to a vector of T, iterating over comparisons of a[i] < a[i+1] / a[i+1] < a[i]. An alternate expression of the algorithm would be "skip while equal, then compare":
这可以无限地继续，例如，您也可以将其应用于 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];
Of course, if the comparison is expensive, you might want to cache the comparison result.
当然，如果比较开销很大，您可能需要缓存比较结果。
[edit] removed wrong code
[编辑] 删除了错误的代码
[edit] if more than just operator<is available, I tend to use the pattern
[编辑] 如果不仅仅是operator<可用，我倾向于使用该模式
if (a1 != b1)
return a1 < b1;
if (a2 != b2)
return a2 < b2;
...
回答by Martin York
strict weak ordering
严格弱排序
This is a mathematical term to define a relationship between two objects.
Its definition is:
这是一个数学术语，用于定义两个对象之间的关系。
它的定义是：
Two objects x and y are equivalent if both f(x, y) and f(y, x) are false. Note that an object is always (by the irreflexivity invariant) equivalent to itself.
如果 f(x, y) 和 f(y, x) 都为假，则两个对象 x 和 y 是等价的。请注意，对象始终（根据非反身性不变量）等价于自身。
In terms of C++ this means if you have two objects of a given type, you should return the following values when compared with the operator <.
就 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
How you define equivalent/less is totally dependent on the type of your object.
如何定义等效/更少完全取决于对象的类型。
Formal Definition:
Strict Weak ordering
正式定义：
严格弱序
Computer Science:
Strict Weak Ordering
计算机科学：
严格弱排序
How it relates to operators:
Comparator
它与运算符的关系：
比较器
回答by Tony Delroy
...a new answer to a very old question, but the existing answer miss the easy solution from C++11...
...对一个非常古老的问题的新答案，但现有答案错过了 C++11 的简单解决方案...
C++11 solution
C++11 解决方案
C++11 onwards provides std::tuple<T...>, which you can use to store your data. tuples have a matching operator<that initially compares the left-most element, then works along the tuple until the outcome's clear. That's suitable for providing the strict weak orderingexpected by e.g. std::setand std::map.
C++11 以后提供std::tuple<T...>，您可以使用它来存储您的数据。 tuples 有一个匹配operator<，最初比较最左边的元素，然后沿着元组工作，直到结果明确。这适用于提供eg和 所期望的严格弱排序。std::setstd::map
If you have data in some other variables (e.g. fields in a struct), you can even use std::tie()to creates a tuple of references, which can then be compared to another such tuple. That makes it easy to write operator<for specific member-data fields in a user-defined class/structtype:
如果您在其他一些变量中有数据（例如 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_);
}
回答by Tony Delroy
You could simply use three-element vectors, which will already have operator<() suitably defined. This has the advantage that it extends to N-elements without you having to do anything.
您可以简单地使用三元素向量，它们已经适当地定义了 operator<() 。这样做的好处是它可以扩展到 N 个元素，而您无需做任何事情。
回答by Motti
The basic flow should be along the lines of: if the Kth elements are different, return which is smaller else go to next element. The code following assumes you don'thave a boost tuple otherwise you would use get<N>(tuple)and not have the problem to begin with.
基本流程应该是这样的：如果第 K 个元素不同，则返回较小的元素，否则转到下一个元素。以下代码假定您没有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;
回答by markh44
Even if you can't use the boost version, you should be able to nick the code. I nicked this from std::pair - a 3 tuple will be similar I guess.
即使您不能使用 boost 版本，您也应该能够破解代码。我从 std::pair 中删除了这个 - 我猜一个 3 元组将是相似的。
return (_Left.first < _Right.first ||
!(_Right.first < _Left.first) && _Left.second < _Right.second);
Edit: As a couple of people have pointed out, if you steal code from the standard library to use in your code, you should rename things that have underscores on the front as these names are reserved.
编辑：正如一些人指出的那样，如果您从标准库中窃取代码以在您的代码中使用，您应该重命名前面有下划线的内容，因为这些名称是保留的。
