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.