Dictionary

A dictionary (or associative container, symbol table, or map) is an abstract data type that stores key-value pairs. Items within dictionaries can be ordered (in order of insertion) or unordered.

myDict = { # declaration in Python
		  'name': 'Joe!',
		  'height': '170',
		  'mood': 'terrible'
}

Designing efficient data structures to implement dictionaries is difficult (called the dictionary problem), but can be done with hash tables and search trees. In the hash table case, we maintain a complexity of $\mathcal{O}(1)$. In the search tree case, we maintain a complexity of $\mathcal{O}(\log n)$.

Language-specific

Language support of dictionaries is mixed. In Python, they are called dictionaries. In C++ and Java, they’re called maps.

In Python

Dictionaries in Python are declared with curly brackets (see above for an example). Some associated methods are:

• keys() and values() return a “list” of associated data.
• get('key', fallback) grabs a key’s value. If it doesn’t exist, it returns the second argument.
• setdefault('key', value) sets a default value for a given key, even if it doesn’t exist.

In C++

std::map is a part of the Standard Template Library, implemented with a red-black tree (a self-balancing BST). The std::map iterator advances as an in-order traversal of the tree. Because of its implementation, the output is also sorted.

Unordered maps (implemented with hash tables) are std::unordered_map<T, T>. Unlike in std::map, iterating over unordered maps have no guarantee on order (increasing order, insertion order).