O(1)ルックアップを使用したC++のデータ構造はありますか？
Astd::mapにはO(log(n))ルックアップ時間があります（右？）。
私はstdできれば何かから探しています（Boost plsではありません）。また、ある場合、それはどのように機能しますか？
編集：わかりました、私は私が推測するのに十分に明確ではありませんでした。のように、値を関連付けたいmap。だから私はのようなものが欲しいstd::map<int,string>、そしてfind取るinsert必要がありますO(1)。
配列にはO（1）ルックアップがあります。c ++ 11のハッシュテーブル（std :: unordered_map）にはO（1）ルックアップがあります。（償却済みですが、多かれ少なかれ一定です。）
また、マップのようなツリーベースのデータ構造には大きな利点があり、log（n）しかないため、十分ではない場合が多いことにも触れておきます。
編集への回答->配列のインデックスを値の1つに文字通り関連付けることができます。また、ハッシュテーブルは連想的ですが、完全なハッシュ（各キーは正確に1つの値にマップされます）を取得するのは非常に困難です。
言及する価値のあるもう1つのこと：配列は優れたキャッシュパフォーマンスを備えています（局所性、つまり要素が互いに隣接しているため、機能エンジンによってキャッシュにプリフェッチできるため）。木、それほど多くはありません。適度な量の要素がある場合、ハッシュのパフォーマンスは漸近的なパフォーマンスよりも重要になる可能性があります。
配列にはO(1)ルックアップがあります。