根据可散列的模板使用正确的容器类型

Question

我正在开发需要关联容器（map 或 unordered_map）的 C++ class

我的 class 看起来像这样：

    template<typename T>
    class myClass
    {
            static_assert(
                std::is_copy_constructible<T>::value,
                "content of myClass should be copy constructible"
            );
            // TODO: check if T::operator== exists

            /* if hash<T> is available */
            using container = std::unordered_map<T,T>;
            /* if hash<T> is unavailable */
            using container = std::map<T,T>;

        public:
            myClass() = default;

            [...]

        private:
            container m_mapping;
    }

我希望从模板中自动推导出容器 T:

如果 std::hash<T> 可用，我们应该使用 unordered_map 来提高性能。
如果 std::hash<T> 不可用，我们应该回退到 map

有没有办法使用 C++ 模板来做到这一点？

Answer 1

这可以通过一个相当简单的辅助模板来完成：

template <typename T, typename = void>
struct helper
{
    using type = std::map<T, T>;
};

template <typename T>
struct helper<T, std::void_t<decltype(std::hash<T>())>>
{
    using type = std::unordered_map<T, T>;
};

Live demo

如果 std::hash<T>() 格式正确，则选择该专业化，否则 SFINAE 启动并使用基本模板。然后你可以调整 myClass 看起来像这样：

template<typename T>
class myClass
{
    //...
    using container = typename helper<T>::type;
    //...

private:
    //...
    container m_mapping;
    //...
};

请注意，std::void_t 是在 C++17 中添加的。如果您无法访问 C++17，您可以实现自己的 void_t as

template <typename...>
using void_t = void;

Answer 2

如果我猜对了，那么在 C++11 和更新版本中很容易实现。首先，您可以使用 type_traits header 中的条件类型。它看起来像这样：

std::conditional<test, Type1, Type2>

如果 test 为真 conditional 具有等于 Type1'. Otherwise, it has member type equal toType2` 的内部类型 type。

其次，我们需要上面的 test 值，为此我们必须编写一个特征。 ~~我将使用此处的示例：How to decide if a template specialization exist - 让我们保持简单。~~

~~template<class T> bool is_hashable_v = is_complete<std::hash<T>>::value;~~

编辑：以上不起作用。让我们使用 enable_if 然后：

template<class T, class = void>
struct is_hashable : std::false_type {};

template<class T>
struct is_hashable<
    T, 
    typename std::enable_if<decltype(std::hash<T>())>::type
> : std::true_type {};

template<class T>
bool is_hashable_v = is_hashable<T>::value;

所以把它们放在一起，如果你有以上is_hashable_v:

using container =
    typename std::conditional<
        is_hashable_v<T>, 
        std::unordered_map<T, T>,
        std::map<T, T> 
    >::type;

Answer 3

我意识到 std::hash<T> 不是静态函数，而是带有 operator() 和构造函数的结构。与其尝试检查 std::hash<T>()（构造函数）或 std::hash<T>()()（散列函数）是否存在，我们可以简单地检查是否存在 std::hash<T> is_constructible

这使得以下代码有效：

using container = typename std::conditional<
    std::is_constructible<std::hash<T>>::value,
    std::unordered_map<T,T>,
    std::map<T,T>
>::type;

Answer 4

使用 C++20

您可以使用概念：

template<typename Key>
concept Hashable = requires(Key a) {
    { std::hash<Key>{}(a) } -> std::convertible_to<std::size_t>;
};

template<typename Key>
concept Sortable = requires(Key a, Key b) {
    { a < b } -> std::convertible_to<bool>;
};

template<typename Key>
concept SortableNotHashable = Sortable<Key> && !Hashable<Key>;

template <typename Key, typename Value>
struct associative_map;

template <SortableNotHashable Key, typename Value>
struct associative_map<Key, Value>
: std::map<Key, Value> {
    using std::map<Key, Value>::map;
};

template <Hashable Key, typename Value>
struct associative_map<Key, Value> 
: std::unordered_map<Key, Value> {
    using std::unordered_map<Key, Value>::unordered_map;
};

代码：https://godbolt.org/z/3GjuXt

C++ 20 之前

template <typename Key, typename Value, typename = void>
struct associative_map
: std::map<Key, Value> {
    using std::map<Key, Value>::map;
};

template <typename Key, typename Value>
struct associative_map<Key, Value, std::void_t<decltype(std::hash<Key>())>> 
: std::unordered_map<Key, Value> {
    using std::unordered_map<Key, Value>::unordered_map;
};

// Usage:

class Number {
    int _i;
public:
    Number(int i): _i(i) {}
    operator int()const {return _i;}
};

int main() {
    // associative_map below is std::unordered_map
    associative_map<int, std::string> int2string = { {1, "one"} };
    int2string[7] = "seven";
    for(const auto& p : int2string) {
        std::cout << p.first << ": " << p.second << std::endl;
    }
    // associative_map below is std::map
    associative_map<Number, std::string> number2string = { {1, "one"} };
    number2string[7] = "seven";
    for(const auto& p : number2string) {
        std::cout << p.first << ": " << p.second << std::endl;
    }
}

根据可散列的模板使用正确的容器类型

using correct container type depending on a template being hashable

c++

templates

template-specialization

使用 C++20

C++ 20 之前