1

箱から出してそのような保証を与える標準的なコンテナはありません。いくつかの追加の操作が必要です（たとえば、Jerry Coffinが提案したように）、それは重複していません。

ランダムアクセスで少なくともO（ln N）、削除でO（ln N）の準備ができているデータ構造/コンテナはありますか？（stl / boost / etc）

コンテナ内の要素の順序は重要ではありません。

このような操作は、次のように連続して発生する可能性があります。

  1. インデックスによるランダムアクセス（インデックスもランダムです、rand（）％size（））

  2. このアイテムを削除する

  3. インデックスによるランダムアクセス（インデックスもランダムです、rand（）％size（））

  4. このアイテムを削除する

等...

4

1 に答える 1

4

順序は重要ではないと言うので、ベクトルを使用して一定時間で両方を行うことができます。

ランダムアクセスは（明らかに）一定時間です。

一定時間の削除は、削除する要素を最後の要素と交換してから、最後の要素を削除することで実行できます。

于 2013-02-10T06:23:03.890 に答える