标签: partial-ordering

选择哪个类模板特化的首选规则包括将特化重写为函数模板,并通过函数模板[temp.class.order]的排序规则确定哪个函数模板更加专业化.考虑这个例子,然后:

#include <iostream>

template <class T> struct voider { using type = void; };
template <class T> using void_t = typename voider<T>::type;

template <class T, class U> struct A { };

template <class T> int foo(A<T, void_t<T>> ) { return 1; }
template <class T> int foo(A<T*, void> )     { return 2; }

int main() {
    std::cout << foo(A<int*, void>{});
}

gcc和clang都打印2在这里.这是有道理的一些前面的例子-推导对非推测的情况下(void对void_t<T>)只是忽略,所以推断<T, void_t<T>>反对<X*, void>成功,但推断<T*, void>针对<Y, void_t<Y>>在两个参数失败.精细. …

下面这段代码

class point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def dispc(self):
        return ('(' + str(self.x) + ',' + str(self.y) + ')')

    def __cmp__(self, other):
        return ((self.x > other.x) and (self.y > other.y))

在Python 2中工作正常,但在Python 3中我收到一个错误:

>>> p=point(2,3)
>>> q=point(3,4)
>>> p>q
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unorderable types: point() > point()

它只适用于==和!=.

阅读C++ 11标准我无法完全理解以下语句的含义.例子非常受欢迎.

两组类型用于确定部分排序.对于涉及的每个模板,都有原始函数类型和转换后的函数类型.[注意:转换类型的创建在14.5.6.2中描述. - 结束注释]演绎过程使用变换后的类型作为参数模板,将另一个模板的原始类型用作参数模板.对于部分排序比较中涉及的每种类型,此过程完成两次:一次使用转换的模板-1作为参数模板,使用template-2作为参数模板,再次使用转换的模板-2作为参数模板和模板-1作为参数模板
- N3242 14.8.2.4.2

在阅读另一个问题时,我遇到了部分排序问题,我将其缩减为以下测试用例

template<typename T>
struct Const { typedef void type; };

template<typename T>
void f(T, typename Const<T>::type*) { cout << "Const"; } // T1

template<typename T>
void f(T, void*) { cout << "void*"; } // T2

int main() {
  // GCC chokes on f(0, 0) (not being able to match against T1)
  void *p = 0;
  f(0, p);
}

对于两个函数模板,进入重载分辨率的特化的函数类型是void(int, void*).但是,部分排序(根据comeau和GCC)现在说第二个模板更专业.但为什么？

让我通过部分排序,并显示我有问题的地方.可以Q被用于确定根据偏序的独特由上型14.5.5.2.

• 变换参数列表T1(Q插入)(Q, typename Const<Q>::type*).参数的类型是AT=(Q, void*)
• 转换参数列表T2 …

虽然Rust实现的所有整数类型Ord都强调总排序,但浮点类型只能实现PartialOrd.这意味着可能存在无法比较的浮点值.这似乎很难消化,因为浮点数可以被认为是实数的近似值,恰好是一个完全有序的集合.即使增加正负无穷大也能保持实数的整数排序.为什么这个奇怪的选择在Rust？

此限制意味着通用排序/搜索算法只能假设数字的部分排序.IEEE 754标准似乎提供了总排序谓词.

NaN在通用代码中是如此多的问题吗？

考虑以下简单(在模板问题的范围内)示例:

#include <iostream>

template <typename T>
struct identity;

template <>
struct identity<int> {
    using type = int;
};

template<typename T> void bar(T, T ) { std::cout << "a\n"; }
template<typename T> void bar(T, typename identity<T>::type) { std::cout << "b\n"; }

int main ()
{
    bar(0, 0);
}

clang和gcc都在那里打印"a".根据[temp.deduct.partial]和[temp.func.order]中的规则,为了确定部分排序,我们需要合成一些独特的类型.所以我们有两次尝试扣除:

+---+-------------------------------+-------------------------------------------+
|   | Parameters                    | Arguments                                 |
+---+-------------------------------+-------------------------------------------+
| a | T, typename identity<T>::type | UniqueA, UniqueA                          |
| b | T, T                          | UniqueB, typename identity<UniqueB>::type |
+---+-------------------------------+-------------------------------------------+

根据Richard Corden的回答 …

我有一个具有部分订单关系的项目列表,i.e,该列表可以被认为是部分有序的集合.我想以与此问题相同的方式对此列表进行排序.正如那里正确回答的那样,这被称为拓扑排序.

有一个相当简单的已知算法来解决这个问题.我想要一个类似LINQ的实现.

我已经尝试使用OrderBy扩展方法,但我很确定它无法进行拓扑排序.问题是IComparer<TKey>界面无法表示部分订单.之所以会发生这种情况,是因为该Compare方法基本上可以返回3种值:零,负和正,意味着 分别等于,小于,然后大于.只有返回无关的方法才能实现有效的解决方案.

从我偏见的角度来看,我正在寻找的答案可能是由一个IPartialOrderComparer<T>接口和一个扩展方法组成的,如下所示:

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    IPartialOrderComparer<TKey> comparer
);

这将如何实施？IPartialOrderComparer<T>界面如何？你会推荐一种不同的方法吗？我很想看到它.也许有一种更好的方式来表示偏序,我不知道.

为什么接下来的两个模板声明不明确(所以两者都不比另一个更专业)？我知道这个问题已经在Stack Overflow上多次提出,但通常,人们会回答如何解决歧义,而不是为什么会发生这种情况.

一世. template <class T> void func(char* buf, T size) {}

II. template <std::size_t N> void func(char (&buf)[N], std::size_t size) {}

尝试传递C++ 14标准的步骤来解决部分函数模板排序(14.5.6.2):

要生成转换模板,对于每种类型,非类型或模板模板参数(包括其模板参数包(14.5.3))分别合成唯一类型,值或类模板,并将其替换为该参数的每次出现在模板的函数类型中.

转换函数我模板的函数类型是:void func(char*, U1),其中U1是一些独特的合成类型.

转换函数II模板的函数类型是:void func(char (&buf)[N1], std::size_t),其中N1是一些独特的合成值.

使用转换后的函数模板的函数类型,对14.8.2.4中描述的其他模板执行类型推导.

因此,让我们尝试在一侧执行类型推导(使用第一个模板作为参数,第二个模板作为参数模板),在另一侧.

情况1.

参数模板:template <std::size_t N> void func(char (&buf)[N], std::size_t size).转换参数模板:void func(char*, U1).

试图推断出模板参数." char (&buf)[N]"不能从" char*"类型中推断出来.U1也与std::size_t类型不匹配.失败.

案例2.

参数模板:template <class T> void func(char* buf, T size).转换参数模板:void func(char (&buf)[N1], std::size_t) …

这是我的问题:我有一个序列S(非空但可能不是不同)设置s_i,并且对于每个s_i需要知道S(i≠j)中有多少个集合s_j是s_i的子集.

我还需要增量性能:一旦我完成所有计数,我可以用s_i的某个子集替换一组s_i并逐步更新计数.

使用纯功能代码执行所有这些将是一个巨大的优势(我在Scala中的代码).

由于set包含是一个部分排序,我认为解决我的问题的最好方法是构建一个DAG,它表示集合的Hasse图,边表示包含,并将一个整数值连接到表示大小的每个节点节点下方的子d加1.但是,我已经被困了好几天试图开发从部分排序构建Hasse图的算法(让我们不谈增量!),即使我认为它会是一些标准本科教材.

这是我的数据结构:

case class HNode[A] (
  val v: A,
  val child: List[HNode[A]]) {
  val rank = 1 + child.map(_.rank).sum
}

我的DAG由根列表和一些部分排序定义:

class Hasse[A](val po: PartialOrdering[A], val roots: List[HNode[A]]) {
  def +(v: A): Hasse[A] = new Hasse[A](po, add(v, roots))

  private def collect(v: A, roots: List[HNode[A]], collected: List[HNode[A]]): List[HNode[A]] =
    if (roots == Nil) collected
    else {
      val (subsets, remaining) = roots.partition(r => po.lteq(r.v, v))
      collect(v, remaining.map(_.child).flatten, subsets.filter(r => !collected.exists(c => po.lteq(r.v, c.v))) ::: collected)
    }
}

我很困在这里.我最后向DAG添加了一个新值v:

1. 找到DAG中v的所有"根子集"rs_i,即v的子集,使得rs_i的超集不是v的子集.这可以通过在图上执行搜索(BFS或DFS)非常容易地完成( …

在C++ 11草案的14.8.2.4p10中,写了

如果对于每种类型被认为是给定的模板至少对所有类型都是专用的,并且对于某些类型更专用,而另一个模板对于任何类型都不是更专用的,或者至少不是对任何类型的专用,那么给定的模板比其他模板更专业.

为什么"或者至少不是任何类型的专业"？据我所知,如果我们有一个类型列表

T1, T2, T3
U1, U2, U3

如果所有Ts至少都是专业的,有些则更专业.并且没有一个人更专业,那么在我看来,从逻辑上讲,整个T的集合比U集合更专业.为什么当时没有一个人至少比相应的Ts更专业？