问题标签 [partial-ordering]

我目前正在使用 Boost.ProgramOptions 进行项目，我必须创建以下结构来为选项添加一些约束：

为了验证该新选项，您必须重载该boost::program_options::validate函数：

对此验证函数的调用如下：

正如 boost 所指出的那样：“目标类型是通过一个参数指定的，该参数具有指向所需类型的指针类型。对于没有部分模板排序的编译器，这是一种解决方法，就像最后一个 'long/int' 参数一样。”

因此，我以以下方式编写了我的验证版本：

看起来我的 clang 版本（Ubuntu clang 版本 3.5.0-4ubuntu2~trusty2 (tags/RELEASE_350/final)（基于 LLVM 3.5.0））只是跳过我的版本并在默认版本中优雅地失败。虽然我的 gcc ((Ubuntu 4.8.2-19ubuntu1) 4.8.2) 愉快地编译。

编辑查看显示不同行为的实时示例，感谢@dyp：

Live On Coliru

此外，对结构/函数使用非可变模板（固定数量的 const char*）的相同过程确实像一个魅力。

我不太确定哪个查找过程会导致这种模棱两可的错误。如果我的函数没有使用模板，它会根据重载规则进行选择，但事实并非如此。通过阅读模板函数的部分排序规则，两个函数对模板参数具有相同的特化，但我的期望是 int/long 技巧应该起作用。关于如何解决这个模板之谜的任何想法？

指针关系运算符不定义总顺序（C++11 标准第 5.9 节）：

如果两个相同类型的指针指向不同的对象p，q这些对象不是同一对象的成员或同一数组的元素或不同的函数，或者如果其中只有一个为空，则 、 、 和 的p<q结果p>q未p<=q指定p>=q。

std::less文档说：

任何指针类型的部分特化std::less都会产生一个全序，即使内置operator<没有。

它如何从部分订单中产生这个全订单？

我无法通过查看定义来回答这个/usr/include/c++/4.9/bits/stl_function.h问题struct less：

（与我之前的问题有关）

在 QT 中，QMap文档说：

QMap 的键类型必须提供operator<()指定总顺序。

但是，在 中qmap.h，它们似乎使用类似于 的东西std::less来比较指针：

他们只是将指针转换为quintptrs （这是 的 QT 版本uintptr_t，即能够存储指针的无符号整数）并比较结果。

以下类型指定了一个无符号整数类型，其属性是任何指向 void 的有效指针都可以转换为此类型，然后转换回指向 void 的指针，结果将与原始指针进行比较：uintptr_t

你认为这种qMapLessThanKey()on 指针的实现好吗？

当然，整数类型有一个总顺序。但我认为这不足以得出此操作定义了指针的总顺序的结论。

我认为只有在没有指定 AFAIKp1 == p2的情况下，它才是正确的。quintptr(p1) == quintptr(p2)

作为这种情况的反例，想象一个使用 40 位指针的目标；它可以将指针转换为quintptr，将 40 个最低位设置为指针地址，并使 24 个最高位保持不变（随机）。这足以尊重quintptr和指针之间的可转换性，但这并没有定义指针的总顺序。

你怎么看？

考虑以下简单（就模板问题而言）示例：

clang 和 gcc 都在那里打印“a”。根据[temp.deduct.partial]和[temp.func.order]中的规则，要确定偏序，我们需要合成一些唯一的类型。所以我们有两次推演尝试：

对于“b”的推论，根据Richard Corden 的回答，表达式typename identity<UniqueB>::type被视为一种类型并且不被评估。也就是说，这将被合成为：

很明显，对“b”的推论失败了。这是两种不同的类型，因此您不能同时推断出这两种类型T。

但是，在我看来，扣除A应该失败。对于第一个参数，您将匹配T == UniqueA. 第二个论点是一个非演绎的上下文 - 那么如果UniqueA可以转换为，那么演绎不会成功identity<UniqueA>::type吗？后者是替换失败，所以我看不出这个推论怎么会成功。

在这种情况下，gcc 和 clang 如何以及为什么更喜欢“a”重载？

根据 [temp.class.order] §14.5.5.2，t在此示例中选择部分专业化：

等效于f在此示例中选择重载：

但是，GCC、Clang 和 ICC 都拒绝第一个示例，认为其模棱两可，但接受第二个示例。

更奇怪的是，第一个示例在::v被替换为时有效，::w反之亦然。未推断的上下文c::显然s< c >::是在专业化排序中考虑的，这是没有意义的。

我是否遗漏了标准中的某些内容，或者所有这些实现都有相同的错误？

首先：这不是Partial Ordered Comparator问题的副本，而是建立在它之上。

我的目标是对对象列表（例如[2，“a”，1]）进行就地排序，以便在排序后没有两个整数出现乱序。

为此，我在这个答案中使用了以下部分排序的实现并得到了IllegalArgumentException：

这是因为建议的比较器存在缺陷。示范：

对iff和都是整数并根据整数的自然排序的R所有Object实例使用偏序：a.before(b)aba < b

原因是通过以下实现

这可以在生成的排序中产生一个循环，因为

都是真的，即 2 < "a"、"a" < 1 和 "1 < 2，这显然不是有效的总排序。

这给我留下了最后一个问题：如何修复这个错误？

我正在尝试解决以下问题：

返回错误

我尝试将以下内容添加到我的代码中：

并且 temp1 <= temp2 仍然不起作用。

我能够运行诸如

但不是

所以似乎 scala 没有看到我对 (Int, String) 元组的排序声明。

我可以使用引用我的声明

我的一些同事建议为 (Int, String) 元组创建一个新类，但我发现这些解决方案不优雅。我真的很想能够使用普通的旧“<=”比较运算符！

有谁知道我做错了什么，“<=”仍然不是（Int，String）的成员？有没有办法隐式设置它？

是否有一种有效的算法可以从偏序的单个线性扩展创建传递减少？

更新：实际上，部分顺序是已知的。我也知道计算给定偏序的传递减少的时间复杂度。我想知道的是：给定一个偏序及其线性扩展之一，可以降低时间复杂度吗？

我正在寻找一种半有效的算法，给定一个输入集，从中生成所有总的预序关系（或者，等效地，所有弱序）。您也可以将其称为 n 个标记元素的所有优先安排。

我已经尝试通过首先生成所有大小为 n 的排列然后用“~”折叠这些排列的子序列来实现这一点，但是由于很多重复，这非常低效，而且我也错过了一些结果。大小由 Fubini 数字 1、1、3、13、75、541、4683、47293、545835，...（OEIS 编号 A000670）给出，并且随着 n 快速增长。我只需要前几个，比如说，直到 n=8。

示例：对于 A={a, b, c} 且 n=3，结果是 13 个预购：

b>a>c, b>a~c, b>c>a, b~c>a, c>b>a, c>a~b, c>a>b, a~c>b, a> c>b, a>b~c, a>b>c, a~b>c, a~b~c

我有一些问题。我需要对查询集的不同部分使用两个排序。这意味着：订购所有 -> 订购第一部分 -> 订购第二部分