Programming in D - 連想配列

連想配列

連想配列は、ほとんどの現代の高水準言語に存在する機能である。これらは、ミニデータベースのように機能する非常に高速なデータ構造であり、多くのプログラムで使用されている。

配列の章で見たように、単純な配列は要素を横並びに格納し、インデックスでアクセスするコンテナだ。週の日の名前を格納する配列は次のように定義できる。

string[] dayNames =
    [ "Monday", "Tuesday", "Wednesday", "Thursday",
      "Friday", "Saturday", "Sunday" ];

特定の日の名前は、その配列内のインデックスでアクセスできる:

writeln(dayNames[1]);   // "Tuesday"を表示

単純な配列は、インデックス番号によってその値にアクセスできることを、インデックスと値の関連付けと表現することができる。つまり、配列はインデックスを値にマッピングする。単純な配列では、インデックスとして整数しか使用できない。

連想配列では、整数だけでなく、他の型もインデックスとして使用できる。連想配列は、ある型の値を別の型の値にマッピングする。連想配列がマッピングする元の型の値は、インデックスではなくキーと呼ばれる。連想配列は、要素をキーと値のペアとして格納する。

連想配列はDではハッシュテーブルを使用して実装されている。ハッシュテーブルは、要素の格納とアクセスにおいて最も高速なコレクションの一つである。まれな病的なケースを除き、要素を格納またはアクセスする時間は、連想配列内の要素の数に依存しない。

ハッシュテーブルの高性能は、要素を無順序に格納する代償として得られている。また、配列とは異なり、ハッシュテーブルの要素は隣り合って格納されない。

単純な配列では、インデックス値はまったく格納されない。配列の要素はメモリ内に隣り合って格納されるため、インデックス値は配列の先頭からの要素の相対的な位置となる。

一方、連想配列は、要素のキーと値の両方を格納する。この違いにより、連想配列はより多くのメモリを使用するが、疎なキー値を使用することができる。例えば、キー0と999に格納する要素が2つだけの場合、連想配列は2つの要素だけを格納するが、単純な配列では1000個を格納しなければならない。

定義

連想配列の構文は、配列の構文と似ている。違いは、角括弧で指定するのは配列の長さではなく、キーの型であることである。

value_type[key_type] associative_array_name;

例えば、string型の曜日名をint型の曜日番号にマッピングする連想配列は、次のように定義できる。

int[string] dayNumbers;

上記のdayNumbers変数は、曜日名と曜日番号を対応付けるテーブルとして使用できる連想配列だ。つまり、この章の冒頭で紹介したdayNames配列の逆の役割を果たす。以下の例では、dayNumbers連想配列を使用する。

連想配列のキーは、ユーザー定義のstructやclass型を含め、あらゆる型にすることができる。ユーザー定義型については、後の章で説明する。

連想配列の長さは、定義時に指定することはできない。キーと値のペアが追加されるたびに、自動的に長さが伸びる。

注釈:要素を一切定義していない連想配列は、空ではなく、nullである。この違いは、連想配列を関数に渡す際に重要な意味を持つ。これらの概念については、後の章で説明する。

キーと値のペアの追加

キーと値の関連付けは、代入演算子を使うだけで作成できる。

// 値0をキー"Monday"に関連付ける
dayNumbers["Monday"] = 0;

// 値1をキー"Tuesday"に関連付ける
dayNumbers["Tuesday"] = 1;

テーブルは、関連付けが追加されるたびに自動的に大きくなる。例えば、dayNumbersは、上記の操作の後、2つのキーと値のペアを持つことになる。これは、テーブル全体を出力することで確認できる。

writeln(dayNumbers);

出力は、値0と1がそれぞれキー"Monday"と"Tuesday"に対応していることを示している。

["Monday":0, "Tuesday":1]

キーごとに値は1つしか設定できない。そのため、新しいキーと値のペアを割り当てたときに、そのキーがすでに存在する場合、テーブルは拡大せず、既存のキーの値が変更される。

dayNumbers["Tuesday"] = 222;
writeln(dayNumbers);

出力:

["Monday":0, "Tuesday":222]

初期化

連想配列の定義時に、キーと値の対応の一部がすでにわかっている場合がある。連想配列は、通常の配列と同様に、コロンを使用して各キーとそれに対応する値を区切って初期化する。

// キー : 値
int[string] dayNumbers =
    [ "Monday"   : 0, "Tuesday" : 1, "Wednesday" : 2,
      "Thursday" : 3, "Friday"  : 4, "Saturday"  : 5,
      "Sunday"   : 6 ];

writeln(dayNumbers["Tuesday"]);    // 1を表示

キーと値のペアの削除

キーと値のペアは、.remove()を使用して削除することができる。

dayNumbers.remove("Tuesday");
writeln(dayNumbers["Tuesday"]);    // ← 実行時エラー

上記の最初の行は、キーと値のペア "Tuesday" /1を削除する。そのキーはコンテナにもはや存在しないため、2行目は例外をスローし、その例外がキャッチされない場合、プログラムは終了する。例外については、後の章で説明する。

.clear すべての要素を削除する:

dayNumbers.clear;    // 連想配列が空になる

キーの存在を確認する

in演算子は、指定されたキーが連想配列に存在するかどうかを判断する:

int[string] colorCodes = [ /* ... */ ];

if ("purple" in colorCodes) {
    // キー"purple"はテーブルに存在する

} else {
    // キー"purple"はテーブルに存在しない
}

連想配列にキーが存在しない場合に、デフォルト値を使用することが適切な場合がある。例えば、colorCodesに存在しない色のコードとして、特別な値-1を使用することができる。.get()は、このような場合に便利だ。この関数は、指定したキーが存在する場合、そのキーに関連付けられた値を返し、存在しない場合はデフォルト値を返す。デフォルト値は、.get()の2番目のパラメータとして指定する。

int[string] colorCodes = [ "blue" : 10, "green" : 20 ];
writeln(colorCodes.get("purple", -1));

配列にはキー "purple"の値が含まれていないため、.get()は-1を返す:

-1

プロパティ

.lengthは、キーと値のペアの数を返す。
.keys すべてのキーのコピーを動的配列として返す。
.byKey キーをコピーせずにアクセスする。.byKeyがforeachループでどのように使用されるかは、次の章で説明する。
.values すべての値のコピーを動的配列として返す。
.byValue 値をコピーせずにアクセスする。
.byKeyValue キーと値のペアをコピーせずにアクセスできる。
.rehash 多くの場合、配列の効率が向上する。例えば、多数のキーと値のペアを挿入した後などだ。
.sizeofは、配列参照のサイズだ (テーブル内のキーと値のペアの数とは関係なく、すべての連想配列で同じ値になる)。
.get 値が存在する場合、その値を返す。
.remove 指定したキーとその値を配列から削除する。
.clear すべての要素を削除する。

例

英語で指定された色のトルコ語名を表示するプログラムの例:

import std.stdio;
import std.string;

void main() {
    string[string] colors = [ "black" : "siyah",
                              "white" : "beyaz",
                              "red"   : "kırmızı",
                              "green" : "yeşil",
                              "blue"  : "mavi" ];

    writefln("I know the Turkish names of these %s colors: %s",
             colors.length, colors.keys);

    write("Please ask me one: ");
    string inEnglish = strip(readln());

    if (inEnglish in colors) {
        writefln("\"%s\" is \"%s\" in Turkish.",
                 inEnglish, colors[inEnglish]);

    } else {
        writeln("I don't know that one.");
    }
}

演習

.clearを呼び出す以外に、連想配列のすべてのキーと値のペアを削除するにはどうすればいいか?(.clearが最も自然な方法である。)少なくとも3つの方法がある。
- 連想配列から1つずつ削除する。
- 空の連想配列を代入する。
- 前の方法と同様に、配列の.initプロパティを代入する。
  注釈:変数または型のプロパティは、その型の初期値だ。.init
```
number = int.init;    // 0はint
```
  D
  IDEで開く
配列と同様、各キーには1つの値しか指定できない。これは、一部のアプリケーションでは制限となる場合がある。
連想配列を学生の成績の保存に使用するとする。例えば、学生"emre"の成績90、85、95などを保存するとする。

連想配列を使用すると、grades["emre"]のように、学生の名前で成績に簡単にアクセスできる。しかし、次のコードのように成績を挿入することはできない。なぜなら、各成績が前の成績を上書きしてしまうからだ:
```
int[string] grades;
grades["emre"] = 90;
grades["emre"] = 85;   // ← 前の成績を上書きする!
```
D
IDEで開く
この問題を解決するにはどうすればよいか?1人の生徒につき複数の成績を格納できる連想配列を定義しよう。

... 解答