Node:Associative containers, Previous:Sequences, Up: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: All of them are parameterized on |
| key_compare key_comp () | Method on associate containers |
| value_compare value_comp () | Method on associate containers |
In this section when we talk about equality of keys we mean 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 |
| 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(
|
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 dereferenceable 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.