166 lines
6.3 KiB
Markdown
166 lines
6.3 KiB
Markdown
[flat.multimap.overview]
|
||
|
||
# 23 Containers library [[containers]](./#containers)
|
||
|
||
## 23.6 Container adaptors [[container.adaptors]](container.adaptors#flat.multimap.overview)
|
||
|
||
### 23.6.9 Class template flat_multimap [[flat.multimap]](flat.multimap#overview)
|
||
|
||
#### 23.6.9.1 Overview [flat.multimap.overview]
|
||
|
||
[1](#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[.](#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"))[.](#1.sentence-2)
|
||
|
||
[2](#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"))[.](#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)](#2.1)
|
||
|
||
it does not meet the requirements related to node handles ([[container.node]](container.node "23.2.5 Node handles")),
|
||
|
||
- [(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 map is linear,
|
||
including the ones that take an insertion position iterator[.](#2.sentence-2)
|
||
|
||
[*Note [1](#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"))[.](#2.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
[3](#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[.](#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[.](#3.sentence-2)
|
||
|
||
For a flat_multimap<Key, T> the key_type is Key and
|
||
the value_type is pair<Key, T>[.](#3.sentence-3)
|
||
|
||
[4](#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[.](#4.sentence-1)
|
||
|
||
[*Example [1](#example-1)*:
|
||
|
||
flat_multimap constructors and emplace do not erase
|
||
non-unique elements after sorting them[.](#4.sentence-2)
|
||
|
||
â *end example*]
|
||
|
||
[5](#5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L18203)
|
||
|
||
A flat_multimap maintains the following invariants:
|
||
|
||
- [(5.1)](#5.1)
|
||
|
||
it contains the same number of keys and values;
|
||
|
||
- [(5.2)](#5.2)
|
||
|
||
the keys are sorted with respect to the comparison object; and
|
||
|
||
- [(5.3)](#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[.](#5.sentence-1)
|
||
|
||
[6](#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[.](#6.sentence-1)
|
||
|
||
[*Note [2](#note-2)*:
|
||
|
||
This can result in the flat_multimap being emptied[.](#6.sentence-2)
|
||
|
||
â *end note*]
|
||
|
||
[7](#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[.](#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#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[.](#8.sentence-1)
|
||
|
||
[9](#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[.](#9.sentence-1)
|
||
|
||
[10](#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[.](#10.sentence-1)
|
||
|
||
[11](#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"))[.](#11.sentence-1)
|