8

「ユーザー指定」の定義されたキーの順序を維持しながら、 type のキーを typeの値に[(a,b)]マッピングする、辞書として機能するペアの単純なリストのように動作する型を使用したいと思います。（つまり、通常のリストと同じように、「最後の要素」として認識されるアイテムを「追加」できるようにしたいと考えています。）ただし、線形パフォーマンスよりも優れたキーのランダムアクセスルックアップが必要です。 . 1 つのオプションは、順序を定義するキーのリストに加えて、通常のマップを維持することです。abData.Map

data OrderedDict a b = OrderedDict (Map a b) [a]

append次に、2 つのキー コレクションの同期を維持する操作などを定義します。ただし、同じキーの 2 つの個別のコレクションを維持するのは見苦しく思えます。順序付けられたキーとキーによる効率的なランダム アクセス ルックアップを既に組み合わせた既製のデータ型はありますか?

4

3 に答える 3

4

ixsetライブラリを見てみましょう- 複数の列 (あなたの場合はbyaと by ) によってインデックス付けされたセットを維持できます。Intこれは、手動でマップの一貫性を維持するよりもはるかに保守性が高くなります

于 2012-06-08T09:05:19.357 に答える
3

私があなたの質問を完全に誤解していない限り、Data.Map はOrd順序付けにキー タイプのインスタンスを使用して、まさにこれを行います。これは二分木であるため、実装ではキーの順序も維持されます。

Data.Map.keys昇順でマップのキーを提供します。Map のなどの変換mapは純粋に機能的であるため、トラバーサルの順序は無関係であり、キーのシーケンスまたはキーと値のペアを Map から取得するすべての方法で、順序付けられたリストが得られます。

于 2012-06-08T06:50:30.893 に答える
3

O(log n) ルックアップ/挿入に加えて、固定された順序 (挿入時間など)を維持したい場合は、単純に複数のマップを使用してそれらを同時に更新できます。

  1. Map a b実際のデータを格納するため、および
  2. Map Int aこれにより、順序で i 番目のキーが得られます。(特定のキーのインデックスも照会する必要がある場合は、追加できますMap a Int)
于 2012-06-08T07:29:02.557 に答える