From Jason Turner

[flat.multimap]

C++20 → C++23 23.6 KB 521 lines
Current Draft | LaTeX Source
Archived: C++20 | C++23
Markdown: C++20 | C++23
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpjcq4b4uf/{from.md → to.md} +518 -0
tmp/tmpjcq4b4uf/{from.md → to.md} RENAMED
@@ -0,0 +1,518 @@
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
+ ### Class template `flat_multimap` <a id="flat.multimap">[[flat.multimap]]</a>
2
+
3
+ #### Overview <a id="flat.multimap.overview">[[flat.multimap.overview]]</a>
4
+
5
+ A `flat_multimap` is a container adaptor that provides an associative
6
+ container interface that supports equivalent keys (i.e., possibly
7
+ containing multiple copies of the same key value) and provides for fast
8
+ retrieval of values of another type `T` based on the keys.
9
+ `flat_multimap` supports iterators that meet the *Cpp17InputIterator*
10
+ requirements and model the `random_access_iterator` concept
11
+ [[iterator.concept.random.access]].
12
+
13
+ A `flat_multimap` meets all of the requirements for a container
14
+ [[container.reqmts]] and for a reversible container
15
+ [[container.rev.reqmts]], plus the optional container requirements
16
+ [[container.opt.reqmts]]. `flat_multimap` meets the requirements of an
17
+ associative container [[associative.reqmts]], except that:
18
+
19
+ - it does not meet the requirements related to node handles
20
+ [[container.node]],
21
+ - it does not meet the requirements related to iterator invalidation,
22
+ and
23
+ - the time complexity of the operations that insert or erase a single
24
+ element from the map is linear, including the ones that take an
25
+ insertion position iterator.
26
+
27
+ [*Note 1*: A `flat_multimap` does not meet the additional requirements
28
+ of an allocator-aware container
29
+ [[container.alloc.reqmts]]. — *end note*]
30
+
31
+ A `flat_multimap` also provides most operations described in
32
+ [[associative.reqmts]] for equal keys. This means that a `flat_multimap`
33
+ supports the `a_eq` operations in [[associative.reqmts]] but not the
34
+ `a_uniq` operations. For a `flat_multimap<Key, T>` the `key_type` is
35
+ `Key` and the `value_type` is `pair<Key, T>`.
36
+
37
+ Except as otherwise noted, operations on `flat_multimap` are equivalent
38
+ to those of `flat_map`, except that `flat_multimap` operations do not
39
+ remove or replace elements with equal keys.
40
+
41
+ [*Example 1*: `flat_multimap` constructors and emplace do not erase
42
+ non-unique elements after sorting them. — *end example*]
43
+
44
+ A `flat_multimap` maintains the following invariants:
45
+
46
+ - it contains the same number of keys and values;
47
+ - the keys are sorted with respect to the comparison object; and
48
+ - the value at offset `off` within the value container is the value
49
+ associated with the key at offset `off` within the key container.
50
+
51
+ If any member function in [[flat.multimap.defn]] exits via an exception,
52
+ the invariants are restored.
53
+
54
+ [*Note 2*: This can result in the `flat_multimap` being
55
+ emptied. — *end note*]
56
+
57
+ Any type `C` that meets the sequence container requirements
58
+ [[sequence.reqmts]] can be used to instantiate `flat_multimap`, as long
59
+ as `C::iterator` meets the *Cpp17RandomAccessIterator* requirements and
60
+ invocations of member functions `C::size` and `C::max_size` do not exit
61
+ via an exception. In particular, `vector` [[vector]] and `deque`
62
+ [[deque]] can be used.
63
+
64
+ [*Note 3*: `vector<bool>` is not a sequence container. — *end note*]
65
+
66
+ The program is ill-formed if `Key` is not the same type as
67
+ `KeyContainer::value_type` or `T` is not the same type as
68
+ `MappedContainer::value_type`.
69
+
70
+ The effect of calling a constructor that takes both `key_container_type`
71
+ and `mapped_container_type` arguments with containers of different sizes
72
+ is undefined.
73
+
74
+ The effect of calling a constructor or member function that takes a
75
+ `sorted_equivalent_t` argument with a container, containers, or range
76
+ that are not sorted with respect to `key_comp()` is undefined.
77
+
78
+ #### Definition <a id="flat.multimap.defn">[[flat.multimap.defn]]</a>
79
+
80
+ ``` cpp
81
+ namespace std {
82
+ template<class Key, class T, class Compare = less<Key>,
83
+ class KeyContainer = vector<Key>, class MappedContainer = vector<T>>
84
+ class flat_multimap {
85
+ public:
86
+ // types
87
+ using key_type = Key;
88
+ using mapped_type = T;
89
+ using value_type = pair<key_type, mapped_type>;
90
+ using key_compare = Compare;
91
+ using reference = pair<const key_type&, mapped_type&>;
92
+ using const_reference = pair<const key_type&, const mapped_type&>;
93
+ using size_type = size_t;
94
+ using difference_type = ptrdiff_t;
95
+ using iterator = implementation-defined // type of flat_multimap::iterator; // see [container.requirements]
96
+ using const_iterator = implementation-defined // type of flat_multimap::const_iterator; // see [container.requirements]
97
+ using reverse_iterator = std::reverse_iterator<iterator>;
98
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>;
99
+ using key_container_type = KeyContainer;
100
+ using mapped_container_type = MappedContainer;
101
+
102
+ class value_compare {
103
+ private:
104
+ key_compare comp; // exposition only
105
+ value_compare(key_compare c) : comp(c) { } // exposition only
106
+
107
+ public:
108
+ bool operator()(const_reference x, const_reference y) const {
109
+ return comp(x.first, y.first);
110
+ }
111
+ };
112
+
113
+ struct containers {
114
+ key_container_type keys;
115
+ mapped_container_type values;
116
+ };
117
+
118
+ // [flat.multimap.cons], construct/copy/destroy
119
+ flat_multimap() : flat_multimap(key_compare()) { }
120
+
121
+ flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,
122
+ const key_compare& comp = key_compare());
123
+ template<class Allocator>
124
+ flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
125
+ const Allocator& a);
126
+ template<class Allocator>
127
+ flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
128
+ const key_compare& comp, const Allocator& a);
129
+
130
+ flat_multimap(sorted_equivalent_t,
131
+ key_container_type key_cont, mapped_container_type mapped_cont,
132
+ const key_compare& comp = key_compare());
133
+ template<class Allocator>
134
+ flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
135
+ const mapped_container_type& mapped_cont, const Allocator& a);
136
+ template<class Allocator>
137
+ flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
138
+ const mapped_container_type& mapped_cont,
139
+ const key_compare& comp, const Allocator& a);
140
+
141
+ explicit flat_multimap(const key_compare& comp)
142
+ : c(), compare(comp) { }
143
+ template<class Allocator>
144
+ flat_multimap(const key_compare& comp, const Allocator& a);
145
+ template<class Allocator>
146
+ explicit flat_multimap(const Allocator& a);
147
+
148
+ template<class InputIterator>
149
+ flat_multimap(InputIterator first, InputIterator last,
150
+ const key_compare& comp = key_compare())
151
+ : c(), compare(comp)
152
+ { insert(first, last); }
153
+ template<class InputIterator, class Allocator>
154
+ flat_multimap(InputIterator first, InputIterator last,
155
+ const key_compare& comp, const Allocator& a);
156
+ template<class InputIterator, class Allocator>
157
+ flat_multimap(InputIterator first, InputIterator last, const Allocator& a);
158
+
159
+ template<container-compatible-range<value_type> R>
160
+ flat_multimap(from_range_t fr, R&& rg)
161
+ : flat_multimap(fr, std::forward<R>(rg), key_compare()) { }
162
+ template<container-compatible-range<value_type> R, class Allocator>
163
+ flat_multimap(from_range_t, R&& rg, const Allocator& a);
164
+ template<container-compatible-range<value_type> R>
165
+ flat_multimap(from_range_t, R&& rg, const key_compare& comp)
166
+ : flat_multimap(comp) { insert_range(std::forward<R>(rg)); }
167
+ template<container-compatible-range<value_type> R, class Allocator>
168
+ flat_multimap(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
169
+
170
+ template<class InputIterator>
171
+ flat_multimap(sorted_equivalent_t s, InputIterator first, InputIterator last,
172
+ const key_compare& comp = key_compare())
173
+ : c(), compare(comp) { insert(s, first, last); }
174
+ template<class InputIterator, class Allocator>
175
+ flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
176
+ const key_compare& comp, const Allocator& a);
177
+ template<class InputIterator, class Allocator>
178
+ flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
179
+ const Allocator& a);
180
+
181
+ flat_multimap(initializer_list<value_type> il, const key_compare& comp = key_compare())
182
+ : flat_multimap(il.begin(), il.end(), comp) { }
183
+ template<class Allocator>
184
+ flat_multimap(initializer_list<value_type> il, const key_compare& comp,
185
+ const Allocator& a);
186
+ template<class Allocator>
187
+ flat_multimap(initializer_list<value_type> il, const Allocator& a);
188
+
189
+ flat_multimap(sorted_equivalent_t s, initializer_list<value_type> il,
190
+ const key_compare& comp = key_compare())
191
+ : flat_multimap(s, il.begin(), il.end(), comp) { }
192
+ template<class Allocator>
193
+ flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
194
+ const key_compare& comp, const Allocator& a);
195
+ template<class Allocator>
196
+ flat_multimap(sorted_equivalent_t, initializer_list<value_type> il, const Allocator& a);
197
+
198
+ flat_multimap& operator=(initializer_list<value_type> il);
199
+
200
+ // iterators
201
+ iterator begin() noexcept;
202
+ const_iterator begin() const noexcept;
203
+ iterator end() noexcept;
204
+ const_iterator end() const noexcept;
205
+
206
+ reverse_iterator rbegin() noexcept;
207
+ const_reverse_iterator rbegin() const noexcept;
208
+ reverse_iterator rend() noexcept;
209
+ const_reverse_iterator rend() const noexcept;
210
+
211
+ const_iterator cbegin() const noexcept;
212
+ const_iterator cend() const noexcept;
213
+ const_reverse_iterator crbegin() const noexcept;
214
+ const_reverse_iterator crend() const noexcept;
215
+
216
+ // capacity
217
+ [[nodiscard]] bool empty() const noexcept;
218
+ size_type size() const noexcept;
219
+ size_type max_size() const noexcept;
220
+
221
+ // modifiers
222
+ template<class... Args> iterator emplace(Args&&... args);
223
+ template<class... Args>
224
+ iterator emplace_hint(const_iterator position, Args&&... args);
225
+
226
+ iterator insert(const value_type& x)
227
+ { return emplace(x); }
228
+ iterator insert(value_type&& x)
229
+ { return emplace(std::move(x)); }
230
+ iterator insert(const_iterator position, const value_type& x)
231
+ { return emplace_hint(position, x); }
232
+ iterator insert(const_iterator position, value_type&& x)
233
+ { return emplace_hint(position, std::move(x)); }
234
+
235
+ template<class P> iterator insert(P&& x);
236
+ template<class P>
237
+ iterator insert(const_iterator position, P&&);
238
+ template<class InputIterator>
239
+ void insert(InputIterator first, InputIterator last);
240
+ template<class InputIterator>
241
+ void insert(sorted_equivalent_t, InputIterator first, InputIterator last);
242
+ template<container-compatible-range<value_type> R>
243
+ void insert_range(R&& rg);
244
+
245
+ void insert(initializer_list<value_type> il)
246
+ { insert(il.begin(), il.end()); }
247
+ void insert(sorted_equivalent_t s, initializer_list<value_type> il)
248
+ { insert(s, il.begin(), il.end()); }
249
+
250
+ containers extract() &&;
251
+ void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);
252
+
253
+ iterator erase(iterator position);
254
+ iterator erase(const_iterator position);
255
+ size_type erase(const key_type& x);
256
+ template<class K> size_type erase(K&& x);
257
+ iterator erase(const_iterator first, const_iterator last);
258
+
259
+ void swap(flat_multimap&) noexcept;
260
+ void clear() noexcept;
261
+
262
+ // observers
263
+ key_compare key_comp() const;
264
+ value_compare value_comp() const;
265
+
266
+ const key_container_type& keys() const noexcept { return c.keys; }
267
+ const mapped_container_type& values() const noexcept { return c.values; }
268
+
269
+ // map operations
270
+ iterator find(const key_type& x);
271
+ const_iterator find(const key_type& x) const;
272
+ template<class K> iterator find(const K& x);
273
+ template<class K> const_iterator find(const K& x) const;
274
+
275
+ size_type count(const key_type& x) const;
276
+ template<class K> size_type count(const K& x) const;
277
+
278
+ bool contains(const key_type& x) const;
279
+ template<class K> bool contains(const K& x) const;
280
+
281
+ iterator lower_bound(const key_type& x);
282
+ const_iterator lower_bound(const key_type& x) const;
283
+ template<class K> iterator lower_bound(const K& x);
284
+ template<class K> const_iterator lower_bound(const K& x) const;
285
+
286
+ iterator upper_bound(const key_type& x);
287
+ const_iterator upper_bound(const key_type& x) const;
288
+ template<class K> iterator upper_bound(const K& x);
289
+ template<class K> const_iterator upper_bound(const K& x) const;
290
+
291
+ pair<iterator, iterator> equal_range(const key_type& x);
292
+ pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
293
+ template<class K>
294
+ pair<iterator, iterator> equal_range(const K& x);
295
+ template<class K>
296
+ pair<const_iterator, const_iterator> equal_range(const K& x) const;
297
+
298
+ friend bool operator==(const flat_multimap& x, const flat_multimap& y);
299
+
300
+ friend synth-three-way-result<value_type>
301
+ operator<=>(const flat_multimap& x, const flat_multimap& y);
302
+
303
+ friend void swap(flat_multimap& x, flat_multimap& y) noexcept
304
+ { x.swap(y); }
305
+
306
+ private:
307
+ containers c; // exposition only
308
+ key_compare compare; // exposition only
309
+ };
310
+
311
+ template<class KeyContainer, class MappedContainer,
312
+ class Compare = less<typename KeyContainer::value_type>>
313
+ flat_multimap(KeyContainer, MappedContainer, Compare = Compare())
314
+ -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
315
+ Compare, KeyContainer, MappedContainer>;
316
+
317
+ template<class KeyContainer, class MappedContainer, class Allocator>
318
+ flat_multimap(KeyContainer, MappedContainer, Allocator)
319
+ -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
320
+ less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
321
+ template<class KeyContainer, class MappedContainer, class Compare, class Allocator>
322
+ flat_multimap(KeyContainer, MappedContainer, Compare, Allocator)
323
+ -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
324
+ Compare, KeyContainer, MappedContainer>;
325
+
326
+ template<class KeyContainer, class MappedContainer,
327
+ class Compare = less<typename KeyContainer::value_type>>
328
+ flat_multimap(sorted_equivalent_t, KeyContainer, MappedContainer, Compare = Compare())
329
+ -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
330
+ Compare, KeyContainer, MappedContainer>;
331
+
332
+ template<class KeyContainer, class MappedContainer, class Allocator>
333
+ flat_multimap(sorted_equivalent_t, KeyContainer, MappedContainer, Allocator)
334
+ -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
335
+ less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
336
+ template<class KeyContainer, class MappedContainer, class Compare, class Allocator>
337
+ flat_multimap(sorted_equivalent_t, KeyContainer, MappedContainer, Compare, Allocator)
338
+ -> flat_multimap<typename KeyContainer::value_type, typename MappedContainer::value_type,
339
+ Compare, KeyContainer, MappedContainer>;
340
+
341
+ template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>>
342
+ flat_multimap(InputIterator, InputIterator, Compare = Compare())
343
+ -> flat_multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Compare>;
344
+
345
+ template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>>
346
+ flat_multimap(sorted_equivalent_t, InputIterator, InputIterator, Compare = Compare())
347
+ -> flat_multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Compare>;
348
+
349
+ template<ranges::input_range R, class Compare = less<range-key-type<R>>,
350
+ class Allocator = allocator<byte>>
351
+ flat_multimap(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
352
+ -> flat_multimap<range-key-type<R>, range-mapped-type<R>, Compare,
353
+ vector<range-key-type<R>,
354
+ alloc-rebind<Allocator, range-key-type<R>>>,
355
+ vector<range-mapped-type<R>,
356
+ alloc-rebind<Allocator, range-mapped-type<R>>>>;
357
+
358
+ template<ranges::input_range R, class Allocator>
359
+ flat_multimap(from_range_t, R&&, Allocator)
360
+ -> flat_multimap<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>,
361
+ vector<range-key-type<R>,
362
+ alloc-rebind<Allocator, range-key-type<R>>>,
363
+ vector<range-mapped-type<R>,
364
+ alloc-rebind<Allocator, range-mapped-type<R>>>>;
365
+
366
+ template<class Key, class T, class Compare = less<Key>>
367
+ flat_multimap(initializer_list<pair<Key, T>>, Compare = Compare())
368
+ -> flat_multimap<Key, T, Compare>;
369
+
370
+ template<class Key, class T, class Compare = less<Key>>
371
+ flat_multimap(sorted_equivalent_t, initializer_list<pair<Key, T>>, Compare = Compare())
372
+ -> flat_multimap<Key, T, Compare>;
373
+
374
+ template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
375
+ class Allocator>
376
+ struct uses_allocator<flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>,
377
+ Allocator>
378
+ : bool_constant<uses_allocator_v<KeyContainer, Allocator> &&
379
+ uses_allocator_v<MappedContainer, Allocator>> { };
380
+ }
381
+ ```
382
+
383
+ The member type `containers` has the data members and special members
384
+ specified above. It has no base classes or members other than those
385
+ specified.
386
+
387
+ #### Constructors <a id="flat.multimap.cons">[[flat.multimap.cons]]</a>
388
+
389
+ ``` cpp
390
+ flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,
391
+ const key_compare& comp = key_compare());
392
+ ```
393
+
394
+ *Effects:* Initializes `c.keys` with `std::move(key_cont)`, `c.values`
395
+ with `std::move(mapped_cont)`, and `compare` with `comp`; sorts the
396
+ range \[`begin()`, `end()`) with respect to `value_comp()`.
397
+
398
+ *Complexity:* Linear in N if the container arguments are already sorted
399
+ with respect to `value_comp()` and otherwise N log N, where N is the
400
+ value of `key_cont.size()` before this call.
401
+
402
+ ``` cpp
403
+ template<class Allocator>
404
+ flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
405
+ const Allocator& a);
406
+ template<class Allocator>
407
+ flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
408
+ const key_compare& comp, const Allocator& a);
409
+ ```
410
+
411
+ *Constraints:* `uses_allocator_v<key_container_type, Allocator>` is
412
+ `true` and `uses_allocator_v<mapped_container_type, Allocator>` is
413
+ `true`.
414
+
415
+ *Effects:* Equivalent to `flat_multimap(key_cont, mapped_cont)` and
416
+ `flat_multimap(key_cont, mapped_cont, comp)`, respectively, except that
417
+ `c.keys` and `c.values` are constructed with uses-allocator
418
+ construction [[allocator.uses.construction]].
419
+
420
+ *Complexity:* Same as `flat_multimap(key_cont, mapped_cont)` and
421
+ `flat_multimap(key_cont, mapped_cont, comp)`, respectively.
422
+
423
+ ``` cpp
424
+ flat_multimap(sorted_equivalent_t, key_container_type key_cont, mapped_container_type mapped_cont,
425
+ const key_compare& comp = key_compare());
426
+ ```
427
+
428
+ *Effects:* Initializes `c.keys` with `std::move(key_cont)`, `c.values`
429
+ with `std::move(mapped_cont)`, and `compare` with `comp`.
430
+
431
+ *Complexity:* Constant.
432
+
433
+ ``` cpp
434
+ template<class Allocator>
435
+ flat_multimap(sorted_equivalent_t s, const key_container_type& key_cont,
436
+ const mapped_container_type& mapped_cont, const Allocator& a);
437
+ template<class Allocator>
438
+ flat_multimap(sorted_equivalent_t s, const key_container_type& key_cont,
439
+ const mapped_container_type& mapped_cont, const key_compare& comp,
440
+ const Allocator& a);
441
+ ```
442
+
443
+ *Constraints:* `uses_allocator_v<key_container_type, Allocator>` is
444
+ `true` and `uses_allocator_v<mapped_container_type, Allocator>` is
445
+ `true`.
446
+
447
+ *Effects:* Equivalent to `flat_multimap(s, key_cont, mapped_cont)` and
448
+ `flat_multimap(s, key_cont, mapped_cont, comp)`, respectively, except
449
+ that `c.keys` and `c.values` are constructed with uses-allocator
450
+ construction [[allocator.uses.construction]].
451
+
452
+ *Complexity:* Linear.
453
+
454
+ ``` cpp
455
+ template<class Allocator>
456
+ flat_multimap(const key_compare& comp, const Allocator& a);
457
+ template<class Allocator>
458
+ explicit flat_multimap(const Allocator& a);
459
+ template<class InputIterator, class Allocator>
460
+ flat_multimap(InputIterator first, InputIterator last, const key_compare& comp,
461
+ const Allocator& a);
462
+ template<class InputIterator, class Allocator>
463
+ flat_multimap(InputIterator first, InputIterator last, const Allocator& a);
464
+ template<container-compatible-range<value_type> R, class Allocator>
465
+ flat_multimap(from_range_t, R&& rg, const Allocator& a);
466
+ template<container-compatible-range<value_type> R, class Allocator>
467
+ flat_multimap(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
468
+ template<class InputIterator, class Allocator>
469
+ flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
470
+ const key_compare& comp, const Allocator& a);
471
+ template<class InputIterator, class Allocator>
472
+ flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
473
+ const Allocator& a);
474
+ template<class Allocator>
475
+ flat_multimap(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
476
+ template<class Allocator>
477
+ flat_multimap(initializer_list<value_type> il, const Allocator& a);
478
+ template<class Allocator>
479
+ flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
480
+ const key_compare& comp, const Allocator& a);
481
+ template<class Allocator>
482
+ flat_multimap(sorted_equivalent_t, initializer_list<value_type> il, const Allocator& a);
483
+ ```
484
+
485
+ *Constraints:* `uses_allocator_v<key_container_type, Allocator>` is
486
+ `true` and `uses_allocator_v<mapped_container_type, Allocator>` is
487
+ `true`.
488
+
489
+ *Effects:* Equivalent to the corresponding non-allocator constructors
490
+ except that `c.keys` and `c.values` are constructed with uses-allocator
491
+ construction [[allocator.uses.construction]].
492
+
493
+ #### Erasure <a id="flat.multimap.erasure">[[flat.multimap.erasure]]</a>
494
+
495
+ ``` cpp
496
+ template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
497
+ class Predicate>
498
+ typename flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>::size_type
499
+ erase_if(flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
500
+ ```
501
+
502
+ *Preconditions:* `Key` and `T` meet the *Cpp17MoveAssignable*
503
+ requirements.
504
+
505
+ *Effects:* Let E be `bool(pred(pair<const Key&, const T&>(e)))`. Erases
506
+ all elements `e` in `c` for which E holds.
507
+
508
+ *Returns:* The number of elements erased.
509
+
510
+ *Complexity:* Exactly `c.size()` applications of the predicate.
511
+
512
+ *Remarks:* Stable [[algorithm.stable]]. If an invocation of `erase_if`
513
+ exits via an exception, `c` is in a valid but unspecified
514
+ state [[defns.valid]].
515
+
516
+ [*Note 1*: `c` still meets its invariants, but can be
517
+ empty. — *end note*]
518
+