Книга: Standard Template Library Programmer

Unique Associative Container

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

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

• set
• map
• hash_set
• hash_map

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

Оглавление книги


Генерация: 0.924. Запросов К БД/Cache: 3 / 0
поделиться
Вверх Вниз