Associative containers

(See Containers.)

key_type Typedef on associative containers
key_compare Typedef on associative containers
value_compare Typedef on associative containers

Associative containers provide an ability for fast retrieval of data based on keys. The library provides four basic kinds of associative containers: set, multiset, map and multimap.
All of them are parameterized on Key and an ordering relation Compare that induces a total ordering on elements of Key. In addition, map and multimap associate an arbitrary type T with the Key. The object of type Compare is called the comparison object of a container.

key_compare key_comp () Method on associate containers
value_compare value_comp () Method on associate containers
This section talks about equality of keys, the equivalence relation imposed by the comparison and not the operator== on keys. That is, two keys k1 and k2 are considered to be equal if for the comparison object comp, comp(k1, k2) == false && comp(k2, k1) == false.

insert (T& t) Method on associate containers
erase (...) Method on associate containers
An associative container supports unique keys if it may contain at most one element for each key. Otherwise, it supports equal keys. set and map support unique keys. multiset and multimap support equal keys.

For set and multiset the value type is the same as the key type. For map and multimap it is equal to pair<const Key, T>.

iterator of an associative container is of the bidirectional iterator category. insert does not affect the validity of iterators and references to the container, and erase invalidates only the iterators and references to the erased elements.

In the following table, X is an associative container class, a is a value of X, a_uniq is a value of X when X supports unique keys, and a_eq is a value of X when X supports multiple keys, i and j satisfy input iterator requirements and refer to elements of value_type, [i, j) is a valid range, p is a valid iterator to a, q is a dereferenceable iterator to a, [q1, q2) is a valid range in a, t is a value of X::value_type and k is a value of X::key_type.

X (InputIterator& i, InputIterator& j, Compare& c) Constructor on associative containers
X (InputIterator& i, InputIterator& j) Constructor on associative containers

( const_)iterator find (const key_type& k) Method on associative containers
size_type count (const key_type& k) Method on associative containers
( const_)iterator lower_bound (const key_type& k) Method on associative containers
( const_)iterator upper_bound (const key_type& k) Method on associative containers
pair<(const_)iterator> equal_range (const key_type& k) Method on associative containers

Table 12: Associative container requirements (in addition to container)

Expression Return type Assertion/note pre/post-condition Complexity
X::key_type Key compile time
X::key_compare Compare defaults to less<key_type>. compile time
X::value_compare a binary predicate type is the same as key_compare for set and multiset; is an ordering relation on pairs induced by the first component (i.e. Key) for map and multimap. compile time
X(c);
X a(c); 		  constructs an empty container; uses c as a comparison object. constant
X();
X a; 		  constructs an empty container; uses Compare() as a comparison object. constant
X(i, j, c);
X a(i, j, c); 		  constructs an empty container and inserts elements from the range [i, j) into it; uses c as a comparison object. N \log N in general(N is the distance from i to j); linear if [i, j) is sorted with value_comp()
X(i, j);
X a(i, j); 		  same as above, but uses Compare() as a comparison object. same as above
a.key_comp() X::key_compare returns the comparison object out of which a was constructed. constant
a.value_comp() X::value_compare returns an object of value_compare constructed out of the comparison object. constant
a_uniq.insert(t) pair<iterator, bool> inserts t if and only if there is no element in the container with key equal to the key of t. The bool component of the returned pair indicates whether the insertion takes place and the iterator component of the pair points to the element with key equal to the key of t. logarithmic
a_eq.insert(t) iterator inserts t and returns the iterator pointing to the newly inserted element. logarithmic
a.insert(p, t) iterator inserts t if and only if there is no element with key equal to the key of t in containers with unique keys; always inserts t in containers with equal keys.
Always returns the iterator pointing to the element with key equal to the key of t.
Iterator p is a hint pointing to where the insert should start to search. 		logarithmic in general, but amortized constant if t is inserted right before p.
a.insert(i, j) result is not used inserts the elements from the range [i, j) into the container. N \log(size()+N) (N is the distance from i to j) in general; linear if [i, j) is sorted according to value_comp()
a.erase(k) size_type erases all the elements in the container with key equal to k.
returns the number of erased elements. 		\log(size()) + count(k)
a.erase(q) result is not used erases the element pointed to by q. amortized constant
a.erase(q1, q2) result is not used erases all the elements in the range [q1, q2). \log(size())+ N where N is the distance from q1 to q2.
a.find(k) iterator; const_iterator for constant a returns an iterator pointing to an element with the key equal to k, or a.end() if such an element is not found. logarithmic
a.count(k) size_type returns the number of elements with key equal to k. \log(size()) + count(k)
a.lower_bound(k) iterator; const_iterator for constant a returns an iterator pointing to the first element with key not less than k. logarithmic
a.upper_bound(k) iterator; const_iterator for constant a returns an iterator pointing to the first element with key greater than k. logarithmic
a.equal_range(k) pair<iterator, iterator>; pair<const_iterator, const_iterator> for constant a equivalent to make_pair(a.lower_bound(k), a.upper_bound(k)). logarithmic

The fundamental property of iterators of associative containers is that they iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct them. For any two de-referenceable iterators i and j such that distance from i to j is positive, 

value_comp(*j, *i) == false

For associative containers with unique keys the stronger condition holds: 

value_comp(*i, *j) == true