5

次のコードがあるとします。

struct Item
{
    std::string name;
    int someInt;
    string someString;
    Item(const std::string& aName):name(aName){}
};
std::unordered_map<std::string, Item*> items;
Item* item = new Item("testitem");
items.insert(make_pair(item.name, item);

アイテム名は 2 回メモリに格納されます。1 回は Item 構造体の一部として、もう 1 回はマップ エントリのキーとして格納されます。重複を避けることはできますか？1 億レコード程度では、このオーバーヘッドは非常に大きくなります。

注: Item の別のコンテナーへのインデックスとしてハッシュマップを使用し、マップのキー値にアクセスできないため、Item 構造内に名前を付ける必要があります。

4

5 に答える 5

3

OK、あなたはポインターを値として使用していると言っているので、ここで私の答えを生き返らせます。

少しハックですが、動作するはずです。基本的に、ポインタとカスタム ハッシュ関数を使用します

struct Item
{
    std::string name;
    int someInt;
    string someString;
    Item(const std::string& aName):name(aName){}

    struct name_hash  
    { 
       size_t operator() (std::string* name)
       {
           std::hash<std::string> h;
           return h(*name);
       }
    };
};
std::unordered_map<std::string*, Item*, Item::name_hash> items;
Item* item = new Item ("testitem");
items.insert(make_pair(&(item->name), item);
于 2012-11-29T09:35:45.377 に答える
2

最初にアイテムを格納するために使用する構造が単純なリストであると仮定すると、それをマルチインデックス コンテナーに置き換えることができます。

それらの線に沿ったもの（テストされていない）が要件を満たすはずです：

typedef multi_index_container<
    Item,
    indexed_by<
        sequenced<>,
        hashed_unique<member<Item, std::string, &Item::name
    >
> itemContainer;

itemContainer items;

これで、アイテムに挿入順にアクセスするか、名前で検索できるようになりました。

itemContainer::nth_index<0>::type & sequentialItems = items.get<O>();
// use sequentialItems as a regular std::list

itemContainer::nth_index<1>::type & associativeItems = items.get<1>();
// uses associativeItems as a regular std::unordered_set

必要に応じて、他のインデックスも使用できます。

于 2012-11-29T10:17:08.943 に答える
1

いいえ、ありません。あなたはできる：

  • 保管nameしItemて別々に回さないでください。
  • 名前といずれかを除いて 同じフィールドを持つを作成ItemしますItemDataItem
    • （=タイプItemの）またはstd::pair<std::string, ItemData>value_type
    • そのタイプとの間で変換可能にします。
  • キーの文字列への参照を使用します。キーとして使用し、キーと検索のためにキーstd::reference_wrapper<const std::string>を渡すことができるはずです。専門にする必要があるかもしれませんが、それは簡単なはずです。std::cref(value.name)std::cref(std::string(whatever))std::hash<std::reference_wrapper<const std::string>>
  • を使用std::unordered_setしますが、ルックアップによってルックアップ用のダミーが作成されるという欠点がありItemます。
    • 実際にItem *値型を使用している場合は、名前を基本クラスに移動し、ポリモーフィズムを使用してその欠点を回避できます。
  • たとえば、 Boost.Intrusiveを使用してカスタムハッシュマップを作成します。
于 2012-11-29T09:34:11.287 に答える
1

構造体にフィールドを格納しないstd::string nameでください。とにかく、ルックアップを実行すると、すでに名前フィールドがわかっています。

于 2012-11-29T09:26:33.983 に答える
1

TL;DR libstdc++ (gcc に付属) を使用している場合は、既に問題ありません。

3 つの方法があり、2 つは「シンプル」です。

  • オブジェクトを2つのキー/値に分割し、値のキーの複製を停止します
  • unordered_set代わりにオブジェクトを保存します

3 番目のものは、コンパイラによって提供されない限り、より複雑です。

  • 参照カウントの実装を使用するstd::string(libstdc++ など)

この場合、 astd::stringを別のものにコピーすると、内部バッファーの参照カウンターがインクリメントされます...それだけです。コピーは、所有者の 1 人によって変更が要求されるまで延期されます: Copy On Write。

于 2012-11-29T09:36:14.513 に答える