标签: partial-ordering

我有一个由某种“状态机”（“流程图”）定义的分布式系统

每个系统都将状态写入共享“日志”中

我将每个州表示为密封特征的一部分以及该州的给定“状态”

我想“合并/减少”到代表当前进度的单一状态。

（有一些放宽措施，因为并非所有项目都必须成功才能成功完成最终状态）

有 2 个密封特征代表流程：

sealed trait System
case object A extends System
case object B extends System
case object C extends System
...

sealed trait Status
case object Pending extends Status
case object InProgress extends Status
case object Success extends Status
case object Fail extends Status

日志：

A, Success
B, Fail
C, Pending
...
...

现在我用一组规则来定义单个状态降低

基本上它优先

A < B < C, ... < Z

和

Pending < InProgress < Success < Fail

因此，如果存在以下状态：

(A, Success) …

我需要订购一系列信封.每个信封的高度和宽度都有描述.如果可以将信封插入信封2中,则信封1小于信封2.如果envelope1不能插入envelope2中,反之亦然,则无法比较它们.

我如何在scala中订购这些信封？我在互联网上找不到任何相关信息.

这是我的一些代码:

object EnvelopeOrdering extends PartialOrdering[(Int, Int)] {
  override def tryCompare(x: (Int, Int), y: (Int, Int)): Option[Int] = {
    if (x._1 < y._1 && x._2 < y._2) return Some(1)
    if (x._1 > y._1 && x._2 > y._2) return Some(-1)
    if (x._1 == y._1 && x._2 == y._2) return Some(0)
    None
  }

  override def lteq(x: (Int, Int), y: (Int, Int)): Boolean = x._1 < y._1 && x._2 < y._2
}

最近，我发现GCC在偏序期间改变了行为，具体情况如下：

#include <iostream>
template<class T>
struct unknow_context{
    using type = int;
};
template<class U>
void show(typename unknow_context<U>::type, U){ // candidate #1
    std::cout<<"#1\n";
}

template<class T>
void show(int, T){   // candidate #2
    std::cout<<"#2\n";
}
int main(){
    show(0,0);  
}

结果是，Clang打印#2（任何版本Clang都打印出一致的结果）。但是，GCC具有不同的行为。旧版本的GCC打印#2，相反，最新的GCC抱怨候选函数不明确。让我们看看标准对偏序是怎么说的。
temp.deduct.partial#2

推导过程使用转换后的类型作为参数模板，使用另一个模板的原始类型作为参数模板。这个过程对偏序比较中涉及的每个类型进行两次：一次使用转换后的 template-1 作为参数模板和 template-2 作为参数模板，再次使用转换后的 template-2 作为参数模板和 template-1作为参数模板。

因此，我们可以分别得到候选#1和 的两组 P/A 对#2。一个是变换#1为A，原#2为P。另一个是原#1为P，变换#2为A。所以这两个集合如下：

#a …

[SGI官方文件]

由于无反射性和传递性,operator <始终满足部分排序的定义.严格弱序的定义更严格,总排序的定义更严格.

我还阅读了文档中严格弱排序的定义:StrictWeakOrdering

前三个公理,无反射性,反对称性和传递性,是部分排序的定义; 严格弱排序的定义需要等价的传递性.总排序是满足更强条件的顺序:等价必须与平等相同.

我对这些定义不太确定.一些主要问题:

1. 偏序是否隐含地定义了等价？

2. 严格的弱订货和总订货怎么样？

3.STL在排序算法中需要严格的弱排序,为什么不是部分排序或总排序？ 对于这个问题,我通过证明规则满足三个公理来阅读一些证明有效比较规则的教科书:无反射性,反对称性,传递性,这是部分排序的定义,文件指的是运算符<总是满足这个定义,所以为什么我们不能只使用部分排序比较对象,或者等效地使用运算符

从§5.2.6/ 1我们得到(重点是我的):

后缀++表达式的值是其操作数的值.[注意:获得的值是原始值的副本 - 结束注释]操作数应是可修改的左值.操作数的类型应该是cv bool以外的算术类型,或者是指向完整对象类型的指针.通过向其添加1来修改操作数对象的值.在修改操作数对象之前,对++表达式的值计算进行排序.对于不确定顺序的函数调用,后缀++的操作是单个评估.[注意:因此,函数调用不应介入左值到右值的转换和与任何单个后缀++运算符相关的副作用. - 结束注释]结果是一个prvalue.结果的类型是操作数类型的cv-nonqualified版本.如果操作数是不能表示递增值的位字段,则位字段的结果值是实现定义的.另请参见[expr.add]和[expr.ass].

也就是说,在表达式的值计算之后对操作数对象的修改进行排序++.

从§5.18/ 1我们得到(重点是我的):

赋值运算符(=)和复合赋值运算符都是从右到左分组.所有都需要一个可修改的左值作为左操作数,并返回一个左值操作数的左值.如果左操作数是位字段,则所有情况下的结果都是位字段.在所有情况下,在右和左操作数的值计算之后,以及在赋值表达式的值计算之前,对赋值进行排序.对于不确定序列的函数调用,复合赋值的操作是单个评估.[注意:因此,函数调用不应介入左值到右值的转换和与任何单个复合赋值运算符相关的副作用. - 结束说明]

assignment-expression:
      conditional-expression
      logical-or-expression assignment-operator initializer-clause
      throw-expression

assignment-operator:其中一个
      =*=/=%= + = - = >> = << =&= ^ = | =

在赋值运算符的右和左操作数的值计算之后,也对赋值进行排序.

因此,如果我们考虑表达式

i = i++;

我们从§5.2.6/ 1中知道,表达式i++对该赋值表达式的RHS的副作用是在计算值之后对其进行排序i++.从§5.18/ 1我们知道,在i赋值运算符的右和左操作数的值计算之后,对应于赋值运算符的LHS的赋值的副作用被排序.

但是,为了证明表达式i = i++;显示未定义的行为,我如何证明这两个副作用是无效的？

template <typename T>
void show(T&);       // #1
template <typename T>
void show(T const&); // #2

int main()
{
    int a = 0;
    show(a);        // #1 to be called
}

我对这些偏序规则感到困惑。以下是一些引用：[temp.deduct.partial]/5

在完成偏序之前，对用于偏序的类型执行某些转换：

• 如果P是引用类型，P则替换为引用的类型。

• 如果A是引用类型，A则替换为引用的类型。

[temp.deduct.partial]/6

如果P和A都是引用类型（在被上面提到的类型替换之前），确定这两种类型中的哪一种（如果有的话）比另一个更符合 cv 限定；否则，出于偏序目的，这些类型被视为同样具有 cv 限定。下面将使用该确定的结果。

[temp.deduct.partial]/7

删除任何顶级 cv 限定符：

• 如果P是 cv 限定类型，P则替换为 的 cv 非限定版本P。

• 如果A是 cv 限定类型，A则替换为 的 cv 非限定版本A。 …

int indent = 0;
int listDir(const char* dirname){
    DIR* dir;
    struct dirent* d;
    if(!(dir = opendir(dirname)))
        return -1;
    while((d = readdir(dir)) != NULL){
        if(strcmp(d->d_name, ".") == 0 || strcmp(d->d_name, "..") == 0 ){
            continue;
        }
        else if(d->d_type != DT_DIR){ // Any except folders.
            printf("%*s- %s:%ld\n", indent, "", d->d_name, d->d_ino);
        }
        else if(d->d_type == DT_DIR){ // Folders only
            printf("%*s[%s]\n", indent, "", d->d_name);
            char path[1024];
            snprintf(path, sizeof(path), "%s/%s", dirname, d->d_name);
            indent +=2;
            listDir(path);
            indent -=2;
        }

这个函数工作得很好，但唯一的问题是它输出以下结果作为示例：

我需要输出是容器文件夹、文件和文件夹。文件夹应位于列表的末尾。例如，上面的输出应该是：

我使用标准BinaryHeap作为算法的一部分，我需要检索最大的对象（通过一些最大的定义）。两个非等价元素可能都一样大（因此它们在二进制堆中的相对顺序无关紧要）——例如，我可能只对多字段结构的单个字段的排序感兴趣。

因此，让我的类型实现Ord和Eq. 相反，我可能应该实施PartialOrd和PartialEq唯一。但是，唉，BinaryHeap需要它的元素是Ord！为什么会这样，使用BinaryHeap这些类型的最惯用的方法是什么？

（顺便说一句，在 C++ 中，在这种情况下我会很容易地编写自定义比较器类型，并在比较器类型上模板化优先级队列。所以我不认为我想做的在数学上或算法上是错误的。）

如果我们有一个这样的枚举类

enum class alpha{ a, b, c, d};

是否可以实现一个运算符，在字母表中的字母之间建立排序关系，使得

enum class alpha{ a, b, c, d};

constexpr auto operator <=> (alpha lhs, alpha rhs)
{ 
//how do we achieve this? 
};

#include <gtest/gtest.h>

TEST(alphabet, allows_ordering_comparison) 
{
    EXPECT_TRUE(alpha::a < alpha::b);
} 

小于比较将评估为真。我对此的平庸理解是 enum 是一种偏序。对代码中的错误表示歉意。考虑这个问题

比较关系（=、?、<、>、? 和 ?）之间的以下数学关系始终有效，因此在 Python 中默认实现（除了 2 个联合关系，这似乎是任意的，这也是本文的原因）：

• 2互补关系：“=和?互为互补”；
• 6个逆关系*：“=是自身的逆”，“?是自身的逆”，“<和>是彼此的逆”，“?和?是彼此的逆”；
• 2联合关系：“? 是联合 < 和 ="，而“? 是 > 和 =" 的联合。

以下比较关系之间的关系仅对总订单有效，因此在Python中默认不实现（但用户可以functools.total_ordering通过Python标准库提供的类装饰器方便地实现它们）：

• 4种互补关系：“<和?互为补”，">和?互为补”。

为什么 Python 只缺少上面的 2 个联合关系（“？是联合 < 和 =" 和“？是 > 和 =" 的联合）？

它应该提供的默认实现__le__来讲__lt__和__eq__，和的默认实现__ge__来讲__gt__和__eq__（性能，但可能是在C，像，像这些__ne__）：

def __le__(self, other):
    result_1 = self.__lt__(other)
    result_2 = self.__eq__(other)
    if result_1 is not NotImplemented and …