연관 배열

연관 배열 (Associative Arrays)

연관 배열(associative array, AA)은 반드시 정수일 필요가 없는 인덱스를 가지며 드물게 채워질 수 있는 배열이에요. 인덱스를 키(key)라고 하고, 그 타입을 KeyType이라고 해요. 삽입·삭제·멤버십 테스트, 키 타입으로 클래스·struct 사용, 속성과 반복 연산을 다루는 페이지예요.

출처: Associative Arrays

본문

연관 배열은 반드시 정수일 필요가 없는 인덱스를 가지며, 드물게 채워질 수 있어요. 연관 배열의 인덱스를 키(key)라고 하고, 그 타입을 KeyType이라고 해요.

연관 배열은 배열 선언의 [ ] 안에 KeyType을 넣어 선언해요:

int[string] aa;   // Associative array of ints that are
                  // indexed by string keys.
                  // The KeyType is string.
aa["hello"] = 3;  // set value associated with key "hello" to 3
int value = aa["hello"];  // lookup value from a key
assert(value == 3);

연관 배열의 KeyType이나 요소 타입은 함수 타입이나 void일 수 없어요.

구현 정의(Implementation Defined): 내장 연관 배열은 배열에 삽입된 키들의 순서를 보존하지 않아요. 특히 foreach 루프에서 요소들이 반복되는 순서는 보통 지정되지 않아요.

Literals

auto aa = [21u: "he", 38: "ho", 2: "hi"];
static assert(is(typeof(aa) == string[uint]));
assert(aa[2] == "hi");

참고: Associative Array Literals.

Removing Keys

연관 배열의 특정 키는 remove 함수로 제거할 수 있어요:

aa.remove("hello");

remove(key)는 주어진 키가 존재하지 않으면 아무것도 하지 않고 false를 반환해요. 주어진 키가 존재하면 AA에서 제거하고 true를 반환해요.

모든 키는 clear 메서드로 제거할 수 있어요.

Testing Membership

InExpression은 키가 연관 배열에 있으면 그 값에 대한 포인터를, 없으면 null을 산출해요:

int* p;

p = "hello" in aa;
if (p !is null)
{
    *p = 4;  // update value associated with key
    assert(aa["hello"] == 4);
}

정의되지 않은 동작(Undefined Behavior): 주소가 반환된 요소의 앞이나 뒤를 가리키도록 포인터를 조정한 다음 역참조하는 것.

Using Classes as the KeyType

클래스는 KeyType으로 사용할 수 있어요. 동작은 class Object의 다음 멤버 함수들이 제어해요:

• size_t toHash() @trusted nothrow
• bool opEquals(Object)

opEquals의 매개변수는 정의된 클래스의 타입이 아니라 Object 타입이라는 점에 주의하세요.

예를 들어:

class Foo
{
    int a, b;

    override size_t toHash() { return a + b; }

    override bool opEquals(Object o)
    {
        Foo foo = cast(Foo) o;
        return foo && a == foo.a && b == foo.b;
    }
}

opEquals의 기본 구현은 비교에 인스턴스의 주소를 사용하고, toHash의 기본 구현은 인스턴스의 주소를 해시해요.

구현 정의: opCmp는 연관 배열이 동등성을 확인하는 데 사용하지 않아요. 그러나 실제로 호출되는 opEquals 또는 opCmp는 런타임까지 결정되지 않으므로 컴파일러가 항상 불일치 함수를 감지할 수는 없어요. 레거시 문제 때문에 컴파일러는 opCmp는 오버라이드하지만 opEquals는 오버라이드하지 않는 연관 배열 키 타입을 거부할 수 있어요. 이 제한은 향후 버전에서 제거될 수 있어요.

정의되지 않은 동작: opEquals가 true를 반환할 때 toHash는 항상 같은 값이어야 해요. 다시 말해, 동등하다고 간주되는 두 객체는 항상 같은 해시 값을 가져야 해요. 그렇지 않으면 정의되지 않은 동작이 발생해요.

모범 사례: toHash와 opEquals 오버라이드에 @safe, @nogc, pure, const, scope 속성을 가능한 한 많이 사용하세요.

Using Structs or Unions as the KeyType

KeyType이 struct 또는 union 타입이면, struct 값의 필드에 기반한 해시와 비교를 계산하는 기본 메커니즘이 사용돼요. 다음 함수들을 struct 멤버로 제공하면 사용자 정의 메커니즘을 쓸 수 있어요:

size_t toHash() const @safe pure nothrow;
bool opEquals(ref const typeof(this) s) const @safe pure nothrow;

예를 들어:

import std.string;

struct MyString
{
    string str;

    size_t toHash() const @safe pure nothrow
    {
        size_t hash;
        foreach (char c; str)
            hash = (hash * 9) + c;
        return hash;
    }

    bool opEquals(ref const MyString s) const @safe pure nothrow
    {
        return std.string.cmp(this.str, s.str) == 0;
    }
}

함수들은 @safe 대신 @trusted를 쓸 수 있어요.

구현 정의: opCmp는 연관 배열이 동등성을 확인하는 데 사용하지 않아요. 이런 이유와 레거시 이유로, 연관 배열 키는 특수화된 opCmp를 정의하면서 특수화된 opEquals는 생략할 수 없어요. 이 제한은 향후 D 버전에서 제거될 수 있어요.

정의되지 않은 동작: opEquals가 true를 반환할 때 toHash는 항상 같은 값이어야 해요. 다시 말해, 동등하다고 간주되는 두 struct는 항상 같은 해시 값을 가져야 해요. 그렇지 않으면 정의되지 않은 동작이 발생해요.

모범 사례: toHash와 opEquals 오버라이드에 @nogc 속성을 가능한 한 많이 사용하세요.

Construction or Assignment on Setting AA Entries

AA 인덱싱 접근이 할당 연산자의 왼쪽에 나타나면, 키와 연관된 AA 항목을 설정하기 위한 것으로 특별히 처리돼요.

string[int] aa;
string s;

//s = aa[1];        // throws RangeError in runtime
aa[1] = "hello";    // handled for setting AA entry
s = aa[1];          // succeeds to lookup
assert(s == "hello");

할당된 값 타입이 AA 요소 타입과 동등하면:

• 인덱싱 키가 아직 AA에 없으면 새 AA 항목이 할당되고 할당된 값으로 초기화돼요.
• 인덱싱 키가 이미 AA에 있으면 설정은 일반 할당을 실행해요.

struct S
{
    int val;
    void opAssign(S rhs) { this.val = rhs.val * 2; }
}
S[int] aa;
aa[1] = S(10);  // first setting initializes the entry aa[1]
assert(aa[1].val == 10);
aa[1] = S(10);  // second setting invokes normal assignment, and
                // operator-overloading rewrites it to member opAssign function.
assert(aa[1].val == 20);

할당된 값 타입이 AA 요소 타입과 동등하지 않으면, 표현식은 일반 인덱싱 접근으로 연산자 오버로딩을 호출할 수 있어요:

struct S
{
    int val;
    void opAssign(int v) { this.val = v * 2; }
}
S[int] aa;
aa[1] = 10;     // is rewritten to: aa[1].opAssign(10), and
                // throws RangeError before opAssign is called

그러나 AA 요소 타입이 할당된 값에서 암시적 생성자 호출을 지원하는 struct라면, AA 항목 설정에 암시적 생성을 사용해요:

struct S
{
    int val;
    this(int v) { this.val = v; }
    void opAssign(int v) { this.val = v * 2; }
}
S s = 1;    // OK, rewritten to: S s = S(1);
s = 1;      // OK, rewritten to: s.opAssign(1);

S[int] aa;
aa[1] = 10; // first setting is rewritten to: aa[1] = S(10);
assert(aa[1].val == 10);
aa[1] = 10; // second setting is rewritten to: aa[1].opAssign(10);
assert(aa[1].val == 20);

이것은 값 의미론(value-semantics)의 일부 struct, 예컨대 std.bigint.BigInt에서 효율적인 메모리 재사용을 위해 설계된 것이에요.

import std.bigint;
BigInt[string] aa;
aa["a"] = 10;   // construct BigInt(10) and move it in AA
aa["a"] = 20;   // call aa["a"].opAssign(20)

Inserting if not present

AA 접근이 키에 대응하는 값이 반드시 있어야 한다고 요구할 때, 없으면 값을 생성하고 삽입해야 해요. require 함수는 지연(lazy) 인자를 통해 새 값을 생성하는 수단을 제공해요. 지연 인자는 키가 없을 때 평가돼요. require 연산은 여러 번의 키 조회를 수행할 필요를 피해줘요.

class C{}
C[string] aa;

auto a = aa.require("a", new C);   // lookup "a", construct if not present

때로는 값이 생성됐는지 이미 존재하는지 알아야 할 필요가 있어요. require 함수는 값이 생성됐는지를 나타내는 불리언 매개변수를 제공하지 않고, 대신 함수나 delegate를 통한 생성을 허용해요. 이를 통해 아래처럼 어떤 메커니즘이든 사용할 수 있어요.

class C{}
C[string] aa;

bool constructed;
auto a = aa.require("a", { constructed=true; return new C;}());
assert(constructed == true);

C newc;
auto b = aa.require("b", { newc = new C; return newc;}());
assert(b is newc);

Advanced updating

보통 연관 배열에서 값을 갱신하는 것은 간단히 할당 문으로 해요.

int[string] aa;

aa["a"] = 3;  // set value associated with key "a" to 3

때로는 값이 이미 존재하는지 생성해야 하는지에 따라 다른 연산을 수행해야 할 때가 있어요. update 함수는 creator를 통해 새 값을 생성하거나 updater를 통해 기존 값을 갱신하는 수단을 제공해요. update 연산은 여러 번의 키 조회를 수행할 필요를 피해줘요.

int[string] aa;

// create
aa.update("key",
    () => 1,
    (int) {} // not executed
    );
assert(aa["key"] == 1);

// update value by ref
aa.update("key",
    () => 0, // not executed
    (ref int v) {
        v += 1;
    });
assert(aa["key"] == 2);

자세한 내용은 update를 참고하세요.

Runtime Initialization of Immutable AAs

불변(immutable) 연관 배열은 종종 바람직하지만, 때로는 초기화를 런타임에 해야 할 때가 있어요. 이것은 생성자(스코프에 따라 정적 생성자), 버퍼 연관 배열과 assumeUnique로 달성할 수 있어요:

immutable long[string] aa;

shared static this()
{
    import std.exception : assumeUnique;
    import std.conv : to;

    long[string] temp; // mutable buffer
    foreach (i; 0 .. 10)
    {
        temp[to!string(i)] = i;
    }
    temp.rehash; // for faster lookups

    aa = assumeUnique(temp);
}

void main()
{
    assert(aa["1"] == 1);
    assert(aa["5"] == 5);
    assert(aa["9"] == 9);
}

Construction and Reference Semantics

연관 배열은 기본적으로 null이고, 첫 번째 키/값 쌍을 할당할 때 생성돼요. 그러나 일단 생성되면 연관 배열은 참조 의미론을 가져요. 즉, 한 배열을 다른 배열에 할당해도 데이터가 복사되지 않아요. 이것은 같은 배열에 대한 여러 참조를 만들려고 할 때 특히 중요해요.

int[int] aa;             // defaults to null
int[int] aa2 = aa;       // copies the null reference

assert(aa is null);
aa[1] = 1;
assert(aa2.length == 0); // aa2 still is null
aa2 = aa;
aa2[2] = 2;
assert(aa[2] == 2);      // now both refer to the same instance

NewExpression은 키를 삽입할 때가 아니라 즉시 연관 배열 인스턴스를 생성할 수 있게 해요.

int[string] a = new int[string];
auto b = a; // a and b point to the same AA instance

assert(b !is null);
a["1"] = 1;
assert(b["1"] == 1);

Properties and Operations

• dup
• rehash
• clear

Name	Description
sizeof	연관 배열에 대한 참조의 크기. 32비트 빌드에서는 4, 64비트 빌드에서는 8.
length	연관 배열의 값 개수. 동적 배열과 달리 읽기 전용.
	연관 배열이 null이면 null을 반환. 그렇지 않으면 연관 배열의 키와 값 사본으로 새로 할당된 연관 배열을 반환.
	연관 배열을 제자리에서 재편성해 조회가 더 효율적으로 되게 함. rehash를 호출하는 것은 예를 들어 프로그램이 심볼 테이블을 다 채우고 이제 그 안에서 빠른 조회가 필요할 때 효과적. 재편성된 배열에 대한 참조를 반환.
	연관 배열에서 모든 키와 값을 제거. 제거 후 배열은 재해시되지 않아 기존 저장소를 재사용할 수 있음. 이것은 같은 인스턴스에 대한 모든 참조에 영향을 주며, 현재 참조만 null로 설정하는 destroy(aa)와 동등하지 않음.

참고: 내장 empty 속성은 없어요. Phobos는 std.range.primitives에 empty의 구현을 제공해요.

Iteration Operations

• keys
• values
• byKey forward range
• byValue
• byKeyValue

Operation	Description
	연관 배열의 키 사본을 담은 새로 할당된 동적 배열을 반환. 순서는 values()와 일치하지만 그 외에는 지정되지 않음.
	연관 배열의 값 사본을 담은 새로 할당된 동적 배열을 반환. 순서는 keys()와 일치하지만 그 외에는 지정되지 않음.
	키를 참조로 열거하는 것을 반환. 순서는 byValue()와 일치하지만 그 외에는 지정되지 않음. 버그: 키가 변경 가능하게 제공되지만 변경은 정의되지 않은 동작.
	값을 참조로 열거하는 forward range를 반환. 순서는 byKey()와 일치하지만 그 외에는 지정되지 않음.
	키와 값 속성을 제공하는 불투명 객체를 열거하는 forward range를 반환. 이 속성들은 결과를 참조로 반환. 요소 순서는 지정되지 않음. 버그: 키가 변경 가능하게 제공되지만 변경은 정의되지 않은 동작.

keys()와 values()는 물론 byKey(), byValue(), byKeyValue()가 반환하는 키와 값의 순서는 지정되지 않지만, 연관 배열이 재편성되지 않는 한(예: 호출 사이에 키를 추가·제거함으로써) 일관성이 보장돼요. 기존 키에 새 값을 연관시키는 것은 연관 배열을 재편성하지 않아요. 연관 배열을 재편성하면 byKey(), byValue(), byKeyValue()가 반환한 모든 입력 범위가 무효화돼요.

모범 사례: keys()와 values()를 호출하면(연관 배열이 null이거나 비어 있지 않는 한) 할당이 발생해요. 키와/또는 값의 독립적 복사본이 필요하면 사용하고, 그렇지 않으면 byKey()와 byValue()를 고려하세요.

연관 배열은 값 반복과 키-값 반복을 위해 foreach를 직접 지원해요. 불필요한 복사를 피하려면 필요할 때 키와 값 변수에 ref를 사용하세요. 키만 반복하려면 키-값 반복을 사용하고 값은 무시하세요. 범위 알고리즘 같은 더 정교한 경우에는 byKey(), byValue(), byKeyValue()를 사용하세요.

Key Lookup Operations

• get
• require
• update

Operation	Description
Value (Key key, lazy Value defVal)	키가 존재하면 대응 값을 반환. 그렇지 않으면 defVal을 키와 연관시키지 않고 평가·반환.
ref Value (Key key, lazy Value value)	키가 존재하면 대응 값을 참조로 반환. 그렇지 않으면 value를 평가해 연관 배열에서 키와 연관시킨 뒤 새로 저장된 값을 참조로 반환.
void (Key key, Creator creator, Updater updater)	키가 존재하면 대응 값으로 updater를 호출. 값이 반환되면 그 값을 키와 연관시킴. 키를 찾지 못했으면 creator를 호출해 그 결과를 키와 연관시킴.

update 연산은 지정된 대로 호출 가능한 모든 creator와 updater와 함께 동작해요. updater는 인자를 참조로 바인딩하면 값을 제자리에서 수정할 수 있어요.

모범 사례: ref 매개변수를 가진 void 반환 updater는 불필요한 복사를 피해요.

Examples

Associative Array Example: word count

import std.algorithm;
import std.stdio;

void main()
{
    ulong[string] dictionary;
    ulong wordCount, lineCount, charCount;

    foreach (line; stdin.byLine(KeepTerminator.yes))
    {
        charCount += line.length;
        foreach (word; splitter(line))
        {
            wordCount += 1;
            if (auto count = word in dictionary)
                *count += 1;
            else
                dictionary[word.idup] = 1;
        }

        lineCount += 1;
    }

    writeln("   lines   words   bytes");
    writefln("%8s%8s%8s", lineCount, wordCount, charCount);

    const char[37] hr = '-';

    writeln(hr);
    foreach (word; sort(dictionary.keys))
    {
        writefln("%3s %s", dictionary[word], word);
    }
}

전체 버전은 wc를 참고하세요.

Associative Array Example: counting pairs

연관 배열은 foreach 문을 사용해 키/값 방식으로 반복할 수 있어요. 예를 들어 문자열에서 길이 2의 모든 가능한 부분 문자열(일명 2-mer)의 발생 횟수를 세어볼게요:

import std.range : slide;
import std.stdio : writefln;
import std.utf : byCodeUnit; // avoids UTF-8 auto-decoding

int[string] aa;

// The string `arr` has a limited alphabet: {A, C, G, T}
// Thus, for better performance, iteration can be done _without_ decoding
auto arr = "AGATAGA".byCodeUnit;

// iterate over all pairs in the string and count each pair
// ('A', 'G'), ('G', 'A'), ('A', 'T'), ...
foreach (window; arr.slide(2))
    aa[window.source]++; // source unwraps the code unit range

// iterate over all key/value pairs of the Associative Array
foreach (key, value; aa)
{
    writefln("key: %s, value: %d", key, value);
}

> rdmd count.d
key: AT, value: 1
key: GA, value: 2
key: TA, value: 1
key: AG, value: 2

더 알아보기

• 연관 배열 리터럴의 문법은 Expressions 문서를 참고하세요.
• AA 속성·연산의 상세 규약은 object 모듈에서 볼 수 있어요.
• foreach로 AA를 반복하는 방법은 Statements 문서를 참고하세요.
• dlang.org의 원문에서 최신 내용을 확인할 수 있어요.