9

stl セット内の要素のランクを見つけたい。最初からその要素までトラバースしてそのランクを見つけることはできますが、それには O(n) が必要です。O(logn)でランクを見つける方法はありますか。

4

5 に答える 5

2

flat_set@Potatoswatter によって提案された並べ替えられたベクターの機能は、Boost.Containerによって提供されます。ドキュメントには、次のトレードオフがリストされています

  • 標準の連想コンテナよりも高速なルックアップ
  • 標準の連想コンテナーよりもはるかに高速な反復
  • 小さなオブジェクト (および、shrink_to_fit が使用されている場合は大きなオブジェクト) のメモリ消費量が少ない
  • キャッシュ パフォーマンスの向上 (データは連続したメモリに格納されます)
  • 非安定反復子 (要素を挿入および消去すると、反復子は無効になります)
  • コピー不可および移動不可の値型は保存できません
  • 標準の連想コンテナーよりも弱い例外安全性 (消去および挿入で値をシフトするときに、コピー/移動コンストラクターがスローされる可能性があります)
  • 標準の連想コンテナーよりも挿入と消去が遅い (特に非可動型の場合)
于 2013-08-07T06:39:58.687 に答える