Clever Geek Handbook

C ++の連想コンテナでの異種検索

C ++連想コンテナは、特定のキータイプで機能します。このタイプのキー（std :: string、std :: string_view、const char *）でそれらを検索すると、パフォーマンスが大幅に低下する可能性があります。この記事では、比較的最近追加された異種検索機能を使用してこれを回避する方法を紹介します。



コンテナstd :: map <std :: string、int>を使用すると、c.find（ "hello world"）のスタイルで検索（およびキーをパラメータとして使用するその他の操作）時に発生する可能性のある高コストについて通知する必要があります。実際のところ、デフォルトでは、これらすべての操作には必要なタイプのキーが必要です。この場合はstd :: stringです。その結果、findを呼び出すときに、const char *からstd :: string型のキーを暗黙的に作成する必要があります。これにより、最大で1つの追加のmemcpyが必要になります（標準のライブラリ実装に「小さな文字列の最適化」があり、キーが短い場合）。また余分なstrlen（コンパイラがコンパイル時に行の長さを推測するか、計算する方法がない場合を除く）。最悪の場合、全額を支払う必要があります。一見平らな場所で一時キーのメモリをヒープから割り当てて解放することで、これはすでに検索時間自体に匹敵する可能性があります。



異種検索による不要な作業を回避できます。正しい操作のための関数は、C ++ 14標準以降、すべての同様の場所の順序付きコンテナー（set、multiset、map、multimap）と、C ++ 20以降の順序なしコンテナー（unordered_set、unordered_multiset、unordered_map、unordered_multimap）に追加されました。



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


さて、これは機能だけではないことを忘れないでくださいfind。ただ、この懸念機能：count、equal_range、lower_bound、upper_boundとcontains。



幸せな異種検索、親愛なる読者！



More articles:


All Articles