|
ALINK="#ff0000">
Unique Associative Container
|
|
Category: containers |
Component type: concept |
Description
A Unique Associative Container is an Associative Container 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
Associative Container
Associated types
None, except for those defined by Associative Container.
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
Associative Container, the
following expressions must be valid.
Name
|
Expression
|
Type requirements
|
Return type
|
Range constructor
|
X(i, j)
X a(i, j);
|
i and j are Input Iterators 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 Input Iterators 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
|
X(i, j)
X a(i, j);
|
[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 Input Iterator
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
Associative Container, Multiple Associative Container,
Unique Sorted Associative Container,
Multiple Sorted Associative Container
Copyright ©
1999 Silicon Graphics, Inc. All Rights Reserved.
TrademarkInformation
|