c++建模一个偏序概念，例如自定义比较器

Question

我正在为自定义比较器函数建模偏序的概念，如下所示:

template <typename F, typename T>
concept PartiallyOrderedBy = requires(F &&f, const std::remove_reference_t<T> &t1,
const std::remove_reference_t<T> &t2) {
{ std::invoke(std::forward<F>(f), t1, t2) } -> std::convertible_to<std::partial_ordering>;
{ std::invoke(std::forward<F>(f), t2, t1) } -> std::convertible_to<std::partial_ordering>;
// ????
// { (t1 < t2) == (t2 > t1) };
// { (t2 < t1) == (t1 > t2) };
// { (t1 <= t2) == (t2 >= t1) };
// { (t2 <= t1) == (t1 >= t2) };
};

F基本上是一个三向比较器。

我想保证剩下的四个需求使用概念，所以我写了这个:

template <typename F, typename T>
concept PartiallyOrderedBy = requires(F &&f, const std::remove_reference_t<T> &t1,
const std::remove_reference_t<T> &t2) {
{ std::invoke(std::forward<F>(f), t1, t2) } -> std::convertible_to<std::partial_ordering>;
{ std::invoke(std::forward<F>(f), t2, t1) } -> std::convertible_to<std::partial_ordering>;
// are these really being tested???
{ bool(std::invoke(std::forward<F>(f), t1, t2) == std::partial_ordering::less)
== bool(std::invoke(std::forward<F>(f), t2, t1) == std::partial_ordering::greater) };
{ bool(std::invoke(std::forward<F>(f), t2, t1) == std::partial_ordering::less)
== bool(std::invoke(std::forward<F>(f), t1, t2) == std::partial_ordering::greater) };
{ bool(std::invoke(std::forward<F>(f), t1, t2) != std::partial_ordering::less)
== bool(std::invoke(std::forward<F>(f), t2, t1) != std::partial_ordering::greater) };
{ bool(std::invoke(std::forward<F>(f), t2, t1) != std::partial_ordering::less)
== bool(std::invoke(std::forward<F>(f), t1, t2) != std::partial_ordering::greater) };
};

代码运行没有错误(链接)，但我怀疑，如果这四种情况真的得到了测试，所以我很荒唐地修改了它们(link):

#include <functional>
#include <type_traits>
#include <utility>
#include <compare>
template <typename F, typename T>
concept PartiallyOrderedBy = requires(F &&f, const std::remove_reference_t<T> &t1,
const std::remove_reference_t<T> &t2) {
{ std::invoke(std::forward<F>(f), t1, t2) } -> std::convertible_to<std::partial_ordering>;
{ std::invoke(std::forward<F>(f), t2, t1) } -> std::convertible_to<std::partial_ordering>;
// are these really being tested???
{ bool(std::invoke(std::forward<F>(f), t1, t2) == std::partial_ordering::less)
== bool(std::invoke(std::forward<F>(f), t2, t1) == std::partial_ordering::less) };
{ bool(std::invoke(std::forward<F>(f), t2, t1) == std::partial_ordering::less)
== bool(std::invoke(std::forward<F>(f), t1, t2) == std::partial_ordering::less) };
{ bool(std::invoke(std::forward<F>(f), t1, t2) != std::partial_ordering::less)
== bool(std::invoke(std::forward<F>(f), t2, t1) != std::partial_ordering::less) };
{ bool(std::invoke(std::forward<F>(f), t2, t1) != std::partial_ordering::less)
== bool(std::invoke(std::forward<F>(f), t1, t2) != std::partial_ordering::less) };
};
int main() {
// assert passes, so they aren't being tested!!!
static_assert(PartiallyOrderedBy<std::compare_three_way, int>);
}

assert通过了，所以下面四个要求什么都不做。

测试它们的语法正确的方法是什么?

Answer 1

概念(无论是c++还是其他语言)总是有两种不同的要求:

• 静态要求(可以/应该被编译器测试的东西)
• 语义要求(需要保留但成本太高而无法实际测试或根本无法测试的东西)

例如，让我们看一下[concept.strictweakorder]:

template<class R, class T, class U>
concept strict_­weak_­order = relation<R, T, U>;

这定义了语法要求(您可以做r(t, u)和r(u, t)和r(t, t)和r(u, u)，所有这些都可以转换为bool)，但它也定义了语义要求:

一个关系只有在它的参数上施加严格的弱排序时才为strict_weak_order建模。

术语strict指的是对一个非自反关系的要求(!comp(x, x)对所有x)，术语weak指的是没有全排序强，但比偏排序强的要求。如果将equiv(a, b)定义为!comp(a, b) && !comp(b, a)，则要求comp和equiv都是传递关系:

• comp(a, b) && comp(b, c)暗含comp(a, c)
• equiv(a, b) && equiv(b, c)暗含equiv(a, c)

你不能静态地测试这个-这是一个属性，必须在所有a,b,c的概念域内保持。但是这个属性不需要保留。如果在语法上是strict_weak_order而不是(T, T)，但在语义上不是strict_weak_order的类型传递给sort这样的算法，您将得到无意义的结果。因为你违反了这一概念。但是你的违例在静态上是无法检测到的。

---

这个想法也完全为你PartiallyOrderedBy概念:你有一个语法要求,partial_orderingf(t1, t2)给你,和你有一个语义要求,f给你一个一致的排序。但是您不能检查后者-这将需要检查T的整个值。所以这部分需求只能被文档化。

为了避免你认为这是c++的限制，我们可以看看Rust中等价的PartialOrd。静态需求只是提供一个返回Option<Ordering>的函数partial_cmp，然后语义需求有一长串属性，必须满足域中的所有值。Rust只能检查partial_cmp是否具有正确的形状，您可以提供真正的排序。

例如，在声明排序时，一个非常常见的错误编译得很好(即使有些Pair可能同时持有a < b和b < a):

#[derive(PartialEq, Eq)]
struct Pair {
first: i32,
second: i32
}
impl PartialOrd for Pair {
fn partial_cmp(&self, rhs: &Pair) -> Option<Ordering> {
if self.first < rhs.first || self.second < rhs.first {
Some(Ordering::Less)
}
else if self.first > rhs.first || self.second > rhs.first {
Some(Ordering::Greater)
} else {
Some(Ordering::Equal)
}
}
}

---

最后，具体看看你的实现:

template <typename F, typename T>
concept PartiallyOrderedBy = requires(F &&f, const std::remove_reference_t<T> &t1,
const std::remove_reference_t<T> &t2) {
{ std::invoke(std::forward<F>(f), t1, t2) } -> std::convertible_to<std::partial_ordering>;
{ std::invoke(std::forward<F>(f), t2, t1) } -> std::convertible_to<std::partial_ordering>;
};

这里的两个检查完全相同-t1和t2具有相同的类型。这可以简化为:

template <typename T>
using const_cref = std::remove_reference_t<T> const&;
template <typename F, typename T>
concept PartiallyOrderedBy = 
// to pick up the semantic requirement of equality-preservation
std::regular_invocable<F, const_cref<T>, const_cref<T>>
// and to get the right type
&& std::convertible_to<std::invoke_result_t<F, const_cref<T>, const_cref<T>>, std::partial_ordering>;

当您添加这样的需求时:

{ bool(std::invoke(std::forward<F>(f), t1, t2) == std::partial_ordering::less)
== bool(std::invoke(std::forward<F>(f), t2, t1) == std::partial_ordering::greater) };

这是一个要求，这个表达式是一个有效的表达式，仅此而已。一旦您要求该调用的结果可转换为partial_ordering，那么(对愚蠢的、无意义的东西取模)它将与特定的partial_ordering值具有可比性，该相等结果已经是bool，您当然可以比较两个bool。这对你的概念没有任何帮助。

这个名字也值得注释:PartiallyOrderedBy<F, T>。这是反向的——从某种意义上说，是F对T排序，而不是相反。是,我们得到:

template <PartiallyOrderedBy<int> F>

更好的名字应该是PartialOrder。