std::tr1::unowned_map がわかりません

Question

文字列を通じて特定のオブジェクトにインデックスを付けるだけでなく、挿入順序も維持する連想コンテナが必要です。そのため、特定のオブジェクトを名前で検索したり、オブジェクトを反復処理して、挿入した順序と同じ順序でオブジェクトを取得したりできます。彼ら。

私はこう思います リンクリストとハッシュマップのハイブリッド 仕事をするはずですが、使用しようとする前に std::tr1::unordered_map 私が説明したように機能していると考えていましたが、そうではありませんでした。それで誰かが私に の意味と動作を説明してもらえませんか unordered_map?

---

@ウェスク:std::map は STL によって実装されていると確信していますが、std::hash_map は STL に含まれていないと確信しています (古いバージョンの Visual Studio では stdext という名前空間に配置されていたと思います)。

@クリストファー:したがって、正しく理解できれば、違いは実装 (したがってパフォーマンス) にあり、外部での動作の違いではありません。

Answer 1

順序付けされていないコンテナーの文書化を強化する

違いは、ルックアップを生成する方法にあります。

マップ/セットコンテナでは、 operator< 順序付きツリーを生成するために使用されます。

順序付けされていないコンテナでは、 operator( key ) => index 使用されている。

その仕組みの説明については、「ハッシュ」を参照してください。

Answer 2

Boost::MultiIndex が作成された正規の理由を尋ねました。キーによる高速検索によるリスト挿入順序。 MultiIndex をブーストするチュートリアル:リストの高速検索

Answer 3

連想コンテナにインデックスを付けるには、次の 2 つの方法が必要です。

• 広告掲載オーダー
• 文字列比較

試す Boost.MultiIndex または ブースト侵入型. 。私はこの方法で使用したことはありませんが、可能だと思います。

Answer 4

申し訳ありませんが、最後のコメントを読み間違えてください。はい、hash_map は STL にありませんが、map は STL にあります。しかし、unowned_map と hash_map は、私が読んできたものと同じです。

マップ -> ログ (n) の挿入、取得、反復は効率的です (キーの比較によって順序付けされます)。

hash_map/unowned_map -> 一定時間の挿入と取得、反復時間は効率的であるとは保証されない

マップは挿入シーケンスではなくキーの内容に基づいて順序付けするため、これらはどちらも単独では機能しません (キーに挿入シーケンスに関する情報が含まれていない限り)。

説明したこと (list + hash_map) を実行するか、挿入シーケンス番号と適切な比較関数を持つキー タイプを作成する必要があります。

Answer 5

私 考える unowned_map と hash_map は多かれ少なかれ同じものであるということです。違いは、STL には正式に hash_map がないことです (使用しているものはおそらくコンパイラ固有のものです)。そのため、unowned_map はその省略を修正するものです。

unowned_map はまさに...注文されていない。反復時に順序が維持されることに依存することはできません。

Answer 6

std::hash_map が存在することを確認します 全て STL実装?SGI STL はこれを実装していますが、4.3.1 の時点では GNU g++ にはそれがありません (__gnu_cxx 名前空間にあります)。私の知る限り、hash_map は常に非標準でしたが、現在 tr1 がそれ​​を修正しています。

Answer 7

@ウェスク:STLにはstd::mapがあります...では、unowned_map との違いは何でしょうか?STL が同じものを 2 回実装して、それを別の方法で呼び出すとは思いません。