stl セット内の要素のランクを見つけたい。最初からその要素までトラバースしてそのランクを見つけることはできますが、それには O(n) が必要です。O(logn)でランクを見つける方法はありますか。
4601 次
5 に答える
2
flat_set
@Potatoswatter によって提案された並べ替えられたベクターの機能は、Boost.Containerによって提供されます。ドキュメントには、次のトレードオフがリストされています
- 標準の連想コンテナよりも高速なルックアップ
- 標準の連想コンテナーよりもはるかに高速な反復
- 小さなオブジェクト (および、shrink_to_fit が使用されている場合は大きなオブジェクト) のメモリ消費量が少ない
- キャッシュ パフォーマンスの向上 (データは連続したメモリに格納されます)
- 非安定反復子 (要素を挿入および消去すると、反復子は無効になります)
- コピー不可および移動不可の値型は保存できません
- 標準の連想コンテナーよりも弱い例外安全性 (消去および挿入で値をシフトするときに、コピー/移動コンストラクターがスローされる可能性があります)
- 標準の連想コンテナーよりも挿入と消去が遅い (特に非可動型の場合)
于 2013-08-07T06:39:58.687 に答える