|
| |
|
| Category: containers | | Component type: concept |
Description
A Unique Associative Container is an AssociativeContainer with the property that each key in the container is unique: no two elements in a Unique Associative Container have the same key.
Refinement of
AssociativeContainer
Associated types
None, except for those defined by AssociativeContainer.
Notation
X | A type that is a model of Unique Associative Container |
a | Object of type X |
t | Object of type X::value_type |
k | Object of type X::key_type |
p, q | Object of type X::iterator |
Definitions
Valid expressions
In addition to the expressions defined in AssociativeContainer, the following expressions must be valid.
| Name | Expression | Type requirements | Return type |
| Range constructor | | i and j are InputIterator whose value type is convertible to T [1] | |
| Insert element | a.insert(t) | | pair<X::iterator, bool> |
| Insert range | a.insert(i, j) | i and j are InputIterator whose value type is convertible to X::value_type. [1] | void |
| Count | a.count(k) | | size_type |
Expression semantics
| Name | Expression | Precondition | Semantics | Postcondition |
| Range constructor | | [i,j) is a valid range. | Creates an associative container that contains all of the elements in the range [i,j) that have unique keys. | size() is less than or equal to the distance from i to j. |
| Insert element | a.insert(t) | | Inserts t into a if and only if a does not already contain an element whose key is the same as the key of t. The return value is a pair P. P.first is an iterator pointing to the element whose key is the same as the key of t. P.second is a bool: it is true if t was actually inserted into a, and false if t was not inserted into a, i.e. if a already contained an element with the same key as t. | P.first is a dereferenceable iterator. *(P.first) has the same key as t. The size of a is incremented by 1 if and only if P.second is true. |
| Insert range | a.insert(i, j) | [i, j) is a valid range. | Equivalent to a.insert(t) for each object t that is pointed to by an iterator in the range [i, j). Each element is inserted into a if and only if a does not already contain an element with the same key. | The size of a is incremented by at most j - i. |
| Count | a.count(k) | | Returns the number of elements in a whose keys are the same as k. | The return value is either 0 or 1. |
Complexity guarantees
Average complexity for insert element is at most logarithmic.
Average complexity for insert range is at most O(N * log(size() + N)), where N is j - i.
Invariants
| Uniqueness | No two elements have the same key. Equivalently, this means that for every object k of type key_type, a.count(k) returns either 0 or 1. |
Models
Notes
[1] At present (early 1998), not all compilers support "member templates". If your compiler supports member templates then i and j may be of any type that conforms to the InputIterator requirements. If your compiler does not yet support member templates, however, then i and j must be of type const T* or of type X::const_iterator.
See also
AssociativeContainer, MultipleAssociativeContainer, UniqueSortedAssociativeContainer, MultipleSortedAssociativeContainer
