From Jason Turner

[flat.map]

C++20 → C++23 36.2 KB 943 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/tmpbc_i3cg4/{from.md → to.md} +940 -0
tmp/tmpbc_i3cg4/{from.md → to.md} RENAMED
@@ -0,0 +1,940 @@
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
+ ### Class template `flat_map` <a id="flat.map">[[flat.map]]</a>
2
+
3
+ #### Overview <a id="flat.map.overview">[[flat.map.overview]]</a>
4
+
5
+ A `flat_map` is a container adaptor that provides an associative
6
+ container interface that supports unique keys (i.e., contains at most
7
+ one of each key value) and provides for fast retrieval of values of
8
+ another type `T` based on the keys. `flat_map` supports iterators that
9
+ meet the *Cpp17InputIterator* requirements and model the
10
+ `random_access_iterator` concept [[iterator.concept.random.access]].
11
+
12
+ A `flat_map` meets all of the requirements of a container
13
+ [[container.reqmts]] and of a reversible container
14
+ [[container.rev.reqmts]], plus the optional container requirements
15
+ [[container.opt.reqmts]]. `flat_map` meets the requirements of an
16
+ associative container [[associative.reqmts]], except that:
17
+
18
+ - it does not meet the requirements related to node handles
19
+ [[container.node]],
20
+ - it does not meet the requirements related to iterator invalidation,
21
+ and
22
+ - the time complexity of the operations that insert or erase a single
23
+ element from the map is linear, including the ones that take an
24
+ insertion position iterator.
25
+
26
+ [*Note 1*: A `flat_map` does not meet the additional requirements of an
27
+ allocator-aware container [[container.alloc.reqmts]]. — *end note*]
28
+
29
+ A `flat_map` also provides most operations described in
30
+ [[associative.reqmts]] for unique keys. This means that a `flat_map`
31
+ supports the `a_uniq` operations in [[associative.reqmts]] but not the
32
+ `a_eq` operations. For a `flat_map<Key, T>` the `key_type` is `Key` and
33
+ the `value_type` is `pair<Key, T>`.
34
+
35
+ Descriptions are provided here only for operations on `flat_map` that
36
+ are not described in one of those sets of requirements or for operations
37
+ where there is additional semantic information.
38
+
39
+ A `flat_map` maintains the following invariants:
40
+
41
+ - it contains the same number of keys and values;
42
+ - the keys are sorted with respect to the comparison object; and
43
+ - the value at offset `off` within the value container is the value
44
+ associated with the key at offset `off` within the key container.
45
+
46
+ If any member function in [[flat.map.defn]] exits via an exception the
47
+ invariants are restored.
48
+
49
+ [*Note 2*: This can result in the `flat_map` being
50
+ emptied. — *end note*]
51
+
52
+ Any type `C` that meets the sequence container requirements
53
+ [[sequence.reqmts]] can be used to instantiate `flat_map`, as long as
54
+ `C::iterator` meets the *Cpp17RandomAccessIterator* requirements and
55
+ invocations of member functions `C::size` and `C::max_size` do not exit
56
+ via an exception. In particular, `vector` [[vector]] and `deque`
57
+ [[deque]] can be used.
58
+
59
+ [*Note 3*: `vector<bool>` is not a sequence container. — *end note*]
60
+
61
+ The program is ill-formed if `Key` is not the same type as
62
+ `KeyContainer::value_type` or `T` is not the same type as
63
+ `MappedContainer::value_type`.
64
+
65
+ The effect of calling a constructor that takes both `key_container_type`
66
+ and `mapped_container_type` arguments with containers of different sizes
67
+ is undefined.
68
+
69
+ The effect of calling a constructor or member function that takes a
70
+ `sorted_unique_t` argument with a container, containers, or range that
71
+ is not sorted with respect to `key_comp()`, or that contains equal
72
+ elements, is undefined.
73
+
74
+ #### Definition <a id="flat.map.defn">[[flat.map.defn]]</a>
75
+
76
+ ``` cpp
77
+ namespace std {
78
+ template<class Key, class T, class Compare = less<Key>,
79
+ class KeyContainer = vector<Key>, class MappedContainer = vector<T>>
80
+ class flat_map {
81
+ public:
82
+ // types
83
+ using key_type = Key;
84
+ using mapped_type = T;
85
+ using value_type = pair<key_type, mapped_type>;
86
+ using key_compare = Compare;
87
+ using reference = pair<const key_type&, mapped_type&>;
88
+ using const_reference = pair<const key_type&, const mapped_type&>;
89
+ using size_type = size_t;
90
+ using difference_type = ptrdiff_t;
91
+ using iterator = implementation-defined // type of flat_map::iterator; // see [container.requirements]
92
+ using const_iterator = implementation-defined // type of flat_map::const_iterator; // see [container.requirements]
93
+ using reverse_iterator = std::reverse_iterator<iterator>;
94
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>;
95
+ using key_container_type = KeyContainer;
96
+ using mapped_container_type = MappedContainer;
97
+
98
+ class value_compare {
99
+ private:
100
+ key_compare comp; // exposition only
101
+ value_compare(key_compare c) : comp(c) { } // exposition only
102
+
103
+ public:
104
+ bool operator()(const_reference x, const_reference y) const {
105
+ return comp(x.first, y.first);
106
+ }
107
+ };
108
+
109
+ struct containers {
110
+ key_container_type keys;
111
+ mapped_container_type values;
112
+ };
113
+
114
+ // [flat.map.cons], construct/copy/destroy
115
+ flat_map() : flat_map(key_compare()) { }
116
+
117
+ flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
118
+ const key_compare& comp = key_compare());
119
+ template<class Allocator>
120
+ flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
121
+ const Allocator& a);
122
+ template<class Allocator>
123
+ flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
124
+ const key_compare& comp, const Allocator& a);
125
+
126
+ flat_map(sorted_unique_t, key_container_type key_cont, mapped_container_type mapped_cont,
127
+ const key_compare& comp = key_compare());
128
+ template<class Allocator>
129
+ flat_map(sorted_unique_t, const key_container_type& key_cont,
130
+ const mapped_container_type& mapped_cont, const Allocator& a);
131
+ template<class Allocator>
132
+ flat_map(sorted_unique_t, const key_container_type& key_cont,
133
+ const mapped_container_type& mapped_cont,
134
+ const key_compare& comp, const Allocator& a);
135
+
136
+ explicit flat_map(const key_compare& comp)
137
+ : c(), compare(comp) { }
138
+ template<class Allocator>
139
+ flat_map(const key_compare& comp, const Allocator& a);
140
+ template<class Allocator>
141
+ explicit flat_map(const Allocator& a);
142
+
143
+ template<class InputIterator>
144
+ flat_map(InputIterator first, InputIterator last, const key_compare& comp = key_compare())
145
+ : c(), compare(comp) { insert(first, last); }
146
+ template<class InputIterator, class Allocator>
147
+ flat_map(InputIterator first, InputIterator last,
148
+ const key_compare& comp, const Allocator& a);
149
+ template<class InputIterator, class Allocator>
150
+ flat_map(InputIterator first, InputIterator last, const Allocator& a);
151
+
152
+ template<container-compatible-range<value_type> R>
153
+ flat_map(from_range_t fr, R&& rg)
154
+ : flat_map(fr, std::forward<R>(rg), key_compare()) { }
155
+ template<container-compatible-range<value_type> R, class Allocator>
156
+ flat_map(from_range_t, R&& rg, const Allocator& a);
157
+ template<container-compatible-range<value_type> R>
158
+ flat_map(from_range_t, R&& rg, const key_compare& comp)
159
+ : flat_map(comp) { insert_range(std::forward<R>(rg)); }
160
+ template<container-compatible-range<value_type> R, class Allocator>
161
+ flat_map(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
162
+
163
+ template<class InputIterator>
164
+ flat_map(sorted_unique_t s, InputIterator first, InputIterator last,
165
+ const key_compare& comp = key_compare())
166
+ : c(), compare(comp) { insert(s, first, last); }
167
+ template<class InputIterator, class Allocator>
168
+ flat_map(sorted_unique_t, InputIterator first, InputIterator last,
169
+ const key_compare& comp, const Allocator& a);
170
+ template<class InputIterator, class Allocator>
171
+ flat_map(sorted_unique_t, InputIterator first, InputIterator last, const Allocator& a);
172
+
173
+ flat_map(initializer_list<value_type> il, const key_compare& comp = key_compare())
174
+ : flat_map(il.begin(), il.end(), comp) { }
175
+ template<class Allocator>
176
+ flat_map(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
177
+ template<class Allocator>
178
+ flat_map(initializer_list<value_type> il, const Allocator& a);
179
+
180
+ flat_map(sorted_unique_t s, initializer_list<value_type> il,
181
+ const key_compare& comp = key_compare())
182
+ : flat_map(s, il.begin(), il.end(), comp) { }
183
+ template<class Allocator>
184
+ flat_map(sorted_unique_t, initializer_list<value_type> il,
185
+ const key_compare& comp, const Allocator& a);
186
+ template<class Allocator>
187
+ flat_map(sorted_unique_t, initializer_list<value_type> il, const Allocator& a);
188
+
189
+ flat_map& operator=(initializer_list<value_type> il);
190
+
191
+ // iterators
192
+ iterator begin() noexcept;
193
+ const_iterator begin() const noexcept;
194
+ iterator end() noexcept;
195
+ const_iterator end() const noexcept;
196
+
197
+ reverse_iterator rbegin() noexcept;
198
+ const_reverse_iterator rbegin() const noexcept;
199
+ reverse_iterator rend() noexcept;
200
+ const_reverse_iterator rend() const noexcept;
201
+
202
+ const_iterator cbegin() const noexcept;
203
+ const_iterator cend() const noexcept;
204
+ const_reverse_iterator crbegin() const noexcept;
205
+ const_reverse_iterator crend() const noexcept;
206
+
207
+ // [flat.map.capacity], capacity
208
+ [[nodiscard]] bool empty() const noexcept;
209
+ size_type size() const noexcept;
210
+ size_type max_size() const noexcept;
211
+
212
+ // [flat.map.access], element access
213
+ mapped_type& operator[](const key_type& x);
214
+ mapped_type& operator[](key_type&& x);
215
+ template<class K> mapped_type& operator[](K&& x);
216
+ mapped_type& at(const key_type& x);
217
+ const mapped_type& at(const key_type& x) const;
218
+ template<class K> mapped_type& at(const K& x);
219
+ template<class K> const mapped_type& at(const K& x) const;
220
+
221
+ // [flat.map.modifiers], modifiers
222
+ template<class... Args> pair<iterator, bool> emplace(Args&&... args);
223
+ template<class... Args>
224
+ iterator emplace_hint(const_iterator position, Args&&... args);
225
+
226
+ pair<iterator, bool> insert(const value_type& x)
227
+ { return emplace(x); }
228
+ pair<iterator, bool> 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> pair<iterator, bool> 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_unique_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_unique_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
+ template<class... Args>
254
+ pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
255
+ template<class... Args>
256
+ pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
257
+ template<class K, class... Args>
258
+ pair<iterator, bool> try_emplace(K&& k, Args&&... args);
259
+ template<class... Args>
260
+ iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
261
+ template<class... Args>
262
+ iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
263
+ template<class K, class... Args>
264
+ iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
265
+ template<class M>
266
+ pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
267
+ template<class M>
268
+ pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
269
+ template<class K, class M>
270
+ pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
271
+ template<class M>
272
+ iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
273
+ template<class M>
274
+ iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
275
+ template<class K, class M>
276
+ iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
277
+
278
+ iterator erase(iterator position);
279
+ iterator erase(const_iterator position);
280
+ size_type erase(const key_type& x);
281
+ template<class K> size_type erase(K&& x);
282
+ iterator erase(const_iterator first, const_iterator last);
283
+
284
+ void swap(flat_map& y) noexcept;
285
+ void clear() noexcept;
286
+
287
+ // observers
288
+ key_compare key_comp() const;
289
+ value_compare value_comp() const;
290
+
291
+ const key_container_type& keys() const noexcept { return c.keys; }
292
+ const mapped_container_type& values() const noexcept { return c.values; }
293
+
294
+ // map operations
295
+ iterator find(const key_type& x);
296
+ const_iterator find(const key_type& x) const;
297
+ template<class K> iterator find(const K& x);
298
+ template<class K> const_iterator find(const K& x) const;
299
+
300
+ size_type count(const key_type& x) const;
301
+ template<class K> size_type count(const K& x) const;
302
+
303
+ bool contains(const key_type& x) const;
304
+ template<class K> bool contains(const K& x) const;
305
+
306
+ iterator lower_bound(const key_type& x);
307
+ const_iterator lower_bound(const key_type& x) const;
308
+ template<class K> iterator lower_bound(const K& x);
309
+ template<class K> const_iterator lower_bound(const K& x) const;
310
+
311
+ iterator upper_bound(const key_type& x);
312
+ const_iterator upper_bound(const key_type& x) const;
313
+ template<class K> iterator upper_bound(const K& x);
314
+ template<class K> const_iterator upper_bound(const K& x) const;
315
+
316
+ pair<iterator, iterator> equal_range(const key_type& x);
317
+ pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
318
+ template<class K> pair<iterator, iterator> equal_range(const K& x);
319
+ template<class K> pair<const_iterator, const_iterator> equal_range(const K& x) const;
320
+
321
+ friend bool operator==(const flat_map& x, const flat_map& y);
322
+
323
+ friend synth-three-way-result<value_type>
324
+ operator<=>(const flat_map& x, const flat_map& y);
325
+
326
+ friend void swap(flat_map& x, flat_map& y) noexcept
327
+ { x.swap(y); }
328
+
329
+ private:
330
+ containers c; // exposition only
331
+ key_compare compare; // exposition only
332
+
333
+ struct key_equiv { // exposition only
334
+ key_equiv(key_compare c) : comp(c) { }
335
+ bool operator()(const_reference x, const_reference y) const {
336
+ return !comp(x.first, y.first) && !comp(y.first, x.first);
337
+ }
338
+ key_compare comp;
339
+ };
340
+ };
341
+
342
+ template<class KeyContainer, class MappedContainer,
343
+ class Compare = less<typename KeyContainer::value_type>>
344
+ flat_map(KeyContainer, MappedContainer, Compare = Compare())
345
+ -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
346
+ Compare, KeyContainer, MappedContainer>;
347
+
348
+ template<class KeyContainer, class MappedContainer, class Allocator>
349
+ flat_map(KeyContainer, MappedContainer, Allocator)
350
+ -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
351
+ less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
352
+ template<class KeyContainer, class MappedContainer, class Compare, class Allocator>
353
+ flat_map(KeyContainer, MappedContainer, Compare, Allocator)
354
+ -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
355
+ Compare, KeyContainer, MappedContainer>;
356
+
357
+ template<class KeyContainer, class MappedContainer,
358
+ class Compare = less<typename KeyContainer::value_type>>
359
+ flat_map(sorted_unique_t, KeyContainer, MappedContainer, Compare = Compare())
360
+ -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
361
+ Compare, KeyContainer, MappedContainer>;
362
+
363
+ template<class KeyContainer, class MappedContainer, class Allocator>
364
+ flat_map(sorted_unique_t, KeyContainer, MappedContainer, Allocator)
365
+ -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
366
+ less<typename KeyContainer::value_type>, KeyContainer, MappedContainer>;
367
+ template<class KeyContainer, class MappedContainer, class Compare, class Allocator>
368
+ flat_map(sorted_unique_t, KeyContainer, MappedContainer, Compare, Allocator)
369
+ -> flat_map<typename KeyContainer::value_type, typename MappedContainer::value_type,
370
+ Compare, KeyContainer, MappedContainer>;
371
+
372
+ template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>>
373
+ flat_map(InputIterator, InputIterator, Compare = Compare())
374
+ -> flat_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Compare>;
375
+
376
+ template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>>
377
+ flat_map(sorted_unique_t, InputIterator, InputIterator, Compare = Compare())
378
+ -> flat_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Compare>;
379
+
380
+ template<ranges::input_range R, class Compare = less<range-key-type<R>>,
381
+ class Allocator = allocator<byte>>
382
+ flat_map(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
383
+ -> flat_map<range-key-type<R>, range-mapped-type<R>, Compare,
384
+ vector<range-key-type<R>, alloc-rebind<Allocator, range-key-type<R>>>,
385
+ vector<range-mapped-type<R>, alloc-rebind<Allocator, range-mapped-type<R>>>>;
386
+
387
+ template<ranges::input_range R, class Allocator>
388
+ flat_map(from_range_t, R&&, Allocator)
389
+ -> flat_map<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>,
390
+ vector<range-key-type<R>, alloc-rebind<Allocator, range-key-type<R>>>,
391
+ vector<range-mapped-type<R>, alloc-rebind<Allocator, range-mapped-type<R>>>>;
392
+
393
+ template<class Key, class T, class Compare = less<Key>>
394
+ flat_map(initializer_list<pair<Key, T>>, Compare = Compare())
395
+ -> flat_map<Key, T, Compare>;
396
+
397
+ template<class Key, class T, class Compare = less<Key>>
398
+ flat_map(sorted_unique_t, initializer_list<pair<Key, T>>, Compare = Compare())
399
+ -> flat_map<Key, T, Compare>;
400
+
401
+ template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
402
+ class Allocator>
403
+ struct uses_allocator<flat_map<Key, T, Compare, KeyContainer, MappedContainer>, Allocator>
404
+ : bool_constant<uses_allocator_v<KeyContainer, Allocator> &&
405
+ uses_allocator_v<MappedContainer, Allocator>> { };
406
+ }
407
+ ```
408
+
409
+ The member type `containers` has the data members and special members
410
+ specified above. It has no base classes or members other than those
411
+ specified.
412
+
413
+ #### Constructors <a id="flat.map.cons">[[flat.map.cons]]</a>
414
+
415
+ ``` cpp
416
+ flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
417
+ const key_compare& comp = key_compare());
418
+ ```
419
+
420
+ *Effects:* Initializes `c.keys` with `std::move(key_cont)`, `c.values`
421
+ with `std::move(mapped_cont)`, and `compare` with `comp`; sorts the
422
+ range \[`begin()`, `end()`) with respect to `value_comp()`; and finally
423
+ erases the duplicate elements as if by:
424
+
425
+ ``` cpp
426
+ auto zv = ranges::zip_view(c.keys, c.values);
427
+ auto it = ranges::unique(zv, key_equiv(compare)).begin();
428
+ auto dist = distance(zv.begin(), it);
429
+ c.keys.erase(c.keys.begin() + dist, c.keys.end());
430
+ c.values.erase(c.values.begin() + dist, c.values.end());
431
+ ```
432
+
433
+ *Complexity:* Linear in N if the container arguments are already sorted
434
+ with respect to `value_comp()` and otherwise N log N, where N is the
435
+ value of `key_cont.size()` before this call.
436
+
437
+ ``` cpp
438
+ template<class Allocator>
439
+ flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
440
+ const Allocator& a);
441
+ template<class Allocator>
442
+ flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
443
+ const key_compare& comp, const Allocator& a);
444
+ ```
445
+
446
+ *Constraints:* `uses_allocator_v<key_container_type, Allocator>` is
447
+ `true` and `uses_allocator_v<mapped_container_type, Allocator>` is
448
+ `true`.
449
+
450
+ *Effects:* Equivalent to `flat_map(key_cont, mapped_cont)` and
451
+ `flat_map(key_cont, mapped_cont, comp)`, respectively, except that
452
+ `c.keys` and `c.values` are constructed with uses-allocator
453
+ construction [[allocator.uses.construction]].
454
+
455
+ *Complexity:* Same as `flat_map(key_cont, mapped_cont)` and
456
+ `flat_map(key_cont, mapped_cont, comp)`, respectively.
457
+
458
+ ``` cpp
459
+ flat_map(sorted_unique_t, key_container_type key_cont, mapped_container_type mapped_cont,
460
+ const key_compare& comp = key_compare());
461
+ ```
462
+
463
+ *Effects:* Initializes `c.keys` with `std::move(key_cont)`, `c.values`
464
+ with `std::move(mapped_cont)`, and `compare` with `comp`.
465
+
466
+ *Complexity:* Constant.
467
+
468
+ ``` cpp
469
+ template<class Allocator>
470
+ flat_map(sorted_unique_t s, const key_container_type& key_cont,
471
+ const mapped_container_type& mapped_cont, const Allocator& a);
472
+ template<class Allocator>
473
+ flat_map(sorted_unique_t s, const key_container_type& key_cont,
474
+ const mapped_container_type& mapped_cont, const key_compare& comp,
475
+ const Allocator& a);
476
+ ```
477
+
478
+ *Constraints:* `uses_allocator_v<key_container_type, Allocator>` is
479
+ `true` and `uses_allocator_v<mapped_container_type, Allocator>` is
480
+ `true`.
481
+
482
+ *Effects:* Equivalent to `flat_map(s, key_cont, mapped_cont)` and
483
+ `flat_map(s, key_cont, mapped_cont, comp)`, respectively, except that
484
+ `c.keys` and `c.values` are constructed with uses-allocator
485
+ construction [[allocator.uses.construction]].
486
+
487
+ *Complexity:* Linear.
488
+
489
+ ``` cpp
490
+ template<class Allocator>
491
+ flat_map(const key_compare& comp, const Allocator& a);
492
+ template<class Allocator>
493
+ explicit flat_map(const Allocator& a);
494
+ template<class InputIterator, class Allocator>
495
+ flat_map(InputIterator first, InputIterator last, const key_compare& comp, const Allocator& a);
496
+ template<class InputIterator, class Allocator>
497
+ flat_map(InputIterator first, InputIterator last, const Allocator& a);
498
+ template<container-compatible-range<value_type> R, class Allocator>
499
+ flat_map(from_range_t, R&& rg, const Allocator& a);
500
+ template<container-compatible-range<value_type> R, class Allocator>
501
+ flat_map(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
502
+ template<class InputIterator, class Allocator>
503
+ flat_map(sorted_unique_t, InputIterator first, InputIterator last,
504
+ const key_compare& comp, const Allocator& a);
505
+ template<class InputIterator, class Allocator>
506
+ flat_map(sorted_unique_t, InputIterator first, InputIterator last, const Allocator& a);
507
+ template<class Allocator>
508
+ flat_map(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
509
+ template<class Allocator>
510
+ flat_map(initializer_list<value_type> il, const Allocator& a);
511
+ template<class Allocator>
512
+ flat_map(sorted_unique_t, initializer_list<value_type> il,
513
+ const key_compare& comp, const Allocator& a);
514
+ template<class Allocator>
515
+ flat_map(sorted_unique_t, initializer_list<value_type> il, const Allocator& a);
516
+ ```
517
+
518
+ *Constraints:* `uses_allocator_v<key_container_type, Allocator>` is
519
+ `true` and `uses_allocator_v<mapped_container_type, Allocator>` is
520
+ `true`.
521
+
522
+ *Effects:* Equivalent to the corresponding non-allocator constructors
523
+ except that `c.keys` and `c.values` are constructed with uses-allocator
524
+ construction [[allocator.uses.construction]].
525
+
526
+ #### Capacity <a id="flat.map.capacity">[[flat.map.capacity]]</a>
527
+
528
+ ``` cpp
529
+ size_type size() const noexcept;
530
+ ```
531
+
532
+ *Returns:* `c.keys.size()`.
533
+
534
+ ``` cpp
535
+ size_type max_size() const noexcept;
536
+ ```
537
+
538
+ *Returns:* `min<size_type>(c.keys.max_size(), c.values.max_size())`.
539
+
540
+ #### Access <a id="flat.map.access">[[flat.map.access]]</a>
541
+
542
+ ``` cpp
543
+ mapped_type& operator[](const key_type& x);
544
+ ```
545
+
546
+ *Effects:* Equivalent to: `return try_emplace(x).first->second;`
547
+
548
+ ``` cpp
549
+ mapped_type& operator[](key_type&& x);
550
+ ```
551
+
552
+ *Effects:* Equivalent to:
553
+ `return try_emplace(std::move(x)).first->second;`
554
+
555
+ ``` cpp
556
+ template<class K> mapped_type& operator[](K&& x);
557
+ ```
558
+
559
+ *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
560
+ denotes a type.
561
+
562
+ *Effects:* Equivalent to:
563
+ `return try_emplace(std::forward<K>(x)).first->second;`
564
+
565
+ ``` cpp
566
+ mapped_type& at(const key_type& x);
567
+ const mapped_type& at(const key_type& x) const;
568
+ ```
569
+
570
+ *Returns:* A reference to the `mapped_type` corresponding to `x` in
571
+ `*this`.
572
+
573
+ *Throws:* An exception object of type `out_of_range` if no such element
574
+ is present.
575
+
576
+ *Complexity:* Logarithmic.
577
+
578
+ ``` cpp
579
+ template<class K> mapped_type& at(const K& x);
580
+ template<class K> const mapped_type& at(const K& x) const;
581
+ ```
582
+
583
+ *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
584
+ denotes a type.
585
+
586
+ *Preconditions:* The expression `find(x)` is well-formed and has
587
+ well-defined behavior.
588
+
589
+ *Returns:* A reference to the `mapped_type` corresponding to `x` in
590
+ `*this`.
591
+
592
+ *Throws:* An exception object of type `out_of_range` if no such element
593
+ is present.
594
+
595
+ *Complexity:* Logarithmic.
596
+
597
+ #### Modifiers <a id="flat.map.modifiers">[[flat.map.modifiers]]</a>
598
+
599
+ ``` cpp
600
+ template<class... Args> pair<iterator, bool> emplace(Args&&... args);
601
+ ```
602
+
603
+ *Constraints:*
604
+ `is_constructible_v<pair<key_type, mapped_type>, Args...>` is `true`.
605
+
606
+ *Effects:* Initializes an object `t` of type
607
+ `pair<key_type, mapped_type>` with `std::forward<Args>(args)...`; if the
608
+ map already contains an element whose key is equivalent to `t.first`,
609
+ `*this` is unchanged. Otherwise, equivalent to:
610
+
611
+ ``` cpp
612
+ auto key_it = ranges::upper_bound(c.keys, t.first, compare);
613
+ auto value_it = c.values.begin() + distance(c.keys.begin(), key_it);
614
+ c.keys.insert(key_it, std::move(t.first));
615
+ c.values.insert(value_it, std::move(t.second));
616
+ ```
617
+
618
+ *Returns:* The `bool` component of the returned pair is `true` if and
619
+ only if the insertion took place, and the iterator component of the pair
620
+ points to the element with key equivalent to `t.first`.
621
+
622
+ ``` cpp
623
+ template<class P> pair<iterator, bool> insert(P&& x);
624
+ template<class P> iterator insert(const_iterator position, P&& x);
625
+ ```
626
+
627
+ *Constraints:* `is_constructible_v<pair<key_type, mapped_type>, P>` is
628
+ `true`.
629
+
630
+ *Effects:* The first form is equivalent to
631
+ `return emplace(std::forward<P>(x));`. The second form is equivalent to
632
+ `return emplace_hint(position, std::forward<P>(x));`.
633
+
634
+ ``` cpp
635
+ template<class InputIterator>
636
+ void insert(InputIterator first, InputIterator last);
637
+ ```
638
+
639
+ *Effects:* Adds elements to `c` as if by:
640
+
641
+ ``` cpp
642
+ for (; first != last; ++first) {
643
+ value_type value = *first;
644
+ c.keys.insert(c.keys.end(), std::move(value.first));
645
+ c.values.insert(c.values.end(), std::move(value.second));
646
+ }
647
+ ```
648
+
649
+ Then, sorts the range of newly inserted elements with respect to
650
+ `value_comp()`; merges the resulting sorted range and the sorted range
651
+ of pre-existing elements into a single sorted range; and finally erases
652
+ the duplicate elements as if by:
653
+
654
+ ``` cpp
655
+ auto zv = ranges::zip_view(c.keys, c.values);
656
+ auto it = ranges::unique(zv, key_equiv(compare)).begin();
657
+ auto dist = distance(zv.begin(), it);
658
+ c.keys.erase(c.keys.begin() + dist, c.keys.end());
659
+ c.values.erase(c.values.begin() + dist, c.values.end());
660
+ ```
661
+
662
+ *Complexity:* N + M log M, where N is `size()` before the operation and
663
+ M is `distance(first, last)`.
664
+
665
+ *Remarks:* Since this operation performs an in-place merge, it may
666
+ allocate memory.
667
+
668
+ ``` cpp
669
+ template<class InputIterator>
670
+ void insert(sorted_unique_t, InputIterator first, InputIterator last);
671
+ ```
672
+
673
+ *Effects:* Adds elements to `c` as if by:
674
+
675
+ ``` cpp
676
+ for (; first != last; ++first) {
677
+ value_type value = *first;
678
+ c.keys.insert(c.keys.end(), std::move(value.first));
679
+ c.values.insert(c.values.end(), std::move(value.second));
680
+ }
681
+ ```
682
+
683
+ Then, merges the sorted range of newly added elements and the sorted
684
+ range of pre-existing elements into a single sorted range; and finally
685
+ erases the duplicate elements as if by:
686
+
687
+ ``` cpp
688
+ auto zv = ranges::zip_view(c.keys, c.values);
689
+ auto it = ranges::unique(zv, key_equiv(compare)).begin();
690
+ auto dist = distance(zv.begin(), it);
691
+ c.keys.erase(c.keys.begin() + dist, c.keys.end());
692
+ c.values.erase(c.values.begin() + dist, c.values.end());
693
+ ```
694
+
695
+ *Complexity:* Linear in N, where N is `size()` after the operation.
696
+
697
+ *Remarks:* Since this operation performs an in-place merge, it may
698
+ allocate memory.
699
+
700
+ ``` cpp
701
+ template<container-compatible-range<value_type> R>
702
+ void insert_range(R&& rg);
703
+ ```
704
+
705
+ *Effects:* Adds elements to `c` as if by:
706
+
707
+ ``` cpp
708
+ for (const auto& e : rg) {
709
+ c.keys.insert(c.keys.end(), e.first);
710
+ c.values.insert(c.values.end(), e.second);
711
+ }
712
+ ```
713
+
714
+ Then, sorts the range of newly inserted elements with respect to
715
+ `value_comp()`; merges the resulting sorted range and the sorted range
716
+ of pre-existing elements into a single sorted range; and finally erases
717
+ the duplicate elements as if by:
718
+
719
+ ``` cpp
720
+ auto zv = ranges::zip_view(c.keys, c.values);
721
+ auto it = ranges::unique(zv, key_equiv(compare)).begin();
722
+ auto dist = distance(zv.begin(), it);
723
+ c.keys.erase(c.keys.begin() + dist, c.keys.end());
724
+ c.values.erase(c.values.begin() + dist, c.values.end());
725
+ ```
726
+
727
+ *Complexity:* N + M log M, where N is `size()` before the operation and
728
+ M is `ranges::distance(rg)`.
729
+
730
+ *Remarks:* Since this operation performs an in-place merge, it may
731
+ allocate memory.
732
+
733
+ ``` cpp
734
+ template<class... Args>
735
+ pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
736
+ template<class... Args>
737
+ pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
738
+ template<class... Args>
739
+ iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
740
+ template<class... Args>
741
+ iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
742
+ ```
743
+
744
+ *Constraints:* `is_constructible_v<mapped_type, Args...>` is `true`.
745
+
746
+ *Effects:* If the map already contains an element whose key is
747
+ equivalent to `k`, `*this` and `args...` are unchanged. Otherwise
748
+ equivalent to:
749
+
750
+ ``` cpp
751
+ auto key_it = ranges::upper_bound(c.keys, k, compare);
752
+ auto value_it = c.values.begin() + distance(c.keys.begin(), key_it);
753
+ c.keys.insert(key_it, std::forward<decltype(k)>(k));
754
+ c.values.emplace(value_it, std::forward<Args>(args)...);
755
+ ```
756
+
757
+ *Returns:* In the first two overloads, the `bool` component of the
758
+ returned pair is `true` if and only if the insertion took place. The
759
+ returned iterator points to the map element whose key is equivalent to
760
+ `k`.
761
+
762
+ *Complexity:* The same as `emplace` for the first two overloads, and the
763
+ same as `emplace_hint` for the last two overloads.
764
+
765
+ ``` cpp
766
+ template<class K, class... Args>
767
+ pair<iterator, bool> try_emplace(K&& k, Args&&... args);
768
+ template<class K, class... Args>
769
+ iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
770
+ ```
771
+
772
+ *Constraints:*
773
+
774
+ - The *qualified-id* `Compare::is_transparent` is valid and denotes a
775
+ type.
776
+ - `is_constructible_v<key_type, K>` is `true`.
777
+ - `is_constructible_v<mapped_type, Args...>` is `true`.
778
+ - For the first overload, `is_convertible_v<K&&, const_iterator>` and
779
+ `is_convertible_v<K&&, iterator>` are both `false`.
780
+
781
+ *Preconditions:* The conversion from `k` into `key_type` constructs an
782
+ object `u`, for which `find(k) == find(u)` is `true`.
783
+
784
+ *Effects:* If the map already contains an element whose key is
785
+ equivalent to `k`, `*this` and `args...` are unchanged. Otherwise
786
+ equivalent to:
787
+
788
+ ``` cpp
789
+ auto key_it = ranges::upper_bound(c.keys, k, compare);
790
+ auto value_it = c.values.begin() + distance(c.keys.begin(), key_it);
791
+ c.keys.emplace(key_it, std::forward<K>(k));
792
+ c.values.emplace(value_it, std::forward<Args>(args)...);
793
+ ```
794
+
795
+ *Returns:* In the first overload, the `bool` component of the returned
796
+ pair is `true` if and only if the insertion took place. The returned
797
+ iterator points to the map element whose key is equivalent to `k`.
798
+
799
+ *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
800
+
801
+ ``` cpp
802
+ template<class M>
803
+ pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
804
+ template<class M>
805
+ pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
806
+ template<class M>
807
+ iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
808
+ template<class M>
809
+ iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
810
+ ```
811
+
812
+ *Constraints:* `is_assignable_v<mapped_type&, M>` is `true` and
813
+ `is_constructible_v<mapped_type, M>` is `true`.
814
+
815
+ *Effects:* If the map already contains an element `e` whose key is
816
+ equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
817
+ Otherwise, equivalent to
818
+
819
+ ``` cpp
820
+ try_emplace(std::forward<decltype(k)>(k), std::forward<M>(obj))
821
+ ```
822
+
823
+ for the first two overloads or
824
+
825
+ ``` cpp
826
+ try_emplace(hint, std::forward<decltype(k)>(k), std::forward<M>(obj))
827
+ ```
828
+
829
+ for the last two overloads.
830
+
831
+ *Returns:* In the first two overloads, the `bool` component of the
832
+ returned pair is `true` if and only if the insertion took place. The
833
+ returned iterator points to the map element whose key is equivalent to
834
+ `k`.
835
+
836
+ *Complexity:* The same as `emplace` for the first two overloads and the
837
+ same as `emplace_hint` for the last two overloads.
838
+
839
+ ``` cpp
840
+ template<class K, class M>
841
+ pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
842
+ template<class K, class M>
843
+ iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
844
+ ```
845
+
846
+ *Constraints:*
847
+
848
+ - The *qualified-id* `Compare::is_transparent` is valid and denotes a
849
+ type.
850
+ - `is_constructible_v<key_type, K>` is `true`.
851
+ - `is_assignable_v<mapped_type&, M>` is `true`.
852
+ - `is_constructible_v<mapped_type, M>` is `true`.
853
+
854
+ *Preconditions:* The conversion from `k` into `key_type` constructs an
855
+ object `u`, for which `find(k) == find(u)` is `true`.
856
+
857
+ *Effects:* If the map already contains an element `e` whose key is
858
+ equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
859
+ Otherwise, equivalent to
860
+
861
+ ``` cpp
862
+ try_emplace(std::forward<K>(k), std::forward<M>(obj))
863
+ ```
864
+
865
+ for the first overload or
866
+
867
+ ``` cpp
868
+ try_emplace(hint, std::forward<K>(k), std::forward<M>(obj))
869
+ ```
870
+
871
+ for the second overload.
872
+
873
+ *Returns:* In the first overload, the `bool` component of the returned
874
+ pair is `true` if and only if the insertion took place. The returned
875
+ iterator points to the map element whose key is equivalent to `k`.
876
+
877
+ *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
878
+
879
+ ``` cpp
880
+ void swap(flat_map& y) noexcept;
881
+ ```
882
+
883
+ *Effects:* Equivalent to:
884
+
885
+ ``` cpp
886
+ ranges::swap(compare, y.compare);
887
+ ranges::swap(c.keys, y.c.keys);
888
+ ranges::swap(c.values, y.c.values);
889
+ ```
890
+
891
+ ``` cpp
892
+ containers extract() &&;
893
+ ```
894
+
895
+ *Ensures:* `*this` is emptied, even if the function exits via an
896
+ exception.
897
+
898
+ *Returns:* `std::move(c)`.
899
+
900
+ ``` cpp
901
+ void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);
902
+ ```
903
+
904
+ *Preconditions:* `key_cont.size() == mapped_cont.size()` is `true`, the
905
+ elements of `key_cont` are sorted with respect to `compare`, and
906
+ `key_cont` contains no equal elements.
907
+
908
+ *Effects:* Equivalent to:
909
+
910
+ ``` cpp
911
+ c.keys = std::move(key_cont);
912
+ c.values = std::move(mapped_cont);
913
+ ```
914
+
915
+ #### Erasure <a id="flat.map.erasure">[[flat.map.erasure]]</a>
916
+
917
+ ``` cpp
918
+ template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
919
+ class Predicate>
920
+ typename flat_map<Key, T, Compare, KeyContainer, MappedContainer>::size_type
921
+ erase_if(flat_map<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
922
+ ```
923
+
924
+ *Preconditions:* `Key` and `T` meet the *Cpp17MoveAssignable*
925
+ requirements.
926
+
927
+ *Effects:* Let E be `bool(pred(pair<const Key&, const T&>(e)))`. Erases
928
+ all elements `e` in `c` for which E holds.
929
+
930
+ *Returns:* The number of elements erased.
931
+
932
+ *Complexity:* Exactly `c.size()` applications of the predicate.
933
+
934
+ *Remarks:* Stable [[algorithm.stable]]. If an invocation of `erase_if`
935
+ exits via an exception, `c` is in a valid but unspecified
936
+ state [[defns.valid]].
937
+
938
+ [*Note 1*: `c` still meets its invariants, but can be
939
+ empty. — *end note*]
940
+