Búsqueda heterogénea en contenedores asociativos en C ++

Los contenedores asociativos de C ++ funcionan con un tipo de clave específico. Para buscarlos por una clave de este tipo ( std :: string , std :: string_view , const char * ), podemos incurrir en pérdidas significativas de rendimiento. En este artículo, le mostraré cómo evitar esto con una función de búsqueda heterogénea recientemente agregada.

Teniendo un contenedor std :: map <std :: string, int> con deberíamos estar informados sobre el posible alto costo al buscar (y algunas otras operaciones con una clave como parámetro) en el estilo de c.find ("hello world") . El hecho es que por defecto todas estas operaciones requieren una clave del tipo requerido, en nuestro caso es std :: string . Como resultado, al llamar a find, necesitamos construir implícitamente una clave de tipo std :: string a partir de const char * , lo que nos costará, en el mejor de los casos, una memoria extra (si nuestra implementación de biblioteca estándar tiene "optimización de cadena pequeña" y la clave es corta), y también extra strlen(a menos que el compilador adivine o no tenga forma de calcular la longitud de la línea en el momento de la compilación). En el peor de los casos, tendrá que pagar por completo: asignando y liberando memoria del montón para una clave temporal en un lugar aparentemente plano, y esto ya puede ser comparable al tiempo de búsqueda en sí.

Podemos evitar trabajos innecesarios con búsquedas heterogéneas. Se han agregado funciones para su correcto funcionamiento a los contenedores ordenados ( set , multiset , map , multimap ) en todos los lugares similares desde el estándar C ++ 14 y a los contenedores no 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());

Bueno, no olvides que esto no se trata solo de la función find. Sólo esta se refiere a las funciones: count, equal_range, lower_bound, upper_boundy contains.

¡Feliz búsqueda heterogénea, querido lector!