C++ named requirements: AssociativeContainer

 

C++

Compiler support

Freestanding and hosted

Language

Standard library

Standard library headers

Named requirements

Feature test macros (C++20)

Language support library

Concepts library (C++20)

Metaprogramming library (C++11)

Diagnostics library

General utilities library

Strings library

Containers library

Iterators library

Ranges library (C++20)

Algorithms library

Numerics library

Localizations library

Input/output library

Filesystem library (C++17)

Regular expressions library (C++11)

Concurrency support library (C++11)

Technical specifications

Symbols index

External libraries

 

C++ named requirements

Basic
DefaultConstructible CopyAssignable	CopyConstructible MoveAssignable (C++11)	MoveConstructible (C++11) Destructible
Type properties
ScalarType TriviallyCopyable (C++11)	StandardLayoutType (C++11) PODType	TrivialType (C++11) ImplicitLifetimeType
Library-Wide
EqualityComparable LessThanComparable Swappable ValueSwappable (C++11)	NullablePointer (C++11) Hash (C++11) Allocator FunctionObject	Callable Predicate BinaryPredicate Compare
Container
Container SequenceContainer ContiguousContainer (C++17)	ReversibleContainer AssociativeContainer AllocatorAwareContainer	UnorderedAssociativeContainer (C++11)
Container Elements
DefaultInsertable (C++11) CopyInsertable (C++11)	MoveInsertable (C++11) EmplaceConstructible (C++11)	Erasable (C++11)
Iterator
LegacyIterator LegacyOutputIterator LegacyInputIterator	LegacyForwardIterator LegacyBidirectionalIterator LegacyRandomAccessIterator	LegacyContiguousIterator (C++17) ConstexprIterator (C++20)
Stream I/O
FormattedInputFunction UnformattedInputFunction	FormattedOutputFunction	UnformattedOutputFunction
Formatters
BasicFormatter (C++20)	Formatter (C++20)
Random Numbers
SeedSequence (C++11) RandomNumberEngine (C++11)	RandomNumberDistribution (C++11) UniformRandomBitGenerator (C++11)	RandomNumberEngineAdaptor (C++11)
Concurrency
BasicLockable (C++11) Lockable (C++11) TimedLockable (C++11)	SharedLockable (C++14) SharedTimedLockable (C++14) Mutex (C++11)	TimedMutex (C++11) SharedMutex (C++17) SharedTimedMutex (C++14)
Ranges
RangeAdaptorObject (C++20)	RangeAdaptorClosureObject (C++20)
Other
CharTraits RegexTraits (C++11) BitmaskType LiteralType (C++11)	NumericType UnaryTypeTrait (C++11) BinaryTypeTrait (C++11) TransformationTrait (C++11)	Clock (C++11) TrivialClock (C++11)

 

An AssociativeContainer is an ordered Container that provides fast lookup of objects based on keys.

An associative container supports unique keys if it may contain at most one element for each key. Otherwise, it supports equivalent keys.

Requirements

The type X satisfies AssociativeContainer if

• The type X satisfies Container (until C++11)AllocatorAwareContainer (since C++11),
• is parameterized on Key and an ordering relation Compare that induces a strict weak ordering on elements of Key, and
  • In addition, std::map and std::multimap associate an arbitrary mapped type T with the Key.
  • The object of type Compare is called the comparison object of a container of type X.

Given

• a, a value of type X
• a2, a value of a type Y whose node handles are compatible with X
• b, a value of type X or const X
• a_uniq, a value of type X when X supports unique keys
• a_eq, a value of type X when X supports equivalent keys
• a_tran, a value of type X or const X when type X::key_compare::is_transparent exists
• i and j, LegacyInputIterators denoting a valid range and referring to elements implicitly convertible to X::value_type
• p, a valid constant iterator to a
• q, a valid dereferenceable constant iterator to a
• r, a valid dereferenceable iterator to a
• q1 and q2, const iterators denoting a valid range in a
• il, an object of type std::initializer_list<X::value_type>
• t, a value of type X::value_type
• k, a value of type X::key_type
• c, a value of type X::key_compare or const X::key_compare
• kl, a value such that a is partitioned with respect to c(x, kl), with x the key value of e and e in a
• ku, a value such that a is partitioned with respect to !c(ku, x), with x the key value of e and e in a
• ke, a value such that a is partitioned with respect to c(x, ke) and !c(ke, x), with c(x, ke) implying !c(ke, x) and with x the key value of e and e in a
• kx, a value such that
  • a is partitioned with respect to c(x, kx) and !c(kx, x), with c(x, kx) implying !c(kx, x) and with x the key value of e and e in a, and
  • kx is not convertible to either X::iterator or X::const_iterator
• A, the allocator type of X: X::allocator_type if it exists, otherwise std::allocator<X::value_type>
• m, an allocator of a type convertible to A
• nh, a non-const rvalue of type X::node_type

Types

Name	Type	Requirements
key_type	Key
mapped_type	T (for std::map and std::multimap only)
value_type	Key (for std::set and std::multiset only) std::pair<const Key, T>(for std::map and std::multimap only)	Erasable from X
key_compare	Compare	CopyConstructible
value_compare	same as key_compare (for std::set and std::multiset) an ordering relation on pairs induced by the first component (i.e. Key) (for std::map and std::multimap)	BinaryPredicate
node_type	A specialization of the node-handle class template, such that the public nested types are the same types as the corresponding types in X.

Methods and operators

expression	return type	pre/requirements	post/effects	complexity
X(c)			Construct an empty container using a copy of c as the comparison object	constant
X(), X a = X();		X::key_compare is DefaultConstructible	Construct an empty container using a Compare() as the comparison object	constant
X(i, j, c)		X::value_type is EmplaceConstructible into X from *i	Constructs an empty container using a copy of c as the comparison object and inserts all elements from the range [i, j)	generally N·log N, or N if [i, j) is sorted (where N is std::distance(i, j))
X(i, j)		X::key_compare is DefaultConstructible and X::value_type is EmplaceConstructible into X from *i	Constructs an empty container using a Compare() as the comparison object and inserts all elements from the range [i, j)	generally N·log N, or N if [i, j) is sorted according to value_comp() (where N is std::distance(i, j))
X(il);		Equivalent to X(il.begin(),   il.end());	Equivalent to X(il.begin(),   il.end());
a = il	X&	T is CopyInsertable into X and also CopyAssignable	Assign the range [il.begin(), il.end()) into a. Elements of a that were not assigned to are destroyed	generally N·log N, or N if [il.begin(), il.end()) is sorted according to value_comp() (where N is il.size() + a.size())
a.key_comp()	X::key_compare		The comparison object with which a was constructed is returned.	constant
a.value_comp()	X::value_compare		An object of type X::value_compare constructed out of the comparison object is returned.	constant

Associative containers in the standard library

set	collection of unique keys, sorted by keys (class template)
multiset	collection of keys, sorted by keys (class template)
map	collection of key-value pairs, sorted by keys, keys are unique (class template)
multimap	collection of key-value pairs, sorted by keys (class template)

Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR	Applied to	Behavior as published	Correct behavior
LWG 354	C++98	lower_bound and upper_bound did not return the end iterator if no element is found	they return the end iterator in this case
LWG 589	C++98	the elements that i and j refer to had the type X::value_type	the elements are implicitly convertible to X::value_type