k3kaimu
6/29/2013 - 2:48 PM

d-manual, 「009 連想配列」 誤字脱字チェック:未完 推敲:未完

d-manual, 「009 連想配列」 誤字脱字チェック:未完 推敲:未完

連想配列

連想配列(Associative Array)とは?

連想配列は、その名前の通り、「キー(key)から、値(value)を連想する」配列です。 ちゃんと言うと、「インデックスが整数じゃなかったり、飛び飛びの値になっている配列」になります。 つまり、「文字列をインデックスとしてdouble型の値を格納した連想配列」というのもできます。 連想配列では、配列でインデックスと呼ばれたものは「キー(key)」といわれます。

基本操作

キーの型をK、値の型をVとすれば、連想配列の型はV[K]です。

百聞は一見に如かず、以下のサンプルソースコードを確認してみましょう。

// test00901.d
import std.stdio;

void main()
{
    int[string] aa = ["homu" : 1, "mami" : 2];

    writeln(aa["homu"]);        // 1
    writeln(aa["mami"]);        // 2
    //writeln(aa["saya"]);      // core.exception.RangeError@test00901(9): Range violation
                                // 存在しないキーにアクセスしたから、エラーが出た.

    aa["foo"] = 12;             // キー"foo"に値`12`を格納
    aa["bar"] = 13;
    writeln(aa["foo"]);         // 12
    writeln(aa["bar"]);         // 13

    aa["foo"] = 15;             // 再度代入
    writeln(aa["foo"]);         // 15

    size_t len = aa.length;     // 現在格納している要素数
    writeln(len);               // 4

    bool b = aa.remove("foo");  // "foo"を削除, removeはaaが"foo"を持っていたかどうかを返す
    writeln(b);                 // true
    len = aa.length;
    writeln(len);               // 3

    aa = null;                  // nullを代入すると、初期化される
    len = aa.length;
    writeln(len);               // 0

    auto aa2 = aa;              // 連想配列は「凄いポインタ」なので、代入はポインタ値の代入に等しい
    aa2["home"] = 2;            // aa2の"home"の書き換え
    writeln(aa["home"]);        // 2
                                // aaも書き換わる

    aa2["mado"] = 100;          // aa2に"mado"を追加
    writeln(aa["mado"]);        // 100
                                // aaにも"mado"が追加されている
}

文章で説明する必要はないと思いますが、連想配列リテラルは[<key0>: <value0>, <key1>:<value1>, ...]というように書きます。 また、キーを指定して値の左辺値を得る方法は、<aa>[<key>]です。

ある一組のキーと値を、連想配列から取り除きたい場合には、<aa>.remove(<key>)とします。 また、全要素削除したいなら、nullを代入します。

連想配列について注意しなければいけないのは、実際には「凄いポインタ」であるということです。 つまり、代入したとしても、凄いポインタなので、ポインタ値が代入されるだけで全く同じ連想配列を指しています。

in演算子

たとえば、連想配列aaが、キーkeyの要素を持っているかどうかわからない状況があります。 そのような場合に、連想配列が実際にそのキーを持っているか確認する方法があります。 それが、in演算子です。

in演算子は、2項演算子で、<key> in <aa>という形式になります。 間違いやすいのは、キーと連想配列の位置ですが、英文的に考えれば自然的でしょう 。

in演算子の結果は、値へのポインタV*です。 もし、連想配列にそのキーがなければnullを返しますが、ある場合にはそのキーに対応する値へのポインタになります。

<key> !in <aa>とすれば、連想配列にそのキーがない場合にtrueとなり、ある場合にはfalseとなります。

// test00902.d
import std.stdio;
import std.exception : enforce;

void main()
{
    auto madoMagi = ["mado": 1, "homu": 2,
                     "saya": 3, "anko": 4];

    // if文と組み合わせて使うと便利
    if(auto p = "mami" in madoMagi)             // false
        writefln("マミさん(%s)は生きています。", *p);
    else
        writeln("マミさんは、マミられたようです");

    madoMagi.remove("saya");


    if("saya" !in madoMagi)                     // true
        writeln("さやかちゃんは魔女化したようです");
}

同値テスト(==, is)

2つの連想配列が等しい==とは、2つの連想配列のキーがすべて等しく、その対応する値がお互いに等しい場合にいいます。 また、2つの連想配列が全く同じ連想配列を指しているなら、a is btrueとなります。

auto aa1 = ["mado": 1, "homu": 2, "saya": 3, "anko": 4];
auto aa2 = ["mado": 1, "homu": 2, "saya": 3, "anko": 4];

writeln(aa1 == aa2);            // true
writeln(aa1 != aa2);            // true

aa1["mami"] = 5;
writeln(aa1 != aa2);            // true

aa1 = aa2;
writeln(aa1 is aa2);            // true

プロパティ

size_t aa.length

その連想配列が持つ要素の数を返します。

int[int] aa = [0:0, 1:1, 2:2];

writeln(aa.length);         // 3

V[K] aa.dup

配列に対するdup同様に、新しい連想配列にすべてコピーし、返します。

int[int] aa = [0:0, 1:1, 2:2];
auto aa2 = aa;

aa2[0] = 12;
writeln(aa);                // 12
                            // aa2を書き換えると、aa3も書き換わってしまう

aa2 = aa.dup;

aa2[0] = 13;
writeln(aa[0]);             // 12
                            // aa2を書き換えても、aaには影響はない

V aa.get(K key, lazy V defValue)

aakeyの要素を返します。 aa[key]とは違い、もしkeyaaに無ければdefValueを返します。 また、返されるのは右辺値なので、その値を通しての書き換えは不可能です。 defValueは、keyaaにない場合にのみ評価されます。 (lazyは遅延評価を表し、式の評価を遅らせることを意味します。)

int[int] aa = [0:0, 1:1, 2:2];

writeln(aa.get(0, -1));         // 0

writeln(aa.get(10, -1));        // -1

K[] aa.keys

連想配列が持つ、キーすべてをスライスにして返します。 キーの並び順は予測不能です。

auto madoMagi = ["mado": 1, "homu": 2,
                 "saya": 3, "anko": 4];

writeln(madoMagi.keys);
    // ["homu", "saya", "mado", "anko"]
    // 実際に必ずこのような順番になるかはわからない

V[] aa.values

連想配列が持つ値すべてをスライスにして返します。 .keys同様に、並び順は予測不能です。

auto madoMagi = ["mado": 1, "homu": 2,
                 "saya": 3, "anko": 4];

writeln(madoMagi.values);
    // [2, 3, 1, 4]
    // 実際に必ずこのような順番になるかはわからない

auto aa.byKey

連想配列が持つキーをすべて、レンジ(Input Range)にして返します。 もちろん、並び順は予測不能です。

auto madoMagi = ["mado": 1, "homu": 2,
                 "saya": 3, "anko": 4];

auto keyRng = madoMagi.byKey;
//keyRng.front = "majo";        // .frontは左辺値を返すので経由で書き換え可能だが、
                                // 危険なので書き換えてはいけない。

writeln(keyRng);                // ["homu", "saya", "mado", "anko"]

auto aa.byValue

連想配列が持つキーをすべて、レンジ(Input Range)にして返します。 何度もいいますが、並び順は予測不能です。

auto madoMagi = ["mado": 1, "homu": 2,
                 "saya": 3, "anko": 4];

writeln(madoMagi.byValue);      // [2, 3, 1, 4]
    // ["homu", "saya", "mado", "anko"]
    // 実際に必ずこのような順番になるかはわからない

auto valueRng = madoMagi.byValue;
valueRng.front = 100;

valueRng.popFront();
valueRng.front = 100;           // これは、.byKeysとは違いOK

writeln(madoMagi);              // ["homu":100, "saya":100, "mado":1, "anko":4]

V[K] aa.rehash()

詳しくは「ハッシュ」の節で説明しますが、連想配列の各要素に高速にアクセス可能なようにします。

auto madoMagi = ["mado": 1, "homu": 2,
                 "saya": 3, "anko": 4];

writeln(madoMagi);  // ["homu":2, "saya":3, "mado":1, "anko":4]

madoMagi.rehash();

writeln(madoMagi);  // ["homu":2, "saya":3, "anko":4, "mado":1]
                    // 最適化されたので、並び順が上と異なっている!

foreach

連想配列は、さまざまな方法を使ってforeachで回すことができます。

ベーシックな方法

もっとも基本的な方法は、foreach(key, value; aa)とすることです。 valueの方はrefをつけて参照(書き換え可能)にできますが、keyrefにすると危険なので、できません。

auto madoMagi = ["mado": 1, "homu": 2,
                 "saya": 3, "anko": 4, "mami": 5];

foreach(k, v; madoMagi)
    writefln("%s : %s", k, v);

writeln();

foreach(k, ref v; madoMagi)
    v = 100;

writefln("%-(%s : %s%|\n%)", madoMagi);

/* 実行結果
homu : 2
saya : 3
mado : 1
anko : 4
mami : 5

homu : 100
saya : 100
mado : 100
anko : 100
mami : 100
*/

aa.keysを使った方法

aa.keysはキーのスライスを返すので、そのスライスをforeachでたどれば良いのです。 ただし、新たに領域が確保されてしまいます。 先ほどの例と同じ動作をするものを.keysで書くと、以下のようになります。

auto madoMagi = ["mado": 1, "homu": 2,
                 "saya": 3, "anko": 4, "mami": 5];

foreach(k; madoMagi.keys)
    writefln("%s : %s", k, madoMagi[k]);

writeln();

foreach(k; madoMagi.keys)
    madoMagi[k] = 100;

writefln("%-(%s : %s%|\n%)", madoMagi);

aa.byKeyを使った場合

aa.byKeyは、キーを要素とするレンジなので、.keys同様に使えますが、新たな領域が確保されません。

auto madoMagi = ["mado": 1, "homu": 2,
                 "saya": 3, "anko": 4, "mami": 5];

foreach(k; madoMagi.byKey)
    writefln("%s : %s", k, madoMagi[k]);

writeln();

foreach(k; madoMagi.byKey)
    madoMagi[k] = 100;

writefln("%-(%s : %s%|\n%)", madoMagi);

aa.valuesを使った場合

もしキーの値が要らないのであれば、.valuesを使うことで値だけイテレートできます。 .keys同様に、新しく領域が確保されます。

auto madoMagi = ["mado": 1, "homu": 2,
                 "saya": 3, "anko": 4, "mami": 5];

foreach(v; madoMagi.values)
    writeln(v);

aa.byValue()を使った場合

.values同様に値のみでイテレートできますが、.byValue経由だと値の変更ができ、レンジなので新しく領域が確保されません。

auto madoMagi = ["mado": 1, "homu": 2,
                 "saya": 3, "anko": 4, "mami": 5];

foreach(v; madoMagi.byValue)
    writeln(v);

writeln();

foreach(ref v; madoMagi.byValue)
    v = 100;

writefln("%-(%s : %s%|\n%)", madoMagi);

クラスをキーとして使うには(高度)

連想配列のキーとしてクラスを使うには、クラスに次のメソッドを定義する必要があります。 hash_tsize_taliasです。

hash_t toHash()
bool opEquals(Object)
int opCmp(Object)

構造体や共用体については、これらはデフォルトではバイナリから算出されます。 しかし、これらをプログラマが定義すると、プログラマ定義の方式でハッシュ, 比較されます。

問題

  • 入力として、スペース区切りの文字列が与えられる。たとえば以下のように。
foge fuga foo bar bar bar fuga foo

これらの

おわりに

キーワード

  • 連想配列(Associative Array)
  • キー(Key)
  • 値(Value)
  • in
  • .length
  • .dup
  • .get(K key, lazy V defValue)
  • .keys
  • .values
  • .byKey
  • .byValue
  • ハッシュ(Hash)

仕様

英語 日本語