C++ STD template specialization inside another namespace

Question

I've solved this problem which required me to group anagrams together. So for the given input it should give the following output:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

I decided to use a class called Signature to hold the character frequency for each word alongside a simple hashing algorithm

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <array>
#include <list>
#include <string>

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

class Signature 
{
public:
    void Push( char c ) 
    {
        ++counts[c - 'a']; 
    }
    bool operator==( const Signature& rhs ) const 
    { 
        return counts == rhs.counts; 
    }
    size_t Hash() const 
    {
        size_t hash = 0;
        for( auto v : counts ) 
        {
            hash_combine( hash, v );
        }

        return hash;
    }

private:
    std::array<unsigned char, 26> counts = { 0 };
};

Then I use this template specialization:

namespace std 
{
    template <> struct std::hash<Signature> 
    {
        size_t operator()( const Signature& s ) const 
        { 
            return s.Hash(); 
        }
    };
}

Followed by this AnagramMap class which has an unordered map of the signatures

class AnagramMap 
{
public:
    void Push( const Signature& sig, int index ) 
    {
        auto val = map.emplace( sig, std::list{ index } );
        if( !val.second ) 
        {
            val.first->second.emplace_back( index );
        }
    }
    size_t GetSize() 
    { 
        return map.size(); 
    }
    auto begin() 
    { 
        return map.begin(); 
    }
    auto end() 
    { 
        return map.end(); 
    }

private:
    std::unordered_map<Signature, std::list<int>> map;
};

To finish this, the Solution class uses both the Signature and AnagramMap classes to solve the problem and return the anagrams properly grouped:

class Solution 
{
public:
    std::vector<std::vector<std::string>> groupAnagrams( std::vector<std::string>& strs )
    {
        AnagramMap anagrams;

        for( auto i = 0; i < strs.size(); ++i )
        {
            Signature sig;
            for( auto c : strs[i] )
            {
                sig.Push( c );
            }

            anagrams.Push( sig, i );
        }

        std::vector<std::vector<std::string>> result;

        for( auto& anagram : anagrams )
        {
            auto current_list = anagram.second;
            std::vector<std::string> current_anagram_group;

            while( !current_list.empty() )
            {
                auto current_anagram = strs[current_list.front()];
                current_list.pop_front();
                current_anagram_group.emplace_back( current_anagram );
            }
            result.emplace_back( current_anagram_group );
        }

        return result;
    }
};

This is all working fine, but now I wanted to move both the Signature and AnagramMap classes into a new namespace but not the Solution class, something like this:

namespace foo
{
    class Signature { ... }
    class AnagramMap { ... }
    
}

Is there a way to achieve this?

Answer 1

You should not specialize std::hash in the namespace std. You should specialize std::hash in the global namespace. When you use struct std::hash you already specialize it in the namespace std for a user defined type.

Since Signature is in the global namespace, the specialization should be

// DELETE namespace std 
// DELETE {
template <> struct std::hash<Signature> 
{
    size_t operator()( const Signature& s ) const 
    { 
        return s.Hash(); 
    }
};
// DELETE }

https://godbolt.org/z/v46G34GTq - compiles well in namespace foo.