C++中模板选择的优先级

Question

我刚刚写了下面的代码

template<typename T>
inline bool contains(T haystack,typename T::key_type needle) {
    return haystack.find(needle) != haystack.end();
}

template<typename T>
inline bool contains(T haystack,typename T::value_type needle) {
    return find(haystack.begin(),haystack.end(),needle) != haystack.end();
}

vector当我实例化没有typedef 的模板时key_type，SFINAE将确保我不会实例化第一个版本。但是，如果我用 a 实例化模板map，它同时具有key_type和value_typetypedef，该怎么办？编译器将如何选择使用哪个模板函数？

对于当前的 STL 映射，key_type是 a ，但是如果我定义一个与 相同的pair类型会发生什么？key_typevalue_type

class MyMap {typedef int key_type;typedef int value_type;};
MyMap m;
contains(m,1); // both functions are valid, which will be chosen?

而惊喜惊喜，std::set已经key_type == value_type。所以我真的需要求助于模板元编程以获得简单的contains功能。叹息。

引用标准可加分。

Answer 1

如果您愿意这样做，您可以通过一些元编程来帮助您。基本上，您需要编写一个模板元函数来确定要调用一个或另一个函数的条件，并在子句中使用它enable_if_c：

template <typename T> inline
typename enable_if_c< has_key_type<T>::value, bool >::type
contains( T const & c, T::key_type const & k ) {...}        // associative container

template <typename T> inline
typename enable_if_c< !has_key_type<T>::value, bool >::type
contains( T const & c, T::value_type const & k ) {...}      // non-associative container

该enable_if_c模板是一个简单的常见 SFINAE 技巧（您可以从 C++0x 编译器或 boost 中使用）。它需要一个条件和一个类型，如果条件为真，它将生成参数类型的内部 typedef，如果不存在，则不会定义该内部类型，并且可以在 SFINAE 外部使用：

template <bool condition, typename T>
struct enable_if_c {};        // by default do not declare inner type

template <typename T>
struct enable_if_c<true,T> {  // if true, typedef the argument as inner type
    typedef T type;
};

现在有趣的部分是如何确定类型T具有内部类型key_type，虽然可能还有其他选项，但首先想到的是：

template <typename T>
class has_key_type {
    typedef char _a;
    struct _b { _a x[2]; };

    template <typename U>
    static _a foo( U const &, typename U::key_type* p = 0 );
    static _b foo( ... );
    static T& generate_ref();
public:
    static const bool value = sizeof(foo(generate_ref())) == sizeof(_a);
};

模板has_key_type将包含一个内部常量value仅true当传递的类型包含内部T::key_type。解决方案并不太复杂：定义一个模板函数，该函数对于除您想要检测的类型之外的所有类型都会失败，并提供带有省略号的不同重载，以便在模板（具有比省略号更高的优先级）失败时捕获它代替。然后使用返回类型的大小来检测编译器选择了哪个重载。这generate_ref是为了避免必须实际构造一个对象（即不要强加T可以以任何特定方式构造的对象）。

总体结果是，当类型T包含内部类型时key_type， 的结果has_key_type<T>::value将为 true，并且enable_if_c将启用第一个重载并禁用第二个重载，因此 SFINAE 将丢弃第二个重载，而不是因为类型第二个函数参数未定义，而是根据返回类型。

如果您想到这一点，就会发现围绕一个小更改的只是一堆样板代码：不是提供两个不明确的模板函数重载，而是提供一个模板重载和一个较低优先级的函数（省略号）。由于您无法真正使用该省略号函数来实现非关联容器版本，因此它用于获取布尔值，然后将该布尔值植入到常见的元编程结构和样板中。