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

Question

假设我在我的代码中使用std::unordered_map<std::string, Foo>，它既方便又好用，但不幸的是，每次执行在这个映射中进行查找(find())操作时，都必须创建一个std::string实例。例如，假设我正在对另一个字符串进行标记化，并想在每个标记上调用find()。这就迫使我在查找之前构造出一个std::string，这需要一个分配器(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()的方法，但这是一个单独的话题。

- yonil

---

使用更好的库实现？可以实现std::string，使得小字符串永远不使用任何动态内存分配... - Kerrek SB

如果 std::string 太昂贵，可以将自己的对象包装在令牌周围，避免堆分配。侵入式和非侵入式容器是一个正交问题。 - n. m.

@BoPersson：不过，libstdc++仍然没有... - Matthieu M.

Answer 1

事实证明，boost::unordered_map （截至1.42版本）有一个重载的 find 方法，它接受 CompatibleKey、CompatibleHash 和 CompatiblePredicate 类型，因此它可以完全满足我在这里提出的要求。

- yonil

Answer 2

说到词法分析，我个人使用两个简单的技巧：

1. 我使用类似LLVM的StringRef，它只是封装了char const*和size_t，并提供了类似于字符串的操作（显然只有const操作）。
2. 我使用一个bump分配器（使用4K大小的块）来池化遇到的字符串。

两者结合起来非常高效，但需要注意的是，所有指向池中的StringRef在池被销毁后显然都将失效。

- Matthieu M.

---

从Boost 1.53开始，您可以使用#include <boost/utility/string_ref.hpp>。 - Marshall Clow

非常好，谢谢。我无法升级到Boost 1.53以完成我的当前工作。不管怎样，我正在利用unordered_map<immutable_substring, Foo>。本质上，这是唯一一个实际选项，不涉及对容器接口进行调整。我的immutable_string实际上与StringRef相同。 - yonil