Recherche hétérogène dans des conteneurs associatifs en C ++

Les conteneurs associatifs C ++ fonctionnent avec un type de clé spécifique. Pour les rechercher par une clé de ce type ( std :: string , std :: string_view , const char * ), nous pouvons subir des pertes de performances importantes. Dans cet article, je vais vous montrer comment éviter cela avec une fonction de recherche hétérogène ajoutée relativement récemment.

Avoir un conteneur std :: map <std :: string, int> avec nous devrions être informés du coût élevé possible lors de la recherche (et de certaines autres opérations avec une clé comme paramètre) dans le style de c.find ("hello world") . Le fait est que par défaut toutes ces opérations nécessitent une clé du type requis, dans notre cas c'est std :: string . En conséquence, lors de l'appel de find, nous devons construire implicitement une clé de type std :: string à partir de const char * , ce qui nous coûtera au mieux un memcpy supplémentaire (si notre implémentation de bibliothèque standard a une "optimisation de petite chaîne" et que la clé est courte), et aussi extra strlen(sauf si le compilateur devine ou n'a aucun moyen de calculer la longueur de la ligne au moment de la compilation). Dans le pire des cas, vous devrez payer intégralement: en allouant et en libérant de la mémoire du tas pour une clé temporaire à un endroit apparemment plat, et cela peut déjà être comparable au temps de recherche lui-même.

Nous pouvons éviter un travail inutile avec une recherche hétérogène. Des fonctions pour son bon fonctionnement ont été ajoutées aux conteneurs ordonnés ( set , multiset , map , multimap ) dans tous les endroits similaires depuis le standard C ++ 14 et aux conteneurs non ordonnés ( unordered_set , unordered_multiset , unordered_map , unordered_multimap ) depuis 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());

Eh bien, n'oubliez pas que ce n'est pas seulement une question de fonction find. Juste cette fonction concerne: count, equal_range, lower_bound, upper_boundet contains.

Bonne recherche hétérogène, cher lecteur!