Я решил эту проблему, которая требовала от меня группировки анаграмм. Таким образом, для данного ввода он должен дать следующий результат:
Ввод: strs = ["eat","tea","tan","ate","nat","bat"]
Вывод: [["летучая мышь"],["нат","загар"],["ели","есть","чай"]]
Я решил использовать класс Signature для хранения частоты символов для каждого слова вместе с простым алгоритмом хеширования.
#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 };
};
Затем я использую эту специализацию шаблона:
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 для решения проблемы и возврата правильно сгруппированных анаграмм:
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 { ... }
}
Есть ли способ добиться этого?
«Ненависть приводит к страданию» — Йода.
namespace std { template <> struct std::hash<Signature> ...
-- дополнительная квалификация не допускается. Вы либо специализируетесь на заключении пространства имен, то есть глобальном, написании struct std::hash...
, либо на стандартном пространстве имен без квалификации hash
Вам не следует специализироваться std::hash
на namespace std
. Вам следует специализироваться std::hash
на глобальном пространстве имен. Когда вы используете struct std::hash
, вы уже специализируетесь на namespace std
для определенного пользователем типа.
Поскольку Signature
находится в глобальном пространстве имен, специализация должна быть
// 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 - хорошо компилируется в namespace foo
.
Поиск, зависящий от аргументов, не имеет к этому никакого отношения. Сопоставление специализаций просто учитывает все предыдущие явные и частичные объявления специализации того же основного шаблона, независимо от того, где эти объявления находились. Почему вы говорите «вы не должны» специализироваться на namespace std
?
Явная специализация может быть объявлена в любой области, где может быть определен ее основной шаблон (которая может отличаться от области, в которой определен основной шаблон; например, при специализации вне класса шаблона члена). Явная специализация должна появиться после объявления неспециализированного шаблона. en.cppreference.com/w/cpp/language/template_specialization