🏳️‍🌈 👨🏾‍🤝‍👨🏽 🦂 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类型的键，这最多会使我们多花一分钱（如果我们的标准库实现具有“小字符串优化”且键很短），并且还额外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。

祝您搜索愉快，亲爱的读者！

C ++中关联容器中的异构搜索

More articles: