0

フル機能の抽象データ型としてハッシュマップをC++でゼロから実装します。特に、このデータコンテナには、識別キーの昇順ですべてのレコードをトラバースできるイテレータを提供します。そして、この部分は私を混乱させます、私はこれをどのように行うのか分かりません。ところで、ハッシュ関数によって、私は一方向リストで別々のチェーンを使用することにしました。私が思いついた解決策の1つは、すべての要素を適切な順序でまとめてバインドする別のリストを作成することです。このリストの機能は、挿入プロセス自体で保護されます。しかし、少なくとも挿入に関しては、ハッシュ自体の利点の多くを損なうように思われます。特に、私のADTの目的を見ると、トラバーサル機能は比較的めったに使用されません。短編小説、どのようなソリューションを提供する必要がありますか？専用ライブラリは使用できませんのでご了承ください。

ノート：

私はハッシュマップが何であるか、そしてそれが本質的に順序付けられていないその学術的定義によるものであることを知っています。別の言い方をすれば、基本的にハッシュマップとイテレータ機能を提供する追加の軽量モジュールで構成されるハイブリッドで実用的なADTを構築して、そのようなADTのユーザーがキーの昇順でレコードを随時。

4

2 に答える 2

3

ハッシュマップは本質的に順序付けられていません。そのため、C++では通常unordered_mapという名前が付けられています。ハッシュマップのイテレータは、各メンバーを1回訪問しますが、順序は定義されていません。

実際には、ハッシュマップを使用せず、赤黒木などの他の連想マップコンテナを使用する可能性があります。または、更新がまれな場合は、並列順序付けされたインデックスを維持します。または、更新が頻繁であるがトラバーサルがまれである場合は、ソートされたインデックスをオンデマンドで生成します。

于 2012-12-06T22:34:31.470 に答える
0

ハッシュを使用して値を格納する場所を知ることが重要であるため、ハッシュマップは本質的にソートされていません。

これが機能する可能性があることを確認できる唯一の方法は(パフォーマンスと実際の使いやすさに多少のコストがかかります)、ハッシュが常に増加していることを保証する場合です。つまり、ハッシュは挿入順序の関数であり、順序付けられたハッシュが得られます。ただし、これは衝突しないハッシュのみを処理します。バケット内のリストを正しい順序でトラバースする必要があるため、挿入時にリストをソートしておくだけです

多分これはうまくいかないでしょう、それはただのアイデアです

そうでない場合、他の唯一の方法は、すべての値を並べ替えに適した構造に格納し、そこから反復することです。ハッシュマップ クラスでこれを行うと、ハッシュマップを反復しているように見えますが、実際にはそうではありません。このアプローチでは、反復時にメモリ要件が 2 倍になることに注意してください。

それがどうなるか教えてください、これは奇妙な要件です

于 2012-12-06T22:42:10.913 に答える