[flat.set]

# 23 Containers library [[containers]](./#containers)

## 23.6 Container adaptors [[container.adaptors]](container.adaptors#flat.set)

### 23.6.11 Class template flat_set [flat.set]

#### [23.6.11.1](#overview) Overview [[flat.set.overview]](flat.set.overview)

[1](#overview-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[.](#overview-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"))[.](#overview-1.sentence-2)

[2](#overview-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"))[.](#overview-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)](#overview-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)](#overview-2.2)

it does not meet the requirements related to iterator invalidation, and

- [(2.3)](#overview-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[.](#overview-2.sentence-2)

[*Note [1](#overview-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")[.](#overview-2.sentence-3)

â *end note*]

[3](#overview-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[.](#overview-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[.](#overview-3.sentence-2)

For a flat_set<Key>,
both the key_type and value_type are Key[.](#overview-3.sentence-3)

[4](#overview-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[.](#overview-4.sentence-1)

[5](#overview-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[.](#overview-5.sentence-1)

[6](#overview-6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18858)

If any member function in [[flat.set.defn]](#defn "23.6.11.2 Definition") exits via an exception,
the invariant is restored[.](#overview-6.sentence-1)

[*Note [2](#overview-note-2)*:

This can result in the flat_set's being emptied[.](#overview-6.sentence-2)

â *end note*]

[7](#overview-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[.](#overview-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[.](#overview-7.sentence-2)

[*Note [3](#overview-note-3)*:

vector<bool> is not a sequence container[.](#overview-7.sentence-3)

â *end note*]

[8](#overview-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[.](#overview-8.sentence-1)

[9](#overview-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[.](#overview-9.sentence-1)

[10](#overview-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"))[.](#overview-10.sentence-1)

#### [23.6.11.2](#defn) Definition [[flat.set.defn]](flat.set.defn)

namespace std {template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>class [flat_set](#lib:flat_set "23.6.11.2 Definition [flat.set.defn]") {public:// typesusing key_type = Key; using value_type = Key; using key_compare = Compare; using value_compare = Compare; using reference = value_type&; using const_reference = const value_type&; using size_type = typename KeyContainer::size_type; using difference_type = typename KeyContainer::difference_type; using iterator = *implementation-defined*; // see [[container.requirements]](container.requirements "23.2 Requirements")using const_iterator = *implementation-defined*; // see [[container.requirements]](container.requirements "23.2 Requirements")using reverse_iterator = std::reverse_iterator<iterator>; using const_reverse_iterator = std::reverse_iterator<const_iterator>; using container_type = KeyContainer; // [[flat.set.cons]](#cons "23.6.11.3 Constructors"), constructorsconstexpr flat_set() : flat_set(key_compare()) { }constexpr explicit flat_set(const key_compare& comp): *c*(), *compare*(comp) { }constexpr explicit flat_set(container_type cont, const key_compare& comp = key_compare()); constexpr flat_set(sorted_unique_t, container_type cont, const key_compare& comp = key_compare()): *c*(std::move(cont)), *compare*(comp) { }template<class InputIterator>constexpr flat_set(InputIterator first, InputIterator last, const key_compare& comp = key_compare()): *c*(), *compare*(comp){ insert(first, last); }template<class InputIterator>constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last, const key_compare& comp = key_compare()): *c*(first, last), *compare*(comp) { }template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<value_type> R>constexpr flat_set(from_range_t, R&& rg): flat_set(from_range, std::forward<R>(rg), key_compare()) { }template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<value_type> R>constexpr flat_set(from_range_t, R&& rg, const key_compare& comp): flat_set(comp){ insert_range(std::forward<R>(rg)); }constexpr flat_set(initializer_list<value_type> il, const key_compare& comp = key_compare()): flat_set(il.begin(), il.end(), comp) { }constexpr flat_set(sorted_unique_t, initializer_list<value_type> il, const key_compare& comp = key_compare()): flat_set(sorted_unique, il.begin(), il.end(), comp) { }// [[flat.set.cons.alloc]](#cons.alloc "23.6.11.4 Constructors with allocators"), constructors with allocatorstemplate<class Alloc>constexpr explicit flat_set(const Alloc& a); template<class Alloc>constexpr flat_set(const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_set(const container_type& cont, const Alloc& a); template<class Alloc>constexpr flat_set(const container_type& cont, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_set(sorted_unique_t, const container_type& cont, const Alloc& a); template<class Alloc>constexpr flat_set(sorted_unique_t, const container_type& cont, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_set(const flat_set&, const Alloc& a); template<class Alloc>constexpr flat_set(flat_set&&, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_set(InputIterator first, InputIterator last, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_set(InputIterator first, InputIterator last, const key_compare& comp, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last, const key_compare& comp, const Alloc& a); template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<value_type> R, class Alloc>constexpr flat_set(from_range_t, R&& rg, const Alloc& a); template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<value_type> R, class Alloc>constexpr flat_set(from_range_t, R&& rg, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_set(initializer_list<value_type> il, const Alloc& a); template<class Alloc>constexpr flat_set(initializer_list<value_type> il, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_set(sorted_unique_t, initializer_list<value_type> il, const Alloc& a); template<class Alloc>constexpr flat_set(sorted_unique_t, initializer_list<value_type> il, const key_compare& comp, const Alloc& a); constexpr flat_set& operator=(initializer_list<value_type>); // iteratorsconstexpr iterator begin() noexcept; constexpr const_iterator begin() const noexcept; constexpr iterator end() noexcept; constexpr const_iterator end() const noexcept; constexpr reverse_iterator rbegin() noexcept; constexpr const_reverse_iterator rbegin() const noexcept; constexpr reverse_iterator rend() noexcept; constexpr const_reverse_iterator rend() const noexcept; constexpr const_iterator cbegin() const noexcept; constexpr const_iterator cend() const noexcept; constexpr const_reverse_iterator crbegin() const noexcept; constexpr const_reverse_iterator crend() const noexcept; // capacityconstexpr bool empty() const noexcept; constexpr size_type size() const noexcept; constexpr size_type max_size() const noexcept; // [[flat.set.modifiers]](#modifiers "23.6.11.5 Modifiers"), modifierstemplate<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args); template<class... Args>constexpr iterator emplace_hint(const_iterator position, Args&&... args); constexpr pair<iterator, bool> insert(const value_type& x){ return emplace(x); }constexpr pair<iterator, bool> insert(value_type&& x){ return emplace(std::move(x)); }template<class K> constexpr pair<iterator, bool> insert(K&& x); constexpr iterator insert(const_iterator position, const value_type& x){ return emplace_hint(position, x); }constexpr iterator insert(const_iterator position, value_type&& x){ return emplace_hint(position, std::move(x)); }template<class K> constexpr iterator insert(const_iterator hint, K&& x); template<class InputIterator>constexpr void insert(InputIterator first, InputIterator last); template<class InputIterator>constexpr void insert(sorted_unique_t, InputIterator first, InputIterator last); template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<value_type> R>constexpr void insert_range(R&& rg); constexpr void insert(initializer_list<value_type> il){ insert(il.begin(), il.end()); }constexpr void insert(sorted_unique_t, initializer_list<value_type> il){ insert(sorted_unique, il.begin(), il.end()); }constexpr container_type extract() &&; constexpr void replace(container_type&&); constexpr iterator erase(iterator position); constexpr iterator erase(const_iterator position); constexpr size_type erase(const key_type& x); template<class K> constexpr size_type erase(K&& x); constexpr iterator erase(const_iterator first, const_iterator last); constexpr void swap(flat_set& y) noexcept; constexpr void clear() noexcept; // observersconstexpr key_compare key_comp() const; constexpr value_compare value_comp() const; // set operationsconstexpr iterator find(const key_type& x); constexpr const_iterator find(const key_type& x) const; template<class K> constexpr iterator find(const K& x); template<class K> constexpr const_iterator find(const K& x) const; constexpr size_type count(const key_type& x) const; template<class K> constexpr size_type count(const K& x) const; constexpr bool contains(const key_type& x) const; template<class K> constexpr bool contains(const K& x) const; constexpr iterator lower_bound(const key_type& x); constexpr const_iterator lower_bound(const key_type& x) const; template<class K> constexpr iterator lower_bound(const K& x); template<class K> constexpr const_iterator lower_bound(const K& x) const; constexpr iterator upper_bound(const key_type& x); constexpr const_iterator upper_bound(const key_type& x) const; template<class K> constexpr iterator upper_bound(const K& x); template<class K> constexpr const_iterator upper_bound(const K& x) const; constexpr pair<iterator, iterator> equal_range(const key_type& x); constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const; template<class K>constexpr pair<iterator, iterator> equal_range(const K& x); template<class K>constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const; friend constexpr bool operator==(const flat_set& x, const flat_set& y); friend constexpr *synth-three-way-result*<value_type>operator<=>(const flat_set& x, const flat_set& y); friend constexpr void swap(flat_set& x, flat_set& y) noexcept { x.swap(y); }private: container_type *c*; // *exposition only* key_compare *compare*; // *exposition only*}; template<class KeyContainer, class Compare = less<typename KeyContainer::value_type>> flat_set(KeyContainer, Compare = Compare())-> flat_set<typename KeyContainer::value_type, Compare, KeyContainer>; template<class KeyContainer, class Allocator> flat_set(KeyContainer, Allocator)-> flat_set<typename KeyContainer::value_type,
 less<typename KeyContainer::value_type>, KeyContainer>; template<class KeyContainer, class Compare, class Allocator> flat_set(KeyContainer, Compare, Allocator)-> flat_set<typename KeyContainer::value_type, Compare, KeyContainer>; template<class KeyContainer, class Compare = less<typename KeyContainer::value_type>> flat_set(sorted_unique_t, KeyContainer, Compare = Compare())-> flat_set<typename KeyContainer::value_type, Compare, KeyContainer>; template<class KeyContainer, class Allocator> flat_set(sorted_unique_t, KeyContainer, Allocator)-> flat_set<typename KeyContainer::value_type,
 less<typename KeyContainer::value_type>, KeyContainer>; template<class KeyContainer, class Compare, class Allocator> flat_set(sorted_unique_t, KeyContainer, Compare, Allocator)-> flat_set<typename KeyContainer::value_type, Compare, KeyContainer>; template<class InputIterator, class Compare = less<*iter-value-type*<InputIterator>>> flat_set(InputIterator, InputIterator, Compare = Compare())-> flat_set<*iter-value-type*<InputIterator>, Compare>; template<class InputIterator, class Compare = less<*iter-value-type*<InputIterator>>> flat_set(sorted_unique_t, InputIterator, InputIterator, Compare = Compare())-> flat_set<*iter-value-type*<InputIterator>, Compare>; template<ranges::[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Compare = less<ranges::range_value_t<R>>, class Allocator = allocator<ranges::range_value_t<R>>> flat_set(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())-> flat_set<ranges::range_value_t<R>, Compare,
 vector<ranges::range_value_t<R>, *alloc-rebind*<Allocator, ranges::range_value_t<R>>>>; template<ranges::[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Allocator> flat_set(from_range_t, R&&, Allocator)-> flat_set<ranges::range_value_t<R>, less<ranges::range_value_t<R>>,
 vector<ranges::range_value_t<R>, *alloc-rebind*<Allocator, ranges::range_value_t<R>>>>; template<class Key, class Compare = less<Key>> flat_set(initializer_list<Key>, Compare = Compare())-> flat_set<Key, Compare>; template<class Key, class Compare = less<Key>> flat_set(sorted_unique_t, initializer_list<Key>, Compare = Compare())-> flat_set<Key, Compare>; template<class Key, class Compare, class KeyContainer, class Allocator>struct uses_allocator<flat_set<Key, Compare, KeyContainer>, Allocator>: bool_constant<uses_allocator_v<KeyContainer, Allocator>> { };}

#### [23.6.11.3](#cons) Constructors [[flat.set.cons]](flat.set.cons)

[ð](#lib:flat_set,constructor)

`constexpr explicit flat_set(container_type cont, const key_compare& comp = key_compare());
`

[1](#cons-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19167)

*Effects*: Initializes *c* with std​::​move(cont) and*compare* with comp,
sorts the range [begin(), end()) with respect to *compare*, and
finally erases all but the first element
from each group of consecutive equivalent elements[.](#cons-1.sentence-1)

[2](#cons-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19175)

*Complexity*: Linear in N if cont is already sorted with respect to *compare* and
otherwise NlogN, where N is the value of cont.size() before this call[.](#cons-2.sentence-1)

#### [23.6.11.4](#cons.alloc) Constructors with allocators [[flat.set.cons.alloc]](flat.set.cons.alloc)

[1](#cons.alloc-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19183)

The constructors in this subclause shall not participate in overload resolution
unless uses_allocator_v<container_type, Alloc> is true[.](#cons.alloc-1.sentence-1)

[ð](#lib:flat_set,constructor_)

`template<class Alloc>
  constexpr flat_set(const container_type& cont, const Alloc& a);
template<class Alloc>
  constexpr flat_set(const container_type& cont, const key_compare& comp, const Alloc& a);
`

[2](#cons.alloc-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19196)

*Effects*: Equivalent toflat_set(cont) and flat_set(cont, comp), respectively,
except that *c* is constructed with
uses-allocator construction ([[allocator.uses.construction]](allocator.uses.construction "20.2.8.2 Uses-allocator construction"))[.](#cons.alloc-2.sentence-1)

[3](#cons.alloc-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19203)

*Complexity*: Same as flat_set(cont) and flat_set(cont, comp), respectively[.](#cons.alloc-3.sentence-1)

[ð](#lib:flat_set,constructor__)

`template<class Alloc>
  constexpr flat_set(sorted_unique_t, const container_type& cont, const Alloc& a);
template<class Alloc>
  constexpr flat_set(sorted_unique_t, const container_type& cont,
                     const key_compare& comp, const Alloc& a);
`

[4](#cons.alloc-4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19218)

*Effects*: Equivalent toflat_set(sorted_unique, cont) andflat_set(sorted_unique, cont,  
comp), respectively,
except that *c* is constructed with
uses-allocator construction ([[allocator.uses.construction]](allocator.uses.construction "20.2.8.2 Uses-allocator construction"))[.](#cons.alloc-4.sentence-1)

[5](#cons.alloc-5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19226)

*Complexity*: Linear[.](#cons.alloc-5.sentence-1)

[ð](#lib:flat_set,constructor___)

`template<class Alloc>
  constexpr explicit flat_set(const Alloc& a);
template<class Alloc>
  constexpr flat_set(const key_compare& comp, const Alloc& a);
template<class Alloc>
  constexpr flat_set(const flat_set&, const Alloc& a);
template<class Alloc>
  constexpr flat_set(flat_set&&, const Alloc& a);
template<class InputIterator, class Alloc>
  constexpr flat_set(InputIterator first, InputIterator last, const Alloc& a);
template<class InputIterator, class Alloc>
  constexpr flat_set(InputIterator first, InputIterator last, const key_compare& comp,
                     const Alloc& a);
template<class InputIterator, class Alloc>
  constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last, const Alloc& a);
template<class InputIterator, class Alloc>
  constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last,
                     const key_compare& comp, const Alloc& a);
template<[container-compatible-range](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<value_type> R, class Alloc>
  constexpr flat_set(from_range_t, R&& rg, const Alloc& a);
template<[container-compatible-range](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<value_type> R, class Alloc>
  constexpr flat_set(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
template<class Alloc>
  constexpr flat_set(initializer_list<value_type> il, const Alloc& a);
template<class Alloc>
  constexpr flat_set(initializer_list<value_type> il, const key_compare& comp, const Alloc& a);
template<class Alloc>
  constexpr flat_set(sorted_unique_t, initializer_list<value_type> il, const Alloc& a);
template<class Alloc>
  constexpr flat_set(sorted_unique_t, initializer_list<value_type> il,
                     const key_compare& comp, const Alloc& a);
`

[6](#cons.alloc-6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19267)

*Effects*: Equivalent to the corresponding non-allocator constructors
except that *c* is constructed with
uses-allocator construction ([[allocator.uses.construction]](allocator.uses.construction "20.2.8.2 Uses-allocator construction"))[.](#cons.alloc-6.sentence-1)

#### [23.6.11.5](#modifiers) Modifiers [[flat.set.modifiers]](flat.set.modifiers)

[ð](#lib:insert,flat_set)

`template<class K> constexpr pair<iterator, bool> insert(K&& x);
template<class K> constexpr iterator insert(const_iterator hint, K&& x);
`

[1](#modifiers-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19283)

*Constraints*: The [*qualified-id*](expr.prim.id.qual#nt:qualified-id "7.5.5.3 Qualified names [expr.prim.id.qual]") Compare​::​is_transparent is valid and denotes a type[.](#modifiers-1.sentence-1)

is_constructible_v<value_type, K> is true[.](#modifiers-1.sentence-2)

[2](#modifiers-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19289)

*Preconditions*: The conversion from x into value_type constructs
an object u, for which find(x) == find(u) is true[.](#modifiers-2.sentence-1)

[3](#modifiers-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19294)

*Effects*: If the set already contains an element equivalent to x,*this and x are unchanged[.](#modifiers-3.sentence-1)

Otherwise,
inserts a new element as if by emplace(std​::​forward<K>(x))[.](#modifiers-3.sentence-2)

[4](#modifiers-4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19301)

*Returns*: In the first overload,
the bool component of the returned pair is true if and only if the insertion took place[.](#modifiers-4.sentence-1)

The returned iterator points to the element
whose key is equivalent to x[.](#modifiers-4.sentence-2)

[ð](#lib:insert,flat_set_)

`template<class InputIterator>
  constexpr void insert(InputIterator first, InputIterator last);
`

[5](#modifiers-5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19317)

*Effects*: Adds elements to *c* as if by:*c*.insert(*c*.end(), first, last);

Then,
sorts the range of newly inserted elements with respect to *compare*;
merges the resulting sorted range and
the sorted range of pre-existing elements into a single sorted range; and
finally erases all but the first element
from each group of consecutive equivalent elements[.](#modifiers-5.sentence-2)

[6](#modifiers-6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19330)

*Complexity*: N + MlogM, where N is size() before the operation andM is distance(first, last)[.](#modifiers-6.sentence-1)

[7](#modifiers-7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19335)

*Remarks*: Since this operation performs an in-place merge, it may allocate memory[.](#modifiers-7.sentence-1)

[ð](#lib:insert,flat_set__)

`template<class InputIterator>
  constexpr void insert(sorted_unique_t, InputIterator first, InputIterator last);
`

[8](#modifiers-8)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19347)

*Effects*: Equivalent to insert(first, last)[.](#modifiers-8.sentence-1)

[9](#modifiers-9)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19351)

*Complexity*: Linear[.](#modifiers-9.sentence-1)

[ð](#lib:insert_range,flat_set)

`template<[container-compatible-range](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<value_type> R>
  constexpr void insert_range(R&& rg);
`

[10](#modifiers-10)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19363)

*Effects*: Adds elements to *c* as if by:for (const auto& e : rg) {*c*.insert(*c*.end(), e);}

Then,
sorts the range of newly inserted elements with respect to *compare*;
merges the resulting sorted range and
the sorted range of pre-existing elements into a single sorted range; and
finally erases all but the first element
from each group of consecutive equivalent elements[.](#modifiers-10.sentence-2)

[11](#modifiers-11)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19378)

*Complexity*: N + MlogM, where N is size() before the operation and M is ranges​::​distance(rg)[.](#modifiers-11.sentence-1)

[12](#modifiers-12)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19383)

*Remarks*: Since this operation performs an in-place merge, it may allocate memory[.](#modifiers-12.sentence-1)

[ð](#lib:swap,flat_set)

`constexpr void swap(flat_set& y) noexcept;
`

[13](#modifiers-13)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19394)

*Effects*: Equivalent to:ranges::swap(*compare*, y.*compare*);
ranges::swap(*c*, y.*c*);

[ð](#lib:extract,flat_set)

`constexpr container_type extract() &&;
`

[14](#modifiers-14)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19409)

*Postconditions*: *this is emptied, even if the function exits via an exception[.](#modifiers-14.sentence-1)

[15](#modifiers-15)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19413)

*Returns*: std​::​move(*c*)[.](#modifiers-15.sentence-1)

[ð](#lib:replace,flat_set)

`constexpr void replace(container_type&& cont);
`

[16](#modifiers-16)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19424)

*Preconditions*: The elements of cont are sorted with respect to *compare*, andcont contains no equal elements[.](#modifiers-16.sentence-1)

[17](#modifiers-17)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19429)

*Effects*: Equivalent to: *c* = std​::​move(cont);

#### [23.6.11.6](#erasure) Erasure [[flat.set.erasure]](flat.set.erasure)

[ð](#lib:erase_if,flat_set)

`template<class Key, class Compare, class KeyContainer, class Predicate>
  constexpr typename flat_set<Key, Compare, KeyContainer>::size_type
    erase_if(flat_set<Key, Compare, KeyContainer>& c, Predicate pred);
`

[1](#erasure-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19444)

*Preconditions*: Key meets the *Cpp17MoveAssignable* requirements[.](#erasure-1.sentence-1)

[2](#erasure-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19448)

*Effects*: Let E be bool(pred(as_const(e)))[.](#erasure-2.sentence-1)

Erases all elements e in c for which E holds[.](#erasure-2.sentence-2)

[3](#erasure-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19453)

*Returns*: The number of elements erased[.](#erasure-3.sentence-1)

[4](#erasure-4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19457)

*Complexity*: Exactly c.size() applications of the predicate[.](#erasure-4.sentence-1)

[5](#erasure-5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19461)

*Remarks*: Stable ([[algorithm.stable]](algorithm.stable "16.4.6.8 Requirements for stable algorithms"))[.](#erasure-5.sentence-1)

If an invocation of erase_if exits via an exception,c is in a valid but unspecified state ([[defns.valid]](defns.valid "3.67 valid but unspecified state"))[.](#erasure-5.sentence-2)

[*Note [1](#erasure-note-1)*:

c still meets its invariants, but can be empty[.](#erasure-5.sentence-3)

â *end note*]
