Associative containers


In computing, associative containers refer to a group of class templates in the standard library of the C++ programming language that implement ordered associative arrays. 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.

Design

Characteristics

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. 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.
Both 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, make sure that the hashing algorithm for your elements returns evenly distributed hash values.

Performance

The asymptotic complexity of the operations that can be applied to associative containers are as follows:
OperationComplexity
Searching for an elementO
Inserting a new elementO
Incrementing/decrementing an iteratorO
Removing a single elementO

Overview of functions

The containers are defined in headers named after the names of the containers, e.g. set is defined in header . All containers satisfy the requirements of the concept, which means they have begin, end, size, max_size, empty, and swap methods.
setmapmultisetmultimapDescription
Constructs the container from variety of sources
Destructs the set and the contained elements
Assigns values to the container
Returns the allocator used to allocate memory for the elements
Element accessAccesses specified element with bounds checking.
Element access]Accesses specified element without bounds checking.
IteratorsReturns an iterator to the beginning of the container
IteratorsReturns an iterator to the end of the container
IteratorsReturns a reverse iterator to the reverse beginning of the container
IteratorsReturns a reverse iterator to the reverse end of the container
CapacityChecks whether the container is empty
CapacityReturns number of elements in the container.
CapacityReturns the maximum possible number of elements in the container
ModifiersClears the contents.
ModifiersInserts elements.
ModifiersConstructs elements in-place
ModifiersConstructs elements in-place using a hint
ModifiersErases elements.
ModifiersSwaps the contents with another container.
LookupReturns the number of elements matching specific key.
LookupFinds an element with specific key.
LookupReturns a range of elements matching specific key.
LookupReturns an iterator to the first element with a key not less than the given value.
LookupReturns an iterator to the first element with a key greater than a certain value.
ObserversReturns the key comparison function.
ObserversReturns the value comparison function. In set and multiset this function is
equivalent to key_comp, since the elements are composed from a key only.

Usage

The following code demonstrates how to use the map to count occurrences of words. It uses the word as the key and the count as the value.

  1. include
  2. include
  3. include
int main

When executed, the user first types a series of words separated by spaces, and a word "end" to signify the end of input; then the user can input words to query how many times each word occurred in the previous series.
The above example also demonstrates that the operator inserts new objects in the map if there isn't 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:

  1. include
  2. include
  3. include // make_pair
int main

In the above example, six elements are entered using the insertion function, and then the first element is deleted. Then, the size of the map is output. Next, the user is prompted for a key to search for. Using the iterator, the find function searches for an element with the given key. If it finds the key, the program prints the element's value. If it does not 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.

Iterators

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:

map::iterator it; // declares a map iterator
it->first; // the key value
it->second; // the mapped value
; // the "element value", which is of type: pair

Below is an example of looping through a map to display all keys and values using iterators:

  1. include
  2. include
  3. include
int main

For compiling above sample on GCC compiler, must use specific standard select flag.
g++ -std=c++11 source.cpp -o src
This will output the keys and values of the entire map, sorted by keys.