コードで使用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());
もう 1 つの方法は、"検索して見つからない場合は挿入する" ユース ケースを高速化することです。このトリックはlower_bound()
、注文されたコンテナーに対してのみ機能します。侵入型コンテナには と というメソッドがinsert_check()
ありますinsert_commit()
が、それは別のトピックだと思います。