1

私の目標は、ストリングインターニングを行うことです。このために、次のことができるハッシュ化されたコンテナー クラスを探しています。

  • ノードごとに 1 つのメモリ ブロックのみを割り当てる
  • ノードごとに異なるユーザーデータ サイズ

値の型は次のようになります。

struct String
{
    size_t refcnt;
    size_t len;
    char data[];
};

すべての String オブジェクトのサイズは異なります。これは、演算子 new + 配置 new で実現されます。したがって、基本的にはノードを自分で割り当てて、後でコンテナーにプッシュしたいと考えています。

以下の容器は適していません:

  • std::unordored_set

  • ブースト::マルチインデックス::*

    異なるサイズのノードを割り当てることはできません

  • boost::intrusive::unordered_set

    最初はうまくいくようです。しかし、いくつかの欠点があります。まず、バケット配列を割り当て、負荷係数を自分で維持する必要があります。これは単に不必要であり、エラーが発生しやすいものです。

    しかし、もう 1 つの問題は解決が困難です。文字列型のオブジェクトしか検索できません。しかし、エントリを探すたびに文字列を割り当てるのは非効率的で、入力として std::string しかありません。

このタスクに使用できるハッシュ化されたコンテナーは他にありますか?

4

2 に答える 2

0

標準のコンテナではそれができないと思います。

あなたができることは、ポインタを保存し、Stringカスタムハッシュとcmpファンクターを提供することです

struct StringHash
{
   size_t operator() (String* str)
  {
    // calc hash
  } 
};

struct StringCmp
{
   bool operator() (String* str1, String* str2)
  {
    // compare
  } 
};

std::unordered_set<String*, StringHash, StringCmp> my_set;
于 2012-12-04T10:52:01.513 に答える
0

の定義Stringは C++ ではコンパイルされません。明らかな解決策は、フィールドをポインターに置き換えることdataです (この場合、構造体自体を に入れることができます std::unordered_set)。

次のようなものを使用して、C++ で終わりのない構造体を作成することができます。

struct String
{
    int refcnt;
    int len;
    char* data()
    {
        return reinterpret_cast<char*>(this + 1);
    }
};

ただし、そうすると、薄い氷の上でスケートをしていることになります。以外の型の場合、適切に整列されないcharリスクがあります。this +

これを行う場合std::unordered_set、要素ではなくポインターを含める必要があるため、その努力に対して何かが得られるとは思えません。

于 2012-12-04T11:36:37.253 に答える