Should the type of an argument for a non-type template parameter match the type of the parameter?

Question

I was instantiating a std::unordered_set of std::array<int,3>, I found that the following code cannot pass compilation:

#include <iostream>
#include <unordered_set>
#include <array>

namespace std {
    template <class T>
    inline void hash_combine(size_t& seed, const T& v) {
        hash<T> hasher;
        seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }

    template <typename T, int N>
    struct hash<array<T, N>>
    {
        size_t operator()(array<T, N> arr) const noexcept {
            size_t hs = 0;
            for (auto iter = arr.begin(); iter != arr.end(); iter++) {
                hash_combine(hs, *iter);
            }
            return hs;
        }
    };
}

int main(int argc, char** argv) {
    std::unordered_set<std::array<int, 3>> arrset;
    std::cout << arrset.size() << std::endl;
    return 0;
}

The error message tells me that the specialization hash<array<T, N>> is not detected. After some hard work, I found that it is caused by the mismatching between the type of non-type template argument N and the type of parameter (size_t). But shouldn't the compiler cast the int N to size_t N automatically? Since the usage of std::array<int, true> also passes the compilation, as I have tested on g++9.4. Is there any specific mention in the C++ standard regarding this particular situation?

Answer 1

std::hash is a red herring, as do I interpret the formal UB described in @Jason's answer to be, w.r.t. to OP's question:

But shouldn't the compiler cast the int N to size_t N automatically?

A minimal example:

#include <cstddef>

template<std::size_t N>
struct A {};

template<typename T>
struct S { S() = delete; };

template<int N>
struct S<A<N>> {};  // #1

S<A<4>> s{};  // error ("use of deleted function")
              // picks non-defined primary template

[temp.class.spec.match] describes the relevant rules [emphasis mine]:

/1 When a class template is used in a context that requires an instantiation of the class, it is necessary to determine whether the instantiation is to be generated using the primary template or one of the partial specializations. [...]

/2 A partial specialization matches a given actual template argument list if the template arguments of the partial specialization can be deduced from the actual template argument list, [...]

The actual template argument list, from #1 above, is A<4>, from which we can deduce the type A<std::size_t{4}>. The template argument list for the partial specialization, however, is A<int{N}>, which is not a match for the actual template argument list. In fact, the partial specialization #1 will never be used (given the current example), as we cannot produce a template argument list that will match it.

Answer 2

You will need to add the hash function to the template arguments too. Here is a revised version of your code (with some small feedback as well).

#include <iostream>
#include <unordered_set>
#include <array>

namespace std
{
    namespace details
    {
        template <class type_t>
        inline void hash_combine(size_t& seed, const type_t& v)
        {
            auto hash = std::hash<type_t>()(v);
            seed ^= hash + 0x9e3779b9ul + (seed << 6) + (seed >> 2); // initialize magic number as std::size_t too 
        }
    }

    template <typename type_t, std::size_t N>
    struct hash<std::array<type_t, N>>
    {
        size_t operator()(const std::array<type_t, N>& arr) const noexcept // pass by const ref to avoid copies
        {
            size_t hs{ 0ul };

            for (const auto& value : arr) // use range based for loop
            {
                details::hash_combine(hs, value);
            }
            return hs;
        }
    };

}

int main()
{
    std::unordered_set<std::array<int,3>> arrset;

    arrset.insert({ 1,2 });
    std::cout << arrset.size() << std::endl;
    return 0;
}

Answer 3

Specializing std::hash for std::array<int, N> leads to undefined behavior.

From [namespace.std]:

Unless explicitly prohibited, a program may add a template specialization for any standard library class template to namespace std provided that

(a) the added declaration depends on at least one program-defined type and

(b) the specialization meets the standard library requirements for the original template.

(emphasis mine)

But the first requirement of having at least one program-defined type is not satisfied in your example. From [defns.prog.def.type]:

non-closure class type or enumeration type that is not part of the C++ standard library and not defined by the implementation, or a closure type of a non-implementation-provided lambda expression, or an instantiation of a program-defined specialization.

---

One possible solution is to use a lambda.