0

L私は（一般的な意味ではなくstd::list）数のリストを持っており、これは。iの最小要素のインデックスでもありLます。インデックスで区切られた2つのパーティションを交換したいi。これを可能な限り効率的に（できれば一定時間で）実行できるようにするには、どのような標準データ構造とどの操作を実行する必要がありますか？

例：にしましょLう9 6 -4 6 12。最小値はL[2] = -4、なのでi = 2。2つのパーティションを交換した後、私はなりたいLです-4 6 12 9 6。

リストはかなり大きく（最大10 3要素）、複数回トラバースする必要があるため（最悪の場合、最大10 3トラバージョン）、キャッシュの問題があるため、使用することはstd::listお勧めできません。一方、std::vector2つのパーティションを交換することは困難になります。これにはstd::deque良い選択ですか？

4

1 に答える 1

1

問題には2つの側面があります。

1-定数時間スワップ：概念的に言えば、最良のアプローチは、スワッピングに関して二重にリンクされたリスト（ ）です。std::list

データが大きいため、ノードは常にメモリ内の最初の場所に残り、言及しているタイプのスワップを実行するために一定数のポインタのみを変更します。

2-局所性：メモリ内に連続して割り当てられたスペースがキャッシュパフォーマンスに優れていることは誰もが知っています。これはに傾いていstd::vectorます。

真ん中に何がありますか？ カスタムアロケータを介して割り当てることができる、サイズ変更可能な連続したメモリチャンク。これらを設計する方法はたくさんあります。例。_

于 2013-03-17T21:42:57.717 に答える