0

コンテナのタイプを見つけるのに苦労しています。使用している名前が間違っている可能性があります。

std::map のような C++ コンテナーを知っている人はいますか?ただし、キーは整数型です。インデックスによる挿入、削除、検索の複雑さは O(1) です。その反復子は、インデックス (キー) によってマップされる要素を反復処理する必要があります。また、順序付けられた方法でインデックスを反復処理する必要があります。ランダム アクセスで、任意の位置に移動するには O(1) の複雑さが必要です。

イテレータが双方向で、そのインクリメント/デクリメントが O(1) の複雑さである場合を検討したいと思います。

4

1 に答える 1

2

あなたは不可能を求めている

O(1)削除、挿入、検索、反復を順に実行すると、O(n)すべての要素をプッシュしてから順番に反復することでソートが可能になります。

整数ソートで知られている最適なアルゴリズムは ですO(n * sqrt(loglogn))。したがって、あなたが説明したようなものがあれば、それは最もよく知られている整数ソート アルゴリズムよりも優れています。

編集（質問に対するあなたのコメントによると）：

反復順序を保証せずにO(1)検索/検索/挿入を実行できる場合は、ハッシュ テーブルを実装するunordered_mapを使用できます。

于 2012-10-25T09:27:33.037 に答える