10

Java には、予測可能な反復順序を持つセットであるLinkedHashSetがあります。C++ で利用可能な最も近いデータ構造は何ですか?

現在、セットとベクターの両方を使用してデータを複製しています。データをセットに挿入します。データが正常に挿入された場合 (つまり、データがまだセットに存在していなかった場合)、ベクターに push_back します。データを反復処理するときは、ベクトルを使用します。

4

4 に答える 4

10

使用できる場合、とインデックスを持つBoost.MultiIndexは と同じデータ構造です。sequencedhashed_uniqueLinkedHashSet

それに失敗した場合は、リストノードを含む何らかのタイプの an unordered_set(またはhash_set、それが実装で提供されている場合は ) を保持し、そのリストノードを使用して自分で順番を処理します。

現在行っていること (setおよびvector) の問題は次のとおりです。

  • データの 2 つのコピー (データ型が大きい場合は問題になる可能性があります。これは、2 つの異なる反復が、同じ値であっても、異なるオブジェクトへの参照を返すことを意味します。アドレスが等しいことを期待して、2 つの異なる方法で取得された「同じ」要素のアドレス、またはmutable順序比較によって無視されるデータ メンバーがオブジェクトにあり、誰かがルックアップを介して変化し、変更を確認することを期待するコードを記述した場合順番に繰り返す）。
  • とは異なりLinkedHashSet、シーケンスの途中で要素をすばやく削除する方法はありません。また、位置ではなく値で削除する場合は、削除する値のベクトルを検索する必要があります。
  • setハッシュ セットとは異なるパフォーマンス特性を持っています。

あなたがそれらのことを気にしないなら、あなたが持っているものはおそらく大丈夫です. 重複が唯一の問題である場合は、重複のベクトルではなく、セット内の要素へのポインターのベクトルを保持することを検討できます。

于 2013-04-03T23:20:06.823 に答える
1

C++ で Java から複製するLinkedHashSetには、これが機能するために 2 つのバニラが必要になると思います(挿入と削除のために O(log n) を取得する代わりに本物ではなくstd::map取得することに注意してください)。LinkedTreeSetLinkedHashSet

  • 実際の値をキーとして使用し、挿入順序 (通常は int または long int) を値として使用します。
  • 別のものは逆で、挿入順序をキーとして使用し、実際の値を値として使用します。

挿入するときはstd::map::find、最初std::mapに in を使用して、同じオブジェクトが存在しないことを確認します。

  • 既に存在する場合は、新しいものを無視します。
  • そうでない場合は、std::map前述の両方に増分挿入順序でこのオブジェクトをマップします。

これを挿入順に反復する場合は、挿入順に並べ替えられるため、2 番目を反復します( orstd::mapに該当するものはすべて自動的に並べ替えられます)。std::mapstd::set

要素を削除する場合は、 を使用std::map::findして挿入の順序を取得します。この挿入順序を使用して、2 番目のものから要素を削除std::mapし、最初のものからオブジェクトを削除します。

このソリューションは完璧ではないことに注意してください。これを長期的に使用する予定がある場合は、最終的に広告掲載オーダー (2 unsigned int の場合は ^32 インデックス、unsigned long long int の場合は 2^64 インデックス)。これを行うには、すべての「値」オブジェクトをベクトルに配置し、両方のマップからすべての値をクリアしてから、ベクトルから両方のマップに値を再挿入する必要があります。この手順には O(nlogn) 時間がかかります。

C++11 を使用している場合、効率を向上させるために最初のものstd::mapをstd::unordered_mapに置き換えることができますが、2 番目のものを置き換えることはできません。その理由はstd::unordered map、この状況ではインデックスを確実にソートできないように、インデックス作成にハッシュ コードを使用するためです。

于 2014-08-15T15:10:25.117 に答える
0

「null」ルックアップ時間のように、std::map が (log n) のようなものを与えないことを知りたいかもしれません。また、 std::tr1::unordered を使用すると、一定のルックアップ時間を得るために順序付けが破棄されるため、危険なビジネスになります。

ブースト マルチ インデックス コンテナーをバッシュして、より自由に操作できるようにしてください。

于 2013-04-03T23:14:37.487 に答える
0

と の組み合わせを説明した方法は、(Java の HashSet と同等) と(二重にリンクされたリスト)を使用することを除いて、やるべきことのようstd::setに聞こえます。また、(キーがオブジェクト (またはオブジェクトの一部のみ) と異なる場合) を格納する実際のオブジェクトを見つけるリストにイテレータと共にキー (検索用) を格納するために使用することもできます。std::vectorstd::unordered_setstd::liststd::unordered_map

ブースト ライブラリは、コンテナーとルックアップ インデックスのこれらの種類の組み合わせを多数提供します。たとえば、この高速ルックアップの双方向リストの例をご覧ください。

于 2013-04-03T23:21:29.383 に答える