From Jason Turner

[container.adaptors]

Large diff (171.2 KB) - rendering may be slow on some devices

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpolrii7h9/{from.md → to.md} +1214 -1145
tmp/tmpolrii7h9/{from.md → to.md} RENAMED
@@ -1,8 +1,8 @@
1
  ## Container adaptors <a id="container.adaptors">[[container.adaptors]]</a>
2
 
3
- ### In general <a id="container.adaptors.general">[[container.adaptors.general]]</a>
4
 
5
  The headers `<queue>`, `<stack>`, `<flat_map>`, and `<flat_set>` define
6
  the container adaptors `queue` and `priority_queue`, `stack`, `flat_map`
7
  and `flat_multimap`, and `flat_set` and `flat_multiset`, respectively.
8
 
@@ -73,12 +73,11 @@ deduction guides for container adaptors.
73
  The following exposition-only alias template may appear in deduction
74
  guides for container adaptors:
75
 
76
  ``` cpp
77
  template<class Allocator, class T>
78
- using alloc-rebind = // exposition only
79
- typename allocator_traits<Allocator>::template rebind_alloc<T>;
80
  ```
81
 
82
  ### Header `<queue>` synopsis <a id="queue.syn">[[queue.syn]]</a>
83
 
84
  ``` cpp
@@ -88,159 +87,49 @@ template<class Allocator, class T>
88
  namespace std {
89
  // [queue], class template queue
90
  template<class T, class Container = deque<T>> class queue;
91
 
92
  template<class T, class Container>
93
- bool operator==(const queue<T, Container>& x, const queue<T, Container>& y);
94
  template<class T, class Container>
95
- bool operator!=(const queue<T, Container>& x, const queue<T, Container>& y);
96
  template<class T, class Container>
97
- bool operator< (const queue<T, Container>& x, const queue<T, Container>& y);
98
  template<class T, class Container>
99
- bool operator> (const queue<T, Container>& x, const queue<T, Container>& y);
100
  template<class T, class Container>
101
- bool operator<=(const queue<T, Container>& x, const queue<T, Container>& y);
102
  template<class T, class Container>
103
- bool operator>=(const queue<T, Container>& x, const queue<T, Container>& y);
104
  template<class T, three_way_comparable Container>
105
- compare_three_way_result_t<Container>
106
  operator<=>(const queue<T, Container>& x, const queue<T, Container>& y);
107
 
108
  template<class T, class Container>
109
- void swap(queue<T, Container>& x, queue<T, Container>& y) noexcept(noexcept(x.swap(y)));
 
110
  template<class T, class Container, class Alloc>
111
  struct uses_allocator<queue<T, Container>, Alloc>;
112
 
 
 
 
 
113
  // [priority.queue], class template priority_queue
114
  template<class T, class Container = vector<T>,
115
  class Compare = less<typename Container::value_type>>
116
  class priority_queue;
117
 
118
  template<class T, class Container, class Compare>
119
- void swap(priority_queue<T, Container, Compare>& x,
120
  priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
121
  template<class T, class Container, class Compare, class Alloc>
122
  struct uses_allocator<priority_queue<T, Container, Compare>, Alloc>;
123
- }
124
- ```
125
 
126
- ### Header `<stack>` synopsis <a id="stack.syn">[[stack.syn]]</a>
127
-
128
- ``` cpp
129
- #include <compare> // see [compare.syn]
130
- #include <initializer_list> // see [initializer.list.syn]
131
-
132
- namespace std {
133
- // [stack], class template stack
134
- template<class T, class Container = deque<T>> class stack;
135
-
136
- template<class T, class Container>
137
- bool operator==(const stack<T, Container>& x, const stack<T, Container>& y);
138
- template<class T, class Container>
139
- bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y);
140
- template<class T, class Container>
141
- bool operator< (const stack<T, Container>& x, const stack<T, Container>& y);
142
- template<class T, class Container>
143
- bool operator> (const stack<T, Container>& x, const stack<T, Container>& y);
144
- template<class T, class Container>
145
- bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y);
146
- template<class T, class Container>
147
- bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y);
148
- template<class T, three_way_comparable Container>
149
- compare_three_way_result_t<Container>
150
- operator<=>(const stack<T, Container>& x, const stack<T, Container>& y);
151
-
152
- template<class T, class Container>
153
- void swap(stack<T, Container>& x, stack<T, Container>& y) noexcept(noexcept(x.swap(y)));
154
- template<class T, class Container, class Alloc>
155
- struct uses_allocator<stack<T, Container>, Alloc>;
156
- }
157
- ```
158
-
159
- ### Header `<flat_map>` synopsis <a id="flat.map.syn">[[flat.map.syn]]</a>
160
-
161
- ``` cpp
162
- #include <compare> // see [compare.syn]
163
- #include <initializer_list> // see [initializer.list.syn]
164
-
165
- namespace std {
166
- // [flat.map], class template flat_map
167
- template<class Key, class T, class Compare = less<Key>,
168
- class KeyContainer = vector<Key>, class MappedContainer = vector<T>>
169
- class flat_map;
170
-
171
- struct sorted_unique_t { explicit sorted_unique_t() = default; };
172
- inline constexpr sorted_unique_t sorted_unique{};
173
-
174
- template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
175
- class Allocator>
176
- struct uses_allocator<flat_map<Key, T, Compare, KeyContainer, MappedContainer>,
177
- Allocator>;
178
-
179
- // [flat.map.erasure], erasure for flat_map
180
- template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
181
- class Predicate>
182
- typename flat_map<Key, T, Compare, KeyContainer, MappedContainer>::size_type
183
- erase_if(flat_map<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
184
-
185
- // [flat.multimap], class template flat_multimap
186
- template<class Key, class T, class Compare = less<Key>,
187
- class KeyContainer = vector<Key>, class MappedContainer = vector<T>>
188
- class flat_multimap;
189
-
190
- struct sorted_equivalent_t { explicit sorted_equivalent_t() = default; };
191
- inline constexpr sorted_equivalent_t sorted_equivalent{};
192
-
193
- template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
194
- class Allocator>
195
- struct uses_allocator<flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>,
196
- Allocator>;
197
-
198
- // [flat.multimap.erasure], erasure for flat_multimap
199
- template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
200
- class Predicate>
201
- typename flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>::size_type
202
- erase_if(flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
203
- }
204
- ```
205
-
206
- ### Header `<flat_set>` synopsis <a id="flat.set.syn">[[flat.set.syn]]</a>
207
-
208
- ``` cpp
209
- #include <compare> // see [compare.syn]
210
- #include <initializer_list> // see [initializer.list.syn]
211
-
212
- namespace std {
213
- // [flat.set], class template flat_set
214
- template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>
215
- class flat_set;
216
-
217
- struct sorted_unique_t { explicit sorted_unique_t() = default; };
218
- inline constexpr sorted_unique_t sorted_unique{};
219
-
220
- template<class Key, class Compare, class KeyContainer, class Allocator>
221
- struct uses_allocator<flat_set<Key, Compare, KeyContainer>, Allocator>;
222
-
223
- // [flat.set.erasure], erasure for flat_set
224
- template<class Key, class Compare, class KeyContainer, class Predicate>
225
- typename flat_set<Key, Compare, KeyContainer>::size_type
226
- erase_if(flat_set<Key, Compare, KeyContainer>& c, Predicate pred);
227
-
228
- // [flat.multiset], class template flat_multiset
229
- template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>
230
- class flat_multiset;
231
-
232
- struct sorted_equivalent_t { explicit sorted_equivalent_t() = default; };
233
- inline constexpr sorted_equivalent_t sorted_equivalent{};
234
-
235
- template<class Key, class Compare, class KeyContainer, class Allocator>
236
- struct uses_allocator<flat_multiset<Key, Compare, KeyContainer>, Allocator>;
237
-
238
- // [flat.multiset.erasure], erasure for flat_multiset
239
- template<class Key, class Compare, class KeyContainer, class Predicate>
240
- typename flat_multiset<Key, Compare, KeyContainer>::size_type
241
- erase_if(flat_multiset<Key, Compare, KeyContainer>& c, Predicate pred);
242
  }
243
  ```
244
 
245
  ### Class template `queue` <a id="queue">[[queue]]</a>
246
 
@@ -253,49 +142,49 @@ particular, `list` [[list]] and `deque` [[deque]] can be used.
253
  ``` cpp
254
  namespace std {
255
  template<class T, class Container = deque<T>>
256
  class queue {
257
  public:
258
- using value_type = typename Container::value_type;
259
- using reference = typename Container::reference;
260
- using const_reference = typename Container::const_reference;
261
- using size_type = typename Container::size_type;
262
  using container_type = Container;
263
 
264
  protected:
265
  Container c;
266
 
267
  public:
268
- queue() : queue(Container()) {}
269
- explicit queue(const Container&);
270
- explicit queue(Container&&);
271
- template<class InputIterator> queue(InputIterator first, InputIterator last);
272
- template<container-compatible-range<T> R> queue(from_range_t, R&& rg);
273
- template<class Alloc> explicit queue(const Alloc&);
274
- template<class Alloc> queue(const Container&, const Alloc&);
275
- template<class Alloc> queue(Container&&, const Alloc&);
276
- template<class Alloc> queue(const queue&, const Alloc&);
277
- template<class Alloc> queue(queue&&, const Alloc&);
278
  template<class InputIterator, class Alloc>
279
- queue(InputIterator first, InputIterator last, const Alloc&);
280
  template<container-compatible-range<T> R, class Alloc>
281
- queue(from_range_t, R&& rg, const Alloc&);
282
 
283
- [[nodiscard]] bool empty() const { return c.empty(); }
284
- size_type size() const { return c.size(); }
285
- reference front() { return c.front(); }
286
- const_reference front() const { return c.front(); }
287
- reference back() { return c.back(); }
288
- const_reference back() const { return c.back(); }
289
- void push(const value_type& x) { c.push_back(x); }
290
- void push(value_type&& x) { c.push_back(std::move(x)); }
291
- template<container-compatible-range<T> R> void push_range(R&& rg);
292
  template<class... Args>
293
- decltype(auto) emplace(Args&&... args)
294
  { return c.emplace_back(std::forward<Args>(args)...); }
295
- void pop() { c.pop_front(); }
296
- void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>)
297
  { using std::swap; swap(c, q.c); }
298
  };
299
 
300
  template<class Container>
301
  queue(Container) -> queue<typename Container::value_type, Container>;
@@ -325,32 +214,32 @@ namespace std {
325
  ```
326
 
327
  #### Constructors <a id="queue.cons">[[queue.cons]]</a>
328
 
329
  ``` cpp
330
- explicit queue(const Container& cont);
331
  ```
332
 
333
  *Effects:* Initializes `c` with `cont`.
334
 
335
  ``` cpp
336
- explicit queue(Container&& cont);
337
  ```
338
 
339
  *Effects:* Initializes `c` with `std::move(cont)`.
340
 
341
  ``` cpp
342
  template<class InputIterator>
343
- queue(InputIterator first, InputIterator last);
344
  ```
345
 
346
  *Effects:* Initializes `c` with `first` as the first argument and `last`
347
  as the second argument.
348
 
349
  ``` cpp
350
  template<container-compatible-range<T> R>
351
- queue(from_range_t, R&& rg);
352
  ```
353
 
354
  *Effects:* Initializes `c` with
355
  `ranges::to<Container>(std::forward<R>(rg))`.
356
 
@@ -358,127 +247,127 @@ template<container-compatible-range<T> R>
358
 
359
  If `uses_allocator_v<container_type, Alloc>` is `false` the constructors
360
  in this subclause shall not participate in overload resolution.
361
 
362
  ``` cpp
363
- template<class Alloc> explicit queue(const Alloc& a);
364
  ```
365
 
366
  *Effects:* Initializes `c` with `a`.
367
 
368
  ``` cpp
369
- template<class Alloc> queue(const container_type& cont, const Alloc& a);
370
  ```
371
 
372
  *Effects:* Initializes `c` with `cont` as the first argument and `a` as
373
  the second argument.
374
 
375
  ``` cpp
376
- template<class Alloc> queue(container_type&& cont, const Alloc& a);
377
  ```
378
 
379
  *Effects:* Initializes `c` with `std::move(cont)` as the first argument
380
  and `a` as the second argument.
381
 
382
  ``` cpp
383
- template<class Alloc> queue(const queue& q, const Alloc& a);
384
  ```
385
 
386
  *Effects:* Initializes `c` with `q.c` as the first argument and `a` as
387
  the second argument.
388
 
389
  ``` cpp
390
- template<class Alloc> queue(queue&& q, const Alloc& a);
391
  ```
392
 
393
  *Effects:* Initializes `c` with `std::move(q.c)` as the first argument
394
  and `a` as the second argument.
395
 
396
  ``` cpp
397
  template<class InputIterator, class Alloc>
398
- queue(InputIterator first, InputIterator last, const Alloc& alloc);
399
  ```
400
 
401
  *Effects:* Initializes `c` with `first` as the first argument, `last` as
402
  the second argument, and `alloc` as the third argument.
403
 
404
  ``` cpp
405
  template<container-compatible-range<T> R, class Alloc>
406
- queue(from_range_t, R&& rg, const Alloc& a);
407
  ```
408
 
409
  *Effects:* Initializes `c` with
410
  `ranges::to<Container>(std::forward<R>(rg), a)`.
411
 
412
  #### Modifiers <a id="queue.mod">[[queue.mod]]</a>
413
 
414
  ``` cpp
415
  template<container-compatible-range<T> R>
416
- void push_range(R&& rg);
417
  ```
418
 
419
  *Effects:* Equivalent to `c.append_range(std::forward<R>(rg))` if that
420
  is a valid expression, otherwise `ranges::copy(rg, back_inserter(c))`.
421
 
422
  #### Operators <a id="queue.ops">[[queue.ops]]</a>
423
 
424
  ``` cpp
425
  template<class T, class Container>
426
- bool operator==(const queue<T, Container>& x, const queue<T, Container>& y);
427
  ```
428
 
429
  *Returns:* `x.c == y.c`.
430
 
431
  ``` cpp
432
  template<class T, class Container>
433
- bool operator!=(const queue<T, Container>& x, const queue<T, Container>& y);
434
  ```
435
 
436
  *Returns:* `x.c != y.c`.
437
 
438
  ``` cpp
439
  template<class T, class Container>
440
- bool operator< (const queue<T, Container>& x, const queue<T, Container>& y);
441
  ```
442
 
443
  *Returns:* `x.c < y.c`.
444
 
445
  ``` cpp
446
  template<class T, class Container>
447
- bool operator> (const queue<T, Container>& x, const queue<T, Container>& y);
448
  ```
449
 
450
  *Returns:* `x.c > y.c`.
451
 
452
  ``` cpp
453
  template<class T, class Container>
454
- bool operator<=(const queue<T, Container>& x, const queue<T, Container>& y);
455
  ```
456
 
457
  *Returns:* `x.c <= y.c`.
458
 
459
  ``` cpp
460
  template<class T, class Container>
461
- bool operator>=(const queue<T, Container>& x,
462
- const queue<T, Container>& y);
463
  ```
464
 
465
  *Returns:* `x.c >= y.c`.
466
 
467
  ``` cpp
468
  template<class T, three_way_comparable Container>
469
- compare_three_way_result_t<Container>
470
  operator<=>(const queue<T, Container>& x, const queue<T, Container>& y);
471
  ```
472
 
473
  *Returns:* `x.c <=> y.c`.
474
 
475
  #### Specialized algorithms <a id="queue.special">[[queue.special]]</a>
476
 
477
  ``` cpp
478
  template<class T, class Container>
479
- void swap(queue<T, Container>& x, queue<T, Container>& y) noexcept(noexcept(x.swap(y)));
 
480
  ```
481
 
482
  *Constraints:* `is_swappable_v<Container>` is `true`.
483
 
484
  *Effects:* As if by `x.swap(y)`.
@@ -499,67 +388,70 @@ defines a strict weak ordering [[alg.sorting]].
499
  namespace std {
500
  template<class T, class Container = vector<T>,
501
  class Compare = less<typename Container::value_type>>
502
  class priority_queue {
503
  public:
504
- using value_type = typename Container::value_type;
505
- using reference = typename Container::reference;
506
- using const_reference = typename Container::const_reference;
507
- using size_type = typename Container::size_type;
508
  using container_type = Container;
509
  using value_compare = Compare;
510
 
511
  protected:
512
  Container c;
513
  Compare comp;
514
 
515
  public:
516
- priority_queue() : priority_queue(Compare()) {}
517
- explicit priority_queue(const Compare& x) : priority_queue(x, Container()) {}
518
- priority_queue(const Compare& x, const Container&);
519
- priority_queue(const Compare& x, Container&&);
520
  template<class InputIterator>
521
- priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare());
 
522
  template<class InputIterator>
523
- priority_queue(InputIterator first, InputIterator last, const Compare& x,
524
  const Container&);
525
  template<class InputIterator>
526
- priority_queue(InputIterator first, InputIterator last, const Compare& x,
527
  Container&&);
528
  template<container-compatible-range<T> R>
529
- priority_queue(from_range_t, R&& rg, const Compare& x = Compare());
530
- template<class Alloc> explicit priority_queue(const Alloc&);
531
- template<class Alloc> priority_queue(const Compare&, const Alloc&);
532
- template<class Alloc> priority_queue(const Compare&, const Container&, const Alloc&);
533
- template<class Alloc> priority_queue(const Compare&, Container&&, const Alloc&);
534
- template<class Alloc> priority_queue(const priority_queue&, const Alloc&);
535
- template<class Alloc> priority_queue(priority_queue&&, const Alloc&);
 
536
  template<class InputIterator, class Alloc>
537
- priority_queue(InputIterator, InputIterator, const Alloc&);
538
  template<class InputIterator, class Alloc>
539
- priority_queue(InputIterator, InputIterator, const Compare&, const Alloc&);
540
  template<class InputIterator, class Alloc>
541
- priority_queue(InputIterator, InputIterator, const Compare&, const Container&,
542
  const Alloc&);
543
  template<class InputIterator, class Alloc>
544
- priority_queue(InputIterator, InputIterator, const Compare&, Container&&, const Alloc&);
 
545
  template<container-compatible-range<T> R, class Alloc>
546
- priority_queue(from_range_t, R&& rg, const Compare&, const Alloc&);
547
  template<container-compatible-range<T> R, class Alloc>
548
- priority_queue(from_range_t, R&& rg, const Alloc&);
549
 
550
- [[nodiscard]] bool empty() const { return c.empty(); }
551
- size_type size() const { return c.size(); }
552
- const_reference top() const { return c.front(); }
553
- void push(const value_type& x);
554
- void push(value_type&& x);
555
  template<container-compatible-range<T> R>
556
- void push_range(R&& rg);
557
- template<class... Args> void emplace(Args&&... args);
558
- void pop();
559
- void swap(priority_queue& q) noexcept(is_nothrow_swappable_v<Container> &&
560
- is_nothrow_swappable_v<Compare>)
561
  { using std::swap; swap(c, q.c); swap(comp, q.comp); }
562
  };
563
 
564
  template<class Compare, class Container>
565
  priority_queue(Compare, Container)
@@ -612,36 +504,38 @@ namespace std {
612
  ```
613
 
614
  #### Constructors <a id="priqueue.cons">[[priqueue.cons]]</a>
615
 
616
  ``` cpp
617
- priority_queue(const Compare& x, const Container& y);
618
- priority_queue(const Compare& x, Container&& y);
619
  ```
620
 
621
  *Preconditions:* `x` defines a strict weak ordering [[alg.sorting]].
622
 
623
  *Effects:* Initializes `comp` with `x` and `c` with `y` (copy
624
  constructing or move constructing as appropriate); calls
625
  `make_heap(c.begin(), c.end(), comp)`.
626
 
627
  ``` cpp
628
  template<class InputIterator>
629
- priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare());
630
  ```
631
 
632
  *Preconditions:* `x` defines a strict weak ordering [[alg.sorting]].
633
 
634
  *Effects:* Initializes `c` with `first` as the first argument and `last`
635
  as the second argument, and initializes `comp` with `x`; then calls
636
  `make_heap(c.begin(), c.end(), comp)`.
637
 
638
  ``` cpp
639
  template<class InputIterator>
640
- priority_queue(InputIterator first, InputIterator last, const Compare& x, const Container& y);
 
641
  template<class InputIterator>
642
- priority_queue(InputIterator first, InputIterator last, const Compare& x, Container&& y);
 
643
  ```
644
 
645
  *Preconditions:* `x` defines a strict weak ordering [[alg.sorting]].
646
 
647
  *Effects:* Initializes `comp` with `x` and `c` with `y` (copy
@@ -649,11 +543,11 @@ constructing or move constructing as appropriate); calls
649
  `c.insert(c.end(), first, last)`; and finally calls
650
  `make_heap(c.begin(), c.end(), comp)`.
651
 
652
  ``` cpp
653
  template<container-compatible-range<T> R>
654
- priority_queue(from_range_t, R&& rg, const Compare& x = Compare());
655
  ```
656
 
657
  *Preconditions:* `x` defines a strict weak ordering [[alg.sorting]].
658
 
659
  *Effects:* Initializes `comp` with `x` and `c` with
@@ -664,128 +558,129 @@ template<container-compatible-range<T> R>
664
 
665
  If `uses_allocator_v<container_type, Alloc>` is `false` the constructors
666
  in this subclause shall not participate in overload resolution.
667
 
668
  ``` cpp
669
- template<class Alloc> explicit priority_queue(const Alloc& a);
670
  ```
671
 
672
  *Effects:* Initializes `c` with `a` and value-initializes `comp`.
673
 
674
  ``` cpp
675
- template<class Alloc> priority_queue(const Compare& compare, const Alloc& a);
676
  ```
677
 
678
  *Effects:* Initializes `c` with `a` and initializes `comp` with
679
  `compare`.
680
 
681
  ``` cpp
682
  template<class Alloc>
683
- priority_queue(const Compare& compare, const Container& cont, const Alloc& a);
684
  ```
685
 
686
  *Effects:* Initializes `c` with `cont` as the first argument and `a` as
687
  the second argument, and initializes `comp` with `compare`; calls
688
  `make_heap(c.begin(), c.end(), comp)`.
689
 
690
  ``` cpp
691
  template<class Alloc>
692
- priority_queue(const Compare& compare, Container&& cont, const Alloc& a);
693
  ```
694
 
695
  *Effects:* Initializes `c` with `std::move(cont)` as the first argument
696
  and `a` as the second argument, and initializes `comp` with `compare`;
697
  calls `make_heap(c.begin(), c.end(), comp)`.
698
 
699
  ``` cpp
700
- template<class Alloc> priority_queue(const priority_queue& q, const Alloc& a);
701
  ```
702
 
703
  *Effects:* Initializes `c` with `q.c` as the first argument and `a` as
704
  the second argument, and initializes `comp` with `q.comp`.
705
 
706
  ``` cpp
707
- template<class Alloc> priority_queue(priority_queue&& q, const Alloc& a);
708
  ```
709
 
710
  *Effects:* Initializes `c` with `std::move(q.c)` as the first argument
711
  and `a` as the second argument, and initializes `comp` with
712
  `std::move(q.comp)`.
713
 
714
  ``` cpp
715
  template<class InputIterator, class Alloc>
716
- priority_queue(InputIterator first, InputIterator last, const Alloc& a);
717
  ```
718
 
719
  *Effects:* Initializes `c` with `first` as the first argument, `last` as
720
  the second argument, and `a` as the third argument, and
721
  value-initializes `comp`; calls `make_heap(c.begin(), c.end(), comp)`.
722
 
723
  ``` cpp
724
  template<class InputIterator, class Alloc>
725
- priority_queue(InputIterator first, InputIterator last, const Compare& compare, const Alloc& a);
 
726
  ```
727
 
728
  *Effects:* Initializes `c` with `first` as the first argument, `last` as
729
  the second argument, and `a` as the third argument, and initializes
730
  `comp` with `compare`; calls `make_heap(c.begin(), c.end(), comp)`.
731
 
732
  ``` cpp
733
  template<class InputIterator, class Alloc>
734
- priority_queue(InputIterator first, InputIterator last, const Compare& compare,
735
  const Container& cont, const Alloc& a);
736
  ```
737
 
738
  *Effects:* Initializes `c` with `cont` as the first argument and `a` as
739
  the second argument, and initializes `comp` with `compare`; calls
740
  `c.insert(c.end(), first, last)`; and finally calls
741
  `make_heap(c.begin(), c.end(), comp)`.
742
 
743
  ``` cpp
744
  template<class InputIterator, class Alloc>
745
- priority_queue(InputIterator first, InputIterator last, const Compare& compare, Container&& cont,
746
- const Alloc& a);
747
  ```
748
 
749
  *Effects:* Initializes `c` with `std::move(cont)` as the first argument
750
  and `a` as the second argument, and initializes `comp` with `compare`;
751
  calls `c.insert(c.end(), first, last)`; and finally calls
752
  `make_heap(c.begin(), c.end(), comp)`.
753
 
754
  ``` cpp
755
  template<container-compatible-range<T> R, class Alloc>
756
- priority_queue(from_range_t, R&& rg, const Compare& compare, const Alloc& a);
757
  ```
758
 
759
  *Effects:* Initializes `comp` with `compare` and `c` with
760
  `ranges::to<Container>(std::forward<R>(rg), a)`; calls
761
  `make_heap(c.begin(), c.end(), comp)`.
762
 
763
  ``` cpp
764
  template<container-compatible-range<T> R, class Alloc>
765
- priority_queue(from_range_t, R&& rg, const Alloc& a);
766
  ```
767
 
768
  *Effects:* Initializes `c` with
769
- `ranges::to<Container>(std::forward<R>(rg), a)`; calls
770
- `make_heap(c.begin(), c.end(), comp)`.
771
 
772
  #### Members <a id="priqueue.members">[[priqueue.members]]</a>
773
 
774
  ``` cpp
775
- void push(const value_type& x);
776
  ```
777
 
778
  *Effects:* As if by:
779
 
780
  ``` cpp
781
  c.push_back(x);
782
  push_heap(c.begin(), c.end(), comp);
783
  ```
784
 
785
  ``` cpp
786
- void push(value_type&& x);
787
  ```
788
 
789
  *Effects:* As if by:
790
 
791
  ``` cpp
@@ -793,33 +688,33 @@ c.push_back(std::move(x));
793
  push_heap(c.begin(), c.end(), comp);
794
  ```
795
 
796
  ``` cpp
797
  template<container-compatible-range<T> R>
798
- void push_range(R&& rg);
799
  ```
800
 
801
  *Effects:* Inserts all elements of `rg` in `c` via
802
  `c.append_range(std::forward<R>(rg))` if that is a valid expression, or
803
  `ranges::copy(rg, back_inserter(c))` otherwise. Then restores the heap
804
  property as if by `make_heap(c.begin(), c.end(), comp)`.
805
 
806
  *Ensures:* `is_heap(c.begin(), c.end(), comp)` is `true`.
807
 
808
  ``` cpp
809
- template<class... Args> void emplace(Args&&... args);
810
  ```
811
 
812
  *Effects:* As if by:
813
 
814
  ``` cpp
815
  c.emplace_back(std::forward<Args>(args)...);
816
  push_heap(c.begin(), c.end(), comp);
817
  ```
818
 
819
  ``` cpp
820
- void pop();
821
  ```
822
 
823
  *Effects:* As if by:
824
 
825
  ``` cpp
@@ -829,19 +724,57 @@ c.pop_back();
829
 
830
  #### Specialized algorithms <a id="priqueue.special">[[priqueue.special]]</a>
831
 
832
  ``` cpp
833
  template<class T, class Container, class Compare>
834
- void swap(priority_queue<T, Container, Compare>& x,
835
  priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
836
  ```
837
 
838
  *Constraints:* `is_swappable_v<Container>` is `true` and
839
  `is_swappable_v<Compare>` is `true`.
840
 
841
  *Effects:* As if by `x.swap(y)`.
842
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
843
  ### Class template `stack` <a id="stack">[[stack]]</a>
844
 
845
  #### General <a id="stack.general">[[stack.general]]</a>
846
 
847
  Any sequence container supporting operations `back()`, `push_back()` and
@@ -853,48 +786,49 @@ Any sequence container supporting operations `back()`, `push_back()` and
853
  ``` cpp
854
  namespace std {
855
  template<class T, class Container = deque<T>>
856
  class stack {
857
  public:
858
- using value_type = typename Container::value_type;
859
- using reference = typename Container::reference;
860
- using const_reference = typename Container::const_reference;
861
- using size_type = typename Container::size_type;
862
  using container_type = Container;
863
 
864
  protected:
865
  Container c;
866
 
867
  public:
868
- stack() : stack(Container()) {}
869
- explicit stack(const Container&);
870
- explicit stack(Container&&);
871
- template<class InputIterator> stack(InputIterator first, InputIterator last);
872
- template<container-compatible-range<T> R> stack(from_range_t, R&& rg);
873
- template<class Alloc> explicit stack(const Alloc&);
874
- template<class Alloc> stack(const Container&, const Alloc&);
875
- template<class Alloc> stack(Container&&, const Alloc&);
876
- template<class Alloc> stack(const stack&, const Alloc&);
877
- template<class Alloc> stack(stack&&, const Alloc&);
 
878
  template<class InputIterator, class Alloc>
879
- stack(InputIterator first, InputIterator last, const Alloc&);
880
  template<container-compatible-range<T> R, class Alloc>
881
- stack(from_range_t, R&& rg, const Alloc&);
882
 
883
- [[nodiscard]] bool empty() const { return c.empty(); }
884
- size_type size() const { return c.size(); }
885
- reference top() { return c.back(); }
886
- const_reference top() const { return c.back(); }
887
- void push(const value_type& x) { c.push_back(x); }
888
- void push(value_type&& x) { c.push_back(std::move(x)); }
889
  template<container-compatible-range<T> R>
890
- void push_range(R&& rg);
891
  template<class... Args>
892
- decltype(auto) emplace(Args&&... args)
893
  { return c.emplace_back(std::forward<Args>(args)...); }
894
- void pop() { c.pop_back(); }
895
- void swap(stack& s) noexcept(is_nothrow_swappable_v<Container>)
896
  { using std::swap; swap(c, s.c); }
897
  };
898
 
899
  template<class Container>
900
  stack(Container) -> stack<typename Container::value_type, Container>;
@@ -924,32 +858,32 @@ namespace std {
924
  ```
925
 
926
  #### Constructors <a id="stack.cons">[[stack.cons]]</a>
927
 
928
  ``` cpp
929
- explicit stack(const Container& cont);
930
  ```
931
 
932
  *Effects:* Initializes `c` with `cont`.
933
 
934
  ``` cpp
935
- explicit stack(Container&& cont);
936
  ```
937
 
938
  *Effects:* Initializes `c` with `std::move(cont)`.
939
 
940
  ``` cpp
941
  template<class InputIterator>
942
- stack(InputIterator first, InputIterator last);
943
  ```
944
 
945
  *Effects:* Initializes `c` with `first` as the first argument and `last`
946
  as the second argument.
947
 
948
  ``` cpp
949
  template<container-compatible-range<T> R>
950
- stack(from_range_t, R&& rg);
951
  ```
952
 
953
  *Effects:* Initializes `c` with
954
  `ranges::to<Container>(std::forward<R>(rg))`.
955
 
@@ -957,132 +891,180 @@ template<container-compatible-range<T> R>
957
 
958
  If `uses_allocator_v<container_type, Alloc>` is `false` the constructors
959
  in this subclause shall not participate in overload resolution.
960
 
961
  ``` cpp
962
- template<class Alloc> explicit stack(const Alloc& a);
963
  ```
964
 
965
  *Effects:* Initializes `c` with `a`.
966
 
967
  ``` cpp
968
- template<class Alloc> stack(const container_type& cont, const Alloc& a);
969
  ```
970
 
971
  *Effects:* Initializes `c` with `cont` as the first argument and `a` as
972
  the second argument.
973
 
974
  ``` cpp
975
- template<class Alloc> stack(container_type&& cont, const Alloc& a);
976
  ```
977
 
978
  *Effects:* Initializes `c` with `std::move(cont)` as the first argument
979
  and `a` as the second argument.
980
 
981
  ``` cpp
982
- template<class Alloc> stack(const stack& s, const Alloc& a);
983
  ```
984
 
985
  *Effects:* Initializes `c` with `s.c` as the first argument and `a` as
986
  the second argument.
987
 
988
  ``` cpp
989
- template<class Alloc> stack(stack&& s, const Alloc& a);
990
  ```
991
 
992
  *Effects:* Initializes `c` with `std::move(s.c)` as the first argument
993
  and `a` as the second argument.
994
 
995
  ``` cpp
996
  template<class InputIterator, class Alloc>
997
- stack(InputIterator first, InputIterator last, const Alloc& alloc);
998
  ```
999
 
1000
  *Effects:* Initializes `c` with `first` as the first argument, `last` as
1001
  the second argument, and `alloc` as the third argument.
1002
 
1003
  ``` cpp
1004
  template<container-compatible-range<T> R, class Alloc>
1005
- stack(from_range_t, R&& rg, const Alloc& a);
1006
  ```
1007
 
1008
  *Effects:* Initializes `c` with
1009
  `ranges::to<Container>(std::forward<R>(rg), a)`.
1010
 
1011
  #### Modifiers <a id="stack.mod">[[stack.mod]]</a>
1012
 
1013
  ``` cpp
1014
  template<container-compatible-range<T> R>
1015
- void push_range(R&& rg);
1016
  ```
1017
 
1018
  *Effects:* Equivalent to `c.append_range(std::forward<R>(rg))` if that
1019
  is a valid expression, otherwise `ranges::copy(rg, back_inserter(c))`.
1020
 
1021
  #### Operators <a id="stack.ops">[[stack.ops]]</a>
1022
 
1023
  ``` cpp
1024
  template<class T, class Container>
1025
- bool operator==(const stack<T, Container>& x, const stack<T, Container>& y);
1026
  ```
1027
 
1028
  *Returns:* `x.c == y.c`.
1029
 
1030
  ``` cpp
1031
  template<class T, class Container>
1032
- bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y);
1033
  ```
1034
 
1035
  *Returns:* `x.c != y.c`.
1036
 
1037
  ``` cpp
1038
  template<class T, class Container>
1039
- bool operator< (const stack<T, Container>& x, const stack<T, Container>& y);
1040
  ```
1041
 
1042
  *Returns:* `x.c < y.c`.
1043
 
1044
  ``` cpp
1045
  template<class T, class Container>
1046
- bool operator> (const stack<T, Container>& x, const stack<T, Container>& y);
1047
  ```
1048
 
1049
  *Returns:* `x.c > y.c`.
1050
 
1051
  ``` cpp
1052
  template<class T, class Container>
1053
- bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y);
1054
  ```
1055
 
1056
  *Returns:* `x.c <= y.c`.
1057
 
1058
  ``` cpp
1059
  template<class T, class Container>
1060
- bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y);
1061
  ```
1062
 
1063
  *Returns:* `x.c >= y.c`.
1064
 
1065
  ``` cpp
1066
  template<class T, three_way_comparable Container>
1067
- compare_three_way_result_t<Container>
1068
  operator<=>(const stack<T, Container>& x, const stack<T, Container>& y);
1069
  ```
1070
 
1071
  *Returns:* `x.c <=> y.c`.
1072
 
1073
  #### Specialized algorithms <a id="stack.special">[[stack.special]]</a>
1074
 
1075
  ``` cpp
1076
  template<class T, class Container>
1077
- void swap(stack<T, Container>& x, stack<T, Container>& y) noexcept(noexcept(x.swap(y)));
 
1078
  ```
1079
 
1080
  *Constraints:* `is_swappable_v<Container>` is `true`.
1081
 
1082
  *Effects:* As if by `x.swap(y)`.
1083
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1084
  ### Class template `flat_map` <a id="flat.map">[[flat.map]]</a>
1085
 
1086
  #### Overview <a id="flat.map.overview">[[flat.map.overview]]</a>
1087
 
1088
  A `flat_map` is a container adaptor that provides an associative
@@ -1147,14 +1129,16 @@ The program is ill-formed if `Key` is not the same type as
1147
 
1148
  The effect of calling a constructor that takes both `key_container_type`
1149
  and `mapped_container_type` arguments with containers of different sizes
1150
  is undefined.
1151
 
1152
- The effect of calling a constructor or member function that takes a
1153
- `sorted_unique_t` argument with a container, containers, or range that
1154
- is not sorted with respect to `key_comp()`, or that contains equal
1155
- elements, is undefined.
 
 
1156
 
1157
  #### Definition <a id="flat.map.defn">[[flat.map.defn]]</a>
1158
 
1159
  ``` cpp
1160
  namespace std {
@@ -1179,245 +1163,259 @@ namespace std {
1179
  using mapped_container_type = MappedContainer;
1180
 
1181
  class value_compare {
1182
  private:
1183
  key_compare comp; // exposition only
1184
- value_compare(key_compare c) : comp(c) { } // exposition only
1185
 
1186
  public:
1187
- bool operator()(const_reference x, const_reference y) const {
1188
  return comp(x.first, y.first);
1189
  }
1190
  };
1191
 
1192
  struct containers {
1193
  key_container_type keys;
1194
  mapped_container_type values;
1195
  };
1196
 
1197
- // [flat.map.cons], construct/copy/destroy
1198
- flat_map() : flat_map(key_compare()) { }
1199
 
1200
- flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
1201
- const key_compare& comp = key_compare());
1202
- template<class Allocator>
1203
- flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
1204
- const Allocator& a);
1205
- template<class Allocator>
1206
- flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
1207
- const key_compare& comp, const Allocator& a);
1208
-
1209
- flat_map(sorted_unique_t, key_container_type key_cont, mapped_container_type mapped_cont,
1210
- const key_compare& comp = key_compare());
1211
- template<class Allocator>
1212
- flat_map(sorted_unique_t, const key_container_type& key_cont,
1213
- const mapped_container_type& mapped_cont, const Allocator& a);
1214
- template<class Allocator>
1215
- flat_map(sorted_unique_t, const key_container_type& key_cont,
1216
- const mapped_container_type& mapped_cont,
1217
- const key_compare& comp, const Allocator& a);
1218
-
1219
- explicit flat_map(const key_compare& comp)
1220
  : c(), compare(comp) { }
1221
- template<class Allocator>
1222
- flat_map(const key_compare& comp, const Allocator& a);
1223
- template<class Allocator>
1224
- explicit flat_map(const Allocator& a);
 
 
 
1225
 
1226
  template<class InputIterator>
1227
- flat_map(InputIterator first, InputIterator last, const key_compare& comp = key_compare())
 
1228
  : c(), compare(comp) { insert(first, last); }
1229
- template<class InputIterator, class Allocator>
1230
- flat_map(InputIterator first, InputIterator last,
1231
- const key_compare& comp, const Allocator& a);
1232
- template<class InputIterator, class Allocator>
1233
- flat_map(InputIterator first, InputIterator last, const Allocator& a);
1234
 
1235
  template<container-compatible-range<value_type> R>
1236
- flat_map(from_range_t fr, R&& rg)
1237
- : flat_map(fr, std::forward<R>(rg), key_compare()) { }
1238
- template<container-compatible-range<value_type> R, class Allocator>
1239
- flat_map(from_range_t, R&& rg, const Allocator& a);
1240
  template<container-compatible-range<value_type> R>
1241
- flat_map(from_range_t, R&& rg, const key_compare& comp)
1242
  : flat_map(comp) { insert_range(std::forward<R>(rg)); }
1243
- template<container-compatible-range<value_type> R, class Allocator>
1244
- flat_map(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
1245
 
1246
- template<class InputIterator>
1247
- flat_map(sorted_unique_t s, InputIterator first, InputIterator last,
1248
- const key_compare& comp = key_compare())
1249
- : c(), compare(comp) { insert(s, first, last); }
1250
- template<class InputIterator, class Allocator>
1251
- flat_map(sorted_unique_t, InputIterator first, InputIterator last,
1252
- const key_compare& comp, const Allocator& a);
1253
- template<class InputIterator, class Allocator>
1254
- flat_map(sorted_unique_t, InputIterator first, InputIterator last, const Allocator& a);
1255
-
1256
- flat_map(initializer_list<value_type> il, const key_compare& comp = key_compare())
1257
  : flat_map(il.begin(), il.end(), comp) { }
1258
- template<class Allocator>
1259
- flat_map(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
1260
- template<class Allocator>
1261
- flat_map(initializer_list<value_type> il, const Allocator& a);
1262
 
1263
- flat_map(sorted_unique_t s, initializer_list<value_type> il,
1264
  const key_compare& comp = key_compare())
1265
- : flat_map(s, il.begin(), il.end(), comp) { }
1266
- template<class Allocator>
1267
- flat_map(sorted_unique_t, initializer_list<value_type> il,
1268
- const key_compare& comp, const Allocator& a);
1269
- template<class Allocator>
1270
- flat_map(sorted_unique_t, initializer_list<value_type> il, const Allocator& a);
1271
 
1272
- flat_map& operator=(initializer_list<value_type> il);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1273
 
1274
  // iterators
1275
- iterator begin() noexcept;
1276
- const_iterator begin() const noexcept;
1277
- iterator end() noexcept;
1278
- const_iterator end() const noexcept;
1279
 
1280
- reverse_iterator rbegin() noexcept;
1281
- const_reverse_iterator rbegin() const noexcept;
1282
- reverse_iterator rend() noexcept;
1283
- const_reverse_iterator rend() const noexcept;
1284
 
1285
- const_iterator cbegin() const noexcept;
1286
- const_iterator cend() const noexcept;
1287
- const_reverse_iterator crbegin() const noexcept;
1288
- const_reverse_iterator crend() const noexcept;
1289
 
1290
  // [flat.map.capacity], capacity
1291
- [[nodiscard]] bool empty() const noexcept;
1292
- size_type size() const noexcept;
1293
- size_type max_size() const noexcept;
1294
 
1295
  // [flat.map.access], element access
1296
- mapped_type& operator[](const key_type& x);
1297
- mapped_type& operator[](key_type&& x);
1298
- template<class K> mapped_type& operator[](K&& x);
1299
- mapped_type& at(const key_type& x);
1300
- const mapped_type& at(const key_type& x) const;
1301
- template<class K> mapped_type& at(const K& x);
1302
- template<class K> const mapped_type& at(const K& x) const;
1303
 
1304
  // [flat.map.modifiers], modifiers
1305
- template<class... Args> pair<iterator, bool> emplace(Args&&... args);
1306
  template<class... Args>
1307
- iterator emplace_hint(const_iterator position, Args&&... args);
1308
 
1309
- pair<iterator, bool> insert(const value_type& x)
1310
  { return emplace(x); }
1311
- pair<iterator, bool> insert(value_type&& x)
1312
  { return emplace(std::move(x)); }
1313
- iterator insert(const_iterator position, const value_type& x)
1314
  { return emplace_hint(position, x); }
1315
- iterator insert(const_iterator position, value_type&& x)
1316
  { return emplace_hint(position, std::move(x)); }
1317
 
1318
- template<class P> pair<iterator, bool> insert(P&& x);
1319
  template<class P>
1320
- iterator insert(const_iterator position, P&&);
1321
  template<class InputIterator>
1322
- void insert(InputIterator first, InputIterator last);
1323
  template<class InputIterator>
1324
- void insert(sorted_unique_t, InputIterator first, InputIterator last);
1325
  template<container-compatible-range<value_type> R>
1326
- void insert_range(R&& rg);
1327
 
1328
- void insert(initializer_list<value_type> il)
1329
  { insert(il.begin(), il.end()); }
1330
- void insert(sorted_unique_t s, initializer_list<value_type> il)
1331
- { insert(s, il.begin(), il.end()); }
1332
 
1333
- containers extract() &&;
1334
- void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);
1335
 
1336
  template<class... Args>
1337
- pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
1338
  template<class... Args>
1339
- pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
1340
  template<class K, class... Args>
1341
- pair<iterator, bool> try_emplace(K&& k, Args&&... args);
1342
  template<class... Args>
1343
- iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
1344
  template<class... Args>
1345
- iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
1346
  template<class K, class... Args>
1347
- iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
1348
  template<class M>
1349
- pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
1350
  template<class M>
1351
- pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
1352
  template<class K, class M>
1353
- pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
1354
  template<class M>
1355
- iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
1356
  template<class M>
1357
- iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
1358
  template<class K, class M>
1359
- iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
1360
 
1361
- iterator erase(iterator position);
1362
- iterator erase(const_iterator position);
1363
- size_type erase(const key_type& x);
1364
- template<class K> size_type erase(K&& x);
1365
- iterator erase(const_iterator first, const_iterator last);
1366
 
1367
- void swap(flat_map& y) noexcept;
1368
- void clear() noexcept;
1369
 
1370
  // observers
1371
- key_compare key_comp() const;
1372
- value_compare value_comp() const;
1373
 
1374
- const key_container_type& keys() const noexcept { return c.keys; }
1375
- const mapped_container_type& values() const noexcept { return c.values; }
1376
 
1377
  // map operations
1378
- iterator find(const key_type& x);
1379
- const_iterator find(const key_type& x) const;
1380
- template<class K> iterator find(const K& x);
1381
- template<class K> const_iterator find(const K& x) const;
1382
 
1383
- size_type count(const key_type& x) const;
1384
- template<class K> size_type count(const K& x) const;
1385
 
1386
- bool contains(const key_type& x) const;
1387
- template<class K> bool contains(const K& x) const;
1388
 
1389
- iterator lower_bound(const key_type& x);
1390
- const_iterator lower_bound(const key_type& x) const;
1391
- template<class K> iterator lower_bound(const K& x);
1392
- template<class K> const_iterator lower_bound(const K& x) const;
1393
 
1394
- iterator upper_bound(const key_type& x);
1395
- const_iterator upper_bound(const key_type& x) const;
1396
- template<class K> iterator upper_bound(const K& x);
1397
- template<class K> const_iterator upper_bound(const K& x) const;
1398
 
1399
- pair<iterator, iterator> equal_range(const key_type& x);
1400
- pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
1401
- template<class K> pair<iterator, iterator> equal_range(const K& x);
1402
- template<class K> pair<const_iterator, const_iterator> equal_range(const K& x) const;
 
1403
 
1404
- friend bool operator==(const flat_map& x, const flat_map& y);
1405
 
1406
- friend synth-three-way-result<value_type>
1407
  operator<=>(const flat_map& x, const flat_map& y);
1408
 
1409
- friend void swap(flat_map& x, flat_map& y) noexcept
1410
  { x.swap(y); }
1411
 
1412
  private:
1413
  containers c; // exposition only
1414
  key_compare compare; // exposition only
1415
 
1416
- struct key_equiv { // exposition only
1417
- key_equiv(key_compare c) : comp(c) { }
1418
- bool operator()(const_reference x, const_reference y) const {
1419
  return !comp(x.first, y.first) && !comp(y.first, x.first);
1420
  }
1421
  key_compare comp;
1422
  };
1423
  };
@@ -1494,162 +1492,163 @@ specified above. It has no base classes or members other than those
1494
  specified.
1495
 
1496
  #### Constructors <a id="flat.map.cons">[[flat.map.cons]]</a>
1497
 
1498
  ``` cpp
1499
- flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
1500
  const key_compare& comp = key_compare());
1501
  ```
1502
 
1503
- *Effects:* Initializes `c.keys` with `std::move(key_cont)`, `c.values`
1504
- with `std::move(mapped_cont)`, and `compare` with `comp`; sorts the
1505
- range \[`begin()`, `end()`) with respect to `value_comp()`; and finally
1506
- erases the duplicate elements as if by:
1507
 
1508
  ``` cpp
1509
- auto zv = ranges::zip_view(c.keys, c.values);
1510
- auto it = ranges::unique(zv, key_equiv(compare)).begin();
1511
  auto dist = distance(zv.begin(), it);
1512
  c.keys.erase(c.keys.begin() + dist, c.keys.end());
1513
  c.values.erase(c.values.begin() + dist, c.values.end());
1514
  ```
1515
 
1516
  *Complexity:* Linear in N if the container arguments are already sorted
1517
  with respect to `value_comp()` and otherwise N log N, where N is the
1518
  value of `key_cont.size()` before this call.
1519
 
1520
  ``` cpp
1521
- template<class Allocator>
1522
- flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
1523
- const Allocator& a);
1524
- template<class Allocator>
1525
- flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
1526
- const key_compare& comp, const Allocator& a);
1527
  ```
1528
 
1529
- *Constraints:* `uses_allocator_v<key_container_type, Allocator>` is
1530
- `true` and `uses_allocator_v<mapped_container_type, Allocator>` is
1531
- `true`.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1532
 
1533
  *Effects:* Equivalent to `flat_map(key_cont, mapped_cont)` and
1534
  `flat_map(key_cont, mapped_cont, comp)`, respectively, except that
1535
- `c.keys` and `c.values` are constructed with uses-allocator
1536
  construction [[allocator.uses.construction]].
1537
 
1538
  *Complexity:* Same as `flat_map(key_cont, mapped_cont)` and
1539
  `flat_map(key_cont, mapped_cont, comp)`, respectively.
1540
 
1541
  ``` cpp
1542
- flat_map(sorted_unique_t, key_container_type key_cont, mapped_container_type mapped_cont,
1543
- const key_compare& comp = key_compare());
1544
- ```
1545
-
1546
- *Effects:* Initializes `c.keys` with `std::move(key_cont)`, `c.values`
1547
- with `std::move(mapped_cont)`, and `compare` with `comp`.
1548
-
1549
- *Complexity:* Constant.
1550
-
1551
- ``` cpp
1552
- template<class Allocator>
1553
- flat_map(sorted_unique_t s, const key_container_type& key_cont,
1554
- const mapped_container_type& mapped_cont, const Allocator& a);
1555
- template<class Allocator>
1556
- flat_map(sorted_unique_t s, const key_container_type& key_cont,
1557
  const mapped_container_type& mapped_cont, const key_compare& comp,
1558
- const Allocator& a);
1559
  ```
1560
 
1561
- *Constraints:* `uses_allocator_v<key_container_type, Allocator>` is
1562
- `true` and `uses_allocator_v<mapped_container_type, Allocator>` is
1563
- `true`.
1564
-
1565
- *Effects:* Equivalent to `flat_map(s, key_cont, mapped_cont)` and
1566
- `flat_map(s, key_cont, mapped_cont, comp)`, respectively, except that
1567
- `c.keys` and `c.values` are constructed with uses-allocator
1568
- construction [[allocator.uses.construction]].
1569
 
1570
  *Complexity:* Linear.
1571
 
1572
  ``` cpp
1573
- template<class Allocator>
1574
- flat_map(const key_compare& comp, const Allocator& a);
1575
- template<class Allocator>
1576
- explicit flat_map(const Allocator& a);
1577
- template<class InputIterator, class Allocator>
1578
- flat_map(InputIterator first, InputIterator last, const key_compare& comp, const Allocator& a);
1579
- template<class InputIterator, class Allocator>
1580
- flat_map(InputIterator first, InputIterator last, const Allocator& a);
1581
- template<container-compatible-range<value_type> R, class Allocator>
1582
- flat_map(from_range_t, R&& rg, const Allocator& a);
1583
- template<container-compatible-range<value_type> R, class Allocator>
1584
- flat_map(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
1585
- template<class InputIterator, class Allocator>
1586
- flat_map(sorted_unique_t, InputIterator first, InputIterator last,
1587
- const key_compare& comp, const Allocator& a);
1588
- template<class InputIterator, class Allocator>
1589
- flat_map(sorted_unique_t, InputIterator first, InputIterator last, const Allocator& a);
1590
- template<class Allocator>
1591
- flat_map(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
1592
- template<class Allocator>
1593
- flat_map(initializer_list<value_type> il, const Allocator& a);
1594
- template<class Allocator>
1595
- flat_map(sorted_unique_t, initializer_list<value_type> il,
1596
- const key_compare& comp, const Allocator& a);
1597
- template<class Allocator>
1598
- flat_map(sorted_unique_t, initializer_list<value_type> il, const Allocator& a);
 
 
 
 
 
1599
  ```
1600
 
1601
- *Constraints:* `uses_allocator_v<key_container_type, Allocator>` is
1602
- `true` and `uses_allocator_v<mapped_container_type, Allocator>` is
1603
- `true`.
1604
-
1605
  *Effects:* Equivalent to the corresponding non-allocator constructors
1606
- except that `c.keys` and `c.values` are constructed with uses-allocator
1607
- construction [[allocator.uses.construction]].
1608
 
1609
  #### Capacity <a id="flat.map.capacity">[[flat.map.capacity]]</a>
1610
 
1611
  ``` cpp
1612
- size_type size() const noexcept;
1613
  ```
1614
 
1615
- *Returns:* `c.keys.size()`.
1616
 
1617
  ``` cpp
1618
- size_type max_size() const noexcept;
1619
  ```
1620
 
1621
- *Returns:* `min<size_type>(c.keys.max_size(), c.values.max_size())`.
 
1622
 
1623
  #### Access <a id="flat.map.access">[[flat.map.access]]</a>
1624
 
1625
  ``` cpp
1626
- mapped_type& operator[](const key_type& x);
1627
  ```
1628
 
1629
  *Effects:* Equivalent to: `return try_emplace(x).first->second;`
1630
 
1631
  ``` cpp
1632
- mapped_type& operator[](key_type&& x);
1633
  ```
1634
 
1635
  *Effects:* Equivalent to:
1636
  `return try_emplace(std::move(x)).first->second;`
1637
 
1638
  ``` cpp
1639
- template<class K> mapped_type& operator[](K&& x);
1640
  ```
1641
 
1642
  *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
1643
  denotes a type.
1644
 
1645
  *Effects:* Equivalent to:
1646
  `return try_emplace(std::forward<K>(x)).first->second;`
1647
 
1648
  ``` cpp
1649
- mapped_type& at(const key_type& x);
1650
- const mapped_type& at(const key_type& x) const;
1651
  ```
1652
 
1653
  *Returns:* A reference to the `mapped_type` corresponding to `x` in
1654
  `*this`.
1655
 
@@ -1657,12 +1656,12 @@ const mapped_type& at(const key_type& x) const;
1657
  is present.
1658
 
1659
  *Complexity:* Logarithmic.
1660
 
1661
  ``` cpp
1662
- template<class K> mapped_type& at(const K& x);
1663
- template<class K> const mapped_type& at(const K& x) const;
1664
  ```
1665
 
1666
  *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
1667
  denotes a type.
1668
 
@@ -1678,11 +1677,11 @@ is present.
1678
  *Complexity:* Logarithmic.
1679
 
1680
  #### Modifiers <a id="flat.map.modifiers">[[flat.map.modifiers]]</a>
1681
 
1682
  ``` cpp
1683
- template<class... Args> pair<iterator, bool> emplace(Args&&... args);
1684
  ```
1685
 
1686
  *Constraints:*
1687
  `is_constructible_v<pair<key_type, mapped_type>, Args...>` is `true`.
1688
 
@@ -1701,12 +1700,12 @@ c.values.insert(value_it, std::move(t.second));
1701
  *Returns:* The `bool` component of the returned pair is `true` if and
1702
  only if the insertion took place, and the iterator component of the pair
1703
  points to the element with key equivalent to `t.first`.
1704
 
1705
  ``` cpp
1706
- template<class P> pair<iterator, bool> insert(P&& x);
1707
- template<class P> iterator insert(const_iterator position, P&& x);
1708
  ```
1709
 
1710
  *Constraints:* `is_constructible_v<pair<key_type, mapped_type>, P>` is
1711
  `true`.
1712
 
@@ -1714,14 +1713,14 @@ template<class P> iterator insert(const_iterator position, P&& x);
1714
  `return emplace(std::forward<P>(x));`. The second form is equivalent to
1715
  `return emplace_hint(position, std::forward<P>(x));`.
1716
 
1717
  ``` cpp
1718
  template<class InputIterator>
1719
- void insert(InputIterator first, InputIterator last);
1720
  ```
1721
 
1722
- *Effects:* Adds elements to `c` as if by:
1723
 
1724
  ``` cpp
1725
  for (; first != last; ++first) {
1726
  value_type value = *first;
1727
  c.keys.insert(c.keys.end(), std::move(value.first));
@@ -1733,12 +1732,12 @@ Then, sorts the range of newly inserted elements with respect to
1733
  `value_comp()`; merges the resulting sorted range and the sorted range
1734
  of pre-existing elements into a single sorted range; and finally erases
1735
  the duplicate elements as if by:
1736
 
1737
  ``` cpp
1738
- auto zv = ranges::zip_view(c.keys, c.values);
1739
- auto it = ranges::unique(zv, key_equiv(compare)).begin();
1740
  auto dist = distance(zv.begin(), it);
1741
  c.keys.erase(c.keys.begin() + dist, c.keys.end());
1742
  c.values.erase(c.values.begin() + dist, c.values.end());
1743
  ```
1744
 
@@ -1748,46 +1747,23 @@ M is `distance(first, last)`.
1748
  *Remarks:* Since this operation performs an in-place merge, it may
1749
  allocate memory.
1750
 
1751
  ``` cpp
1752
  template<class InputIterator>
1753
- void insert(sorted_unique_t, InputIterator first, InputIterator last);
1754
  ```
1755
 
1756
- *Effects:* Adds elements to `c` as if by:
1757
-
1758
- ``` cpp
1759
- for (; first != last; ++first) {
1760
- value_type value = *first;
1761
- c.keys.insert(c.keys.end(), std::move(value.first));
1762
- c.values.insert(c.values.end(), std::move(value.second));
1763
- }
1764
- ```
1765
-
1766
- Then, merges the sorted range of newly added elements and the sorted
1767
- range of pre-existing elements into a single sorted range; and finally
1768
- erases the duplicate elements as if by:
1769
-
1770
- ``` cpp
1771
- auto zv = ranges::zip_view(c.keys, c.values);
1772
- auto it = ranges::unique(zv, key_equiv(compare)).begin();
1773
- auto dist = distance(zv.begin(), it);
1774
- c.keys.erase(c.keys.begin() + dist, c.keys.end());
1775
- c.values.erase(c.values.begin() + dist, c.values.end());
1776
- ```
1777
 
1778
  *Complexity:* Linear in N, where N is `size()` after the operation.
1779
 
1780
- *Remarks:* Since this operation performs an in-place merge, it may
1781
- allocate memory.
1782
-
1783
  ``` cpp
1784
  template<container-compatible-range<value_type> R>
1785
- void insert_range(R&& rg);
1786
  ```
1787
 
1788
- *Effects:* Adds elements to `c` as if by:
1789
 
1790
  ``` cpp
1791
  for (const auto& e : rg) {
1792
  c.keys.insert(c.keys.end(), e.first);
1793
  c.values.insert(c.values.end(), e.second);
@@ -1798,12 +1774,12 @@ Then, sorts the range of newly inserted elements with respect to
1798
  `value_comp()`; merges the resulting sorted range and the sorted range
1799
  of pre-existing elements into a single sorted range; and finally erases
1800
  the duplicate elements as if by:
1801
 
1802
  ``` cpp
1803
- auto zv = ranges::zip_view(c.keys, c.values);
1804
- auto it = ranges::unique(zv, key_equiv(compare)).begin();
1805
  auto dist = distance(zv.begin(), it);
1806
  c.keys.erase(c.keys.begin() + dist, c.keys.end());
1807
  c.values.erase(c.values.begin() + dist, c.values.end());
1808
  ```
1809
 
@@ -1813,17 +1789,17 @@ M is `ranges::distance(rg)`.
1813
  *Remarks:* Since this operation performs an in-place merge, it may
1814
  allocate memory.
1815
 
1816
  ``` cpp
1817
  template<class... Args>
1818
- pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
1819
  template<class... Args>
1820
- pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
1821
  template<class... Args>
1822
- iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
1823
  template<class... Args>
1824
- iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
1825
  ```
1826
 
1827
  *Constraints:* `is_constructible_v<mapped_type, Args...>` is `true`.
1828
 
1829
  *Effects:* If the map already contains an element whose key is
@@ -1845,13 +1821,13 @@ returned iterator points to the map element whose key is equivalent to
1845
  *Complexity:* The same as `emplace` for the first two overloads, and the
1846
  same as `emplace_hint` for the last two overloads.
1847
 
1848
  ``` cpp
1849
  template<class K, class... Args>
1850
- pair<iterator, bool> try_emplace(K&& k, Args&&... args);
1851
  template<class K, class... Args>
1852
- iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
1853
  ```
1854
 
1855
  *Constraints:*
1856
 
1857
  - The *qualified-id* `Compare::is_transparent` is valid and denotes a
@@ -1867,11 +1843,11 @@ object `u`, for which `find(k) == find(u)` is `true`.
1867
  *Effects:* If the map already contains an element whose key is
1868
  equivalent to `k`, `*this` and `args...` are unchanged. Otherwise
1869
  equivalent to:
1870
 
1871
  ``` cpp
1872
- auto key_it = ranges::upper_bound(c.keys, k, compare);
1873
  auto value_it = c.values.begin() + distance(c.keys.begin(), key_it);
1874
  c.keys.emplace(key_it, std::forward<K>(k));
1875
  c.values.emplace(value_it, std::forward<Args>(args)...);
1876
  ```
1877
 
@@ -1881,17 +1857,17 @@ iterator points to the map element whose key is equivalent to `k`.
1881
 
1882
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
1883
 
1884
  ``` cpp
1885
  template<class M>
1886
- pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
1887
  template<class M>
1888
- pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
1889
  template<class M>
1890
- iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
1891
  template<class M>
1892
- iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
1893
  ```
1894
 
1895
  *Constraints:* `is_assignable_v<mapped_type&, M>` is `true` and
1896
  `is_constructible_v<mapped_type, M>` is `true`.
1897
 
@@ -1919,13 +1895,13 @@ returned iterator points to the map element whose key is equivalent to
1919
  *Complexity:* The same as `emplace` for the first two overloads and the
1920
  same as `emplace_hint` for the last two overloads.
1921
 
1922
  ``` cpp
1923
  template<class K, class M>
1924
- pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
1925
  template<class K, class M>
1926
- iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
1927
  ```
1928
 
1929
  *Constraints:*
1930
 
1931
  - The *qualified-id* `Compare::is_transparent` is valid and denotes a
@@ -1958,11 +1934,11 @@ pair is `true` if and only if the insertion took place. The returned
1958
  iterator points to the map element whose key is equivalent to `k`.
1959
 
1960
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
1961
 
1962
  ``` cpp
1963
- void swap(flat_map& y) noexcept;
1964
  ```
1965
 
1966
  *Effects:* Equivalent to:
1967
 
1968
  ``` cpp
@@ -1970,24 +1946,24 @@ ranges::swap(compare, y.compare);
1970
  ranges::swap(c.keys, y.c.keys);
1971
  ranges::swap(c.values, y.c.values);
1972
  ```
1973
 
1974
  ``` cpp
1975
- containers extract() &&;
1976
  ```
1977
 
1978
  *Ensures:* `*this` is emptied, even if the function exits via an
1979
  exception.
1980
 
1981
- *Returns:* `std::move(c)`.
1982
 
1983
  ``` cpp
1984
- void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);
1985
  ```
1986
 
1987
  *Preconditions:* `key_cont.size() == mapped_cont.size()` is `true`, the
1988
- elements of `key_cont` are sorted with respect to `compare`, and
1989
  `key_cont` contains no equal elements.
1990
 
1991
  *Effects:* Equivalent to:
1992
 
1993
  ``` cpp
@@ -1998,11 +1974,11 @@ c.values = std::move(mapped_cont);
1998
  #### Erasure <a id="flat.map.erasure">[[flat.map.erasure]]</a>
1999
 
2000
  ``` cpp
2001
  template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
2002
  class Predicate>
2003
- typename flat_map<Key, T, Compare, KeyContainer, MappedContainer>::size_type
2004
  erase_if(flat_map<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
2005
  ```
2006
 
2007
  *Preconditions:* `Key` and `T` meet the *Cpp17MoveAssignable*
2008
  requirements.
@@ -2092,14 +2068,17 @@ The program is ill-formed if `Key` is not the same type as
2092
 
2093
  The effect of calling a constructor that takes both `key_container_type`
2094
  and `mapped_container_type` arguments with containers of different sizes
2095
  is undefined.
2096
 
2097
- The effect of calling a constructor or member function that takes a
2098
  `sorted_equivalent_t` argument with a container, containers, or range
2099
  that are not sorted with respect to `key_comp()` is undefined.
2100
 
 
 
 
2101
  #### Definition <a id="flat.multimap.defn">[[flat.multimap.defn]]</a>
2102
 
2103
  ``` cpp
2104
  namespace std {
2105
  template<class Key, class T, class Compare = less<Key>,
@@ -2123,209 +2102,219 @@ namespace std {
2123
  using mapped_container_type = MappedContainer;
2124
 
2125
  class value_compare {
2126
  private:
2127
  key_compare comp; // exposition only
2128
- value_compare(key_compare c) : comp(c) { } // exposition only
2129
 
2130
  public:
2131
- bool operator()(const_reference x, const_reference y) const {
2132
  return comp(x.first, y.first);
2133
  }
2134
  };
2135
 
2136
  struct containers {
2137
  key_container_type keys;
2138
  mapped_container_type values;
2139
  };
2140
 
2141
- // [flat.multimap.cons], construct/copy/destroy
2142
- flat_multimap() : flat_multimap(key_compare()) { }
2143
 
2144
- flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,
 
 
 
2145
  const key_compare& comp = key_compare());
2146
- template<class Allocator>
2147
- flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
2148
- const Allocator& a);
2149
- template<class Allocator>
2150
- flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
2151
- const key_compare& comp, const Allocator& a);
2152
 
2153
- flat_multimap(sorted_equivalent_t,
2154
  key_container_type key_cont, mapped_container_type mapped_cont,
2155
  const key_compare& comp = key_compare());
2156
- template<class Allocator>
2157
- flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
2158
- const mapped_container_type& mapped_cont, const Allocator& a);
2159
- template<class Allocator>
2160
- flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
2161
- const mapped_container_type& mapped_cont,
2162
- const key_compare& comp, const Allocator& a);
2163
-
2164
- explicit flat_multimap(const key_compare& comp)
2165
- : c(), compare(comp) { }
2166
- template<class Allocator>
2167
- flat_multimap(const key_compare& comp, const Allocator& a);
2168
- template<class Allocator>
2169
- explicit flat_multimap(const Allocator& a);
2170
 
2171
  template<class InputIterator>
2172
- flat_multimap(InputIterator first, InputIterator last,
2173
  const key_compare& comp = key_compare())
2174
  : c(), compare(comp)
2175
  { insert(first, last); }
2176
- template<class InputIterator, class Allocator>
2177
- flat_multimap(InputIterator first, InputIterator last,
2178
- const key_compare& comp, const Allocator& a);
2179
- template<class InputIterator, class Allocator>
2180
- flat_multimap(InputIterator first, InputIterator last, const Allocator& a);
2181
 
2182
  template<container-compatible-range<value_type> R>
2183
- flat_multimap(from_range_t fr, R&& rg)
2184
- : flat_multimap(fr, std::forward<R>(rg), key_compare()) { }
2185
- template<container-compatible-range<value_type> R, class Allocator>
2186
- flat_multimap(from_range_t, R&& rg, const Allocator& a);
2187
  template<container-compatible-range<value_type> R>
2188
- flat_multimap(from_range_t, R&& rg, const key_compare& comp)
2189
  : flat_multimap(comp) { insert_range(std::forward<R>(rg)); }
2190
- template<container-compatible-range<value_type> R, class Allocator>
2191
- flat_multimap(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
2192
 
2193
- template<class InputIterator>
2194
- flat_multimap(sorted_equivalent_t s, InputIterator first, InputIterator last,
2195
  const key_compare& comp = key_compare())
2196
- : c(), compare(comp) { insert(s, first, last); }
2197
- template<class InputIterator, class Allocator>
2198
- flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
2199
- const key_compare& comp, const Allocator& a);
2200
- template<class InputIterator, class Allocator>
2201
- flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
2202
- const Allocator& a);
2203
-
2204
- flat_multimap(initializer_list<value_type> il, const key_compare& comp = key_compare())
2205
  : flat_multimap(il.begin(), il.end(), comp) { }
2206
- template<class Allocator>
2207
- flat_multimap(initializer_list<value_type> il, const key_compare& comp,
2208
- const Allocator& a);
2209
- template<class Allocator>
2210
- flat_multimap(initializer_list<value_type> il, const Allocator& a);
2211
 
2212
- flat_multimap(sorted_equivalent_t s, initializer_list<value_type> il,
2213
  const key_compare& comp = key_compare())
2214
- : flat_multimap(s, il.begin(), il.end(), comp) { }
2215
- template<class Allocator>
2216
- flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
2217
- const key_compare& comp, const Allocator& a);
2218
- template<class Allocator>
2219
- flat_multimap(sorted_equivalent_t, initializer_list<value_type> il, const Allocator& a);
2220
 
2221
- flat_multimap& operator=(initializer_list<value_type> il);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2222
 
2223
  // iterators
2224
- iterator begin() noexcept;
2225
- const_iterator begin() const noexcept;
2226
- iterator end() noexcept;
2227
- const_iterator end() const noexcept;
2228
 
2229
- reverse_iterator rbegin() noexcept;
2230
- const_reverse_iterator rbegin() const noexcept;
2231
- reverse_iterator rend() noexcept;
2232
- const_reverse_iterator rend() const noexcept;
2233
 
2234
- const_iterator cbegin() const noexcept;
2235
- const_iterator cend() const noexcept;
2236
- const_reverse_iterator crbegin() const noexcept;
2237
- const_reverse_iterator crend() const noexcept;
2238
 
2239
  // capacity
2240
- [[nodiscard]] bool empty() const noexcept;
2241
- size_type size() const noexcept;
2242
- size_type max_size() const noexcept;
2243
 
2244
  // modifiers
2245
- template<class... Args> iterator emplace(Args&&... args);
2246
  template<class... Args>
2247
- iterator emplace_hint(const_iterator position, Args&&... args);
2248
 
2249
- iterator insert(const value_type& x)
2250
  { return emplace(x); }
2251
- iterator insert(value_type&& x)
2252
  { return emplace(std::move(x)); }
2253
- iterator insert(const_iterator position, const value_type& x)
2254
  { return emplace_hint(position, x); }
2255
- iterator insert(const_iterator position, value_type&& x)
2256
  { return emplace_hint(position, std::move(x)); }
2257
 
2258
- template<class P> iterator insert(P&& x);
2259
  template<class P>
2260
- iterator insert(const_iterator position, P&&);
2261
  template<class InputIterator>
2262
- void insert(InputIterator first, InputIterator last);
2263
  template<class InputIterator>
2264
- void insert(sorted_equivalent_t, InputIterator first, InputIterator last);
2265
  template<container-compatible-range<value_type> R>
2266
- void insert_range(R&& rg);
2267
 
2268
- void insert(initializer_list<value_type> il)
2269
  { insert(il.begin(), il.end()); }
2270
- void insert(sorted_equivalent_t s, initializer_list<value_type> il)
2271
- { insert(s, il.begin(), il.end()); }
2272
 
2273
- containers extract() &&;
2274
- void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);
2275
 
2276
- iterator erase(iterator position);
2277
- iterator erase(const_iterator position);
2278
- size_type erase(const key_type& x);
2279
- template<class K> size_type erase(K&& x);
2280
- iterator erase(const_iterator first, const_iterator last);
2281
 
2282
- void swap(flat_multimap&) noexcept;
2283
- void clear() noexcept;
2284
 
2285
  // observers
2286
- key_compare key_comp() const;
2287
- value_compare value_comp() const;
2288
 
2289
- const key_container_type& keys() const noexcept { return c.keys; }
2290
- const mapped_container_type& values() const noexcept { return c.values; }
2291
 
2292
  // map operations
2293
- iterator find(const key_type& x);
2294
- const_iterator find(const key_type& x) const;
2295
- template<class K> iterator find(const K& x);
2296
- template<class K> const_iterator find(const K& x) const;
2297
 
2298
- size_type count(const key_type& x) const;
2299
- template<class K> size_type count(const K& x) const;
2300
 
2301
- bool contains(const key_type& x) const;
2302
- template<class K> bool contains(const K& x) const;
2303
 
2304
- iterator lower_bound(const key_type& x);
2305
- const_iterator lower_bound(const key_type& x) const;
2306
- template<class K> iterator lower_bound(const K& x);
2307
- template<class K> const_iterator lower_bound(const K& x) const;
2308
 
2309
- iterator upper_bound(const key_type& x);
2310
- const_iterator upper_bound(const key_type& x) const;
2311
- template<class K> iterator upper_bound(const K& x);
2312
- template<class K> const_iterator upper_bound(const K& x) const;
2313
 
2314
- pair<iterator, iterator> equal_range(const key_type& x);
2315
- pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
2316
  template<class K>
2317
- pair<iterator, iterator> equal_range(const K& x);
2318
  template<class K>
2319
- pair<const_iterator, const_iterator> equal_range(const K& x) const;
2320
 
2321
- friend bool operator==(const flat_multimap& x, const flat_multimap& y);
2322
 
2323
- friend synth-three-way-result<value_type>
2324
  operator<=>(const flat_multimap& x, const flat_multimap& y);
2325
 
2326
- friend void swap(flat_multimap& x, flat_multimap& y) noexcept
2327
  { x.swap(y); }
2328
 
2329
  private:
2330
  containers c; // exposition only
2331
  key_compare compare; // exposition only
@@ -2408,119 +2397,122 @@ specified above. It has no base classes or members other than those
2408
  specified.
2409
 
2410
  #### Constructors <a id="flat.multimap.cons">[[flat.multimap.cons]]</a>
2411
 
2412
  ``` cpp
2413
- flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,
2414
  const key_compare& comp = key_compare());
2415
  ```
2416
 
2417
- *Effects:* Initializes `c.keys` with `std::move(key_cont)`, `c.values`
2418
- with `std::move(mapped_cont)`, and `compare` with `comp`; sorts the
2419
- range \[`begin()`, `end()`) with respect to `value_comp()`.
2420
 
2421
  *Complexity:* Linear in N if the container arguments are already sorted
2422
  with respect to `value_comp()` and otherwise N log N, where N is the
2423
  value of `key_cont.size()` before this call.
2424
 
2425
  ``` cpp
2426
- template<class Allocator>
2427
- flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
2428
- const Allocator& a);
2429
- template<class Allocator>
2430
- flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
2431
- const key_compare& comp, const Allocator& a);
2432
  ```
2433
 
2434
- *Constraints:* `uses_allocator_v<key_container_type, Allocator>` is
2435
- `true` and `uses_allocator_v<mapped_container_type, Allocator>` is
2436
- `true`.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2437
 
2438
  *Effects:* Equivalent to `flat_multimap(key_cont, mapped_cont)` and
2439
  `flat_multimap(key_cont, mapped_cont, comp)`, respectively, except that
2440
- `c.keys` and `c.values` are constructed with uses-allocator
2441
  construction [[allocator.uses.construction]].
2442
 
2443
  *Complexity:* Same as `flat_multimap(key_cont, mapped_cont)` and
2444
  `flat_multimap(key_cont, mapped_cont, comp)`, respectively.
2445
 
2446
  ``` cpp
2447
- flat_multimap(sorted_equivalent_t, key_container_type key_cont, mapped_container_type mapped_cont,
2448
- const key_compare& comp = key_compare());
2449
- ```
2450
-
2451
- *Effects:* Initializes `c.keys` with `std::move(key_cont)`, `c.values`
2452
- with `std::move(mapped_cont)`, and `compare` with `comp`.
2453
-
2454
- *Complexity:* Constant.
2455
-
2456
- ``` cpp
2457
- template<class Allocator>
2458
- flat_multimap(sorted_equivalent_t s, const key_container_type& key_cont,
2459
- const mapped_container_type& mapped_cont, const Allocator& a);
2460
- template<class Allocator>
2461
- flat_multimap(sorted_equivalent_t s, const key_container_type& key_cont,
2462
  const mapped_container_type& mapped_cont, const key_compare& comp,
2463
- const Allocator& a);
2464
  ```
2465
 
2466
- *Constraints:* `uses_allocator_v<key_container_type, Allocator>` is
2467
- `true` and `uses_allocator_v<mapped_container_type, Allocator>` is
2468
- `true`.
2469
-
2470
- *Effects:* Equivalent to `flat_multimap(s, key_cont, mapped_cont)` and
2471
- `flat_multimap(s, key_cont, mapped_cont, comp)`, respectively, except
2472
- that `c.keys` and `c.values` are constructed with uses-allocator
2473
  construction [[allocator.uses.construction]].
2474
 
2475
  *Complexity:* Linear.
2476
 
2477
  ``` cpp
2478
- template<class Allocator>
2479
- flat_multimap(const key_compare& comp, const Allocator& a);
2480
- template<class Allocator>
2481
- explicit flat_multimap(const Allocator& a);
2482
- template<class InputIterator, class Allocator>
2483
- flat_multimap(InputIterator first, InputIterator last, const key_compare& comp,
2484
- const Allocator& a);
2485
- template<class InputIterator, class Allocator>
2486
- flat_multimap(InputIterator first, InputIterator last, const Allocator& a);
2487
- template<container-compatible-range<value_type> R, class Allocator>
2488
- flat_multimap(from_range_t, R&& rg, const Allocator& a);
2489
- template<container-compatible-range<value_type> R, class Allocator>
2490
- flat_multimap(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
2491
- template<class InputIterator, class Allocator>
2492
- flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
2493
- const key_compare& comp, const Allocator& a);
2494
- template<class InputIterator, class Allocator>
2495
- flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
2496
- const Allocator& a);
2497
- template<class Allocator>
2498
- flat_multimap(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
2499
- template<class Allocator>
2500
- flat_multimap(initializer_list<value_type> il, const Allocator& a);
2501
- template<class Allocator>
2502
- flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
2503
- const key_compare& comp, const Allocator& a);
2504
- template<class Allocator>
2505
- flat_multimap(sorted_equivalent_t, initializer_list<value_type> il, const Allocator& a);
 
 
 
 
 
2506
  ```
2507
 
2508
- *Constraints:* `uses_allocator_v<key_container_type, Allocator>` is
2509
- `true` and `uses_allocator_v<mapped_container_type, Allocator>` is
2510
- `true`.
2511
-
2512
  *Effects:* Equivalent to the corresponding non-allocator constructors
2513
- except that `c.keys` and `c.values` are constructed with uses-allocator
2514
- construction [[allocator.uses.construction]].
2515
 
2516
  #### Erasure <a id="flat.multimap.erasure">[[flat.multimap.erasure]]</a>
2517
 
2518
  ``` cpp
2519
  template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
2520
  class Predicate>
2521
- typename flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>::size_type
2522
  erase_if(flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
2523
  ```
2524
 
2525
  *Preconditions:* `Key` and `T` meet the *Cpp17MoveAssignable*
2526
  requirements.
@@ -2537,10 +2529,49 @@ exits via an exception, `c` is in a valid but unspecified
2537
  state [[defns.valid]].
2538
 
2539
  [*Note 1*: `c` still meets its invariants, but can be
2540
  empty. — *end note*]
2541
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2542
  ### Class template `flat_set` <a id="flat.set">[[flat.set]]</a>
2543
 
2544
  #### Overview <a id="flat.set.overview">[[flat.set.overview]]</a>
2545
 
2546
  A `flat_set` is a container adaptor that provides an associative
@@ -2593,13 +2624,16 @@ particular, `vector` [[vector]] and `deque` [[deque]] can be used.
2593
  [*Note 3*: `vector<bool>` is not a sequence container. — *end note*]
2594
 
2595
  The program is ill-formed if `Key` is not the same type as
2596
  `KeyContainer::value_type`.
2597
 
2598
- The effect of calling a constructor or member function that takes a
2599
- `sorted_unique_t` argument with a range that is not sorted with respect
2600
- to `key_comp()`, or that contains equal elements, is undefined.
 
 
 
2601
 
2602
  #### Definition <a id="flat.set.defn">[[flat.set.defn]]</a>
2603
 
2604
  ``` cpp
2605
  namespace std {
@@ -2611,192 +2645,203 @@ namespace std {
2611
  using value_type = Key;
2612
  using key_compare = Compare;
2613
  using value_compare = Compare;
2614
  using reference = value_type&;
2615
  using const_reference = const value_type&;
2616
- using size_type = typename KeyContainer::size_type;
2617
- using difference_type = typename KeyContainer::difference_type;
2618
  using iterator = implementation-defined // type of flat_set::iterator; // see [container.requirements]
2619
  using const_iterator = implementation-defined // type of flat_set::const_iterator; // see [container.requirements]
2620
  using reverse_iterator = std::reverse_iterator<iterator>;
2621
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
2622
  using container_type = KeyContainer;
2623
 
2624
  // [flat.set.cons], constructors
2625
- flat_set() : flat_set(key_compare()) { }
2626
 
2627
- explicit flat_set(container_type cont, const key_compare& comp = key_compare());
2628
- template<class Allocator>
2629
- flat_set(const container_type& cont, const Allocator& a);
2630
- template<class Allocator>
2631
- flat_set(const container_type& cont, const key_compare& comp, const Allocator& a);
2632
-
2633
- flat_set(sorted_unique_t, container_type cont, const key_compare& comp = key_compare())
2634
- : c(std::move(cont)), compare(comp) { }
2635
- template<class Allocator>
2636
- flat_set(sorted_unique_t, const container_type& cont, const Allocator& a);
2637
- template<class Allocator>
2638
- flat_set(sorted_unique_t, const container_type& cont,
2639
- const key_compare& comp, const Allocator& a);
2640
-
2641
- explicit flat_set(const key_compare& comp)
2642
  : c(), compare(comp) { }
2643
- template<class Allocator>
2644
- flat_set(const key_compare& comp, const Allocator& a);
2645
- template<class Allocator>
2646
- explicit flat_set(const Allocator& a);
 
 
2647
 
2648
  template<class InputIterator>
2649
- flat_set(InputIterator first, InputIterator last, const key_compare& comp = key_compare())
 
2650
  : c(), compare(comp)
2651
  { insert(first, last); }
2652
- template<class InputIterator, class Allocator>
2653
- flat_set(InputIterator first, InputIterator last,
2654
- const key_compare& comp, const Allocator& a);
2655
- template<class InputIterator, class Allocator>
2656
- flat_set(InputIterator first, InputIterator last, const Allocator& a);
2657
 
2658
  template<container-compatible-range<value_type> R>
2659
- flat_set(from_range_t fr, R&& rg)
2660
- : flat_set(fr, std::forward<R>(rg), key_compare()) { }
2661
- template<container-compatible-range<value_type> R, class Allocator>
2662
- flat_set(from_range_t, R&& rg, const Allocator& a);
2663
  template<container-compatible-range<value_type> R>
2664
- flat_set(from_range_t, R&& rg, const key_compare& comp)
2665
  : flat_set(comp)
2666
  { insert_range(std::forward<R>(rg)); }
2667
- template<container-compatible-range<value_type> R, class Allocator>
2668
- flat_set(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
2669
 
2670
- template<class InputIterator>
2671
- flat_set(sorted_unique_t, InputIterator first, InputIterator last,
2672
- const key_compare& comp = key_compare())
2673
- : c(first, last), compare(comp) { }
2674
- template<class InputIterator, class Allocator>
2675
- flat_set(sorted_unique_t, InputIterator first, InputIterator last,
2676
- const key_compare& comp, const Allocator& a);
2677
- template<class InputIterator, class Allocator>
2678
- flat_set(sorted_unique_t, InputIterator first, InputIterator last, const Allocator& a);
2679
-
2680
- flat_set(initializer_list<value_type> il, const key_compare& comp = key_compare())
2681
  : flat_set(il.begin(), il.end(), comp) { }
2682
- template<class Allocator>
2683
- flat_set(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
2684
- template<class Allocator>
2685
- flat_set(initializer_list<value_type> il, const Allocator& a);
2686
 
2687
- flat_set(sorted_unique_t s, initializer_list<value_type> il,
2688
  const key_compare& comp = key_compare())
2689
- : flat_set(s, il.begin(), il.end(), comp) { }
2690
- template<class Allocator>
2691
- flat_set(sorted_unique_t, initializer_list<value_type> il,
2692
- const key_compare& comp, const Allocator& a);
2693
- template<class Allocator>
2694
- flat_set(sorted_unique_t, initializer_list<value_type> il, const Allocator& a);
2695
 
2696
- flat_set& operator=(initializer_list<value_type>);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2697
 
2698
  // iterators
2699
- iterator begin() noexcept;
2700
- const_iterator begin() const noexcept;
2701
- iterator end() noexcept;
2702
- const_iterator end() const noexcept;
2703
 
2704
- reverse_iterator rbegin() noexcept;
2705
- const_reverse_iterator rbegin() const noexcept;
2706
- reverse_iterator rend() noexcept;
2707
- const_reverse_iterator rend() const noexcept;
2708
 
2709
- const_iterator cbegin() const noexcept;
2710
- const_iterator cend() const noexcept;
2711
- const_reverse_iterator crbegin() const noexcept;
2712
- const_reverse_iterator crend() const noexcept;
2713
 
2714
  // capacity
2715
- [[nodiscard]] bool empty() const noexcept;
2716
- size_type size() const noexcept;
2717
- size_type max_size() const noexcept;
2718
 
2719
  // [flat.set.modifiers], modifiers
2720
- template<class... Args> pair<iterator, bool> emplace(Args&&... args);
2721
  template<class... Args>
2722
- iterator emplace_hint(const_iterator position, Args&&... args);
2723
 
2724
- pair<iterator, bool> insert(const value_type& x)
2725
  { return emplace(x); }
2726
- pair<iterator, bool> insert(value_type&& x)
2727
  { return emplace(std::move(x)); }
2728
- template<class K> pair<iterator, bool> insert(K&& x);
2729
- iterator insert(const_iterator position, const value_type& x)
2730
  { return emplace_hint(position, x); }
2731
- iterator insert(const_iterator position, value_type&& x)
2732
  { return emplace_hint(position, std::move(x)); }
2733
- template<class K> iterator insert(const_iterator hint, K&& x);
2734
 
2735
  template<class InputIterator>
2736
- void insert(InputIterator first, InputIterator last);
2737
  template<class InputIterator>
2738
- void insert(sorted_unique_t, InputIterator first, InputIterator last);
2739
  template<container-compatible-range<value_type> R>
2740
- void insert_range(R&& rg);
2741
 
2742
- void insert(initializer_list<value_type> il)
2743
  { insert(il.begin(), il.end()); }
2744
- void insert(sorted_unique_t s, initializer_list<value_type> il)
2745
- { insert(s, il.begin(), il.end()); }
2746
 
2747
- container_type extract() &&;
2748
- void replace(container_type&&);
2749
 
2750
- iterator erase(iterator position);
2751
- iterator erase(const_iterator position);
2752
- size_type erase(const key_type& x);
2753
- template<class K> size_type erase(K&& x);
2754
- iterator erase(const_iterator first, const_iterator last);
2755
 
2756
- void swap(flat_set& y) noexcept;
2757
- void clear() noexcept;
2758
 
2759
  // observers
2760
- key_compare key_comp() const;
2761
- value_compare value_comp() const;
2762
 
2763
  // set operations
2764
- iterator find(const key_type& x);
2765
- const_iterator find(const key_type& x) const;
2766
- template<class K> iterator find(const K& x);
2767
- template<class K> const_iterator find(const K& x) const;
2768
 
2769
- size_type count(const key_type& x) const;
2770
- template<class K> size_type count(const K& x) const;
2771
 
2772
- bool contains(const key_type& x) const;
2773
- template<class K> bool contains(const K& x) const;
2774
 
2775
- iterator lower_bound(const key_type& x);
2776
- const_iterator lower_bound(const key_type& x) const;
2777
- template<class K> iterator lower_bound(const K& x);
2778
- template<class K> const_iterator lower_bound(const K& x) const;
2779
 
2780
- iterator upper_bound(const key_type& x);
2781
- const_iterator upper_bound(const key_type& x) const;
2782
- template<class K> iterator upper_bound(const K& x);
2783
- template<class K> const_iterator upper_bound(const K& x) const;
2784
 
2785
- pair<iterator, iterator> equal_range(const key_type& x);
2786
- pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
2787
  template<class K>
2788
- pair<iterator, iterator> equal_range(const K& x);
2789
  template<class K>
2790
- pair<const_iterator, const_iterator> equal_range(const K& x) const;
2791
 
2792
- friend bool operator==(const flat_set& x, const flat_set& y);
2793
 
2794
- friend synth-three-way-result<value_type>
2795
  operator<=>(const flat_set& x, const flat_set& y);
2796
 
2797
- friend void swap(flat_set& x, flat_set& y) noexcept { x.swap(y); }
2798
 
2799
  private:
2800
  container_type c; // exposition only
2801
  key_compare compare; // exposition only
2802
  };
@@ -2859,101 +2904,106 @@ namespace std {
2859
  ```
2860
 
2861
  #### Constructors <a id="flat.set.cons">[[flat.set.cons]]</a>
2862
 
2863
  ``` cpp
2864
- explicit flat_set(container_type cont, const key_compare& comp = key_compare());
2865
  ```
2866
 
2867
  *Effects:* Initializes *c* with `std::move(cont)` and *compare* with
2868
  `comp`, sorts the range \[`begin()`, `end()`) with respect to *compare*,
2869
  and finally erases all but the first element from each group of
2870
  consecutive equivalent elements.
2871
 
2872
- *Complexity:* Linear in N if `cont` is sorted with respect to *compare*
2873
- and otherwise N log N, where N is the value of `cont.size()` before this
2874
- call.
 
 
 
 
 
2875
 
2876
  ``` cpp
2877
- template<class Allocator>
2878
- flat_set(const container_type& cont, const Allocator& a);
2879
- template<class Allocator>
2880
- flat_set(const container_type& cont, const key_compare& comp, const Allocator& a);
2881
  ```
2882
 
2883
- *Constraints:* `uses_allocator_v<container_type, Allocator>` is `true`.
2884
-
2885
  *Effects:* Equivalent to `flat_set(cont)` and `flat_set(cont, comp)`,
2886
  respectively, except that *c* is constructed with uses-allocator
2887
  construction [[allocator.uses.construction]].
2888
 
2889
  *Complexity:* Same as `flat_set(cont)` and `flat_set(cont, comp)`,
2890
  respectively.
2891
 
2892
  ``` cpp
2893
- template<class Allocator>
2894
- flat_set(sorted_unique_t s, const container_type& cont, const Allocator& a);
2895
- template<class Allocator>
2896
- flat_set(sorted_unique_t s, const container_type& cont,
2897
- const key_compare& comp, const Allocator& a);
2898
  ```
2899
 
2900
- *Constraints:* `uses_allocator_v<container_type, Allocator>` is `true`.
2901
-
2902
- *Effects:* Equivalent to `flat_set(s, cont)` and
2903
- `flat_set(s, cont, comp)`, respectively, except that *c* is constructed
2904
- with uses-allocator construction [[allocator.uses.construction]].
2905
 
2906
  *Complexity:* Linear.
2907
 
2908
  ``` cpp
2909
- template<class Allocator>
2910
- flat_set(const key_compare& comp, const Allocator& a);
2911
- template<class Allocator>
2912
- explicit flat_set(const Allocator& a);
2913
- template<class InputIterator, class Allocator>
2914
- flat_set(InputIterator first, InputIterator last, const key_compare& comp, const Allocator& a);
2915
- template<class InputIterator, class Allocator>
2916
- flat_set(InputIterator first, InputIterator last, const Allocator& a);
2917
- template<container-compatible-range<value_type> R, class Allocator>
2918
- flat_set(from_range_t, R&& rg, const Allocator& a);
2919
- template<container-compatible-range<value_type> R, class Allocator>
2920
- flat_set(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
2921
- template<class InputIterator, class Allocator>
2922
- flat_set(sorted_unique_t, InputIterator first, InputIterator last,
2923
- const key_compare& comp, const Allocator& a);
2924
- template<class InputIterator, class Allocator>
2925
- flat_set(sorted_unique_t, InputIterator first, InputIterator last, const Allocator& a);
2926
- template<class Allocator>
2927
- flat_set(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
2928
- template<class Allocator>
2929
- flat_set(initializer_list<value_type> il, const Allocator& a);
2930
- template<class Allocator>
2931
- flat_set(sorted_unique_t, initializer_list<value_type> il,
2932
- const key_compare& comp, const Allocator& a);
2933
- template<class Allocator>
2934
- flat_set(sorted_unique_t, initializer_list<value_type> il, const Allocator& a);
 
 
 
 
 
2935
  ```
2936
 
2937
- *Constraints:* `uses_allocator_v<container_type, Allocator>` is `true`.
2938
-
2939
  *Effects:* Equivalent to the corresponding non-allocator constructors
2940
  except that *c* is constructed with uses-allocator
2941
  construction [[allocator.uses.construction]].
2942
 
2943
  #### Modifiers <a id="flat.set.modifiers">[[flat.set.modifiers]]</a>
2944
 
2945
  ``` cpp
2946
- template<class K> pair<iterator, bool> insert(K&& x);
2947
- template<class K> iterator insert(const_iterator hint, K&& x);
2948
  ```
2949
 
2950
  *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
2951
  denotes a type. `is_constructible_v<value_type, K>` is `true`.
2952
 
2953
  *Preconditions:* The conversion from `x` into `value_type` constructs an
2954
- object `u`, for which `find(x) == find(u)` is true.
2955
 
2956
  *Effects:* If the set already contains an element equivalent to `x`,
2957
  `*this` and `x` are unchanged. Otherwise, inserts a new element as if by
2958
  `emplace(std::forward<K>(x))`.
2959
 
@@ -2961,11 +3011,11 @@ object `u`, for which `find(x) == find(u)` is true.
2961
  pair is `true` if and only if the insertion took place. The returned
2962
  iterator points to the element whose key is equivalent to `x`.
2963
 
2964
  ``` cpp
2965
  template<class InputIterator>
2966
- void insert(InputIterator first, InputIterator last);
2967
  ```
2968
 
2969
  *Effects:* Adds elements to *c* as if by:
2970
 
2971
  ``` cpp
@@ -2984,20 +3034,20 @@ M is `distance(first, last)`.
2984
  *Remarks:* Since this operation performs an in-place merge, it may
2985
  allocate memory.
2986
 
2987
  ``` cpp
2988
  template<class InputIterator>
2989
- void insert(sorted_unique_t, InputIterator first, InputIterator last);
2990
  ```
2991
 
2992
  *Effects:* Equivalent to `insert(first, last)`.
2993
 
2994
  *Complexity:* Linear.
2995
 
2996
  ``` cpp
2997
  template<container-compatible-range<value_type> R>
2998
- void insert_range(R&& rg);
2999
  ```
3000
 
3001
  *Effects:* Adds elements to *c* as if by:
3002
 
3003
  ``` cpp
@@ -3017,31 +3067,31 @@ M is `ranges::distance(rg)`.
3017
 
3018
  *Remarks:* Since this operation performs an in-place merge, it may
3019
  allocate memory.
3020
 
3021
  ``` cpp
3022
- void swap(flat_set& y) noexcept;
3023
  ```
3024
 
3025
  *Effects:* Equivalent to:
3026
 
3027
  ``` cpp
3028
  ranges::swap(compare, y.compare);
3029
  ranges::swap(c, y.c);
3030
  ```
3031
 
3032
  ``` cpp
3033
- container_type extract() &&;
3034
  ```
3035
 
3036
  *Ensures:* `*this` is emptied, even if the function exits via an
3037
  exception.
3038
 
3039
  *Returns:* `std::move(`*`c`*`)`.
3040
 
3041
  ``` cpp
3042
- void replace(container_type&& cont);
3043
  ```
3044
 
3045
  *Preconditions:* The elements of `cont` are sorted with respect to
3046
  *compare*, and `cont` contains no equal elements.
3047
 
@@ -3049,11 +3099,11 @@ void replace(container_type&& cont);
3049
 
3050
  #### Erasure <a id="flat.set.erasure">[[flat.set.erasure]]</a>
3051
 
3052
  ``` cpp
3053
  template<class Key, class Compare, class KeyContainer, class Predicate>
3054
- typename flat_set<Key, Compare, KeyContainer>::size_type
3055
  erase_if(flat_set<Key, Compare, KeyContainer>& c, Predicate pred);
3056
  ```
3057
 
3058
  *Preconditions:* `Key` meets the *Cpp17MoveAssignable* requirements.
3059
 
@@ -3126,14 +3176,17 @@ In particular, `vector` [[vector]] and `deque` [[deque]] can be used.
3126
  [*Note 3*: `vector<bool>` is not a sequence container. — *end note*]
3127
 
3128
  The program is ill-formed if `Key` is not the same type as
3129
  `KeyContainer::value_type`.
3130
 
3131
- The effect of calling a constructor or member function that takes a
3132
  `sorted_equivalent_t` argument with a range that is not sorted with
3133
  respect to `key_comp()` is undefined.
3134
 
 
 
 
3135
  #### Definition <a id="flat.multiset.defn">[[flat.multiset.defn]]</a>
3136
 
3137
  ``` cpp
3138
  namespace std {
3139
  template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>
@@ -3144,194 +3197,205 @@ namespace std {
3144
  using value_type = Key;
3145
  using key_compare = Compare;
3146
  using value_compare = Compare;
3147
  using reference = value_type&;
3148
  using const_reference = const value_type&;
3149
- using size_type = typename KeyContainer::size_type;
3150
- using difference_type = typename KeyContainer::difference_type;
3151
  using iterator = implementation-defined // type of flat_multiset::iterator; // see [container.requirements]
3152
  using const_iterator = implementation-defined // type of flat_multiset::const_iterator; // see [container.requirements]
3153
  using reverse_iterator = std::reverse_iterator<iterator>;
3154
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
3155
  using container_type = KeyContainer;
3156
 
3157
  // [flat.multiset.cons], constructors
3158
- flat_multiset() : flat_multiset(key_compare()) { }
3159
 
3160
- explicit flat_multiset(container_type cont, const key_compare& comp = key_compare());
3161
- template<class Allocator>
3162
- flat_multiset(const container_type& cont, const Allocator& a);
3163
- template<class Allocator>
3164
- flat_multiset(const container_type& cont, const key_compare& comp, const Allocator& a);
3165
-
3166
- flat_multiset(sorted_equivalent_t, container_type cont,
3167
- const key_compare& comp = key_compare())
3168
- : c(std::move(cont)), compare(comp) { }
3169
- template<class Allocator>
3170
- flat_multiset(sorted_equivalent_t, const container_type&, const Allocator& a);
3171
- template<class Allocator>
3172
- flat_multiset(sorted_equivalent_t, const container_type& cont,
3173
- const key_compare& comp, const Allocator& a);
3174
-
3175
- explicit flat_multiset(const key_compare& comp)
3176
  : c(), compare(comp) { }
3177
- template<class Allocator>
3178
- flat_multiset(const key_compare& comp, const Allocator& a);
3179
- template<class Allocator>
3180
- explicit flat_multiset(const Allocator& a);
 
 
 
3181
 
3182
  template<class InputIterator>
3183
- flat_multiset(InputIterator first, InputIterator last,
3184
  const key_compare& comp = key_compare())
3185
  : c(), compare(comp)
3186
  { insert(first, last); }
3187
- template<class InputIterator, class Allocator>
3188
- flat_multiset(InputIterator first, InputIterator last,
3189
- const key_compare& comp, const Allocator& a);
3190
- template<class InputIterator, class Allocator>
3191
- flat_multiset(InputIterator first, InputIterator last, const Allocator& a);
3192
 
3193
  template<container-compatible-range<value_type> R>
3194
- flat_multiset(from_range_t fr, R&& rg)
3195
- : flat_multiset(fr, std::forward<R>(rg), key_compare()) { }
3196
- template<container-compatible-range<value_type> R, class Allocator>
3197
- flat_multiset(from_range_t, R&& rg, const Allocator& a);
3198
  template<container-compatible-range<value_type> R>
3199
- flat_multiset(from_range_t, R&& rg, const key_compare& comp)
3200
  : flat_multiset(comp)
3201
  { insert_range(std::forward<R>(rg)); }
3202
- template<container-compatible-range<value_type> R, class Allocator>
3203
- flat_multiset(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
3204
 
3205
- template<class InputIterator>
3206
- flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
3207
  const key_compare& comp = key_compare())
3208
- : c(first, last), compare(comp) { }
3209
- template<class InputIterator, class Allocator>
3210
- flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
3211
- const key_compare& comp, const Allocator& a);
3212
- template<class InputIterator, class Allocator>
3213
- flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
3214
- const Allocator& a);
3215
-
3216
- flat_multiset(initializer_list<value_type> il, const key_compare& comp = key_compare())
3217
  : flat_multiset(il.begin(), il.end(), comp) { }
3218
- template<class Allocator>
3219
- flat_multiset(initializer_list<value_type> il, const key_compare& comp,
3220
- const Allocator& a);
3221
- template<class Allocator>
3222
- flat_multiset(initializer_list<value_type> il, const Allocator& a);
3223
 
3224
- flat_multiset(sorted_equivalent_t s, initializer_list<value_type> il,
3225
  const key_compare& comp = key_compare())
3226
- : flat_multiset(s, il.begin(), il.end(), comp) { }
3227
- template<class Allocator>
3228
- flat_multiset(sorted_equivalent_t, initializer_list<value_type> il,
3229
- const key_compare& comp, const Allocator& a);
3230
- template<class Allocator>
3231
- flat_multiset(sorted_equivalent_t, initializer_list<value_type> il, const Allocator& a);
3232
 
3233
- flat_multiset& operator=(initializer_list<value_type>);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3234
 
3235
  // iterators
3236
- iterator begin() noexcept;
3237
- const_iterator begin() const noexcept;
3238
- iterator end() noexcept;
3239
- const_iterator end() const noexcept;
3240
 
3241
- reverse_iterator rbegin() noexcept;
3242
- const_reverse_iterator rbegin() const noexcept;
3243
- reverse_iterator rend() noexcept;
3244
- const_reverse_iterator rend() const noexcept;
3245
 
3246
- const_iterator cbegin() const noexcept;
3247
- const_iterator cend() const noexcept;
3248
- const_reverse_iterator crbegin() const noexcept;
3249
- const_reverse_iterator crend() const noexcept;
3250
 
3251
  // capacity
3252
- [[nodiscard]] bool empty() const noexcept;
3253
- size_type size() const noexcept;
3254
- size_type max_size() const noexcept;
3255
 
3256
  // [flat.multiset.modifiers], modifiers
3257
- template<class... Args> iterator emplace(Args&&... args);
3258
  template<class... Args>
3259
- iterator emplace_hint(const_iterator position, Args&&... args);
3260
 
3261
- iterator insert(const value_type& x)
3262
  { return emplace(x); }
3263
- iterator insert(value_type&& x)
3264
  { return emplace(std::move(x)); }
3265
- iterator insert(const_iterator position, const value_type& x)
3266
  { return emplace_hint(position, x); }
3267
- iterator insert(const_iterator position, value_type&& x)
3268
  { return emplace_hint(position, std::move(x)); }
3269
 
3270
  template<class InputIterator>
3271
- void insert(InputIterator first, InputIterator last);
3272
  template<class InputIterator>
3273
- void insert(sorted_equivalent_t, InputIterator first, InputIterator last);
3274
  template<container-compatible-range<value_type> R>
3275
- void insert_range(R&& rg);
3276
 
3277
- void insert(initializer_list<value_type> il)
3278
  { insert(il.begin(), il.end()); }
3279
- void insert(sorted_equivalent_t s, initializer_list<value_type> il)
3280
- { insert(s, il.begin(), il.end()); }
3281
 
3282
- container_type extract() &&;
3283
- void replace(container_type&&);
3284
 
3285
- iterator erase(iterator position);
3286
- iterator erase(const_iterator position);
3287
- size_type erase(const key_type& x);
3288
- template<class K> size_type erase(K&& x);
3289
- iterator erase(const_iterator first, const_iterator last);
3290
 
3291
- void swap(flat_multiset& y) noexcept;
3292
- void clear() noexcept;
3293
 
3294
  // observers
3295
- key_compare key_comp() const;
3296
- value_compare value_comp() const;
3297
 
3298
  // set operations
3299
- iterator find(const key_type& x);
3300
- const_iterator find(const key_type& x) const;
3301
- template<class K> iterator find(const K& x);
3302
- template<class K> const_iterator find(const K& x) const;
3303
 
3304
- size_type count(const key_type& x) const;
3305
- template<class K> size_type count(const K& x) const;
3306
 
3307
- bool contains(const key_type& x) const;
3308
- template<class K> bool contains(const K& x) const;
3309
 
3310
- iterator lower_bound(const key_type& x);
3311
- const_iterator lower_bound(const key_type& x) const;
3312
- template<class K> iterator lower_bound(const K& x);
3313
- template<class K> const_iterator lower_bound(const K& x) const;
3314
 
3315
- iterator upper_bound(const key_type& x);
3316
- const_iterator upper_bound(const key_type& x) const;
3317
- template<class K> iterator upper_bound(const K& x);
3318
- template<class K> const_iterator upper_bound(const K& x) const;
3319
 
3320
- pair<iterator, iterator> equal_range(const key_type& x);
3321
- pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
3322
  template<class K>
3323
- pair<iterator, iterator> equal_range(const K& x);
3324
  template<class K>
3325
- pair<const_iterator, const_iterator> equal_range(const K& x) const;
3326
 
3327
- friend bool operator==(const flat_multiset& x, const flat_multiset& y);
3328
 
3329
- friend synth-three-way-result<value_type>
3330
  operator<=>(const flat_multiset& x, const flat_multiset& y);
3331
 
3332
- friend void swap(flat_multiset& x, flat_multiset& y) noexcept
3333
  { x.swap(y); }
3334
 
3335
  private:
3336
  container_type c; // exposition only
3337
  key_compare compare; // exposition only
@@ -3359,15 +3423,15 @@ namespace std {
3359
  flat_multiset(sorted_equivalent_t, KeyContainer, Compare, Allocator)
3360
  -> flat_multiset<typename KeyContainer::value_type, Compare, KeyContainer>;
3361
 
3362
  template<class InputIterator, class Compare = less<iter-value-type<InputIterator>>>
3363
  flat_multiset(InputIterator, InputIterator, Compare = Compare())
3364
- -> flat_multiset<iter-value-type<InputIterator>, iter-value-type<InputIterator>, Compare>;
3365
 
3366
  template<class InputIterator, class Compare = less<iter-value-type<InputIterator>>>
3367
  flat_multiset(sorted_equivalent_t, InputIterator, InputIterator, Compare = Compare())
3368
- -> flat_multiset<iter-value-type<InputIterator>, iter-value-type<InputIterator>, Compare>;
3369
 
3370
  template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
3371
  class Allocator = allocator<ranges::range_value_t<R>>>
3372
  flat_multiset(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
3373
  -> flat_multiset<ranges::range_value_t<R>, Compare,
@@ -3395,95 +3459,100 @@ namespace std {
3395
  ```
3396
 
3397
  #### Constructors <a id="flat.multiset.cons">[[flat.multiset.cons]]</a>
3398
 
3399
  ``` cpp
3400
- explicit flat_multiset(container_type cont, const key_compare& comp = key_compare());
3401
  ```
3402
 
3403
  *Effects:* Initializes *c* with `std::move(cont)` and *compare* with
3404
  `comp`, and sorts the range \[`begin()`, `end()`) with respect to
3405
  *compare*.
3406
 
3407
- *Complexity:* Linear in N if `cont` is sorted with respect to *compare*
3408
- and otherwise N log N, where N is the value of `cont.size()` before this
3409
- call.
 
 
 
 
 
3410
 
3411
  ``` cpp
3412
- template<class Allocator>
3413
- flat_multiset(const container_type& cont, const Allocator& a);
3414
- template<class Allocator>
3415
- flat_multiset(const container_type& cont, const key_compare& comp, const Allocator& a);
3416
  ```
3417
 
3418
- *Constraints:* `uses_allocator_v<container_type, Allocator>` is `true`.
3419
-
3420
  *Effects:* Equivalent to `flat_multiset(cont)` and
3421
  `flat_multiset(cont, comp)`, respectively, except that *c* is
3422
  constructed with uses-allocator
3423
  construction [[allocator.uses.construction]].
3424
 
3425
  *Complexity:* Same as `flat_multiset(cont)` and
3426
  `flat_multiset(cont, comp)`, respectively.
3427
 
3428
  ``` cpp
3429
- template<class Allocator>
3430
- flat_multiset(sorted_equivalent_t s, const container_type& cont, const Allocator& a);
3431
- template<class Allocator>
3432
- flat_multiset(sorted_equivalent_t s, const container_type& cont,
3433
- const key_compare& comp, const Allocator& a);
3434
  ```
3435
 
3436
- *Constraints:* `uses_allocator_v<container_type, Allocator>` is `true`.
3437
-
3438
- *Effects:* Equivalent to `flat_multiset(s, cont)` and
3439
- `flat_multiset(s, cont, comp)`, respectively, except that *c* is
3440
- constructed with uses-allocator
3441
  construction [[allocator.uses.construction]].
3442
 
3443
  *Complexity:* Linear.
3444
 
3445
  ``` cpp
3446
- template<class Allocator>
3447
- flat_multiset(const key_compare& comp, const Allocator& a);
3448
- template<class Allocator>
3449
- explicit flat_multiset(const Allocator& a);
3450
- template<class InputIterator, class Allocator>
3451
- flat_multiset(InputIterator first, InputIterator last,
3452
- const key_compare& comp, const Allocator& a);
3453
- template<class InputIterator, class Allocator>
3454
- flat_multiset(InputIterator first, InputIterator last, const Allocator& a);
3455
- template<container-compatible-range<value_type> R, class Allocator>
3456
- flat_multiset(from_range_t, R&& rg, const Allocator& a);
3457
- template<container-compatible-range<value_type> R, class Allocator>
3458
- flat_multiset(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
3459
- template<class InputIterator, class Allocator>
3460
- flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
3461
- const key_compare& comp, const Allocator& a);
3462
- template<class InputIterator, class Allocator>
3463
- flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last, const Allocator& a);
3464
- template<class Allocator>
3465
- flat_multiset(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
3466
- template<class Allocator>
3467
- flat_multiset(initializer_list<value_type> il, const Allocator& a);
3468
- template<class Allocator>
3469
- flat_multiset(sorted_equivalent_t, initializer_list<value_type> il,
3470
- const key_compare& comp, const Allocator& a);
3471
- template<class Allocator>
3472
- flat_multiset(sorted_equivalent_t, initializer_list<value_type> il, const Allocator& a);
 
 
 
 
 
 
3473
  ```
3474
 
3475
- *Constraints:* `uses_allocator_v<container_type, Allocator>` is `true`.
3476
-
3477
  *Effects:* Equivalent to the corresponding non-allocator constructors
3478
  except that *c* is constructed with uses-allocator
3479
  construction [[allocator.uses.construction]].
3480
 
3481
  #### Modifiers <a id="flat.multiset.modifiers">[[flat.multiset.modifiers]]</a>
3482
 
3483
  ``` cpp
3484
- template<class... Args> iterator emplace(Args&&... args);
3485
  ```
3486
 
3487
  *Constraints:* `is_constructible_v<value_type, Args...>` is `true`.
3488
 
3489
  *Effects:* First, initializes an object `t` of type `value_type` with
@@ -3496,11 +3565,11 @@ c.insert(it, std::move(t));
3496
 
3497
  *Returns:* An iterator that points to the inserted element.
3498
 
3499
  ``` cpp
3500
  template<class InputIterator>
3501
- void insert(InputIterator first, InputIterator last);
3502
  ```
3503
 
3504
  *Effects:* Adds elements to *c* as if by:
3505
 
3506
  ``` cpp
@@ -3517,51 +3586,51 @@ M is `distance(first, last)`.
3517
  *Remarks:* Since this operation performs an in-place merge, it may
3518
  allocate memory.
3519
 
3520
  ``` cpp
3521
  template<class InputIterator>
3522
- void insert(sorted_equivalent_t, InputIterator first, InputIterator last);
3523
  ```
3524
 
3525
  *Effects:* Equivalent to `insert(first, last)`.
3526
 
3527
  *Complexity:* Linear.
3528
 
3529
  ``` cpp
3530
- void swap(flat_multiset& y) noexcept;
3531
  ```
3532
 
3533
  *Effects:* Equivalent to:
3534
 
3535
  ``` cpp
3536
  ranges::swap(compare, y.compare);
3537
  ranges::swap(c, y.c);
3538
  ```
3539
 
3540
  ``` cpp
3541
- container_type extract() &&;
3542
  ```
3543
 
3544
  *Ensures:* `*this` is emptied, even if the function exits via an
3545
  exception.
3546
 
3547
- *Returns:* `std::move(c)`.
3548
 
3549
  ``` cpp
3550
- void replace(container_type&& cont);
3551
  ```
3552
 
3553
  *Preconditions:* The elements of `cont` are sorted with respect to
3554
  *compare*.
3555
 
3556
- *Effects:* Equivalent to: `c = std::move(cont);`
3557
 
3558
  #### Erasure <a id="flat.multiset.erasure">[[flat.multiset.erasure]]</a>
3559
 
3560
  ``` cpp
3561
  template<class Key, class Compare, class KeyContainer, class Predicate>
3562
- typename flat_multiset<Key, Compare, KeyContainer>::size_type
3563
  erase_if(flat_multiset<Key, Compare, KeyContainer>& c, Predicate pred);
3564
  ```
3565
 
3566
  *Preconditions:* `Key` meets the *Cpp17MoveAssignable* requirements.
3567
 
 
1
  ## Container adaptors <a id="container.adaptors">[[container.adaptors]]</a>
2
 
3
+ ### General <a id="container.adaptors.general">[[container.adaptors.general]]</a>
4
 
5
  The headers `<queue>`, `<stack>`, `<flat_map>`, and `<flat_set>` define
6
  the container adaptors `queue` and `priority_queue`, `stack`, `flat_map`
7
  and `flat_multimap`, and `flat_set` and `flat_multiset`, respectively.
8
 
 
73
  The following exposition-only alias template may appear in deduction
74
  guides for container adaptors:
75
 
76
  ``` cpp
77
  template<class Allocator, class T>
78
+ using alloc-rebind = allocator_traits<Allocator>::template rebind_alloc<T>; // exposition only
 
79
  ```
80
 
81
  ### Header `<queue>` synopsis <a id="queue.syn">[[queue.syn]]</a>
82
 
83
  ``` cpp
 
87
  namespace std {
88
  // [queue], class template queue
89
  template<class T, class Container = deque<T>> class queue;
90
 
91
  template<class T, class Container>
92
+ constexpr bool operator==(const queue<T, Container>& x, const queue<T, Container>& y);
93
  template<class T, class Container>
94
+ constexpr bool operator!=(const queue<T, Container>& x, const queue<T, Container>& y);
95
  template<class T, class Container>
96
+ constexpr bool operator< (const queue<T, Container>& x, const queue<T, Container>& y);
97
  template<class T, class Container>
98
+ constexpr bool operator> (const queue<T, Container>& x, const queue<T, Container>& y);
99
  template<class T, class Container>
100
+ constexpr bool operator<=(const queue<T, Container>& x, const queue<T, Container>& y);
101
  template<class T, class Container>
102
+ constexpr bool operator>=(const queue<T, Container>& x, const queue<T, Container>& y);
103
  template<class T, three_way_comparable Container>
104
+ constexpr compare_three_way_result_t<Container>
105
  operator<=>(const queue<T, Container>& x, const queue<T, Container>& y);
106
 
107
  template<class T, class Container>
108
+ constexpr void swap(queue<T, Container>& x, queue<T, Container>& y)
109
+ noexcept(noexcept(x.swap(y)));
110
  template<class T, class Container, class Alloc>
111
  struct uses_allocator<queue<T, Container>, Alloc>;
112
 
113
+ // [container.adaptors.format], formatter specialization for queue
114
+ template<class charT, class T, formattable<charT> Container>
115
+ struct formatter<queue<T, Container>, charT>;
116
+
117
  // [priority.queue], class template priority_queue
118
  template<class T, class Container = vector<T>,
119
  class Compare = less<typename Container::value_type>>
120
  class priority_queue;
121
 
122
  template<class T, class Container, class Compare>
123
+ constexpr void swap(priority_queue<T, Container, Compare>& x,
124
  priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
125
  template<class T, class Container, class Compare, class Alloc>
126
  struct uses_allocator<priority_queue<T, Container, Compare>, Alloc>;
 
 
127
 
128
+ // [container.adaptors.format], formatter specialization for priority_queue
129
+ template<class charT, class T, formattable<charT> Container, class Compare>
130
+ struct formatter<priority_queue<T, Container, Compare>, charT>;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
131
  }
132
  ```
133
 
134
  ### Class template `queue` <a id="queue">[[queue]]</a>
135
 
 
142
  ``` cpp
143
  namespace std {
144
  template<class T, class Container = deque<T>>
145
  class queue {
146
  public:
147
+ using value_type = Container::value_type;
148
+ using reference = Container::reference;
149
+ using const_reference = Container::const_reference;
150
+ using size_type = Container::size_type;
151
  using container_type = Container;
152
 
153
  protected:
154
  Container c;
155
 
156
  public:
157
+ constexpr queue() : queue(Container()) {}
158
+ constexpr explicit queue(const Container&);
159
+ constexpr explicit queue(Container&&);
160
+ template<class InputIterator> constexpr queue(InputIterator first, InputIterator last);
161
+ template<container-compatible-range<T> R> constexpr queue(from_range_t, R&& rg);
162
+ template<class Alloc> constexpr explicit queue(const Alloc&);
163
+ template<class Alloc> constexpr queue(const Container&, const Alloc&);
164
+ template<class Alloc> constexpr queue(Container&&, const Alloc&);
165
+ template<class Alloc> constexpr queue(const queue&, const Alloc&);
166
+ template<class Alloc> constexpr queue(queue&&, const Alloc&);
167
  template<class InputIterator, class Alloc>
168
+ constexpr queue(InputIterator first, InputIterator last, const Alloc&);
169
  template<container-compatible-range<T> R, class Alloc>
170
+ constexpr queue(from_range_t, R&& rg, const Alloc&);
171
 
172
+ constexpr bool empty() const { return c.empty(); }
173
+ constexpr size_type size() const { return c.size(); }
174
+ constexpr reference front() { return c.front(); }
175
+ constexpr const_reference front() const { return c.front(); }
176
+ constexpr reference back() { return c.back(); }
177
+ constexpr const_reference back() const { return c.back(); }
178
+ constexpr void push(const value_type& x) { c.push_back(x); }
179
+ constexpr void push(value_type&& x) { c.push_back(std::move(x)); }
180
+ template<container-compatible-range<T> R> constexpr void push_range(R&& rg);
181
  template<class... Args>
182
+ constexpr decltype(auto) emplace(Args&&... args)
183
  { return c.emplace_back(std::forward<Args>(args)...); }
184
+ constexpr void pop() { c.pop_front(); }
185
+ constexpr void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>)
186
  { using std::swap; swap(c, q.c); }
187
  };
188
 
189
  template<class Container>
190
  queue(Container) -> queue<typename Container::value_type, Container>;
 
214
  ```
215
 
216
  #### Constructors <a id="queue.cons">[[queue.cons]]</a>
217
 
218
  ``` cpp
219
+ constexpr explicit queue(const Container& cont);
220
  ```
221
 
222
  *Effects:* Initializes `c` with `cont`.
223
 
224
  ``` cpp
225
+ constexpr explicit queue(Container&& cont);
226
  ```
227
 
228
  *Effects:* Initializes `c` with `std::move(cont)`.
229
 
230
  ``` cpp
231
  template<class InputIterator>
232
+ constexpr queue(InputIterator first, InputIterator last);
233
  ```
234
 
235
  *Effects:* Initializes `c` with `first` as the first argument and `last`
236
  as the second argument.
237
 
238
  ``` cpp
239
  template<container-compatible-range<T> R>
240
+ constexpr queue(from_range_t, R&& rg);
241
  ```
242
 
243
  *Effects:* Initializes `c` with
244
  `ranges::to<Container>(std::forward<R>(rg))`.
245
 
 
247
 
248
  If `uses_allocator_v<container_type, Alloc>` is `false` the constructors
249
  in this subclause shall not participate in overload resolution.
250
 
251
  ``` cpp
252
+ template<class Alloc> constexpr explicit queue(const Alloc& a);
253
  ```
254
 
255
  *Effects:* Initializes `c` with `a`.
256
 
257
  ``` cpp
258
+ template<class Alloc> constexpr queue(const container_type& cont, const Alloc& a);
259
  ```
260
 
261
  *Effects:* Initializes `c` with `cont` as the first argument and `a` as
262
  the second argument.
263
 
264
  ``` cpp
265
+ template<class Alloc> constexpr queue(container_type&& cont, const Alloc& a);
266
  ```
267
 
268
  *Effects:* Initializes `c` with `std::move(cont)` as the first argument
269
  and `a` as the second argument.
270
 
271
  ``` cpp
272
+ template<class Alloc> constexpr queue(const queue& q, const Alloc& a);
273
  ```
274
 
275
  *Effects:* Initializes `c` with `q.c` as the first argument and `a` as
276
  the second argument.
277
 
278
  ``` cpp
279
+ template<class Alloc> constexpr queue(queue&& q, const Alloc& a);
280
  ```
281
 
282
  *Effects:* Initializes `c` with `std::move(q.c)` as the first argument
283
  and `a` as the second argument.
284
 
285
  ``` cpp
286
  template<class InputIterator, class Alloc>
287
+ constexpr queue(InputIterator first, InputIterator last, const Alloc& alloc);
288
  ```
289
 
290
  *Effects:* Initializes `c` with `first` as the first argument, `last` as
291
  the second argument, and `alloc` as the third argument.
292
 
293
  ``` cpp
294
  template<container-compatible-range<T> R, class Alloc>
295
+ constexpr queue(from_range_t, R&& rg, const Alloc& a);
296
  ```
297
 
298
  *Effects:* Initializes `c` with
299
  `ranges::to<Container>(std::forward<R>(rg), a)`.
300
 
301
  #### Modifiers <a id="queue.mod">[[queue.mod]]</a>
302
 
303
  ``` cpp
304
  template<container-compatible-range<T> R>
305
+ constexpr void push_range(R&& rg);
306
  ```
307
 
308
  *Effects:* Equivalent to `c.append_range(std::forward<R>(rg))` if that
309
  is a valid expression, otherwise `ranges::copy(rg, back_inserter(c))`.
310
 
311
  #### Operators <a id="queue.ops">[[queue.ops]]</a>
312
 
313
  ``` cpp
314
  template<class T, class Container>
315
+ constexpr bool operator==(const queue<T, Container>& x, const queue<T, Container>& y);
316
  ```
317
 
318
  *Returns:* `x.c == y.c`.
319
 
320
  ``` cpp
321
  template<class T, class Container>
322
+ constexpr bool operator!=(const queue<T, Container>& x, const queue<T, Container>& y);
323
  ```
324
 
325
  *Returns:* `x.c != y.c`.
326
 
327
  ``` cpp
328
  template<class T, class Container>
329
+ constexpr bool operator< (const queue<T, Container>& x, const queue<T, Container>& y);
330
  ```
331
 
332
  *Returns:* `x.c < y.c`.
333
 
334
  ``` cpp
335
  template<class T, class Container>
336
+ constexpr bool operator> (const queue<T, Container>& x, const queue<T, Container>& y);
337
  ```
338
 
339
  *Returns:* `x.c > y.c`.
340
 
341
  ``` cpp
342
  template<class T, class Container>
343
+ constexpr bool operator<=(const queue<T, Container>& x, const queue<T, Container>& y);
344
  ```
345
 
346
  *Returns:* `x.c <= y.c`.
347
 
348
  ``` cpp
349
  template<class T, class Container>
350
+ constexpr bool operator>=(const queue<T, Container>& x, const queue<T, Container>& y);
 
351
  ```
352
 
353
  *Returns:* `x.c >= y.c`.
354
 
355
  ``` cpp
356
  template<class T, three_way_comparable Container>
357
+ constexpr compare_three_way_result_t<Container>
358
  operator<=>(const queue<T, Container>& x, const queue<T, Container>& y);
359
  ```
360
 
361
  *Returns:* `x.c <=> y.c`.
362
 
363
  #### Specialized algorithms <a id="queue.special">[[queue.special]]</a>
364
 
365
  ``` cpp
366
  template<class T, class Container>
367
+ constexpr void swap(queue<T, Container>& x, queue<T, Container>& y)
368
+ noexcept(noexcept(x.swap(y)));
369
  ```
370
 
371
  *Constraints:* `is_swappable_v<Container>` is `true`.
372
 
373
  *Effects:* As if by `x.swap(y)`.
 
388
  namespace std {
389
  template<class T, class Container = vector<T>,
390
  class Compare = less<typename Container::value_type>>
391
  class priority_queue {
392
  public:
393
+ using value_type = Container::value_type;
394
+ using reference = Container::reference;
395
+ using const_reference = Container::const_reference;
396
+ using size_type = Container::size_type;
397
  using container_type = Container;
398
  using value_compare = Compare;
399
 
400
  protected:
401
  Container c;
402
  Compare comp;
403
 
404
  public:
405
+ constexpr priority_queue() : priority_queue(Compare()) {}
406
+ constexpr explicit priority_queue(const Compare& x) : priority_queue(x, Container()) {}
407
+ constexpr priority_queue(const Compare& x, const Container&);
408
+ constexpr priority_queue(const Compare& x, Container&&);
409
  template<class InputIterator>
410
+ constexpr priority_queue(InputIterator first, InputIterator last,
411
+ const Compare& x = Compare());
412
  template<class InputIterator>
413
+ constexpr priority_queue(InputIterator first, InputIterator last, const Compare& x,
414
  const Container&);
415
  template<class InputIterator>
416
+ constexpr priority_queue(InputIterator first, InputIterator last, const Compare& x,
417
  Container&&);
418
  template<container-compatible-range<T> R>
419
+ constexpr priority_queue(from_range_t, R&& rg, const Compare& x = Compare());
420
+ template<class Alloc> constexpr explicit priority_queue(const Alloc&);
421
+ template<class Alloc> constexpr priority_queue(const Compare&, const Alloc&);
422
+ template<class Alloc>
423
+ constexpr priority_queue(const Compare&, const Container&, const Alloc&);
424
+ template<class Alloc> constexpr priority_queue(const Compare&, Container&&, const Alloc&);
425
+ template<class Alloc> constexpr priority_queue(const priority_queue&, const Alloc&);
426
+ template<class Alloc> constexpr priority_queue(priority_queue&&, const Alloc&);
427
  template<class InputIterator, class Alloc>
428
+ constexpr priority_queue(InputIterator, InputIterator, const Alloc&);
429
  template<class InputIterator, class Alloc>
430
+ constexpr priority_queue(InputIterator, InputIterator, const Compare&, const Alloc&);
431
  template<class InputIterator, class Alloc>
432
+ constexpr priority_queue(InputIterator, InputIterator, const Compare&, const Container&,
433
  const Alloc&);
434
  template<class InputIterator, class Alloc>
435
+ constexpr priority_queue(InputIterator, InputIterator, const Compare&, Container&&,
436
+ const Alloc&);
437
  template<container-compatible-range<T> R, class Alloc>
438
+ constexpr priority_queue(from_range_t, R&& rg, const Compare&, const Alloc&);
439
  template<container-compatible-range<T> R, class Alloc>
440
+ constexpr priority_queue(from_range_t, R&& rg, const Alloc&);
441
 
442
+ constexpr bool empty() const { return c.empty(); }
443
+ constexpr size_type size() const { return c.size(); }
444
+ constexpr const_reference top() const { return c.front(); }
445
+ constexpr void push(const value_type& x);
446
+ constexpr void push(value_type&& x);
447
  template<container-compatible-range<T> R>
448
+ constexpr void push_range(R&& rg);
449
+ template<class... Args> constexpr void emplace(Args&&... args);
450
+ constexpr void pop();
451
+ constexpr void swap(priority_queue& q)
452
+ noexcept(is_nothrow_swappable_v<Container> && is_nothrow_swappable_v<Compare>)
453
  { using std::swap; swap(c, q.c); swap(comp, q.comp); }
454
  };
455
 
456
  template<class Compare, class Container>
457
  priority_queue(Compare, Container)
 
504
  ```
505
 
506
  #### Constructors <a id="priqueue.cons">[[priqueue.cons]]</a>
507
 
508
  ``` cpp
509
+ constexpr priority_queue(const Compare& x, const Container& y);
510
+ constexpr priority_queue(const Compare& x, Container&& y);
511
  ```
512
 
513
  *Preconditions:* `x` defines a strict weak ordering [[alg.sorting]].
514
 
515
  *Effects:* Initializes `comp` with `x` and `c` with `y` (copy
516
  constructing or move constructing as appropriate); calls
517
  `make_heap(c.begin(), c.end(), comp)`.
518
 
519
  ``` cpp
520
  template<class InputIterator>
521
+ constexpr priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare());
522
  ```
523
 
524
  *Preconditions:* `x` defines a strict weak ordering [[alg.sorting]].
525
 
526
  *Effects:* Initializes `c` with `first` as the first argument and `last`
527
  as the second argument, and initializes `comp` with `x`; then calls
528
  `make_heap(c.begin(), c.end(), comp)`.
529
 
530
  ``` cpp
531
  template<class InputIterator>
532
+ constexpr priority_queue(InputIterator first, InputIterator last, const Compare& x,
533
+ const Container& y);
534
  template<class InputIterator>
535
+ constexpr priority_queue(InputIterator first, InputIterator last, const Compare& x,
536
+ Container&& y);
537
  ```
538
 
539
  *Preconditions:* `x` defines a strict weak ordering [[alg.sorting]].
540
 
541
  *Effects:* Initializes `comp` with `x` and `c` with `y` (copy
 
543
  `c.insert(c.end(), first, last)`; and finally calls
544
  `make_heap(c.begin(), c.end(), comp)`.
545
 
546
  ``` cpp
547
  template<container-compatible-range<T> R>
548
+ constexpr priority_queue(from_range_t, R&& rg, const Compare& x = Compare());
549
  ```
550
 
551
  *Preconditions:* `x` defines a strict weak ordering [[alg.sorting]].
552
 
553
  *Effects:* Initializes `comp` with `x` and `c` with
 
558
 
559
  If `uses_allocator_v<container_type, Alloc>` is `false` the constructors
560
  in this subclause shall not participate in overload resolution.
561
 
562
  ``` cpp
563
+ template<class Alloc> constexpr explicit priority_queue(const Alloc& a);
564
  ```
565
 
566
  *Effects:* Initializes `c` with `a` and value-initializes `comp`.
567
 
568
  ``` cpp
569
+ template<class Alloc> constexpr priority_queue(const Compare& compare, const Alloc& a);
570
  ```
571
 
572
  *Effects:* Initializes `c` with `a` and initializes `comp` with
573
  `compare`.
574
 
575
  ``` cpp
576
  template<class Alloc>
577
+ constexpr priority_queue(const Compare& compare, const Container& cont, const Alloc& a);
578
  ```
579
 
580
  *Effects:* Initializes `c` with `cont` as the first argument and `a` as
581
  the second argument, and initializes `comp` with `compare`; calls
582
  `make_heap(c.begin(), c.end(), comp)`.
583
 
584
  ``` cpp
585
  template<class Alloc>
586
+ constexpr priority_queue(const Compare& compare, Container&& cont, const Alloc& a);
587
  ```
588
 
589
  *Effects:* Initializes `c` with `std::move(cont)` as the first argument
590
  and `a` as the second argument, and initializes `comp` with `compare`;
591
  calls `make_heap(c.begin(), c.end(), comp)`.
592
 
593
  ``` cpp
594
+ template<class Alloc> constexpr priority_queue(const priority_queue& q, const Alloc& a);
595
  ```
596
 
597
  *Effects:* Initializes `c` with `q.c` as the first argument and `a` as
598
  the second argument, and initializes `comp` with `q.comp`.
599
 
600
  ``` cpp
601
+ template<class Alloc> constexpr priority_queue(priority_queue&& q, const Alloc& a);
602
  ```
603
 
604
  *Effects:* Initializes `c` with `std::move(q.c)` as the first argument
605
  and `a` as the second argument, and initializes `comp` with
606
  `std::move(q.comp)`.
607
 
608
  ``` cpp
609
  template<class InputIterator, class Alloc>
610
+ constexpr priority_queue(InputIterator first, InputIterator last, const Alloc& a);
611
  ```
612
 
613
  *Effects:* Initializes `c` with `first` as the first argument, `last` as
614
  the second argument, and `a` as the third argument, and
615
  value-initializes `comp`; calls `make_heap(c.begin(), c.end(), comp)`.
616
 
617
  ``` cpp
618
  template<class InputIterator, class Alloc>
619
+ constexpr priority_queue(InputIterator first, InputIterator last,
620
+ const Compare& compare, const Alloc& a);
621
  ```
622
 
623
  *Effects:* Initializes `c` with `first` as the first argument, `last` as
624
  the second argument, and `a` as the third argument, and initializes
625
  `comp` with `compare`; calls `make_heap(c.begin(), c.end(), comp)`.
626
 
627
  ``` cpp
628
  template<class InputIterator, class Alloc>
629
+ constexpr priority_queue(InputIterator first, InputIterator last, const Compare& compare,
630
  const Container& cont, const Alloc& a);
631
  ```
632
 
633
  *Effects:* Initializes `c` with `cont` as the first argument and `a` as
634
  the second argument, and initializes `comp` with `compare`; calls
635
  `c.insert(c.end(), first, last)`; and finally calls
636
  `make_heap(c.begin(), c.end(), comp)`.
637
 
638
  ``` cpp
639
  template<class InputIterator, class Alloc>
640
+ constexpr priority_queue(InputIterator first, InputIterator last, const Compare& compare,
641
+ Container&& cont, const Alloc& a);
642
  ```
643
 
644
  *Effects:* Initializes `c` with `std::move(cont)` as the first argument
645
  and `a` as the second argument, and initializes `comp` with `compare`;
646
  calls `c.insert(c.end(), first, last)`; and finally calls
647
  `make_heap(c.begin(), c.end(), comp)`.
648
 
649
  ``` cpp
650
  template<container-compatible-range<T> R, class Alloc>
651
+ constexpr priority_queue(from_range_t, R&& rg, const Compare& compare, const Alloc& a);
652
  ```
653
 
654
  *Effects:* Initializes `comp` with `compare` and `c` with
655
  `ranges::to<Container>(std::forward<R>(rg), a)`; calls
656
  `make_heap(c.begin(), c.end(), comp)`.
657
 
658
  ``` cpp
659
  template<container-compatible-range<T> R, class Alloc>
660
+ constexpr priority_queue(from_range_t, R&& rg, const Alloc& a);
661
  ```
662
 
663
  *Effects:* Initializes `c` with
664
+ `ranges::to<Container>(std::forward<R>(rg), a)` and value-initializes
665
+ `comp`; calls `make_heap(c.begin(), c.end(), comp)`.
666
 
667
  #### Members <a id="priqueue.members">[[priqueue.members]]</a>
668
 
669
  ``` cpp
670
+ constexpr void push(const value_type& x);
671
  ```
672
 
673
  *Effects:* As if by:
674
 
675
  ``` cpp
676
  c.push_back(x);
677
  push_heap(c.begin(), c.end(), comp);
678
  ```
679
 
680
  ``` cpp
681
+ constexpr void push(value_type&& x);
682
  ```
683
 
684
  *Effects:* As if by:
685
 
686
  ``` cpp
 
688
  push_heap(c.begin(), c.end(), comp);
689
  ```
690
 
691
  ``` cpp
692
  template<container-compatible-range<T> R>
693
+ constexpr void push_range(R&& rg);
694
  ```
695
 
696
  *Effects:* Inserts all elements of `rg` in `c` via
697
  `c.append_range(std::forward<R>(rg))` if that is a valid expression, or
698
  `ranges::copy(rg, back_inserter(c))` otherwise. Then restores the heap
699
  property as if by `make_heap(c.begin(), c.end(), comp)`.
700
 
701
  *Ensures:* `is_heap(c.begin(), c.end(), comp)` is `true`.
702
 
703
  ``` cpp
704
+ template<class... Args> constexpr void emplace(Args&&... args);
705
  ```
706
 
707
  *Effects:* As if by:
708
 
709
  ``` cpp
710
  c.emplace_back(std::forward<Args>(args)...);
711
  push_heap(c.begin(), c.end(), comp);
712
  ```
713
 
714
  ``` cpp
715
+ constexpr void pop();
716
  ```
717
 
718
  *Effects:* As if by:
719
 
720
  ``` cpp
 
724
 
725
  #### Specialized algorithms <a id="priqueue.special">[[priqueue.special]]</a>
726
 
727
  ``` cpp
728
  template<class T, class Container, class Compare>
729
+ constexpr void swap(priority_queue<T, Container, Compare>& x,
730
  priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
731
  ```
732
 
733
  *Constraints:* `is_swappable_v<Container>` is `true` and
734
  `is_swappable_v<Compare>` is `true`.
735
 
736
  *Effects:* As if by `x.swap(y)`.
737
 
738
+ ### Header `<stack>` synopsis <a id="stack.syn">[[stack.syn]]</a>
739
+
740
+ ``` cpp
741
+ #include <compare> // see [compare.syn]
742
+ #include <initializer_list> // see [initializer.list.syn]
743
+
744
+ namespace std {
745
+ // [stack], class template stack
746
+ template<class T, class Container = deque<T>> class stack;
747
+
748
+ template<class T, class Container>
749
+ constexpr bool operator==(const stack<T, Container>& x, const stack<T, Container>& y);
750
+ template<class T, class Container>
751
+ constexpr bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y);
752
+ template<class T, class Container>
753
+ constexpr bool operator< (const stack<T, Container>& x, const stack<T, Container>& y);
754
+ template<class T, class Container>
755
+ constexpr bool operator> (const stack<T, Container>& x, const stack<T, Container>& y);
756
+ template<class T, class Container>
757
+ constexpr bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y);
758
+ template<class T, class Container>
759
+ constexpr bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y);
760
+ template<class T, three_way_comparable Container>
761
+ constexpr compare_three_way_result_t<Container>
762
+ operator<=>(const stack<T, Container>& x, const stack<T, Container>& y);
763
+
764
+ template<class T, class Container>
765
+ constexpr void swap(stack<T, Container>& x, stack<T, Container>& y)
766
+ noexcept(noexcept(x.swap(y)));
767
+ template<class T, class Container, class Alloc>
768
+ struct uses_allocator<stack<T, Container>, Alloc>;
769
+
770
+ // [container.adaptors.format], formatter specialization for stack
771
+ template<class charT, class T, formattable<charT> Container>
772
+ struct formatter<stack<T, Container>, charT>;
773
+ }
774
+ ```
775
+
776
  ### Class template `stack` <a id="stack">[[stack]]</a>
777
 
778
  #### General <a id="stack.general">[[stack.general]]</a>
779
 
780
  Any sequence container supporting operations `back()`, `push_back()` and
 
786
  ``` cpp
787
  namespace std {
788
  template<class T, class Container = deque<T>>
789
  class stack {
790
  public:
791
+ using value_type = Container::value_type;
792
+ using reference = Container::reference;
793
+ using const_reference = Container::const_reference;
794
+ using size_type = Container::size_type;
795
  using container_type = Container;
796
 
797
  protected:
798
  Container c;
799
 
800
  public:
801
+ constexpr stack() : stack(Container()) {}
802
+ constexpr explicit stack(const Container&);
803
+ constexpr explicit stack(Container&&);
804
+ template<class InputIterator> constexpr stack(InputIterator first, InputIterator last);
805
+ template<container-compatible-range<T> R>
806
+ constexpr stack(from_range_t, R&& rg);
807
+ template<class Alloc> constexpr explicit stack(const Alloc&);
808
+ template<class Alloc> constexpr stack(const Container&, const Alloc&);
809
+ template<class Alloc> constexpr stack(Container&&, const Alloc&);
810
+ template<class Alloc> constexpr stack(const stack&, const Alloc&);
811
+ template<class Alloc> constexpr stack(stack&&, const Alloc&);
812
  template<class InputIterator, class Alloc>
813
+ constexpr stack(InputIterator first, InputIterator last, const Alloc&);
814
  template<container-compatible-range<T> R, class Alloc>
815
+ constexpr stack(from_range_t, R&& rg, const Alloc&);
816
 
817
+ constexpr bool empty() const { return c.empty(); }
818
+ constexpr size_type size() const { return c.size(); }
819
+ constexpr reference top() { return c.back(); }
820
+ constexpr const_reference top() const { return c.back(); }
821
+ constexpr void push(const value_type& x) { c.push_back(x); }
822
+ constexpr void push(value_type&& x) { c.push_back(std::move(x)); }
823
  template<container-compatible-range<T> R>
824
+ constexpr void push_range(R&& rg);
825
  template<class... Args>
826
+ constexpr decltype(auto) emplace(Args&&... args)
827
  { return c.emplace_back(std::forward<Args>(args)...); }
828
+ constexpr void pop() { c.pop_back(); }
829
+ constexpr void swap(stack& s) noexcept(is_nothrow_swappable_v<Container>)
830
  { using std::swap; swap(c, s.c); }
831
  };
832
 
833
  template<class Container>
834
  stack(Container) -> stack<typename Container::value_type, Container>;
 
858
  ```
859
 
860
  #### Constructors <a id="stack.cons">[[stack.cons]]</a>
861
 
862
  ``` cpp
863
+ constexpr explicit stack(const Container& cont);
864
  ```
865
 
866
  *Effects:* Initializes `c` with `cont`.
867
 
868
  ``` cpp
869
+ constexpr explicit stack(Container&& cont);
870
  ```
871
 
872
  *Effects:* Initializes `c` with `std::move(cont)`.
873
 
874
  ``` cpp
875
  template<class InputIterator>
876
+ constexpr stack(InputIterator first, InputIterator last);
877
  ```
878
 
879
  *Effects:* Initializes `c` with `first` as the first argument and `last`
880
  as the second argument.
881
 
882
  ``` cpp
883
  template<container-compatible-range<T> R>
884
+ constexpr stack(from_range_t, R&& rg);
885
  ```
886
 
887
  *Effects:* Initializes `c` with
888
  `ranges::to<Container>(std::forward<R>(rg))`.
889
 
 
891
 
892
  If `uses_allocator_v<container_type, Alloc>` is `false` the constructors
893
  in this subclause shall not participate in overload resolution.
894
 
895
  ``` cpp
896
+ template<class Alloc> constexpr explicit stack(const Alloc& a);
897
  ```
898
 
899
  *Effects:* Initializes `c` with `a`.
900
 
901
  ``` cpp
902
+ template<class Alloc> constexpr stack(const container_type& cont, const Alloc& a);
903
  ```
904
 
905
  *Effects:* Initializes `c` with `cont` as the first argument and `a` as
906
  the second argument.
907
 
908
  ``` cpp
909
+ template<class Alloc> constexpr stack(container_type&& cont, const Alloc& a);
910
  ```
911
 
912
  *Effects:* Initializes `c` with `std::move(cont)` as the first argument
913
  and `a` as the second argument.
914
 
915
  ``` cpp
916
+ template<class Alloc> constexpr stack(const stack& s, const Alloc& a);
917
  ```
918
 
919
  *Effects:* Initializes `c` with `s.c` as the first argument and `a` as
920
  the second argument.
921
 
922
  ``` cpp
923
+ template<class Alloc> constexpr stack(stack&& s, const Alloc& a);
924
  ```
925
 
926
  *Effects:* Initializes `c` with `std::move(s.c)` as the first argument
927
  and `a` as the second argument.
928
 
929
  ``` cpp
930
  template<class InputIterator, class Alloc>
931
+ constexpr stack(InputIterator first, InputIterator last, const Alloc& alloc);
932
  ```
933
 
934
  *Effects:* Initializes `c` with `first` as the first argument, `last` as
935
  the second argument, and `alloc` as the third argument.
936
 
937
  ``` cpp
938
  template<container-compatible-range<T> R, class Alloc>
939
+ constexpr stack(from_range_t, R&& rg, const Alloc& a);
940
  ```
941
 
942
  *Effects:* Initializes `c` with
943
  `ranges::to<Container>(std::forward<R>(rg), a)`.
944
 
945
  #### Modifiers <a id="stack.mod">[[stack.mod]]</a>
946
 
947
  ``` cpp
948
  template<container-compatible-range<T> R>
949
+ constexpr void push_range(R&& rg);
950
  ```
951
 
952
  *Effects:* Equivalent to `c.append_range(std::forward<R>(rg))` if that
953
  is a valid expression, otherwise `ranges::copy(rg, back_inserter(c))`.
954
 
955
  #### Operators <a id="stack.ops">[[stack.ops]]</a>
956
 
957
  ``` cpp
958
  template<class T, class Container>
959
+ constexpr bool operator==(const stack<T, Container>& x, const stack<T, Container>& y);
960
  ```
961
 
962
  *Returns:* `x.c == y.c`.
963
 
964
  ``` cpp
965
  template<class T, class Container>
966
+ constexpr bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y);
967
  ```
968
 
969
  *Returns:* `x.c != y.c`.
970
 
971
  ``` cpp
972
  template<class T, class Container>
973
+ constexpr bool operator< (const stack<T, Container>& x, const stack<T, Container>& y);
974
  ```
975
 
976
  *Returns:* `x.c < y.c`.
977
 
978
  ``` cpp
979
  template<class T, class Container>
980
+ constexpr bool operator> (const stack<T, Container>& x, const stack<T, Container>& y);
981
  ```
982
 
983
  *Returns:* `x.c > y.c`.
984
 
985
  ``` cpp
986
  template<class T, class Container>
987
+ constexpr bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y);
988
  ```
989
 
990
  *Returns:* `x.c <= y.c`.
991
 
992
  ``` cpp
993
  template<class T, class Container>
994
+ constexpr bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y);
995
  ```
996
 
997
  *Returns:* `x.c >= y.c`.
998
 
999
  ``` cpp
1000
  template<class T, three_way_comparable Container>
1001
+ constexpr compare_three_way_result_t<Container>
1002
  operator<=>(const stack<T, Container>& x, const stack<T, Container>& y);
1003
  ```
1004
 
1005
  *Returns:* `x.c <=> y.c`.
1006
 
1007
  #### Specialized algorithms <a id="stack.special">[[stack.special]]</a>
1008
 
1009
  ``` cpp
1010
  template<class T, class Container>
1011
+ constexpr void swap(stack<T, Container>& x, stack<T, Container>& y)
1012
+ noexcept(noexcept(x.swap(y)));
1013
  ```
1014
 
1015
  *Constraints:* `is_swappable_v<Container>` is `true`.
1016
 
1017
  *Effects:* As if by `x.swap(y)`.
1018
 
1019
+ ### Header `<flat_map>` synopsis <a id="flat.map.syn">[[flat.map.syn]]</a>
1020
+
1021
+ ``` cpp
1022
+ #include <compare> // see [compare.syn]
1023
+ #include <initializer_list> // see [initializer.list.syn]
1024
+
1025
+ namespace std {
1026
+ // [flat.map], class template flat_map
1027
+ template<class Key, class T, class Compare = less<Key>,
1028
+ class KeyContainer = vector<Key>, class MappedContainer = vector<T>>
1029
+ class flat_map;
1030
+
1031
+ struct sorted_unique_t { explicit sorted_unique_t() = default; };
1032
+ inline constexpr sorted_unique_t sorted_unique{};
1033
+
1034
+ template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
1035
+ class Allocator>
1036
+ struct uses_allocator<flat_map<Key, T, Compare, KeyContainer, MappedContainer>,
1037
+ Allocator>;
1038
+
1039
+ // [flat.map.erasure], erasure for flat_map
1040
+ template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
1041
+ class Predicate>
1042
+ constexpr typename flat_map<Key, T, Compare, KeyContainer, MappedContainer>::size_type
1043
+ erase_if(flat_map<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
1044
+
1045
+ // [flat.multimap], class template flat_multimap
1046
+ template<class Key, class T, class Compare = less<Key>,
1047
+ class KeyContainer = vector<Key>, class MappedContainer = vector<T>>
1048
+ class flat_multimap;
1049
+
1050
+ struct sorted_equivalent_t { explicit sorted_equivalent_t() = default; };
1051
+ inline constexpr sorted_equivalent_t sorted_equivalent{};
1052
+
1053
+ template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
1054
+ class Allocator>
1055
+ struct uses_allocator<flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>,
1056
+ Allocator>;
1057
+
1058
+ // [flat.multimap.erasure], erasure for flat_multimap
1059
+ template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
1060
+ class Predicate>
1061
+ constexpr typename flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>::size_type
1062
+ erase_if(flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
1063
+ }
1064
+ ```
1065
+
1066
  ### Class template `flat_map` <a id="flat.map">[[flat.map]]</a>
1067
 
1068
  #### Overview <a id="flat.map.overview">[[flat.map.overview]]</a>
1069
 
1070
  A `flat_map` is a container adaptor that provides an associative
 
1129
 
1130
  The effect of calling a constructor that takes both `key_container_type`
1131
  and `mapped_container_type` arguments with containers of different sizes
1132
  is undefined.
1133
 
1134
+ The effect of calling a member function that takes a `sorted_unique_t`
1135
+ argument with a container, containers, or range that is not sorted with
1136
+ respect to `key_comp()`, or that contains equal elements, is undefined.
1137
+
1138
+ The types `iterator` and `const_iterator` meet the constexpr iterator
1139
+ requirements [[iterator.requirements.general]].
1140
 
1141
  #### Definition <a id="flat.map.defn">[[flat.map.defn]]</a>
1142
 
1143
  ``` cpp
1144
  namespace std {
 
1163
  using mapped_container_type = MappedContainer;
1164
 
1165
  class value_compare {
1166
  private:
1167
  key_compare comp; // exposition only
1168
+ constexpr value_compare(key_compare c) : comp(c) { } // exposition only
1169
 
1170
  public:
1171
+ constexpr bool operator()(const_reference x, const_reference y) const {
1172
  return comp(x.first, y.first);
1173
  }
1174
  };
1175
 
1176
  struct containers {
1177
  key_container_type keys;
1178
  mapped_container_type values;
1179
  };
1180
 
1181
+ // [flat.map.cons], constructors
1182
+ constexpr flat_map() : flat_map(key_compare()) { }
1183
 
1184
+ constexpr explicit flat_map(const key_compare& comp)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1185
  : c(), compare(comp) { }
1186
+
1187
+ constexpr flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
1188
+ const key_compare& comp = key_compare());
1189
+
1190
+ constexpr flat_map(sorted_unique_t, key_container_type key_cont,
1191
+ mapped_container_type mapped_cont,
1192
+ const key_compare& comp = key_compare());
1193
 
1194
  template<class InputIterator>
1195
+ constexpr flat_map(InputIterator first, InputIterator last,
1196
+ const key_compare& comp = key_compare())
1197
  : c(), compare(comp) { insert(first, last); }
1198
+
1199
+ template<class InputIterator>
1200
+ constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last,
1201
+ const key_compare& comp = key_compare())
1202
+ : c(), compare(comp) { insert(sorted_unique, first, last); }
1203
 
1204
  template<container-compatible-range<value_type> R>
1205
+ constexpr flat_map(from_range_t, R&& rg)
1206
+ : flat_map(from_range, std::forward<R>(rg), key_compare()) { }
 
 
1207
  template<container-compatible-range<value_type> R>
1208
+ constexpr flat_map(from_range_t, R&& rg, const key_compare& comp)
1209
  : flat_map(comp) { insert_range(std::forward<R>(rg)); }
 
 
1210
 
1211
+ constexpr flat_map(initializer_list<value_type> il, const key_compare& comp = key_compare())
 
 
 
 
 
 
 
 
 
 
1212
  : flat_map(il.begin(), il.end(), comp) { }
 
 
 
 
1213
 
1214
+ constexpr flat_map(sorted_unique_t, initializer_list<value_type> il,
1215
  const key_compare& comp = key_compare())
1216
+ : flat_map(sorted_unique, il.begin(), il.end(), comp) { }
 
 
 
 
 
1217
 
1218
+ // [flat.map.cons.alloc], constructors with allocators
1219
+
1220
+ template<class Alloc>
1221
+ constexpr explicit flat_map(const Alloc& a);
1222
+ template<class Alloc>
1223
+ constexpr flat_map(const key_compare& comp, const Alloc& a);
1224
+ template<class Alloc>
1225
+ constexpr flat_map(const key_container_type& key_cont,
1226
+ const mapped_container_type& mapped_cont,
1227
+ const Alloc& a);
1228
+ template<class Alloc>
1229
+ constexpr flat_map(const key_container_type& key_cont,
1230
+ const mapped_container_type& mapped_cont,
1231
+ const key_compare& comp, const Alloc& a);
1232
+ template<class Alloc>
1233
+ constexpr flat_map(sorted_unique_t, const key_container_type& key_cont,
1234
+ const mapped_container_type& mapped_cont, const Alloc& a);
1235
+ template<class Alloc>
1236
+ constexpr flat_map(sorted_unique_t, const key_container_type& key_cont,
1237
+ const mapped_container_type& mapped_cont, const key_compare& comp,
1238
+ const Alloc& a);
1239
+ template<class Alloc>
1240
+ constexpr flat_map(const flat_map&, const Alloc& a);
1241
+ template<class Alloc>
1242
+ constexpr flat_map(flat_map&&, const Alloc& a);
1243
+ template<class InputIterator, class Alloc>
1244
+ constexpr flat_map(InputIterator first, InputIterator last, const Alloc& a);
1245
+ template<class InputIterator, class Alloc>
1246
+ constexpr flat_map(InputIterator first, InputIterator last,
1247
+ const key_compare& comp, const Alloc& a);
1248
+ template<class InputIterator, class Alloc>
1249
+ constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last,
1250
+ const Alloc& a);
1251
+ template<class InputIterator, class Alloc>
1252
+ constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last,
1253
+ const key_compare& comp, const Alloc& a);
1254
+ template<container-compatible-range<value_type> R, class Alloc>
1255
+ constexpr flat_map(from_range_t, R&& rg, const Alloc& a);
1256
+ template<container-compatible-range<value_type> R, class Alloc>
1257
+ constexpr flat_map(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
1258
+ template<class Alloc>
1259
+ constexpr flat_map(initializer_list<value_type> il, const Alloc& a);
1260
+ template<class Alloc>
1261
+ constexpr flat_map(initializer_list<value_type> il, const key_compare& comp,
1262
+ const Alloc& a);
1263
+ template<class Alloc>
1264
+ constexpr flat_map(sorted_unique_t, initializer_list<value_type> il, const Alloc& a);
1265
+ template<class Alloc>
1266
+ constexpr flat_map(sorted_unique_t, initializer_list<value_type> il,
1267
+ const key_compare& comp, const Alloc& a);
1268
+
1269
+ constexpr flat_map& operator=(initializer_list<value_type>);
1270
 
1271
  // iterators
1272
+ constexpr iterator begin() noexcept;
1273
+ constexpr const_iterator begin() const noexcept;
1274
+ constexpr iterator end() noexcept;
1275
+ constexpr const_iterator end() const noexcept;
1276
 
1277
+ constexpr reverse_iterator rbegin() noexcept;
1278
+ constexpr const_reverse_iterator rbegin() const noexcept;
1279
+ constexpr reverse_iterator rend() noexcept;
1280
+ constexpr const_reverse_iterator rend() const noexcept;
1281
 
1282
+ constexpr const_iterator cbegin() const noexcept;
1283
+ constexpr const_iterator cend() const noexcept;
1284
+ constexpr const_reverse_iterator crbegin() const noexcept;
1285
+ constexpr const_reverse_iterator crend() const noexcept;
1286
 
1287
  // [flat.map.capacity], capacity
1288
+ constexpr bool empty() const noexcept;
1289
+ constexpr size_type size() const noexcept;
1290
+ constexpr size_type max_size() const noexcept;
1291
 
1292
  // [flat.map.access], element access
1293
+ constexpr mapped_type& operator[](const key_type& x);
1294
+ constexpr mapped_type& operator[](key_type&& x);
1295
+ template<class K> constexpr mapped_type& operator[](K&& x);
1296
+ constexpr mapped_type& at(const key_type& x);
1297
+ constexpr const mapped_type& at(const key_type& x) const;
1298
+ template<class K> constexpr mapped_type& at(const K& x);
1299
+ template<class K> constexpr const mapped_type& at(const K& x) const;
1300
 
1301
  // [flat.map.modifiers], modifiers
1302
+ template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
1303
  template<class... Args>
1304
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
1305
 
1306
+ constexpr pair<iterator, bool> insert(const value_type& x)
1307
  { return emplace(x); }
1308
+ constexpr pair<iterator, bool> insert(value_type&& x)
1309
  { return emplace(std::move(x)); }
1310
+ constexpr iterator insert(const_iterator position, const value_type& x)
1311
  { return emplace_hint(position, x); }
1312
+ constexpr iterator insert(const_iterator position, value_type&& x)
1313
  { return emplace_hint(position, std::move(x)); }
1314
 
1315
+ template<class P> constexpr pair<iterator, bool> insert(P&& x);
1316
  template<class P>
1317
+ constexpr iterator insert(const_iterator position, P&&);
1318
  template<class InputIterator>
1319
+ constexpr void insert(InputIterator first, InputIterator last);
1320
  template<class InputIterator>
1321
+ constexpr void insert(sorted_unique_t, InputIterator first, InputIterator last);
1322
  template<container-compatible-range<value_type> R>
1323
+ constexpr void insert_range(R&& rg);
1324
 
1325
+ constexpr void insert(initializer_list<value_type> il)
1326
  { insert(il.begin(), il.end()); }
1327
+ constexpr void insert(sorted_unique_t, initializer_list<value_type> il)
1328
+ { insert(sorted_unique, il.begin(), il.end()); }
1329
 
1330
+ constexpr containers extract() &&;
1331
+ constexpr void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);
1332
 
1333
  template<class... Args>
1334
+ constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
1335
  template<class... Args>
1336
+ constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
1337
  template<class K, class... Args>
1338
+ constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args);
1339
  template<class... Args>
1340
+ constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
1341
  template<class... Args>
1342
+ constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
1343
  template<class K, class... Args>
1344
+ constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
1345
  template<class M>
1346
+ constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
1347
  template<class M>
1348
+ constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
1349
  template<class K, class M>
1350
+ constexpr pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
1351
  template<class M>
1352
+ constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
1353
  template<class M>
1354
+ constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
1355
  template<class K, class M>
1356
+ constexpr iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
1357
 
1358
+ constexpr iterator erase(iterator position);
1359
+ constexpr iterator erase(const_iterator position);
1360
+ constexpr size_type erase(const key_type& x);
1361
+ template<class K> constexpr size_type erase(K&& x);
1362
+ constexpr iterator erase(const_iterator first, const_iterator last);
1363
 
1364
+ constexpr void swap(flat_map& y) noexcept;
1365
+ constexpr void clear() noexcept;
1366
 
1367
  // observers
1368
+ constexpr key_compare key_comp() const;
1369
+ constexpr value_compare value_comp() const;
1370
 
1371
+ constexpr const key_container_type& keys() const noexcept { return c.keys; }
1372
+ constexpr const mapped_container_type& values() const noexcept { return c.values; }
1373
 
1374
  // map operations
1375
+ constexpr iterator find(const key_type& x);
1376
+ constexpr const_iterator find(const key_type& x) const;
1377
+ template<class K> constexpr iterator find(const K& x);
1378
+ template<class K> constexpr const_iterator find(const K& x) const;
1379
 
1380
+ constexpr size_type count(const key_type& x) const;
1381
+ template<class K> constexpr size_type count(const K& x) const;
1382
 
1383
+ constexpr bool contains(const key_type& x) const;
1384
+ template<class K> constexpr bool contains(const K& x) const;
1385
 
1386
+ constexpr iterator lower_bound(const key_type& x);
1387
+ constexpr const_iterator lower_bound(const key_type& x) const;
1388
+ template<class K> constexpr iterator lower_bound(const K& x);
1389
+ template<class K> constexpr const_iterator lower_bound(const K& x) const;
1390
 
1391
+ constexpr iterator upper_bound(const key_type& x);
1392
+ constexpr const_iterator upper_bound(const key_type& x) const;
1393
+ template<class K> constexpr iterator upper_bound(const K& x);
1394
+ template<class K> constexpr const_iterator upper_bound(const K& x) const;
1395
 
1396
+ constexpr pair<iterator, iterator> equal_range(const key_type& x);
1397
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
1398
+ template<class K> constexpr pair<iterator, iterator> equal_range(const K& x);
1399
+ template<class K>
1400
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
1401
 
1402
+ friend constexpr bool operator==(const flat_map& x, const flat_map& y);
1403
 
1404
+ friend constexpr synth-three-way-result<value_type>
1405
  operator<=>(const flat_map& x, const flat_map& y);
1406
 
1407
+ friend constexpr void swap(flat_map& x, flat_map& y) noexcept
1408
  { x.swap(y); }
1409
 
1410
  private:
1411
  containers c; // exposition only
1412
  key_compare compare; // exposition only
1413
 
1414
+ struct key-equiv { // exposition only
1415
+ constexpr key-equiv(key_compare c) : comp(c) { }
1416
+ constexpr bool operator()(const_reference x, const_reference y) const {
1417
  return !comp(x.first, y.first) && !comp(y.first, x.first);
1418
  }
1419
  key_compare comp;
1420
  };
1421
  };
 
1492
  specified.
1493
 
1494
  #### Constructors <a id="flat.map.cons">[[flat.map.cons]]</a>
1495
 
1496
  ``` cpp
1497
+ constexpr flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
1498
  const key_compare& comp = key_compare());
1499
  ```
1500
 
1501
+ *Effects:* Initializes *`c`*`.keys` with `std::move(key_cont)`,
1502
+ *`c`*`.values` with `std::move(mapped_cont)`, and *compare* with `comp`;
1503
+ sorts the range \[`begin()`, `end()`) with respect to `value_comp()`;
1504
+ and finally erases the duplicate elements as if by:
1505
 
1506
  ``` cpp
1507
+ auto zv = views::zip(c.keys, c.values);
1508
+ auto it = ranges::unique(zv, key-equiv(compare)).begin();
1509
  auto dist = distance(zv.begin(), it);
1510
  c.keys.erase(c.keys.begin() + dist, c.keys.end());
1511
  c.values.erase(c.values.begin() + dist, c.values.end());
1512
  ```
1513
 
1514
  *Complexity:* Linear in N if the container arguments are already sorted
1515
  with respect to `value_comp()` and otherwise N log N, where N is the
1516
  value of `key_cont.size()` before this call.
1517
 
1518
  ``` cpp
1519
+ constexpr flat_map(sorted_unique_t, key_container_type key_cont, mapped_container_type mapped_cont,
1520
+ const key_compare& comp = key_compare());
 
 
 
 
1521
  ```
1522
 
1523
+ *Effects:* Initializes *`c`*`.keys` with `std::move(key_cont)`,
1524
+ *`c`*`.values` with `std::move(mapped_cont)`, and *compare* with `comp`.
1525
+
1526
+ *Complexity:* Constant.
1527
+
1528
+ #### Constructors with allocators <a id="flat.map.cons.alloc">[[flat.map.cons.alloc]]</a>
1529
+
1530
+ The constructors in this subclause shall not participate in overload
1531
+ resolution unless `uses_allocator_v<key_container_type, Alloc>` is
1532
+ `true` and `uses_allocator_v<mapped_container_type, Alloc>` is `true`.
1533
+
1534
+ ``` cpp
1535
+ template<class Alloc>
1536
+ constexpr flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
1537
+ const Alloc& a);
1538
+ template<class Alloc>
1539
+ constexpr flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
1540
+ const key_compare& comp, const Alloc& a);
1541
+ ```
1542
 
1543
  *Effects:* Equivalent to `flat_map(key_cont, mapped_cont)` and
1544
  `flat_map(key_cont, mapped_cont, comp)`, respectively, except that
1545
+ *`c`*`.keys` and *`c`*`.values` are constructed with uses-allocator
1546
  construction [[allocator.uses.construction]].
1547
 
1548
  *Complexity:* Same as `flat_map(key_cont, mapped_cont)` and
1549
  `flat_map(key_cont, mapped_cont, comp)`, respectively.
1550
 
1551
  ``` cpp
1552
+ template<class Alloc>
1553
+ constexpr flat_map(sorted_unique_t, const key_container_type& key_cont,
1554
+ const mapped_container_type& mapped_cont, const Alloc& a);
1555
+ template<class Alloc>
1556
+ constexpr flat_map(sorted_unique_t, const key_container_type& key_cont,
 
 
 
 
 
 
 
 
 
 
1557
  const mapped_container_type& mapped_cont, const key_compare& comp,
1558
+ const Alloc& a);
1559
  ```
1560
 
1561
+ *Effects:* Equivalent to
1562
+ `flat_map(sorted_unique, key_cont, mapped_cont)` and
1563
+ `flat_map(sorted_unique, key_cont, mapped_cont, comp)`, respectively,
1564
+ except that *`c`*`.keys` and *`c`*`.values` are constructed with
1565
+ uses-allocator construction [[allocator.uses.construction]].
 
 
 
1566
 
1567
  *Complexity:* Linear.
1568
 
1569
  ``` cpp
1570
+ template<class Alloc>
1571
+ constexpr explicit flat_map(const Alloc& a);
1572
+ template<class Alloc>
1573
+ constexpr flat_map(const key_compare& comp, const Alloc& a);
1574
+ template<class Alloc>
1575
+ constexpr flat_map(const flat_map&, const Alloc& a);
1576
+ template<class Alloc>
1577
+ constexpr flat_map(flat_map&&, const Alloc& a);
1578
+ template<class InputIterator, class Alloc>
1579
+ constexpr flat_map(InputIterator first, InputIterator last, const Alloc& a);
1580
+ template<class InputIterator, class Alloc>
1581
+ constexpr flat_map(InputIterator first, InputIterator last, const key_compare& comp,
1582
+ const Alloc& a);
1583
+ template<class InputIterator, class Alloc>
1584
+ constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last, const Alloc& a);
1585
+ template<class InputIterator, class Alloc>
1586
+ constexpr flat_map(sorted_unique_t, InputIterator first, InputIterator last,
1587
+ const key_compare& comp, const Alloc& a);
1588
+ template<container-compatible-range<value_type> R, class Alloc>
1589
+ constexpr flat_map(from_range_t, R&& rg, const Alloc& a);
1590
+ template<container-compatible-range<value_type> R, class Alloc>
1591
+ constexpr flat_map(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
1592
+ template<class Alloc>
1593
+ constexpr flat_map(initializer_list<value_type> il, const Alloc& a);
1594
+ template<class Alloc>
1595
+ constexpr flat_map(initializer_list<value_type> il, const key_compare& comp, const Alloc& a);
1596
+ template<class Alloc>
1597
+ constexpr flat_map(sorted_unique_t, initializer_list<value_type> il, const Alloc& a);
1598
+ template<class Alloc>
1599
+ constexpr flat_map(sorted_unique_t, initializer_list<value_type> il,
1600
+ const key_compare& comp, const Alloc& a);
1601
  ```
1602
 
 
 
 
 
1603
  *Effects:* Equivalent to the corresponding non-allocator constructors
1604
+ except that *`c`*`.keys` and *`c`*`.values` are constructed with
1605
+ uses-allocator construction [[allocator.uses.construction]].
1606
 
1607
  #### Capacity <a id="flat.map.capacity">[[flat.map.capacity]]</a>
1608
 
1609
  ``` cpp
1610
+ constexpr size_type size() const noexcept;
1611
  ```
1612
 
1613
+ *Returns:* *`c`*`.keys.size()`.
1614
 
1615
  ``` cpp
1616
+ constexpr size_type max_size() const noexcept;
1617
  ```
1618
 
1619
+ *Returns:*
1620
+ `min<size_type>(`*`c`*`.keys.max_size(), `*`c`*`.values.max_size())`.
1621
 
1622
  #### Access <a id="flat.map.access">[[flat.map.access]]</a>
1623
 
1624
  ``` cpp
1625
+ constexpr mapped_type& operator[](const key_type& x);
1626
  ```
1627
 
1628
  *Effects:* Equivalent to: `return try_emplace(x).first->second;`
1629
 
1630
  ``` cpp
1631
+ constexpr mapped_type& operator[](key_type&& x);
1632
  ```
1633
 
1634
  *Effects:* Equivalent to:
1635
  `return try_emplace(std::move(x)).first->second;`
1636
 
1637
  ``` cpp
1638
+ template<class K> constexpr mapped_type& operator[](K&& x);
1639
  ```
1640
 
1641
  *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
1642
  denotes a type.
1643
 
1644
  *Effects:* Equivalent to:
1645
  `return try_emplace(std::forward<K>(x)).first->second;`
1646
 
1647
  ``` cpp
1648
+ constexpr mapped_type& at(const key_type& x);
1649
+ constexpr const mapped_type& at(const key_type& x) const;
1650
  ```
1651
 
1652
  *Returns:* A reference to the `mapped_type` corresponding to `x` in
1653
  `*this`.
1654
 
 
1656
  is present.
1657
 
1658
  *Complexity:* Logarithmic.
1659
 
1660
  ``` cpp
1661
+ template<class K> constexpr mapped_type& at(const K& x);
1662
+ template<class K> constexpr const mapped_type& at(const K& x) const;
1663
  ```
1664
 
1665
  *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
1666
  denotes a type.
1667
 
 
1677
  *Complexity:* Logarithmic.
1678
 
1679
  #### Modifiers <a id="flat.map.modifiers">[[flat.map.modifiers]]</a>
1680
 
1681
  ``` cpp
1682
+ template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
1683
  ```
1684
 
1685
  *Constraints:*
1686
  `is_constructible_v<pair<key_type, mapped_type>, Args...>` is `true`.
1687
 
 
1700
  *Returns:* The `bool` component of the returned pair is `true` if and
1701
  only if the insertion took place, and the iterator component of the pair
1702
  points to the element with key equivalent to `t.first`.
1703
 
1704
  ``` cpp
1705
+ template<class P> constexpr pair<iterator, bool> insert(P&& x);
1706
+ template<class P> constexpr iterator insert(const_iterator position, P&& x);
1707
  ```
1708
 
1709
  *Constraints:* `is_constructible_v<pair<key_type, mapped_type>, P>` is
1710
  `true`.
1711
 
 
1713
  `return emplace(std::forward<P>(x));`. The second form is equivalent to
1714
  `return emplace_hint(position, std::forward<P>(x));`.
1715
 
1716
  ``` cpp
1717
  template<class InputIterator>
1718
+ constexpr void insert(InputIterator first, InputIterator last);
1719
  ```
1720
 
1721
+ *Effects:* Adds elements to *c* as if by:
1722
 
1723
  ``` cpp
1724
  for (; first != last; ++first) {
1725
  value_type value = *first;
1726
  c.keys.insert(c.keys.end(), std::move(value.first));
 
1732
  `value_comp()`; merges the resulting sorted range and the sorted range
1733
  of pre-existing elements into a single sorted range; and finally erases
1734
  the duplicate elements as if by:
1735
 
1736
  ``` cpp
1737
+ auto zv = views::zip(c.keys, c.values);
1738
+ auto it = ranges::unique(zv, key-equiv(compare)).begin();
1739
  auto dist = distance(zv.begin(), it);
1740
  c.keys.erase(c.keys.begin() + dist, c.keys.end());
1741
  c.values.erase(c.values.begin() + dist, c.values.end());
1742
  ```
1743
 
 
1747
  *Remarks:* Since this operation performs an in-place merge, it may
1748
  allocate memory.
1749
 
1750
  ``` cpp
1751
  template<class InputIterator>
1752
+ constexpr void insert(sorted_unique_t, InputIterator first, InputIterator last);
1753
  ```
1754
 
1755
+ *Effects:* Equivalent to `insert(first, last)`.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1756
 
1757
  *Complexity:* Linear in N, where N is `size()` after the operation.
1758
 
 
 
 
1759
  ``` cpp
1760
  template<container-compatible-range<value_type> R>
1761
+ constexpr void insert_range(R&& rg);
1762
  ```
1763
 
1764
+ *Effects:* Adds elements to *c* as if by:
1765
 
1766
  ``` cpp
1767
  for (const auto& e : rg) {
1768
  c.keys.insert(c.keys.end(), e.first);
1769
  c.values.insert(c.values.end(), e.second);
 
1774
  `value_comp()`; merges the resulting sorted range and the sorted range
1775
  of pre-existing elements into a single sorted range; and finally erases
1776
  the duplicate elements as if by:
1777
 
1778
  ``` cpp
1779
+ auto zv = views::zip(c.keys, c.values);
1780
+ auto it = ranges::unique(zv, key-equiv(compare)).begin();
1781
  auto dist = distance(zv.begin(), it);
1782
  c.keys.erase(c.keys.begin() + dist, c.keys.end());
1783
  c.values.erase(c.values.begin() + dist, c.values.end());
1784
  ```
1785
 
 
1789
  *Remarks:* Since this operation performs an in-place merge, it may
1790
  allocate memory.
1791
 
1792
  ``` cpp
1793
  template<class... Args>
1794
+ constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
1795
  template<class... Args>
1796
+ constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
1797
  template<class... Args>
1798
+ constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
1799
  template<class... Args>
1800
+ constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
1801
  ```
1802
 
1803
  *Constraints:* `is_constructible_v<mapped_type, Args...>` is `true`.
1804
 
1805
  *Effects:* If the map already contains an element whose key is
 
1821
  *Complexity:* The same as `emplace` for the first two overloads, and the
1822
  same as `emplace_hint` for the last two overloads.
1823
 
1824
  ``` cpp
1825
  template<class K, class... Args>
1826
+ constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args);
1827
  template<class K, class... Args>
1828
+ constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
1829
  ```
1830
 
1831
  *Constraints:*
1832
 
1833
  - The *qualified-id* `Compare::is_transparent` is valid and denotes a
 
1843
  *Effects:* If the map already contains an element whose key is
1844
  equivalent to `k`, `*this` and `args...` are unchanged. Otherwise
1845
  equivalent to:
1846
 
1847
  ``` cpp
1848
+ auto key_it = upper_bound(c.keys.begin(), c.keys.end(), k, compare);
1849
  auto value_it = c.values.begin() + distance(c.keys.begin(), key_it);
1850
  c.keys.emplace(key_it, std::forward<K>(k));
1851
  c.values.emplace(value_it, std::forward<Args>(args)...);
1852
  ```
1853
 
 
1857
 
1858
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
1859
 
1860
  ``` cpp
1861
  template<class M>
1862
+ constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
1863
  template<class M>
1864
+ constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
1865
  template<class M>
1866
+ constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
1867
  template<class M>
1868
+ constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
1869
  ```
1870
 
1871
  *Constraints:* `is_assignable_v<mapped_type&, M>` is `true` and
1872
  `is_constructible_v<mapped_type, M>` is `true`.
1873
 
 
1895
  *Complexity:* The same as `emplace` for the first two overloads and the
1896
  same as `emplace_hint` for the last two overloads.
1897
 
1898
  ``` cpp
1899
  template<class K, class M>
1900
+ constexpr pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
1901
  template<class K, class M>
1902
+ constexpr iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
1903
  ```
1904
 
1905
  *Constraints:*
1906
 
1907
  - The *qualified-id* `Compare::is_transparent` is valid and denotes a
 
1934
  iterator points to the map element whose key is equivalent to `k`.
1935
 
1936
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
1937
 
1938
  ``` cpp
1939
+ constexpr void swap(flat_map& y) noexcept;
1940
  ```
1941
 
1942
  *Effects:* Equivalent to:
1943
 
1944
  ``` cpp
 
1946
  ranges::swap(c.keys, y.c.keys);
1947
  ranges::swap(c.values, y.c.values);
1948
  ```
1949
 
1950
  ``` cpp
1951
+ constexpr containers extract() &&;
1952
  ```
1953
 
1954
  *Ensures:* `*this` is emptied, even if the function exits via an
1955
  exception.
1956
 
1957
+ *Returns:* `std::move(`*`c`*`)`.
1958
 
1959
  ``` cpp
1960
+ constexpr void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);
1961
  ```
1962
 
1963
  *Preconditions:* `key_cont.size() == mapped_cont.size()` is `true`, the
1964
+ elements of `key_cont` are sorted with respect to *compare*, and
1965
  `key_cont` contains no equal elements.
1966
 
1967
  *Effects:* Equivalent to:
1968
 
1969
  ``` cpp
 
1974
  #### Erasure <a id="flat.map.erasure">[[flat.map.erasure]]</a>
1975
 
1976
  ``` cpp
1977
  template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
1978
  class Predicate>
1979
+ constexpr typename flat_map<Key, T, Compare, KeyContainer, MappedContainer>::size_type
1980
  erase_if(flat_map<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
1981
  ```
1982
 
1983
  *Preconditions:* `Key` and `T` meet the *Cpp17MoveAssignable*
1984
  requirements.
 
2068
 
2069
  The effect of calling a constructor that takes both `key_container_type`
2070
  and `mapped_container_type` arguments with containers of different sizes
2071
  is undefined.
2072
 
2073
+ The effect of calling a member function that takes a
2074
  `sorted_equivalent_t` argument with a container, containers, or range
2075
  that are not sorted with respect to `key_comp()` is undefined.
2076
 
2077
+ The types `iterator` and `const_iterator` meet the constexpr iterator
2078
+ requirements [[iterator.requirements.general]].
2079
+
2080
  #### Definition <a id="flat.multimap.defn">[[flat.multimap.defn]]</a>
2081
 
2082
  ``` cpp
2083
  namespace std {
2084
  template<class Key, class T, class Compare = less<Key>,
 
2102
  using mapped_container_type = MappedContainer;
2103
 
2104
  class value_compare {
2105
  private:
2106
  key_compare comp; // exposition only
2107
+ constexpr value_compare(key_compare c) : comp(c) { } // exposition only
2108
 
2109
  public:
2110
+ constexpr bool operator()(const_reference x, const_reference y) const {
2111
  return comp(x.first, y.first);
2112
  }
2113
  };
2114
 
2115
  struct containers {
2116
  key_container_type keys;
2117
  mapped_container_type values;
2118
  };
2119
 
2120
+ // [flat.multimap.cons], constructors
2121
+ constexpr flat_multimap() : flat_multimap(key_compare()) { }
2122
 
2123
+ constexpr explicit flat_multimap(const key_compare& comp)
2124
+ : c(), compare(comp) { }
2125
+
2126
+ constexpr flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,
2127
  const key_compare& comp = key_compare());
 
 
 
 
 
 
2128
 
2129
+ constexpr flat_multimap(sorted_equivalent_t,
2130
  key_container_type key_cont, mapped_container_type mapped_cont,
2131
  const key_compare& comp = key_compare());
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2132
 
2133
  template<class InputIterator>
2134
+ constexpr flat_multimap(InputIterator first, InputIterator last,
2135
  const key_compare& comp = key_compare())
2136
  : c(), compare(comp)
2137
  { insert(first, last); }
2138
+
2139
+ template<class InputIterator>
2140
+ constexpr flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
2141
+ const key_compare& comp = key_compare())
2142
+ : c(), compare(comp) { insert(sorted_equivalent, first, last); }
2143
 
2144
  template<container-compatible-range<value_type> R>
2145
+ constexpr flat_multimap(from_range_t, R&& rg)
2146
+ : flat_multimap(from_range, std::forward<R>(rg), key_compare()) { }
 
 
2147
  template<container-compatible-range<value_type> R>
2148
+ constexpr flat_multimap(from_range_t, R&& rg, const key_compare& comp)
2149
  : flat_multimap(comp) { insert_range(std::forward<R>(rg)); }
 
 
2150
 
2151
+ constexpr flat_multimap(initializer_list<value_type> il,
 
2152
  const key_compare& comp = key_compare())
 
 
 
 
 
 
 
 
 
2153
  : flat_multimap(il.begin(), il.end(), comp) { }
 
 
 
 
 
2154
 
2155
+ constexpr flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
2156
  const key_compare& comp = key_compare())
2157
+ : flat_multimap(sorted_equivalent, il.begin(), il.end(), comp) { }
 
 
 
 
 
2158
 
2159
+ // [flat.multimap.cons.alloc], constructors with allocators
2160
+
2161
+ template<class Alloc>
2162
+ constexpr explicit flat_multimap(const Alloc& a);
2163
+ template<class Alloc>
2164
+ constexpr flat_multimap(const key_compare& comp, const Alloc& a);
2165
+ template<class Alloc>
2166
+ constexpr flat_multimap(const key_container_type& key_cont,
2167
+ const mapped_container_type& mapped_cont, const Alloc& a);
2168
+ template<class Alloc>
2169
+ constexpr flat_multimap(const key_container_type& key_cont,
2170
+ const mapped_container_type& mapped_cont,
2171
+ const key_compare& comp, const Alloc& a);
2172
+ template<class Alloc>
2173
+ constexpr flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
2174
+ const mapped_container_type& mapped_cont, const Alloc& a);
2175
+ template<class Alloc>
2176
+ constexpr flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
2177
+ const mapped_container_type& mapped_cont,
2178
+ const key_compare& comp, const Alloc& a);
2179
+ template<class Alloc>
2180
+ constexpr flat_multimap(const flat_multimap&, const Alloc& a);
2181
+ template<class Alloc>
2182
+ constexpr flat_multimap(flat_multimap&&, const Alloc& a);
2183
+ template<class InputIterator, class Alloc>
2184
+ constexpr flat_multimap(InputIterator first, InputIterator last, const Alloc& a);
2185
+ template<class InputIterator, class Alloc>
2186
+ constexpr flat_multimap(InputIterator first, InputIterator last,
2187
+ const key_compare& comp, const Alloc& a);
2188
+ template<class InputIterator, class Alloc>
2189
+ constexpr flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
2190
+ const Alloc& a);
2191
+ template<class InputIterator, class Alloc>
2192
+ constexpr flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
2193
+ const key_compare& comp, const Alloc& a);
2194
+ template<container-compatible-range<value_type> R, class Alloc>
2195
+ constexpr flat_multimap(from_range_t, R&& rg, const Alloc& a);
2196
+ template<container-compatible-range<value_type> R, class Alloc>
2197
+ constexpr flat_multimap(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
2198
+ template<class Alloc>
2199
+ constexpr flat_multimap(initializer_list<value_type> il, const Alloc& a);
2200
+ template<class Alloc>
2201
+ constexpr flat_multimap(initializer_list<value_type> il, const key_compare& comp,
2202
+ const Alloc& a);
2203
+ template<class Alloc>
2204
+ constexpr flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
2205
+ const Alloc& a);
2206
+ template<class Alloc>
2207
+ constexpr flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
2208
+ const key_compare& comp, const Alloc& a);
2209
+
2210
+ flat_multimap& operator=(initializer_list<value_type>);
2211
 
2212
  // iterators
2213
+ constexpr iterator begin() noexcept;
2214
+ constexpr const_iterator begin() const noexcept;
2215
+ constexpr iterator end() noexcept;
2216
+ constexpr const_iterator end() const noexcept;
2217
 
2218
+ constexpr reverse_iterator rbegin() noexcept;
2219
+ constexpr const_reverse_iterator rbegin() const noexcept;
2220
+ constexpr reverse_iterator rend() noexcept;
2221
+ constexpr const_reverse_iterator rend() const noexcept;
2222
 
2223
+ constexpr const_iterator cbegin() const noexcept;
2224
+ constexpr const_iterator cend() const noexcept;
2225
+ constexpr const_reverse_iterator crbegin() const noexcept;
2226
+ constexpr const_reverse_iterator crend() const noexcept;
2227
 
2228
  // capacity
2229
+ constexpr bool empty() const noexcept;
2230
+ constexpr size_type size() const noexcept;
2231
+ constexpr size_type max_size() const noexcept;
2232
 
2233
  // modifiers
2234
+ template<class... Args> constexpr iterator emplace(Args&&... args);
2235
  template<class... Args>
2236
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
2237
 
2238
+ constexpr iterator insert(const value_type& x)
2239
  { return emplace(x); }
2240
+ constexpr iterator insert(value_type&& x)
2241
  { return emplace(std::move(x)); }
2242
+ constexpr iterator insert(const_iterator position, const value_type& x)
2243
  { return emplace_hint(position, x); }
2244
+ constexpr iterator insert(const_iterator position, value_type&& x)
2245
  { return emplace_hint(position, std::move(x)); }
2246
 
2247
+ template<class P> constexpr iterator insert(P&& x);
2248
  template<class P>
2249
+ constexpr iterator insert(const_iterator position, P&&);
2250
  template<class InputIterator>
2251
+ constexpr void insert(InputIterator first, InputIterator last);
2252
  template<class InputIterator>
2253
+ constexpr void insert(sorted_equivalent_t, InputIterator first, InputIterator last);
2254
  template<container-compatible-range<value_type> R>
2255
+ constexpr void insert_range(R&& rg);
2256
 
2257
+ constexpr void insert(initializer_list<value_type> il)
2258
  { insert(il.begin(), il.end()); }
2259
+ constexpr void insert(sorted_equivalent_t, initializer_list<value_type> il)
2260
+ { insert(sorted_equivalent, il.begin(), il.end()); }
2261
 
2262
+ constexpr containers extract() &&;
2263
+ constexpr void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);
2264
 
2265
+ constexpr iterator erase(iterator position);
2266
+ constexpr iterator erase(const_iterator position);
2267
+ constexpr size_type erase(const key_type& x);
2268
+ template<class K> constexpr size_type erase(K&& x);
2269
+ constexpr iterator erase(const_iterator first, const_iterator last);
2270
 
2271
+ constexpr void swap(flat_multimap&) noexcept;
2272
+ constexpr void clear() noexcept;
2273
 
2274
  // observers
2275
+ constexpr key_compare key_comp() const;
2276
+ constexpr value_compare value_comp() const;
2277
 
2278
+ constexpr const key_container_type& keys() const noexcept { return c.keys; }
2279
+ constexpr const mapped_container_type& values() const noexcept { return c.values; }
2280
 
2281
  // map operations
2282
+ constexpr iterator find(const key_type& x);
2283
+ constexpr const_iterator find(const key_type& x) const;
2284
+ template<class K> constexpr iterator find(const K& x);
2285
+ template<class K> constexpr const_iterator find(const K& x) const;
2286
 
2287
+ constexpr size_type count(const key_type& x) const;
2288
+ template<class K> constexpr size_type count(const K& x) const;
2289
 
2290
+ constexpr bool contains(const key_type& x) const;
2291
+ template<class K> constexpr bool contains(const K& x) const;
2292
 
2293
+ constexpr iterator lower_bound(const key_type& x);
2294
+ constexpr const_iterator lower_bound(const key_type& x) const;
2295
+ template<class K> constexpr iterator lower_bound(const K& x);
2296
+ template<class K> constexpr const_iterator lower_bound(const K& x) const;
2297
 
2298
+ constexpr iterator upper_bound(const key_type& x);
2299
+ constexpr const_iterator upper_bound(const key_type& x) const;
2300
+ template<class K> constexpr iterator upper_bound(const K& x);
2301
+ template<class K> constexpr const_iterator upper_bound(const K& x) const;
2302
 
2303
+ constexpr pair<iterator, iterator> equal_range(const key_type& x);
2304
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
2305
  template<class K>
2306
+ constexpr pair<iterator, iterator> equal_range(const K& x);
2307
  template<class K>
2308
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
2309
 
2310
+ friend constexpr bool operator==(const flat_multimap& x, const flat_multimap& y);
2311
 
2312
+ friend constexpr synth-three-way-result<value_type>
2313
  operator<=>(const flat_multimap& x, const flat_multimap& y);
2314
 
2315
+ friend constexpr void swap(flat_multimap& x, flat_multimap& y) noexcept
2316
  { x.swap(y); }
2317
 
2318
  private:
2319
  containers c; // exposition only
2320
  key_compare compare; // exposition only
 
2397
  specified.
2398
 
2399
  #### Constructors <a id="flat.multimap.cons">[[flat.multimap.cons]]</a>
2400
 
2401
  ``` cpp
2402
+ constexpr flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,
2403
  const key_compare& comp = key_compare());
2404
  ```
2405
 
2406
+ *Effects:* Initializes *`c`*`.keys` with `std::move(key_cont)`,
2407
+ *`c`*`.values` with `std::move(mapped_cont)`, and *compare* with `comp`;
2408
+ sorts the range \[`begin()`, `end()`) with respect to `value_comp()`.
2409
 
2410
  *Complexity:* Linear in N if the container arguments are already sorted
2411
  with respect to `value_comp()` and otherwise N log N, where N is the
2412
  value of `key_cont.size()` before this call.
2413
 
2414
  ``` cpp
2415
+ constexpr flat_multimap(sorted_equivalent_t, key_container_type key_cont,
2416
+ mapped_container_type mapped_cont,
2417
+ const key_compare& comp = key_compare());
 
 
 
2418
  ```
2419
 
2420
+ *Effects:* Initializes *`c`*`.keys` with `std::move(key_cont)`,
2421
+ *`c`*`.values` with `std::move(mapped_cont)`, and *compare* with `comp`.
2422
+
2423
+ *Complexity:* Constant.
2424
+
2425
+ #### Constructors with allocators <a id="flat.multimap.cons.alloc">[[flat.multimap.cons.alloc]]</a>
2426
+
2427
+ The constructors in this subclause shall not participate in overload
2428
+ resolution unless `uses_allocator_v<key_container_type, Alloc>` is
2429
+ `true` and `uses_allocator_v<mapped_container_type, Alloc>` is `true`.
2430
+
2431
+ ``` cpp
2432
+ template<class Alloc>
2433
+ constexpr flat_multimap(const key_container_type& key_cont,
2434
+ const mapped_container_type& mapped_cont, const Alloc& a);
2435
+ template<class Alloc>
2436
+ constexpr flat_multimap(const key_container_type& key_cont,
2437
+ const mapped_container_type& mapped_cont,
2438
+ const key_compare& comp, const Alloc& a);
2439
+ ```
2440
 
2441
  *Effects:* Equivalent to `flat_multimap(key_cont, mapped_cont)` and
2442
  `flat_multimap(key_cont, mapped_cont, comp)`, respectively, except that
2443
+ *`c`*`.keys` and *`c`*`.values` are constructed with uses-allocator
2444
  construction [[allocator.uses.construction]].
2445
 
2446
  *Complexity:* Same as `flat_multimap(key_cont, mapped_cont)` and
2447
  `flat_multimap(key_cont, mapped_cont, comp)`, respectively.
2448
 
2449
  ``` cpp
2450
+ template<class Alloc>
2451
+ constexpr flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
2452
+ const mapped_container_type& mapped_cont, const Alloc& a);
2453
+ template<class Alloc>
2454
+ constexpr flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
 
 
 
 
 
 
 
 
 
 
2455
  const mapped_container_type& mapped_cont, const key_compare& comp,
2456
+ const Alloc& a);
2457
  ```
2458
 
2459
+ *Effects:* Equivalent to
2460
+ `flat_multimap(sorted_equivalent, key_cont, mapped_cont)` and
2461
+ `flat_multimap(sorted_equivalent, key_cont, mapped_cont, comp)`,
2462
+ respectively, except that *`c`*`.keys` and *`c`*`.values` are
2463
+ constructed with uses-allocator
 
 
2464
  construction [[allocator.uses.construction]].
2465
 
2466
  *Complexity:* Linear.
2467
 
2468
  ``` cpp
2469
+ template<class Alloc>
2470
+ constexpr explicit flat_multimap(const Alloc& a);
2471
+ template<class Alloc>
2472
+ constexpr flat_multimap(const key_compare& comp, const Alloc& a);
2473
+ template<class Alloc>
2474
+ constexpr flat_multimap(const flat_multimap&, const Alloc& a);
2475
+ template<class Alloc>
2476
+ constexpr flat_multimap(flat_multimap&&, const Alloc& a);
2477
+ template<class InputIterator, class Alloc>
2478
+ constexpr flat_multimap(InputIterator first, InputIterator last, const Alloc& a);
2479
+ template<class InputIterator, class Alloc>
2480
+ constexpr flat_multimap(InputIterator first, InputIterator last, const key_compare& comp,
2481
+ const Alloc& a);
2482
+ template<class InputIterator, class Alloc>
2483
+ constexpr flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
2484
+ const Alloc& a);
2485
+ template<class InputIterator, class Alloc>
2486
+ constexpr flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
2487
+ const key_compare& comp, const Alloc& a);
2488
+ template<container-compatible-range<value_type> R, class Alloc>
2489
+ constexpr flat_multimap(from_range_t, R&& rg, const Alloc& a);
2490
+ template<container-compatible-range<value_type> R, class Alloc>
2491
+ constexpr flat_multimap(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
2492
+ template<class Alloc>
2493
+ constexpr flat_multimap(initializer_list<value_type> il, const Alloc& a);
2494
+ template<class Alloc>
2495
+ constexpr flat_multimap(initializer_list<value_type> il, const key_compare& comp,
2496
+ const Alloc& a);
2497
+ template<class Alloc>
2498
+ constexpr flat_multimap(sorted_equivalent_t, initializer_list<value_type> il, const Alloc& a);
2499
+ template<class Alloc>
2500
+ constexpr flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
2501
+ const key_compare& comp, const Alloc& a);
2502
  ```
2503
 
 
 
 
 
2504
  *Effects:* Equivalent to the corresponding non-allocator constructors
2505
+ except that *`c`*`.keys` and *`c`*`.values` are constructed with
2506
+ uses-allocator construction [[allocator.uses.construction]].
2507
 
2508
  #### Erasure <a id="flat.multimap.erasure">[[flat.multimap.erasure]]</a>
2509
 
2510
  ``` cpp
2511
  template<class Key, class T, class Compare, class KeyContainer, class MappedContainer,
2512
  class Predicate>
2513
+ constexpr typename flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>::size_type
2514
  erase_if(flat_multimap<Key, T, Compare, KeyContainer, MappedContainer>& c, Predicate pred);
2515
  ```
2516
 
2517
  *Preconditions:* `Key` and `T` meet the *Cpp17MoveAssignable*
2518
  requirements.
 
2529
  state [[defns.valid]].
2530
 
2531
  [*Note 1*: `c` still meets its invariants, but can be
2532
  empty. — *end note*]
2533
 
2534
+ ### Header `<flat_set>` synopsis <a id="flat.set.syn">[[flat.set.syn]]</a>
2535
+
2536
+ ``` cpp
2537
+ #include <compare> // see [compare.syn]
2538
+ #include <initializer_list> // see [initializer.list.syn]
2539
+
2540
+ namespace std {
2541
+ // [flat.set], class template flat_set
2542
+ template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>
2543
+ class flat_set;
2544
+
2545
+ struct sorted_unique_t { explicit sorted_unique_t() = default; };
2546
+ inline constexpr sorted_unique_t sorted_unique{};
2547
+
2548
+ template<class Key, class Compare, class KeyContainer, class Allocator>
2549
+ struct uses_allocator<flat_set<Key, Compare, KeyContainer>, Allocator>;
2550
+
2551
+ // [flat.set.erasure], erasure for flat_set
2552
+ template<class Key, class Compare, class KeyContainer, class Predicate>
2553
+ constexpr typename flat_set<Key, Compare, KeyContainer>::size_type
2554
+ erase_if(flat_set<Key, Compare, KeyContainer>& c, Predicate pred);
2555
+
2556
+ // [flat.multiset], class template flat_multiset
2557
+ template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>
2558
+ class flat_multiset;
2559
+
2560
+ struct sorted_equivalent_t { explicit sorted_equivalent_t() = default; };
2561
+ inline constexpr sorted_equivalent_t sorted_equivalent{};
2562
+
2563
+ template<class Key, class Compare, class KeyContainer, class Allocator>
2564
+ struct uses_allocator<flat_multiset<Key, Compare, KeyContainer>, Allocator>;
2565
+
2566
+ // [flat.multiset.erasure], erasure for flat_multiset
2567
+ template<class Key, class Compare, class KeyContainer, class Predicate>
2568
+ constexpr typename flat_multiset<Key, Compare, KeyContainer>::size_type
2569
+ erase_if(flat_multiset<Key, Compare, KeyContainer>& c, Predicate pred);
2570
+ }
2571
+ ```
2572
+
2573
  ### Class template `flat_set` <a id="flat.set">[[flat.set]]</a>
2574
 
2575
  #### Overview <a id="flat.set.overview">[[flat.set.overview]]</a>
2576
 
2577
  A `flat_set` is a container adaptor that provides an associative
 
2624
  [*Note 3*: `vector<bool>` is not a sequence container. — *end note*]
2625
 
2626
  The program is ill-formed if `Key` is not the same type as
2627
  `KeyContainer::value_type`.
2628
 
2629
+ The effect of calling a member function that takes a `sorted_unique_t`
2630
+ argument with a range that is not sorted with respect to `key_comp()`,
2631
+ or that contains equal elements, is undefined.
2632
+
2633
+ The types `iterator` and `const_iterator` meet the constexpr iterator
2634
+ requirements [[iterator.requirements.general]].
2635
 
2636
  #### Definition <a id="flat.set.defn">[[flat.set.defn]]</a>
2637
 
2638
  ``` cpp
2639
  namespace std {
 
2645
  using value_type = Key;
2646
  using key_compare = Compare;
2647
  using value_compare = Compare;
2648
  using reference = value_type&;
2649
  using const_reference = const value_type&;
2650
+ using size_type = KeyContainer::size_type;
2651
+ using difference_type = KeyContainer::difference_type;
2652
  using iterator = implementation-defined // type of flat_set::iterator; // see [container.requirements]
2653
  using const_iterator = implementation-defined // type of flat_set::const_iterator; // see [container.requirements]
2654
  using reverse_iterator = std::reverse_iterator<iterator>;
2655
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
2656
  using container_type = KeyContainer;
2657
 
2658
  // [flat.set.cons], constructors
2659
+ constexpr flat_set() : flat_set(key_compare()) { }
2660
 
2661
+ constexpr explicit flat_set(const key_compare& comp)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2662
  : c(), compare(comp) { }
2663
+
2664
+ constexpr explicit flat_set(container_type cont, const key_compare& comp = key_compare());
2665
+
2666
+ constexpr flat_set(sorted_unique_t, container_type cont,
2667
+ const key_compare& comp = key_compare())
2668
+ : c(std::move(cont)), compare(comp) { }
2669
 
2670
  template<class InputIterator>
2671
+ constexpr flat_set(InputIterator first, InputIterator last,
2672
+ const key_compare& comp = key_compare())
2673
  : c(), compare(comp)
2674
  { insert(first, last); }
2675
+
2676
+ template<class InputIterator>
2677
+ constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last,
2678
+ const key_compare& comp = key_compare())
2679
+ : c(first, last), compare(comp) { }
2680
 
2681
  template<container-compatible-range<value_type> R>
2682
+ constexpr flat_set(from_range_t, R&& rg)
2683
+ : flat_set(from_range, std::forward<R>(rg), key_compare()) { }
 
 
2684
  template<container-compatible-range<value_type> R>
2685
+ constexpr flat_set(from_range_t, R&& rg, const key_compare& comp)
2686
  : flat_set(comp)
2687
  { insert_range(std::forward<R>(rg)); }
 
 
2688
 
2689
+ constexpr flat_set(initializer_list<value_type> il, const key_compare& comp = key_compare())
 
 
 
 
 
 
 
 
 
 
2690
  : flat_set(il.begin(), il.end(), comp) { }
 
 
 
 
2691
 
2692
+ constexpr flat_set(sorted_unique_t, initializer_list<value_type> il,
2693
  const key_compare& comp = key_compare())
2694
+ : flat_set(sorted_unique, il.begin(), il.end(), comp) { }
 
 
 
 
 
2695
 
2696
+ // [flat.set.cons.alloc], constructors with allocators
2697
+
2698
+ template<class Alloc>
2699
+ constexpr explicit flat_set(const Alloc& a);
2700
+ template<class Alloc>
2701
+ constexpr flat_set(const key_compare& comp, const Alloc& a);
2702
+ template<class Alloc>
2703
+ constexpr flat_set(const container_type& cont, const Alloc& a);
2704
+ template<class Alloc>
2705
+ constexpr flat_set(const container_type& cont, const key_compare& comp, const Alloc& a);
2706
+ template<class Alloc>
2707
+ constexpr flat_set(sorted_unique_t, const container_type& cont, const Alloc& a);
2708
+ template<class Alloc>
2709
+ constexpr flat_set(sorted_unique_t, const container_type& cont,
2710
+ const key_compare& comp, const Alloc& a);
2711
+ template<class Alloc>
2712
+ constexpr flat_set(const flat_set&, const Alloc& a);
2713
+ template<class Alloc>
2714
+ constexpr flat_set(flat_set&&, const Alloc& a);
2715
+ template<class InputIterator, class Alloc>
2716
+ constexpr flat_set(InputIterator first, InputIterator last, const Alloc& a);
2717
+ template<class InputIterator, class Alloc>
2718
+ constexpr flat_set(InputIterator first, InputIterator last,
2719
+ const key_compare& comp, const Alloc& a);
2720
+ template<class InputIterator, class Alloc>
2721
+ constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last,
2722
+ const Alloc& a);
2723
+ template<class InputIterator, class Alloc>
2724
+ constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last,
2725
+ const key_compare& comp, const Alloc& a);
2726
+ template<container-compatible-range<value_type> R, class Alloc>
2727
+ constexpr flat_set(from_range_t, R&& rg, const Alloc& a);
2728
+ template<container-compatible-range<value_type> R, class Alloc>
2729
+ constexpr flat_set(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
2730
+ template<class Alloc>
2731
+ constexpr flat_set(initializer_list<value_type> il, const Alloc& a);
2732
+ template<class Alloc>
2733
+ constexpr flat_set(initializer_list<value_type> il, const key_compare& comp,
2734
+ const Alloc& a);
2735
+ template<class Alloc>
2736
+ constexpr flat_set(sorted_unique_t, initializer_list<value_type> il, const Alloc& a);
2737
+ template<class Alloc>
2738
+ constexpr flat_set(sorted_unique_t, initializer_list<value_type> il,
2739
+ const key_compare& comp, const Alloc& a);
2740
+
2741
+ constexpr flat_set& operator=(initializer_list<value_type>);
2742
 
2743
  // iterators
2744
+ constexpr iterator begin() noexcept;
2745
+ constexpr const_iterator begin() const noexcept;
2746
+ constexpr iterator end() noexcept;
2747
+ constexpr const_iterator end() const noexcept;
2748
 
2749
+ constexpr reverse_iterator rbegin() noexcept;
2750
+ constexpr const_reverse_iterator rbegin() const noexcept;
2751
+ constexpr reverse_iterator rend() noexcept;
2752
+ constexpr const_reverse_iterator rend() const noexcept;
2753
 
2754
+ constexpr const_iterator cbegin() const noexcept;
2755
+ constexpr const_iterator cend() const noexcept;
2756
+ constexpr const_reverse_iterator crbegin() const noexcept;
2757
+ constexpr const_reverse_iterator crend() const noexcept;
2758
 
2759
  // capacity
2760
+ constexpr bool empty() const noexcept;
2761
+ constexpr size_type size() const noexcept;
2762
+ constexpr size_type max_size() const noexcept;
2763
 
2764
  // [flat.set.modifiers], modifiers
2765
+ template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
2766
  template<class... Args>
2767
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
2768
 
2769
+ constexpr pair<iterator, bool> insert(const value_type& x)
2770
  { return emplace(x); }
2771
+ constexpr pair<iterator, bool> insert(value_type&& x)
2772
  { return emplace(std::move(x)); }
2773
+ template<class K> constexpr pair<iterator, bool> insert(K&& x);
2774
+ constexpr iterator insert(const_iterator position, const value_type& x)
2775
  { return emplace_hint(position, x); }
2776
+ constexpr iterator insert(const_iterator position, value_type&& x)
2777
  { return emplace_hint(position, std::move(x)); }
2778
+ template<class K> constexpr iterator insert(const_iterator hint, K&& x);
2779
 
2780
  template<class InputIterator>
2781
+ constexpr void insert(InputIterator first, InputIterator last);
2782
  template<class InputIterator>
2783
+ constexpr void insert(sorted_unique_t, InputIterator first, InputIterator last);
2784
  template<container-compatible-range<value_type> R>
2785
+ constexpr void insert_range(R&& rg);
2786
 
2787
+ constexpr void insert(initializer_list<value_type> il)
2788
  { insert(il.begin(), il.end()); }
2789
+ constexpr void insert(sorted_unique_t, initializer_list<value_type> il)
2790
+ { insert(sorted_unique, il.begin(), il.end()); }
2791
 
2792
+ constexpr container_type extract() &&;
2793
+ constexpr void replace(container_type&&);
2794
 
2795
+ constexpr iterator erase(iterator position);
2796
+ constexpr iterator erase(const_iterator position);
2797
+ constexpr size_type erase(const key_type& x);
2798
+ template<class K> constexpr size_type erase(K&& x);
2799
+ constexpr iterator erase(const_iterator first, const_iterator last);
2800
 
2801
+ constexpr void swap(flat_set& y) noexcept;
2802
+ constexpr void clear() noexcept;
2803
 
2804
  // observers
2805
+ constexpr key_compare key_comp() const;
2806
+ constexpr value_compare value_comp() const;
2807
 
2808
  // set operations
2809
+ constexpr iterator find(const key_type& x);
2810
+ constexpr const_iterator find(const key_type& x) const;
2811
+ template<class K> constexpr iterator find(const K& x);
2812
+ template<class K> constexpr const_iterator find(const K& x) const;
2813
 
2814
+ constexpr size_type count(const key_type& x) const;
2815
+ template<class K> constexpr size_type count(const K& x) const;
2816
 
2817
+ constexpr bool contains(const key_type& x) const;
2818
+ template<class K> constexpr bool contains(const K& x) const;
2819
 
2820
+ constexpr iterator lower_bound(const key_type& x);
2821
+ constexpr const_iterator lower_bound(const key_type& x) const;
2822
+ template<class K> constexpr iterator lower_bound(const K& x);
2823
+ template<class K> constexpr const_iterator lower_bound(const K& x) const;
2824
 
2825
+ constexpr iterator upper_bound(const key_type& x);
2826
+ constexpr const_iterator upper_bound(const key_type& x) const;
2827
+ template<class K> constexpr iterator upper_bound(const K& x);
2828
+ template<class K> constexpr const_iterator upper_bound(const K& x) const;
2829
 
2830
+ constexpr pair<iterator, iterator> equal_range(const key_type& x);
2831
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
2832
  template<class K>
2833
+ constexpr pair<iterator, iterator> equal_range(const K& x);
2834
  template<class K>
2835
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
2836
 
2837
+ friend constexpr bool operator==(const flat_set& x, const flat_set& y);
2838
 
2839
+ friend constexpr synth-three-way-result<value_type>
2840
  operator<=>(const flat_set& x, const flat_set& y);
2841
 
2842
+ friend constexpr void swap(flat_set& x, flat_set& y) noexcept { x.swap(y); }
2843
 
2844
  private:
2845
  container_type c; // exposition only
2846
  key_compare compare; // exposition only
2847
  };
 
2904
  ```
2905
 
2906
  #### Constructors <a id="flat.set.cons">[[flat.set.cons]]</a>
2907
 
2908
  ``` cpp
2909
+ constexpr explicit flat_set(container_type cont, const key_compare& comp = key_compare());
2910
  ```
2911
 
2912
  *Effects:* Initializes *c* with `std::move(cont)` and *compare* with
2913
  `comp`, sorts the range \[`begin()`, `end()`) with respect to *compare*,
2914
  and finally erases all but the first element from each group of
2915
  consecutive equivalent elements.
2916
 
2917
+ *Complexity:* Linear in N if `cont` is already sorted with respect to
2918
+ *compare* and otherwise N log N, where N is the value of `cont.size()`
2919
+ before this call.
2920
+
2921
+ #### Constructors with allocators <a id="flat.set.cons.alloc">[[flat.set.cons.alloc]]</a>
2922
+
2923
+ The constructors in this subclause shall not participate in overload
2924
+ resolution unless `uses_allocator_v<container_type, Alloc>` is `true`.
2925
 
2926
  ``` cpp
2927
+ template<class Alloc>
2928
+ constexpr flat_set(const container_type& cont, const Alloc& a);
2929
+ template<class Alloc>
2930
+ constexpr flat_set(const container_type& cont, const key_compare& comp, const Alloc& a);
2931
  ```
2932
 
 
 
2933
  *Effects:* Equivalent to `flat_set(cont)` and `flat_set(cont, comp)`,
2934
  respectively, except that *c* is constructed with uses-allocator
2935
  construction [[allocator.uses.construction]].
2936
 
2937
  *Complexity:* Same as `flat_set(cont)` and `flat_set(cont, comp)`,
2938
  respectively.
2939
 
2940
  ``` cpp
2941
+ template<class Alloc>
2942
+ constexpr flat_set(sorted_unique_t, const container_type& cont, const Alloc& a);
2943
+ template<class Alloc>
2944
+ constexpr flat_set(sorted_unique_t, const container_type& cont,
2945
+ const key_compare& comp, const Alloc& a);
2946
  ```
2947
 
2948
+ *Effects:* Equivalent to `flat_set(sorted_unique, cont)` and
2949
+ `flat_set(sorted_unique, cont,comp)`, respectively, except that *c* is
2950
+ constructed with uses-allocator
2951
+ construction [[allocator.uses.construction]].
 
2952
 
2953
  *Complexity:* Linear.
2954
 
2955
  ``` cpp
2956
+ template<class Alloc>
2957
+ constexpr explicit flat_set(const Alloc& a);
2958
+ template<class Alloc>
2959
+ constexpr flat_set(const key_compare& comp, const Alloc& a);
2960
+ template<class Alloc>
2961
+ constexpr flat_set(const flat_set&, const Alloc& a);
2962
+ template<class Alloc>
2963
+ constexpr flat_set(flat_set&&, const Alloc& a);
2964
+ template<class InputIterator, class Alloc>
2965
+ constexpr flat_set(InputIterator first, InputIterator last, const Alloc& a);
2966
+ template<class InputIterator, class Alloc>
2967
+ constexpr flat_set(InputIterator first, InputIterator last, const key_compare& comp,
2968
+ const Alloc& a);
2969
+ template<class InputIterator, class Alloc>
2970
+ constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last, const Alloc& a);
2971
+ template<class InputIterator, class Alloc>
2972
+ constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last,
2973
+ const key_compare& comp, const Alloc& a);
2974
+ template<container-compatible-range<value_type> R, class Alloc>
2975
+ constexpr flat_set(from_range_t, R&& rg, const Alloc& a);
2976
+ template<container-compatible-range<value_type> R, class Alloc>
2977
+ constexpr flat_set(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
2978
+ template<class Alloc>
2979
+ constexpr flat_set(initializer_list<value_type> il, const Alloc& a);
2980
+ template<class Alloc>
2981
+ constexpr flat_set(initializer_list<value_type> il, const key_compare& comp, const Alloc& a);
2982
+ template<class Alloc>
2983
+ constexpr flat_set(sorted_unique_t, initializer_list<value_type> il, const Alloc& a);
2984
+ template<class Alloc>
2985
+ constexpr flat_set(sorted_unique_t, initializer_list<value_type> il,
2986
+ const key_compare& comp, const Alloc& a);
2987
  ```
2988
 
 
 
2989
  *Effects:* Equivalent to the corresponding non-allocator constructors
2990
  except that *c* is constructed with uses-allocator
2991
  construction [[allocator.uses.construction]].
2992
 
2993
  #### Modifiers <a id="flat.set.modifiers">[[flat.set.modifiers]]</a>
2994
 
2995
  ``` cpp
2996
+ template<class K> constexpr pair<iterator, bool> insert(K&& x);
2997
+ template<class K> constexpr iterator insert(const_iterator hint, K&& x);
2998
  ```
2999
 
3000
  *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
3001
  denotes a type. `is_constructible_v<value_type, K>` is `true`.
3002
 
3003
  *Preconditions:* The conversion from `x` into `value_type` constructs an
3004
+ object `u`, for which `find(x) == find(u)` is `true`.
3005
 
3006
  *Effects:* If the set already contains an element equivalent to `x`,
3007
  `*this` and `x` are unchanged. Otherwise, inserts a new element as if by
3008
  `emplace(std::forward<K>(x))`.
3009
 
 
3011
  pair is `true` if and only if the insertion took place. The returned
3012
  iterator points to the element whose key is equivalent to `x`.
3013
 
3014
  ``` cpp
3015
  template<class InputIterator>
3016
+ constexpr void insert(InputIterator first, InputIterator last);
3017
  ```
3018
 
3019
  *Effects:* Adds elements to *c* as if by:
3020
 
3021
  ``` cpp
 
3034
  *Remarks:* Since this operation performs an in-place merge, it may
3035
  allocate memory.
3036
 
3037
  ``` cpp
3038
  template<class InputIterator>
3039
+ constexpr void insert(sorted_unique_t, InputIterator first, InputIterator last);
3040
  ```
3041
 
3042
  *Effects:* Equivalent to `insert(first, last)`.
3043
 
3044
  *Complexity:* Linear.
3045
 
3046
  ``` cpp
3047
  template<container-compatible-range<value_type> R>
3048
+ constexpr void insert_range(R&& rg);
3049
  ```
3050
 
3051
  *Effects:* Adds elements to *c* as if by:
3052
 
3053
  ``` cpp
 
3067
 
3068
  *Remarks:* Since this operation performs an in-place merge, it may
3069
  allocate memory.
3070
 
3071
  ``` cpp
3072
+ constexpr void swap(flat_set& y) noexcept;
3073
  ```
3074
 
3075
  *Effects:* Equivalent to:
3076
 
3077
  ``` cpp
3078
  ranges::swap(compare, y.compare);
3079
  ranges::swap(c, y.c);
3080
  ```
3081
 
3082
  ``` cpp
3083
+ constexpr container_type extract() &&;
3084
  ```
3085
 
3086
  *Ensures:* `*this` is emptied, even if the function exits via an
3087
  exception.
3088
 
3089
  *Returns:* `std::move(`*`c`*`)`.
3090
 
3091
  ``` cpp
3092
+ constexpr void replace(container_type&& cont);
3093
  ```
3094
 
3095
  *Preconditions:* The elements of `cont` are sorted with respect to
3096
  *compare*, and `cont` contains no equal elements.
3097
 
 
3099
 
3100
  #### Erasure <a id="flat.set.erasure">[[flat.set.erasure]]</a>
3101
 
3102
  ``` cpp
3103
  template<class Key, class Compare, class KeyContainer, class Predicate>
3104
+ constexpr typename flat_set<Key, Compare, KeyContainer>::size_type
3105
  erase_if(flat_set<Key, Compare, KeyContainer>& c, Predicate pred);
3106
  ```
3107
 
3108
  *Preconditions:* `Key` meets the *Cpp17MoveAssignable* requirements.
3109
 
 
3176
  [*Note 3*: `vector<bool>` is not a sequence container. — *end note*]
3177
 
3178
  The program is ill-formed if `Key` is not the same type as
3179
  `KeyContainer::value_type`.
3180
 
3181
+ The effect of calling a member function that takes a
3182
  `sorted_equivalent_t` argument with a range that is not sorted with
3183
  respect to `key_comp()` is undefined.
3184
 
3185
+ The types `iterator` and `const_iterator` meet the constexpr iterator
3186
+ requirements [[iterator.requirements.general]].
3187
+
3188
  #### Definition <a id="flat.multiset.defn">[[flat.multiset.defn]]</a>
3189
 
3190
  ``` cpp
3191
  namespace std {
3192
  template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>
 
3197
  using value_type = Key;
3198
  using key_compare = Compare;
3199
  using value_compare = Compare;
3200
  using reference = value_type&;
3201
  using const_reference = const value_type&;
3202
+ using size_type = KeyContainer::size_type;
3203
+ using difference_type = KeyContainer::difference_type;
3204
  using iterator = implementation-defined // type of flat_multiset::iterator; // see [container.requirements]
3205
  using const_iterator = implementation-defined // type of flat_multiset::const_iterator; // see [container.requirements]
3206
  using reverse_iterator = std::reverse_iterator<iterator>;
3207
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
3208
  using container_type = KeyContainer;
3209
 
3210
  // [flat.multiset.cons], constructors
3211
+ constexpr flat_multiset() : flat_multiset(key_compare()) { }
3212
 
3213
+ constexpr explicit flat_multiset(const key_compare& comp)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3214
  : c(), compare(comp) { }
3215
+
3216
+ constexpr explicit flat_multiset(container_type cont,
3217
+ const key_compare& comp = key_compare());
3218
+
3219
+ constexpr flat_multiset(sorted_equivalent_t, container_type cont,
3220
+ const key_compare& comp = key_compare())
3221
+ : c(std::move(cont)), compare(comp) { }
3222
 
3223
  template<class InputIterator>
3224
+ constexpr flat_multiset(InputIterator first, InputIterator last,
3225
  const key_compare& comp = key_compare())
3226
  : c(), compare(comp)
3227
  { insert(first, last); }
3228
+
3229
+ template<class InputIterator>
3230
+ constexpr flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
3231
+ const key_compare& comp = key_compare())
3232
+ : c(first, last), compare(comp) { }
3233
 
3234
  template<container-compatible-range<value_type> R>
3235
+ constexpr flat_multiset(from_range_t, R&& rg)
3236
+ : flat_multiset(from_range, std::forward<R>(rg), key_compare()) { }
 
 
3237
  template<container-compatible-range<value_type> R>
3238
+ constexpr flat_multiset(from_range_t, R&& rg, const key_compare& comp)
3239
  : flat_multiset(comp)
3240
  { insert_range(std::forward<R>(rg)); }
 
 
3241
 
3242
+ constexpr flat_multiset(initializer_list<value_type> il,
 
3243
  const key_compare& comp = key_compare())
 
 
 
 
 
 
 
 
 
3244
  : flat_multiset(il.begin(), il.end(), comp) { }
 
 
 
 
 
3245
 
3246
+ constexpr flat_multiset(sorted_equivalent_t, initializer_list<value_type> il,
3247
  const key_compare& comp = key_compare())
3248
+ : flat_multiset(sorted_equivalent, il.begin(), il.end(), comp) { }
 
 
 
 
 
3249
 
3250
+ // [flat.multiset.cons.alloc], constructors with allocators
3251
+
3252
+ template<class Alloc>
3253
+ constexpr explicit flat_multiset(const Alloc& a);
3254
+ template<class Alloc>
3255
+ constexpr flat_multiset(const key_compare& comp, const Alloc& a);
3256
+ template<class Alloc>
3257
+ constexpr flat_multiset(const container_type& cont, const Alloc& a);
3258
+ template<class Alloc>
3259
+ constexpr flat_multiset(const container_type& cont, const key_compare& comp,
3260
+ const Alloc& a);
3261
+ template<class Alloc>
3262
+ constexpr flat_multiset(sorted_equivalent_t, const container_type& cont, const Alloc& a);
3263
+ template<class Alloc>
3264
+ constexpr flat_multiset(sorted_equivalent_t, const container_type& cont,
3265
+ const key_compare& comp, const Alloc& a);
3266
+ template<class Alloc>
3267
+ constexpr flat_multiset(const flat_multiset&, const Alloc& a);
3268
+ template<class Alloc>
3269
+ constexpr flat_multiset(flat_multiset&&, const Alloc& a);
3270
+ template<class InputIterator, class Alloc>
3271
+ constexpr flat_multiset(InputIterator first, InputIterator last, const Alloc& a);
3272
+ template<class InputIterator, class Alloc>
3273
+ constexpr flat_multiset(InputIterator first, InputIterator last,
3274
+ const key_compare& comp, const Alloc& a);
3275
+ template<class InputIterator, class Alloc>
3276
+ constexpr flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
3277
+ const Alloc& a);
3278
+ template<class InputIterator, class Alloc>
3279
+ constexpr flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
3280
+ const key_compare& comp, const Alloc& a);
3281
+ template<container-compatible-range<value_type> R, class Alloc>
3282
+ constexpr flat_multiset(from_range_t, R&& rg, const Alloc& a);
3283
+ template<container-compatible-range<value_type> R, class Alloc>
3284
+ constexpr flat_multiset(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
3285
+ template<class Alloc>
3286
+ constexpr flat_multiset(initializer_list<value_type> il, const Alloc& a);
3287
+ template<class Alloc>
3288
+ constexpr flat_multiset(initializer_list<value_type> il, const key_compare& comp,
3289
+ const Alloc& a);
3290
+ template<class Alloc>
3291
+ constexpr flat_multiset(sorted_equivalent_t, initializer_list<value_type> il,
3292
+ const Alloc& a);
3293
+ template<class Alloc>
3294
+ constexpr flat_multiset(sorted_equivalent_t, initializer_list<value_type> il,
3295
+ const key_compare& comp, const Alloc& a);
3296
+
3297
+ constexpr flat_multiset& operator=(initializer_list<value_type>);
3298
 
3299
  // iterators
3300
+ constexpr iterator begin() noexcept;
3301
+ constexpr const_iterator begin() const noexcept;
3302
+ constexpr iterator end() noexcept;
3303
+ constexpr const_iterator end() const noexcept;
3304
 
3305
+ constexpr reverse_iterator rbegin() noexcept;
3306
+ constexpr const_reverse_iterator rbegin() const noexcept;
3307
+ constexpr reverse_iterator rend() noexcept;
3308
+ constexpr const_reverse_iterator rend() const noexcept;
3309
 
3310
+ constexpr const_iterator cbegin() const noexcept;
3311
+ constexpr const_iterator cend() const noexcept;
3312
+ constexpr const_reverse_iterator crbegin() const noexcept;
3313
+ constexpr const_reverse_iterator crend() const noexcept;
3314
 
3315
  // capacity
3316
+ constexpr bool empty() const noexcept;
3317
+ constexpr size_type size() const noexcept;
3318
+ constexpr size_type max_size() const noexcept;
3319
 
3320
  // [flat.multiset.modifiers], modifiers
3321
+ template<class... Args> constexpr iterator emplace(Args&&... args);
3322
  template<class... Args>
3323
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
3324
 
3325
+ constexpr iterator insert(const value_type& x)
3326
  { return emplace(x); }
3327
+ constexpr iterator insert(value_type&& x)
3328
  { return emplace(std::move(x)); }
3329
+ constexpr iterator insert(const_iterator position, const value_type& x)
3330
  { return emplace_hint(position, x); }
3331
+ constexpr iterator insert(const_iterator position, value_type&& x)
3332
  { return emplace_hint(position, std::move(x)); }
3333
 
3334
  template<class InputIterator>
3335
+ constexpr void insert(InputIterator first, InputIterator last);
3336
  template<class InputIterator>
3337
+ constexpr void insert(sorted_equivalent_t, InputIterator first, InputIterator last);
3338
  template<container-compatible-range<value_type> R>
3339
+ constexpr void insert_range(R&& rg);
3340
 
3341
+ constexpr void insert(initializer_list<value_type> il)
3342
  { insert(il.begin(), il.end()); }
3343
+ constexpr void insert(sorted_equivalent_t, initializer_list<value_type> il)
3344
+ { insert(sorted_equivalent, il.begin(), il.end()); }
3345
 
3346
+ constexpr container_type extract() &&;
3347
+ constexpr void replace(container_type&&);
3348
 
3349
+ constexpr iterator erase(iterator position);
3350
+ constexpr iterator erase(const_iterator position);
3351
+ constexpr size_type erase(const key_type& x);
3352
+ template<class K> constexpr size_type erase(K&& x);
3353
+ constexpr iterator erase(const_iterator first, const_iterator last);
3354
 
3355
+ constexpr void swap(flat_multiset& y) noexcept;
3356
+ constexpr void clear() noexcept;
3357
 
3358
  // observers
3359
+ constexpr key_compare key_comp() const;
3360
+ constexpr value_compare value_comp() const;
3361
 
3362
  // set operations
3363
+ constexpr iterator find(const key_type& x);
3364
+ constexpr const_iterator find(const key_type& x) const;
3365
+ template<class K> constexpr iterator find(const K& x);
3366
+ template<class K> constexpr const_iterator find(const K& x) const;
3367
 
3368
+ constexpr size_type count(const key_type& x) const;
3369
+ template<class K> constexpr size_type count(const K& x) const;
3370
 
3371
+ constexpr bool contains(const key_type& x) const;
3372
+ template<class K> constexpr bool contains(const K& x) const;
3373
 
3374
+ constexpr iterator lower_bound(const key_type& x);
3375
+ constexpr const_iterator lower_bound(const key_type& x) const;
3376
+ template<class K> constexpr iterator lower_bound(const K& x);
3377
+ template<class K> constexpr const_iterator lower_bound(const K& x) const;
3378
 
3379
+ constexpr iterator upper_bound(const key_type& x);
3380
+ constexpr const_iterator upper_bound(const key_type& x) const;
3381
+ template<class K> constexpr iterator upper_bound(const K& x);
3382
+ template<class K> constexpr const_iterator upper_bound(const K& x) const;
3383
 
3384
+ constexpr pair<iterator, iterator> equal_range(const key_type& x);
3385
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
3386
  template<class K>
3387
+ constexpr pair<iterator, iterator> equal_range(const K& x);
3388
  template<class K>
3389
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
3390
 
3391
+ friend constexpr bool operator==(const flat_multiset& x, const flat_multiset& y);
3392
 
3393
+ friend constexpr synth-three-way-result<value_type>
3394
  operator<=>(const flat_multiset& x, const flat_multiset& y);
3395
 
3396
+ friend constexpr void swap(flat_multiset& x, flat_multiset& y) noexcept
3397
  { x.swap(y); }
3398
 
3399
  private:
3400
  container_type c; // exposition only
3401
  key_compare compare; // exposition only
 
3423
  flat_multiset(sorted_equivalent_t, KeyContainer, Compare, Allocator)
3424
  -> flat_multiset<typename KeyContainer::value_type, Compare, KeyContainer>;
3425
 
3426
  template<class InputIterator, class Compare = less<iter-value-type<InputIterator>>>
3427
  flat_multiset(InputIterator, InputIterator, Compare = Compare())
3428
+ -> flat_multiset<iter-value-type<InputIterator>, Compare>;
3429
 
3430
  template<class InputIterator, class Compare = less<iter-value-type<InputIterator>>>
3431
  flat_multiset(sorted_equivalent_t, InputIterator, InputIterator, Compare = Compare())
3432
+ -> flat_multiset<iter-value-type<InputIterator>, Compare>;
3433
 
3434
  template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
3435
  class Allocator = allocator<ranges::range_value_t<R>>>
3436
  flat_multiset(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
3437
  -> flat_multiset<ranges::range_value_t<R>, Compare,
 
3459
  ```
3460
 
3461
  #### Constructors <a id="flat.multiset.cons">[[flat.multiset.cons]]</a>
3462
 
3463
  ``` cpp
3464
+ constexpr explicit flat_multiset(container_type cont, const key_compare& comp = key_compare());
3465
  ```
3466
 
3467
  *Effects:* Initializes *c* with `std::move(cont)` and *compare* with
3468
  `comp`, and sorts the range \[`begin()`, `end()`) with respect to
3469
  *compare*.
3470
 
3471
+ *Complexity:* Linear in N if `cont` is already sorted with respect to
3472
+ *compare* and otherwise N log N, where N is the value of `cont.size()`
3473
+ before this call.
3474
+
3475
+ #### Constructors with allocators <a id="flat.multiset.cons.alloc">[[flat.multiset.cons.alloc]]</a>
3476
+
3477
+ The constructors in this subclause shall not participate in overload
3478
+ resolution unless `uses_allocator_v<container_type, Alloc>` is `true`.
3479
 
3480
  ``` cpp
3481
+ template<class Alloc>
3482
+ constexpr flat_multiset(const container_type& cont, const Alloc& a);
3483
+ template<class Alloc>
3484
+ constexpr flat_multiset(const container_type& cont, const key_compare& comp, const Alloc& a);
3485
  ```
3486
 
 
 
3487
  *Effects:* Equivalent to `flat_multiset(cont)` and
3488
  `flat_multiset(cont, comp)`, respectively, except that *c* is
3489
  constructed with uses-allocator
3490
  construction [[allocator.uses.construction]].
3491
 
3492
  *Complexity:* Same as `flat_multiset(cont)` and
3493
  `flat_multiset(cont, comp)`, respectively.
3494
 
3495
  ``` cpp
3496
+ template<class Alloc>
3497
+ constexpr flat_multiset(sorted_equivalent_t, const container_type& cont, const Alloc& a);
3498
+ template<class Alloc>
3499
+ constexpr flat_multiset(sorted_equivalent_t, const container_type& cont,
3500
+ const key_compare& comp, const Alloc& a);
3501
  ```
3502
 
3503
+ *Effects:* Equivalent to `flat_multiset(sorted_equivalent, cont)` and
3504
+ `flat_multiset(sorted_equivalent, cont, comp)`, respectively, except
3505
+ that *c* is constructed with uses-allocator
 
 
3506
  construction [[allocator.uses.construction]].
3507
 
3508
  *Complexity:* Linear.
3509
 
3510
  ``` cpp
3511
+ template<class Alloc>
3512
+ constexpr explicit flat_multiset(const Alloc& a);
3513
+ template<class Alloc>
3514
+ constexpr flat_multiset(const key_compare& comp, const Alloc& a);
3515
+ template<class Alloc>
3516
+ constexpr flat_multiset(const flat_multiset&, const Alloc& a);
3517
+ template<class Alloc>
3518
+ constexpr flat_multiset(flat_multiset&&, const Alloc& a);
3519
+ template<class InputIterator, class Alloc>
3520
+ constexpr flat_multiset(InputIterator first, InputIterator last, const Alloc& a);
3521
+ template<class InputIterator, class Alloc>
3522
+ constexpr flat_multiset(InputIterator first, InputIterator last,
3523
+ const key_compare& comp, const Alloc& a);
3524
+ template<class InputIterator, class Alloc>
3525
+ constexpr flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
3526
+ const Alloc& a);
3527
+ template<class InputIterator, class Alloc>
3528
+ constexpr flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
3529
+ const key_compare& comp, const Alloc& a);
3530
+ template<container-compatible-range<value_type> R, class Alloc>
3531
+ constexpr flat_multiset(from_range_t, R&& rg, const Alloc& a);
3532
+ template<container-compatible-range<value_type> R, class Alloc>
3533
+ constexpr flat_multiset(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
3534
+ template<class Alloc>
3535
+ constexpr flat_multiset(initializer_list<value_type> il, const Alloc& a);
3536
+ template<class Alloc>
3537
+ constexpr flat_multiset(initializer_list<value_type> il, const key_compare& comp,
3538
+ const Alloc& a);
3539
+ template<class Alloc>
3540
+ constexpr flat_multiset(sorted_equivalent_t, initializer_list<value_type> il, const Alloc& a);
3541
+ template<class Alloc>
3542
+ constexpr flat_multiset(sorted_equivalent_t, initializer_list<value_type> il,
3543
+ const key_compare& comp, const Alloc& a);
3544
  ```
3545
 
 
 
3546
  *Effects:* Equivalent to the corresponding non-allocator constructors
3547
  except that *c* is constructed with uses-allocator
3548
  construction [[allocator.uses.construction]].
3549
 
3550
  #### Modifiers <a id="flat.multiset.modifiers">[[flat.multiset.modifiers]]</a>
3551
 
3552
  ``` cpp
3553
+ template<class... Args> constexpr iterator emplace(Args&&... args);
3554
  ```
3555
 
3556
  *Constraints:* `is_constructible_v<value_type, Args...>` is `true`.
3557
 
3558
  *Effects:* First, initializes an object `t` of type `value_type` with
 
3565
 
3566
  *Returns:* An iterator that points to the inserted element.
3567
 
3568
  ``` cpp
3569
  template<class InputIterator>
3570
+ constexpr void insert(InputIterator first, InputIterator last);
3571
  ```
3572
 
3573
  *Effects:* Adds elements to *c* as if by:
3574
 
3575
  ``` cpp
 
3586
  *Remarks:* Since this operation performs an in-place merge, it may
3587
  allocate memory.
3588
 
3589
  ``` cpp
3590
  template<class InputIterator>
3591
+ constexpr void insert(sorted_equivalent_t, InputIterator first, InputIterator last);
3592
  ```
3593
 
3594
  *Effects:* Equivalent to `insert(first, last)`.
3595
 
3596
  *Complexity:* Linear.
3597
 
3598
  ``` cpp
3599
+ constexpr void swap(flat_multiset& y) noexcept;
3600
  ```
3601
 
3602
  *Effects:* Equivalent to:
3603
 
3604
  ``` cpp
3605
  ranges::swap(compare, y.compare);
3606
  ranges::swap(c, y.c);
3607
  ```
3608
 
3609
  ``` cpp
3610
+ constexpr container_type extract() &&;
3611
  ```
3612
 
3613
  *Ensures:* `*this` is emptied, even if the function exits via an
3614
  exception.
3615
 
3616
+ *Returns:* `std::move(`*`c`*`)`.
3617
 
3618
  ``` cpp
3619
+ constexpr void replace(container_type&& cont);
3620
  ```
3621
 
3622
  *Preconditions:* The elements of `cont` are sorted with respect to
3623
  *compare*.
3624
 
3625
+ *Effects:* Equivalent to: *`c`*` = std::move(cont);`
3626
 
3627
  #### Erasure <a id="flat.multiset.erasure">[[flat.multiset.erasure]]</a>
3628
 
3629
  ``` cpp
3630
  template<class Key, class Compare, class KeyContainer, class Predicate>
3631
+ constexpr typename flat_multiset<Key, Compare, KeyContainer>::size_type
3632
  erase_if(flat_multiset<Key, Compare, KeyContainer>& c, Predicate pred);
3633
  ```
3634
 
3635
  *Preconditions:* `Key` meets the *Cpp17MoveAssignable* requirements.
3636