c++ - std::map 最小 n 要素を取得する時間

Question

std::mapドキュメントで読んだように、バイナリ検索ツリーで実装する必要があり、それらもソートします。

要素をすばやく挿入してすばやく取得する必要があります。また、最初の最小 N 要素を時々取得する必要もあります。

を使おうと思っていたstd::mapのですが、いい選択でしょうか？もしそうなら、最小の N 個の要素を取得するのに必要な時間は? O(n*logn)?

Answer 1

検索と n 最小の両方が必要な場合、std::map妥当な選択だと思います。ただし、正確なアクセス パターンによっては、std::vector並べ替えも適切な選択になる場合があります。

リトリーブとはどういう意味かわかりません。k 個の要素を読み取る時間は O( k ) (反復子を使用して順次実行する場合)、それらを削除する時間は O( k log n ) です ( nは要素の合計量です。反復子を使用して順次実行する場合でも)。

Answer 2

イテレータを使用して、最下位の N 要素をすばやく読み取ることができます。N begin()-1 番目の要素に移動するには、O(n) 時間かかります (次の要素を取得するには、a の定数時間が償却されますstd::map)。

std::vectorただし、正確な要件に応じて、実行しているように聞こえるものを実装するために、ソートされたバイナリチョップ検索メソッドを使用する方が実際には高速であることが多いことに注意してください。これは調査する価値があります。

Answer 3

C++ 標準では、必要なすべての反復子操作 (反復子のインクリメントを含む) を一定時間償却する必要があります。したがって、コンテナー内の最初の N 個のアイテムを取得するには、償却されO(N)た時間がかかる必要があります。

Answer 4

どちらの質問にも「はい」と答えます。