2019-04-10

如何判断一个容器是否关联容器

如果你正在编写一个C++工具库，那么有可能需要知道一个容器是否关联容器。例如，你要写一个Contain()工具函数，该函数用来判断元素是否在容器中。而且你希望对于不同的容器，总是使用性能最优的查找方式，也就是说，对于关联容器，使用find()成员函数；而对于非关联容器，则使用std::find()函数。

此时，你也许需要使用模板元编程。在STL中，所有关联容器都有一个特征：定义了key_type成员类型，根据这个特征即可判断某个类型是否关联容器。

进行这个判断的模板元类型如下所示：

template<typename C>
struct IsAssociativeContainer {
private:
    template<typename T>
    static constexpr bool Test(typename T::key_type*) {
        return true;
    }

    template<typename T>
    static constexpr bool Test(...) {
        return false;
    }

public:
    static constexpr bool Value = Test<C>(nullptr);
};

使用方式：

std::cout << IsAssociativeContainer<std::vector<int>>::Value;    // false
std::cout << IsAssociativeContainer<std::list<int>>::Value;      // false
std::cout << IsAssociativeContainer<std::set<int>>::Value;       // true
std::cout << IsAssociativeContainer<std::map<int, int>>::Value;  // true

IsAssociativeContainer的实现使用了C++模板的SFINAE技术，全称为“Substitution Failure Is Not An Error”，它的意思是：当编译器试图在多个重载的模板函数中查找最佳匹配时，如果某个函数的模板参数推导失败，那么这个函数会被丢弃，而不会出现编译错误。

首先，在IsAssociativeContainer内部，定义了两个重载的Test()模板函数，第一个重载带有T::key_type*参数，对应关联容器类型，该函数返回true；第二个重载接受可变参数，对应非关联容器类型，该函数返回false。

然后，在定义静态常量Value时，使用Test<C>(nullptr)对其赋值。这里正是C++魔法起作用的时刻：编译器要在两个Test()重载函数中找到最佳匹配，使用它的返回值作为Value的值。假如模板类型C不是关联容器，它没有key_type成员类型，那么编译器在推导第一个重载的时候会失败，这个重载函数随即被丢弃，就像它从来没有出现过那样，所以编译器只能选择第二个重载。假如C是关联容器，它具有key_type成员类型，那么两个重载函数都能推导成功，此时编译器会优先选择第一个重载，因为接受可变参数的重载函数优先级是最低的。这种只接受可变参数的模板函数经常与SFINAE一起使用。

C++