Boost 1.56.0に向けて、Boost.MultiIndexがhashed indexを完全に再実装したそうです。
再実装の内容としては、今まで要素の削除にO(D(n))計算量かかっていたのを、O(1)にしたとのこと。
これは、標準Unorderedコンテナのベンダーごとの様々な実装から得られた経験を、反映させたものです。その調査については、Boost.MultiIndex作者であるJoaquín M López Muñozさんのブログにまとまっています。
- Implementation of C++ unordered associative containers
- Implementation of C++ unordered associative containers with duplicate elements
パフォーマンス測定の結果: