16

一連のキー値オブジェクトを保存したいのですが、値オブジェクト自体 (およびそれへの参照) がそのキーを知っている場所です。また、キーのみを指定してこれらのオブジェクトを効率的に検索したいと考えています。

class SomeObject
{
private:
    //String or integer. int seem cheap enough to duplicate with std::map, but
    //strings seem pretty expensive when there may be thousands of objects in existence.
    //Reference/Pointer to key is fine
    const SomeOtherObject key;
    ...other stuff...
public:
    ...methods, some of which use the key in some way...
};
  • std::マップ
    • 値がキーにアクセスできないように、ストレージが std::pair である必要があるようです。値にキーが含まれている場合は、複製する必要があります。
    • 値内のキーが何らかの方法で変更されないように実際に強制するわけではありません
  • std::set
    • キーフィールドだけでなく、値全体が const になることに気付くまで、カスタム比較メソッドを使用してキーごとに一意性を提供する、非常に優れたソリューションのように見えます。
  • std::vector (または他の配列/リストのようなソリューション)
    • 線形検索を使用できます。または、アイテムがソートされている場合はバイナリ検索を使用できます。ただし、これはパフォーマンスの点で最適ではないと思われます。目的の動作を実際に実装するには、何らかの追加レイヤーが必要です。
4

4 に答える 4

2

あなたの痛みが分かります。私が怒っているのは、setとmapが常に内部で同じデータ構造を使用して実装されていることです。これはtree、キー エクストラクタでパラメータ化された値です。残念ながら、標準にはそのようなものはありません。

ブーストが問題ない場合は、Boost.MultiIndexを使用して必要なものを達成してください。Boost.Intrusiveも見てみましょう。

于 2012-12-11T20:48:47.850 に答える
2

C++ はmutable、2 番目のソリューションを使用できるようにするキーワードを提供します -- a set. アイテム クラスのように値を宣言するmutableと、アイテムが であっても値を変更できますconst。参照: 'mutable' キーワードには、const 関数による変数の変更を許可する以外の目的がありますか?

または、さらに単純にconst_cast、アイテムの定数性を遠ざける値のアクセサーを実装します。

于 2012-12-11T21:07:51.753 に答える
1

...しかし、値オブジェクト自体（およびそれへの参照）がそのキーを知っている場合

地図：

同じオブジェクトへのポインタが異なるキーを使用して複数のマップに追加される可能性があるため、オブジェクトはそのキーを認識できません。キーはマップに属しています。オブジェクトではありません。

セットする：

このメンバーの値が変わるとどうなりますか？どのようにインデックスの再作成を強制しますか？これが、setがconstnessを強制する理由です。

-

メンバーの1つに基づいて特定のクラスのアイテムにインデックスを付けようとしていますが、インデックス作成の目的でこのメンバーをコピーしたくないし、オブジェクトをconstにしたくない（私はあなたがしたいと思いますメンバーをconstにします）。

赤黒またはAVLツリーの上に構築したでしょう。

ybungalobillによって提案されたBoost.MultiIndexに精通していません。インスタンス化されたコードがインデックス付きメンバーをコピーするかどうか、またはこのメンバーの値の変更をどのように処理するかはわかりません。

于 2012-12-11T21:26:29.143 に答える