Standard Template Library Programmer's Guide

is a dereferenceable iterator in a, then either p lies in the range [P.first, P.second), or else *p has a key that is not the same as k.

Complexity guarantees

Average complexity for erase key is at most O(log(size()) + count(k)).

Average complexity for erase element is constant time.

Average complexity for erase range is at most O(log(size()) + N), where N is the number of elements in the range.

Average complexity for count is at most O(log(size()) + count(k)).

Average complexity for find is at most logarithmic.

Average complexity for equal range is at most logarithmic.

Invariants

Contiguous storage	All elements with the same key are adjacent to each other. That is, if p and q are iterators that point to elements that have the same key, and if p precedes q , then every element in the range [p, q) has the same key as every other element.
Immutability of keys	Every element of an Associative Container has an immutable key. Objects may be inserted and erased, but an element in an Associative Container may not be modified in such a way as to change its key.

Models

• set
• multiset
• hash_set
• hash_multiset
• map
• multimap
• hash_map
• hash_multimap

Notes

[1] The reason there is no such mechanism is that the way in which elements are arranged in an associative container is typically a class invariant; elements in a Sorted Associative Container, for example, are always stored in ascending order, and elements in a Hashed Associative Container are always stored according to the hash function. It would make no sense to allow the position of an element to be chosen arbitrarily.

[2] Keys are not required to be Equality Comparable: associative containers do not necessarily use operator== to determine whether two keys are the same. In Sorted Associative Containers, for example, where keys are ordered by a comparison function, two keys are considered to be the same if neither one is less than the other.

[3] Note the implications of this member function: it means that if two elements have the same key, there must be no elements with different keys in between them. The requirement that elements with the same key be stored contiguously is an associative container invariant.

See also

Simple Associative Container, Pair Associative Container, Unique Associative Container, Multiple Associative Container, Sorted Associative Container, Unique Sorted Associative Container, Multiple Sorted Associative Container, Hashed Associative Container, Unique Hashed Associative Container, Multiple Hashed Associative Container.

Simple Associative Container

Category: containers

Component type: concept

Description

A Simple Associative Container is an Associative Container where elements are their own keys. A key in a Simple Associative Container is not associated with any additional value.

Refinement of

Associative Container

Associated types

None, except for those described in the Associative Container requirements. Simple Associative Container, however, introduces two new type restrictions.

Key type	X::key_type	The type of the key associated with X::value_type. The types key_type and value_type must be the same type.
Iterator	X::iterator	The type of iterator used to iterate through a Simple Associative Container's elements. The types X::iterator and X::const_iterator must be the same type. That is, a Simple Associative Container does not provide mutable iterators. [1]

Notation

X A type that is a model of Simple Associative Container

a Object of type X

k Object of type X::key_type

p, q Object of type X::iterator

Valid expressions

None, except for those defined in the Associative Container requirements.

Invariants

Immutability of Elements

Every element of a Simple Associative Container is immutable. Objects may be inserted and erased, but not modified. [1]