Pesquisa heterogênea em contêineres associativos em C ++

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_bounde contains.



Feliz busca heterogênea, caro leitor!




All Articles