Dictionaries

Dictionary Syntax and Semantics

A dictionary is a mapping from a key type to a value type.

For example:

module M
{
    struct Employee
    {
        long   number;
        string firstName;
        string lastName;
    }

    dictionary<long, Employee> EmployeeMap;
}

This definition creates a dictionary named EmployeeMap that maps from an employee number to a structure containing the details for an employee. Whether or not the key type (the employee number, of type long in this example) is also part of the value type (the Employee structure in this example) is up to you — as far as Slice is concerned, there is no need to include the key as part of the value.

Dictionaries can be used to implement sparse arrays, or any lookup data structure with non-integral key type. Even though a sequence of structures containing key-value pairs could be used to model the same thing, a dictionary is more appropriate:

• A dictionary clearly signals the intent of the designer, namely, to provide a mapping from a domain of values to a range of values. (A sequence of structures of key-value pairs does not signal that same intent as clearly.)

• At the programming language level, sequences are implemented as vectors (or possibly lists), that is, they are not well suited to model sparsely populated domains and require a linear search to locate an element with a particular value. On the other hand, dictionaries are implemented as a data structure (typically a hash table or red-black tree) that supports efficient searching in O(log n) average time or better.

Allowable Types for Dictionary Keys and Values

The key type of a dictionary need not be an integral type. For example, we could use the following definition to translate the names of the days of the week:

dictionary<string, string> WeekdaysEnglishToGerman;

The server implementation would take care of initializing this map with the key-value pairs Monday-Montag, Tuesday-Dienstag, and so on.

The value type of a dictionary can be any Slice type. However, the key type of a dictionary is limited to one of the following types:

• Integral types (short, int, long)

• bool

• byte

• string

• enum

• Structures containing only data members of legal key types

Other complex types, such as dictionaries, and floating-point types (float and double) cannot be used as the key type. Complex types are disallowed because they complicate the language mappings for dictionaries, and floating-point types are disallowed because representational changes of values as they cross machine boundaries can lead to ill-defined semantics for equality.

Language Mapping

Default Dictionary Mapping

Here is the definition of our EmployeeMap once more:

dictionary<long, Employee> EmployeeMap;

The following code is generated for this definition:

using EmployeeMap = std::map<long long, Employee>;

Again, there are no surprises here: a Slice dictionary simply maps to a standard std::map. As a result, you can use the dictionary like any other map, for example:

EmployeeMap em;
Employee e;

e.number = 42;
e.firstName = "Stan";
e.lastName = "Lippman";
em[e.number] = e;

e.number = 77;
e.firstName = "Herb";
e.lastName = "Sutter";
em[e.number] = e;

Customizing the Dictionary Mapping with cpp:type

You can override the default mapping of Slice dictionaries to C++ with a cpp:type metadata directive, for example:

[["cpp:include:unordered_map"]]

["cpp:type:std::unordered_map<std::int64_t, Employee>"] 
dictionary<long, Employee> EmployeeMap;

With this metadata directive, the dictionary now maps to a C++ std::unordered_map:

#include <unordered_map>

using EmployeeMap = std::unordered_map<std::int64_t, Employee>;

Like with sequences, anything following the cpp:type: prefix is taken to be the name of the type. For example, we could use ["cpp:type:::std::unordered_map<std::int64_t, std::string>"]. In that case, the compiler would use a fully-qualified name to define the type:

using IntStringDict = ::std::unordered_map<std::int64_t, std::string>;

To avoid compilation errors in the generated code, you must instruct the compiler to generate an appropriate include directive with the cpp:include file metadata directive. This causes the compiler to add the line

#include <unordered_map>

to the generated header file.

Instead of std::unordered_map, you can specify a type of your own as the dictionary type, for example:

[["cpp:include:CustomMap.h"]]

["cpp:type:MyCustomMap<std::int64_t, Employee>"]
dictionary<long, Employee> EmployeeMap;

With these metadata directives, the compiler will use a C++ type MyCustomMap as the dictionary type, and add an include directive for the header file CustomMap.h to the generated code.

The class or template class you provide must meet the following requirements:

• The class must have a default constructor.

• The class must have a copy constructor.

• The class must provide nested types named key_type, mapped_type and value_type.

• The class must provide iterator and const_iterator types and provide begin and end member functions with the usual semantics; these iterators must be comparable for equality and inequality.

• The class must provide a clear function.

• The class must provide an insert function that takes an iterator (as location hint) plus a value_type parameter, and returns an iterator to the new entry or to the existing entry with the given key.

Less formally, this means you can use any class or template class that looks like a standard map or unordered_map as your custom dictionary type.

In addition to modifying the type of a dictionary itself, you can also modify the mapping for particular return values or parameters. For example:

[["cpp:include:unordered_map"]]

module HR
{
    struct Employee
    {
       long   number;
       string firstName;
       string lastName;
    }
    dictionary<long, Employee> EmployeeMap;

    interface Office
    {
        ["cpp:type:std::unordered_map<long long, Employee>"] 
        EmployeeMap getAllEmployees();
    }
}

With this definition, getAllEmployees  returns an unordered_map, while other unqualified parameters of type EmployeeMap would use the default mapping (to a std::map).