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());

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

4

2 に答える 2

1

レキシングに関して言えば、私は個人的に 2 つの簡単なトリックを使用します。

  1. 私はStringRef（LLVMのものと同様に） achar const*と aをラップするだけでsize_t、文字列のような操作を提供します（明らかにconst操作のみ）を使用します
  2. バンプアロケーターを使用して、遭遇した文字列をプールします（たとえば4Kの塊を使用）

2 つを組み合わせると非常に効率的ですがStringRef、プールが破棄されるとすぐにプールへのすべてのポイントが明らかに無効になることを理解する必要があります。

于 2013-02-23T14:51:14.700 に答える
1

( 1.42boost::unordered_mapの時点で) には, ,型findを取るオーバーロードがあることが判明したため、ここで要求したことを正確に実行できます。CompatibleKeyCompatibleHashCompatiblePredicate

于 2013-03-11T11:02:00.907 に答える