24 Containers library [containers]

24.6 Container adaptors [container.adaptors]

24.6.11 Class template flat_set [flat.set] Overview [flat.set.overview]

A flat_set is a container adaptor that provides an associative container interface that supports unique keys (i.e., contains at most one of each key value) and provides for fast retrieval of the keys themselves.
flat_set supports iterators that model the random_access_iterator concept ([iterator.concept.random.access]).
A flat_set meets all of the requirements for a container ([container.reqmts]) and for a reversible container ([container.rev.reqmts]), plus the optional container requirements ([container.opt.reqmts]).
flat_set 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_set does not meet the additional requirements of an allocator-aware container, as described in [container.alloc.reqmts].
— end note]
A flat_set also provides most operations described in [associative.reqmts] for unique keys.
This means that a flat_set supports the a_uniq operations in [associative.reqmts] but not the a_eq operations.
For a flat_set<Key>, both the key_type and value_type are Key.
Descriptions are provided here only for operations on flat_set that are not described in one of those sets of requirements or for operations where there is additional semantic information.
A flat_set maintains the invariant that the keys are sorted with respect to the comparison object.
If any member function in [flat.set.defn] exits via an exception, the invariant is restored.
[Note 2:
This can result in the flat_set's being emptied.
— end note]
Any sequence container ([sequence.reqmts]) supporting Cpp17RandomAccessIterator can be used to instantiate flat_set.
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_unique_t argument with a range that is not sorted with respect to key_comp(), or that contains equal elements, is undefined.