• Introduction
• Lexical
• Interpolation Expression Sequence
• Grammar
• Modules
• Declarations
• Types
• Properties
• Attributes
• Pragmas
• Expressions
• Statements
• Arrays
• Associative Arrays
• Structs and Unions
• Classes
• Interfaces
• Enums
• Type Qualifiers
• Functions
• Operator Overloading
• Templates
• Template Mixins
• Contract Programming
• Conditional Compilation
• Traits
• Error Handling
• Unit Tests
• Garbage Collection
• Floating Point
• D x86 Inline Assembler
• Embedded Documentation
• Interfacing to C
• Interfacing to C++
• Interfacing to Objective-C
• Portability Guide
• Named Character Entities
• Memory Safety
• Application Binary Interface
• Vector Extensions
• Better C
• ImportC
• Live Functions
• Windows Programming
• Glossary
• Legacy Code
• Editions

Associative Arrays

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

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

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 3int value = aa["hello"];// lookup value from a keyassert(value == 3);

Neither theKeyTypes nor the element types of an associative array can be function types orvoid.

Literals

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

SeeAssociative 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 givenkey does not exist and returnsfalse. If the givenkey does exist, it removes it from the AA and returnstrue.

All keys can be removed by using the methodclear.

Testing Membership

TheInExpression yields a pointer to the value if the key is in the associative array, ornull if not:

int* p;p ="hello"in aa;if (p !isnull){    *p = 4;// update value associated with keyassert(aa["hello"] == 4);}

Using Classes as the KeyType

Classes can be used as theKeyType. The behavior is controlled by the following member functions of classObject:

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

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

For example:

class Foo{int a, b;override size_ttoHash() {return a + b; }overrideboolopEquals(Object o)    {        Foo foo =cast(Foo) o;return foo && a == foo.a && b == foo.b;    }}

Using Structs or Unions as the KeyType

If theKeyType 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_ttoHash()const @safepurenothrow;boolopEquals(refconsttypeof(this) s)const @safepurenothrow;

For example:

import std.string;struct MyString{    string str;    size_ttoHash()const @safepurenothrow    {        size_t hash;foreach (char c; str)            hash = (hash * 9) + c;return hash;    }boolopEquals(refconst MyString s)const @safepurenothrow    {return std.string.cmp(this.str, s.str) == 0;    }}

The functions can use@trusted instead of@safe.

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;//s = aa[1];        // throws RangeError in runtimeaa[1] ="hello";// handled for setting AA entrys = aa[1];// succeeds to lookupassert(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);// 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);

If the assigned value type isnot 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;// is rewritten to: aa[1].opAssign(10), and// throws RangeError before opAssign is called

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

import std.bigint;BigInt[string] aa;aa["a"] = 10;// construct BigInt(10) and move it in AAaa["a"] = 20;// call aa["a"].opAssign(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. Therequire operation avoids the need to perform multiple key lookups.

class C{}C[string] aa;auto a = aa.require("a",new C);// lookup "a", construct if not present

Sometimes it is necessary to know whether the value was constructed or already exists. Therequire 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;returnnew C;}());assert(constructed ==true);C newc;auto b = aa.require("b", { newc =new C;return newc;}());assert(bis newc);

Advanced updating

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

int[string] aa;aa["a"] = 3;// set value associated with key "a" to 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 thecreator or update an existing value via theupdater. Theupdate operation avoids the need to perform multiple key lookups.

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

For details, seeupdate.

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 andassumeUnique:

immutablelong[string] aa;sharedstaticthis(){import std.exception : assumeUnique;import std.conv : to;long[string] temp;// mutable bufferforeach (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

An Associative Array defaults tonull, and is constructed upon assigning the first key/value pair. However, once constructed, an associative array hasreference 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;// defaults to nullint[int] aa2 = aa;// copies the null referenceassert(aaisnull);aa[1] = 1;assert(aa2.length == 0);// aa2 still is nullaa2 = aa;aa2[2] = 2;assert(aa[2] == 2);// now both refer to the same instance

ANewExpression allows constructing an associative array instance immediately, rather than wheninserting a key.

int[string] a =newint[string];auto b = a;// a and b point to the same AA instanceassert(b !isnull);a["1"] = 1;assert(b["1"] == 1);

Properties and Operations

Iteration Operations

The order of keys and values returned bykeys() andvalues() as well asbyKey(),byValue(), andbyKeyValue() is unspecified, but is guaranteed to be consistent as long as the associative array has not been reorganized, e.g. by adding or removing keys between the calls. Associating a new value to an existing key does not reorganize an associative array. Reorganizing an associative array invalidates any input ranges returned bybyKey(),byValue(), andbyKeyValue().

Key Lookup Operations

Theupdate operation works with anycreator andupdater that is invokable as specified.updater can modify the value in-place if it binds its argument by reference.

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 = wordin dictionary)                *count += 1;else                dictionary[word.idup] = 1;        }        lineCount += 1;    }    writeln("   lines   words   bytes");    writefln("%8s%8s%8s", lineCount, wordCount, charCount);constchar[37] hr = '-';    writeln(hr);foreach (word; sort(dictionary.keys))    {        writefln("%3s %s", dictionary[word], word);    }}

Seewc 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;// avoids UTF-8 auto-decodingint[string] aa;// The string `arr` has a limited alphabet: {A, C, G, T}// Thus, for better performance, iteration can be done _without_ decodingauto 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 Arrayforeach (key, value; aa){    writefln("key: %s, value: %d", key, value);}

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