D Programming Language 1.0

>
- Forum
- Wiki
- Search
- Downloads
- Home

Last update Tue Nov 9 13:50:07 2010

# 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 the key, and its type is called the KeyType.

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

    int[char[]] b;		// associative array b of ints that are
    			// indexed by an array of characters.
    			// The KeyType is char[]
    b["hello"] = 3;		// set value associated with key "hello" to 3
    func(b["hello"]);	// pass 3 as parameter to func()

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

    b.remove("hello");

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 b);
    if (p != null)
    	...

KeyTypes cannot be functions or voids.

The element types of an associative array cannot be functions or voids.

### 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`:

- `hash_t toHash()`
- `int opEquals(Object)`
- `int opCmp(Object)`

`hash_t` is an alias to an integral type.

Note that the parameter to `opCmp` and `opEquals` is of type `Object`, not the type of the class in which it is defined.

For example:

    class Foo
    {
        int a, b;

        hash_t toHash() { return a + b; }

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

        int opCmp(Object o)
        {	Foo f = cast(Foo) o;
    	if (!f)
    	    return -1;
    	if (a == foo.a)
    	    return b - foo.b;
    	return a - foo.a;
        }
    }

The implementation may use either `opEquals` or `opCmp` or both. Care should be taken so that the results of `opEquals` and `opCmp` are consistent with each other when the class objects are the same or not.

### 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 binary data within the struct value. A custom mechanism can be used by providing the following functions as struct members:

     hash_t toHash();
    int opEquals(KeyType* s);
    int opCmp(KeyType* s);

For example:

    import std.string;

    struct MyString
    {
        string str;

        hash_t toHash()
        {   hash_t hash;
    	foreach (char c; s)
    	    hash = (hash * 9) + c;
    	return hash;
        }

        bool opEquals(MyString* s)
        {
    	return std.string.cmp(this.str, s.str) == 0;
        }

        int opCmp(MyString* s)
        {
    	return std.string.cmp(this.str, s.str);
        }

    }

The implementation may use either `opEquals` or `opCmp` or both. Care should be taken so that the results of `opEquals` and `opCmp` are consistent with each other when the struct/union objects are the same or not.

### Properties

Properties for associative arrays are:

Associative Array Properties
Property | Description
--- | ---
.sizeof | Returns the size of the reference to the associative array; it is typically 8.
.length | Returns number of values in the associative array. Unlike for dynamic arrays, it is read-only.
.keys | Returns dynamic array, the elements of which are the keys in the associative array.
.values | Returns dynamic array, the elements of which are the values in the associative array.
.rehash | Reorganizes the associative array in place so that lookups are more efficient. rehash is effective when, for example, the program is done loading up a symbol table and now needs fast lookups in it. Returns a reference to the reorganized array.

### Associative Array Example: word count

    import std.file;         // D file I/O
    import std.stdio;

    int main (string[] args)
    {
        int word_total;
        int line_total;
        int char_total;
        int[char[]] dictionary;

        writefln("   lines   words   bytes file");
        for (int i = 1; i < args.length; ++i)      // program arguments
        {
    	char[] input;            // input buffer
    	int w_cnt, l_cnt, c_cnt; // word, line, char counts
    	int inword;
    	int wstart;

    	// read file into input[]
    	input = cast(char[])std.file.read(args[i]);

    	foreach (j, char c; input)
    	{
    	    if (c == '\n')
    		    ++l_cnt;
    	    if (c >= '0' && c <= '9')
    	    {
    	    }
    	    else if (c >= 'a' && c <= 'z' ||
    		    c >= 'A' && c <= 'Z')
    	    {
    		if (!inword)
    		{
    		    wstart = j;
    		    inword = 1;
    		    ++w_cnt;
    		}
    	    }
    	    else if (inword)
    	    {
    		char[] word = input[wstart .. j];
    		dictionary[word]++;        // increment count for word
    		inword = 0;
    	    }
    	    ++c_cnt;
    	}
    	if (inword)
    	{
    	    char[] word = input[wstart .. input.length];
    	    dictionary[word]++;
    	}
    	writefln("%8d%8d%8d %s", l_cnt, w_cnt, c_cnt, args[i]);
    	line_total += l_cnt;
    	word_total += w_cnt;
    	char_total += c_cnt;
        }

        if (args.length > 2)
        {
    	writef("-------------------------------------\n%8d%8d%8d total",
    		line_total, word_total, char_total);
        }

        writefln("-------------------------------------");
        foreach (word; dictionary.keys.sort)
        {
    	writefln("%3d %s", dictionary[word], word);
        }
        return 0;
    }

Forums | Comments | D | Search | Downloads | Home
Copyright © 1999-2010 by Digital Mars ®, All Rights Reserved | Page generated by Ddoc.