3306 lines
206 KiB
Markdown
3306 lines
206 KiB
Markdown
[container.adaptors]
|
||
|
||
# 23 Containers library [[containers]](./#containers)
|
||
|
||
## 23.6 Container adaptors [container.adaptors]
|
||
|
||
### [23.6.1](#general) General [[container.adaptors.general]](container.adaptors.general)
|
||
|
||
[1](#general-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15483)
|
||
|
||
The headers[<queue>](#header:%3cqueue%3e "23.6.2 Header <queue> synopsis [queue.syn]"),[<stack>](#header:%3cstack%3e "23.6.5 Header <stack> synopsis [stack.syn]"),[<flat_map>](#header:%3cflat_map%3e "23.6.7 Header <flat_map> synopsis [flat.map.syn]"),
|
||
and [<flat_set>](#header:%3cflat_set%3e "23.6.10 Header <flat_set> synopsis [flat.set.syn]") define the container adaptorsqueue and priority_queue,stack,flat_map and flat_multimap,
|
||
and flat_set and flat_multiset,
|
||
respectively[.](#general-1.sentence-1)
|
||
|
||
[2](#general-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15496)
|
||
|
||
Each container adaptor takes
|
||
one or more template parameters
|
||
named Container, KeyContainer, or MappedContainer that denote the types of containers that the container adaptor adapts[.](#general-2.sentence-1)
|
||
|
||
Each container adaptor has at least one constructor
|
||
that takes a reference argument to one or more such template parameters[.](#general-2.sentence-2)
|
||
|
||
For each constructor reference argument to a container C,
|
||
the constructor copies the container into the container adaptor[.](#general-2.sentence-3)
|
||
|
||
If C takes an allocator, then a compatible allocator may be passed in
|
||
to the adaptor's constructor[.](#general-2.sentence-4)
|
||
|
||
Otherwise, normal copy or move construction is used for the container
|
||
argument[.](#general-2.sentence-5)
|
||
|
||
For the container adaptors
|
||
that take a single container template parameter Container,
|
||
the first template parameter T of the container adaptor
|
||
shall denote the same type as Container::value_type[.](#general-2.sentence-6)
|
||
|
||
[3](#general-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15513)
|
||
|
||
For container adaptors, no swap function throws an exception unless that
|
||
exception is thrown by the swap of the adaptor'sContainer,KeyContainer,MappedContainer, orCompare object (if any)[.](#general-3.sentence-1)
|
||
|
||
[4](#general-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15521)
|
||
|
||
A constructor template of a container adaptor
|
||
shall not participate in overload resolution
|
||
if it has an InputIterator template parameter and
|
||
a type that does not qualify as an input iterator is deduced for that parameter[.](#general-4.sentence-1)
|
||
|
||
[5](#general-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15527)
|
||
|
||
For container adaptors that have them,
|
||
the insert, emplace, and erase members
|
||
affect the validity of iterators, references, and pointers
|
||
to the adaptor's container(s) in the same way that
|
||
the containers' respectiveinsert, emplace, and erase members do[.](#general-5.sentence-1)
|
||
|
||
[*Example [1](#general-example-1)*:
|
||
|
||
A call to flat_map<Key, T>::insert can invalidate all iterators to the flat_map[.](#general-5.sentence-2)
|
||
|
||
â *end example*]
|
||
|
||
[6](#general-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15539)
|
||
|
||
A deduction guide for a container adaptor shall not participate in overload resolution if any of the following are true:
|
||
|
||
- [(6.1)](#general-6.1)
|
||
|
||
It has an InputIterator template parameter and a type that does not qualify as an input iterator is deduced for that parameter[.](#general-6.1.sentence-1)
|
||
|
||
- [(6.2)](#general-6.2)
|
||
|
||
It has a Compare template parameter and a type that qualifies as an allocator is deduced for that parameter[.](#general-6.2.sentence-1)
|
||
|
||
- [(6.3)](#general-6.3)
|
||
|
||
It has a Container, KeyContainer, or MappedContainer template parameter and a type that qualifies as an allocator is deduced for that parameter[.](#general-6.3.sentence-1)
|
||
|
||
- [(6.4)](#general-6.4)
|
||
|
||
It has no Container, KeyContainer, or MappedContainer template parameter, and it has an Allocator template parameter, and a type that does not qualify as an allocator is deduced for that parameter[.](#general-6.4.sentence-1)
|
||
|
||
- [(6.5)](#general-6.5)
|
||
|
||
It has both Container and Allocator template parameters, and uses_allocator_v<Container, Allocator> is false[.](#general-6.5.sentence-1)
|
||
|
||
- [(6.6)](#general-6.6)
|
||
|
||
It has both KeyContainer and Allocator template parameters, anduses_allocator_v<KeyContainer, Allocator> is false[.](#general-6.6.sentence-1)
|
||
|
||
- [(6.7)](#general-6.7)
|
||
|
||
It has both KeyContainer and Compare template parameters, andis_invocable_v<const Compare&, const typename KeyContainer::value_type&, const typename KeyContainer::value_type&> is not a valid expression or is false[.](#general-6.7.sentence-1)
|
||
|
||
- [(6.8)](#general-6.8)
|
||
|
||
It has both MappedContainer and Allocator template parameters, anduses_allocator_v<MappedContainer, Allocator> is false[.](#general-6.8.sentence-1)
|
||
|
||
[7](#general-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15560)
|
||
|
||
The exposition-only alias template *iter-value-type* defined in [[sequences.general]](sequences.general "23.3.1 General") and
|
||
the exposition-only alias templates *iter-key-type*, *iter-mapped-type*,*range-key-type*, and *range-mapped-type* defined in [[associative.general]](associative.general "23.4.1 General") may appear in deduction guides for container adaptors[.](#general-7.sentence-1)
|
||
|
||
[8](#general-8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15568)
|
||
|
||
The following exposition-only alias template
|
||
may appear in deduction guides for container adaptors:template<class Allocator, class T>using *alloc-rebind* = // *exposition only*typename allocator_traits<Allocator>::template rebind_alloc<T>;
|
||
|
||
### [23.6.2](#queue.syn) Header <queue> synopsis [[queue.syn]](queue.syn)
|
||
|
||
[ð](#header:%3cqueue%3e)
|
||
|
||
#include <compare> // see [[compare.syn]](compare.syn "17.12.1 Header <compare> synopsis")#include <initializer_list> // see [[initializer.list.syn]](initializer.list.syn "17.11.2 Header <initializer_list> synopsis")namespace std {// [[queue]](#queue "23.6.3 Class template queue"), class template queuetemplate<class T, class Container = deque<T>> class queue; template<class T, class Container>constexpr bool operator==(const queue<T, Container>& x, const queue<T, Container>& y); template<class T, class Container>constexpr bool operator!=(const queue<T, Container>& x, const queue<T, Container>& y); template<class T, class Container>constexpr bool operator< (const queue<T, Container>& x, const queue<T, Container>& y); template<class T, class Container>constexpr bool operator> (const queue<T, Container>& x, const queue<T, Container>& y); template<class T, class Container>constexpr bool operator<=(const queue<T, Container>& x, const queue<T, Container>& y); template<class T, class Container>constexpr bool operator>=(const queue<T, Container>& x, const queue<T, Container>& y); template<class T, [three_way_comparable](cmp.concept#concept:three_way_comparable "17.12.4 Concept three_way_comparable [cmp.concept]") Container>constexpr compare_three_way_result_t<Container>operator<=>(const queue<T, Container>& x, const queue<T, Container>& y); template<class T, class Container>constexpr void swap(queue<T, Container>& x, queue<T, Container>& y)noexcept(noexcept(x.swap(y))); template<class T, class Container, class Alloc>struct uses_allocator<queue<T, Container>, Alloc>; // [[container.adaptors.format]](#format "23.6.13 Container adaptors formatting"), formatter specialization for queuetemplate<class charT, class T, [formattable](format.formattable#concept:formattable "28.5.6.3 Concept formattable [format.formattable]")<charT> Container>struct formatter<queue<T, Container>, charT>; // [[priority.queue]](#priority.queue "23.6.4 Class template priority_queue"), class template priority_queuetemplate<class T, class Container = vector<T>, class Compare = less<typename Container::value_type>>class priority_queue; template<class T, class Container, class Compare>constexpr void swap(priority_queue<T, Container, Compare>& x,
|
||
priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y))); template<class T, class Container, class Compare, class Alloc>struct uses_allocator<priority_queue<T, Container, Compare>, Alloc>; // [[container.adaptors.format]](#format "23.6.13 Container adaptors formatting"), formatter specialization for priority_queuetemplate<class charT, class T, [formattable](format.formattable#concept:formattable "28.5.6.3 Concept formattable [format.formattable]")<charT> Container, class Compare>struct formatter<priority_queue<T, Container, Compare>, charT>;}
|
||
|
||
### [23.6.3](#queue) Class template queue [[queue]](queue)
|
||
|
||
#### [23.6.3.1](#queue.defn) Definition [[queue.defn]](queue.defn)
|
||
|
||
[1](#queue.defn-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15635)
|
||
|
||
Any sequence container supporting operationsfront(),back(),push_back() andpop_front() can be used to instantiatequeue[.](#queue.defn-1.sentence-1)
|
||
|
||
In particular,<list> and<deque> can be used[.](#queue.defn-1.sentence-2)
|
||
|
||
namespace std {template<class T, class Container = deque<T>>class queue {public:using value_type = typename Container::value_type; using reference = typename Container::reference; using const_reference = typename Container::const_reference; using size_type = typename Container::size_type; using container_type = Container; protected: Container c; public:constexpr queue() : queue(Container()) {}constexpr explicit queue(const Container&); constexpr explicit queue(Container&&); template<class InputIterator> constexpr queue(InputIterator first, InputIterator last); template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R> constexpr queue(from_range_t, R&& rg); template<class Alloc> constexpr explicit queue(const Alloc&); template<class Alloc> constexpr queue(const Container&, const Alloc&); template<class Alloc> constexpr queue(Container&&, const Alloc&); template<class Alloc> constexpr queue(const queue&, const Alloc&); template<class Alloc> constexpr queue(queue&&, const Alloc&); template<class InputIterator, class Alloc>constexpr queue(InputIterator first, InputIterator last, const Alloc&); template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R, class Alloc>constexpr queue(from_range_t, R&& rg, const Alloc&); constexpr bool empty() const { return c.empty(); }constexpr size_type size() const { return c.size(); }constexpr reference front() { return c.front(); }constexpr const_reference front() const { return c.front(); }constexpr reference back() { return c.back(); }constexpr const_reference back() const { return c.back(); }constexpr void push(const value_type& x) { c.push_back(x); }constexpr void push(value_type&& x) { c.push_back(std::move(x)); }template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R> constexpr void push_range(R&& rg); template<class... Args>constexpr decltype(auto) emplace(Args&&... args){ return c.emplace_back(std::forward<Args>(args)...); }constexpr void pop() { c.pop_front(); }constexpr void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>){ using std::swap; swap(c, q.c); }}; template<class Container> queue(Container) -> queue<typename Container::value_type, Container>; template<class InputIterator> queue(InputIterator, InputIterator) -> queue<*iter-value-type*<InputIterator>>; template<ranges::[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R> queue(from_range_t, R&&) -> queue<ranges::range_value_t<R>>; template<class Container, class Allocator> queue(Container, Allocator) -> queue<typename Container::value_type, Container>; template<class InputIterator, class Allocator> queue(InputIterator, InputIterator, Allocator)-> queue<*iter-value-type*<InputIterator>, deque<*iter-value-type*<InputIterator>,
|
||
Allocator>>; template<ranges::[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Allocator> queue(from_range_t, R&&, Allocator)-> queue<ranges::range_value_t<R>, deque<ranges::range_value_t<R>, Allocator>>; template<class T, class Container, class Alloc>struct uses_allocator<queue<T, Container>, Alloc>: uses_allocator<Container, Alloc>::type { };}
|
||
|
||
#### [23.6.3.2](#queue.cons) Constructors [[queue.cons]](queue.cons)
|
||
|
||
[ð](#lib:queue,constructor)
|
||
|
||
`constexpr explicit queue(const Container& cont);
|
||
`
|
||
|
||
[1](#queue.cons-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15733)
|
||
|
||
*Effects*: Initializes c with cont[.](#queue.cons-1.sentence-1)
|
||
|
||
[ð](#lib:queue,constructor_)
|
||
|
||
`constexpr explicit queue(Container&& cont);
|
||
`
|
||
|
||
[2](#queue.cons-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15744)
|
||
|
||
*Effects*: Initializes c with std::move(cont)[.](#queue.cons-2.sentence-1)
|
||
|
||
[ð](#lib:queue,constructor__)
|
||
|
||
`template<class InputIterator>
|
||
constexpr queue(InputIterator first, InputIterator last);
|
||
`
|
||
|
||
[3](#queue.cons-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15756)
|
||
|
||
*Effects*: Initializes c withfirst as the first argument and last as the second argument[.](#queue.cons-3.sentence-1)
|
||
|
||
[ð](#lib:queue,constructor___)
|
||
|
||
`template<[container-compatible-range](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R>
|
||
constexpr queue(from_range_t, R&& rg);
|
||
`
|
||
|
||
[4](#queue.cons-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15769)
|
||
|
||
*Effects*: Initializes c with ranges::to<Container>(std::forward<R>(rg))[.](#queue.cons-4.sentence-1)
|
||
|
||
#### [23.6.3.3](#queue.cons.alloc) Constructors with allocators [[queue.cons.alloc]](queue.cons.alloc)
|
||
|
||
[1](#queue.cons.alloc-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15776)
|
||
|
||
If uses_allocator_v<container_type, Alloc> is false the constructors in this subclause shall not participate in overload resolution[.](#queue.cons.alloc-1.sentence-1)
|
||
|
||
[ð](#lib:queue,constructor____)
|
||
|
||
`template<class Alloc> constexpr explicit queue(const Alloc& a);
|
||
`
|
||
|
||
[2](#queue.cons.alloc-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15786)
|
||
|
||
*Effects*: Initializes c with a[.](#queue.cons.alloc-2.sentence-1)
|
||
|
||
[ð](#lib:queue,constructor_____)
|
||
|
||
`template<class Alloc> constexpr queue(const container_type& cont, const Alloc& a);
|
||
`
|
||
|
||
[3](#queue.cons.alloc-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15797)
|
||
|
||
*Effects*: Initializes c with cont as the first argument and a as the second argument[.](#queue.cons.alloc-3.sentence-1)
|
||
|
||
[ð](#lib:queue,constructor______)
|
||
|
||
`template<class Alloc> constexpr queue(container_type&& cont, const Alloc& a);
|
||
`
|
||
|
||
[4](#queue.cons.alloc-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15809)
|
||
|
||
*Effects*: Initializes c with std::move(cont) as the first argument and a as the second argument[.](#queue.cons.alloc-4.sentence-1)
|
||
|
||
[ð](#lib:queue,constructor_______)
|
||
|
||
`template<class Alloc> constexpr queue(const queue& q, const Alloc& a);
|
||
`
|
||
|
||
[5](#queue.cons.alloc-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15821)
|
||
|
||
*Effects*: Initializes c with q.c as the first argument and a as the
|
||
second argument[.](#queue.cons.alloc-5.sentence-1)
|
||
|
||
[ð](#lib:queue,constructor________)
|
||
|
||
`template<class Alloc> constexpr queue(queue&& q, const Alloc& a);
|
||
`
|
||
|
||
[6](#queue.cons.alloc-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15833)
|
||
|
||
*Effects*: Initializes c with std::move(q.c) as the first argument and a as the second argument[.](#queue.cons.alloc-6.sentence-1)
|
||
|
||
[ð](#lib:queue,constructor_________)
|
||
|
||
`template<class InputIterator, class Alloc>
|
||
constexpr queue(InputIterator first, InputIterator last, const Alloc& alloc);
|
||
`
|
||
|
||
[7](#queue.cons.alloc-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15846)
|
||
|
||
*Effects*: Initializes c withfirst as the first argument,last as the second argument, andalloc as the third argument[.](#queue.cons.alloc-7.sentence-1)
|
||
|
||
[ð](#lib:queue,constructor__________)
|
||
|
||
`template<[container-compatible-range](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R, class Alloc>
|
||
constexpr queue(from_range_t, R&& rg, const Alloc& a);
|
||
`
|
||
|
||
[8](#queue.cons.alloc-8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15861)
|
||
|
||
*Effects*: Initializes c withranges::to<Container>(std::forward<R>(rg), a)[.](#queue.cons.alloc-8.sentence-1)
|
||
|
||
#### [23.6.3.4](#queue.mod) Modifiers [[queue.mod]](queue.mod)
|
||
|
||
[ð](#lib:push_range,queue)
|
||
|
||
`template<[container-compatible-range](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R>
|
||
constexpr void push_range(R&& rg);
|
||
`
|
||
|
||
[1](#queue.mod-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15876)
|
||
|
||
*Effects*: Equivalent to c.append_range(std::forward<R>(rg)) if that is a valid expression,
|
||
otherwise ranges::copy(rg, back_inserter(c))[.](#queue.mod-1.sentence-1)
|
||
|
||
#### [23.6.3.5](#queue.ops) Operators [[queue.ops]](queue.ops)
|
||
|
||
[ð](#lib:operator==,queue)
|
||
|
||
`template<class T, class Container>
|
||
constexpr bool operator==(const queue<T, Container>& x, const queue<T, Container>& y);
|
||
`
|
||
|
||
[1](#queue.ops-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15892)
|
||
|
||
*Returns*: x.c == y.c[.](#queue.ops-1.sentence-1)
|
||
|
||
[ð](#lib:operator!=,queue)
|
||
|
||
`template<class T, class Container>
|
||
constexpr bool operator!=(const queue<T, Container>& x, const queue<T, Container>& y);
|
||
`
|
||
|
||
[2](#queue.ops-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15904)
|
||
|
||
*Returns*: x.c != y.c[.](#queue.ops-2.sentence-1)
|
||
|
||
[ð](#lib:operator%3c,queue)
|
||
|
||
`template<class T, class Container>
|
||
constexpr bool operator< (const queue<T, Container>& x, const queue<T, Container>& y);
|
||
`
|
||
|
||
[3](#queue.ops-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15916)
|
||
|
||
*Returns*: x.c < y.c[.](#queue.ops-3.sentence-1)
|
||
|
||
[ð](#lib:operator%3e,queue)
|
||
|
||
`template<class T, class Container>
|
||
constexpr bool operator> (const queue<T, Container>& x, const queue<T, Container>& y);
|
||
`
|
||
|
||
[4](#queue.ops-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15928)
|
||
|
||
*Returns*: x.c > y.c[.](#queue.ops-4.sentence-1)
|
||
|
||
[ð](#lib:operator%3c=,queue)
|
||
|
||
`template<class T, class Container>
|
||
constexpr bool operator<=(const queue<T, Container>& x, const queue<T, Container>& y);
|
||
`
|
||
|
||
[5](#queue.ops-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15940)
|
||
|
||
*Returns*: x.c <= y.c[.](#queue.ops-5.sentence-1)
|
||
|
||
[ð](#lib:operator%3e=,queue)
|
||
|
||
`template<class T, class Container>
|
||
constexpr bool operator>=(const queue<T, Container>& x, const queue<T, Container>& y);
|
||
`
|
||
|
||
[6](#queue.ops-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15952)
|
||
|
||
*Returns*: x.c >= y.c[.](#queue.ops-6.sentence-1)
|
||
|
||
[ð](#lib:operator%3c=%3e,queue)
|
||
|
||
`template<class T, [three_way_comparable](cmp.concept#concept:three_way_comparable "17.12.4 Concept three_way_comparable [cmp.concept]") Container>
|
||
constexpr compare_three_way_result_t<Container>
|
||
operator<=>(const queue<T, Container>& x, const queue<T, Container>& y);
|
||
`
|
||
|
||
[7](#queue.ops-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15965)
|
||
|
||
*Returns*: x.c <=> y.c[.](#queue.ops-7.sentence-1)
|
||
|
||
#### [23.6.3.6](#queue.special) Specialized algorithms [[queue.special]](queue.special)
|
||
|
||
[ð](#lib:swap,queue)
|
||
|
||
`template<class T, class Container>
|
||
constexpr void swap(queue<T, Container>& x, queue<T, Container>& y)
|
||
noexcept(noexcept(x.swap(y)));
|
||
`
|
||
|
||
[1](#queue.special-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15980)
|
||
|
||
*Constraints*: is_swappable_v<Container> is true[.](#queue.special-1.sentence-1)
|
||
|
||
[2](#queue.special-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15984)
|
||
|
||
*Effects*: As if by x.swap(y)[.](#queue.special-2.sentence-1)
|
||
|
||
### [23.6.4](#priority.queue) Class template priority_queue [[priority.queue]](priority.queue)
|
||
|
||
#### [23.6.4.1](#priqueue.overview) Overview [[priqueue.overview]](priqueue.overview)
|
||
|
||
[1](#priqueue.overview-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L15993)
|
||
|
||
Any sequence container with random access iterator and supporting operationsfront(),push_back() andpop_back() can be used to instantiatepriority_queue[.](#priqueue.overview-1.sentence-1)
|
||
|
||
In particular,<vector> and<deque> can be used[.](#priqueue.overview-1.sentence-2)
|
||
|
||
Instantiatingpriority_queue also involves supplying a function or function object for making
|
||
priority comparisons; the library assumes that the function or function
|
||
object defines a [strict weak ordering](alg.sorting "26.8 Sorting and related operations [alg.sorting]")[.](#priqueue.overview-1.sentence-3)
|
||
|
||
namespace std {template<class T, class Container = vector<T>, class Compare = less<typename Container::value_type>>class priority_queue {public:using value_type = typename Container::value_type; using reference = typename Container::reference; using const_reference = typename Container::const_reference; using size_type = typename Container::size_type; using container_type = Container; using value_compare = Compare; protected: Container c;
|
||
Compare comp; public:constexpr priority_queue() : priority_queue(Compare()) {}constexpr explicit priority_queue(const Compare& x) : priority_queue(x, Container()) {}constexpr priority_queue(const Compare& x, const Container&); constexpr priority_queue(const Compare& x, Container&&); template<class InputIterator>constexpr priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare()); template<class InputIterator>constexpr priority_queue(InputIterator first, InputIterator last, const Compare& x, const Container&); template<class InputIterator>constexpr priority_queue(InputIterator first, InputIterator last, const Compare& x,
|
||
Container&&); template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R>constexpr priority_queue(from_range_t, R&& rg, const Compare& x = Compare()); template<class Alloc> constexpr explicit priority_queue(const Alloc&); template<class Alloc> constexpr priority_queue(const Compare&, const Alloc&); template<class Alloc>constexpr priority_queue(const Compare&, const Container&, const Alloc&); template<class Alloc> constexpr priority_queue(const Compare&, Container&&, const Alloc&); template<class Alloc> constexpr priority_queue(const priority_queue&, const Alloc&); template<class Alloc> constexpr priority_queue(priority_queue&&, const Alloc&); template<class InputIterator, class Alloc>constexpr priority_queue(InputIterator, InputIterator, const Alloc&); template<class InputIterator, class Alloc>constexpr priority_queue(InputIterator, InputIterator, const Compare&, const Alloc&); template<class InputIterator, class Alloc>constexpr priority_queue(InputIterator, InputIterator, const Compare&, const Container&, const Alloc&); template<class InputIterator, class Alloc>constexpr priority_queue(InputIterator, InputIterator, const Compare&, Container&&, const Alloc&); template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R, class Alloc>constexpr priority_queue(from_range_t, R&& rg, const Compare&, const Alloc&); template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R, class Alloc>constexpr priority_queue(from_range_t, R&& rg, const Alloc&); constexpr bool empty() const { return c.empty(); }constexpr size_type size() const { return c.size(); }constexpr const_reference top() const { return c.front(); }constexpr void push(const value_type& x); constexpr void push(value_type&& x); template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R>constexpr void push_range(R&& rg); template<class... Args> constexpr void emplace(Args&&... args); constexpr void pop(); constexpr void swap(priority_queue& q)noexcept(is_nothrow_swappable_v<Container> && is_nothrow_swappable_v<Compare>){ using std::swap; swap(c, q.c); swap(comp, q.comp); }}; template<class Compare, class Container> priority_queue(Compare, Container)-> priority_queue<typename Container::value_type, Container, Compare>; template<class InputIterator, class Compare = less<*iter-value-type*<InputIterator>>, class Container = vector<*iter-value-type*<InputIterator>>> priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())-> priority_queue<*iter-value-type*<InputIterator>, Container, 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>>> priority_queue(from_range_t, R&&, Compare = Compare())-> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>>, Compare>; template<class Compare, class Container, class Allocator> priority_queue(Compare, Container, Allocator)-> priority_queue<typename Container::value_type, Container, Compare>; template<class InputIterator, class Allocator> priority_queue(InputIterator, InputIterator, Allocator)-> priority_queue<*iter-value-type*<InputIterator>,
|
||
vector<*iter-value-type*<InputIterator>, Allocator>,
|
||
less<*iter-value-type*<InputIterator>>>; template<class InputIterator, class Compare, class Allocator> priority_queue(InputIterator, InputIterator, Compare, Allocator)-> priority_queue<*iter-value-type*<InputIterator>,
|
||
vector<*iter-value-type*<InputIterator>, Allocator>, Compare>; template<class InputIterator, class Compare, class Container, class Allocator> priority_queue(InputIterator, InputIterator, Compare, Container, Allocator)-> priority_queue<typename Container::value_type, Container, Compare>; template<ranges::[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Compare, class Allocator> priority_queue(from_range_t, R&&, Compare, Allocator)-> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>, Allocator>,
|
||
Compare>; template<ranges::[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Allocator> priority_queue(from_range_t, R&&, Allocator)-> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>, Allocator>>; // no equality is providedtemplate<class T, class Container, class Compare, class Alloc>struct uses_allocator<priority_queue<T, Container, Compare>, Alloc>: uses_allocator<Container, Alloc>::type { };}
|
||
|
||
#### [23.6.4.2](#priqueue.cons) Constructors [[priqueue.cons]](priqueue.cons)
|
||
|
||
[ð](#lib:priority_queue,constructor)
|
||
|
||
`constexpr priority_queue(const Compare& x, const Container& y);
|
||
constexpr priority_queue(const Compare& x, Container&& y);
|
||
`
|
||
|
||
[1](#priqueue.cons-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16141)
|
||
|
||
*Preconditions*: x defines a strict weak ordering ([[alg.sorting]](alg.sorting "26.8 Sorting and related operations"))[.](#priqueue.cons-1.sentence-1)
|
||
|
||
[2](#priqueue.cons-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16145)
|
||
|
||
*Effects*: Initializescomp withx andc withy (copy constructing or move constructing as appropriate);
|
||
callsmake_heap(c.begin(), c.end(), comp)[.](#priqueue.cons-2.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor_)
|
||
|
||
`template<class InputIterator>
|
||
constexpr priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare());
|
||
`
|
||
|
||
[3](#priqueue.cons-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16163)
|
||
|
||
*Preconditions*: x defines a strict weak ordering ([[alg.sorting]](alg.sorting "26.8 Sorting and related operations"))[.](#priqueue.cons-3.sentence-1)
|
||
|
||
[4](#priqueue.cons-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16167)
|
||
|
||
*Effects*: Initializes c withfirst as the first argument andlast as the second argument, and
|
||
initializes comp with x;
|
||
then calls make_heap(c.begin(), c.end(), comp)[.](#priqueue.cons-4.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor__)
|
||
|
||
`template<class InputIterator>
|
||
constexpr priority_queue(InputIterator first, InputIterator last, const Compare& x,
|
||
const Container& y);
|
||
template<class InputIterator>
|
||
constexpr priority_queue(InputIterator first, InputIterator last, const Compare& x,
|
||
Container&& y);
|
||
`
|
||
|
||
[5](#priqueue.cons-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16187)
|
||
|
||
*Preconditions*: x defines a strict weak ordering ([[alg.sorting]](alg.sorting "26.8 Sorting and related operations"))[.](#priqueue.cons-5.sentence-1)
|
||
|
||
[6](#priqueue.cons-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16191)
|
||
|
||
*Effects*: Initializescomp withx andc withy (copy constructing or move constructing as appropriate);
|
||
callsc.insert(c.end(), first, last);
|
||
and finally callsmake_heap(c.begin(), c.end(), comp)[.](#priqueue.cons-6.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor___)
|
||
|
||
`template<[container-compatible-range](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R>
|
||
constexpr priority_queue(from_range_t, R&& rg, const Compare& x = Compare());
|
||
`
|
||
|
||
[7](#priqueue.cons-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16211)
|
||
|
||
*Preconditions*: x defines a strict weak ordering ([[alg.sorting]](alg.sorting "26.8 Sorting and related operations"))[.](#priqueue.cons-7.sentence-1)
|
||
|
||
[8](#priqueue.cons-8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16215)
|
||
|
||
*Effects*: Initializes comp with x andc with ranges::to<Container>(std::forward<R>(rg)) and
|
||
finally calls make_heap(c.begin(), c.end(), comp)[.](#priqueue.cons-8.sentence-1)
|
||
|
||
#### [23.6.4.3](#priqueue.cons.alloc) Constructors with allocators [[priqueue.cons.alloc]](priqueue.cons.alloc)
|
||
|
||
[1](#priqueue.cons.alloc-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16224)
|
||
|
||
If uses_allocator_v<container_type, Alloc> is false the constructors in this subclause shall not participate in overload resolution[.](#priqueue.cons.alloc-1.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor____)
|
||
|
||
`template<class Alloc> constexpr explicit priority_queue(const Alloc& a);
|
||
`
|
||
|
||
[2](#priqueue.cons.alloc-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16234)
|
||
|
||
*Effects*: Initializes c with a and value-initializes comp[.](#priqueue.cons.alloc-2.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor_____)
|
||
|
||
`template<class Alloc> constexpr priority_queue(const Compare& compare, const Alloc& a);
|
||
`
|
||
|
||
[3](#priqueue.cons.alloc-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16245)
|
||
|
||
*Effects*: Initializes c with a and initializes comp with compare[.](#priqueue.cons.alloc-3.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor______)
|
||
|
||
`template<class Alloc>
|
||
constexpr priority_queue(const Compare& compare, const Container& cont, const Alloc& a);
|
||
`
|
||
|
||
[4](#priqueue.cons.alloc-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16257)
|
||
|
||
*Effects*: Initializes c with cont as the first argument and a as the second
|
||
argument, and initializes comp with compare;
|
||
calls make_heap(c.begin(), c.end(), comp)[.](#priqueue.cons.alloc-4.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor_______)
|
||
|
||
`template<class Alloc>
|
||
constexpr priority_queue(const Compare& compare, Container&& cont, const Alloc& a);
|
||
`
|
||
|
||
[5](#priqueue.cons.alloc-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16271)
|
||
|
||
*Effects*: Initializes c with std::move(cont) as the first argument and a as the second argument, and initializes comp with compare;
|
||
calls make_heap(c.begin(), c.end(), comp)[.](#priqueue.cons.alloc-5.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor________)
|
||
|
||
`template<class Alloc> constexpr priority_queue(const priority_queue& q, const Alloc& a);
|
||
`
|
||
|
||
[6](#priqueue.cons.alloc-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16284)
|
||
|
||
*Effects*: Initializes c with q.c as the first argument and a as
|
||
the second argument, and initializes comp with q.comp[.](#priqueue.cons.alloc-6.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor_________)
|
||
|
||
`template<class Alloc> constexpr priority_queue(priority_queue&& q, const Alloc& a);
|
||
`
|
||
|
||
[7](#priqueue.cons.alloc-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16296)
|
||
|
||
*Effects*: Initializes c with std::move(q.c) as the first argument and a as the second argument, and initializes comp with std::move(q.comp)[.](#priqueue.cons.alloc-7.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor__________)
|
||
|
||
`template<class InputIterator, class Alloc>
|
||
constexpr priority_queue(InputIterator first, InputIterator last, const Alloc& a);
|
||
`
|
||
|
||
[8](#priqueue.cons.alloc-8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16309)
|
||
|
||
*Effects*: Initializes c withfirst as the first argument,last as the second argument, anda as the third argument, and
|
||
value-initializes comp;
|
||
calls make_heap(c.begin(), c.end(), comp)[.](#priqueue.cons.alloc-8.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor___________)
|
||
|
||
`template<class InputIterator, class Alloc>
|
||
constexpr priority_queue(InputIterator first, InputIterator last,
|
||
const Compare& compare, const Alloc& a);
|
||
`
|
||
|
||
[9](#priqueue.cons.alloc-9)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16327)
|
||
|
||
*Effects*: Initializes c withfirst as the first argument,last as the second argument, anda as the third argument, and
|
||
initializes comp with compare;
|
||
calls make_heap(c.begin(), c.end(), comp)[.](#priqueue.cons.alloc-9.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor____________)
|
||
|
||
`template<class InputIterator, class Alloc>
|
||
constexpr priority_queue(InputIterator first, InputIterator last, const Compare& compare,
|
||
const Container& cont, const Alloc& a);
|
||
`
|
||
|
||
[10](#priqueue.cons.alloc-10)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16345)
|
||
|
||
*Effects*: Initializes c withcont as the first argument and a as the second argument, and
|
||
initializes comp with compare;
|
||
calls c.insert(c.end(), first, last); and
|
||
finally calls make_heap(c.begin(), c.end(), comp)[.](#priqueue.cons.alloc-10.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor_____________)
|
||
|
||
`template<class InputIterator, class Alloc>
|
||
constexpr priority_queue(InputIterator first, InputIterator last, const Compare& compare,
|
||
Container&& cont, const Alloc& a);
|
||
`
|
||
|
||
[11](#priqueue.cons.alloc-11)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16362)
|
||
|
||
*Effects*: Initializes c withstd::move(cont) as the first argument anda as the second argument, and
|
||
initializes comp with compare;
|
||
calls c.insert(c.end(), first, last); and
|
||
finally calls make_heap(c.begin(), c.end(), comp)[.](#priqueue.cons.alloc-11.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor______________)
|
||
|
||
`template<[container-compatible-range](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R, class Alloc>
|
||
constexpr priority_queue(from_range_t, R&& rg, const Compare& compare, const Alloc& a);
|
||
`
|
||
|
||
[12](#priqueue.cons.alloc-12)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16379)
|
||
|
||
*Effects*: Initializes comp with compare andc with ranges::to<Container>(std::forward<R>(rg), a);
|
||
calls make_heap(c.begin(), c.end(), comp)[.](#priqueue.cons.alloc-12.sentence-1)
|
||
|
||
[ð](#lib:priority_queue,constructor_______________)
|
||
|
||
`template<[container-compatible-range](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R, class Alloc>
|
||
constexpr priority_queue(from_range_t, R&& rg, const Alloc& a);
|
||
`
|
||
|
||
[13](#priqueue.cons.alloc-13)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16393)
|
||
|
||
*Effects*: Initializesc with ranges::to<Container>(std::forward<R>(rg), a) and value-initializes comp;
|
||
calls make_heap(c.begin(), c.end(), comp)[.](#priqueue.cons.alloc-13.sentence-1)
|
||
|
||
#### [23.6.4.4](#priqueue.members) Members [[priqueue.members]](priqueue.members)
|
||
|
||
[ð](#lib:push,priority_queue)
|
||
|
||
`constexpr void push(const value_type& x);
|
||
`
|
||
|
||
[1](#priqueue.members-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16409)
|
||
|
||
*Effects*: As if by:c.push_back(x);
|
||
push_heap(c.begin(), c.end(), comp);
|
||
|
||
[ð](#lib:push,priority_queue_)
|
||
|
||
`constexpr void push(value_type&& x);
|
||
`
|
||
|
||
[2](#priqueue.members-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16424)
|
||
|
||
*Effects*: As if by:c.push_back(std::move(x));
|
||
push_heap(c.begin(), c.end(), comp);
|
||
|
||
[ð](#lib:push_range,priority_queue)
|
||
|
||
`template<[container-compatible-range](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R>
|
||
constexpr void push_range(R&& rg);
|
||
`
|
||
|
||
[3](#priqueue.members-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16440)
|
||
|
||
*Effects*: Inserts all elements of rg in c viac.append_range(std::forward<R>(rg)) if that is a valid expression, orranges::copy(rg, back_inserter(c)) otherwise[.](#priqueue.members-3.sentence-1)
|
||
|
||
Then restores the heap property as if bymake_heap(c.begin(), c.end(), comp)[.](#priqueue.members-3.sentence-2)
|
||
|
||
[4](#priqueue.members-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16448)
|
||
|
||
*Postconditions*: is_heap(c.begin(), c.end(), comp) is true[.](#priqueue.members-4.sentence-1)
|
||
|
||
[ð](#lib:emplace,priority_queue)
|
||
|
||
`template<class... Args> constexpr void emplace(Args&&... args);
|
||
`
|
||
|
||
[5](#priqueue.members-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16459)
|
||
|
||
*Effects*: As if by:c.emplace_back(std::forward<Args>(args)...);
|
||
push_heap(c.begin(), c.end(), comp);
|
||
|
||
[ð](#lib:pop,priority_queue)
|
||
|
||
`constexpr void pop();
|
||
`
|
||
|
||
[6](#priqueue.members-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16474)
|
||
|
||
*Effects*: As if by:pop_heap(c.begin(), c.end(), comp);
|
||
c.pop_back();
|
||
|
||
#### [23.6.4.5](#priqueue.special) Specialized algorithms [[priqueue.special]](priqueue.special)
|
||
|
||
[ð](#lib:swap,priority_queue)
|
||
|
||
`template<class T, class Container, class Compare>
|
||
constexpr void swap(priority_queue<T, Container, Compare>& x,
|
||
priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
|
||
`
|
||
|
||
[1](#priqueue.special-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16493)
|
||
|
||
*Constraints*: is_swappable_v<Container> is true andis_swappable_v<Compare> is true[.](#priqueue.special-1.sentence-1)
|
||
|
||
[2](#priqueue.special-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16498)
|
||
|
||
*Effects*: As if by x.swap(y)[.](#priqueue.special-2.sentence-1)
|
||
|
||
### [23.6.5](#stack.syn) Header <stack> synopsis [[stack.syn]](stack.syn)
|
||
|
||
[ð](#header:%3cstack%3e)
|
||
|
||
#include <compare> // see [[compare.syn]](compare.syn "17.12.1 Header <compare> synopsis")#include <initializer_list> // see [[initializer.list.syn]](initializer.list.syn "17.11.2 Header <initializer_list> synopsis")namespace std {// [[stack]](#stack "23.6.6 Class template stack"), class template stacktemplate<class T, class Container = deque<T>> class stack; template<class T, class Container>constexpr bool operator==(const stack<T, Container>& x, const stack<T, Container>& y); template<class T, class Container>constexpr bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y); template<class T, class Container>constexpr bool operator< (const stack<T, Container>& x, const stack<T, Container>& y); template<class T, class Container>constexpr bool operator> (const stack<T, Container>& x, const stack<T, Container>& y); template<class T, class Container>constexpr bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y); template<class T, class Container>constexpr bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y); template<class T, [three_way_comparable](cmp.concept#concept:three_way_comparable "17.12.4 Concept three_way_comparable [cmp.concept]") Container>constexpr compare_three_way_result_t<Container>operator<=>(const stack<T, Container>& x, const stack<T, Container>& y); template<class T, class Container>constexpr void swap(stack<T, Container>& x, stack<T, Container>& y)noexcept(noexcept(x.swap(y))); template<class T, class Container, class Alloc>struct uses_allocator<stack<T, Container>, Alloc>; // [[container.adaptors.format]](#format "23.6.13 Container adaptors formatting"), formatter specialization for stacktemplate<class charT, class T, [formattable](format.formattable#concept:formattable "28.5.6.3 Concept formattable [format.formattable]")<charT> Container>struct formatter<stack<T, Container>, charT>;}
|
||
|
||
### [23.6.6](#stack) Class template stack [[stack]](stack)
|
||
|
||
#### [23.6.6.1](#stack.general) General [[stack.general]](stack.general)
|
||
|
||
[1](#stack.general-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16546)
|
||
|
||
Any sequence container supporting operationsback(),push_back() andpop_back() can be used to instantiatestack[.](#stack.general-1.sentence-1)
|
||
|
||
In particular,<vector>,<list> and<deque> can be used[.](#stack.general-1.sentence-2)
|
||
|
||
#### [23.6.6.2](#stack.defn) Definition [[stack.defn]](stack.defn)
|
||
|
||
namespace std {template<class T, class Container = deque<T>>class stack {public:using value_type = typename Container::value_type; using reference = typename Container::reference; using const_reference = typename Container::const_reference; using size_type = typename Container::size_type; using container_type = Container; protected: Container c; public:constexpr stack() : stack(Container()) {}constexpr explicit stack(const Container&); constexpr explicit stack(Container&&); template<class InputIterator> constexpr stack(InputIterator first, InputIterator last); template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R>constexpr stack(from_range_t, R&& rg); template<class Alloc> constexpr explicit stack(const Alloc&); template<class Alloc> constexpr stack(const Container&, const Alloc&); template<class Alloc> constexpr stack(Container&&, const Alloc&); template<class Alloc> constexpr stack(const stack&, const Alloc&); template<class Alloc> constexpr stack(stack&&, const Alloc&); template<class InputIterator, class Alloc>constexpr stack(InputIterator first, InputIterator last, const Alloc&); template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R, class Alloc>constexpr stack(from_range_t, R&& rg, const Alloc&); constexpr bool empty() const { return c.empty(); }constexpr size_type size() const { return c.size(); }constexpr reference top() { return c.back(); }constexpr const_reference top() const { return c.back(); }constexpr void push(const value_type& x) { c.push_back(x); }constexpr void push(value_type&& x) { c.push_back(std::move(x)); }template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R>constexpr void push_range(R&& rg); template<class... Args>constexpr decltype(auto) emplace(Args&&... args){ return c.emplace_back(std::forward<Args>(args)...); }constexpr void pop() { c.pop_back(); }constexpr void swap(stack& s) noexcept(is_nothrow_swappable_v<Container>){ using std::swap; swap(c, s.c); }}; template<class Container> stack(Container) -> stack<typename Container::value_type, Container>; template<class InputIterator> stack(InputIterator, InputIterator) -> stack<*iter-value-type*<InputIterator>>; template<ranges::[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R> stack(from_range_t, R&&) -> stack<ranges::range_value_t<R>>; template<class Container, class Allocator> stack(Container, Allocator) -> stack<typename Container::value_type, Container>; template<class InputIterator, class Allocator> stack(InputIterator, InputIterator, Allocator)-> stack<*iter-value-type*<InputIterator>, deque<*iter-value-type*<InputIterator>,
|
||
Allocator>>; template<ranges::[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Allocator> stack(from_range_t, R&&, Allocator)-> stack<ranges::range_value_t<R>, deque<ranges::range_value_t<R>, Allocator>>; template<class T, class Container, class Alloc>struct uses_allocator<stack<T, Container>, Alloc>: uses_allocator<Container, Alloc>::type { };}
|
||
|
||
#### [23.6.6.3](#stack.cons) Constructors [[stack.cons]](stack.cons)
|
||
|
||
[ð](#lib:stack,constructor)
|
||
|
||
`constexpr explicit stack(const Container& cont);
|
||
`
|
||
|
||
[1](#stack.cons-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16646)
|
||
|
||
*Effects*: Initializes c with cont[.](#stack.cons-1.sentence-1)
|
||
|
||
[ð](#lib:stack,constructor_)
|
||
|
||
`constexpr explicit stack(Container&& cont);
|
||
`
|
||
|
||
[2](#stack.cons-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16657)
|
||
|
||
*Effects*: Initializes c with std::move(cont)[.](#stack.cons-2.sentence-1)
|
||
|
||
[ð](#lib:stack,constructor__)
|
||
|
||
`template<class InputIterator>
|
||
constexpr stack(InputIterator first, InputIterator last);
|
||
`
|
||
|
||
[3](#stack.cons-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16669)
|
||
|
||
*Effects*: Initializes c withfirst as the first argument and last as the second argument[.](#stack.cons-3.sentence-1)
|
||
|
||
[ð](#lib:stack,constructor___)
|
||
|
||
`template<[container-compatible-range](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R>
|
||
constexpr stack(from_range_t, R&& rg);
|
||
`
|
||
|
||
[4](#stack.cons-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16682)
|
||
|
||
*Effects*: Initializes c with ranges::to<Container>(std::forward<R>(rg))[.](#stack.cons-4.sentence-1)
|
||
|
||
#### [23.6.6.4](#stack.cons.alloc) Constructors with allocators [[stack.cons.alloc]](stack.cons.alloc)
|
||
|
||
[1](#stack.cons.alloc-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16689)
|
||
|
||
If uses_allocator_v<container_type, Alloc> is false the constructors in this subclause shall not participate in overload resolution[.](#stack.cons.alloc-1.sentence-1)
|
||
|
||
[ð](#lib:stack,constructor____)
|
||
|
||
`template<class Alloc> constexpr explicit stack(const Alloc& a);
|
||
`
|
||
|
||
[2](#stack.cons.alloc-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16699)
|
||
|
||
*Effects*: Initializes c with a[.](#stack.cons.alloc-2.sentence-1)
|
||
|
||
[ð](#lib:stack,constructor_____)
|
||
|
||
`template<class Alloc> constexpr stack(const container_type& cont, const Alloc& a);
|
||
`
|
||
|
||
[3](#stack.cons.alloc-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16710)
|
||
|
||
*Effects*: Initializes c with cont as the first argument and a as the
|
||
second argument[.](#stack.cons.alloc-3.sentence-1)
|
||
|
||
[ð](#lib:stack,constructor______)
|
||
|
||
`template<class Alloc> constexpr stack(container_type&& cont, const Alloc& a);
|
||
`
|
||
|
||
[4](#stack.cons.alloc-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16722)
|
||
|
||
*Effects*: Initializes c with std::move(cont) as the first argument and a as the second argument[.](#stack.cons.alloc-4.sentence-1)
|
||
|
||
[ð](#lib:stack,constructor_______)
|
||
|
||
`template<class Alloc> constexpr stack(const stack& s, const Alloc& a);
|
||
`
|
||
|
||
[5](#stack.cons.alloc-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16734)
|
||
|
||
*Effects*: Initializes c with s.c as the first argument and a as the second argument[.](#stack.cons.alloc-5.sentence-1)
|
||
|
||
[ð](#lib:stack,constructor________)
|
||
|
||
`template<class Alloc> constexpr stack(stack&& s, const Alloc& a);
|
||
`
|
||
|
||
[6](#stack.cons.alloc-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16746)
|
||
|
||
*Effects*: Initializes c with std::move(s.c) as the first argument and a as the second argument[.](#stack.cons.alloc-6.sentence-1)
|
||
|
||
[ð](#lib:stack,constructor_________)
|
||
|
||
`template<class InputIterator, class Alloc>
|
||
constexpr stack(InputIterator first, InputIterator last, const Alloc& alloc);
|
||
`
|
||
|
||
[7](#stack.cons.alloc-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16759)
|
||
|
||
*Effects*: Initializes c withfirst as the first argument,last as the second argument, andalloc as the third argument[.](#stack.cons.alloc-7.sentence-1)
|
||
|
||
[ð](#lib:stack,constructor__________)
|
||
|
||
`template<[container-compatible-range](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R, class Alloc>
|
||
constexpr stack(from_range_t, R&& rg, const Alloc& a);
|
||
`
|
||
|
||
[8](#stack.cons.alloc-8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16774)
|
||
|
||
*Effects*: Initializesc with ranges::to<Container>(std::forward<R>(rg), a)[.](#stack.cons.alloc-8.sentence-1)
|
||
|
||
#### [23.6.6.5](#stack.mod) Modifiers [[stack.mod]](stack.mod)
|
||
|
||
[ð](#lib:push_range,stack)
|
||
|
||
`template<[container-compatible-range](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R>
|
||
constexpr void push_range(R&& rg);
|
||
`
|
||
|
||
[1](#stack.mod-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16789)
|
||
|
||
*Effects*: Equivalent to c.append_range(std::forward<R>(rg)) if that is a valid expression,
|
||
otherwise ranges::copy(rg, back_inserter(c))[.](#stack.mod-1.sentence-1)
|
||
|
||
#### [23.6.6.6](#stack.ops) Operators [[stack.ops]](stack.ops)
|
||
|
||
[ð](#lib:operator==,stack)
|
||
|
||
`template<class T, class Container>
|
||
constexpr bool operator==(const stack<T, Container>& x, const stack<T, Container>& y);
|
||
`
|
||
|
||
[1](#stack.ops-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16805)
|
||
|
||
*Returns*: x.c == y.c[.](#stack.ops-1.sentence-1)
|
||
|
||
[ð](#lib:operator!=,stack)
|
||
|
||
`template<class T, class Container>
|
||
constexpr bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y);
|
||
`
|
||
|
||
[2](#stack.ops-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16817)
|
||
|
||
*Returns*: x.c != y.c[.](#stack.ops-2.sentence-1)
|
||
|
||
[ð](#lib:operator%3c,stack)
|
||
|
||
`template<class T, class Container>
|
||
constexpr bool operator< (const stack<T, Container>& x, const stack<T, Container>& y);
|
||
`
|
||
|
||
[3](#stack.ops-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16829)
|
||
|
||
*Returns*: x.c < y.c[.](#stack.ops-3.sentence-1)
|
||
|
||
[ð](#lib:operator%3e,stack)
|
||
|
||
`template<class T, class Container>
|
||
constexpr bool operator> (const stack<T, Container>& x, const stack<T, Container>& y);
|
||
`
|
||
|
||
[4](#stack.ops-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16841)
|
||
|
||
*Returns*: x.c > y.c[.](#stack.ops-4.sentence-1)
|
||
|
||
[ð](#lib:operator%3c=,stack)
|
||
|
||
`template<class T, class Container>
|
||
constexpr bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y);
|
||
`
|
||
|
||
[5](#stack.ops-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16853)
|
||
|
||
*Returns*: x.c <= y.c[.](#stack.ops-5.sentence-1)
|
||
|
||
[ð](#lib:operator%3e=,stack)
|
||
|
||
`template<class T, class Container>
|
||
constexpr bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y);
|
||
`
|
||
|
||
[6](#stack.ops-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16865)
|
||
|
||
*Returns*: x.c >= y.c[.](#stack.ops-6.sentence-1)
|
||
|
||
[ð](#lib:operator%3c=%3e,stack)
|
||
|
||
`template<class T, [three_way_comparable](cmp.concept#concept:three_way_comparable "17.12.4 Concept three_way_comparable [cmp.concept]") Container>
|
||
constexpr compare_three_way_result_t<Container>
|
||
operator<=>(const stack<T, Container>& x, const stack<T, Container>& y);
|
||
`
|
||
|
||
[7](#stack.ops-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16878)
|
||
|
||
*Returns*: x.c <=> y.c[.](#stack.ops-7.sentence-1)
|
||
|
||
#### [23.6.6.7](#stack.special) Specialized algorithms [[stack.special]](stack.special)
|
||
|
||
[ð](#lib:swap,stack)
|
||
|
||
`template<class T, class Container>
|
||
constexpr void swap(stack<T, Container>& x, stack<T, Container>& y)
|
||
noexcept(noexcept(x.swap(y)));
|
||
`
|
||
|
||
[1](#stack.special-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16893)
|
||
|
||
*Constraints*: is_swappable_v<Container> is true[.](#stack.special-1.sentence-1)
|
||
|
||
[2](#stack.special-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16897)
|
||
|
||
*Effects*: As if by x.swap(y)[.](#stack.special-2.sentence-1)
|
||
|
||
### [23.6.7](#flat.map.syn) Header <flat_map> synopsis [[flat.map.syn]](flat.map.syn)
|
||
|
||
[ð](#header:%3cflat_map%3e)
|
||
|
||
#include <compare> // see [[compare.syn]](compare.syn "17.12.1 Header <compare> synopsis")#include <initializer_list> // see [[initializer.list.syn]](initializer.list.syn "17.11.2 Header <initializer_list> synopsis")namespace std {// [[flat.map]](#flat.map "23.6.8 Class template flat_map"), class template flat_maptemplate<class Key, class T, class Compare = less<Key>, class KeyContainer = vector<Key>, class MappedContainer = vector<T>>class flat_map; struct sorted_unique_t { explicit sorted_unique_t() = default; }; inline constexpr sorted_unique_t sorted_unique{}; template<class Key, class T, class Compare, class KeyContainer, class MappedContainer, class Allocator>struct uses_allocator<flat_map<Key, T, Compare, KeyContainer, MappedContainer>,
|
||
Allocator>; // [[flat.map.erasure]](#flat.map.erasure "23.6.8.8 Erasure"), erasure for flat_maptemplate<class Key, class T, class Compare, class KeyContainer, class MappedContainer, class Predicate>constexpr typename flat_map<Key, T, Compare, KeyContainer, MappedContainer>::size_type
|
||
erase_if(flat_map<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred); // [[flat.multimap]](#flat.multimap "23.6.9 Class template flat_multimap"), class template flat_multimaptemplate<class Key, class T, class Compare = less<Key>, class KeyContainer = vector<Key>, class MappedContainer = vector<T>>class flat_multimap; struct sorted_equivalent_t { explicit sorted_equivalent_t() = default; }; inline constexpr sorted_equivalent_t sorted_equivalent{}; template<class Key, class T, class Compare, class KeyContainer, class MappedContainer, class Allocator>struct uses_allocator<flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>,
|
||
Allocator>; // [[flat.multimap.erasure]](#flat.multimap.erasure "23.6.9.5 Erasure"), erasure for flat_multimaptemplate<class Key, class T, class Compare, class KeyContainer, class MappedContainer, class Predicate>constexpr typename flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>::size_type
|
||
erase_if(flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);}
|
||
|
||
### [23.6.8](#flat.map) Class template flat_map [[flat.map]](flat.map)
|
||
|
||
#### [23.6.8.1](#flat.map.overview) Overview [[flat.map.overview]](flat.map.overview)
|
||
|
||
[1](#flat.map.overview-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16954)
|
||
|
||
A flat_map 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 values of another type T based on the keys[.](#flat.map.overview-1.sentence-1)
|
||
|
||
flat_map supports iterators
|
||
that meet the *Cpp17InputIterator* requirements and
|
||
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"))[.](#flat.map.overview-1.sentence-2)
|
||
|
||
[2](#flat.map.overview-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16967)
|
||
|
||
A flat_map meets all of the requirements
|
||
of a container ([[container.reqmts]](container.reqmts "23.2.2.2 Container requirements")) and
|
||
of 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"))[.](#flat.map.overview-2.sentence-1)
|
||
|
||
flat_map meets the requirements of
|
||
an associative container ([[associative.reqmts]](associative.reqmts "23.2.7 Associative containers")),
|
||
except that:
|
||
|
||
- [(2.1)](#flat.map.overview-2.1)
|
||
|
||
it does not meet the requirements related to node handles ([[container.node]](container.node "23.2.5 Node handles")),
|
||
|
||
- [(2.2)](#flat.map.overview-2.2)
|
||
|
||
it does not meet the requirements related to iterator invalidation, and
|
||
|
||
- [(2.3)](#flat.map.overview-2.3)
|
||
|
||
the time complexity of the operations that insert or erase a single
|
||
element from the map is linear, including the ones that take an insertion
|
||
position iterator[.](#flat.map.overview-2.sentence-2)
|
||
|
||
[*Note [1](#flat.map.overview-note-1)*:
|
||
|
||
A flat_map does not meet the additional requirements of
|
||
an allocator-aware container ([[container.alloc.reqmts]](container.alloc.reqmts "23.2.2.5 Allocator-aware containers"))[.](#flat.map.overview-2.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
[3](#flat.map.overview-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L16990)
|
||
|
||
A flat_map also provides most operations
|
||
described in [[associative.reqmts]](associative.reqmts "23.2.7 Associative containers") for unique keys[.](#flat.map.overview-3.sentence-1)
|
||
|
||
This means that a flat_map supports
|
||
the a_uniq operations in [[associative.reqmts]](associative.reqmts "23.2.7 Associative containers") but not the a_eq operations[.](#flat.map.overview-3.sentence-2)
|
||
|
||
For a flat_map<Key, T> the key_type is Key and
|
||
the value_type is pair<Key, T>[.](#flat.map.overview-3.sentence-3)
|
||
|
||
[4](#flat.map.overview-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17000)
|
||
|
||
Descriptions are provided here only for operations on flat_map that
|
||
are not described in one of those sets of requirements or for operations where
|
||
there is additional semantic information[.](#flat.map.overview-4.sentence-1)
|
||
|
||
[5](#flat.map.overview-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17005)
|
||
|
||
A flat_map maintains the following invariants:
|
||
|
||
- [(5.1)](#flat.map.overview-5.1)
|
||
|
||
it contains the same number of keys and values;
|
||
|
||
- [(5.2)](#flat.map.overview-5.2)
|
||
|
||
the keys are sorted with respect to the comparison object; and
|
||
|
||
- [(5.3)](#flat.map.overview-5.3)
|
||
|
||
the value at offset off within the value container is
|
||
the value associated with the key at offset off within the key container[.](#flat.map.overview-5.sentence-1)
|
||
|
||
[6](#flat.map.overview-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17018)
|
||
|
||
If any member function in [[flat.map.defn]](#flat.map.defn "23.6.8.2 Definition") exits via an exception
|
||
the invariants are restored[.](#flat.map.overview-6.sentence-1)
|
||
|
||
[*Note [2](#flat.map.overview-note-2)*:
|
||
|
||
This can result in the flat_map being emptied[.](#flat.map.overview-6.sentence-2)
|
||
|
||
â *end note*]
|
||
|
||
[7](#flat.map.overview-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17025)
|
||
|
||
Any type C that meets the sequence container requirements ([[sequence.reqmts]](sequence.reqmts "23.2.4 Sequence containers"))
|
||
can be used to instantiate flat_map,
|
||
as long asC::iterator meets the *Cpp17RandomAccessIterator* requirements and
|
||
invocations of
|
||
member functions C::size and C::max_size do not exit via an exception[.](#flat.map.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[.](#flat.map.overview-7.sentence-2)
|
||
|
||
[*Note [3](#flat.map.overview-note-3)*:
|
||
|
||
vector<bool> is not a sequence container[.](#flat.map.overview-7.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
[8](#flat.map.overview-8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17039)
|
||
|
||
The program is ill-formed ifKey is not the same type as KeyContainer::value_type orT is not the same type as MappedContainer::value_type[.](#flat.map.overview-8.sentence-1)
|
||
|
||
[9](#flat.map.overview-9)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17044)
|
||
|
||
The effect of calling a constructor
|
||
that takes
|
||
both key_container_type and mapped_container_type arguments with
|
||
containers of different sizes is undefined[.](#flat.map.overview-9.sentence-1)
|
||
|
||
[10](#flat.map.overview-10)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17050)
|
||
|
||
The effect of calling a constructor or member function
|
||
that takes a sorted_unique_t argument with
|
||
a container, containers, or range
|
||
that is not sorted with respect to key_comp(), or
|
||
that contains equal elements,
|
||
is undefined[.](#flat.map.overview-10.sentence-1)
|
||
|
||
[11](#flat.map.overview-11)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17058)
|
||
|
||
The types iterator and const_iterator meet
|
||
the constexpr iterator requirements ([[iterator.requirements.general]](iterator.requirements.general "24.3.1 General"))[.](#flat.map.overview-11.sentence-1)
|
||
|
||
#### [23.6.8.2](#flat.map.defn) Definition [[flat.map.defn]](flat.map.defn)
|
||
|
||
namespace std {template<class Key, class T, class Compare = less<Key>, class KeyContainer = vector<Key>, class MappedContainer = vector<T>>class flat_map {public:// typesusing key_type = Key; using mapped_type = T; using value_type = pair<key_type, mapped_type>; using key_compare = Compare; using reference = pair<const key_type&, mapped_type&>; using const_reference = pair<const key_type&, const mapped_type&>; using size_type = size_t; using difference_type = ptrdiff_t; 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 key_container_type = KeyContainer; using mapped_container_type = MappedContainer; class value_compare {private: key_compare *comp*; // *exposition only*constexpr value_compare(key_compare c) : *comp*(c) { } // *exposition only*public:constexpr bool operator()(const_reference x, const_reference y) const {return *comp*(x.first, y.first); }}; struct containers { key_container_type keys;
|
||
mapped_container_type values; }; // [[flat.map.cons]](#flat.map.cons "23.6.8.3 Constructors"), constructorsconstexpr flat_map() : flat_map(key_compare()) { }constexpr explicit flat_map(const key_compare& comp): *c*(), *compare*(comp) { }constexpr flat_map(key_container_type key_cont, mapped_container_type mapped_cont, const key_compare& comp = key_compare()); constexpr flat_map(sorted_unique_t, key_container_type key_cont,
|
||
mapped_container_type mapped_cont, const key_compare& comp = key_compare()); template<class InputIterator>constexpr flat_map(InputIterator first, InputIterator last, const key_compare& comp = key_compare()): *c*(), *compare*(comp) { insert(first, last); }template<class InputIterator>constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last, const key_compare& comp = key_compare()): *c*(), *compare*(comp) { insert(sorted_unique, first, last); }template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<value_type> R>constexpr flat_map(from_range_t, R&& rg): flat_map(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_map(from_range_t, R&& rg, const key_compare& comp): flat_map(comp) { insert_range(std::forward<R>(rg)); }constexpr flat_map(initializer_list<value_type> il, const key_compare& comp = key_compare()): flat_map(il.begin(), il.end(), comp) { }constexpr flat_map(sorted_unique_t, initializer_list<value_type> il, const key_compare& comp = key_compare()): flat_map(sorted_unique, il.begin(), il.end(), comp) { }// [[flat.map.cons.alloc]](#flat.map.cons.alloc "23.6.8.4 Constructors with allocators"), constructors with allocatorstemplate<class Alloc>constexpr explicit flat_map(const Alloc& a); template<class Alloc>constexpr flat_map(const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont, const Alloc& a); template<class Alloc>constexpr flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_map(sorted_unique_t, const key_container_type& key_cont, const mapped_container_type& mapped_cont, const Alloc& a); template<class Alloc>constexpr flat_map(sorted_unique_t, const key_container_type& key_cont, const mapped_container_type& mapped_cont, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_map(const flat_map&, const Alloc& a); template<class Alloc>constexpr flat_map(flat_map&&, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_map(InputIterator first, InputIterator last, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_map(InputIterator first, InputIterator last, const key_compare& comp, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_map(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_map(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_map(from_range_t, R&& rg, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_map(initializer_list<value_type> il, const Alloc& a); template<class Alloc>constexpr flat_map(initializer_list<value_type> il, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_map(sorted_unique_t, initializer_list<value_type> il, const Alloc& a); template<class Alloc>constexpr flat_map(sorted_unique_t, initializer_list<value_type> il, const key_compare& comp, const Alloc& a); constexpr flat_map& 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; // [[flat.map.capacity]](#flat.map.capacity "23.6.8.5 Capacity"), capacityconstexpr bool empty() const noexcept; constexpr size_type size() const noexcept; constexpr size_type max_size() const noexcept; // [[flat.map.access]](#flat.map.access "23.6.8.6 Access"), element accessconstexpr mapped_type& operator[](const key_type& x); constexpr mapped_type& operator[](key_type&& x); template<class K> constexpr mapped_type& operator[](K&& x); constexpr mapped_type& at(const key_type& x); constexpr const mapped_type& at(const key_type& x) const; template<class K> constexpr mapped_type& at(const K& x); template<class K> constexpr const mapped_type& at(const K& x) const; // [[flat.map.modifiers]](#flat.map.modifiers "23.6.8.7 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)); }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 P> constexpr pair<iterator, bool> insert(P&& x); template<class P>constexpr iterator insert(const_iterator position, P&&); 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 containers extract() &&; constexpr void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont); template<class... Args>constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); template<class... Args>constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); template<class K, class... Args>constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args); template<class... Args>constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); template<class... Args>constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); template<class K, class... Args>constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args); template<class M>constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); template<class M>constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); template<class K, class M>constexpr pair<iterator, bool> insert_or_assign(K&& k, M&& obj); template<class M>constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); template<class M>constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); template<class K, class M>constexpr iterator insert_or_assign(const_iterator hint, K&& k, M&& obj); 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_map& y) noexcept; constexpr void clear() noexcept; // observersconstexpr key_compare key_comp() const; constexpr value_compare value_comp() const; constexpr const key_container_type& keys() const noexcept { return *c*.keys; }constexpr const mapped_container_type& values() const noexcept { return *c*.values; }// map 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_map& x, const flat_map& y); friend constexpr *synth-three-way-result*<value_type>operator<=>(const flat_map& x, const flat_map& y); friend constexpr void swap(flat_map& x, flat_map& y) noexcept{ x.swap(y); }private: containers *c*; // *exposition only* key_compare *compare*; // *exposition only*struct *key-equiv* { // *exposition only*constexpr *key-equiv*(key_compare c) : comp(c) { }constexpr bool operator()(const_reference x, const_reference y) const {return !comp(x.first, y.first) && !comp(y.first, x.first); } key_compare comp; }; }; template<class KeyContainer, class MappedContainer, class Compare = less<typename KeyContainer::value_type>> flat_map(KeyContainer, MappedContainer, Compare = Compare())-> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
|
||
Compare, KeyContainer, MappedContainer>; template<class KeyContainer, class MappedContainer, class Allocator> flat_map(KeyContainer, MappedContainer, Allocator)-> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
|
||
less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>; template<class KeyContainer, class MappedContainer, class Compare, class Allocator> flat_map(KeyContainer, MappedContainer, Compare, Allocator)-> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
|
||
Compare, KeyContainer, MappedContainer>; template<class KeyContainer, class MappedContainer, class Compare = less<typename KeyContainer::value_type>> flat_map(sorted_unique_t, KeyContainer, MappedContainer, Compare = Compare())-> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
|
||
Compare, KeyContainer, MappedContainer>; template<class KeyContainer, class MappedContainer, class Allocator> flat_map(sorted_unique_t, KeyContainer, MappedContainer, Allocator)-> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
|
||
less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>; template<class KeyContainer, class MappedContainer, class Compare, class Allocator> flat_map(sorted_unique_t, KeyContainer, MappedContainer, Compare, Allocator)-> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
|
||
Compare, KeyContainer, MappedContainer>; template<class InputIterator, class Compare = less<*iter-key-type*<InputIterator>>> flat_map(InputIterator, InputIterator, Compare = Compare())-> flat_map<*iter-key-type*<InputIterator>, *iter-mapped-type*<InputIterator>, Compare>; template<class InputIterator, class Compare = less<*iter-key-type*<InputIterator>>> flat_map(sorted_unique_t, InputIterator, InputIterator, Compare = Compare())-> flat_map<*iter-key-type*<InputIterator>, *iter-mapped-type*<InputIterator>, Compare>; template<ranges::[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Compare = less<*range-key-type*<R>>, class Allocator = allocator<byte>> flat_map(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())-> flat_map<*range-key-type*<R>, *range-mapped-type*<R>, Compare,
|
||
vector<*range-key-type*<R>, *alloc-rebind*<Allocator, *range-key-type*<R>>>,
|
||
vector<*range-mapped-type*<R>, *alloc-rebind*<Allocator, *range-mapped-type*<R>>>>; template<ranges::[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Allocator> flat_map(from_range_t, R&&, Allocator)-> flat_map<*range-key-type*<R>, *range-mapped-type*<R>, less<*range-key-type*<R>>,
|
||
vector<*range-key-type*<R>, *alloc-rebind*<Allocator, *range-key-type*<R>>>,
|
||
vector<*range-mapped-type*<R>, *alloc-rebind*<Allocator, *range-mapped-type*<R>>>>; template<class Key, class T, class Compare = less<Key>> flat_map(initializer_list<pair<Key, T>>, Compare = Compare())-> flat_map<Key, T, Compare>; template<class Key, class T, class Compare = less<Key>> flat_map(sorted_unique_t, initializer_list<pair<Key, T>>, Compare = Compare())-> flat_map<Key, T, Compare>; template<class Key, class T, class Compare, class KeyContainer, class MappedContainer, class Allocator>struct uses_allocator<flat_map<Key, T, Compare, KeyContainer, MappedContainer>, Allocator>: bool_constant<uses_allocator_v<KeyContainer, Allocator> && uses_allocator_v<MappedContainer, Allocator>> { };}
|
||
|
||
[1](#flat.map.defn-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17411)
|
||
|
||
The member type containers has the data members and special members
|
||
specified above[.](#flat.map.defn-1.sentence-1)
|
||
|
||
It has no base classes or members other than those specified[.](#flat.map.defn-1.sentence-2)
|
||
|
||
#### [23.6.8.3](#flat.map.cons) Constructors [[flat.map.cons]](flat.map.cons)
|
||
|
||
[ð](#lib:flat_map,constructor)
|
||
|
||
`constexpr flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
|
||
const key_compare& comp = key_compare());
|
||
`
|
||
|
||
[1](#flat.map.cons-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17425)
|
||
|
||
*Effects*: Initializes*c*.keys with std::move(key_cont),*c*.values with std::move(mapped_cont), and*compare* with comp;
|
||
sorts the range [begin(), end()) with respect to value_comp(); and
|
||
finally erases the duplicate elements as if by:auto zv = views::zip(*c*.keys, *c*.values);auto it = ranges::unique(zv, *key-equiv*(*compare*)).begin();auto dist = distance(zv.begin(), it);*c*.keys.erase(*c*.keys.begin() + dist, *c*.keys.end());*c*.values.erase(*c*.values.begin() + dist, *c*.values.end());
|
||
|
||
[2](#flat.map.cons-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17441)
|
||
|
||
*Complexity*: Linear in N if the container arguments are already sorted
|
||
with respect to value_comp() and otherwise NlogN,
|
||
where N is the value of key_cont.size() before this call[.](#flat.map.cons-2.sentence-1)
|
||
|
||
[ð](#lib:flat_map,constructor_)
|
||
|
||
`constexpr flat_map(sorted_unique_t, key_container_type key_cont, mapped_container_type mapped_cont,
|
||
const key_compare& comp = key_compare());
|
||
`
|
||
|
||
[3](#flat.map.cons-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17455)
|
||
|
||
*Effects*: Initializes*c*.keys with std::move(key_cont),*c*.values with std::move(mapped_cont), and*compare* with comp[.](#flat.map.cons-3.sentence-1)
|
||
|
||
[4](#flat.map.cons-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17462)
|
||
|
||
*Complexity*: Constant[.](#flat.map.cons-4.sentence-1)
|
||
|
||
#### [23.6.8.4](#flat.map.cons.alloc) Constructors with allocators [[flat.map.cons.alloc]](flat.map.cons.alloc)
|
||
|
||
[1](#flat.map.cons.alloc-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17469)
|
||
|
||
The constructors in this subclause shall not participate in overload resolution
|
||
unless uses_allocator_v<key_container_type, Alloc> is true and uses_allocator_v<mapped_container_type, Alloc> is true[.](#flat.map.cons.alloc-1.sentence-1)
|
||
|
||
[ð](#lib:flat_map,constructor__)
|
||
|
||
`template<class Alloc>
|
||
constexpr flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
|
||
const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
|
||
const key_compare& comp, const Alloc& a);
|
||
`
|
||
|
||
[2](#flat.map.cons.alloc-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17485)
|
||
|
||
*Effects*: Equivalent to flat_map(key_cont, mapped_cont) andflat_map(key_cont, mapped_cont, comp), respectively,
|
||
except that *c*.keys and *c*.values are constructed with
|
||
uses-allocator construction ([[allocator.uses.construction]](allocator.uses.construction "20.2.8.2 Uses-allocator construction"))[.](#flat.map.cons.alloc-2.sentence-1)
|
||
|
||
[3](#flat.map.cons.alloc-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17492)
|
||
|
||
*Complexity*: Same as flat_map(key_cont, mapped_cont) andflat_map(key_cont, mapped_cont, comp), respectively[.](#flat.map.cons.alloc-3.sentence-1)
|
||
|
||
[ð](#lib:flat_map,constructor___)
|
||
|
||
`template<class Alloc>
|
||
constexpr flat_map(sorted_unique_t, const key_container_type& key_cont,
|
||
const mapped_container_type& mapped_cont, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_map(sorted_unique_t, const key_container_type& key_cont,
|
||
const mapped_container_type& mapped_cont, const key_compare& comp,
|
||
const Alloc& a);
|
||
`
|
||
|
||
[4](#flat.map.cons.alloc-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17510)
|
||
|
||
*Effects*: Equivalent to flat_map(sorted_unique, key_cont, mapped_cont) andflat_map(sorted_unique, key_cont, mapped_cont, comp), respectively,
|
||
except that *c*.keys and *c*.values are constructed
|
||
with uses-allocator construction ([[allocator.uses.construction]](allocator.uses.construction "20.2.8.2 Uses-allocator construction"))[.](#flat.map.cons.alloc-4.sentence-1)
|
||
|
||
[5](#flat.map.cons.alloc-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17517)
|
||
|
||
*Complexity*: Linear[.](#flat.map.cons.alloc-5.sentence-1)
|
||
|
||
[ð](#lib:flat_map,constructor____)
|
||
|
||
`template<class Alloc>
|
||
constexpr explicit flat_map(const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_map(const key_compare& comp, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_map(const flat_map&, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_map(flat_map&&, const Alloc& a);
|
||
template<class InputIterator, class Alloc>
|
||
constexpr flat_map(InputIterator first, InputIterator last, const Alloc& a);
|
||
template<class InputIterator, class Alloc>
|
||
constexpr flat_map(InputIterator first, InputIterator last, const key_compare& comp,
|
||
const Alloc& a);
|
||
template<class InputIterator, class Alloc>
|
||
constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last, const Alloc& a);
|
||
template<class InputIterator, class Alloc>
|
||
constexpr flat_map(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_map(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_map(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_map(initializer_list<value_type> il, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_map(initializer_list<value_type> il, const key_compare& comp, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_map(sorted_unique_t, initializer_list<value_type> il, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_map(sorted_unique_t, initializer_list<value_type> il,
|
||
const key_compare& comp, const Alloc& a);
|
||
`
|
||
|
||
[6](#flat.map.cons.alloc-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17558)
|
||
|
||
*Effects*: Equivalent to the corresponding non-allocator constructors
|
||
except that *c*.keys and *c*.values are constructed
|
||
with uses-allocator construction ([[allocator.uses.construction]](allocator.uses.construction "20.2.8.2 Uses-allocator construction"))[.](#flat.map.cons.alloc-6.sentence-1)
|
||
|
||
#### [23.6.8.5](#flat.map.capacity) Capacity [[flat.map.capacity]](flat.map.capacity)
|
||
|
||
[ð](#lib:size,flat_map)
|
||
|
||
`constexpr size_type size() const noexcept;
|
||
`
|
||
|
||
[1](#flat.map.capacity-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17573)
|
||
|
||
*Returns*: *c*.keys.size()[.](#flat.map.capacity-1.sentence-1)
|
||
|
||
[ð](#lib:max_size,flat_map)
|
||
|
||
`constexpr size_type max_size() const noexcept;
|
||
`
|
||
|
||
[2](#flat.map.capacity-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17584)
|
||
|
||
*Returns*: min<size_type>(*c*.keys.max_size(), *c*.values.max_size())[.](#flat.map.capacity-2.sentence-1)
|
||
|
||
#### [23.6.8.6](#flat.map.access) Access [[flat.map.access]](flat.map.access)
|
||
|
||
[ð](#lib:operator%5b%5d,flat_map)
|
||
|
||
`constexpr mapped_type& operator[](const key_type& x);
|
||
`
|
||
|
||
[1](#flat.map.access-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17597)
|
||
|
||
*Effects*: Equivalent to: return try_emplace(x).first->second;
|
||
|
||
[ð](#lib:operator%5b%5d,flat_map_)
|
||
|
||
`constexpr mapped_type& operator[](key_type&& x);
|
||
`
|
||
|
||
[2](#flat.map.access-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17608)
|
||
|
||
*Effects*: Equivalent to: return try_emplace(std::move(x)).first->second;
|
||
|
||
[ð](#lib:operator%5b%5d,flat_map__)
|
||
|
||
`template<class K> constexpr mapped_type& operator[](K&& x);
|
||
`
|
||
|
||
[3](#flat.map.access-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17619)
|
||
|
||
*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[.](#flat.map.access-3.sentence-1)
|
||
|
||
[4](#flat.map.access-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17624)
|
||
|
||
*Effects*: Equivalent to: return try_emplace(std::forward<K>(x)).first->second;
|
||
|
||
[ð](#lib:at,flat_map)
|
||
|
||
`constexpr mapped_type& at(const key_type& x);
|
||
constexpr const mapped_type& at(const key_type& x) const;
|
||
`
|
||
|
||
[5](#flat.map.access-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17636)
|
||
|
||
*Returns*: A reference to the mapped_type corresponding
|
||
to x in *this[.](#flat.map.access-5.sentence-1)
|
||
|
||
[6](#flat.map.access-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17641)
|
||
|
||
*Throws*: An exception object of type out_of_range if
|
||
no such element is present[.](#flat.map.access-6.sentence-1)
|
||
|
||
[7](#flat.map.access-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17646)
|
||
|
||
*Complexity*: Logarithmic[.](#flat.map.access-7.sentence-1)
|
||
|
||
[ð](#lib:at,flat_map_)
|
||
|
||
`template<class K> constexpr mapped_type& at(const K& x);
|
||
template<class K> constexpr const mapped_type& at(const K& x) const;
|
||
`
|
||
|
||
[8](#flat.map.access-8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17658)
|
||
|
||
*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[.](#flat.map.access-8.sentence-1)
|
||
|
||
[9](#flat.map.access-9)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17663)
|
||
|
||
*Preconditions*: The expression find(x) is well-formed and has well-defined behavior[.](#flat.map.access-9.sentence-1)
|
||
|
||
[10](#flat.map.access-10)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17667)
|
||
|
||
*Returns*: A reference to the mapped_type corresponding tox in *this[.](#flat.map.access-10.sentence-1)
|
||
|
||
[11](#flat.map.access-11)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17672)
|
||
|
||
*Throws*: An exception object of type out_of_range if no such element is present[.](#flat.map.access-11.sentence-1)
|
||
|
||
[12](#flat.map.access-12)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17677)
|
||
|
||
*Complexity*: Logarithmic[.](#flat.map.access-12.sentence-1)
|
||
|
||
#### [23.6.8.7](#flat.map.modifiers) Modifiers [[flat.map.modifiers]](flat.map.modifiers)
|
||
|
||
[ð](#lib:emplace,flat_map)
|
||
|
||
`template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
|
||
`
|
||
|
||
[1](#flat.map.modifiers-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17690)
|
||
|
||
*Constraints*: is_constructible_v<pair<key_type, mapped_type>, Args...> is true[.](#flat.map.modifiers-1.sentence-1)
|
||
|
||
[2](#flat.map.modifiers-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17694)
|
||
|
||
*Effects*: Initializes an object t of type pair<key_type, mapped_type> with std::forward<Args>(args)...;
|
||
if the map already contains an element
|
||
whose key is equivalent to t.first,*this is unchanged[.](#flat.map.modifiers-2.sentence-1)
|
||
|
||
Otherwise, equivalent to:auto key_it = ranges::upper_bound(*c*.keys, t.first, *compare*);auto value_it = *c*.values.begin() + distance(*c*.keys.begin(), key_it);*c*.keys.insert(key_it, std::move(t.first));*c*.values.insert(value_it, std::move(t.second));
|
||
|
||
[3](#flat.map.modifiers-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17709)
|
||
|
||
*Returns*: The bool component of the returned pair is true if and only if the insertion took place, and
|
||
the iterator component of the pair points to
|
||
the element with key equivalent to t.first[.](#flat.map.modifiers-3.sentence-1)
|
||
|
||
[ð](#lib:insert,flat_map)
|
||
|
||
`template<class P> constexpr pair<iterator, bool> insert(P&& x);
|
||
template<class P> constexpr iterator insert(const_iterator position, P&& x);
|
||
`
|
||
|
||
[4](#flat.map.modifiers-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17724)
|
||
|
||
*Constraints*: is_constructible_v<pair<key_type, mapped_type>, P> is true[.](#flat.map.modifiers-4.sentence-1)
|
||
|
||
[5](#flat.map.modifiers-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17728)
|
||
|
||
*Effects*: The first form is equivalent to return emplace(std::forward<P>(x));[.](#flat.map.modifiers-5.sentence-1)
|
||
|
||
The second form is equivalent toreturn emplace_hint(position, std::forward<P>(x));[.](#flat.map.modifiers-5.sentence-2)
|
||
|
||
[ð](#lib:insert,flat_map_)
|
||
|
||
`template<class InputIterator>
|
||
constexpr void insert(InputIterator first, InputIterator last);
|
||
`
|
||
|
||
[6](#flat.map.modifiers-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17742)
|
||
|
||
*Effects*: Adds elements to *c* as if by:for (; first != last; ++first) { value_type value = *first; *c*.keys.insert(*c*.keys.end(), std::move(value.first)); *c*.values.insert(*c*.values.end(), std::move(value.second));}
|
||
|
||
Then, sorts the range of newly inserted elements
|
||
with respect to value_comp();
|
||
merges the resulting sorted range and
|
||
the sorted range of pre-existing elements into a single sorted range; and
|
||
finally erases the duplicate elements as if by:auto zv = views::zip(*c*.keys, *c*.values);auto it = ranges::unique(zv, *key-equiv*(*compare*)).begin();auto dist = distance(zv.begin(), it);*c*.keys.erase(*c*.keys.begin() + dist, *c*.keys.end());*c*.values.erase(*c*.values.begin() + dist, *c*.values.end());
|
||
|
||
[7](#flat.map.modifiers-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17765)
|
||
|
||
*Complexity*: N + MlogM,
|
||
where N is size() before the operation andM is distance(first, last)[.](#flat.map.modifiers-7.sentence-1)
|
||
|
||
[8](#flat.map.modifiers-8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17771)
|
||
|
||
*Remarks*: Since this operation performs an in-place merge, it may allocate memory[.](#flat.map.modifiers-8.sentence-1)
|
||
|
||
[ð](#lib:insert,flat_map__)
|
||
|
||
`template<class InputIterator>
|
||
constexpr void insert(sorted_unique_t, InputIterator first, InputIterator last);
|
||
`
|
||
|
||
[9](#flat.map.modifiers-9)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17783)
|
||
|
||
*Effects*: Adds elements to *c* as if by:for (; first != last; ++first) { value_type value = *first; *c*.keys.insert(*c*.keys.end(), std::move(value.first)); *c*.values.insert(*c*.values.end(), std::move(value.second));}
|
||
|
||
Then, merges the sorted range of newly added elements and
|
||
the sorted range of pre-existing elements into a single sorted range; and
|
||
finally erases the duplicate elements as if by:auto zv = views::zip(*c*.keys, *c*.values);auto it = ranges::unique(zv, *key-equiv*(*compare*)).begin();auto dist = distance(zv.begin(), it);*c*.keys.erase(*c*.keys.begin() + dist, *c*.keys.end());*c*.values.erase(*c*.values.begin() + dist, *c*.values.end());
|
||
|
||
[10](#flat.map.modifiers-10)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17804)
|
||
|
||
*Complexity*: Linear in N, where N is size() after the operation[.](#flat.map.modifiers-10.sentence-1)
|
||
|
||
[11](#flat.map.modifiers-11)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17808)
|
||
|
||
*Remarks*: Since this operation performs an in-place merge, it may allocate memory[.](#flat.map.modifiers-11.sentence-1)
|
||
|
||
[ð](#lib:insert_range,flat_map)
|
||
|
||
`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);
|
||
`
|
||
|
||
[12](#flat.map.modifiers-12)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17820)
|
||
|
||
*Effects*: Adds elements to *c* as if by:for (const auto& e : rg) {*c*.keys.insert(*c*.keys.end(), e.first); *c*.values.insert(*c*.values.end(), e.second);}
|
||
|
||
Then, sorts the range of newly inserted elements
|
||
with respect to value_comp();
|
||
merges the resulting sorted range and
|
||
the sorted range of pre-existing elements into a single sorted range; and
|
||
finally erases the duplicate elements as if by:auto zv = views::zip(*c*.keys, *c*.values);auto it = ranges::unique(zv, *key-equiv*(*compare*)).begin();auto dist = distance(zv.begin(), it);*c*.keys.erase(*c*.keys.begin() + dist, *c*.keys.end());*c*.values.erase(*c*.values.begin() + dist, *c*.values.end());
|
||
|
||
[13](#flat.map.modifiers-13)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17842)
|
||
|
||
*Complexity*: N + MlogM,
|
||
where N is size() before the operation andM is ranges::distance(rg)[.](#flat.map.modifiers-13.sentence-1)
|
||
|
||
[14](#flat.map.modifiers-14)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17848)
|
||
|
||
*Remarks*: Since this operation performs an in-place merge, it may allocate memory[.](#flat.map.modifiers-14.sentence-1)
|
||
|
||
[ð](#lib:try_emplace,flat_map)
|
||
|
||
`template<class... Args>
|
||
constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
|
||
template<class... Args>
|
||
constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
|
||
template<class... Args>
|
||
constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
|
||
template<class... Args>
|
||
constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
|
||
`
|
||
|
||
[15](#flat.map.modifiers-15)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17866)
|
||
|
||
*Constraints*: is_constructible_v<mapped_type, Args...> is true[.](#flat.map.modifiers-15.sentence-1)
|
||
|
||
[16](#flat.map.modifiers-16)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17870)
|
||
|
||
*Effects*: If the map already contains an element whose key is equivalent to k,*this and args... are unchanged[.](#flat.map.modifiers-16.sentence-1)
|
||
|
||
Otherwise equivalent to:auto key_it = ranges::upper_bound(*c*.keys, k, *compare*);auto value_it = *c*.values.begin() + distance(*c*.keys.begin(), key_it);*c*.keys.insert(key_it, std::forward<decltype(k)>(k));*c*.values.emplace(value_it, std::forward<Args>(args)...);
|
||
|
||
[17](#flat.map.modifiers-17)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17882)
|
||
|
||
*Returns*: In the first two overloads,
|
||
the bool component of the returned pair is true if and only if the insertion took place[.](#flat.map.modifiers-17.sentence-1)
|
||
|
||
The returned iterator points to the map element
|
||
whose key is equivalent to k[.](#flat.map.modifiers-17.sentence-2)
|
||
|
||
[18](#flat.map.modifiers-18)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17890)
|
||
|
||
*Complexity*: The same as emplace for the first two overloads, and
|
||
the same as emplace_hint for the last two overloads[.](#flat.map.modifiers-18.sentence-1)
|
||
|
||
[ð](#lib:try_emplace,flat_map_)
|
||
|
||
`template<class K, class... Args>
|
||
constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args);
|
||
template<class K, class... Args>
|
||
constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
|
||
`
|
||
|
||
[19](#flat.map.modifiers-19)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17905)
|
||
|
||
*Constraints*:
|
||
|
||
- [(19.1)](#flat.map.modifiers-19.1)
|
||
|
||
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[.](#flat.map.modifiers-19.1.sentence-1)
|
||
|
||
- [(19.2)](#flat.map.modifiers-19.2)
|
||
|
||
is_constructible_v<key_type, K> is true[.](#flat.map.modifiers-19.2.sentence-1)
|
||
|
||
- [(19.3)](#flat.map.modifiers-19.3)
|
||
|
||
is_constructible_v<mapped_type, Args...> is true[.](#flat.map.modifiers-19.3.sentence-1)
|
||
|
||
- [(19.4)](#flat.map.modifiers-19.4)
|
||
|
||
For the first overload,is_convertible_v<K&&, const_iterator> andis_convertible_v<K&&, iterator> are both false[.](#flat.map.modifiers-19.4.sentence-1)
|
||
|
||
[20](#flat.map.modifiers-20)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17921)
|
||
|
||
*Preconditions*: The conversion from k into key_type constructs
|
||
an object u,
|
||
for which find(k) == find(u) is true[.](#flat.map.modifiers-20.sentence-1)
|
||
|
||
[21](#flat.map.modifiers-21)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17927)
|
||
|
||
*Effects*: If the map already contains an element whose key is equivalent to k,*this and args... are unchanged[.](#flat.map.modifiers-21.sentence-1)
|
||
|
||
Otherwise equivalent to:auto key_it = upper_bound(*c*.keys.begin(), *c*.keys.end(), k, *compare*);auto value_it = *c*.values.begin() + distance(*c*.keys.begin(), key_it);*c*.keys.emplace(key_it, std::forward<K>(k));*c*.values.emplace(value_it, std::forward<Args>(args)...);
|
||
|
||
[22](#flat.map.modifiers-22)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17939)
|
||
|
||
*Returns*: In the first overload,
|
||
the bool component of the returned pair is true if and only if the insertion took place[.](#flat.map.modifiers-22.sentence-1)
|
||
|
||
The returned iterator points to the map element
|
||
whose key is equivalent to k[.](#flat.map.modifiers-22.sentence-2)
|
||
|
||
[23](#flat.map.modifiers-23)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17947)
|
||
|
||
*Complexity*: The same as emplace and emplace_hint, respectively[.](#flat.map.modifiers-23.sentence-1)
|
||
|
||
[ð](#lib:insert_or_assign,flat_map)
|
||
|
||
`template<class M>
|
||
constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
|
||
template<class M>
|
||
constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
|
||
template<class M>
|
||
constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
|
||
template<class M>
|
||
constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
|
||
`
|
||
|
||
[24](#flat.map.modifiers-24)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17965)
|
||
|
||
*Constraints*: is_assignable_v<mapped_type&, M> is true andis_constructible_v<mapped_type, M> is true[.](#flat.map.modifiers-24.sentence-1)
|
||
|
||
[25](#flat.map.modifiers-25)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17970)
|
||
|
||
*Effects*: If the map already contains an element e whose key is equivalent to k,
|
||
assigns std::forward<M>(obj) to e.second[.](#flat.map.modifiers-25.sentence-1)
|
||
|
||
Otherwise, equivalent totry_emplace(std::forward<decltype(k)>(k), std::forward<M>(obj)) for the first two overloads ortry_emplace(hint, std::forward<decltype(k)>(k), std::forward<M>(obj)) for the last two overloads[.](#flat.map.modifiers-25.sentence-2)
|
||
|
||
[26](#flat.map.modifiers-26)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17985)
|
||
|
||
*Returns*: In the first two overloads, the bool component of the returned pair
|
||
is true if and only if the insertion took place[.](#flat.map.modifiers-26.sentence-1)
|
||
|
||
The returned
|
||
iterator points to the map element whose key is equivalent to k[.](#flat.map.modifiers-26.sentence-2)
|
||
|
||
[27](#flat.map.modifiers-27)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L17991)
|
||
|
||
*Complexity*: The same as emplace for the first two overloads and
|
||
the same as emplace_hint for the last two overloads[.](#flat.map.modifiers-27.sentence-1)
|
||
|
||
[ð](#lib:insert_or_assign,flat_map_)
|
||
|
||
`template<class K, class M>
|
||
constexpr pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
|
||
template<class K, class M>
|
||
constexpr iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
|
||
`
|
||
|
||
[28](#flat.map.modifiers-28)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18006)
|
||
|
||
*Constraints*:
|
||
|
||
- [(28.1)](#flat.map.modifiers-28.1)
|
||
|
||
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[.](#flat.map.modifiers-28.1.sentence-1)
|
||
|
||
- [(28.2)](#flat.map.modifiers-28.2)
|
||
|
||
is_constructible_v<key_type, K> is true[.](#flat.map.modifiers-28.2.sentence-1)
|
||
|
||
- [(28.3)](#flat.map.modifiers-28.3)
|
||
|
||
is_assignable_v<mapped_type&, M> is true[.](#flat.map.modifiers-28.3.sentence-1)
|
||
|
||
- [(28.4)](#flat.map.modifiers-28.4)
|
||
|
||
is_constructible_v<mapped_type, M> is true[.](#flat.map.modifiers-28.4.sentence-1)
|
||
|
||
[29](#flat.map.modifiers-29)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18020)
|
||
|
||
*Preconditions*: The conversion from k into key_type constructs
|
||
an object u, for which find(k) == find(u) is true[.](#flat.map.modifiers-29.sentence-1)
|
||
|
||
[30](#flat.map.modifiers-30)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18025)
|
||
|
||
*Effects*: If the map already contains an element e whose key is equivalent to k,
|
||
assigns std::forward<M>(obj) to e.second[.](#flat.map.modifiers-30.sentence-1)
|
||
|
||
Otherwise, equivalent totry_emplace(std::forward<K>(k), std::forward<M>(obj)) for the first overload ortry_emplace(hint, std::forward<K>(k), std::forward<M>(obj)) for the second overload[.](#flat.map.modifiers-30.sentence-2)
|
||
|
||
[31](#flat.map.modifiers-31)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18040)
|
||
|
||
*Returns*: In the first overload,
|
||
the bool component of the returned pair is true if and only if the insertion took place[.](#flat.map.modifiers-31.sentence-1)
|
||
|
||
The returned iterator points to the map element
|
||
whose key is equivalent to k[.](#flat.map.modifiers-31.sentence-2)
|
||
|
||
[32](#flat.map.modifiers-32)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18048)
|
||
|
||
*Complexity*: The same as emplace and emplace_hint, respectively[.](#flat.map.modifiers-32.sentence-1)
|
||
|
||
[ð](#lib:swap,flat_map)
|
||
|
||
`constexpr void swap(flat_map& y) noexcept;
|
||
`
|
||
|
||
[33](#flat.map.modifiers-33)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18059)
|
||
|
||
*Effects*: Equivalent to:ranges::swap(*compare*, y.*compare*);
|
||
ranges::swap(*c*.keys, y.*c*.keys);
|
||
ranges::swap(*c*.values, y.*c*.values);
|
||
|
||
[ð](#lib:extract,flat_map)
|
||
|
||
`constexpr containers extract() &&;
|
||
`
|
||
|
||
[34](#flat.map.modifiers-34)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18075)
|
||
|
||
*Postconditions*: *this is emptied, even if the function exits via an exception[.](#flat.map.modifiers-34.sentence-1)
|
||
|
||
[35](#flat.map.modifiers-35)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18079)
|
||
|
||
*Returns*: std::move(*c*)[.](#flat.map.modifiers-35.sentence-1)
|
||
|
||
[ð](#lib:replace,flat_map)
|
||
|
||
`constexpr void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);
|
||
`
|
||
|
||
[36](#flat.map.modifiers-36)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18090)
|
||
|
||
*Preconditions*: key_cont.size() == mapped_cont.size() is true,
|
||
the elements of key_cont are sorted with respect to *compare*, andkey_cont contains no equal elements[.](#flat.map.modifiers-36.sentence-1)
|
||
|
||
[37](#flat.map.modifiers-37)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18096)
|
||
|
||
*Effects*: Equivalent to:*c*.keys = std::move(key_cont);*c*.values = std::move(mapped_cont);
|
||
|
||
#### [23.6.8.8](#flat.map.erasure) Erasure [[flat.map.erasure]](flat.map.erasure)
|
||
|
||
[ð](#lib:erase_if,flat_map)
|
||
|
||
`template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
|
||
class Predicate>
|
||
constexpr typename flat_map<Key, T, Compare, KeyContainer, MappedContainer>::size_type
|
||
erase_if(flat_map<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
|
||
`
|
||
|
||
[1](#flat.map.erasure-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18116)
|
||
|
||
*Preconditions*: Key and T meet the *Cpp17MoveAssignable* requirements[.](#flat.map.erasure-1.sentence-1)
|
||
|
||
[2](#flat.map.erasure-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18120)
|
||
|
||
*Effects*: Let E be bool(pred(pair<const Key&, const T&>(e)))[.](#flat.map.erasure-2.sentence-1)
|
||
|
||
Erases all elements e in c for which E holds[.](#flat.map.erasure-2.sentence-2)
|
||
|
||
[3](#flat.map.erasure-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18125)
|
||
|
||
*Returns*: The number of elements erased[.](#flat.map.erasure-3.sentence-1)
|
||
|
||
[4](#flat.map.erasure-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18129)
|
||
|
||
*Complexity*: Exactly c.size() applications of the predicate[.](#flat.map.erasure-4.sentence-1)
|
||
|
||
[5](#flat.map.erasure-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18133)
|
||
|
||
*Remarks*: Stable ([[algorithm.stable]](algorithm.stable "16.4.6.8 Requirements for stable algorithms"))[.](#flat.map.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"))[.](#flat.map.erasure-5.sentence-2)
|
||
|
||
[*Note [1](#flat.map.erasure-note-1)*:
|
||
|
||
c still meets its invariants,
|
||
but can be empty[.](#flat.map.erasure-5.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
### [23.6.9](#flat.multimap) Class template flat_multimap [[flat.multimap]](flat.multimap)
|
||
|
||
#### [23.6.9.1](#flat.multimap.overview) Overview [[flat.multimap.overview]](flat.multimap.overview)
|
||
|
||
[1](#flat.multimap.overview-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18148)
|
||
|
||
A flat_multimap 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 values of another type T based on the keys[.](#flat.multimap.overview-1.sentence-1)
|
||
|
||
flat_multimap supports iterators that meet
|
||
the *Cpp17InputIterator* requirements and
|
||
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"))[.](#flat.multimap.overview-1.sentence-2)
|
||
|
||
[2](#flat.multimap.overview-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18161)
|
||
|
||
A flat_multimap 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"))[.](#flat.multimap.overview-2.sentence-1)
|
||
|
||
flat_multimap meets the requirements of
|
||
an associative container ([[associative.reqmts]](associative.reqmts "23.2.7 Associative containers")), except that:
|
||
|
||
- [(2.1)](#flat.multimap.overview-2.1)
|
||
|
||
it does not meet the requirements related to node handles ([[container.node]](container.node "23.2.5 Node handles")),
|
||
|
||
- [(2.2)](#flat.multimap.overview-2.2)
|
||
|
||
it does not meet the requirements related to iterator invalidation, and
|
||
|
||
- [(2.3)](#flat.multimap.overview-2.3)
|
||
|
||
the time complexity of the operations
|
||
that insert or erase a single element from the map is linear,
|
||
including the ones that take an insertion position iterator[.](#flat.multimap.overview-2.sentence-2)
|
||
|
||
[*Note [1](#flat.multimap.overview-note-1)*:
|
||
|
||
A flat_multimap does not meet the additional requirements of an
|
||
allocator-aware container ([[container.alloc.reqmts]](container.alloc.reqmts "23.2.2.5 Allocator-aware containers"))[.](#flat.multimap.overview-2.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
[3](#flat.multimap.overview-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18183)
|
||
|
||
A flat_multimap also provides most operations described
|
||
in [[associative.reqmts]](associative.reqmts "23.2.7 Associative containers") for equal keys[.](#flat.multimap.overview-3.sentence-1)
|
||
|
||
This means that a flat_multimap supports
|
||
the a_eq operations in [[associative.reqmts]](associative.reqmts "23.2.7 Associative containers") but not the a_uniq operations[.](#flat.multimap.overview-3.sentence-2)
|
||
|
||
For a flat_multimap<Key, T> the key_type is Key and
|
||
the value_type is pair<Key, T>[.](#flat.multimap.overview-3.sentence-3)
|
||
|
||
[4](#flat.multimap.overview-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18193)
|
||
|
||
Except as otherwise noted,
|
||
operations on flat_multimap are equivalent to those of flat_map,
|
||
except that flat_multimap operations
|
||
do not remove or replace elements with equal keys[.](#flat.multimap.overview-4.sentence-1)
|
||
|
||
[*Example [1](#flat.multimap.overview-example-1)*:
|
||
|
||
flat_multimap constructors and emplace do not erase
|
||
non-unique elements after sorting them[.](#flat.multimap.overview-4.sentence-2)
|
||
|
||
â *end example*]
|
||
|
||
[5](#flat.multimap.overview-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18203)
|
||
|
||
A flat_multimap maintains the following invariants:
|
||
|
||
- [(5.1)](#flat.multimap.overview-5.1)
|
||
|
||
it contains the same number of keys and values;
|
||
|
||
- [(5.2)](#flat.multimap.overview-5.2)
|
||
|
||
the keys are sorted with respect to the comparison object; and
|
||
|
||
- [(5.3)](#flat.multimap.overview-5.3)
|
||
|
||
the value at offset off within the value container is the value
|
||
associated with the key at offset off within the key container[.](#flat.multimap.overview-5.sentence-1)
|
||
|
||
[6](#flat.multimap.overview-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18215)
|
||
|
||
If any member function in [[flat.multimap.defn]](#flat.multimap.defn "23.6.9.2 Definition") exits via an exception,
|
||
the invariants are restored[.](#flat.multimap.overview-6.sentence-1)
|
||
|
||
[*Note [2](#flat.multimap.overview-note-2)*:
|
||
|
||
This can result in the flat_multimap being emptied[.](#flat.multimap.overview-6.sentence-2)
|
||
|
||
â *end note*]
|
||
|
||
[7](#flat.multimap.overview-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18222)
|
||
|
||
Any type C that meets the sequence container requirements ([[sequence.reqmts]](sequence.reqmts "23.2.4 Sequence containers"))
|
||
can be used to instantiate flat_multimap,
|
||
as long asC::iterator meets the *Cpp17RandomAccessIterator* requirements and
|
||
invocations of
|
||
member functions C::size and C::max_size do not exit via an exception[.](#flat.multimap.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[.](#flat.multimap.overview-7.sentence-2)
|
||
|
||
[*Note [3](#flat.multimap.overview-note-3)*:
|
||
|
||
vector<bool> is not a sequence container[.](#flat.multimap.overview-7.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
[8](#flat.multimap.overview-8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18236)
|
||
|
||
The program is ill-formed ifKey is not the same type as KeyContainer::value_type orT is not the same type as MappedContainer::value_type[.](#flat.multimap.overview-8.sentence-1)
|
||
|
||
[9](#flat.multimap.overview-9)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18241)
|
||
|
||
The effect of calling a constructor
|
||
that takes both key_container_type andmapped_container_type arguments
|
||
with containers of different sizes is undefined[.](#flat.multimap.overview-9.sentence-1)
|
||
|
||
[10](#flat.multimap.overview-10)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18247)
|
||
|
||
The effect of calling a constructor or member function
|
||
that takes a sorted_equivalent_t argument
|
||
with a container, containers, or range
|
||
that are not sorted with respect to key_comp() is undefined[.](#flat.multimap.overview-10.sentence-1)
|
||
|
||
[11](#flat.multimap.overview-11)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18253)
|
||
|
||
The types iterator and const_iterator meet
|
||
the constexpr iterator requirements ([[iterator.requirements.general]](iterator.requirements.general "24.3.1 General"))[.](#flat.multimap.overview-11.sentence-1)
|
||
|
||
#### [23.6.9.2](#flat.multimap.defn) Definition [[flat.multimap.defn]](flat.multimap.defn)
|
||
|
||
namespace std {template<class Key, class T, class Compare = less<Key>, class KeyContainer = vector<Key>, class MappedContainer = vector<T>>class flat_multimap {public:// typesusing key_type = Key; using mapped_type = T; using value_type = pair<key_type, mapped_type>; using key_compare = Compare; using reference = pair<const key_type&, mapped_type&>; using const_reference = pair<const key_type&, const mapped_type&>; using size_type = size_t; using difference_type = ptrdiff_t; 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 key_container_type = KeyContainer; using mapped_container_type = MappedContainer; class value_compare {private: key_compare *comp*; // *exposition only*constexpr value_compare(key_compare c) : *comp*(c) { } // *exposition only*public:constexpr bool operator()(const_reference x, const_reference y) const {return *comp*(x.first, y.first); }}; struct containers { key_container_type keys;
|
||
mapped_container_type values; }; // [[flat.multimap.cons]](#flat.multimap.cons "23.6.9.3 Constructors"), constructorsconstexpr flat_multimap() : flat_multimap(key_compare()) { }constexpr explicit flat_multimap(const key_compare& comp): *c*(), *compare*(comp) { }constexpr flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont, const key_compare& comp = key_compare()); constexpr flat_multimap(sorted_equivalent_t,
|
||
key_container_type key_cont, mapped_container_type mapped_cont, const key_compare& comp = key_compare()); template<class InputIterator>constexpr flat_multimap(InputIterator first, InputIterator last, const key_compare& comp = key_compare()): *c*(), *compare*(comp){ insert(first, last); }template<class InputIterator>constexpr flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last, const key_compare& comp = key_compare()): *c*(), *compare*(comp) { insert(sorted_equivalent, first, last); }template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<value_type> R>constexpr flat_multimap(from_range_t, R&& rg): flat_multimap(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_multimap(from_range_t, R&& rg, const key_compare& comp): flat_multimap(comp) { insert_range(std::forward<R>(rg)); }constexpr flat_multimap(initializer_list<value_type> il, const key_compare& comp = key_compare()): flat_multimap(il.begin(), il.end(), comp) { }constexpr flat_multimap(sorted_equivalent_t, initializer_list<value_type> il, const key_compare& comp = key_compare()): flat_multimap(sorted_equivalent, il.begin(), il.end(), comp) { }// [[flat.multimap.cons.alloc]](#flat.multimap.cons.alloc "23.6.9.4 Constructors with allocators"), constructors with allocatorstemplate<class Alloc>constexpr explicit flat_multimap(const Alloc& a); template<class Alloc>constexpr flat_multimap(const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont, const Alloc& a); template<class Alloc>constexpr flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_multimap(sorted_equivalent_t, const key_container_type& key_cont, const mapped_container_type& mapped_cont, const Alloc& a); template<class Alloc>constexpr flat_multimap(sorted_equivalent_t, const key_container_type& key_cont, const mapped_container_type& mapped_cont, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_multimap(const flat_multimap&, const Alloc& a); template<class Alloc>constexpr flat_multimap(flat_multimap&&, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_multimap(InputIterator first, InputIterator last, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_multimap(InputIterator first, InputIterator last, const key_compare& comp, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_multimap(sorted_equivalent_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_multimap(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_multimap(from_range_t, R&& rg, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_multimap(initializer_list<value_type> il, const Alloc& a); template<class Alloc>constexpr flat_multimap(initializer_list<value_type> il, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_multimap(sorted_equivalent_t, initializer_list<value_type> il, const Alloc& a); template<class Alloc>constexpr flat_multimap(sorted_equivalent_t, initializer_list<value_type> il, const key_compare& comp, const Alloc& a);
|
||
|
||
flat_multimap& 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; // modifierstemplate<class... Args> constexpr iterator emplace(Args&&... args); template<class... Args>constexpr iterator emplace_hint(const_iterator position, Args&&... args); constexpr iterator insert(const value_type& x){ return emplace(x); }constexpr iterator insert(value_type&& x){ return emplace(std::move(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 P> constexpr iterator insert(P&& x); template<class P>constexpr iterator insert(const_iterator position, P&&); template<class InputIterator>constexpr void insert(InputIterator first, InputIterator last); template<class InputIterator>constexpr void insert(sorted_equivalent_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_equivalent_t, initializer_list<value_type> il){ insert(sorted_equivalent, il.begin(), il.end()); }constexpr containers extract() &&; constexpr void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont); 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_multimap&) noexcept; constexpr void clear() noexcept; // observersconstexpr key_compare key_comp() const; constexpr value_compare value_comp() const; constexpr const key_container_type& keys() const noexcept { return *c*.keys; }constexpr const mapped_container_type& values() const noexcept { return *c*.values; }// map 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_multimap& x, const flat_multimap& y); friend constexpr *synth-three-way-result*<value_type>operator<=>(const flat_multimap& x, const flat_multimap& y); friend constexpr void swap(flat_multimap& x, flat_multimap& y) noexcept{ x.swap(y); }private: containers *c*; // *exposition only* key_compare *compare*; // *exposition only*}; template<class KeyContainer, class MappedContainer, class Compare = less<typename KeyContainer::value_type>> flat_multimap(KeyContainer, MappedContainer, Compare = Compare())-> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
|
||
Compare, KeyContainer, MappedContainer>; template<class KeyContainer, class MappedContainer, class Allocator> flat_multimap(KeyContainer, MappedContainer, Allocator)-> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
|
||
less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>; template<class KeyContainer, class MappedContainer, class Compare, class Allocator> flat_multimap(KeyContainer, MappedContainer, Compare, Allocator)-> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
|
||
Compare, KeyContainer, MappedContainer>; template<class KeyContainer, class MappedContainer, class Compare = less<typename KeyContainer::value_type>> flat_multimap(sorted_equivalent_t, KeyContainer, MappedContainer, Compare = Compare())-> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
|
||
Compare, KeyContainer, MappedContainer>; template<class KeyContainer, class MappedContainer, class Allocator> flat_multimap(sorted_equivalent_t, KeyContainer, MappedContainer, Allocator)-> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
|
||
less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>; template<class KeyContainer, class MappedContainer, class Compare, class Allocator> flat_multimap(sorted_equivalent_t, KeyContainer, MappedContainer, Compare, Allocator)-> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
|
||
Compare, KeyContainer, MappedContainer>; template<class InputIterator, class Compare = less<*iter-key-type*<InputIterator>>> flat_multimap(InputIterator, InputIterator, Compare = Compare())-> flat_multimap<*iter-key-type*<InputIterator>, *iter-mapped-type*<InputIterator>, Compare>; template<class InputIterator, class Compare = less<*iter-key-type*<InputIterator>>> flat_multimap(sorted_equivalent_t, InputIterator, InputIterator, Compare = Compare())-> flat_multimap<*iter-key-type*<InputIterator>, *iter-mapped-type*<InputIterator>, Compare>; template<ranges::[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Compare = less<*range-key-type*<R>>, class Allocator = allocator<byte>> flat_multimap(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())-> flat_multimap<*range-key-type*<R>, *range-mapped-type*<R>, Compare,
|
||
vector<*range-key-type*<R>, *alloc-rebind*<Allocator, *range-key-type*<R>>>,
|
||
vector<*range-mapped-type*<R>, *alloc-rebind*<Allocator, *range-mapped-type*<R>>>>; template<ranges::[input_range](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, class Allocator> flat_multimap(from_range_t, R&&, Allocator)-> flat_multimap<*range-key-type*<R>, *range-mapped-type*<R>, less<*range-key-type*<R>>,
|
||
vector<*range-key-type*<R>, *alloc-rebind*<Allocator, *range-key-type*<R>>>,
|
||
vector<*range-mapped-type*<R>, *alloc-rebind*<Allocator, *range-mapped-type*<R>>>>; template<class Key, class T, class Compare = less<Key>> flat_multimap(initializer_list<pair<Key, T>>, Compare = Compare())-> flat_multimap<Key, T, Compare>; template<class Key, class T, class Compare = less<Key>> flat_multimap(sorted_equivalent_t, initializer_list<pair<Key, T>>, Compare = Compare())-> flat_multimap<Key, T, Compare>; template<class Key, class T, class Compare, class KeyContainer, class MappedContainer, class Allocator>struct uses_allocator<flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>,
|
||
Allocator>: bool_constant<uses_allocator_v<KeyContainer, Allocator> && uses_allocator_v<MappedContainer, Allocator>> { };}
|
||
|
||
[1](#flat.multimap.defn-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18572)
|
||
|
||
The member type containers has the data members and special members
|
||
specified above[.](#flat.multimap.defn-1.sentence-1)
|
||
|
||
It has no base classes or members other than those
|
||
specified[.](#flat.multimap.defn-1.sentence-2)
|
||
|
||
#### [23.6.9.3](#flat.multimap.cons) Constructors [[flat.multimap.cons]](flat.multimap.cons)
|
||
|
||
[ð](#lib:flat_multimap,constructor)
|
||
|
||
`constexpr flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,
|
||
const key_compare& comp = key_compare());
|
||
`
|
||
|
||
[1](#flat.multimap.cons-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18586)
|
||
|
||
*Effects*: Initializes*c*.keys with std::move(key_cont),*c*.values with std::move(mapped_cont), and*compare* with comp;
|
||
sorts the range [begin(), end()) with respect to value_comp()[.](#flat.multimap.cons-1.sentence-1)
|
||
|
||
[2](#flat.multimap.cons-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18594)
|
||
|
||
*Complexity*: Linear in N if the container arguments are already sorted
|
||
with respect to value_comp() and otherwise NlogN,
|
||
where N is the value of key_cont.size() before this call[.](#flat.multimap.cons-2.sentence-1)
|
||
|
||
[ð](#lib:flat_multimap,constructor_)
|
||
|
||
`constexpr flat_multimap(sorted_equivalent_t, key_container_type key_cont,
|
||
mapped_container_type mapped_cont,
|
||
const key_compare& comp = key_compare());
|
||
`
|
||
|
||
[3](#flat.multimap.cons-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18609)
|
||
|
||
*Effects*: Initializes*c*.keys with std::move(key_cont),*c*.values with std::move(mapped_cont), and*compare* with comp[.](#flat.multimap.cons-3.sentence-1)
|
||
|
||
[4](#flat.multimap.cons-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18616)
|
||
|
||
*Complexity*: Constant[.](#flat.multimap.cons-4.sentence-1)
|
||
|
||
#### [23.6.9.4](#flat.multimap.cons.alloc) Constructors with allocators [[flat.multimap.cons.alloc]](flat.multimap.cons.alloc)
|
||
|
||
[1](#flat.multimap.cons.alloc-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18623)
|
||
|
||
The constructors in this subclause shall not participate in overload resolution
|
||
unless uses_allocator_v<key_container_type, Alloc> is true and uses_allocator_v<mapped_container_type, Alloc> is true[.](#flat.multimap.cons.alloc-1.sentence-1)
|
||
|
||
[ð](#lib:flat_multimap,constructor__)
|
||
|
||
`template<class Alloc>
|
||
constexpr flat_multimap(const key_container_type& key_cont,
|
||
const mapped_container_type& mapped_cont, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multimap(const key_container_type& key_cont,
|
||
const mapped_container_type& mapped_cont,
|
||
const key_compare& comp, const Alloc& a);
|
||
`
|
||
|
||
[2](#flat.multimap.cons.alloc-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18640)
|
||
|
||
*Effects*: Equivalent to flat_multimap(key_cont, mapped_cont) andflat_multimap(key_cont, mapped_cont, comp), respectively,
|
||
except that *c*.keys and *c*.values are constructed
|
||
with uses-allocator construction ([[allocator.uses.construction]](allocator.uses.construction "20.2.8.2 Uses-allocator construction"))[.](#flat.multimap.cons.alloc-2.sentence-1)
|
||
|
||
[3](#flat.multimap.cons.alloc-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18647)
|
||
|
||
*Complexity*: Same as flat_multimap(key_cont, mapped_cont) andflat_multimap(key_cont, mapped_cont, comp), respectively[.](#flat.multimap.cons.alloc-3.sentence-1)
|
||
|
||
[ð](#lib:flat_multimap,constructor___)
|
||
|
||
`template<class Alloc>
|
||
constexpr flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
|
||
const mapped_container_type& mapped_cont, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
|
||
const mapped_container_type& mapped_cont, const key_compare& comp,
|
||
const Alloc& a);
|
||
`
|
||
|
||
[4](#flat.multimap.cons.alloc-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18665)
|
||
|
||
*Effects*: Equivalent to flat_multimap(sorted_equivalent, key_cont, mapped_cont) andflat_multimap(sorted_equivalent, key_cont, mapped_cont, comp), respectively,
|
||
except that *c*.keys and *c*.values are constructed
|
||
with uses-allocator construction ([[allocator.uses.construction]](allocator.uses.construction "20.2.8.2 Uses-allocator construction"))[.](#flat.multimap.cons.alloc-4.sentence-1)
|
||
|
||
[5](#flat.multimap.cons.alloc-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18672)
|
||
|
||
*Complexity*: Linear[.](#flat.multimap.cons.alloc-5.sentence-1)
|
||
|
||
[ð](#lib:flat_multimap,constructor____)
|
||
|
||
`template<class Alloc>
|
||
constexpr explicit flat_multimap(const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multimap(const key_compare& comp, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multimap(const flat_multimap&, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multimap(flat_multimap&&, const Alloc& a);
|
||
template<class InputIterator, class Alloc>
|
||
constexpr flat_multimap(InputIterator first, InputIterator last, const Alloc& a);
|
||
template<class InputIterator, class Alloc>
|
||
constexpr flat_multimap(InputIterator first, InputIterator last, const key_compare& comp,
|
||
const Alloc& a);
|
||
template<class InputIterator, class Alloc>
|
||
constexpr flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
|
||
const Alloc& a);
|
||
template<class InputIterator, class Alloc>
|
||
constexpr flat_multimap(sorted_equivalent_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_multimap(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_multimap(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multimap(initializer_list<value_type> il, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multimap(initializer_list<value_type> il, const key_compare& comp,
|
||
const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multimap(sorted_equivalent_t, initializer_list<value_type> il, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
|
||
const key_compare& comp, const Alloc& a);
|
||
`
|
||
|
||
[6](#flat.multimap.cons.alloc-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18715)
|
||
|
||
*Effects*: Equivalent to the corresponding non-allocator constructors
|
||
except that *c*.keys and *c*.values are constructed
|
||
with uses-allocator construction ([[allocator.uses.construction]](allocator.uses.construction "20.2.8.2 Uses-allocator construction"))[.](#flat.multimap.cons.alloc-6.sentence-1)
|
||
|
||
#### [23.6.9.5](#flat.multimap.erasure) Erasure [[flat.multimap.erasure]](flat.multimap.erasure)
|
||
|
||
[ð](#lib:erase_if,flat_multimap)
|
||
|
||
`template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
|
||
class Predicate>
|
||
constexpr typename flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>::size_type
|
||
erase_if(flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
|
||
`
|
||
|
||
[1](#flat.multimap.erasure-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18733)
|
||
|
||
*Preconditions*: Key and T meet the *Cpp17MoveAssignable* requirements[.](#flat.multimap.erasure-1.sentence-1)
|
||
|
||
[2](#flat.multimap.erasure-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18737)
|
||
|
||
*Effects*: Let E be bool(pred(pair<const Key&, const T&>(e)))[.](#flat.multimap.erasure-2.sentence-1)
|
||
|
||
Erases all elements e in c for which E holds[.](#flat.multimap.erasure-2.sentence-2)
|
||
|
||
[3](#flat.multimap.erasure-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18742)
|
||
|
||
*Returns*: The number of elements erased[.](#flat.multimap.erasure-3.sentence-1)
|
||
|
||
[4](#flat.multimap.erasure-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18746)
|
||
|
||
*Complexity*: Exactly c.size() applications of the predicate[.](#flat.multimap.erasure-4.sentence-1)
|
||
|
||
[5](#flat.multimap.erasure-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18750)
|
||
|
||
*Remarks*: Stable ([[algorithm.stable]](algorithm.stable "16.4.6.8 Requirements for stable algorithms"))[.](#flat.multimap.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"))[.](#flat.multimap.erasure-5.sentence-2)
|
||
|
||
[*Note [1](#flat.multimap.erasure-note-1)*:
|
||
|
||
c still meets its invariants,
|
||
but can be empty[.](#flat.multimap.erasure-5.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
### [23.6.10](#flat.set.syn) Header <flat_set> synopsis [[flat.set.syn]](flat.set.syn)
|
||
|
||
#include <compare> // see [[compare.syn]](compare.syn "17.12.1 Header <compare> synopsis")#include <initializer_list> // see [[initializer.list.syn]](initializer.list.syn "17.11.2 Header <initializer_list> synopsis")namespace std {// [[flat.set]](#flat.set "23.6.11 Class template flat_set"), class template flat_settemplate<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>class flat_set; struct sorted_unique_t { explicit sorted_unique_t() = default; }; inline constexpr sorted_unique_t sorted_unique{}; template<class Key, class Compare, class KeyContainer, class Allocator>struct uses_allocator<flat_set<Key, Compare, KeyContainer>, Allocator>; // [[flat.set.erasure]](#flat.set.erasure "23.6.11.6 Erasure"), erasure for flat_settemplate<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); // [[flat.multiset]](#flat.multiset "23.6.12 Class template flat_multiset"), class template flat_multisettemplate<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>class flat_multiset; struct sorted_equivalent_t { explicit sorted_equivalent_t() = default; }; inline constexpr sorted_equivalent_t sorted_equivalent{}; template<class Key, class Compare, class KeyContainer, class Allocator>struct uses_allocator<flat_multiset<Key, Compare, KeyContainer>, Allocator>; // [[flat.multiset.erasure]](#flat.multiset.erasure "23.6.12.6 Erasure"), erasure for flat_multisettemplate<class Key, class Compare, class KeyContainer, class Predicate>constexpr typename flat_multiset<Key, Compare, KeyContainer>::size_type
|
||
erase_if(flat_multiset<Key, Compare, KeyContainer>& c, Predicate pred);}
|
||
|
||
### [23.6.11](#flat.set) Class template flat_set [[flat.set]](flat.set)
|
||
|
||
#### [23.6.11.1](#flat.set.overview) Overview [[flat.set.overview]](flat.set.overview)
|
||
|
||
[1](#flat.set.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[.](#flat.set.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"))[.](#flat.set.overview-1.sentence-2)
|
||
|
||
[2](#flat.set.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"))[.](#flat.set.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)](#flat.set.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)](#flat.set.overview-2.2)
|
||
|
||
it does not meet the requirements related to iterator invalidation, and
|
||
|
||
- [(2.3)](#flat.set.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[.](#flat.set.overview-2.sentence-2)
|
||
|
||
[*Note [1](#flat.set.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")[.](#flat.set.overview-2.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
[3](#flat.set.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[.](#flat.set.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[.](#flat.set.overview-3.sentence-2)
|
||
|
||
For a flat_set<Key>,
|
||
both the key_type and value_type are Key[.](#flat.set.overview-3.sentence-3)
|
||
|
||
[4](#flat.set.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[.](#flat.set.overview-4.sentence-1)
|
||
|
||
[5](#flat.set.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[.](#flat.set.overview-5.sentence-1)
|
||
|
||
[6](#flat.set.overview-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[.](#flat.set.overview-6.sentence-1)
|
||
|
||
[*Note [2](#flat.set.overview-note-2)*:
|
||
|
||
This can result in the flat_set's being emptied[.](#flat.set.overview-6.sentence-2)
|
||
|
||
â *end note*]
|
||
|
||
[7](#flat.set.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[.](#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[.](#flat.set.overview-7.sentence-2)
|
||
|
||
[*Note [3](#flat.set.overview-note-3)*:
|
||
|
||
vector<bool> is not a sequence container[.](#flat.set.overview-7.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
[8](#flat.set.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[.](#flat.set.overview-8.sentence-1)
|
||
|
||
[9](#flat.set.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[.](#flat.set.overview-9.sentence-1)
|
||
|
||
[10](#flat.set.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"))[.](#flat.set.overview-10.sentence-1)
|
||
|
||
#### [23.6.11.2](#flat.set.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]](#flat.set.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]](#flat.set.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]](#flat.set.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](#flat.set.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](#flat.set.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[.](#flat.set.cons-1.sentence-1)
|
||
|
||
[2](#flat.set.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[.](#flat.set.cons-2.sentence-1)
|
||
|
||
#### [23.6.11.4](#flat.set.cons.alloc) Constructors with allocators [[flat.set.cons.alloc]](flat.set.cons.alloc)
|
||
|
||
[1](#flat.set.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[.](#flat.set.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](#flat.set.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"))[.](#flat.set.cons.alloc-2.sentence-1)
|
||
|
||
[3](#flat.set.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[.](#flat.set.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](#flat.set.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"))[.](#flat.set.cons.alloc-4.sentence-1)
|
||
|
||
[5](#flat.set.cons.alloc-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19226)
|
||
|
||
*Complexity*: Linear[.](#flat.set.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](#flat.set.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"))[.](#flat.set.cons.alloc-6.sentence-1)
|
||
|
||
#### [23.6.11.5](#flat.set.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](#flat.set.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[.](#flat.set.modifiers-1.sentence-1)
|
||
|
||
is_constructible_v<value_type, K> is true[.](#flat.set.modifiers-1.sentence-2)
|
||
|
||
[2](#flat.set.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[.](#flat.set.modifiers-2.sentence-1)
|
||
|
||
[3](#flat.set.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[.](#flat.set.modifiers-3.sentence-1)
|
||
|
||
Otherwise,
|
||
inserts a new element as if by emplace(std::forward<K>(x))[.](#flat.set.modifiers-3.sentence-2)
|
||
|
||
[4](#flat.set.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[.](#flat.set.modifiers-4.sentence-1)
|
||
|
||
The returned iterator points to the element
|
||
whose key is equivalent to x[.](#flat.set.modifiers-4.sentence-2)
|
||
|
||
[ð](#lib:insert,flat_set_)
|
||
|
||
`template<class InputIterator>
|
||
constexpr void insert(InputIterator first, InputIterator last);
|
||
`
|
||
|
||
[5](#flat.set.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[.](#flat.set.modifiers-5.sentence-2)
|
||
|
||
[6](#flat.set.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)[.](#flat.set.modifiers-6.sentence-1)
|
||
|
||
[7](#flat.set.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[.](#flat.set.modifiers-7.sentence-1)
|
||
|
||
[ð](#lib:insert,flat_set__)
|
||
|
||
`template<class InputIterator>
|
||
constexpr void insert(sorted_unique_t, InputIterator first, InputIterator last);
|
||
`
|
||
|
||
[8](#flat.set.modifiers-8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19347)
|
||
|
||
*Effects*: Equivalent to insert(first, last)[.](#flat.set.modifiers-8.sentence-1)
|
||
|
||
[9](#flat.set.modifiers-9)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19351)
|
||
|
||
*Complexity*: Linear[.](#flat.set.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](#flat.set.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[.](#flat.set.modifiers-10.sentence-2)
|
||
|
||
[11](#flat.set.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)[.](#flat.set.modifiers-11.sentence-1)
|
||
|
||
[12](#flat.set.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[.](#flat.set.modifiers-12.sentence-1)
|
||
|
||
[ð](#lib:swap,flat_set)
|
||
|
||
`constexpr void swap(flat_set& y) noexcept;
|
||
`
|
||
|
||
[13](#flat.set.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](#flat.set.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[.](#flat.set.modifiers-14.sentence-1)
|
||
|
||
[15](#flat.set.modifiers-15)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19413)
|
||
|
||
*Returns*: std::move(*c*)[.](#flat.set.modifiers-15.sentence-1)
|
||
|
||
[ð](#lib:replace,flat_set)
|
||
|
||
`constexpr void replace(container_type&& cont);
|
||
`
|
||
|
||
[16](#flat.set.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[.](#flat.set.modifiers-16.sentence-1)
|
||
|
||
[17](#flat.set.modifiers-17)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19429)
|
||
|
||
*Effects*: Equivalent to: *c* = std::move(cont);
|
||
|
||
#### [23.6.11.6](#flat.set.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](#flat.set.erasure-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19444)
|
||
|
||
*Preconditions*: Key meets the *Cpp17MoveAssignable* requirements[.](#flat.set.erasure-1.sentence-1)
|
||
|
||
[2](#flat.set.erasure-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19448)
|
||
|
||
*Effects*: Let E be bool(pred(as_const(e)))[.](#flat.set.erasure-2.sentence-1)
|
||
|
||
Erases all elements e in c for which E holds[.](#flat.set.erasure-2.sentence-2)
|
||
|
||
[3](#flat.set.erasure-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19453)
|
||
|
||
*Returns*: The number of elements erased[.](#flat.set.erasure-3.sentence-1)
|
||
|
||
[4](#flat.set.erasure-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19457)
|
||
|
||
*Complexity*: Exactly c.size() applications of the predicate[.](#flat.set.erasure-4.sentence-1)
|
||
|
||
[5](#flat.set.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"))[.](#flat.set.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"))[.](#flat.set.erasure-5.sentence-2)
|
||
|
||
[*Note [1](#flat.set.erasure-note-1)*:
|
||
|
||
c still meets its invariants, but can be empty[.](#flat.set.erasure-5.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
### [23.6.12](#flat.multiset) Class template flat_multiset [[flat.multiset]](flat.multiset)
|
||
|
||
#### [23.6.12.1](#flat.multiset.overview) Overview [[flat.multiset.overview]](flat.multiset.overview)
|
||
|
||
[1](#flat.multiset.overview-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19475)
|
||
|
||
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.overview-1.sentence-1)
|
||
|
||
flat_multiset 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"))[.](#flat.multiset.overview-1.sentence-2)
|
||
|
||
[2](#flat.multiset.overview-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19485)
|
||
|
||
A flat_multiset 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"))[.](#flat.multiset.overview-2.sentence-1)
|
||
|
||
flat_multiset meets the requirements of
|
||
an associative container ([[associative.reqmts]](associative.reqmts "23.2.7 Associative containers")), except that:
|
||
|
||
- [(2.1)](#flat.multiset.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)](#flat.multiset.overview-2.2)
|
||
|
||
it does not meet the requirements related to iterator invalidation, and
|
||
|
||
- [(2.3)](#flat.multiset.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[.](#flat.multiset.overview-2.sentence-2)
|
||
|
||
[*Note [1](#flat.multiset.overview-note-1)*:
|
||
|
||
A flat_multiset 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")[.](#flat.multiset.overview-2.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
[3](#flat.multiset.overview-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19510)
|
||
|
||
A flat_multiset also provides most operations
|
||
described in [[associative.reqmts]](associative.reqmts "23.2.7 Associative containers") for equal keys[.](#flat.multiset.overview-3.sentence-1)
|
||
|
||
This means that a flat_multiset supports
|
||
the a_eq operations in [[associative.reqmts]](associative.reqmts "23.2.7 Associative containers") but not the a_uniq operations[.](#flat.multiset.overview-3.sentence-2)
|
||
|
||
For a flat_multiset<Key>,
|
||
both the key_type and value_type are Key[.](#flat.multiset.overview-3.sentence-3)
|
||
|
||
[4](#flat.multiset.overview-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19519)
|
||
|
||
Descriptions are provided here only for operations on flat_multiset that are not described in one of the general sections or
|
||
for operations where there is additional semantic information[.](#flat.multiset.overview-4.sentence-1)
|
||
|
||
[5](#flat.multiset.overview-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19524)
|
||
|
||
A flat_multiset maintains the invariant
|
||
that the keys are sorted with respect to the comparison object[.](#flat.multiset.overview-5.sentence-1)
|
||
|
||
[6](#flat.multiset.overview-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19528)
|
||
|
||
If any member function in [[flat.multiset.defn]](#flat.multiset.defn "23.6.12.2 Definition") exits via an exception,
|
||
the invariant is restored[.](#flat.multiset.overview-6.sentence-1)
|
||
|
||
[*Note [2](#flat.multiset.overview-note-2)*:
|
||
|
||
This can result in the flat_multiset's being emptied[.](#flat.multiset.overview-6.sentence-2)
|
||
|
||
â *end note*]
|
||
|
||
[7](#flat.multiset.overview-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19535)
|
||
|
||
Any sequence container ([[sequence.reqmts]](sequence.reqmts "23.2.4 Sequence containers"))
|
||
supporting *Cpp17RandomAccessIterator* can be used to instantiate flat_multiset[.](#flat.multiset.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[.](#flat.multiset.overview-7.sentence-2)
|
||
|
||
[*Note [3](#flat.multiset.overview-note-3)*:
|
||
|
||
vector<bool> is not a sequence container[.](#flat.multiset.overview-7.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
[8](#flat.multiset.overview-8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19545)
|
||
|
||
The program is ill-formed if Key is not the same type
|
||
as KeyContainer::value_type[.](#flat.multiset.overview-8.sentence-1)
|
||
|
||
[9](#flat.multiset.overview-9)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19549)
|
||
|
||
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[.](#flat.multiset.overview-9.sentence-1)
|
||
|
||
[10](#flat.multiset.overview-10)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19554)
|
||
|
||
The types iterator and const_iterator meet
|
||
the constexpr iterator requirements ([[iterator.requirements.general]](iterator.requirements.general "24.3.1 General"))[.](#flat.multiset.overview-10.sentence-1)
|
||
|
||
#### [23.6.12.2](#flat.multiset.defn) Definition [[flat.multiset.defn]](flat.multiset.defn)
|
||
|
||
namespace std {template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>class flat_multiset {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.multiset.cons]](#flat.multiset.cons "23.6.12.3 Constructors"), constructorsconstexpr flat_multiset() : flat_multiset(key_compare()) { }constexpr explicit flat_multiset(const key_compare& comp): *c*(), *compare*(comp) { }constexpr explicit flat_multiset(container_type cont, const key_compare& comp = key_compare()); constexpr flat_multiset(sorted_equivalent_t, container_type cont, const key_compare& comp = key_compare()): *c*(std::move(cont)), *compare*(comp) { }template<class InputIterator>constexpr flat_multiset(InputIterator first, InputIterator last, const key_compare& comp = key_compare()): *c*(), *compare*(comp){ insert(first, last); }template<class InputIterator>constexpr flat_multiset(sorted_equivalent_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_multiset(from_range_t, R&& rg): flat_multiset(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_multiset(from_range_t, R&& rg, const key_compare& comp): flat_multiset(comp){ insert_range(std::forward<R>(rg)); }constexpr flat_multiset(initializer_list<value_type> il, const key_compare& comp = key_compare()): flat_multiset(il.begin(), il.end(), comp) { }constexpr flat_multiset(sorted_equivalent_t, initializer_list<value_type> il, const key_compare& comp = key_compare()): flat_multiset(sorted_equivalent, il.begin(), il.end(), comp) { }// [[flat.multiset.cons.alloc]](#flat.multiset.cons.alloc "23.6.12.4 Constructors with allocators"), constructors with allocatorstemplate<class Alloc>constexpr explicit flat_multiset(const Alloc& a); template<class Alloc>constexpr flat_multiset(const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_multiset(const container_type& cont, const Alloc& a); template<class Alloc>constexpr flat_multiset(const container_type& cont, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_multiset(sorted_equivalent_t, const container_type& cont, const Alloc& a); template<class Alloc>constexpr flat_multiset(sorted_equivalent_t, const container_type& cont, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_multiset(const flat_multiset&, const Alloc& a); template<class Alloc>constexpr flat_multiset(flat_multiset&&, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_multiset(InputIterator first, InputIterator last, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_multiset(InputIterator first, InputIterator last, const key_compare& comp, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last, const Alloc& a); template<class InputIterator, class Alloc>constexpr flat_multiset(sorted_equivalent_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_multiset(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_multiset(from_range_t, R&& rg, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_multiset(initializer_list<value_type> il, const Alloc& a); template<class Alloc>constexpr flat_multiset(initializer_list<value_type> il, const key_compare& comp, const Alloc& a); template<class Alloc>constexpr flat_multiset(sorted_equivalent_t, initializer_list<value_type> il, const Alloc& a); template<class Alloc>constexpr flat_multiset(sorted_equivalent_t, initializer_list<value_type> il, const key_compare& comp, const Alloc& a); constexpr flat_multiset& 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.multiset.modifiers]](#flat.multiset.modifiers "23.6.12.5 Modifiers"), modifierstemplate<class... Args> constexpr iterator emplace(Args&&... args); template<class... Args>constexpr iterator emplace_hint(const_iterator position, Args&&... args); constexpr iterator insert(const value_type& x){ return emplace(x); }constexpr iterator insert(value_type&& x){ return emplace(std::move(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 InputIterator>constexpr void insert(InputIterator first, InputIterator last); template<class InputIterator>constexpr void insert(sorted_equivalent_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_equivalent_t, initializer_list<value_type> il){ insert(sorted_equivalent, 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_multiset& 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_multiset& x, const flat_multiset& y); friend constexpr *synth-three-way-result*<value_type>operator<=>(const flat_multiset& x, const flat_multiset& y); friend constexpr void swap(flat_multiset& x, flat_multiset& 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_multiset(KeyContainer, Compare = Compare())-> flat_multiset<typename KeyContainer::value_type, Compare, KeyContainer>; template<class KeyContainer, class Allocator> flat_multiset(KeyContainer, Allocator)-> flat_multiset<typename KeyContainer::value_type,
|
||
less<typename KeyContainer::value_type>, KeyContainer>; template<class KeyContainer, class Compare, class Allocator> flat_multiset(KeyContainer, Compare, Allocator)-> flat_multiset<typename KeyContainer::value_type, Compare, KeyContainer>; template<class KeyContainer, class Compare = less<typename KeyContainer::value_type>> flat_multiset(sorted_equivalent_t, KeyContainer, Compare = Compare())-> flat_multiset<typename KeyContainer::value_type, Compare, KeyContainer>; template<class KeyContainer, class Allocator> flat_multiset(sorted_equivalent_t, KeyContainer, Allocator)-> flat_multiset<typename KeyContainer::value_type,
|
||
less<typename KeyContainer::value_type>, KeyContainer>; template<class KeyContainer, class Compare, class Allocator> flat_multiset(sorted_equivalent_t, KeyContainer, Compare, Allocator)-> flat_multiset<typename KeyContainer::value_type, Compare, KeyContainer>; template<class InputIterator, class Compare = less<*iter-value-type*<InputIterator>>> flat_multiset(InputIterator, InputIterator, Compare = Compare())-> flat_multiset<*iter-value-type*<InputIterator>, Compare>; template<class InputIterator, class Compare = less<*iter-value-type*<InputIterator>>> flat_multiset(sorted_equivalent_t, InputIterator, InputIterator, Compare = Compare())-> flat_multiset<*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_multiset(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())-> flat_multiset<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_multiset(from_range_t, R&&, Allocator)-> flat_multiset<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_multiset(initializer_list<Key>, Compare = Compare())-> flat_multiset<Key, Compare>; template<class Key, class Compare = less<Key>> flat_multiset(sorted_equivalent_t, initializer_list<Key>, Compare = Compare())-> flat_multiset<Key, Compare>; template<class Key, class Compare, class KeyContainer, class Allocator>struct uses_allocator<flat_multiset<Key, Compare, KeyContainer>, Allocator>: bool_constant<uses_allocator_v<KeyContainer, Allocator>> { };}
|
||
|
||
#### [23.6.12.3](#flat.multiset.cons) Constructors [[flat.multiset.cons]](flat.multiset.cons)
|
||
|
||
[ð](#lib:flat_multiset,constructor)
|
||
|
||
`constexpr explicit flat_multiset(container_type cont, const key_compare& comp = key_compare());
|
||
`
|
||
|
||
[1](#flat.multiset.cons-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19839)
|
||
|
||
*Effects*: Initializes *c* with std::move(cont) and*compare* with comp, and
|
||
sorts the range [begin(), end()) with respect to *compare*[.](#flat.multiset.cons-1.sentence-1)
|
||
|
||
[2](#flat.multiset.cons-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19845)
|
||
|
||
*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[.](#flat.multiset.cons-2.sentence-1)
|
||
|
||
#### [23.6.12.4](#flat.multiset.cons.alloc) Constructors with allocators [[flat.multiset.cons.alloc]](flat.multiset.cons.alloc)
|
||
|
||
[1](#flat.multiset.cons.alloc-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19853)
|
||
|
||
The constructors in this subclause shall not participate in overload resolution
|
||
unless uses_allocator_v<container_type, Alloc> is true[.](#flat.multiset.cons.alloc-1.sentence-1)
|
||
|
||
[ð](#lib:flat_multiset,constructor_)
|
||
|
||
`template<class Alloc>
|
||
constexpr flat_multiset(const container_type& cont, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multiset(const container_type& cont, const key_compare& comp, const Alloc& a);
|
||
`
|
||
|
||
[2](#flat.multiset.cons.alloc-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19866)
|
||
|
||
*Effects*: Equivalent to flat_multiset(cont) andflat_multiset(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"))[.](#flat.multiset.cons.alloc-2.sentence-1)
|
||
|
||
[3](#flat.multiset.cons.alloc-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19873)
|
||
|
||
*Complexity*: Same as flat_multiset(cont) andflat_multiset(cont, comp), respectively[.](#flat.multiset.cons.alloc-3.sentence-1)
|
||
|
||
[ð](#lib:flat_multiset,constructor__)
|
||
|
||
`template<class Alloc>
|
||
constexpr flat_multiset(sorted_equivalent_t, const container_type& cont, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multiset(sorted_equivalent_t, const container_type& cont,
|
||
const key_compare& comp, const Alloc& a);
|
||
`
|
||
|
||
[4](#flat.multiset.cons.alloc-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19889)
|
||
|
||
*Effects*: Equivalent to flat_multiset(sorted_equivalent, cont) andflat_multiset(sorted_equivalent, 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"))[.](#flat.multiset.cons.alloc-4.sentence-1)
|
||
|
||
[5](#flat.multiset.cons.alloc-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19896)
|
||
|
||
*Complexity*: Linear[.](#flat.multiset.cons.alloc-5.sentence-1)
|
||
|
||
[ð](#lib:flat_multiset,constructor___)
|
||
|
||
`template<class Alloc>
|
||
constexpr explicit flat_multiset(const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multiset(const key_compare& comp, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multiset(const flat_multiset&, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multiset(flat_multiset&&, const Alloc& a);
|
||
template<class InputIterator, class Alloc>
|
||
constexpr flat_multiset(InputIterator first, InputIterator last, const Alloc& a);
|
||
template<class InputIterator, class Alloc>
|
||
constexpr flat_multiset(InputIterator first, InputIterator last,
|
||
const key_compare& comp, const Alloc& a);
|
||
template<class InputIterator, class Alloc>
|
||
constexpr flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
|
||
const Alloc& a);
|
||
template<class InputIterator, class Alloc>
|
||
constexpr flat_multiset(sorted_equivalent_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_multiset(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_multiset(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multiset(initializer_list<value_type> il, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multiset(initializer_list<value_type> il, const key_compare& comp,
|
||
const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multiset(sorted_equivalent_t, initializer_list<value_type> il, const Alloc& a);
|
||
template<class Alloc>
|
||
constexpr flat_multiset(sorted_equivalent_t, initializer_list<value_type> il,
|
||
const key_compare& comp, const Alloc& a);
|
||
`
|
||
|
||
[6](#flat.multiset.cons.alloc-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19939)
|
||
|
||
*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"))[.](#flat.multiset.cons.alloc-6.sentence-1)
|
||
|
||
#### [23.6.12.5](#flat.multiset.modifiers) Modifiers [[flat.multiset.modifiers]](flat.multiset.modifiers)
|
||
|
||
[ð](#lib:emplace,flat_multiset)
|
||
|
||
`template<class... Args> constexpr iterator emplace(Args&&... args);
|
||
`
|
||
|
||
[1](#flat.multiset.modifiers-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19954)
|
||
|
||
*Constraints*: is_constructible_v<value_type, Args...> is true[.](#flat.multiset.modifiers-1.sentence-1)
|
||
|
||
[2](#flat.multiset.modifiers-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19958)
|
||
|
||
*Effects*: First, initializes an object t of type value_type with std::forward<Args>(args)...,
|
||
then inserts t as if by:auto it = ranges::upper_bound(*c*, t, *compare*);*c*.insert(it, std::move(t));
|
||
|
||
[3](#flat.multiset.modifiers-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19968)
|
||
|
||
*Returns*: An iterator that points to the inserted element[.](#flat.multiset.modifiers-3.sentence-1)
|
||
|
||
[ð](#lib:insert,flat_multiset)
|
||
|
||
`template<class InputIterator>
|
||
constexpr void insert(InputIterator first, InputIterator last);
|
||
`
|
||
|
||
[4](#flat.multiset.modifiers-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19980)
|
||
|
||
*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*,
|
||
and merges the resulting sorted range and
|
||
the sorted range of pre-existing elements into a single sorted range[.](#flat.multiset.modifiers-4.sentence-2)
|
||
|
||
[5](#flat.multiset.modifiers-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19990)
|
||
|
||
*Complexity*: N + MlogM, where N is size() before the operation and M is distance(first, last)[.](#flat.multiset.modifiers-5.sentence-1)
|
||
|
||
[6](#flat.multiset.modifiers-6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19995)
|
||
|
||
*Remarks*: Since this operation performs an in-place merge, it may allocate memory[.](#flat.multiset.modifiers-6.sentence-1)
|
||
|
||
[ð](#lib:insert,flat_multiset_)
|
||
|
||
`template<class InputIterator>
|
||
constexpr void insert(sorted_equivalent_t, InputIterator first, InputIterator last);
|
||
`
|
||
|
||
[7](#flat.multiset.modifiers-7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20007)
|
||
|
||
*Effects*: Equivalent to insert(first, last)[.](#flat.multiset.modifiers-7.sentence-1)
|
||
|
||
[8](#flat.multiset.modifiers-8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20011)
|
||
|
||
*Complexity*: Linear[.](#flat.multiset.modifiers-8.sentence-1)
|
||
|
||
[ð](#lib:swap,flat_multiset)
|
||
|
||
`constexpr void swap(flat_multiset& y) noexcept;
|
||
`
|
||
|
||
[9](#flat.multiset.modifiers-9)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20022)
|
||
|
||
*Effects*: Equivalent to:ranges::swap(*compare*, y.*compare*);
|
||
ranges::swap(*c*, y.*c*);
|
||
|
||
[ð](#lib:extract,flat_multiset)
|
||
|
||
`constexpr container_type extract() &&;
|
||
`
|
||
|
||
[10](#flat.multiset.modifiers-10)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20037)
|
||
|
||
*Postconditions*: *this is emptied, even if the function exits via an exception[.](#flat.multiset.modifiers-10.sentence-1)
|
||
|
||
[11](#flat.multiset.modifiers-11)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20041)
|
||
|
||
*Returns*: std::move(*c*)[.](#flat.multiset.modifiers-11.sentence-1)
|
||
|
||
[ð](#lib:replace,flat_multiset)
|
||
|
||
`constexpr void replace(container_type&& cont);
|
||
`
|
||
|
||
[12](#flat.multiset.modifiers-12)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20052)
|
||
|
||
*Preconditions*: The elements of cont are sorted with respect to *compare*[.](#flat.multiset.modifiers-12.sentence-1)
|
||
|
||
[13](#flat.multiset.modifiers-13)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20056)
|
||
|
||
*Effects*: Equivalent to: *c* = std::move(cont);
|
||
|
||
#### [23.6.12.6](#flat.multiset.erasure) Erasure [[flat.multiset.erasure]](flat.multiset.erasure)
|
||
|
||
[ð](#lib:erase_if,flat_multiset)
|
||
|
||
`template<class Key, class Compare, class KeyContainer, class Predicate>
|
||
constexpr typename flat_multiset<Key, Compare, KeyContainer>::size_type
|
||
erase_if(flat_multiset<Key, Compare, KeyContainer>& c, Predicate pred);
|
||
`
|
||
|
||
[1](#flat.multiset.erasure-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20071)
|
||
|
||
*Preconditions*: Key meets the *Cpp17MoveAssignable* requirements[.](#flat.multiset.erasure-1.sentence-1)
|
||
|
||
[2](#flat.multiset.erasure-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20075)
|
||
|
||
*Effects*: Let E be bool(pred(as_const(e)))[.](#flat.multiset.erasure-2.sentence-1)
|
||
|
||
Erases all elements e in c for which E holds[.](#flat.multiset.erasure-2.sentence-2)
|
||
|
||
[3](#flat.multiset.erasure-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20080)
|
||
|
||
*Returns*: The number of elements erased[.](#flat.multiset.erasure-3.sentence-1)
|
||
|
||
[4](#flat.multiset.erasure-4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20084)
|
||
|
||
*Complexity*: Exactly c.size() applications of the predicate[.](#flat.multiset.erasure-4.sentence-1)
|
||
|
||
[5](#flat.multiset.erasure-5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20088)
|
||
|
||
*Remarks*: Stable ([[algorithm.stable]](algorithm.stable "16.4.6.8 Requirements for stable algorithms"))[.](#flat.multiset.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"))[.](#flat.multiset.erasure-5.sentence-2)
|
||
|
||
[*Note [1](#flat.multiset.erasure-note-1)*:
|
||
|
||
c still meets its invariants, but can be empty[.](#flat.multiset.erasure-5.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
### [23.6.13](#format) Container adaptors formatting [[container.adaptors.format]](container.adaptors.format)
|
||
|
||
[1](#format-1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20100)
|
||
|
||
For each ofqueue,priority_queue, andstack,
|
||
the library provides the following formatter specialization
|
||
where *adaptor-type* is the name of the template:
|
||
|
||
[ð](#lib:formatter)
|
||
|
||
namespace std {template<class charT, class T, [formattable](format.formattable#concept:formattable "28.5.6.3 Concept formattable [format.formattable]")<charT> Container, class... U>struct formatter<*adaptor-type*<T, Container, U...>, charT> {private:using *maybe-const-container* = // *exposition only**fmt-maybe-const*<Container, charT>; using *maybe-const-adaptor* = // *exposition only**maybe-const*<is_const_v<*maybe-const-container*>, // see [[ranges.syn]](ranges.syn "25.2 Header <ranges> synopsis")*adaptor-type*<T, Container, U...>>;
|
||
formatter<ranges::ref_view<*maybe-const-container*>, charT> *underlying_*; // *exposition only*public:template<class ParseContext>constexpr typename ParseContext::iterator
|
||
parse(ParseContext& ctx); template<class FormatContext>typename FormatContext::iterator
|
||
format(*maybe-const-adaptor*& r, FormatContext& ctx) const; };}
|
||
|
||
[ð](#lib:parse,formatter)
|
||
|
||
`template<class ParseContext>
|
||
constexpr typename ParseContext::iterator
|
||
parse(ParseContext& ctx);
|
||
`
|
||
|
||
[2](#format-2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20140)
|
||
|
||
*Effects*: Equivalent to: return *underlying_*.parse(ctx);
|
||
|
||
[ð](#lib:format,formatter)
|
||
|
||
`template<class FormatContext>
|
||
typename FormatContext::iterator
|
||
format(maybe-const-adaptor& r, FormatContext& ctx) const;
|
||
`
|
||
|
||
[3](#format-3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L20153)
|
||
|
||
*Effects*: Equivalent to: return *underlying_*.format(r.c, ctx);
|