Pencarian heterogen dalam wadah asosiatif di C ++

Container asosiatif C ++ bekerja dengan jenis kunci tertentu. Untuk mencarinya dengan kunci jenis ini ( std :: string , std :: string_view , const char * ), kita dapat mengalami kerugian kinerja yang signifikan. Dalam artikel ini, saya akan menunjukkan kepada Anda bagaimana menghindari hal ini dengan fitur pencarian heterogen yang baru saja ditambahkan.

Memiliki container std :: map <std :: string, int> dengan kita harus diberi tahu tentang kemungkinan biaya tinggi saat mencari (dan beberapa operasi lain dengan kunci sebagai parameter) di atasnya dengan gaya c.find ("hello world") . Faktanya adalah bahwa secara default semua operasi ini memerlukan kunci dari tipe yang diperlukan, dalam kasus kita ini adalah std :: string . Akibatnya, saat memanggil find, kita perlu secara implisit membangun kunci tipe std :: string dari const char * , yang akan dikenakan biaya paling banyak satu memcpy tambahan (jika implementasi perpustakaan standar kita memiliki "pengoptimalan string kecil" dan kuncinya pendek), dan juga strlen ekstra(kecuali kompiler menebak atau tidak memiliki cara untuk menghitung panjang baris pada waktu kompilasi). Dalam kasus terburuk, Anda harus membayar penuh: dengan mengalokasikan dan membebaskan memori dari heap untuk kunci sementara di tempat yang tampaknya datar, dan ini mungkin sudah sebanding dengan waktu pencarian itu sendiri.

Kita dapat menghindari pekerjaan yang tidak perlu dengan pencarian yang heterogen. Fungsi untuk operasi yang benar telah ditambahkan ke container terurut ( set , multiset , map , multimap ) di semua tempat serupa sejak standar C ++ 14 dan ke container tak berurutan ( unordered_set , unordered_multiset , unordered_map , unordered_multimap ) sejak 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());

Nah, jangan lupa bahwa ini bukan hanya tentang fungsinya find. Hanya ini kekhawatiran fungsi: count, equal_range, lower_bound, upper_bounddan contains.

Selamat mencari heterogen, pembaca yang budiman!