c++ - 如何减少 C++ map/unordered_map 容器中查找的分配？

Question

假设我正在使用 std::unordered_map<std::string, Foo>在我的代码中。它既好又方便，但不幸的是，每次我想在此 map 中进行查找(find())时，我都必须想出一个 std::string 的实例。 .

例如，假设我正在标记其他一些字符串并想调用 find()在每个 token 上。这迫使我构建一个 std::string在查找之前围绕每个 token ，这需要一个分配器( std::allocator ，相当于一个 CRT malloc() )。这很容易比实际查找本身慢。它还与其他线程竞争，因为堆管理需要某种形式的同步。

几年前，我找到了Boost.intrusive 库；当时它只是一个测试版。有趣的是它有一个名为 boost::intrusive::iunordered_set 的容器这允许代码使用任何用户提供的类型执行查找。

我将解释我希望它如何工作:

struct immutable_string
{
    const char *pf, *pl;
    struct equals
    {
        bool operator()(const string& left, immutable_string& right) const
        {
            if (left.length() != right.pl - right.pf)
                return false;

            return std::equals(right.pf, right.pl, left.begin());
        }
    };

    struct hasher
    {
        size_t operator()(const immutable_string& s) const
        {
            return boost::hash_range(s.pf, s.pl);
        }
    };

};

struct string_hasher
{
    size_t operator()(const std::string& s) const
    {
        return boost::hash_range(s.begin(), s.end());
    }
};

std::unordered_map<std::string, Foo, string_hasher> m;
m["abc"] = Foo(123); 

immutable_string token; // token refers to a substring inside some other string

auto it = m.find(token, immutable_string::equals(), immutable_string::hasher());

另一件事是加快“查找并在未找到时插入”用例——lower_bound() 的技巧仅适用于订购的容器。侵入式容器具有称为 insert_check() 的方法和 insert_commit() ，但我想那是一个单独的主题。

Answer 1

原来 boost::unordered_map(从 1.42 开始)有一个 find 重载，它采用 CompatibleKey、CompatibleHash, CompatiblePredicate 类型，因此它可以完全按照我在这里的要求执行。