associative container stl

associative container c++

Associative containers sort their elements automatically according to a certain ordering criterion. This criterion takes the form of a function that compares either the value or a special key that is defined for the value. By default, the containers compare the elements or the keys with operator <. However, you can supply your own comparison function to define another ordering criterion.

Associative containers are typically implemented as binary trees. Thus, every element (every node) has one parent and two children. All ancestors to the left have lesser values; all ancestors to the right have greater values. The associative containers differ in the kind of elements they support and how they handle duplicates.

The following associative containers are predefined in the STL. Because you need iterators to access their elements,

• Sets : A set is a collection in which elements are sorted according to their own values. Each element may occur only once, thus duplicates are not allowed. 
• Multisets : A multiset is the same as a set except that duplicates are allowed. Thus, a multiset may contain multiple elements that have the same value. 
• Maps : A map contains elements that are key/value pairs. Each element has a key that is the basis for the sorting criterion and a value. Each key may occur only once, thus duplicate keys are not allowed. A map can also be used as an associative array, which is an array that has an arbitrary index type 
• Multimaps : A multimap is the same as a map except that duplicates are allowed. Thus, a multimap may contain multiple elements that have the same key. A multimap can also be used as dictionary.

All of these associative container classes have an optional  template argument for the sorting criterion. The default sorting criterion is the operator <. The sorting criterion is also used as the test for equality; that is, two elements are equal if neither is less than the other.

You can consider a set as a special kind of map, in which the value is identical to the key. In fact, all of these associative container types are usually implemented by using the same basic implementation of a binary tree.

See Also:

Using Associative container

Standard Template Library Concepts and sample codes in C++