std :: mapやmultimapに似たものを実装するライブラリを探していますが、ツリーはなく、代わりに。のようなベクトルがありpair<vector<key>,vector<value>>ます。libは、ベクトルの同期とソートを維持する必要があります。
マップとそのようなライブラリのパフォーマンスを比較したいと思いvector<pair<key,value>>ます。私は一般的なベンチマークを作成しようとはしません。自分のアプリケーションにとってより高速なものだけが必要です。
他の人と同じようにマップを使用することもできますが、-そして私が話しているのかわかりません-キャッシュミスが多すぎるのではないかと心配しています。私の野蛮で知識のない推測では、私のアプリは、少数のグループ化された挿入と多くの散在する検索を実行するので、よりコンパクトで連続したキーの恩恵を受けるでしょう。
実際のところ、私が物事をコーディングする場合、2つのクラスでそれを行います。高速のpush_back挿入のみが許可されている未ソートのバージョン、次に未ソートのバージョンを取得してソートし、重複をチェックして、高速の検索と低速のソート済みの挿入を許可するソート済みバージョンへの変換。これは実際にはScottMeyersのEffectiveSTLのアイテム23：「連想コンテナをソートされたベクトルに置き換えることを検討してください」です。
編集：flat_（multi）map / setに関するBoostのドキュメントで指摘されているように、 ScottMeyersではなくMattAusternが最初にマップとセットをベクトルに置き換えることを提案しました：http：//lafstern.org/matt/col1.pdf