c++ - stl::set の stl::map の効率

Question

問題を解決するために boost::icl::interval_map を使用したいと思います (ここで説明します。 interval_maps が最終的に機能する場合は、完全な回答を投稿します。)

を使用したいのですinterval_map<unsigned long long, set<foo*>>が、boost::icl のドキュメントには、潜在的な効率の問題があると記載されています (以下の から)。

教訓的な利点があるため、一連の文字列の間隔マップを使用して interval_maps を導入しています。パーティの例は、インターバル マップとオーバーラップの集計の基本的な考え方にすぐにアクセスできるようにするために使用されます。実際のアプリケーションでは、セットの interval_map は必ずしも推奨されません。std::set の std::map と同じ効率の問題があります。関連する値の数値およびその他の効率的なデータ型で interval_maps を使用することには大きな領域があります。

std::set の std::map の効率の問題は何ですか? どうすればそれらを回避できますか ?

Answer 1

std::map<K, V>とは両方とも、std::set<V>ポインターによってリンクされたノード ベースのコンテナーです。それらをトラバースすると、複雑さが保証されます (つまり、個々の操作は最大で O(log n) です) が、実際には複雑さが問題になるにはかなり大きなコンテナーがstd::vector<std::pair<K, V>>必要KですV。ノードベースのコンテナの主なパフォーマンスの問題は、現在の CPU が何らかの形でクラスタ化されたデータにアクセスすることを好む一方で、それらがメモリ内で多かれ少なかれランダムに配置されることです。

もちろん、いつものように、どのデータ構造が最高のパフォーマンスをもたらすかを判断するために、かなり現実的なデータ セットで異なる実装間で得られた時間を測定する必要があります。