In C++, associative containers or associative collections are a group of class templates in the standard library that implement ordered associative arrays. Being templates, they can be used to store arbitrary elements, such as integers or custom classes. Like all other standard library components, they reside in namespace <code>std</code>.
The following containers are defined in the current revision of the C++ standard:
Each of these containers differ only on constraints placed on their elements.
There are also versions of these collections in namespace <code>std::pmr</code> (for polymorphic memory resources). These versions specify the optional template parameter <code>Allocator</code> as <code>std::pmr::polymorphic_allocator</code>.
<code>std::set</code> and <code>std::multiset</code> are declared in header <code><set></code>, while <code>std::map</code> and <code>std::multimap</code> are declared in header <code><map></code>.
The associative containers are similar to the unordered associative containers in C++ standard library, the only difference is that the unordered associative containers, as their name implies, do not order their elements.
<code>std::map</code> and <code>std::set</code> are usually implemented as red-black trees, and are essentially (respectively) equivalent to <code>java.util.TreeMap</code> and <code>java.util.TreeSet</code> from Java, <code>System.Collections.Generic.SortedDictionary</code> and <code>System.Collections.Generic.SortedSet</code> from .NET, or <code>std::collections::BTreeMap</code> and <code>std::collections::BTreeSet</code> from Rust.
Associative containers are designed to be especially efficient in accessing its elements by their key, as opposed to sequence containers which are more efficient in accessing elements by their position. Associative containers are guaranteed to perform operations of insertion, deletion, and testing whether an element is in it, in logarithmic time â As such, they are typically implemented using self-balancing binary search trees and support bidirectional iteration. Iterators and references are not invalidated by insert and erase operations, except for iterators and references to erased elements.The defining characteristic of associative containers is that elements are inserted in a pre-defined order, such as sorted ascending.
The associative containers can be grouped into two subsets: maps and sets. A map, sometimes referred to as a dictionary, consists of a key/value pair. The key is used to order the sequence, and the value is somehow associated with that key. For example, a map might contain keys representing every unique word in a text and values representing the number of times that word appears in the text. A set is simply an ascending container of unique elements.
As stated earlier, <code>map</code> and <code>set</code> only allow one instance of a key or element to be inserted into the container. If multiple instances of elements are required, use <code>multimap</code> or <code>multiset</code>.
Both maps and sets support bidirectional iterators. For more information on iterators, see Iterators.
While not officially part of the STL standard, <code>hash_map</code> and <code>hash_set</code> are commonly used to improve searching times. These containers store their elements as a hash table, with each table entry containing a bidirectional linked list of elements. To ensure the fastest search times (), make sure that the hashing algorithm for your elements returns evenly distributed hash values.
The asymptotic complexity of the operations that can be applied to associative containers are as follows:
Unordered sets are usually more efficient than ordered sets, with inserting, removing, and searching operations being done in time.
The containers are defined in headers named after the names of the containers, e.g. <code>set</code> is defined in header <code><set></code>. All containers satisfy the requirements of the Container concept, which means they have <code>begin()</code>, <code>end()</code>, <code>size()</code>, <code>max_size()</code>, <code>empty()</code>, and <code>swap()</code> methods.
The following code demonstrates how to use the <code>map<string, int></code> to count occurrences of words. It uses the word as the key and the count as the value.
When executed, program lets user type a series of words separated by spaces, and a word "end" to signify the end of input. Then user can input a word to query how many times it has occurred in the previously entered series.
The above example also demonstrates that the operator <code>[]</code> inserts new objects (using the default constructor) in the map if there is not one associated with the key. So integral types are zero-initialized, strings are initialized to empty strings, etc.
The following example illustrates inserting elements into a map using the insert function and searching for a key using a map iterator and the find function:
Example shown above demonstrates the usage of some of the functions provided by <code>map</code>, such as <code>insert()</code> (place element into the map), <code>erase()</code> (remove element from the map), <code>find()</code> (check presence of the element in the container), etc.
When program is executed, six elements are inserted using the <code>insert()</code> function, then the first element is deleted using <code>erase()</code> function and the size of the map is outputted. Next, the user is prompted for a key to search for in the map. Using the iterator created earlier, the <code>find()</code> function searches for an element with the given key. If it finds the key, the program prints the element's value. If it doesn't find it, an iterator to the end of the map is returned and it outputs that the key could not be found. Finally all the elements in the tree are erased using <code>clear()</code>.
Maps may use iterators to point to specific elements in the container. An iterator can access both the key and the mapped value of an element:
Below is an example of looping through a map to display all keys and values using iterators: