Приоритет выбора шаблона в 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, в котором нет key_type typedef, SFINAE убедится, что я не буду создавать экземпляр первой версии. Но что, если я создаю экземпляр шаблона с map, который имеет как key_type, так и value_type typedefs? Как компилятор выберет, какую функцию шаблона использовать?

При текущей карте STL key_type - это pair, однако что произойдет, если я определю тип, в котором key_type совпадает с value_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, только если тип, переданный int, содержит внутренний тип T::key_type. Разрешения не слишком сложны: определите шаблонную функцию, которая не будет работать для всех типов, кроме той, которую вы хотите обнаружить, и предоставьте другую перегрузку с многоточием, так что она будет ловить, если шаблон (имеет более высокий приоритет, чем многоточие) не сможет замена. Затем используйте размер возвращаемых типов, чтобы определить, какая перегрузка была выбрана компилятором. generate_ref существует для того, чтобы не создавать объект (т. Е. Не навязывать, что T может быть создан любым конкретным способом).

Общий результат заключается в том, что когда тип T содержит внутренний тип key_type, результат has_key_type<T>::value будет равен true, а enable_if_c включит первую перегрузку и отключит вторую, поэтому SFINAE будет Отмените вторую перегрузку не из-за того, что аргумент функции типа второй не определен, а из-за условий возвращаемого типа.

Если вы подумаете об этом, вокруг небольшого изменения есть всего лишь куча кода котельной пластины: вместо двух неоднозначных перегрузок функции шаблона, обеспечьте перегрузку шаблона и функцию с меньшим приоритетом (многоточие). Поскольку вы не можете реально использовать эту многоточную функцию для реализации неассоциативной контейнерной версии, она используется для получения логического значения, которое затем добавляется в общие структуры метапрограммирования и шаблон.

Answer 2

Если есть два или более одинаково хороших кандидата на специализацию шаблона функции, вы получите ошибку компилятора.

Стандарт C ++ говорит:

Еслисуществует ровно одна жизнеспособная функция, которая лучше, чем все другие жизнеспособные функции, тогда она выбирается по разрешению перегрузки;в противном случае вызов плохо сформирован12).

Answer 3

Шаблон key_type соответствует, шаблон value_type - нет.

map<int,int>::value_type - это pair<const int,int>, поэтому будет соответствовать только ваш первый шаблон.Если ваш второй шаблон использовал, например, mapped_type, у вас возникла бы ошибка компилятора из-за неоднозначности.

Answer 4

Использование этого на карте, кажется, работает.

Однако, если бы вы использовали его в каком-либо контейнере, в котором key_type и value_type были одного типа, это в конечном итоге определяло бы «одну и ту же» функцию дважды (и в дополнение к этому).1004 * §13.1

Некоторые объявления функций не могут быть перегружены:
...
- Объявления параметров, отличающиеся только использованием эквивалентных typedef, «типы» эквивалентны.Определение типа - это не отдельный тип, а только синоним другого типа (7.1.3).
[Пример:
typedef int Int;
void f(int i);
void f(Int i); // OK: redeclaration of f(int)
void f(int i) { /* ... */ }
void f(Int i) { /* ... */ } // error: redefinition of f(int)
- конец примера]