Next Previous Contents

12. Associative Arrays

Assoc_Type

An associative array differs from an ordinary array in the sense that its size is not fixed and that it is indexed by a string, called the key. For example, consider:

       A = Assoc_Type [Int_Type];
       A["alpha"] = 1;
       A["beta"] = 2;
       A["gamma"] = 3;
Here, A has been assigned to an associative array of integers (Int_Type) and then three keys were been added to the array.

As the example suggests, an associative array may be created using one of the following forms:

Assoc_Type [type] Assoc_Type [type, default-value] Assoc_Type []
The last form returns an un-typed associative array capable of storing values of any type.

The form involving a default-value is useful for associating a default value with non-existent array members. This feature is explained in more detail below.

There are several functions that are specially designed to work with associative arrays. These include:

To illustrate the use of an associative array, consider the problem of counting the number of repeated occurrences of words in a list. Let the word list be represented as an array of strings given by word_list. The number of occurrences of each word may be stored in an associative array as follows:

     a = Assoc_Type [Int_Type];
     foreach word (word_list)
       {
          if (0 == assoc_key_exists (a, word))
            a[word] = 0;
          a[word]++;  % same as a[word] = a[word] + 1;
       }
Note that assoc_key_exists was necessary to determine whether or not a word was already added to the array in order to properly initialize it. However, by creating the associative array with a default value of 0, the above code may be simplified to
     variable a, word;
     a = Assoc_Type [Int_Type, 0];
     foreach word (word_list)
       a[word]++;

Associative arrays are extremely useful and have may other applications. Whenever there is a one to one mapping between a string and some object, one should always consider using an associative array to represent the mapping. To illustrate this point, consider the following code fragment:

      define call_function (name, arg)
      {
         if (name == "foo") return foo (arg);
         if (name == "bar") return bar (arg);
           .
           .
         if (name == "baz") return baz (arg);
         throw InvalidParmError;
      }
This represents a mapping between names and functions. Such a mapping may be written in terms of an associative array as follows:
      private define invalid_fun (arg) { throw InvalidParmError; }
      Fun_Map = Assoc_Type[Ref_Type, &invalid_fun];
      define add_function (name, fun)
      {
         Fun_Map[name] = fun;
      }
      add_function ("foo", &foo);
      add_function ("bar", &bar);
         .
         .
      add_function ("baz", &baz);
      define call_function (name, arg)
      {
         return (@Fun_Map[name])(arg);
      }
The most redeeming feature of the version involving the series of if statements is that it is easy to understand. However, the version involving the associative array has two significant advantages over the former. Namely, the function lookup will be much faster with a time that is independent of the item being searched, and it is extensible in the sense that additional functions may be added at run-time, e.g.,
      add_function ("bing", &bing);


Next Previous Contents