如何定义operator<
n 元组(例如 3 元组)以满足严格的弱排序概念?我知道 boost 库有正确定义的元组类,operator<
但由于某些原因我不能使用它。
6 回答
严格弱序
这是一个定义两个对象之间关系的数学术语。
它的定义是:
如果 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
已经实现了平等。
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;
...
...一个非常老问题的新答案,但现有答案错过了 C++11 的简单解决方案...
C++11解决方案
C++11 及更高版本提供了std::tuple<T...>
,您可以使用它来存储您的数据。 tuple
s 有一个匹配operator<
,最初比较最左边的元素,然后沿着元组工作,直到结果明确。这适用于提供eg和所期望的严格弱排序。std::set
std::map
如果您在其他一些变量中有数据(例如 a 中的字段struct
),您甚至可以使用std::tie()
来创建references的元组,然后可以将其与另一个这样的元组进行比较。这使得在用户定义/类型中编写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_);
}
您可以简单地使用三元素向量,它已经适当地定义了 operator<()。这样做的好处是它可以扩展到 N 元素,而无需您做任何事情。
基本流程应该是这样的:如果第 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;
即使你不能使用 boost 版本,你也应该可以修改代码。我从 std::pair 中删除了这个 - 我猜 3 元组将是相似的。
return (_Left.first < _Right.first ||
!(_Right.first < _Left.first) && _Left.second < _Right.second);
编辑:正如一些人指出的那样,如果您从标准库中窃取代码以在代码中使用,您应该重命名前面带有下划线的内容,因为这些名称是保留的。