Os contêineres associativos C ++ funcionam com um tipo de chave específico. Para pesquisá-los por uma chave deste tipo ( std :: string , std :: string_view , const char * ), podemos incorrer em perdas de desempenho significativas. Neste artigo, mostrarei como evitar isso com um recurso de pesquisa heterogêneo adicionado recentemente.
Tendo um contêiner std :: map <std :: string, int> com , devemos ser informados sobre o possível alto custo ao pesquisar (e algumas outras operações com uma chave como parâmetro) nele no estilo de c.find ("hello world") . O fato é que por padrão todas essas operações requerem uma chave do tipo necessário, no nosso caso é std :: string . Como resultado, ao chamar find, precisamos construir implicitamente uma chave do tipo std :: string de const char * , o que nos custará, no máximo, um memcpy extra (se nossa implementação de biblioteca padrão tiver "otimização de pequena string" e a chave for curta), e também extra strlen(a menos que o compilador adivinhe ou não tenha como calcular o comprimento da linha em tempo de compilação). No pior caso, você terá que pagar integralmente: alocando e liberando memória do heap para uma chave temporária em um local aparentemente plano, e isso já pode ser comparável ao próprio tempo de pesquisa.
Podemos evitar trabalho desnecessário com pesquisa heterogênea. Funções para sua operação correta foram adicionadas a contêineres ordenados ( conjunto , multiset , mapa , multimapa ) em todos os lugares semelhantes desde o padrão C ++ 14 e a contêineres não ordenados ( unordered_set , unordered_multiset , unordered_map , unordered_multimap ) desde C ++ 20.
// C++14
iterator find(const Key& key);
const_iterator find(const Key& key) const;
// C++14
template < class K > iterator find(const K& x);
template < class K > const_iterator find(const K& x) const;
, , C++ , . std::map<std::string, int> std::less<std::string> :
// T , .. std::string
bool operator()(const T& lhs, const T& rhs) const;
, ( ). std::less<void> .
template <>
struct less<void> {
using is_transparent = void;
template < class T, class U >
bool operator()(T&& t, U&& u) const {
return std::forward<T>(t) < std::forward<U>(u);
}
};
,constexpr
noexcept
.
is_transparent , .
, operator<(const std::string&, const char*) :
std::map<std::string, int, std::less<>> c;
c.find("hello world");
, , , operator< . - , , std::thread std::set std::thread::id.
struct thread_compare {
using is_transparent = void;
bool operator()(const std::thread& a, const std::thread& b) const {
return a.get_id() < b.get_id();
}
bool operator()(const std::thread& a, std::thread::id b) const {
return a.get_id() < b;
}
bool operator()(std::thread::id a, const std::thread& b) const {
return a < b.get_id();
}
};
//
std::set<std::thread, thread_compare> threads;
// id
threads.find(std::this_thread::get_id());
Bem, não se esqueça que não se trata apenas da função find
. Apenas esta diz respeito a funções: count
, equal_range
, lower_bound
, upper_bound
e contains
.
Feliz busca heterogênea, caro leitor!