138 lines
5.2 KiB
Markdown
138 lines
5.2 KiB
Markdown
[flat.set.overview]
|
||
|
||
# 23 Containers library [[containers]](./#containers)
|
||
|
||
## 23.6 Container adaptors [[container.adaptors]](container.adaptors#flat.set.overview)
|
||
|
||
### 23.6.11 Class template flat_set [[flat.set]](flat.set#overview)
|
||
|
||
#### 23.6.11.1 Overview [flat.set.overview]
|
||
|
||
[1](#1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18805)
|
||
|
||
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[.](#1.sentence-1)
|
||
|
||
flat_set supports iterators that model
|
||
the [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]") concept ([[iterator.concept.random.access]](iterator.concept.random.access "24.3.4.13 Concept random_access_iterator"))[.](#1.sentence-2)
|
||
|
||
[2](#2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18815)
|
||
|
||
A flat_set meets all of the requirements
|
||
for a container ([[container.reqmts]](container.reqmts "23.2.2.2 Container requirements")) and
|
||
for a reversible container ([[container.rev.reqmts]](container.rev.reqmts "23.2.2.3 Reversible container requirements")),
|
||
plus the optional container requirements ([[container.opt.reqmts]](container.opt.reqmts "23.2.2.4 Optional container requirements"))[.](#2.sentence-1)
|
||
|
||
flat_set meets the requirements of
|
||
an associative container ([[associative.reqmts]](associative.reqmts "23.2.7 Associative containers")), except that:
|
||
|
||
- [(2.1)](#2.1)
|
||
|
||
it does not meet the requirements
|
||
related to node handles ([[container.node.overview]](container.node.overview "23.2.5.1 Overview")),
|
||
|
||
- [(2.2)](#2.2)
|
||
|
||
it does not meet the requirements related to iterator invalidation, and
|
||
|
||
- [(2.3)](#2.3)
|
||
|
||
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[.](#2.sentence-2)
|
||
|
||
[*Note [1](#note-1)*:
|
||
|
||
A flat_set does not meet
|
||
the additional requirements of an allocator-aware container,
|
||
as described in [[container.alloc.reqmts]](container.alloc.reqmts "23.2.2.5 Allocator-aware containers")[.](#2.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
[3](#3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18840)
|
||
|
||
A flat_set also provides most operations
|
||
described in [[associative.reqmts]](associative.reqmts "23.2.7 Associative containers") for unique keys[.](#3.sentence-1)
|
||
|
||
This means that a flat_set supports
|
||
the a_uniq operations in [[associative.reqmts]](associative.reqmts "23.2.7 Associative containers") but not the a_eq operations[.](#3.sentence-2)
|
||
|
||
For a flat_set<Key>,
|
||
both the key_type and value_type are Key[.](#3.sentence-3)
|
||
|
||
[4](#4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18849)
|
||
|
||
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[.](#4.sentence-1)
|
||
|
||
[5](#5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18854)
|
||
|
||
A flat_set maintains the invariant that the keys are sorted with
|
||
respect to the comparison object[.](#5.sentence-1)
|
||
|
||
[6](#6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18858)
|
||
|
||
If any member function in [[flat.set.defn]](flat.set.defn "23.6.11.2 Definition") exits via an exception,
|
||
the invariant is restored[.](#6.sentence-1)
|
||
|
||
[*Note [2](#note-2)*:
|
||
|
||
This can result in the flat_set's being emptied[.](#6.sentence-2)
|
||
|
||
â *end note*]
|
||
|
||
[7](#7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18865)
|
||
|
||
Any sequence container ([[sequence.reqmts]](sequence.reqmts "23.2.4 Sequence containers"))
|
||
supporting *Cpp17RandomAccessIterator* can be used to instantiate flat_set[.](#7.sentence-1)
|
||
|
||
In particular, vector ([[vector]](vector "23.3.13 Class template vector")) and deque ([[deque]](deque "23.3.5 Class template deque"))
|
||
can be used[.](#7.sentence-2)
|
||
|
||
[*Note [3](#note-3)*:
|
||
|
||
vector<bool> is not a sequence container[.](#7.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
[8](#8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18875)
|
||
|
||
The program is ill-formed if Key is not the same type
|
||
as KeyContainer::value_type[.](#8.sentence-1)
|
||
|
||
[9](#9)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18879)
|
||
|
||
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[.](#9.sentence-1)
|
||
|
||
[10](#10)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18885)
|
||
|
||
The types iterator and const_iterator meet
|
||
the constexpr iterator requirements ([[iterator.requirements.general]](iterator.requirements.general "24.3.1 General"))[.](#10.sentence-1)
|