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.
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 . In the search tree case, we maintain a complexity of .
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()
andvalues()
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++
The C++ map
is a part of the Standard Template Library as std::map
, implemented with a red-black tree (as a balancing BST). The std::map
iterator advances as an in-order traversal of the tree, based on insertion order.
Unordered maps (hash tables) are std::unordered_map<T, T>
.