hash-map.dd

Ddoc

$(SPEC_S Associative Arrays,

        $(P 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 $(I key), and its type is called the $(I KeyType).
        )

        $(P Associative arrays are declared by placing the $(I KeyType)
        within the [ ] of an array declaration:
        )

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

        $(P Particular keys in an associative array can be removed with the
        remove function:
        )

---------
b.$(CODE_HIGHLIGHT remove)("hello");
---------

        $(P The $(I InExpression) yields a pointer to the value
        if the key is in the associative array, or $(D null) if not:
        )

---------
int* p;
p = ("hello" $(CODE_HIGHLIGHT in) b);
if (p !is (B null))
        ...
---------

        $(P $(I KeyType)s cannot be functions or voids.
        )

        $(P The element types of an associative array cannot be functions or voids.)

$(H3 Using Classes as the KeyType)

        $(P Classes can be used as the $(I KeyType). For this to work,
        the class definition must override the following member functions
        of class $(D Object):)

        $(UL
        $(LI $(D hash_t toHash()))

   $(LI $(D bool opEquals(Object)))
        $(LI $(D int opCmp(Object)))
        )

        $(P $(D hash_t) is an alias to an integral type.)

        $(P Note that the parameter to $(D opCmp) and $(D opEquals) is
        of type
        $(D Object), not the type of the class in which it is defined.)

        $(P For example:)

---
class Foo {
  int a, b;

  hash_t $(CODE_HIGHLIGHT toHash)() { return a + b; }

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

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

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

$(H3 Using Structs or Unions as the KeyType)

        $(P If the $(I 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:
        )

---------
const hash_t $(CODE_HIGHLIGHT opHash)();
const bool $(CODE_HIGHLIGHT opEquals)(ref const KeyType s);
const int $(CODE_HIGHLIGHT opCmp)(ref const KeyType s);
---------

        $(P For example:)

---------
import std.string;

struct MyString {
  string str;

  const hash_t $(CODE_HIGHLIGHT toHash)()
  { hash_t hash;
    foreach (char c; str)
      hash = (hash * 9) + c;
    return hash;
  }

  const bool $(CODE_HIGHLIGHT opEquals)(ref const MyString s)
  {
    return std.string.cmp(this.str, s.str) == 0;
  }

  const int $(CODE_HIGHLIGHT opCmp)(ref const MyString s)
  {
    return std.string.cmp(this.str, s.str);
  }
}
---------

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

$(H3 Runtime Initialization of Immutable AAs)

    $(P 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 $(D assumeUnique):)
---------
immutable long[string] aa;

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

unittest
{
    assert(aa["1"] == 1);
    assert(aa["5"] == 5);
    assert(aa["9"] == 9);
}
---------


$(H3 Properties)

Properties for associative arrays are:

    $(TABLE_2COLS Associative Array Properties,
        $(THEAD Property, Description)
        $(TROW $(D .sizeof), Returns the size of the reference to the associative
        array; it is 4 in 32-bit builds and 8 on 64-bit builds.)
        $(TROW $(D .length), $(ARGS Returns number of values in the
        associative array. Unlike for dynamic arrays, it is read-only.))
        $(TROW $(D .dup), Create a new associative array of the same size
        and copy the contents of the associative array into it.)
        $(TROW $(D .keys), $(ARGS Returns dynamic array, the elements of which are the keys in
        the associative array.))
        $(TROW $(D .values), $(ARGS Returns dynamic array, the elements of which are the values in
        the associative array.))
        $(TROW $(D .rehash), $(ARGS Reorganizes the associative array in place so that lookups
        are more efficient. $(D 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.))
        $(TROW $(D .byKey()), $(ARGS Returns a delegate suitable for use as an $(I Aggregate) to
        a $(GLINK2 statement, ForeachStatement)  which will iterate over the keys
        of the associative array.))
        $(TROW $(D .byValue()), $(ARGS Returns a delegate suitable for use as an $(I Aggregate) to
        a $(GLINK2 statement, ForeachStatement)  which will iterate over the values
        of the associative array.))
        $(TROW $(D .get(Key key, lazy Value defVal)),
        $(ARGS Looks up $(D key); if it exists returns corresponding value
        else evaluates and returns $(D defVal).))
    )

$(HR)
$(H3 Associative Array Example: word count)

        $(P Let's consider the file is ASCII encoded with LF EOL.
        In general case we should use $(I dchar c) for iteration
        over code points and functions from $(LINK2 phobos/std_uni.html,std.uni).
        )

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

void main (string[] args) {
  ulong totalWords, totalLines, totalChars;
  ulong[string] dictionary;

  writefln("   lines   words   bytes file");
  foreach (arg; args[1 .. $]) // for each argument except the first one
  {
    ulong wordCount, lineCount, charCount;

    foreach(line; File(arg).byLine())
    {
      bool inWord;
      size_t wordStart;

      void tryFinishWord(size_t wordEnd)
      {
        if (inWord)
        {
          auto word = line[wordStart .. wordEnd];
          ++dictionary[word.idup];   // increment count for word
          inWord = false;
        }
      }

      foreach (i, char c; line)
      {
        if (std.ascii.isDigit(c))
        { // c is a digit (0..9)
        }
        else if (std.ascii.isAlpha(c))
        { // c is an ASCII letter (A..Z, a..z)
          if (!inWord)
          {
            wordStart = i;
            inWord = true;
            ++wordCount;
          }
        }
        else
          tryFinishWord(i);
        ++charCount;
      }
      tryFinishWord(line.length);
      ++lineCount;
    }

    writefln("%8s%8s%8s %s", lineCount, wordCount, charCount, arg);
    totalWords += wordCount;
    totalLines += lineCount;
    totalChars += charCount;
  }

  if (args.length > 2)
  {
    writefln("-------------------------------------\n%8s%8s%8s total",
            totalLines, totalWords, totalChars);
  }

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

)

Macros:
        TITLE=Associative Arrays
        WIKI=AssociativeArrays
        CATEGORY_SPEC=$0