邪魔な unordered_map を使用しようとしています。何らかの理由で、ライブラリには unordered_set しかありません。侵入型のハッシュテーブルもありますが、同じ機能を持っているかどうかはわかりません。また、同じインターフェースもありません。
私は間違っていて、unordered_map リンクを見逃しましたか?
そうでない場合、実装に役立つチュートリアルはありますか?
4029 次
2 に答える
7
興味深い質問です。Boost.Intrusiveは、順序付けされているかどうかに関係なく、マップインターフェイスを提供していないようです。順序付けされたマップ（赤黒木、AVLツリー、スプレーツリー）と順序付けられていないマップ（ハッシュテーブル）の両方として正常に機能する実装タイプが多数あります。しかし、地図はなく、その理由はわかりませんでした。
私が見ているように、2つの選択肢があります。
- 使用するだけ
hashtableです：順序付けされていないコンテナはハッシュテーブルとして実装されます（そして、それらが呼び出されhash_mapない唯一の理由は、その名前を使用している既存のライブラリとの名前の衝突を回避するためです）。あなたがあなたの仕事を成し遂げたいならば、それはうまくいくでしょう。 - 本当に独自の実装が必要な場合は、Boost.Intrusiveのunordered_setのインターフェイスの説明を確認してください。私は実装を見ていませんが、それはほぼ確実に1つ以上のツリータイプのラッパーです。
std::setどちらも通常、std::map赤黒木のラッパーとして実装されます（私が調べたすべての標準ライブラリ実装では、GCC、MSVC、およびApacheのstdcxx）。また、libstdc++がツリー実装をでどのようにラップするかについても見<map>て<set>ください。それは多くの定型文であり、その多くは退屈ですが、どちらのタイプもほとんどすべての作業をツリーに延期します。Boost.Intrusiveの類似したことがほぼ確実に起こっています。unordered_set。マップインターフェイスとセットインターフェイスの違いを確認し、それをに変更するための基礎として使用する必要がありunordered_setますunordered_map。
私は後者を行いました。これは少し面倒な面です。ユニットテストを作成することを強くお勧めします（またはlibstdc ++またはBoost.Intrusiveに付属するテストを盗むことを強くお勧めします）。しかし、それは実行可能です。また、SGI（set、map）またはlibstdc ++のいずれかで、セットとマップの要件ドキュメントを読むことを強くお勧めします。
更新：マップを実行しない理由を理解しました。侵入型コンテナーでは、データ構造のノード情報を、格納している値型に埋め込む必要があります。マップの場合、値とキーの両方に対してこれを行う必要があります。これが不可能なわけではありませんが、aの標準実装では、sと同じ内部型をmap使用します。ただし、これらの内部型には1つの変数しかありません。キーと値を格納するために、キーと値をその変数にコピーし、それをノードに格納します。侵入型で（つまりコピーせずに）これを行うには、その実装型を変更してセットと互換性がないようにする必要があります。キーと値への参照を別々に格納する必要がありますset value_type。したがって、それを行うには、使用する実装も変更する必要があります（おそらくhashtable）。これも不可能ではありませんが、ライブラリ設計者は深刻なコードの重複を避けようとしている可能性が高いため、これを実装する簡単な方法がないため、マップを除外することにした可能性があります。
それは理にかなっていますか？
于 2009-07-31T17:24:22.143 に答える
6
久しぶりの質問ですが、ここに来る人unordered_setは地図としての使い方に興味があると思います。解決策は、高度な挿入方法を使用することです。キーとその値を同じ場所に保存し、 and を使用しvalue_typeて挿入するだけです。insert_checkinsert_commit
于 2012-07-26T12:44:11.220 に答える