Heterogene Suche in assoziativen Containern in C ++

Assoziative C ++ - Container arbeiten mit einem bestimmten Schlüsseltyp. Um sie nach einem Schlüssel dieses Typs ( std :: string , std :: string_view , const char * ) zu durchsuchen , können erhebliche Leistungsverluste auftreten. In diesem Artikel werde ich Ihnen zeigen, wie Sie dies mit einer relativ kürzlich hinzugefügten heterogenen Suchfunktion vermeiden können.

Wenn wir einen Container std :: map <std :: string, int> haben, sollten wir über die möglichen hohen Kosten informiert werden, wenn wir ihn (und einige andere Operationen mit einem Schlüssel als Parameter) im Stil von c.find ("Hallo Welt") suchen . Tatsache ist, dass für alle diese Operationen standardmäßig ein Schlüssel des erforderlichen Typs erforderlich ist, in unserem Fall std :: string . Wenn wir find aufrufen , müssen wir daher implizit einen Schlüssel vom Typ std :: string aus const char * erstellen , was uns bestenfalls einen zusätzlichen Speicherplatz kostet (wenn unsere Standardbibliotheksimplementierung eine "Optimierung kleiner Zeichenfolgen" aufweist und der Schlüssel kurz ist) auch extra strlen(es sei denn, der Compiler errät oder hat keine Möglichkeit, die Zeilenlänge zur Kompilierungszeit zu berechnen). Im schlimmsten Fall müssen Sie den vollen Betrag bezahlen: indem Sie Speicher für einen temporären Schlüssel an einem scheinbar flachen Ort vom Heap zuweisen und freigeben. Dies ist möglicherweise bereits mit der Suchzeit selbst vergleichbar.

Wir können unnötige Arbeit mit heterogener Suche vermeiden. Seit dem C ++ 14-Standard wurden geordneten Containern ( Set , Multiset , Map , Multimap ) an allen ähnlichen Stellen Funktionen für den korrekten Betrieb und seit C ++ 20 ungeordneten Containern ( unordered_set , unordered_multiset , unordered_map , unordered_multimap ) hinzugefügt .

//  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());

Vergessen Sie nicht, dass es nicht nur um die Funktion geht find. Genau dies betrifft Funktionen: count, equal_range, lower_bound, upper_boundund contains.

Viel Spaß beim heterogenen Suchen, lieber Leser!