O(1)ルックアップを持つC++のデータ構造はありますか？C（+）でのO（1）ルックアップ
std::mapには、O(log(n))の検索時間（右？）があります。
私はstdの中から何かを探しています（Boost plsはありません）。また、もしあれば、どのように機能するのですか？
EDIT：わかりました。私は値を関連付けたい、mapのような種類。だから、私はstd::map<int,string>のようなものを、findとinsertはO(1)とする必要があります。
アレイはO（1）ルックアップを持っています。 C++ 11のHashtable（std :: unordered_map）にはO（1）ルックアップがあります。
マップのようなツリーベースのデータ構造には大きな利点があり、log（n）だけで十分ではないこともよく言及したいと思います。
編集への回答文字通り、配列のインデックスを値の1つに関連付けることができます。また、ハッシュテーブルは連想的ですが、完全なハッシュ（各キーは正確に1つの値にマップされます）は実際には得難いです。
さらに言及する価値のあることは、アレイは優れたキャッシュパフォーマンスを持っています（ローカリティのために、要素はすぐ隣にあり、prefectエンジンでキャッシュにプリフェッチできます）。木々、そうではありません。妥当な量の要素では、ハッシュ・パフォーマンスは漸近的なパフォーマンスよりも重要です。
また、TR1には順序付けられていないマップがあることに言及する価値があります。 VS2008以前のGCCのようなコンパイラの中にはTR1を実装していますが、C++ 11は実装していません。 – Puppy
@scarletamaranth主な理由は、配列がとてもパフォーマンスが良いということです - あなたが話しているように正確にはっきりしていないと言ったように、システムはメモリ内でジャンプします（インデックス+ sizeof（type）*インデックスの終わり）キャッシュの –
@Shingetsuそれは私が言ったことです... – ScarletAmaranth
すべてはデータ、特にキーのタイプと可能な*値によって決まります。したがって、どのような種類のデータを保存したいですか？ – Nawaz
リンクされた配列に似たものがありますか？それはO（1）についてです。リンクされた配列は、配列のリンクされたリストです。 –
'std :: unordered_map <>'名前空間 'std'にあるのは、名前空間' boost'に最初にあったからです。 – ildjarn