3

假设我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()and的方法insert_commit()，但我猜这是一个单独的主题。

4

2 回答 2

1

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

  1. 我使用StringRef（类似于 LLVM），它只包装 achar const*和 asize_t并提供类似字符串的操作（显然只有 const 操作）
  2. 我使用凹凸分配器汇集遇到的字符串（使用 4K 块）

两者结合起来非常有效，但需要了解StringRef的是，一旦池被破坏，所有进入池的点显然都会失效。

于 2013-02-23T14:51:14.700 回答
1

结果boost::unordered_map（从 1.42 开始）有一个find重载，它需要CompatibleKey, CompatibleHash,CompatiblePredicate类型，所以它可以完全按照我在这里的要求。

于 2013-03-11T11:02:00.907 回答