From Jason Turner

[flat.map]

C++23 → Trunk 42.0 KB 602 lines
Current Draft | LaTeX Source
Archived: C++23
Markdown: C++23 | Trunk
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmp0xji60rq/{from.md → to.md} +288 -294
tmp/tmp0xji60rq/{from.md → to.md} RENAMED
@@ -64,14 +64,16 @@ The program is ill-formed if `Key` is not the same type as
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 {
@@ -96,245 +98,259 @@ namespace std {
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
  };
@@ -411,162 +427,163 @@ 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
 
@@ -574,12 +591,12 @@ const mapped_type& at(const key_type& x) const;
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
 
@@ -595,11 +612,11 @@ is present.
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
 
@@ -618,12 +635,12 @@ c.values.insert(value_it, std::move(t.second));
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
 
@@ -631,14 +648,14 @@ template<class P> iterator insert(const_iterator position, P&& x);
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));
@@ -650,12 +667,12 @@ 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
 
@@ -665,46 +682,23 @@ M is `distance(first, last)`.
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);
@@ -715,12 +709,12 @@ 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
 
@@ -730,17 +724,17 @@ M is `ranges::distance(rg)`.
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
@@ -762,13 +756,13 @@ returned iterator points to the map element whose key is equivalent to
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
@@ -784,11 +778,11 @@ object `u`, for which `find(k) == find(u)` is `true`.
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
 
@@ -798,17 +792,17 @@ 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
 
@@ -836,13 +830,13 @@ returned iterator points to the map element whose key is equivalent to
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
@@ -875,11 +869,11 @@ 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
@@ -887,24 +881,24 @@ 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
@@ -915,11 +909,11 @@ c.values = std::move(mapped_cont);
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.
 
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 member function that takes a `sorted_unique_t`
70
+ argument with a container, containers, or range that is not sorted with
71
+ respect to `key_comp()`, or that contains equal elements, is undefined.
72
+
73
+ The types `iterator` and `const_iterator` meet the constexpr iterator
74
+ requirements [[iterator.requirements.general]].
75
 
76
  #### Definition <a id="flat.map.defn">[[flat.map.defn]]</a>
77
 
78
  ``` cpp
79
  namespace std {
 
98
  using mapped_container_type = MappedContainer;
99
 
100
  class value_compare {
101
  private:
102
  key_compare comp; // exposition only
103
+ constexpr value_compare(key_compare c) : comp(c) { } // exposition only
104
 
105
  public:
106
+ constexpr bool operator()(const_reference x, const_reference y) const {
107
  return comp(x.first, y.first);
108
  }
109
  };
110
 
111
  struct containers {
112
  key_container_type keys;
113
  mapped_container_type values;
114
  };
115
 
116
+ // [flat.map.cons], constructors
117
+ constexpr flat_map() : flat_map(key_compare()) { }
118
 
119
+ constexpr explicit flat_map(const key_compare& comp)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
120
  : c(), compare(comp) { }
121
+
122
+ constexpr flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
123
+ const key_compare& comp = key_compare());
124
+
125
+ constexpr flat_map(sorted_unique_t, key_container_type key_cont,
126
+ mapped_container_type mapped_cont,
127
+ const key_compare& comp = key_compare());
128
 
129
  template<class InputIterator>
130
+ constexpr flat_map(InputIterator first, InputIterator last,
131
+ const key_compare& comp = key_compare())
132
  : c(), compare(comp) { insert(first, last); }
133
+
134
+ template<class InputIterator>
135
+ constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last,
136
+ const key_compare& comp = key_compare())
137
+ : c(), compare(comp) { insert(sorted_unique, first, last); }
138
 
139
  template<container-compatible-range<value_type> R>
140
+ constexpr flat_map(from_range_t, R&& rg)
141
+ : flat_map(from_range, std::forward<R>(rg), key_compare()) { }
 
 
142
  template<container-compatible-range<value_type> R>
143
+ constexpr flat_map(from_range_t, R&& rg, const key_compare& comp)
144
  : flat_map(comp) { insert_range(std::forward<R>(rg)); }
 
 
145
 
146
+ constexpr flat_map(initializer_list<value_type> il, const key_compare& comp = key_compare())
 
 
 
 
 
 
 
 
 
 
147
  : flat_map(il.begin(), il.end(), comp) { }
 
 
 
 
148
 
149
+ constexpr flat_map(sorted_unique_t, initializer_list<value_type> il,
150
  const key_compare& comp = key_compare())
151
+ : flat_map(sorted_unique, il.begin(), il.end(), comp) { }
 
 
 
 
 
152
 
153
+ // [flat.map.cons.alloc], constructors with allocators
154
+
155
+ template<class Alloc>
156
+ constexpr explicit flat_map(const Alloc& a);
157
+ template<class Alloc>
158
+ constexpr flat_map(const key_compare& comp, const Alloc& a);
159
+ template<class Alloc>
160
+ constexpr flat_map(const key_container_type& key_cont,
161
+ const mapped_container_type& mapped_cont,
162
+ const Alloc& a);
163
+ template<class Alloc>
164
+ constexpr flat_map(const key_container_type& key_cont,
165
+ const mapped_container_type& mapped_cont,
166
+ const key_compare& comp, const Alloc& a);
167
+ template<class Alloc>
168
+ constexpr flat_map(sorted_unique_t, const key_container_type& key_cont,
169
+ const mapped_container_type& mapped_cont, const Alloc& a);
170
+ template<class Alloc>
171
+ constexpr flat_map(sorted_unique_t, const key_container_type& key_cont,
172
+ const mapped_container_type& mapped_cont, const key_compare& comp,
173
+ const Alloc& a);
174
+ template<class Alloc>
175
+ constexpr flat_map(const flat_map&, const Alloc& a);
176
+ template<class Alloc>
177
+ constexpr flat_map(flat_map&&, const Alloc& a);
178
+ template<class InputIterator, class Alloc>
179
+ constexpr flat_map(InputIterator first, InputIterator last, const Alloc& a);
180
+ template<class InputIterator, class Alloc>
181
+ constexpr flat_map(InputIterator first, InputIterator last,
182
+ const key_compare& comp, const Alloc& a);
183
+ template<class InputIterator, class Alloc>
184
+ constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last,
185
+ const Alloc& a);
186
+ template<class InputIterator, class Alloc>
187
+ constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last,
188
+ const key_compare& comp, const Alloc& a);
189
+ template<container-compatible-range<value_type> R, class Alloc>
190
+ constexpr flat_map(from_range_t, R&& rg, const Alloc& a);
191
+ template<container-compatible-range<value_type> R, class Alloc>
192
+ constexpr flat_map(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
193
+ template<class Alloc>
194
+ constexpr flat_map(initializer_list<value_type> il, const Alloc& a);
195
+ template<class Alloc>
196
+ constexpr flat_map(initializer_list<value_type> il, const key_compare& comp,
197
+ const Alloc& a);
198
+ template<class Alloc>
199
+ constexpr flat_map(sorted_unique_t, initializer_list<value_type> il, const Alloc& a);
200
+ template<class Alloc>
201
+ constexpr flat_map(sorted_unique_t, initializer_list<value_type> il,
202
+ const key_compare& comp, const Alloc& a);
203
+
204
+ constexpr flat_map& operator=(initializer_list<value_type>);
205
 
206
  // iterators
207
+ constexpr iterator begin() noexcept;
208
+ constexpr const_iterator begin() const noexcept;
209
+ constexpr iterator end() noexcept;
210
+ constexpr const_iterator end() const noexcept;
211
 
212
+ constexpr reverse_iterator rbegin() noexcept;
213
+ constexpr const_reverse_iterator rbegin() const noexcept;
214
+ constexpr reverse_iterator rend() noexcept;
215
+ constexpr const_reverse_iterator rend() const noexcept;
216
 
217
+ constexpr const_iterator cbegin() const noexcept;
218
+ constexpr const_iterator cend() const noexcept;
219
+ constexpr const_reverse_iterator crbegin() const noexcept;
220
+ constexpr const_reverse_iterator crend() const noexcept;
221
 
222
  // [flat.map.capacity], capacity
223
+ constexpr bool empty() const noexcept;
224
+ constexpr size_type size() const noexcept;
225
+ constexpr size_type max_size() const noexcept;
226
 
227
  // [flat.map.access], element access
228
+ constexpr mapped_type& operator[](const key_type& x);
229
+ constexpr mapped_type& operator[](key_type&& x);
230
+ template<class K> constexpr mapped_type& operator[](K&& x);
231
+ constexpr mapped_type& at(const key_type& x);
232
+ constexpr const mapped_type& at(const key_type& x) const;
233
+ template<class K> constexpr mapped_type& at(const K& x);
234
+ template<class K> constexpr const mapped_type& at(const K& x) const;
235
 
236
  // [flat.map.modifiers], modifiers
237
+ template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
238
  template<class... Args>
239
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
240
 
241
+ constexpr pair<iterator, bool> insert(const value_type& x)
242
  { return emplace(x); }
243
+ constexpr pair<iterator, bool> insert(value_type&& x)
244
  { return emplace(std::move(x)); }
245
+ constexpr iterator insert(const_iterator position, const value_type& x)
246
  { return emplace_hint(position, x); }
247
+ constexpr iterator insert(const_iterator position, value_type&& x)
248
  { return emplace_hint(position, std::move(x)); }
249
 
250
+ template<class P> constexpr pair<iterator, bool> insert(P&& x);
251
  template<class P>
252
+ constexpr iterator insert(const_iterator position, P&&);
253
  template<class InputIterator>
254
+ constexpr void insert(InputIterator first, InputIterator last);
255
  template<class InputIterator>
256
+ constexpr void insert(sorted_unique_t, InputIterator first, InputIterator last);
257
  template<container-compatible-range<value_type> R>
258
+ constexpr void insert_range(R&& rg);
259
 
260
+ constexpr void insert(initializer_list<value_type> il)
261
  { insert(il.begin(), il.end()); }
262
+ constexpr void insert(sorted_unique_t, initializer_list<value_type> il)
263
+ { insert(sorted_unique, il.begin(), il.end()); }
264
 
265
+ constexpr containers extract() &&;
266
+ constexpr void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);
267
 
268
  template<class... Args>
269
+ constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
270
  template<class... Args>
271
+ constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
272
  template<class K, class... Args>
273
+ constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args);
274
  template<class... Args>
275
+ constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
276
  template<class... Args>
277
+ constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
278
  template<class K, class... Args>
279
+ constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
280
  template<class M>
281
+ constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
282
  template<class M>
283
+ constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
284
  template<class K, class M>
285
+ constexpr pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
286
  template<class M>
287
+ constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
288
  template<class M>
289
+ constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
290
  template<class K, class M>
291
+ constexpr iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
292
 
293
+ constexpr iterator erase(iterator position);
294
+ constexpr iterator erase(const_iterator position);
295
+ constexpr size_type erase(const key_type& x);
296
+ template<class K> constexpr size_type erase(K&& x);
297
+ constexpr iterator erase(const_iterator first, const_iterator last);
298
 
299
+ constexpr void swap(flat_map& y) noexcept;
300
+ constexpr void clear() noexcept;
301
 
302
  // observers
303
+ constexpr key_compare key_comp() const;
304
+ constexpr value_compare value_comp() const;
305
 
306
+ constexpr const key_container_type& keys() const noexcept { return c.keys; }
307
+ constexpr const mapped_container_type& values() const noexcept { return c.values; }
308
 
309
  // map operations
310
+ constexpr iterator find(const key_type& x);
311
+ constexpr const_iterator find(const key_type& x) const;
312
+ template<class K> constexpr iterator find(const K& x);
313
+ template<class K> constexpr const_iterator find(const K& x) const;
314
 
315
+ constexpr size_type count(const key_type& x) const;
316
+ template<class K> constexpr size_type count(const K& x) const;
317
 
318
+ constexpr bool contains(const key_type& x) const;
319
+ template<class K> constexpr bool contains(const K& x) const;
320
 
321
+ constexpr iterator lower_bound(const key_type& x);
322
+ constexpr const_iterator lower_bound(const key_type& x) const;
323
+ template<class K> constexpr iterator lower_bound(const K& x);
324
+ template<class K> constexpr const_iterator lower_bound(const K& x) const;
325
 
326
+ constexpr iterator upper_bound(const key_type& x);
327
+ constexpr const_iterator upper_bound(const key_type& x) const;
328
+ template<class K> constexpr iterator upper_bound(const K& x);
329
+ template<class K> constexpr const_iterator upper_bound(const K& x) const;
330
 
331
+ constexpr pair<iterator, iterator> equal_range(const key_type& x);
332
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
333
+ template<class K> constexpr pair<iterator, iterator> equal_range(const K& x);
334
+ template<class K>
335
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
336
 
337
+ friend constexpr bool operator==(const flat_map& x, const flat_map& y);
338
 
339
+ friend constexpr synth-three-way-result<value_type>
340
  operator<=>(const flat_map& x, const flat_map& y);
341
 
342
+ friend constexpr void swap(flat_map& x, flat_map& y) noexcept
343
  { x.swap(y); }
344
 
345
  private:
346
  containers c; // exposition only
347
  key_compare compare; // exposition only
348
 
349
+ struct key-equiv { // exposition only
350
+ constexpr key-equiv(key_compare c) : comp(c) { }
351
+ constexpr bool operator()(const_reference x, const_reference y) const {
352
  return !comp(x.first, y.first) && !comp(y.first, x.first);
353
  }
354
  key_compare comp;
355
  };
356
  };
 
427
  specified.
428
 
429
  #### Constructors <a id="flat.map.cons">[[flat.map.cons]]</a>
430
 
431
  ``` cpp
432
+ constexpr flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
433
  const key_compare& comp = key_compare());
434
  ```
435
 
436
+ *Effects:* Initializes *`c`*`.keys` with `std::move(key_cont)`,
437
+ *`c`*`.values` with `std::move(mapped_cont)`, and *compare* with `comp`;
438
+ sorts the range \[`begin()`, `end()`) with respect to `value_comp()`;
439
+ and finally erases the duplicate elements as if by:
440
 
441
  ``` cpp
442
+ auto zv = views::zip(c.keys, c.values);
443
+ auto it = ranges::unique(zv, key-equiv(compare)).begin();
444
  auto dist = distance(zv.begin(), it);
445
  c.keys.erase(c.keys.begin() + dist, c.keys.end());
446
  c.values.erase(c.values.begin() + dist, c.values.end());
447
  ```
448
 
449
  *Complexity:* Linear in N if the container arguments are already sorted
450
  with respect to `value_comp()` and otherwise N log N, where N is the
451
  value of `key_cont.size()` before this call.
452
 
453
  ``` cpp
454
+ constexpr flat_map(sorted_unique_t, key_container_type key_cont, mapped_container_type mapped_cont,
455
+ const key_compare& comp = key_compare());
 
 
 
 
456
  ```
457
 
458
+ *Effects:* Initializes *`c`*`.keys` with `std::move(key_cont)`,
459
+ *`c`*`.values` with `std::move(mapped_cont)`, and *compare* with `comp`.
460
+
461
+ *Complexity:* Constant.
462
+
463
+ #### Constructors with allocators <a id="flat.map.cons.alloc">[[flat.map.cons.alloc]]</a>
464
+
465
+ The constructors in this subclause shall not participate in overload
466
+ resolution unless `uses_allocator_v<key_container_type, Alloc>` is
467
+ `true` and `uses_allocator_v<mapped_container_type, Alloc>` is `true`.
468
+
469
+ ``` cpp
470
+ template<class Alloc>
471
+ constexpr flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
472
+ const Alloc& a);
473
+ template<class Alloc>
474
+ constexpr flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
475
+ const key_compare& comp, const Alloc& a);
476
+ ```
477
 
478
  *Effects:* Equivalent to `flat_map(key_cont, mapped_cont)` and
479
  `flat_map(key_cont, mapped_cont, comp)`, respectively, except that
480
+ *`c`*`.keys` and *`c`*`.values` are constructed with uses-allocator
481
  construction [[allocator.uses.construction]].
482
 
483
  *Complexity:* Same as `flat_map(key_cont, mapped_cont)` and
484
  `flat_map(key_cont, mapped_cont, comp)`, respectively.
485
 
486
  ``` cpp
487
+ template<class Alloc>
488
+ constexpr flat_map(sorted_unique_t, const key_container_type& key_cont,
489
+ const mapped_container_type& mapped_cont, const Alloc& a);
490
+ template<class Alloc>
491
+ constexpr flat_map(sorted_unique_t, const key_container_type& key_cont,
 
 
 
 
 
 
 
 
 
 
492
  const mapped_container_type& mapped_cont, const key_compare& comp,
493
+ const Alloc& a);
494
  ```
495
 
496
+ *Effects:* Equivalent to
497
+ `flat_map(sorted_unique, key_cont, mapped_cont)` and
498
+ `flat_map(sorted_unique, key_cont, mapped_cont, comp)`, respectively,
499
+ except that *`c`*`.keys` and *`c`*`.values` are constructed with
500
+ uses-allocator construction [[allocator.uses.construction]].
 
 
 
501
 
502
  *Complexity:* Linear.
503
 
504
  ``` cpp
505
+ template<class Alloc>
506
+ constexpr explicit flat_map(const Alloc& a);
507
+ template<class Alloc>
508
+ constexpr flat_map(const key_compare& comp, const Alloc& a);
509
+ template<class Alloc>
510
+ constexpr flat_map(const flat_map&, const Alloc& a);
511
+ template<class Alloc>
512
+ constexpr flat_map(flat_map&&, const Alloc& a);
513
+ template<class InputIterator, class Alloc>
514
+ constexpr flat_map(InputIterator first, InputIterator last, const Alloc& a);
515
+ template<class InputIterator, class Alloc>
516
+ constexpr flat_map(InputIterator first, InputIterator last, const key_compare& comp,
517
+ const Alloc& a);
518
+ template<class InputIterator, class Alloc>
519
+ constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last, const Alloc& a);
520
+ template<class InputIterator, class Alloc>
521
+ constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last,
522
+ const key_compare& comp, const Alloc& a);
523
+ template<container-compatible-range<value_type> R, class Alloc>
524
+ constexpr flat_map(from_range_t, R&& rg, const Alloc& a);
525
+ template<container-compatible-range<value_type> R, class Alloc>
526
+ constexpr flat_map(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
527
+ template<class Alloc>
528
+ constexpr flat_map(initializer_list<value_type> il, const Alloc& a);
529
+ template<class Alloc>
530
+ constexpr flat_map(initializer_list<value_type> il, const key_compare& comp, const Alloc& a);
531
+ template<class Alloc>
532
+ constexpr flat_map(sorted_unique_t, initializer_list<value_type> il, const Alloc& a);
533
+ template<class Alloc>
534
+ constexpr flat_map(sorted_unique_t, initializer_list<value_type> il,
535
+ const key_compare& comp, const Alloc& a);
536
  ```
537
 
 
 
 
 
538
  *Effects:* Equivalent to the corresponding non-allocator constructors
539
+ except that *`c`*`.keys` and *`c`*`.values` are constructed with
540
+ uses-allocator construction [[allocator.uses.construction]].
541
 
542
  #### Capacity <a id="flat.map.capacity">[[flat.map.capacity]]</a>
543
 
544
  ``` cpp
545
+ constexpr size_type size() const noexcept;
546
  ```
547
 
548
+ *Returns:* *`c`*`.keys.size()`.
549
 
550
  ``` cpp
551
+ constexpr size_type max_size() const noexcept;
552
  ```
553
 
554
+ *Returns:*
555
+ `min<size_type>(`*`c`*`.keys.max_size(), `*`c`*`.values.max_size())`.
556
 
557
  #### Access <a id="flat.map.access">[[flat.map.access]]</a>
558
 
559
  ``` cpp
560
+ constexpr mapped_type& operator[](const key_type& x);
561
  ```
562
 
563
  *Effects:* Equivalent to: `return try_emplace(x).first->second;`
564
 
565
  ``` cpp
566
+ constexpr mapped_type& operator[](key_type&& x);
567
  ```
568
 
569
  *Effects:* Equivalent to:
570
  `return try_emplace(std::move(x)).first->second;`
571
 
572
  ``` cpp
573
+ template<class K> constexpr mapped_type& operator[](K&& x);
574
  ```
575
 
576
  *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
577
  denotes a type.
578
 
579
  *Effects:* Equivalent to:
580
  `return try_emplace(std::forward<K>(x)).first->second;`
581
 
582
  ``` cpp
583
+ constexpr mapped_type& at(const key_type& x);
584
+ constexpr const mapped_type& at(const key_type& x) const;
585
  ```
586
 
587
  *Returns:* A reference to the `mapped_type` corresponding to `x` in
588
  `*this`.
589
 
 
591
  is present.
592
 
593
  *Complexity:* Logarithmic.
594
 
595
  ``` cpp
596
+ template<class K> constexpr mapped_type& at(const K& x);
597
+ template<class K> constexpr const mapped_type& at(const K& x) const;
598
  ```
599
 
600
  *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
601
  denotes a type.
602
 
 
612
  *Complexity:* Logarithmic.
613
 
614
  #### Modifiers <a id="flat.map.modifiers">[[flat.map.modifiers]]</a>
615
 
616
  ``` cpp
617
+ template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
618
  ```
619
 
620
  *Constraints:*
621
  `is_constructible_v<pair<key_type, mapped_type>, Args...>` is `true`.
622
 
 
635
  *Returns:* The `bool` component of the returned pair is `true` if and
636
  only if the insertion took place, and the iterator component of the pair
637
  points to the element with key equivalent to `t.first`.
638
 
639
  ``` cpp
640
+ template<class P> constexpr pair<iterator, bool> insert(P&& x);
641
+ template<class P> constexpr iterator insert(const_iterator position, P&& x);
642
  ```
643
 
644
  *Constraints:* `is_constructible_v<pair<key_type, mapped_type>, P>` is
645
  `true`.
646
 
 
648
  `return emplace(std::forward<P>(x));`. The second form is equivalent to
649
  `return emplace_hint(position, std::forward<P>(x));`.
650
 
651
  ``` cpp
652
  template<class InputIterator>
653
+ constexpr void insert(InputIterator first, InputIterator last);
654
  ```
655
 
656
+ *Effects:* Adds elements to *c* as if by:
657
 
658
  ``` cpp
659
  for (; first != last; ++first) {
660
  value_type value = *first;
661
  c.keys.insert(c.keys.end(), std::move(value.first));
 
667
  `value_comp()`; merges the resulting sorted range and the sorted range
668
  of pre-existing elements into a single sorted range; and finally erases
669
  the duplicate elements as if by:
670
 
671
  ``` cpp
672
+ auto zv = views::zip(c.keys, c.values);
673
+ auto it = ranges::unique(zv, key-equiv(compare)).begin();
674
  auto dist = distance(zv.begin(), it);
675
  c.keys.erase(c.keys.begin() + dist, c.keys.end());
676
  c.values.erase(c.values.begin() + dist, c.values.end());
677
  ```
678
 
 
682
  *Remarks:* Since this operation performs an in-place merge, it may
683
  allocate memory.
684
 
685
  ``` cpp
686
  template<class InputIterator>
687
+ constexpr void insert(sorted_unique_t, InputIterator first, InputIterator last);
688
  ```
689
 
690
+ *Effects:* Equivalent to `insert(first, last)`.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
691
 
692
  *Complexity:* Linear in N, where N is `size()` after the operation.
693
 
 
 
 
694
  ``` cpp
695
  template<container-compatible-range<value_type> R>
696
+ constexpr void insert_range(R&& rg);
697
  ```
698
 
699
+ *Effects:* Adds elements to *c* as if by:
700
 
701
  ``` cpp
702
  for (const auto& e : rg) {
703
  c.keys.insert(c.keys.end(), e.first);
704
  c.values.insert(c.values.end(), e.second);
 
709
  `value_comp()`; merges the resulting sorted range and the sorted range
710
  of pre-existing elements into a single sorted range; and finally erases
711
  the duplicate elements as if by:
712
 
713
  ``` cpp
714
+ auto zv = views::zip(c.keys, c.values);
715
+ auto it = ranges::unique(zv, key-equiv(compare)).begin();
716
  auto dist = distance(zv.begin(), it);
717
  c.keys.erase(c.keys.begin() + dist, c.keys.end());
718
  c.values.erase(c.values.begin() + dist, c.values.end());
719
  ```
720
 
 
724
  *Remarks:* Since this operation performs an in-place merge, it may
725
  allocate memory.
726
 
727
  ``` cpp
728
  template<class... Args>
729
+ constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
730
  template<class... Args>
731
+ constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
732
  template<class... Args>
733
+ constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
734
  template<class... Args>
735
+ constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
736
  ```
737
 
738
  *Constraints:* `is_constructible_v<mapped_type, Args...>` is `true`.
739
 
740
  *Effects:* If the map already contains an element whose key is
 
756
  *Complexity:* The same as `emplace` for the first two overloads, and the
757
  same as `emplace_hint` for the last two overloads.
758
 
759
  ``` cpp
760
  template<class K, class... Args>
761
+ constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args);
762
  template<class K, class... Args>
763
+ constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
764
  ```
765
 
766
  *Constraints:*
767
 
768
  - The *qualified-id* `Compare::is_transparent` is valid and denotes a
 
778
  *Effects:* If the map already contains an element whose key is
779
  equivalent to `k`, `*this` and `args...` are unchanged. Otherwise
780
  equivalent to:
781
 
782
  ``` cpp
783
+ auto key_it = upper_bound(c.keys.begin(), c.keys.end(), k, compare);
784
  auto value_it = c.values.begin() + distance(c.keys.begin(), key_it);
785
  c.keys.emplace(key_it, std::forward<K>(k));
786
  c.values.emplace(value_it, std::forward<Args>(args)...);
787
  ```
788
 
 
792
 
793
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
794
 
795
  ``` cpp
796
  template<class M>
797
+ constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
798
  template<class M>
799
+ constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
800
  template<class M>
801
+ constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
802
  template<class M>
803
+ constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
804
  ```
805
 
806
  *Constraints:* `is_assignable_v<mapped_type&, M>` is `true` and
807
  `is_constructible_v<mapped_type, M>` is `true`.
808
 
 
830
  *Complexity:* The same as `emplace` for the first two overloads and the
831
  same as `emplace_hint` for the last two overloads.
832
 
833
  ``` cpp
834
  template<class K, class M>
835
+ constexpr pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
836
  template<class K, class M>
837
+ constexpr iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
838
  ```
839
 
840
  *Constraints:*
841
 
842
  - The *qualified-id* `Compare::is_transparent` is valid and denotes a
 
869
  iterator points to the map element whose key is equivalent to `k`.
870
 
871
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
872
 
873
  ``` cpp
874
+ constexpr void swap(flat_map& y) noexcept;
875
  ```
876
 
877
  *Effects:* Equivalent to:
878
 
879
  ``` cpp
 
881
  ranges::swap(c.keys, y.c.keys);
882
  ranges::swap(c.values, y.c.values);
883
  ```
884
 
885
  ``` cpp
886
+ constexpr containers extract() &&;
887
  ```
888
 
889
  *Ensures:* `*this` is emptied, even if the function exits via an
890
  exception.
891
 
892
+ *Returns:* `std::move(`*`c`*`)`.
893
 
894
  ``` cpp
895
+ constexpr void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);
896
  ```
897
 
898
  *Preconditions:* `key_cont.size() == mapped_cont.size()` is `true`, the
899
+ elements of `key_cont` are sorted with respect to *compare*, and
900
  `key_cont` contains no equal elements.
901
 
902
  *Effects:* Equivalent to:
903
 
904
  ``` cpp
 
909
  #### Erasure <a id="flat.map.erasure">[[flat.map.erasure]]</a>
910
 
911
  ``` cpp
912
  template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
913
  class Predicate>
914
+ constexpr typename flat_map<Key, T, Compare, KeyContainer, MappedContainer>::size_type
915
  erase_if(flat_map<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
916
  ```
917
 
918
  *Preconditions:* `Key` and `T` meet the *Cpp17MoveAssignable*
919
  requirements.