[flat.multiset.overview] (original) (raw)
23 Containers library [containers]
23.6 Container adaptors [container.adaptors]
23.6.12 Class template flat_multiset [flat.multiset]
23.6.12.1 Overview [flat.multiset.overview]
A flat_multiset is a container adaptor that provides an associative container interface that supports equivalent keys (i.e., possibly containing multiple copies of the same key value) and provides for fast retrieval of the keys themselves.
flat_multiset meets the requirements of an associative container ([associative.reqmts]), except that:
- it does not meet the requirements related to node handles ([container.node.overview]),
- it does not meet the requirements related to iterator invalidation, and
- the time complexity of the operations that insert or erase a single element from the set is linear, including the ones that take an insertion position iterator.
[Note 1:
A flat_multiset does not meet the additional requirements of an allocator-aware container, as described in [container.alloc.reqmts].
— _end note_]
A flat_multiset also provides most operations described in [associative.reqmts] for equal keys.
This means that a flat_multiset supports the a_eq operations in [associative.reqmts]but not the a_uniq operations.
For a flat_multiset<Key>, both the key_type and value_type are Key.
Descriptions are provided here only for operations on flat_multisetthat are not described in one of the general sections or for operations where there is additional semantic information.
A flat_multiset maintains the invariant that the keys are sorted with respect to the comparison object.
If any member function in [flat.multiset.defn] exits via an exception, the invariant is restored.
[Note 2:
This can result in the flat_multiset's being emptied.
— _end note_]
Any sequence container ([sequence.reqmts]) supporting _Cpp17RandomAccessIterator_can be used to instantiate flat_multiset.
In particular,vector ([vector]) and deque ([deque]) can be used.
[Note 3:
vector<bool> is not a sequence container.
— _end note_]
The program is ill-formed if Key is not the same type as KeyContainer::value_type.
The effect of calling a constructor or member function that takes a sorted_equivalent_t argument with a range that is not sorted with respect to key_comp() is undefined.