From Jason Turner

[flat.set]

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

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmp8i71ne_6/{from.md → to.md} +201 -182
tmp/tmp8i71ne_6/{from.md → to.md} RENAMED
@@ -52,13 +52,16 @@ particular, `vector` [[vector]] and `deque` [[deque]] can be used.
52
  [*Note 3*: `vector<bool>` is not a sequence container. — *end note*]
53
 
54
  The program is ill-formed if `Key` is not the same type as
55
  `KeyContainer::value_type`.
56
 
57
- The effect of calling a constructor or member function that takes a
58
- `sorted_unique_t` argument with a range that is not sorted with respect
59
- to `key_comp()`, or that contains equal elements, is undefined.
 
 
 
60
 
61
  #### Definition <a id="flat.set.defn">[[flat.set.defn]]</a>
62
 
63
  ``` cpp
64
  namespace std {
@@ -70,192 +73,203 @@ namespace std {
70
  using value_type = Key;
71
  using key_compare = Compare;
72
  using value_compare = Compare;
73
  using reference = value_type&;
74
  using const_reference = const value_type&;
75
- using size_type = typename KeyContainer::size_type;
76
- using difference_type = typename KeyContainer::difference_type;
77
  using iterator = implementation-defined // type of flat_set::iterator; // see [container.requirements]
78
  using const_iterator = implementation-defined // type of flat_set::const_iterator; // see [container.requirements]
79
  using reverse_iterator = std::reverse_iterator<iterator>;
80
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
81
  using container_type = KeyContainer;
82
 
83
  // [flat.set.cons], constructors
84
- flat_set() : flat_set(key_compare()) { }
85
 
86
- explicit flat_set(container_type cont, const key_compare& comp = key_compare());
87
- template<class Allocator>
88
- flat_set(const container_type& cont, const Allocator& a);
89
- template<class Allocator>
90
- flat_set(const container_type& cont, const key_compare& comp, const Allocator& a);
91
-
92
- flat_set(sorted_unique_t, container_type cont, const key_compare& comp = key_compare())
93
- : c(std::move(cont)), compare(comp) { }
94
- template<class Allocator>
95
- flat_set(sorted_unique_t, const container_type& cont, const Allocator& a);
96
- template<class Allocator>
97
- flat_set(sorted_unique_t, const container_type& cont,
98
- const key_compare& comp, const Allocator& a);
99
-
100
- explicit flat_set(const key_compare& comp)
101
  : c(), compare(comp) { }
102
- template<class Allocator>
103
- flat_set(const key_compare& comp, const Allocator& a);
104
- template<class Allocator>
105
- explicit flat_set(const Allocator& a);
 
 
106
 
107
  template<class InputIterator>
108
- flat_set(InputIterator first, InputIterator last, const key_compare& comp = key_compare())
 
109
  : c(), compare(comp)
110
  { insert(first, last); }
111
- template<class InputIterator, class Allocator>
112
- flat_set(InputIterator first, InputIterator last,
113
- const key_compare& comp, const Allocator& a);
114
- template<class InputIterator, class Allocator>
115
- flat_set(InputIterator first, InputIterator last, const Allocator& a);
116
 
117
  template<container-compatible-range<value_type> R>
118
- flat_set(from_range_t fr, R&& rg)
119
- : flat_set(fr, std::forward<R>(rg), key_compare()) { }
120
- template<container-compatible-range<value_type> R, class Allocator>
121
- flat_set(from_range_t, R&& rg, const Allocator& a);
122
  template<container-compatible-range<value_type> R>
123
- flat_set(from_range_t, R&& rg, const key_compare& comp)
124
  : flat_set(comp)
125
  { insert_range(std::forward<R>(rg)); }
126
- template<container-compatible-range<value_type> R, class Allocator>
127
- flat_set(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
128
 
129
- template<class InputIterator>
130
- flat_set(sorted_unique_t, InputIterator first, InputIterator last,
131
- const key_compare& comp = key_compare())
132
- : c(first, last), compare(comp) { }
133
- template<class InputIterator, class Allocator>
134
- flat_set(sorted_unique_t, InputIterator first, InputIterator last,
135
- const key_compare& comp, const Allocator& a);
136
- template<class InputIterator, class Allocator>
137
- flat_set(sorted_unique_t, InputIterator first, InputIterator last, const Allocator& a);
138
-
139
- flat_set(initializer_list<value_type> il, const key_compare& comp = key_compare())
140
  : flat_set(il.begin(), il.end(), comp) { }
141
- template<class Allocator>
142
- flat_set(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
143
- template<class Allocator>
144
- flat_set(initializer_list<value_type> il, const Allocator& a);
145
 
146
- flat_set(sorted_unique_t s, initializer_list<value_type> il,
147
  const key_compare& comp = key_compare())
148
- : flat_set(s, il.begin(), il.end(), comp) { }
149
- template<class Allocator>
150
- flat_set(sorted_unique_t, initializer_list<value_type> il,
151
- const key_compare& comp, const Allocator& a);
152
- template<class Allocator>
153
- flat_set(sorted_unique_t, initializer_list<value_type> il, const Allocator& a);
154
 
155
- flat_set& operator=(initializer_list<value_type>);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
156
 
157
  // iterators
158
- iterator begin() noexcept;
159
- const_iterator begin() const noexcept;
160
- iterator end() noexcept;
161
- const_iterator end() const noexcept;
162
 
163
- reverse_iterator rbegin() noexcept;
164
- const_reverse_iterator rbegin() const noexcept;
165
- reverse_iterator rend() noexcept;
166
- const_reverse_iterator rend() const noexcept;
167
 
168
- const_iterator cbegin() const noexcept;
169
- const_iterator cend() const noexcept;
170
- const_reverse_iterator crbegin() const noexcept;
171
- const_reverse_iterator crend() const noexcept;
172
 
173
  // capacity
174
- [[nodiscard]] bool empty() const noexcept;
175
- size_type size() const noexcept;
176
- size_type max_size() const noexcept;
177
 
178
  // [flat.set.modifiers], modifiers
179
- template<class... Args> pair<iterator, bool> emplace(Args&&... args);
180
  template<class... Args>
181
- iterator emplace_hint(const_iterator position, Args&&... args);
182
 
183
- pair<iterator, bool> insert(const value_type& x)
184
  { return emplace(x); }
185
- pair<iterator, bool> insert(value_type&& x)
186
  { return emplace(std::move(x)); }
187
- template<class K> pair<iterator, bool> insert(K&& x);
188
- iterator insert(const_iterator position, const value_type& x)
189
  { return emplace_hint(position, x); }
190
- iterator insert(const_iterator position, value_type&& x)
191
  { return emplace_hint(position, std::move(x)); }
192
- template<class K> iterator insert(const_iterator hint, K&& x);
193
 
194
  template<class InputIterator>
195
- void insert(InputIterator first, InputIterator last);
196
  template<class InputIterator>
197
- void insert(sorted_unique_t, InputIterator first, InputIterator last);
198
  template<container-compatible-range<value_type> R>
199
- void insert_range(R&& rg);
200
 
201
- void insert(initializer_list<value_type> il)
202
  { insert(il.begin(), il.end()); }
203
- void insert(sorted_unique_t s, initializer_list<value_type> il)
204
- { insert(s, il.begin(), il.end()); }
205
 
206
- container_type extract() &&;
207
- void replace(container_type&&);
208
 
209
- iterator erase(iterator position);
210
- iterator erase(const_iterator position);
211
- size_type erase(const key_type& x);
212
- template<class K> size_type erase(K&& x);
213
- iterator erase(const_iterator first, const_iterator last);
214
 
215
- void swap(flat_set& y) noexcept;
216
- void clear() noexcept;
217
 
218
  // observers
219
- key_compare key_comp() const;
220
- value_compare value_comp() const;
221
 
222
  // set operations
223
- iterator find(const key_type& x);
224
- const_iterator find(const key_type& x) const;
225
- template<class K> iterator find(const K& x);
226
- template<class K> const_iterator find(const K& x) const;
227
 
228
- size_type count(const key_type& x) const;
229
- template<class K> size_type count(const K& x) const;
230
 
231
- bool contains(const key_type& x) const;
232
- template<class K> bool contains(const K& x) const;
233
 
234
- iterator lower_bound(const key_type& x);
235
- const_iterator lower_bound(const key_type& x) const;
236
- template<class K> iterator lower_bound(const K& x);
237
- template<class K> const_iterator lower_bound(const K& x) const;
238
 
239
- iterator upper_bound(const key_type& x);
240
- const_iterator upper_bound(const key_type& x) const;
241
- template<class K> iterator upper_bound(const K& x);
242
- template<class K> const_iterator upper_bound(const K& x) const;
243
 
244
- pair<iterator, iterator> equal_range(const key_type& x);
245
- pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
246
  template<class K>
247
- pair<iterator, iterator> equal_range(const K& x);
248
  template<class K>
249
- pair<const_iterator, const_iterator> equal_range(const K& x) const;
250
 
251
- friend bool operator==(const flat_set& x, const flat_set& y);
252
 
253
- friend synth-three-way-result<value_type>
254
  operator<=>(const flat_set& x, const flat_set& y);
255
 
256
- friend void swap(flat_set& x, flat_set& y) noexcept { x.swap(y); }
257
 
258
  private:
259
  container_type c; // exposition only
260
  key_compare compare; // exposition only
261
  };
@@ -318,101 +332,106 @@ namespace std {
318
  ```
319
 
320
  #### Constructors <a id="flat.set.cons">[[flat.set.cons]]</a>
321
 
322
  ``` cpp
323
- explicit flat_set(container_type cont, const key_compare& comp = key_compare());
324
  ```
325
 
326
  *Effects:* Initializes *c* with `std::move(cont)` and *compare* with
327
  `comp`, sorts the range \[`begin()`, `end()`) with respect to *compare*,
328
  and finally erases all but the first element from each group of
329
  consecutive equivalent elements.
330
 
331
- *Complexity:* Linear in N if `cont` is sorted with respect to *compare*
332
- and otherwise N log N, where N is the value of `cont.size()` before this
333
- call.
 
 
 
 
 
334
 
335
  ``` cpp
336
- template<class Allocator>
337
- flat_set(const container_type& cont, const Allocator& a);
338
- template<class Allocator>
339
- flat_set(const container_type& cont, const key_compare& comp, const Allocator& a);
340
  ```
341
 
342
- *Constraints:* `uses_allocator_v<container_type, Allocator>` is `true`.
343
-
344
  *Effects:* Equivalent to `flat_set(cont)` and `flat_set(cont, comp)`,
345
  respectively, except that *c* is constructed with uses-allocator
346
  construction [[allocator.uses.construction]].
347
 
348
  *Complexity:* Same as `flat_set(cont)` and `flat_set(cont, comp)`,
349
  respectively.
350
 
351
  ``` cpp
352
- template<class Allocator>
353
- flat_set(sorted_unique_t s, const container_type& cont, const Allocator& a);
354
- template<class Allocator>
355
- flat_set(sorted_unique_t s, const container_type& cont,
356
- const key_compare& comp, const Allocator& a);
357
  ```
358
 
359
- *Constraints:* `uses_allocator_v<container_type, Allocator>` is `true`.
360
-
361
- *Effects:* Equivalent to `flat_set(s, cont)` and
362
- `flat_set(s, cont, comp)`, respectively, except that *c* is constructed
363
- with uses-allocator construction [[allocator.uses.construction]].
364
 
365
  *Complexity:* Linear.
366
 
367
  ``` cpp
368
- template<class Allocator>
369
- flat_set(const key_compare& comp, const Allocator& a);
370
- template<class Allocator>
371
- explicit flat_set(const Allocator& a);
372
- template<class InputIterator, class Allocator>
373
- flat_set(InputIterator first, InputIterator last, const key_compare& comp, const Allocator& a);
374
- template<class InputIterator, class Allocator>
375
- flat_set(InputIterator first, InputIterator last, const Allocator& a);
376
- template<container-compatible-range<value_type> R, class Allocator>
377
- flat_set(from_range_t, R&& rg, const Allocator& a);
378
- template<container-compatible-range<value_type> R, class Allocator>
379
- flat_set(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
380
- template<class InputIterator, class Allocator>
381
- flat_set(sorted_unique_t, InputIterator first, InputIterator last,
382
- const key_compare& comp, const Allocator& a);
383
- template<class InputIterator, class Allocator>
384
- flat_set(sorted_unique_t, InputIterator first, InputIterator last, const Allocator& a);
385
- template<class Allocator>
386
- flat_set(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
387
- template<class Allocator>
388
- flat_set(initializer_list<value_type> il, const Allocator& a);
389
- template<class Allocator>
390
- flat_set(sorted_unique_t, initializer_list<value_type> il,
391
- const key_compare& comp, const Allocator& a);
392
- template<class Allocator>
393
- flat_set(sorted_unique_t, initializer_list<value_type> il, const Allocator& a);
 
 
 
 
 
394
  ```
395
 
396
- *Constraints:* `uses_allocator_v<container_type, Allocator>` is `true`.
397
-
398
  *Effects:* Equivalent to the corresponding non-allocator constructors
399
  except that *c* is constructed with uses-allocator
400
  construction [[allocator.uses.construction]].
401
 
402
  #### Modifiers <a id="flat.set.modifiers">[[flat.set.modifiers]]</a>
403
 
404
  ``` cpp
405
- template<class K> pair<iterator, bool> insert(K&& x);
406
- template<class K> iterator insert(const_iterator hint, K&& x);
407
  ```
408
 
409
  *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
410
  denotes a type. `is_constructible_v<value_type, K>` is `true`.
411
 
412
  *Preconditions:* The conversion from `x` into `value_type` constructs an
413
- object `u`, for which `find(x) == find(u)` is true.
414
 
415
  *Effects:* If the set already contains an element equivalent to `x`,
416
  `*this` and `x` are unchanged. Otherwise, inserts a new element as if by
417
  `emplace(std::forward<K>(x))`.
418
 
@@ -420,11 +439,11 @@ object `u`, for which `find(x) == find(u)` is true.
420
  pair is `true` if and only if the insertion took place. The returned
421
  iterator points to the element whose key is equivalent to `x`.
422
 
423
  ``` cpp
424
  template<class InputIterator>
425
- void insert(InputIterator first, InputIterator last);
426
  ```
427
 
428
  *Effects:* Adds elements to *c* as if by:
429
 
430
  ``` cpp
@@ -443,20 +462,20 @@ M is `distance(first, last)`.
443
  *Remarks:* Since this operation performs an in-place merge, it may
444
  allocate memory.
445
 
446
  ``` cpp
447
  template<class InputIterator>
448
- void insert(sorted_unique_t, InputIterator first, InputIterator last);
449
  ```
450
 
451
  *Effects:* Equivalent to `insert(first, last)`.
452
 
453
  *Complexity:* Linear.
454
 
455
  ``` cpp
456
  template<container-compatible-range<value_type> R>
457
- void insert_range(R&& rg);
458
  ```
459
 
460
  *Effects:* Adds elements to *c* as if by:
461
 
462
  ``` cpp
@@ -476,31 +495,31 @@ M is `ranges::distance(rg)`.
476
 
477
  *Remarks:* Since this operation performs an in-place merge, it may
478
  allocate memory.
479
 
480
  ``` cpp
481
- void swap(flat_set& y) noexcept;
482
  ```
483
 
484
  *Effects:* Equivalent to:
485
 
486
  ``` cpp
487
  ranges::swap(compare, y.compare);
488
  ranges::swap(c, y.c);
489
  ```
490
 
491
  ``` cpp
492
- container_type extract() &&;
493
  ```
494
 
495
  *Ensures:* `*this` is emptied, even if the function exits via an
496
  exception.
497
 
498
  *Returns:* `std::move(`*`c`*`)`.
499
 
500
  ``` cpp
501
- void replace(container_type&& cont);
502
  ```
503
 
504
  *Preconditions:* The elements of `cont` are sorted with respect to
505
  *compare*, and `cont` contains no equal elements.
506
 
@@ -508,11 +527,11 @@ void replace(container_type&& cont);
508
 
509
  #### Erasure <a id="flat.set.erasure">[[flat.set.erasure]]</a>
510
 
511
  ``` cpp
512
  template<class Key, class Compare, class KeyContainer, class Predicate>
513
- typename flat_set<Key, Compare, KeyContainer>::size_type
514
  erase_if(flat_set<Key, Compare, KeyContainer>& c, Predicate pred);
515
  ```
516
 
517
  *Preconditions:* `Key` meets the *Cpp17MoveAssignable* requirements.
518
 
 
52
  [*Note 3*: `vector<bool>` is not a sequence container. — *end note*]
53
 
54
  The program is ill-formed if `Key` is not the same type as
55
  `KeyContainer::value_type`.
56
 
57
+ The effect of calling a member function that takes a `sorted_unique_t`
58
+ argument with a range that is not sorted with respect to `key_comp()`,
59
+ or that contains equal elements, is undefined.
60
+
61
+ The types `iterator` and `const_iterator` meet the constexpr iterator
62
+ requirements [[iterator.requirements.general]].
63
 
64
  #### Definition <a id="flat.set.defn">[[flat.set.defn]]</a>
65
 
66
  ``` cpp
67
  namespace std {
 
73
  using value_type = Key;
74
  using key_compare = Compare;
75
  using value_compare = Compare;
76
  using reference = value_type&;
77
  using const_reference = const value_type&;
78
+ using size_type = KeyContainer::size_type;
79
+ using difference_type = KeyContainer::difference_type;
80
  using iterator = implementation-defined // type of flat_set::iterator; // see [container.requirements]
81
  using const_iterator = implementation-defined // type of flat_set::const_iterator; // see [container.requirements]
82
  using reverse_iterator = std::reverse_iterator<iterator>;
83
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
84
  using container_type = KeyContainer;
85
 
86
  // [flat.set.cons], constructors
87
+ constexpr flat_set() : flat_set(key_compare()) { }
88
 
89
+ constexpr explicit flat_set(const key_compare& comp)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
90
  : c(), compare(comp) { }
91
+
92
+ constexpr explicit flat_set(container_type cont, const key_compare& comp = key_compare());
93
+
94
+ constexpr flat_set(sorted_unique_t, container_type cont,
95
+ const key_compare& comp = key_compare())
96
+ : c(std::move(cont)), compare(comp) { }
97
 
98
  template<class InputIterator>
99
+ constexpr flat_set(InputIterator first, InputIterator last,
100
+ const key_compare& comp = key_compare())
101
  : c(), compare(comp)
102
  { insert(first, last); }
103
+
104
+ template<class InputIterator>
105
+ constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last,
106
+ const key_compare& comp = key_compare())
107
+ : c(first, last), compare(comp) { }
108
 
109
  template<container-compatible-range<value_type> R>
110
+ constexpr flat_set(from_range_t, R&& rg)
111
+ : flat_set(from_range, std::forward<R>(rg), key_compare()) { }
 
 
112
  template<container-compatible-range<value_type> R>
113
+ constexpr flat_set(from_range_t, R&& rg, const key_compare& comp)
114
  : flat_set(comp)
115
  { insert_range(std::forward<R>(rg)); }
 
 
116
 
117
+ constexpr flat_set(initializer_list<value_type> il, const key_compare& comp = key_compare())
 
 
 
 
 
 
 
 
 
 
118
  : flat_set(il.begin(), il.end(), comp) { }
 
 
 
 
119
 
120
+ constexpr flat_set(sorted_unique_t, initializer_list<value_type> il,
121
  const key_compare& comp = key_compare())
122
+ : flat_set(sorted_unique, il.begin(), il.end(), comp) { }
 
 
 
 
 
123
 
124
+ // [flat.set.cons.alloc], constructors with allocators
125
+
126
+ template<class Alloc>
127
+ constexpr explicit flat_set(const Alloc& a);
128
+ template<class Alloc>
129
+ constexpr flat_set(const key_compare& comp, const Alloc& a);
130
+ template<class Alloc>
131
+ constexpr flat_set(const container_type& cont, const Alloc& a);
132
+ template<class Alloc>
133
+ constexpr flat_set(const container_type& cont, const key_compare& comp, const Alloc& a);
134
+ template<class Alloc>
135
+ constexpr flat_set(sorted_unique_t, const container_type& cont, const Alloc& a);
136
+ template<class Alloc>
137
+ constexpr flat_set(sorted_unique_t, const container_type& cont,
138
+ const key_compare& comp, const Alloc& a);
139
+ template<class Alloc>
140
+ constexpr flat_set(const flat_set&, const Alloc& a);
141
+ template<class Alloc>
142
+ constexpr flat_set(flat_set&&, const Alloc& a);
143
+ template<class InputIterator, class Alloc>
144
+ constexpr flat_set(InputIterator first, InputIterator last, const Alloc& a);
145
+ template<class InputIterator, class Alloc>
146
+ constexpr flat_set(InputIterator first, InputIterator last,
147
+ const key_compare& comp, const Alloc& a);
148
+ template<class InputIterator, class Alloc>
149
+ constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last,
150
+ const Alloc& a);
151
+ template<class InputIterator, class Alloc>
152
+ constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last,
153
+ const key_compare& comp, const Alloc& a);
154
+ template<container-compatible-range<value_type> R, class Alloc>
155
+ constexpr flat_set(from_range_t, R&& rg, const Alloc& a);
156
+ template<container-compatible-range<value_type> R, class Alloc>
157
+ constexpr flat_set(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
158
+ template<class Alloc>
159
+ constexpr flat_set(initializer_list<value_type> il, const Alloc& a);
160
+ template<class Alloc>
161
+ constexpr flat_set(initializer_list<value_type> il, const key_compare& comp,
162
+ const Alloc& a);
163
+ template<class Alloc>
164
+ constexpr flat_set(sorted_unique_t, initializer_list<value_type> il, const Alloc& a);
165
+ template<class Alloc>
166
+ constexpr flat_set(sorted_unique_t, initializer_list<value_type> il,
167
+ const key_compare& comp, const Alloc& a);
168
+
169
+ constexpr flat_set& operator=(initializer_list<value_type>);
170
 
171
  // iterators
172
+ constexpr iterator begin() noexcept;
173
+ constexpr const_iterator begin() const noexcept;
174
+ constexpr iterator end() noexcept;
175
+ constexpr const_iterator end() const noexcept;
176
 
177
+ constexpr reverse_iterator rbegin() noexcept;
178
+ constexpr const_reverse_iterator rbegin() const noexcept;
179
+ constexpr reverse_iterator rend() noexcept;
180
+ constexpr const_reverse_iterator rend() const noexcept;
181
 
182
+ constexpr const_iterator cbegin() const noexcept;
183
+ constexpr const_iterator cend() const noexcept;
184
+ constexpr const_reverse_iterator crbegin() const noexcept;
185
+ constexpr const_reverse_iterator crend() const noexcept;
186
 
187
  // capacity
188
+ constexpr bool empty() const noexcept;
189
+ constexpr size_type size() const noexcept;
190
+ constexpr size_type max_size() const noexcept;
191
 
192
  // [flat.set.modifiers], modifiers
193
+ template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
194
  template<class... Args>
195
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
196
 
197
+ constexpr pair<iterator, bool> insert(const value_type& x)
198
  { return emplace(x); }
199
+ constexpr pair<iterator, bool> insert(value_type&& x)
200
  { return emplace(std::move(x)); }
201
+ template<class K> constexpr pair<iterator, bool> insert(K&& x);
202
+ constexpr iterator insert(const_iterator position, const value_type& x)
203
  { return emplace_hint(position, x); }
204
+ constexpr iterator insert(const_iterator position, value_type&& x)
205
  { return emplace_hint(position, std::move(x)); }
206
+ template<class K> constexpr iterator insert(const_iterator hint, K&& x);
207
 
208
  template<class InputIterator>
209
+ constexpr void insert(InputIterator first, InputIterator last);
210
  template<class InputIterator>
211
+ constexpr void insert(sorted_unique_t, InputIterator first, InputIterator last);
212
  template<container-compatible-range<value_type> R>
213
+ constexpr void insert_range(R&& rg);
214
 
215
+ constexpr void insert(initializer_list<value_type> il)
216
  { insert(il.begin(), il.end()); }
217
+ constexpr void insert(sorted_unique_t, initializer_list<value_type> il)
218
+ { insert(sorted_unique, il.begin(), il.end()); }
219
 
220
+ constexpr container_type extract() &&;
221
+ constexpr void replace(container_type&&);
222
 
223
+ constexpr iterator erase(iterator position);
224
+ constexpr iterator erase(const_iterator position);
225
+ constexpr size_type erase(const key_type& x);
226
+ template<class K> constexpr size_type erase(K&& x);
227
+ constexpr iterator erase(const_iterator first, const_iterator last);
228
 
229
+ constexpr void swap(flat_set& y) noexcept;
230
+ constexpr void clear() noexcept;
231
 
232
  // observers
233
+ constexpr key_compare key_comp() const;
234
+ constexpr value_compare value_comp() const;
235
 
236
  // set operations
237
+ constexpr iterator find(const key_type& x);
238
+ constexpr const_iterator find(const key_type& x) const;
239
+ template<class K> constexpr iterator find(const K& x);
240
+ template<class K> constexpr const_iterator find(const K& x) const;
241
 
242
+ constexpr size_type count(const key_type& x) const;
243
+ template<class K> constexpr size_type count(const K& x) const;
244
 
245
+ constexpr bool contains(const key_type& x) const;
246
+ template<class K> constexpr bool contains(const K& x) const;
247
 
248
+ constexpr iterator lower_bound(const key_type& x);
249
+ constexpr const_iterator lower_bound(const key_type& x) const;
250
+ template<class K> constexpr iterator lower_bound(const K& x);
251
+ template<class K> constexpr const_iterator lower_bound(const K& x) const;
252
 
253
+ constexpr iterator upper_bound(const key_type& x);
254
+ constexpr const_iterator upper_bound(const key_type& x) const;
255
+ template<class K> constexpr iterator upper_bound(const K& x);
256
+ template<class K> constexpr const_iterator upper_bound(const K& x) const;
257
 
258
+ constexpr pair<iterator, iterator> equal_range(const key_type& x);
259
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
260
  template<class K>
261
+ constexpr pair<iterator, iterator> equal_range(const K& x);
262
  template<class K>
263
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
264
 
265
+ friend constexpr bool operator==(const flat_set& x, const flat_set& y);
266
 
267
+ friend constexpr synth-three-way-result<value_type>
268
  operator<=>(const flat_set& x, const flat_set& y);
269
 
270
+ friend constexpr void swap(flat_set& x, flat_set& y) noexcept { x.swap(y); }
271
 
272
  private:
273
  container_type c; // exposition only
274
  key_compare compare; // exposition only
275
  };
 
332
  ```
333
 
334
  #### Constructors <a id="flat.set.cons">[[flat.set.cons]]</a>
335
 
336
  ``` cpp
337
+ constexpr explicit flat_set(container_type cont, const key_compare& comp = key_compare());
338
  ```
339
 
340
  *Effects:* Initializes *c* with `std::move(cont)` and *compare* with
341
  `comp`, sorts the range \[`begin()`, `end()`) with respect to *compare*,
342
  and finally erases all but the first element from each group of
343
  consecutive equivalent elements.
344
 
345
+ *Complexity:* Linear in N if `cont` is already sorted with respect to
346
+ *compare* and otherwise N log N, where N is the value of `cont.size()`
347
+ before this call.
348
+
349
+ #### Constructors with allocators <a id="flat.set.cons.alloc">[[flat.set.cons.alloc]]</a>
350
+
351
+ The constructors in this subclause shall not participate in overload
352
+ resolution unless `uses_allocator_v<container_type, Alloc>` is `true`.
353
 
354
  ``` cpp
355
+ template<class Alloc>
356
+ constexpr flat_set(const container_type& cont, const Alloc& a);
357
+ template<class Alloc>
358
+ constexpr flat_set(const container_type& cont, const key_compare& comp, const Alloc& a);
359
  ```
360
 
 
 
361
  *Effects:* Equivalent to `flat_set(cont)` and `flat_set(cont, comp)`,
362
  respectively, except that *c* is constructed with uses-allocator
363
  construction [[allocator.uses.construction]].
364
 
365
  *Complexity:* Same as `flat_set(cont)` and `flat_set(cont, comp)`,
366
  respectively.
367
 
368
  ``` cpp
369
+ template<class Alloc>
370
+ constexpr flat_set(sorted_unique_t, const container_type& cont, const Alloc& a);
371
+ template<class Alloc>
372
+ constexpr flat_set(sorted_unique_t, const container_type& cont,
373
+ const key_compare& comp, const Alloc& a);
374
  ```
375
 
376
+ *Effects:* Equivalent to `flat_set(sorted_unique, cont)` and
377
+ `flat_set(sorted_unique, cont,comp)`, respectively, except that *c* is
378
+ constructed with uses-allocator
379
+ construction [[allocator.uses.construction]].
 
380
 
381
  *Complexity:* Linear.
382
 
383
  ``` cpp
384
+ template<class Alloc>
385
+ constexpr explicit flat_set(const Alloc& a);
386
+ template<class Alloc>
387
+ constexpr flat_set(const key_compare& comp, const Alloc& a);
388
+ template<class Alloc>
389
+ constexpr flat_set(const flat_set&, const Alloc& a);
390
+ template<class Alloc>
391
+ constexpr flat_set(flat_set&&, const Alloc& a);
392
+ template<class InputIterator, class Alloc>
393
+ constexpr flat_set(InputIterator first, InputIterator last, const Alloc& a);
394
+ template<class InputIterator, class Alloc>
395
+ constexpr flat_set(InputIterator first, InputIterator last, const key_compare& comp,
396
+ const Alloc& a);
397
+ template<class InputIterator, class Alloc>
398
+ constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last, const Alloc& a);
399
+ template<class InputIterator, class Alloc>
400
+ constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last,
401
+ const key_compare& comp, const Alloc& a);
402
+ template<container-compatible-range<value_type> R, class Alloc>
403
+ constexpr flat_set(from_range_t, R&& rg, const Alloc& a);
404
+ template<container-compatible-range<value_type> R, class Alloc>
405
+ constexpr flat_set(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
406
+ template<class Alloc>
407
+ constexpr flat_set(initializer_list<value_type> il, const Alloc& a);
408
+ template<class Alloc>
409
+ constexpr flat_set(initializer_list<value_type> il, const key_compare& comp, const Alloc& a);
410
+ template<class Alloc>
411
+ constexpr flat_set(sorted_unique_t, initializer_list<value_type> il, const Alloc& a);
412
+ template<class Alloc>
413
+ constexpr flat_set(sorted_unique_t, initializer_list<value_type> il,
414
+ const key_compare& comp, const Alloc& a);
415
  ```
416
 
 
 
417
  *Effects:* Equivalent to the corresponding non-allocator constructors
418
  except that *c* is constructed with uses-allocator
419
  construction [[allocator.uses.construction]].
420
 
421
  #### Modifiers <a id="flat.set.modifiers">[[flat.set.modifiers]]</a>
422
 
423
  ``` cpp
424
+ template<class K> constexpr pair<iterator, bool> insert(K&& x);
425
+ template<class K> constexpr iterator insert(const_iterator hint, K&& x);
426
  ```
427
 
428
  *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
429
  denotes a type. `is_constructible_v<value_type, K>` is `true`.
430
 
431
  *Preconditions:* The conversion from `x` into `value_type` constructs an
432
+ object `u`, for which `find(x) == find(u)` is `true`.
433
 
434
  *Effects:* If the set already contains an element equivalent to `x`,
435
  `*this` and `x` are unchanged. Otherwise, inserts a new element as if by
436
  `emplace(std::forward<K>(x))`.
437
 
 
439
  pair is `true` if and only if the insertion took place. The returned
440
  iterator points to the element whose key is equivalent to `x`.
441
 
442
  ``` cpp
443
  template<class InputIterator>
444
+ constexpr void insert(InputIterator first, InputIterator last);
445
  ```
446
 
447
  *Effects:* Adds elements to *c* as if by:
448
 
449
  ``` cpp
 
462
  *Remarks:* Since this operation performs an in-place merge, it may
463
  allocate memory.
464
 
465
  ``` cpp
466
  template<class InputIterator>
467
+ constexpr void insert(sorted_unique_t, InputIterator first, InputIterator last);
468
  ```
469
 
470
  *Effects:* Equivalent to `insert(first, last)`.
471
 
472
  *Complexity:* Linear.
473
 
474
  ``` cpp
475
  template<container-compatible-range<value_type> R>
476
+ constexpr void insert_range(R&& rg);
477
  ```
478
 
479
  *Effects:* Adds elements to *c* as if by:
480
 
481
  ``` cpp
 
495
 
496
  *Remarks:* Since this operation performs an in-place merge, it may
497
  allocate memory.
498
 
499
  ``` cpp
500
+ constexpr void swap(flat_set& y) noexcept;
501
  ```
502
 
503
  *Effects:* Equivalent to:
504
 
505
  ``` cpp
506
  ranges::swap(compare, y.compare);
507
  ranges::swap(c, y.c);
508
  ```
509
 
510
  ``` cpp
511
+ constexpr container_type extract() &&;
512
  ```
513
 
514
  *Ensures:* `*this` is emptied, even if the function exits via an
515
  exception.
516
 
517
  *Returns:* `std::move(`*`c`*`)`.
518
 
519
  ``` cpp
520
+ constexpr void replace(container_type&& cont);
521
  ```
522
 
523
  *Preconditions:* The elements of `cont` are sorted with respect to
524
  *compare*, and `cont` contains no equal elements.
525
 
 
527
 
528
  #### Erasure <a id="flat.set.erasure">[[flat.set.erasure]]</a>
529
 
530
  ``` cpp
531
  template<class Key, class Compare, class KeyContainer, class Predicate>
532
+ constexpr typename flat_set<Key, Compare, KeyContainer>::size_type
533
  erase_if(flat_set<Key, Compare, KeyContainer>& c, Predicate pred);
534
  ```
535
 
536
  *Preconditions:* `Key` meets the *Cpp17MoveAssignable* requirements.
537