高速ルックアップstd::map用に最適化された-esqueデータ構造を探しています。
std::vector1つのアプローチは、基になるストレージとしてソートされたものを利用してマップのインターフェースを実装することです。これはbinary_search、ランダムアクセスイテレーターとキャッシュの局所性のおかげで高速に提供されます。
しかし、これは車輪の再発明のように聞こえます。確かにこのようなものはすでに存在しますか？
ストレージにstd::vectorを使用するオープンソースの順序付けられた連想データ構造はありますか？
編集：
std :: mapを使用することを提案するコメントに応えて-ここを読んでください：http：//lafstern.org/matt/col1.pdf
Boost.Containers ライブラリには順序付きマップ コンテナがあり、そのストレージは と呼ばれる連続した配列によって支えられていboost::flat_mapます。ただし、漸近的で理論的な複雑さは標準map(対数) と同じであり、より適切な選択はユースケースの多くの詳細(挿入とルックアップ、反復、反復子の無効化要件) に依存することに注意してください。
インターフェイスは非常に似ているため、typedef を介して文字どおり一方を他方に置き換え、相対的なパフォーマンスをプロファイリングすることが可能である必要があります。これは、絶対に実行する必要があることです。
ストレージに std::vector を使用するオープンソースの順序付き連想データ構造はありますか?
sortedvectorを維持するのはどうですか？そうすれば、ルックアップが高速になります (バイナリ検索、ポインター トラバーサルなし)。