Przejdź do głównej zawartości

C++ named requirements: AssociativeContainer

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 (do C++11) AllocatorAwareContainer (od 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

NameTypeRequirements
key_typeKey
mapped_typeT (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_compareCompareCopyConstructible
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_typeA 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

ExpressionReturn typePre/RequirementsPost/EffectsComplexity
X(c)Construct an empty container using a copy of c as the comparison objectconstant
X(),
X a = X();
X::key_compare is DefaultConstructibleConstruct an empty container using a Compare() as the comparison objectconstant
X(i, j, c)X::value_type is EmplaceConstructible into X from *iConstructs 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 *iConstructs 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 = ilX&T is CopyInsertable into X and also CopyAssignableAssign the range [il.begin(), il.end()) into a. Elements of a that were not assigned to are destroyedgenerally 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_compareThe comparison object with which a was constructed is returned.constant
a.value_comp()X::value_compareAn object of type X::value_compare constructed out of the comparison object is returned.constant

Iterators

Iterators of associative containers satisfy the requirements of LegacyBidirectionalIterator.

For associative containers where value_type is the same as key_type, both iterator and const_iterator are constant iterators. It is unspecified whether or not iterator and const_iterator are the same type.

Iterators of associative containers iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct the containers. That is, given

  • a, an associative container
  • i and j, dereferenceable iterators to a

If the distance from i to j is positive, then a.value_comp()(*j, *i) == false. Additionally, if a is an associative container with unique keys, the stronger condition a.value_comp()(*i, *j) != false holds.

uwaga

This section is incomplete
Reason: Unfinished requirements

Associative containers in the standard library

pubstd::setcollection of unique keys, sorted by keys
pubstd::multisetcollection of keys, sorted by keys
pubstd::mapcollection of key-value pairs, sorted by keys, keys are unique
pubstd::multimapcollection of key-value pairs, sorted by keys

Defect reports

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

DRApplied toBehavior as publishedCorrect behavior
LWG 354C++98lower_bound and upper_bound did not return the end iterator if no element is foundthey return the end iterator in this case
LWG 589C++98the elements that i and j refer to had the type X::value_typethe elements are implicitly convertible to X::value_type

C++ named requirements: AssociativeContainer

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 (do C++11) AllocatorAwareContainer (od 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

NameTypeRequirements
key_typeKey
mapped_typeT (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_compareCompareCopyConstructible
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_typeA 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

ExpressionReturn typePre/RequirementsPost/EffectsComplexity
X(c)Construct an empty container using a copy of c as the comparison objectconstant
X(),
X a = X();
X::key_compare is DefaultConstructibleConstruct an empty container using a Compare() as the comparison objectconstant
X(i, j, c)X::value_type is EmplaceConstructible into X from *iConstructs 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 *iConstructs 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 = ilX&T is CopyInsertable into X and also CopyAssignableAssign the range [il.begin(), il.end()) into a. Elements of a that were not assigned to are destroyedgenerally 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_compareThe comparison object with which a was constructed is returned.constant
a.value_comp()X::value_compareAn object of type X::value_compare constructed out of the comparison object is returned.constant

Iterators

Iterators of associative containers satisfy the requirements of LegacyBidirectionalIterator.

For associative containers where value_type is the same as key_type, both iterator and const_iterator are constant iterators. It is unspecified whether or not iterator and const_iterator are the same type.

Iterators of associative containers iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct the containers. That is, given

  • a, an associative container
  • i and j, dereferenceable iterators to a

If the distance from i to j is positive, then a.value_comp()(*j, *i) == false. Additionally, if a is an associative container with unique keys, the stronger condition a.value_comp()(*i, *j) != false holds.

uwaga

This section is incomplete
Reason: Unfinished requirements

Associative containers in the standard library

pubstd::setcollection of unique keys, sorted by keys
pubstd::multisetcollection of keys, sorted by keys
pubstd::mapcollection of key-value pairs, sorted by keys, keys are unique
pubstd::multimapcollection of key-value pairs, sorted by keys

Defect reports

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

DRApplied toBehavior as publishedCorrect behavior
LWG 354C++98lower_bound and upper_bound did not return the end iterator if no element is foundthey return the end iterator in this case
LWG 589C++98the elements that i and j refer to had the type X::value_typethe elements are implicitly convertible to X::value_type