[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)