135 lines
5.3 KiB
Markdown
135 lines
5.3 KiB
Markdown
[flat.multiset.overview]
|
||
|
||
# 23 Containers library [[containers]](./#containers)
|
||
|
||
## 23.6 Container adaptors [[container.adaptors]](container.adaptors#flat.multiset.overview)
|
||
|
||
### 23.6.12 Class template flat_multiset [[flat.multiset]](flat.multiset#overview)
|
||
|
||
#### 23.6.12.1 Overview [flat.multiset.overview]
|
||
|
||
[1](#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[.](#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"))[.](#1.sentence-2)
|
||
|
||
[2](#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"))[.](#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)](#2.1)
|
||
|
||
it does not meet the requirements
|
||
related to node handles ([[container.node.overview]](container.node.overview "23.2.5.1 Overview")),
|
||
|
||
- [(2.2)](#2.2)
|
||
|
||
it does not meet the requirements related to iterator invalidation, and
|
||
|
||
- [(2.3)](#2.3)
|
||
|
||
the time complexity of the operations
|
||
that insert or erase a single element from the
|
||
set is linear,
|
||
including the ones that take an insertion position iterator[.](#2.sentence-2)
|
||
|
||
[*Note [1](#note-1)*:
|
||
|
||
A flat_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")[.](#2.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
[3](#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[.](#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[.](#3.sentence-2)
|
||
|
||
For a flat_multiset<Key>,
|
||
both the key_type and value_type are Key[.](#3.sentence-3)
|
||
|
||
[4](#4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#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[.](#4.sentence-1)
|
||
|
||
[5](#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[.](#5.sentence-1)
|
||
|
||
[6](#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[.](#6.sentence-1)
|
||
|
||
[*Note [2](#note-2)*:
|
||
|
||
This can result in the flat_multiset's being emptied[.](#6.sentence-2)
|
||
|
||
â *end note*]
|
||
|
||
[7](#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[.](#7.sentence-1)
|
||
|
||
In particular,vector ([[vector]](vector "23.3.13 Class template vector")) and deque ([[deque]](deque "23.3.5 Class template deque")) can be used[.](#7.sentence-2)
|
||
|
||
[*Note [3](#note-3)*:
|
||
|
||
vector<bool> is not a sequence container[.](#7.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
[8](#8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L19545)
|
||
|
||
The program is ill-formed if Key is not the same type
|
||
as KeyContainer::value_type[.](#8.sentence-1)
|
||
|
||
[9](#9)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#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[.](#9.sentence-1)
|
||
|
||
[10](#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"))[.](#10.sentence-1)
|