In C++, associative containers are a group of class templates in the standard library of the C++ programming language that implement ordered associative arrays.[1] Being templates, they can be used to store arbitrary elements, such as integers or custom classes. The following containers are defined in the current revision of the C++ standard: set, map, multiset, multimap. Each of these containers differ only on constraints placed on their elements.
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.
map and set each key must be unique. multimap and multiset do not have this restriction.map and multimap each element is composed from a key and a mapped value. In set and multiset each element is key; there are no mapped values.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 – O(log n). 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, map and set only allow one instance of a key or element to be inserted into the container. If multiple instances of elements are required, use multimap or multiset. Both maps and sets support bidirectional iterators. For more information on iterators, see Iterators. While not officially part of the STL standard, hash_map and hash_set 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 (O(1)), make sure that the hashing algorithm for your elements returns evenly distributed hash values.
See also: Big O notation and Time complexity.
The asymptotic complexity of the operations that can be applied to associative containers are as follows:
| Operation | Complexity |
|---|---|
| Searching for an element | O(log n) |
| Inserting a new element | O(log n) |
| Incrementing/decrementing an iterator | O(log n) (amortized O(1) if only increments or only decrements are done) |
| Removing a single element | O(log n) |
The containers are defined in headers named after the names of the containers, e.g. set is defined in header <set>. All containers satisfy the requirements of the Container concept, which means they have begin, end, size, max_size, empty, and swap methods.
set | map | multiset | multimap | Description | |
|---|---|---|---|---|---|
| (constructor) | (constructor) | (constructor) | (constructor) | Constructs the container from variety of sources | |
| (destructor) | (destructor) | (destructor) | (destructor) | Destructs the set and the contained elements | |
[http://en.cppreference.com/w/cpp/container/set/operator= operator=] | [http://en.cppreference.com/w/cpp/container/map/operator= operator=] | [http://en.cppreference.com/w/cpp/container/multiset/operator= operator=] | [http://en.cppreference.com/w/cpp/container/multimap/operator= operator=] | Assigns values to the container | |
[http://en.cppreference.com/w/cpp/container/set/get_allocator get_allocator] | [http://en.cppreference.com/w/cpp/container/map/get_allocator get_allocator] | [http://en.cppreference.com/w/cpp/container/multiset/get_allocator get_allocator] | [http://en.cppreference.com/w/cpp/container/multimap/get_allocator get_allocator] | Returns the allocator used to allocate memory for the elements | |
| Element access | [http://en.cppreference.com/w/cpp/container/map/at at] | Accesses specified element with bounds checking. | |||
[http://en.cppreference.com/w/cpp/container/map/operator_at operator<nowiki>[]</nowiki>]| | | Accesses specified element without bounds checking.|-! rowspan=4 | Iterators| [http://en.cppreference.com/w/cpp/container/set/begin begin]| [http://en.cppreference.com/w/cpp/container/map/begin begin]| [http://en.cppreference.com/w/cpp/container/multiset/begin begin]| [http://en.cppreference.com/w/cpp/container/multimap/begin begin]| Returns an iterator to the beginning of the container|-| [http://en.cppreference.com/w/cpp/container/set/end end]| [http://en.cppreference.com/w/cpp/container/map/end end]| [http://en.cppreference.com/w/cpp/container/multiset/end end]| [http://en.cppreference.com/w/cpp/container/multimap/end end]| Returns an iterator to the end of the container|-| [http://en.cppreference.com/w/cpp/container/set/rbegin rbegin]| [http://en.cppreference.com/w/cpp/container/map/rbegin rbegin]| [http://en.cppreference.com/w/cpp/container/multiset/rbegin rbegin]| [http://en.cppreference.com/w/cpp/container/multimap/rbegin rbegin]| Returns a reverse iterator to the reverse beginning of the container|-| [http://en.cppreference.com/w/cpp/container/set/rend rend]| [http://en.cppreference.com/w/cpp/container/map/rend rend]| [http://en.cppreference.com/w/cpp/container/multiset/rend rend]| [http://en.cppreference.com/w/cpp/container/multimap/rend rend]| Returns a reverse iterator to the reverse end of the container|-! rowspan=3 | Capacity| [http://en.cppreference.com/w/cpp/container/set/empty empty]| [http://en.cppreference.com/w/cpp/container/map/empty empty]| [http://en.cppreference.com/w/cpp/container/multiset/empty empty]| [http://en.cppreference.com/w/cpp/container/multimap/empty empty]| Checks whether the container is empty|-| [http://en.cppreference.com/w/cpp/container/set/size size]| [http://en.cppreference.com/w/cpp/container/map/size size]| [http://en.cppreference.com/w/cpp/container/multiset/size size]| [http://en.cppreference.com/w/cpp/container/multimap/size size]| Returns number of elements in the container.|-| [http://en.cppreference.com/w/cpp/container/set/max_size max_size]| [http://en.cppreference.com/w/cpp/container/map/max_size max_size]| [http://en.cppreference.com/w/cpp/container/multiset/max_size max_size]| [http://en.cppreference.com/w/cpp/container/multimap/max_size max_size]| Returns the maximum possible number of elements in the container|-! rowspan=6 | Modifiers| [http://en.cppreference.com/w/cpp/container/set/clear clear]| [http://en.cppreference.com/w/cpp/container/map/clear clear]| [http://en.cppreference.com/w/cpp/container/multiset/clear clear]| [http://en.cppreference.com/w/cpp/container/multimap/clear clear]| Clears the contents.|-| [http://en.cppreference.com/w/cpp/container/set/insert insert]| [http://en.cppreference.com/w/cpp/container/map/insert insert]| [http://en.cppreference.com/w/cpp/container/multiset/insert insert]| [http://en.cppreference.com/w/cpp/container/multimap/insert insert]| Inserts elements.|-| [http://en.cppreference.com/w/cpp/container/set/emplace emplace]| [http://en.cppreference.com/w/cpp/container/map/emplace emplace]| [http://en.cppreference.com/w/cpp/container/multiset/emplace emplace]| [http://en.cppreference.com/w/cpp/container/multimap/emplace emplace]| Constructs elements in-place (C++11)|-| [http://en.cppreference.com/w/cpp/container/set/emplace_hint emplace_hint]| [http://en.cppreference.com/w/cpp/container/map/emplace_hint emplace_hint]| [http://en.cppreference.com/w/cpp/container/multiset/emplace_hint emplace_hint]| [http://en.cppreference.com/w/cpp/container/multimap/emplace_hint emplace_hint]| Constructs elements in-place using a hint (C++11)|-| [http://en.cppreference.com/w/cpp/container/set/erase erase]| [http://en.cppreference.com/w/cpp/container/map/erase erase]| [http://en.cppreference.com/w/cpp/container/multiset/erase erase]| [http://en.cppreference.com/w/cpp/container/multimap/erase erase]| Erases elements.|-| [http://en.cppreference.com/w/cpp/container/set/swap swap]| [http://en.cppreference.com/w/cpp/container/map/swap swap]| [http://en.cppreference.com/w/cpp/container/multiset/swap swap]| [http://en.cppreference.com/w/cpp/container/multimap/swap swap]| Swaps the contents with another container.|-! rowspan=5 | Lookup| [http://en.cppreference.com/w/cpp/container/set/count count]| [http://en.cppreference.com/w/cpp/container/map/count count]| [http://en.cppreference.com/w/cpp/container/multiset/count count]| [http://en.cppreference.com/w/cpp/container/multimap/count count]| Returns the number of elements matching specific key.|-| [http://en.cppreference.com/w/cpp/container/set/find find]| [http://en.cppreference.com/w/cpp/container/map/find find]| [http://en.cppreference.com/w/cpp/container/multiset/find find]| [http://en.cppreference.com/w/cpp/container/multimap/find find]| Finds an element with specific key.|-| [http://en.cppreference.com/w/cpp/container/set/equal_range equal_range]| [http://en.cppreference.com/w/cpp/container/map/equal_range equal_range]| [http://en.cppreference.com/w/cpp/container/multiset/equal_range equal_range]| [http://en.cppreference.com/w/cpp/container/multimap/equal_range equal_range]| Returns a range of elements matching specific key.|-| [http://en.cppreference.com/w/cpp/container/set/lower_bound lower_bound]| [http://en.cppreference.com/w/cpp/container/map/lower_bound lower_bound]| [http://en.cppreference.com/w/cpp/container/multiset/lower_bound lower_bound]| [http://en.cppreference.com/w/cpp/container/multimap/lower_bound lower_bound]| Returns an iterator to the first element with a key not less than the given value.|-| [http://en.cppreference.com/w/cpp/container/set/upper_bound upper_bound]| [http://en.cppreference.com/w/cpp/container/map/upper_bound upper_bound]| [http://en.cppreference.com/w/cpp/container/multiset/upper_bound upper_bound]| [http://en.cppreference.com/w/cpp/container/multimap/upper_bound upper_bound]| Returns an iterator to the first element with a key greater than a certain value.|-! rowspan=2 | Observers| [http://en.cppreference.com/w/cpp/container/set/key_comp key_comp]| [http://en.cppreference.com/w/cpp/container/map/key_comp key_comp]| [http://en.cppreference.com/w/cpp/container/multiset/key_comp key_comp]| [http://en.cppreference.com/w/cpp/container/multimap/key_comp key_comp]| Returns the key comparison function.|-| [http://en.cppreference.com/w/cpp/container/set/value_comp value_comp]| [http://en.cppreference.com/w/cpp/container/map/value_comp value_comp]| [http://en.cppreference.com/w/cpp/container/multiset/value_comp value_comp]| [http://en.cppreference.com/w/cpp/container/multimap/value_comp value_comp]| Returns the value comparison function. In set and multiset this function is equivalent to key_comp, since the elements are composed from a key only.|}UsageThe following code demonstrates how to use the
int main 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 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:
int main Example shown above demonstrates the usage of some of the functions provided by When program is executed, six elements are inserted using the IteratorsMaps 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: // Accesses the Key value it->first; // Accesses the mapped valueit->second; // The "value" of the iterator, which is of type std::pair Below is an example of looping through a map to display all keys and values using iterators:
int main For compiling above sample on GCC compiler, must use specific standard select flag. See alsoReferences |