"SortedKeyStore" (データ構造)

"SortedKeyStore"

ソートされた順序でキーを維持する，キーと値のストアを表す．

詳細

  • ソートされたキーストアは通常キーと値を保存するために使われる．
  • ソートされたキーストア内のキーは，ソートされた順序で維持される．
  • CreateDataStructure[ "SortedKeyStore"]新しい空の"SortedKeyStore"を作成する
    Typed[x,"SortedKeyStore"]x に"SortedKeyStore"の型を与える
  • "SortedKeyStore"型のデータ構造には，以下の演算が使える．
  • ds["Copy"]ds のコピーを返すtime: O(n)
    ds["Elements"]ds のキーと値のペアのリストを返すtime: O(n)
    ds["EmptyQ"]ds に要素がない場合にTrueを返すtime: O(1)
    ds["Insert",keyvalue]key を関連付けられた value で ds に加える．追加によって ds が変更された場合にはTrueを返すtime: O(log n)
    ds["KeyDrop",key]key とその値を ds から除去するtime: O(log n)
    ds["KeyDropAll"]すべてのキーとその値を ds から除去するtime: O(n)
    ds["KeyExistsQ",key]key が ds に存在する場合にはTrueを返すtime: O(log n)
    ds["Keys"]ds 内のキーをソートしたリストとして返すtime: O(n)
    ds["KeyValueFold",fun,init]fun を ds の規則に適用する．init から始めて，結果を累積するtime: O(n)
    ds["KeyValueScan",fun]fun を ds の規則に適用するtime: O(n)
    ds["Length"]ds に保存されたキーと値のペアの数time: O(1)
    ds["Lookup",key]ds に key と一緒に保存された値を返す．キーが見付からない場合にはMissingオブジェクトを返すtime: O(log n)
    ds["Lookup",key,defFun]ds に key と一緒に保存された値を返す．キーが見付からない場合には defFun[key]を返すtime: O(log n)
    ds["PeekFirst"]ds 内の最初のキーと値のペアを返すtime: O(1)
    ds["PeekLast"]ds 内の最後のキーと値のペアを返すtime: O(1)
    ds["PopFirst"]ds から最初のキーと値のペアを除去し，それを返すtime: O(1)
    ds["PopLast"]ds から最後のキーと値のペアを除去し，それを返すtime: O(1)
    ds["Values"]ds 内の値を対応するキーでソートしたリストとして返すtime: O(n)
    ds["Visualization"]ds の可視化を返すtime: O(n)
  • 以下の関数もサポートする．
  • dsi===dsjdsi が dsj に等しい場合はTrue
    FullForm[ds]ds の完全形
    Information[ds]ds についての情報
    InputForm[ds]ds の入力形
    Normal[ds]ds を通常の式に変換する
  • "SortedKeyStore"型のデータ構造は以下のオプション付きで作成できる．
  • "SortDirection""Forward"キーを前進モードと後進モードのどちらでソートするか

例題

すべて開くすべて閉じる

例  (1)

新しい空の"SortedKeyStore"は，CreateDataStructureを使って作成できる：

規則として与えられるキーと値のペアを"SortedKeyStore"のデータ構造に挿入する：

キーがあるかどうかを検証する：

キーはストアから除去することができる：

これでキーがストアに存在しなくなった：

いくつかのキーと値を挿入する：

キーはソートされた順序で返される：

値は，そのキーの順序に従って返される：

式バージョンの ds を返す：

データ構造の可視化を生成することができる：

スコープ  (3)

情報  (1)

新しい"SortedKeyStore"は，CreateDataStructureを使って作成することができる：

データ構造 ds についての情報：

走査  (1)

関数の走査を作成できる．項目は順に計算される．

新しい"SortedKeyStore"は，CreateDataStructureを使って作成し，いくつかの要素を挿入することができる：

それぞれのキーと値のペアに訪れ，関数を適用する：

それぞれのキーと値のペアに訪れて関数を適用し，結果を累積する：

SortDirection  (1)

デフォルトでキーは昇順にソートされる：

"SortDirection"オプションを使うと，キーを降順でソートすることができる：