假设我在我的代码中使用
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()
的方法,但这是一个单独的话题。
std::string
,使得小字符串永远不使用任何动态内存分配... - Kerrek SBstd::string
太昂贵,可以将自己的对象包装在令牌周围,避免堆分配。侵入式和非侵入式容器是一个正交问题。 - n. m.