👺 🎌 🔢 Heterogeneous search in associative containers in C ++ 🔌 💝 💌

C ++ associative containers work with a specific key type. To search them by a key of this type ( std :: string , std :: string_view , const char * ), we can incur significant performance losses. In this article, I'll show you how to avoid this with a relatively recently added heterogeneous search feature.

Having a container std :: map <std :: string, int> with we should be informed about the possible high cost when searching (and some other operations with a key as a parameter) on it in the style of c.find ("hello world") . The fact is that by default all these operations require a key of the required type, in our case it is std :: string . As a result, when calling find, we need to implicitly construct a key of type std :: string from const char * , which will cost us at best one extra memcpy (if our standard library implementation has "small string optimization" and the key is short), and also extra strlen(unless the compiler guesses or has no way of calculating the line length at compile time). In the worst case, you will have to pay in full: by allocating and freeing memory from the heap for a temporary key at a seemingly flat place, and this may already be comparable to the search time itself.

We can avoid unnecessary work with heterogeneous search. Functions for its correct operation have been added to ordered containers ( set , multiset , map , multimap ) in all similar places since the C ++ 14 standard and to unordered containers ( unordered_set , unordered_multiset , unordered_map , unordered_multimap ) since 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());

Well, do not forget that this is not only about the function find. Just this concerns functions: count, equal_range, lower_bound, upper_boundand contains.

Happy heterogeneous search, dear reader!

Heterogeneous search in associative containers in C ++

More articles: