1

次のニーズを満たすC++のコンテナを探しています。

  • インデックスで要素を削除する必要があります。
  • 1つの要素を削除した直後に、別の要素を前面に挿入します（常に!!!!!）
  • それ以外にサイズの変更はありません。
  • インデックスを作成する必要があります。
  • コンテナに格納されている値は、インデックスとして一意です。
  • 1つの値に1つのインデックスを割り当てる必要があります。1つの値を削除または追加しない限り。次に、インデックスを調整する必要があります。

そのコンテナと少し並行して機能している別のデータセットについては、これらの機能とこれらの追加機能を備えたデータセットが必要です。

  • これは2つの方向で機能する必要があります。一意の値を格納するため、実際の値（100％一意）を介してインデックスに非常に高速にアクセスできる必要があります。これは頻繁に発生するためです。

値型のいずれかが、、、...のような演算子をサポートしていることを認めることはでき<ませ<=ん==。!=

質問がある場合は、質問してください。不明な点がある場合は、さらに説明します。

編集：

私が要求されたので、ここにその背後にある実際の問題があります：

一定量のオブジェクトを格納できるテンプレートコンテナクラスで作成されたライブラリを作成しています。これらのオブジェクトはすべて同じタイプです。（もちろん...）これらのオブジェクトのもう1つの非常に重要なプロパティは、一意のインデックスによって再作成できることです。このインデックスも何でもかまいません。この場合の例は、平面上にあるオブジェクトを作成できる2次元空間であり、オブジェクトクラスに座標を指定することで（この場合は単一のオブジェクトとして）、そこにあるすべてのプロパティを再作成できます。これで、コンテナが最大容量に達すると、最後に使用されたオブジェクトが削除されます。私の考えは、コンテナに一意のインデックスを付けるというものでした。目的のオブジェクトがまだ保存されている場合、関数はオブジェクト上のポインターを返し、それを内部コンテナー内で前面に移動します。

これが必要なのは、すべてのRAMとはるかに多くのRAMを簡単に使用できるプログラムがあるからです。毎回オブジェクトを生成して破棄することはできましたが、それは私には計算能力の無駄のように思えます。そこで、長期間使用されていない場合にのみオブジェクトを削除するこのコンテナを思いつきました。これは私の特定のケースでは非常に便利です（巨大な地図でのパスファインディング）

お役に立てば幸いです。

EDIT2：

Ok。これをさらに明確にします。

簡単なデータキャッシュから始めましょう。

[0] d1  [1] d2  [2] d3  [3] d4

ここで、d3を使用したとしましょう。構造は次のようになります。

[0] d3  [1] d1  [2] d2  [3] d4

ここで、完全に新しい要素をコンテナーに追加します（d5）。

[0] d5  [1] d3  [2] d1  [3] d2

それが背後にある考え方です。intインデックスとしての-valuesの代わりに、削除される可能性のあるすべてのオブジェクトを復元できるカスタムインデックスクラスを使用できるようになりました（これは問題ではありません。クラスが機能するための要件です）。

最初のステートメントから始めましょう。最初のケースでは、次のようになります。

[0] i1  [1] i2  [2] i3  [3] i4
[i1] 0  [i2] 1  [i3] 2  [i4] 3

2番目の例は次のようになります。

[0] i3  [1] i1  [2] i2  [3] i4
[i1] 1  [i2] 2  [i3] 0  [i4] 3

そして最後に、最後の状態は次のようになります。

[0] i5  [1] i3  [2] i1  [3] i2
[i1] 2  [i2] 3  [i3] 1  [i5] 0

それがより明確になることを願っています。2つ目は、複数のコンテナが可能である可能性があります。

4

5 に答える 5

3

申し訳ありませんが、あなたの質問は少し曖昧だと思います-しかし、あなたの要件がどうあるべきだと思うかを述べてから、データ構造のニーズについて話し合います...

したがって、次のようなインデックス付きデータがあります-次のようなものです（インデックスは括弧内にあります）：

[0] a  [1] h  [2] b  [3] q

あなたの主な操作は削除/挿入です - 要素 2 を削除し、値 x を挿入したとします。

[0] x  [1] a  [2] h  [3] q

したがって、削除される要素のインデックスをnと呼ぶ場合、実際に行ったことは [0..n-1] を 1 つの位置に沿って移動し、[0] を余分な値で上書きします。

討論

この操作をベクトルで行う場合、移動操作は任意に大きくなり、比較的遅くなる可能性があります。ただし、連想コンテナー (マップ、順序付けされていないマップ) などの他のコンテナーを使用する場合は、これらすべての「移動された」要素のキーをとにかく更新する必要があります。他の一般的なコンテナーは、O(log2N) またはより優れたインデックス作成を提供しないため、有望ではありません。そのため、ベクターに固執して、痛みを最小限に抑える方法を見てみましょう。移動が O(N) であるだけでなく、任意に大きなオブジェクトをシフトする必要があります。オブジェクトがポインターよりもはるかに大きい場合、オブジェクトへのポイントの配列を持ち、オブジェクトを移動せずに配列のポインターを移動するだけで済みます。 : はるかに高速になる可能性があります (移動を好まないオブジェクトにも役立ちます。

このベクトル アプローチよりもはるかに優れたものは考えられません。

質問の曖昧さに戻ります-「インデックス」と「キー」が紛らわしく、単にキー付きコンテナーが必要であるが、オブジェクトが削除/挿入操作ごとにキーをシフトする必要がない場合、マップまたは順序付けられていないマップは非常に重要ですより良い選択。

于 2013-01-29T05:43:47.540 に答える
2

あなたの要件を見てみましょう：

  • 位置別アクセス
  • 要素別アクセス
  • 任意の位置での削除
  • 要素の単一性

方法 ？

  • 「位置によるアクセス」をサポートするには、ランダムアクセスを備えたものが必要です。または、少なくともランダムアクセス O(log N) に近いもので十分かもしれません
  • 要素が順序付けをサポートしていない可能性があることを考えると、ユニシティにはハッシュセットの使用が必要になります

これは、Boost.MultiIndex を使用して簡単に実現できると思います。例のセクションでは既に MRU キャッシュの実装を示しており、十分に近づいています。組み合わせることをお勧めします：

これは次のような意味です。

typedef multi_index_container<
  T,
  indexed_by<
    random_access<>,
    hashed_unique</*...*/>
  > 
> cache_type;

注:ハッシュインデックス==が機能するには、 のサポート(または特殊化std::equal<T>)とハッシュ ファンクターの両方が必要です。後者は、型がまだサポートしていない場合、コンテナーの宣言の時点でユーザーが提供できます。

于 2013-01-29T08:32:17.650 に答える
1

Boost C++ ライブラリを使用している場合は、Multi-index コンテナーをご覧ください。

http://www.boost.org/doc/libs/1_52_0/libs/multi_index/doc/index.html

于 2013-01-29T07:24:12.280 に答える
0

multi_index_container ソリューションには、ランダム アクセスのサポートにベクトルを使用するのと同じ非効率性があることを指摘したいと思います。削除には、データ構造のサイズに比例したコストがかかります。内部的には、random_access インデックスはポインターのベクトルに似たデータ構造を使用します。

任意の要素のランダム アクセスと削除の両方をリニアよりも優れた時間で実行できるデータ構造はそれほど多くありません。AFAIK std::deque は、アイテムがシーケンスの終わりの1つに近い場合を除き、線形時間削除を行います。

これにより、バランスの取れたバイナリ ツリー (およびスキップ リストなどのバリアント) が得られます。自己均衡二分木は、任意のノードの下のサブツリーのサイズを一定のオーバーヘッドで維持でき、この「拡張」により、O(log n) でランダム アクセスを実装できます。残念ながら、 std::map のデフォルトの実装には通常、この機能がありません。したがって、std::map と std::advance を使用すると、線形時間のランダム アクセスが可能になります。ユーザーコードは std::map によって内部的に行われるツリー操作を認識しないため、std::map の「上に」効率的なランダムアクセスを実装することはできません。

独自のロールを作成できます (AVL ツリーは比較的簡単に実装できます)。ランダム アクセス ルックアップまたは削除 + 挿入操作のパフォーマンスの低下を許容しない限り、これ以上簡単な方法は考えられません。ツリーを含まない「最も悪い」ソリューションは、おそらく std::deque を使用しています

編集: 私が言及した拡張ツリー データ構造は、http://en.wikipedia.org/wiki/Order_statistic_treeとして知られています。

于 2013-06-30T16:42:06.783 に答える
0

Ok。皆さんありがとうございますが、私はこれに対して非常に効果的な解決策を見つけました：

私の問題には次のデータ構造が必要です。

[0] d1  [1] d2  [2] d3  [3] d4
[0] i1  [1] i2  [2] i3  [3] i4
[i1] 0  [i2] 1  [i3] 2  [i4] 3

これらのコンテナを使用することにしました：

  1. list
  2. list
  3. map

std::advanceいくつかの調査を通じて、とについて知りましたstd::next。これにより、 の特定の要素に効果的にアクセスできますlist。マップを更新するには、単純な for ループを実行するだけです。これは非常に効率的に機能するはずです。

より良いアイデアがある場合は、ここに投稿してください。

ありがとうございました！

于 2013-01-29T06:47:34.237 に答える