バトルフィールド3のstd :: vectorスワップを実装して要素を「削除/追加する」

Question

アルゴリズムを実装しようとしていて、here（スライド19）のようにDICEの「スワップトリック」を見つけました。

私が理解しているところでは、最初にすべての要素を含むベクトルを作成し、要素を削除する必要があるときは最後の要素と置き換えてベクトルの「サイズ」を小さくします。この「サイズ」は、（ベクトルdoesn't support this internallyのため）「仮想」サイズを追跡するための外部変数です。

注：発注/並べ替えは重要ではありません。また、「削除」と言うと、割り当てられていないものはありません。要素が「使用可能な」範囲外に移動したということだけです。

ここで、削除された要素の要素をベクトルの使用可能な部分に追加する瞬間が来たら、それをどこかに戻す必要があります。そして、これは私が少しブロックしているところです。なぜなら、私たちがそれを交換するとき、私たちはこの繰り返しでそこに存在する必要がある要素と交換することができるからです。同じ要素を入れ替えなければならないからです...

これは、仕事：

繰り返し1：| 1 2 3 4 | （サイズ4）

繰り返し2：| 1 3 | 2 4（要素 '2'と '4'はまだメモリ内にあり、ベクトルの大きさは考慮していないサイズ2）

繰り返し3：| 2 1 3 | 4（大きさ3で要素 '4'が残っています）

私はそれを考えすぎるかもしれませんが、このアルゴリズムを正しく取得する方法があれば役に立ちます。

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

Answer 1

最初に使用できない要素と交換してから、仮想サイズを増やしてください。したがって、たとえば、のは、これはあなたのベクトルであるとしましょう：

// usable   unusable 
{ 0, 1, 2, 3,  4, 5, 6, 7, 8 } // virtual size = 4 

今度は、あなたが使用可能な部分に使用できない部分から7を移動したいとしましょう。これは最初に使用できない要素なので、4と交換します。

// usable   // unusable 
{ 0, 1, 2, 3, 7, 5, 6, 4, 8 } // virtual size = 5