另一个命名空间内的 C++ STD 模板专业化

Question

我已经解决了这个需要我将字谜组合在一起的问题。 因此，对于给定的输入，它应该给出以下输出：

输入：strs = ["eat","tea","tan","ate","nat","bat"]

输出：[["bat"],["nat","tan"],["ate","eat","tea"]]

我决定使用一个名为 Signature 的类来保存每个单词的字符频率以及简单的哈希算法

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 };
};

然后我使用这个模板专业化：

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

后面是这个 AnagramMap 类，它具有无序的签名映射

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;
};

为了完成此任务，Solution类使用Signature和AnagramMap类来解决问题并返回正确分组的anagrams：

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;
    }
};

这一切都工作正常，但现在我想将 Signature 和 AnagramMap 类移动到新的命名空间中，而不是 Solution 类，如下所示：

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

有没有办法实现这个目标？

Answer 1

您不得专注于

std::hash

namespace std

。您应该在参数的命名空间中专门化

std::hash

，并且由于依赖于参数的查找规则将使用它。

由于

Signature

位于全局命名空间中，因此专业化应该是

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