标签: partial-ordering

在阅读了如何使这些std :: function参数明确无误后,我完全糊涂了？到目前为止,我认为我理解函数模板的部分排序是什么,但在阅读了这个问题后,我写了三个例子来检查编译器的行为,并且收到的结果很难让我理解.

示例#1

template <class T>
void foo(T) {}

template <class T>
void foo(T&) {}

int main()
{
  int i;
  foo<int>(i); // error: call is ambiguous! 
}

问题:这两个功能都是可行的,这是显而易见的,但不是那个T&比专业更专业的功能T？相反,编译器会引发模糊的调用错误.

例#2

#include <iostream>

template <class T>
struct X {};

template <>
struct X<int> 
{
  X() {}
  X(X<int&> const&) {} // X<int> is constructible from X<int&>
  // note: this is not a copy constructor!
};

template <>
struct X<int&> …

我能得到的所有编译器都同意这很好:

template <typename Check, typename... T>
auto foo(Check, T...) -> void;

template <typename... T>
auto foo(int, T...) -> void;

int main()
{
  foo(7, "");
}

但是,根据gcc,以下代码(具有无法从函数参数推导出的前导模板参数)是不明确的:

template <typename X, typename Check, typename... T>
auto bar(Check, T...) -> void;

template <typename X, typename... T>
auto bar(int, T...) -> void;

int main()
{
  bar<void>(7, ""); // ambiguous according to gcc
  bar<void>(7);     // just fine
}

另一方面,clang,msvc和icc对此非常满意.

哪个编译器是对的？

参考标准的各个部分是优选的.

如果参数之一是占位符类型，则在非类型模板参数的情况下选择重载函数模板的规则是什么。我对编译器当前的行为感到困惑，请考虑下一个示例：

template<int N> struct A{};

template<auto... N> void f(A<N...>);
template<int N>     void f(A<N>) {}

template<auto N>    void g(A<N>);
template<int N>     void g(A<N>) {}

int main() {
    f( A<1>{} ); // ok in GCC and Clang, error in MSVC
    g( A<1>{} ); // ok in GCC, error in Clang and MSVC
}

这里 MSVC 无法在两组重载之间进行选择。另一方面，GCC总是选择类型更具体的函数模板<int>。Clang 有点处于中间位置，它<int>比参数 pack 更受欢迎，但它在和重载<auto...>之间的选择过程中发现了歧义。在线演示： https: //gcc.godbolt.org/z/4EK99Gjhx<int><auto>

哪一项行为是正确的或者标准没有明确规定？

似乎scala.math.PartialOrdering.lteq必须始终定义为(或至少给出相同的结果):

override def lteq(x: Pattern, y: Pattern) = {
    tryCompare(x, y).map(_ <= 0).getOrElse(false)
}

是否有某种原因这种实施没有在scala.math.PartialOrdering特质中给出？

指针关系运算符没有定义总顺序(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定义:

  template<typename _Tp = void>
    struct less;

  template<typename _Tp>
    struct less : public binary_function<_Tp, _Tp, bool>
    {
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x < __y; }
    };

  template<>
    struct less<void>
    {
      template <typename _Tp, typename _Up>
        auto
        operator()(_Tp&& __t, _Up&& __u) const
        noexcept(noexcept(std::forward<_Tp>(__t) < …

根据[temp.class.order]§14.5.5.2,t在此示例中选择部分特化:

template< typename >
struct s { typedef void v, w; };

template< typename, typename = void >
struct t {};

template< typename c >
struct t< c, typename c::v > {};

template< typename c >
struct t< s< c >, typename s< c >::w > {};

t< s< int > > q;

等效f于此示例中的重载选择:

template< typename >
struct s { typedef void v, w; };

template< typename, typename = void >
struct t {};

template< typename …

可能最好用一个小例子来说明.
鉴于这种关系

A < B < C
A < P < Q 

正确的产出将是

ABCPQ or APQBC or APBCQ ... etc.

换句话说,任何排序都是有效的,其中给定的关系成立.

我最感兴趣的是最容易实现的解决方案,但速度和时间方面的最佳O(n)也很有趣.

_{在提到这个问题时,该问题确实具有相同的标题,但我在标准中找到了答案.我继续挖掘这个主题,最后找出一个不适用这个答案的示例代码.}

让我们考虑一下这段代码:

template<class T> void func(T* buf);           //template I
template<size_t N> void func(char (&buf) [N]); //template II

void g(char (&buf)[3])
   {
   func(buf) //Error: ambiguous function call (Clang, GCC, ICC, MSVC)
   }

根据[temp.func.order]和[temp.deduct.partial]中的部分排序规则,如果通过执行这段代码解释了这个规则,模板II应该比模板I更专业:

template <class T> void func1(T* buf) {}
template <std::size_t N> void func2(char (&buf)[N]) {}

struct invented_T{};
constexpr std::size_t invented_N=42;

void is_template_I_more_specialized(invented_T* buf)
  {
  func2(buf);
  //DO NOT COMPILE
  // => template I is not more specialized than …

背景:

我有一个小的(目前不到100个)但正在增长的正则表达式集合,我想优化确定给定文本字符串的过程我的集合中哪些RE与文本字符串匹配.

一些RE有一个排序关系 - 例如,如果我知道字符串$ t匹配/ windows/i,那么我也知道$ t匹配/windows.*2000/i.因此,当我对我的集合中的RE测试$ t时,我可以跳过测试/ windows/i,如果我已经针对/windows.*2000/i测试了$ t并找到了匹配(尽管如果/windows.*2000/i确实如此)不匹配当然我不能跳过对/ windows/i的测试.

请注意,我的集合中的所有RE都不是完全等效的(对于任何一对RE,至少有一个匹配一个的文本字符串与另一个不匹配).

战略:

我想构建一个有向图G,其中有一个节点用于我的集合中的每个RE,并且每对RE的有向边具有排序关系(A - > B表示"匹配A意味着与B匹配"),并找到一个图的节点的"最小生成集"(节点S的最小集合,使得G中的每个节点位于源自S的有向路径上).

简单的部分:

有很多免费的算法可用于定向非循环图.因此,一旦为我的RE集合构建了图形G(这是不同的,应该保证G是非循环的),我不希望找到一个合适的算法来寻找G的最小生成集.

在哪里我需要帮助:

我想找到一种有效的方法来查找我的集合中的RE之间的所有排序关系 - 也许还要确保集合中没有两个RE是等价的(我需要一种方法来自动验证这个,因为新的RE是添加).

因此,我的(基本上是随机的)网络搜索至少提出了一个合理的说法,即确定两个RE之间存在什么(如果有的话)排序关系的合理方法确实存在,但尚未发现任何完整算法的描述.

有没有人知道现有的实现(用于比较RE),这些实现是合理有效的,可免费获得的,并且(理想情况下)是用一种流行的脚本语言或C/C++实现的？

为什么这个含糊不清？

template<class T> void g(T)  {}   // 1
template<class T> void g(T&) {}   // 2

int main() {
    int  q;
    g(q);
}

我知道这是部分订购的背景.而我的,可能是错误的想法是:任何来自#2的T&#都可以放在#1中,但#1中的任何T都不是#2中的合法.所以部分排序应该有效.