hash-map.dd

Ddoc

$(SPEC_S 連想配列,

        $(P 連想配列はindexが必ずしも整数である必要はなく、
		疎なindexも扱えます。
		連想配列のインデックスのことを $(I key) と呼び、その型を $(I KeyType)と呼びます。
        )

        $(P 連想配列は、
		配列宣言の[]の中に $(I KeyType) を書いて宣言します：
        )

---------
int[string] b;    // 文字の配列で添え字づけられた
                  // int型の連想配列 b
                  // $(I KeyType) は string
b["hello"] = 3;   // key "hello" に値 3 を関連付ける
func(b["hello"]); // 3 を func() へ引数として渡す
---------

        $(P 連想配列のkeyは、
	remove 関数によって取り除くことができます：
        )

---------
b.$(B remove)("hello");
---------

        $(P $(I InExpression) によって、値がある連想配列のkeyであればその要素へのポインタ、
        そうでなければ $(B null) が得られます：
        )

---------
int* p;
p = ("hello" $(B in) b);
if (p !is (B null))
        ...
---------

        $(P 関数型とvoidは $(I KeyType) にできません。
        )

        $(P 関数型とvoidは要素型にすることもできません。)

<h3>クラスをKeyTypeとして使うには</h3>

        $(P クラスを $(I KeyType)として使うこともできます。
		そのためには、
		クラスの定義で、以下にあげる $(D Object) のメンバ関数をオーバーライドしてください:)

        $(UL
        $(LI $(D hash_t toHash()))
$(V1    $(LI $(D int opEquals(Object))))
$(V2    $(LI $(D bool opEquals(Object))))
        $(LI $(D int opCmp(Object)))
        )

        $(P $(D hash_t) は整数型へのaliasです。)

        $(P $(D opCmp) と $(D opEquals)
		への引数の型はそのクラス自身ではなく、
        $(D Object) 型とすることに注意が必要です。)

        $(P 例:)

---
class Foo {
  int a, b;

  hash_t $(B toHash)() { return a + b; }

$(V1    int $(B opEquals)(Object o))$(V2    bool $(B opEquals)(Object o))
  { Foo foo = cast(Foo) o;
    return foo && a == foo.a && b == foo.b;
  }

  int $(B opCmp)(Object o)
  { Foo foo = cast(Foo) o;
    if (!foo)
      return -1;
    if (a == foo.a)
      return b - foo.b;
    return a - foo.a;
  }
}
---

        $(P 処理系は $(D opEquals) か $(D opCmp)、あるいはその両方のいずれかを使用します。
		実装する際は、オブジェクト同士が等しいかどうかの判定に関しては
        $(D opEquals) と $(D opCmp)
		の結果が矛盾しないよう注意してください。)

<h3>構造体や共用体をKeyTypeとして使うには</h3>

        $(P $(I KeyType) が構造体型の場合、
		構造体のバイナリ表現を使ったハッシュ計算や比較が
		デフォルトの方式として使われます。
		カスタマイズしたい場合は、
		以下の関数を構造体のメンバとして提供します：
        )

---------
$(V2 const) hash_t $(B toHash)();
$(V1 int $(B opEquals)($(I KeyType)* s);)$(V2 const bool $(B opEquals)(ref const $(I KeyType) s);)
$(V1 int $(B opCmp)($(I KeyType)* s);)$(V2 const int $(B opCmp)(ref const $(I KeyType) s);)
---------

        $(P 例:)

$(V1
---------
import std.string;

struct MyString {
  string str;

  hash_t $(B toHash)()
  { hash_t hash;
    foreach (char c; str)
      hash = (hash * 9) + c;
    return hash;
  }

  bool $(B opEquals)(MyString* s)
  {
    return std.string.cmp(this.str, s.str) == 0;
  }

  int $(B opCmp)(MyString* s)
  {
    return std.string.cmp(this.str, s.str);
  }
}
---------
)
$(V2
---------
import std.string;

struct MyString {
  string str;

  const hash_t $(B toHash)()
  { hash_t hash;
    foreach (char c; str)
      hash = (hash * 9) + c;
    return hash;
  }

  const bool $(B opEquals)(ref const MyString s)
  {
    return std.string.cmp(this.str, s.str) == 0;
  }

  const int $(B opCmp)(ref const MyString s)
  {
    return std.string.cmp(this.str, s.str);
  }
}
---------
)


        $(P 処理系は $(D opEquals) か $(D opCmp)、あるいはその両方のいずれかを使用します。
	実装する際は、オブジェクト同士が等しいかどうかの判定に関しては
        $(D opEquals) と $(D opCmp)
        の結果が矛盾しないよう注意してください。)

<h3>プロパティ</h3>

連想配列のプロパティは以下の通りです：

    $(TABLE2 連想配列のプロパティ,
        $(TR $(TH プロパティ) $(TH 説明))

        $(TR
        $(TD $(B .sizeof))
        $(TD 連想配列への参照のサイズを返します。
		32bitでは4で64bitでは8です。
        )
        )

        $(TR
        $(TD $(B .length))
        $(TD 連想配列に格納された値の個数を返します。
		動的配列とは異なり、読み取り専用です。
        )
        )

        $(TR
        $(TD $(B .keys))
        $(TD 連想配列のkeyからなる
		動的配列を返します。
        )
        )

        $(TR
        $(TD $(B .values))
        $(TD 連想配列のvalueからなる
		動的配列を返します。
        )
        )

        $(TR
        $(TD $(B .rehash))
        $(TD 連想配列をin-placeで再構成し、より効率的なアクセスを可能にします。
		rehashは、例えば、
		プログラムがシンボルテーブルのロードを終えて、
		さあ高速に参照したい、というときに効果があります。
		返値は、再構成された配列自身です。
        )
        )

$(V2
        $(TR
        $(TD $(B .byKey()))
        $(TD
		$(GLINK2 statement, ForeachStatement)
        によって連想配列のkey全体をループするための
        delegateを返します。
        )
        )

        $(TR
        $(TD $(B .byValue()))
        $(TD 
		$(GLINK2 statement, ForeachStatement)
	によって連想配列のvalue全体をループするための
	delegateを返します。
        )
        )

        $(TR
        $(TD $(B .get(Key key, lazy Value defaultValue)))
        $(TD $(I key) を連想配列から検索し、存在すれば対応する $(I value) を返し、
        存在しなければ $(I defaultValue) を評価し値を返します。
        )
        )
)
    )

<hr>
<h3>連想配列の例： 単語数カウント</h3>

        $(P 例では簡単のために、ファイルがASCIIでエンコードされLFで改行されているものとします。
        汎用に書くには、$(I dchar c) をループに使い、
        $(STD_UNI) の関数を利用します。
        )

---------
import std.file;         // D のファイル I/O
import std.stdio;
import std.$(V1 ctype)$(V2 ascii);

void main (string[] args) {
  ulong totalWords, totalLines, totalChars;
  ulong[string] dictionary;

  writefln("   lines   words   bytes file");
  foreach (arg; args[1 .. $]) // 先頭以外の引数それぞれについて
  {
    ulong wordCount, lineCount, charCount;

    $(V1 bool inWord;
    size_t wordStart;

    // ファイルバッファへ読み込み
    auto input = cast(string)std.file.read(arg);

    foreach (i, char c; input)
    {
      if (std.ctype.isdigit(c))
      { // c は数字 (0..9)
      }
      else if (std.ctype.isalpha(c))
      { // c はASCII文字 (A..Z, a..z)
        if (!inWord)
        {
          wordStart = i;
          inWord = true;
          ++wordCount;
        }
      }
      else if (inWord)
      {
        auto word = input[wordStart .. i];
        ++dictionary[word];   // 単語数をカウントアップ
        inWord = false;
      }
      ++charCount;

      // 行は LF 終端としましょう。
      if (c == '\n')
        ++lineCount;
    }
    if (inWord)
    {
      auto word = input[wordStart .. $];
      ++dictionary[word];
    }
)$(V2 foreach(line; File(arg).byLine())
    {
      bool inWord;
      size_t wordStart;

      void tryFinishWord(size_t wordEnd)
      {
        if (inWord)
        {
          auto word = line[wordStart .. wordEnd];
          ++dictionary[word.idup];   // 単語数をカウントアップ
          inWord = false;
        }
      }

      foreach (i, char c; line)
      {
        if (std.ascii.isDigit(c))
        { // c は数字 (0..9)
        }
        else if (std.ascii.isAlpha(c))
        { // c はASCII文字 (A..Z, a..z)
          if (!inWord)
          {
            wordStart = i;
            inWord = true;
            ++wordCount;
          }
        }
        else
          tryFinishWord(i);
        ++charCount;
      }
      tryFinishWord(line.length);
      ++lineCount;
    }
)
    writefln("%8s%8s%8s %s", lineCount, wordCount, charCount, arg);
    totalWords += wordCount;
    totalLines += lineCount;
    totalChars += charCount;
  }

  if (args.length > 2)
  {
    writefln("-------------------------------------\n%8s%8s%8s total",
            totalLines, totalWords, totalChars);
  }

  write$(V1 f)ln("-------------------------------------");
  foreach (word; dictionary.keys.sort)
  {
    writefln("%3s %s", dictionary[word], word);
  }
}
---------

)

Macros:
        TITLE=連想配列
        WIKI=AssociativeArrays
        DOLLAR=$
        STD_UNI=<a href="phobos/std_uni.html">std.uni</a>
        FOO=
	CATEGORY_SPEC=$0