Associative Arrays - D Programming Language (original) (raw)

Contents

1. Literals
2. Removing Keys
3. Testing Membership
4. Using Classes as the KeyType
5. Using Structs or Unions as the KeyType
6. Construction or Assignment on Setting AA Entries
7. Inserting if not present
8. Advanced updating
9. Runtime Initialization of Immutable AAs
10. Construction and Reference Semantics
11. Properties
12. Examples
13. Associative Array Example: word count
14. Associative Array Example: counting pairs

Associative arrays have an index that is not necessarily an integer, and can be sparsely populated. The index for an associative array is called the key, and its type is called the KeyType.

Associative arrays are declared by placing the KeyType within the [ ] of an array declaration:

int[string] aa; aa["hello"] = 3; int value = aa["hello"]; assert(value == 3);

Neither the _KeyType_s nor the element types of an associative array can be function types or void.

Implementation Defined: The built-in associative arrays do not preserve the order of the keys inserted into the array. In particular, in a foreach loop the order in which the elements are iterated is typically unspecified.

Literals

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

See Associative Array Literals.

Removing Keys

Particular keys in an associative array can be removed with theremove function:

aa.remove("hello");

remove(key) does nothing if the given key does not exist and returns false. If the given key does exist, it removes it from the AA and returns true.

All keys can be removed by using the method clear.

Testing Membership

The InExpression yields a pointer to the value if the key is in the associative array, or null if not:

int* p;

p = "hello" in aa; if (p !is null) { *p = 4; assert(aa["hello"] == 4); }

Undefined Behavior: Adjusting the pointer to point before or after the element whose address is returned, and then dereferencing it.

Using Classes as the KeyType

Classes can be used as the KeyType. For this to work, the class definition must override the following member functions of class Object:

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

Note that the parameter to opEquals is of typeObject, not the type of the class in which it is defined.

For example:

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;
}

}

Implementation Defined: opCmp is not used to check for equality by the associative array. However, since the actual opEquals oropCmp called is not decided until runtime, the compiler cannot always detect mismatched functions. Because of legacy issues, the compiler may reject an associative array key type that overrides opCmp but notopEquals. This restriction may be removed in future versions.

Undefined Behavior:

1. If toHash must consistently be the same value when opEquals returns true. In other words, two objects that are considered equal should always have the same hash value. Otherwise, undefined behavior will result.

Best Practices:

1. Use the attributes @safe, @nogc, pure, const, and scope as much as possible on the toHash and opEquals overrides.

Using Structs or Unions as the KeyType

If the KeyType is a struct or union type, a default mechanism is used to compute the hash and comparisons of it based on the fields of the struct value. A custom mechanism can be used by providing the following functions as struct members:

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

For example:

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;
}

}

The functions can use @trusted instead of @safe.

Implementation Defined: opCmp is not used to check for equality by the associative array. For this reason, and for legacy reasons, an associative array key is not allowed to define a specialized opCmp, but omit a specialized opEquals. This restriction may be removed in future versions of D.

Undefined Behavior:

1. If toHash must consistently be the same value when opEquals returns true. In other words, two structs that are considered equal should always have the same hash value. Otherwise, undefined behavior will result.

Best Practices:

1. Use the attributes @nogc as much as possible on the toHash and opEquals overrides.

Construction or Assignment on Setting AA Entries

When an AA indexing access appears on the left side of an assignment operator, it is specially handled for setting an AA entry associated with the key.

string[int] aa; string s;

aa[1] = "hello"; s = aa[1]; assert(s == "hello");

If the assigned value type is equivalent with the AA element type:

1. If the indexing key does not yet exist in AA, a new AA entry will be allocated, and it will be initialized with the assigned value.
2. If the indexing key already exists in the AA, the setting runs normal assignment.

struct S { int val; void opAssign(S rhs) { this.val = rhs.val * 2; } } S[int] aa; aa[1] = S(10); assert(aa[1].val == 10); aa[1] = S(10); assert(aa[1].val == 20);

If the assigned value type is not equivalent with the AA element type, the expression could invoke operator overloading with normal indexing access:

struct S { int val; void opAssign(int v) { this.val = v * 2; } } S[int] aa; aa[1] = 10;

However, if the AA element type is a struct which supports an implicit constructor call from the assigned value, implicit construction is used for setting the AA entry:

struct S { int val; this(int v) { this.val = v; } void opAssign(int v) { this.val = v * 2; } } S s = 1; s = 1;
S[int] aa; aa[1] = 10; assert(aa[1].val == 10); aa[1] = 10; assert(aa[1].val == 20);

This is designed for efficient memory reuse with some value-semantics structs, eg. std.bigint.BigInt.

import std.bigint; BigInt[string] aa; aa["a"] = 10; aa["a"] = 20;

Inserting if not present

When AA access requires that there must be a value corresponding to the key, a value must be constructed and inserted if not present. Therequire function provides a means to construct a new value via a lazy argument. The lazy argument is evaluated when the key is not present. The require operation avoids the need to perform multiple key lookups.

class C{} C[string] aa;

auto a = aa.require("a", new C);

Sometimes it is necessary to know whether the value was constructed or already exists. The require function doesn't provide a boolean parameter to indicate whether the value was constructed but instead allows the construction via a function or delegate. This allows the use of any mechanism as demonstrated below.

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

Typically updating a value in an associative array is simply done with an assign statement.

int[string] aa;

aa["a"] = 3;

Sometimes it is necessary to perform different operations depending on whether a value already exists or needs to be constructed. Theupdate function provides a means to construct a new value via thecreate delegate or update an existing value via the update delegate. The update operation avoids the need to perform multiple key lookups.

int[string] aa;

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

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

For details, see update.

Runtime Initialization of Immutable AAs

Immutable associative arrays are often desirable, but sometimes initialization must be done at runtime. This can be achieved with a constructor (static constructor depending on scope), a buffer associative array and assumeUnique:

immutable long[string] aa;

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

long[string] temp;     foreach (i; 0 .. 10)
{
    temp[to!string(i)] = i;
}
temp.rehash; 
aa = assumeUnique(temp);

}

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

Construction and Reference Semantics

An Associative Array defaults to null, and is constructed upon assigning the first key/value pair. However, once constructed, an associative array has reference semantics, meaning that assigning one array to another does not copy the data. This is especially important when attempting to create multiple references to the same array.

int[int] aa; int[int] aa2 = aa;
assert(aa is null); aa[1] = 1; assert(aa2.length == 0); aa2 = aa; aa2[2] = 2; assert(aa[2] == 2);

A NewExpression allows constructing an associative array instance immediately, rather than when inserting a key.

int[string] a = new int[string]; auto b = a; assert(b !is null); a["1"] = 1; assert(b["1"] == 1);

Properties

Properties for associative arrays are:

Associative Array Properties

Examples

Associative Array Example: word count

too many cooks too many ingredients

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);
}

}

See wc for the full version.

Associative Array Example: counting pairs

An Associative Array can be iterated in key/value fashion using aforeach statement. As an example, the number of occurrences of all possible substrings of length 2 (aka 2-mers) in a string will be counted:

import std.range : slide; import std.stdio : writefln; import std.utf : byCodeUnit; int[string] aa;

auto arr = "AGATAGA".byCodeUnit;

foreach (window; arr.slide(2)) aa[window.source]++; 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

Copyright © 1999-2025 by the D Language Foundation | Page generated byDdoc on Sat May 3 22:41:58 2025