1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_FLAT_SET
11#define _LIBCPP_FLAT_SET
12
13/*
14 Header <flat_set> synopsis
15
16#include <compare> // see [compare.syn]
17#include <initializer_list> // see [initializer.list.syn]
18
19namespace std {
20 struct sorted_unique_t { explicit sorted_unique_t() = default; };
21 inline constexpr sorted_unique_t sorted_unique{};
22
23 // [flat.set], class template flat_set
24 template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>
25 class flat_set {
26 public:
27 // types
28 using key_type = Key;
29 using value_type = Key;
30 using key_compare = Compare;
31 using value_compare = Compare;
32 using reference = value_type&;
33 using const_reference = const value_type&;
34 using size_type = KeyContainer::size_type;
35 using difference_type = KeyContainer::difference_type;
36 using iterator = implementation-defined; // see [container.requirements]
37 using const_iterator = implementation-defined; // see [container.requirements]
38 using reverse_iterator = std::reverse_iterator<iterator>;
39 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
40 using container_type = KeyContainer;
41
42 // [flat.set.cons], constructors
43 constexpr flat_set() : flat_set(key_compare()) { }
44
45 constexpr flat_set(const flat_set&);
46 constexpr flat_set(flat_set&&);
47 constexpr flat_set& operator=(const flat_set&);
48 constexpr flat_set& operator=(flat_set&&);
49
50 constexpr explicit flat_set(const key_compare& comp)
51 : c(), compare(comp) { }
52
53 constexpr explicit flat_set(container_type cont, const key_compare& comp = key_compare());
54
55 constexpr flat_set(sorted_unique_t, container_type cont,
56 const key_compare& comp = key_compare())
57 : c(std::move(cont)), compare(comp) { }
58
59 template<class InputIterator>
60 constexpr flat_set(InputIterator first, InputIterator last,
61 const key_compare& comp = key_compare())
62 : c(), compare(comp)
63 { insert(first, last); }
64
65 template<class InputIterator>
66 constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last,
67 const key_compare& comp = key_compare())
68 : c(first, last), compare(comp) { }
69
70 template<container-compatible-range<value_type> R>
71 constexpr flat_set(from_range_t, R&& rg)
72 : flat_set(from_range, std::forward<R>(rg), key_compare()) { }
73 template<container-compatible-range<value_type> R>
74 constexpr flat_set(from_range_t, R&& rg, const key_compare& comp)
75 : flat_set(comp)
76 { insert_range(std::forward<R>(rg)); }
77
78 constexpr flat_set(initializer_list<value_type> il, const key_compare& comp = key_compare())
79 : flat_set(il.begin(), il.end(), comp) { }
80
81 constexpr flat_set(sorted_unique_t, initializer_list<value_type> il,
82 const key_compare& comp = key_compare())
83 : flat_set(sorted_unique, il.begin(), il.end(), comp) { }
84
85 // [flat.set.cons.alloc], constructors with allocators
86
87 template<class Alloc>
88 constexpr explicit flat_set(const Alloc& a);
89 template<class Alloc>
90 constexpr flat_set(const key_compare& comp, const Alloc& a);
91 template<class Alloc>
92 constexpr flat_set(const container_type& cont, const Alloc& a);
93 template<class Alloc>
94 constexpr flat_set(const container_type& cont, const key_compare& comp, const Alloc& a);
95 template<class Alloc>
96 constexpr flat_set(sorted_unique_t, const container_type& cont, const Alloc& a);
97 template<class Alloc>
98 constexpr flat_set(sorted_unique_t, const container_type& cont,
99 const key_compare& comp, const Alloc& a);
100 template<class Alloc>
101 constexpr flat_set(const flat_set&, const Alloc& a);
102 template<class Alloc>
103 constexpr flat_set(flat_set&&, const Alloc& a);
104 template<class InputIterator, class Alloc>
105 constexpr flat_set(InputIterator first, InputIterator last, const Alloc& a);
106 template<class InputIterator, class Alloc>
107 constexpr flat_set(InputIterator first, InputIterator last,
108 const key_compare& comp, const Alloc& a);
109 template<class InputIterator, class Alloc>
110 constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last,
111 const Alloc& a);
112 template<class InputIterator, class Alloc>
113 constexpr flat_set(sorted_unique_t, InputIterator first, InputIterator last,
114 const key_compare& comp, const Alloc& a);
115 template<container-compatible-range<value_type> R, class Alloc>
116 constexpr flat_set(from_range_t, R&& rg, const Alloc& a);
117 template<container-compatible-range<value_type> R, class Alloc>
118 constexpr flat_set(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
119 template<class Alloc>
120 constexpr flat_set(initializer_list<value_type> il, const Alloc& a);
121 template<class Alloc>
122 constexpr flat_set(initializer_list<value_type> il, const key_compare& comp,
123 const Alloc& a);
124 template<class Alloc>
125 constexpr flat_set(sorted_unique_t, initializer_list<value_type> il, const Alloc& a);
126 template<class Alloc>
127 constexpr flat_set(sorted_unique_t, initializer_list<value_type> il,
128 const key_compare& comp, const Alloc& a);
129
130 constexpr flat_set& operator=(initializer_list<value_type>);
131
132 // iterators
133 constexpr iterator begin() noexcept;
134 constexpr const_iterator begin() const noexcept;
135 constexpr iterator end() noexcept;
136 constexpr const_iterator end() const noexcept;
137
138 constexpr reverse_iterator rbegin() noexcept;
139 constexpr const_reverse_iterator rbegin() const noexcept;
140 constexpr reverse_iterator rend() noexcept;
141 constexpr const_reverse_iterator rend() const noexcept;
142
143 constexpr const_iterator cbegin() const noexcept;
144 constexpr const_iterator cend() const noexcept;
145 constexpr const_reverse_iterator crbegin() const noexcept;
146 constexpr const_reverse_iterator crend() const noexcept;
147
148 // capacity
149 constexpr bool empty() const noexcept;
150 constexpr size_type size() const noexcept;
151 constexpr size_type max_size() const noexcept;
152
153 // [flat.set.modifiers], modifiers
154 template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
155 template<class... Args>
156 constexpr iterator emplace_hint(const_iterator position, Args&&... args);
157
158 constexpr pair<iterator, bool> insert(const value_type& x)
159 { return emplace(x); }
160 constexpr pair<iterator, bool> insert(value_type&& x)
161 { return emplace(std::move(x)); }
162 template<class K> constexpr pair<iterator, bool> insert(K&& x);
163 constexpr iterator insert(const_iterator position, const value_type& x)
164 { return emplace_hint(position, x); }
165 constexpr iterator insert(const_iterator position, value_type&& x)
166 { return emplace_hint(position, std::move(x)); }
167 template<class K> constexpr iterator insert(const_iterator hint, K&& x);
168
169 template<class InputIterator>
170 constexpr void insert(InputIterator first, InputIterator last);
171 template<class InputIterator>
172 constexpr void insert(sorted_unique_t, InputIterator first, InputIterator last);
173 template<container-compatible-range<value_type> R>
174 constexpr void insert_range(R&& rg);
175 template<container-compatible-range<value_type> R>
176 constexpr void insert_range(sorted_unique_t, R&& rg);
177
178 constexpr void insert(initializer_list<value_type> il)
179 { insert(il.begin(), il.end()); }
180 constexpr void insert(sorted_unique_t, initializer_list<value_type> il)
181 { insert(sorted_unique, il.begin(), il.end()); }
182
183 constexpr container_type extract() &&;
184 constexpr void replace(container_type&&);
185
186 constexpr iterator erase(iterator position) requires (!same_as<iterator, const_iterator>);
187 constexpr iterator erase(const_iterator position);
188 constexpr size_type erase(const key_type& x);
189 template<class K> constexpr size_type erase(K&& x);
190 constexpr iterator erase(const_iterator first, const_iterator last);
191
192 constexpr void swap(flat_set& y) noexcept(see below);
193 constexpr void clear() noexcept;
194
195 // observers
196 constexpr key_compare key_comp() const;
197 constexpr value_compare value_comp() const;
198
199 // set operations
200 constexpr iterator find(const key_type& x);
201 constexpr const_iterator find(const key_type& x) const;
202 template<class K> constexpr iterator find(const K& x);
203 template<class K> constexpr const_iterator find(const K& x) const;
204
205 constexpr size_type count(const key_type& x) const;
206 template<class K> constexpr size_type count(const K& x) const;
207
208 constexpr bool contains(const key_type& x) const;
209 template<class K> constexpr bool contains(const K& x) const;
210
211 constexpr iterator lower_bound(const key_type& x);
212 constexpr const_iterator lower_bound(const key_type& x) const;
213 template<class K> constexpr iterator lower_bound(const K& x);
214 template<class K> constexpr const_iterator lower_bound(const K& x) const;
215
216 constexpr iterator upper_bound(const key_type& x);
217 constexpr const_iterator upper_bound(const key_type& x) const;
218 template<class K> constexpr iterator upper_bound(const K& x);
219 template<class K> constexpr const_iterator upper_bound(const K& x) const;
220
221 constexpr pair<iterator, iterator> equal_range(const key_type& x);
222 constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
223 template<class K>
224 constexpr pair<iterator, iterator> equal_range(const K& x);
225 template<class K>
226 constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
227
228 friend constexpr bool operator==(const flat_set& x, const flat_set& y);
229
230 friend constexpr synth-three-way-result<value_type>
231 operator<=>(const flat_set& x, const flat_set& y);
232
233 friend constexpr void swap(flat_set& x, flat_set& y) noexcept(noexcept(x.swap(y)))
234 { x.swap(y); }
235
236 private:
237 container_type c; // exposition only
238 key_compare compare; // exposition only
239 };
240
241 template<class KeyContainer, class Compare = less<typename KeyContainer::value_type>>
242 flat_set(KeyContainer, Compare = Compare())
243 -> flat_set<typename KeyContainer::value_type, Compare, KeyContainer>;
244 template<class KeyContainer, class Allocator>
245 flat_set(KeyContainer, Allocator)
246 -> flat_set<typename KeyContainer::value_type,
247 less<typename KeyContainer::value_type>, KeyContainer>;
248 template<class KeyContainer, class Compare, class Allocator>
249 flat_set(KeyContainer, Compare, Allocator)
250 -> flat_set<typename KeyContainer::value_type, Compare, KeyContainer>;
251
252 template<class KeyContainer, class Compare = less<typename KeyContainer::value_type>>
253 flat_set(sorted_unique_t, KeyContainer, Compare = Compare())
254 -> flat_set<typename KeyContainer::value_type, Compare, KeyContainer>;
255 template<class KeyContainer, class Allocator>
256 flat_set(sorted_unique_t, KeyContainer, Allocator)
257 -> flat_set<typename KeyContainer::value_type,
258 less<typename KeyContainer::value_type>, KeyContainer>;
259 template<class KeyContainer, class Compare, class Allocator>
260 flat_set(sorted_unique_t, KeyContainer, Compare, Allocator)
261 -> flat_set<typename KeyContainer::value_type, Compare, KeyContainer>;
262
263 template<class InputIterator, class Compare = less<iter-value-type<InputIterator>>>
264 flat_set(InputIterator, InputIterator, Compare = Compare())
265 -> flat_set<iter-value-type<InputIterator>, Compare>;
266
267 template<class InputIterator, class Compare = less<iter-value-type<InputIterator>>>
268 flat_set(sorted_unique_t, InputIterator, InputIterator, Compare = Compare())
269 -> flat_set<iter-value-type<InputIterator>, Compare>;
270
271 template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
272 class Allocator = allocator<ranges::range_value_t<R>>>
273 flat_set(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
274 -> flat_set<ranges::range_value_t<R>, Compare,
275 vector<ranges::range_value_t<R>,
276 alloc-rebind<Allocator, ranges::range_value_t<R>>>>;
277
278 template<ranges::input_range R, class Allocator>
279 flat_set(from_range_t, R&&, Allocator)
280 -> flat_set<ranges::range_value_t<R>, less<ranges::range_value_t<R>>,
281 vector<ranges::range_value_t<R>,
282 alloc-rebind<Allocator, ranges::range_value_t<R>>>>;
283
284 template<class Key, class Compare = less<Key>>
285 flat_set(initializer_list<Key>, Compare = Compare())
286 -> flat_set<Key, Compare>;
287
288 template<class Key, class Compare = less<Key>>
289 flat_set(sorted_unique_t, initializer_list<Key>, Compare = Compare())
290 -> flat_set<Key, Compare>;
291
292 template<class Key, class Compare, class KeyContainer, class Allocator>
293 struct uses_allocator<flat_set<Key, Compare, KeyContainer>, Allocator>
294 : bool_constant<uses_allocator_v<KeyContainer, Allocator>> { };
295
296 // [flat.set.erasure], erasure for flat_set
297 template<class Key, class Compare, class KeyContainer, class Predicate>
298 typename flat_set<Key, Compare, KeyContainer>::size_type
299 erase_if(flat_set<Key, Compare, KeyContainer>& c, Predicate pred);
300
301 struct sorted_equivalent_t { explicit sorted_equivalent_t() = default; };
302 inline constexpr sorted_equivalent_t sorted_equivalent{};
303
304 // [flat.multiset], class template flat_multiset
305 template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>
306 class flat_multiset {
307 public:
308 // types
309 using key_type = Key;
310 using value_type = Key;
311 using key_compare = Compare;
312 using value_compare = Compare;
313 using reference = value_type&;
314 using const_reference = const value_type&;
315 using size_type = KeyContainer::size_type;
316 using difference_type = KeyContainer::difference_type;
317 using iterator = implementation-defined; // see [container.requirements]
318 using const_iterator = implementation-defined; // see [container.requirements]
319 using reverse_iterator = std::reverse_iterator<iterator>;
320 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
321 using container_type = KeyContainer;
322
323 // [flat.multiset.cons], constructors
324 constexpr flat_multiset() : flat_multiset(key_compare()) { }
325
326 constexpr flat_multiset(const flat_multiset&);
327 constexpr flat_multiset(flat_multiset&&);
328 constexpr flat_multiset& operator=(const flat_multiset&);
329 constexpr flat_multiset& operator=(flat_multiset&&);
330
331 constexpr explicit flat_multiset(const key_compare& comp)
332 : c(), compare(comp) { }
333
334 constexpr explicit flat_multiset(container_type cont,
335 const key_compare& comp = key_compare());
336
337 constexpr flat_multiset(sorted_equivalent_t, container_type cont,
338 const key_compare& comp = key_compare())
339 : c(std::move(cont)), compare(comp) { }
340
341 template<class InputIterator>
342 constexpr flat_multiset(InputIterator first, InputIterator last,
343 const key_compare& comp = key_compare())
344 : c(), compare(comp)
345 { insert(first, last); }
346
347 template<class InputIterator>
348 constexpr flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
349 const key_compare& comp = key_compare())
350 : c(first, last), compare(comp) { }
351
352 template<container-compatible-range<value_type> R>
353 constexpr flat_multiset(from_range_t, R&& rg)
354 : flat_multiset(from_range, std::forward<R>(rg), key_compare()) { }
355 template<container-compatible-range<value_type> R>
356 constexpr flat_multiset(from_range_t, R&& rg, const key_compare& comp)
357 : flat_multiset(comp)
358 { insert_range(std::forward<R>(rg)); }
359
360 constexpr flat_multiset(initializer_list<value_type> il,
361 const key_compare& comp = key_compare())
362 : flat_multiset(il.begin(), il.end(), comp) { }
363
364 constexpr flat_multiset(sorted_equivalent_t, initializer_list<value_type> il,
365 const key_compare& comp = key_compare())
366 : flat_multiset(sorted_equivalent, il.begin(), il.end(), comp) { }
367
368 // [flat.multiset.cons.alloc], constructors with allocators
369
370 template<class Alloc>
371 constexpr explicit flat_multiset(const Alloc& a);
372 template<class Alloc>
373 constexpr flat_multiset(const key_compare& comp, const Alloc& a);
374 template<class Alloc>
375 constexpr flat_multiset(const container_type& cont, const Alloc& a);
376 template<class Alloc>
377 constexpr flat_multiset(const container_type& cont, const key_compare& comp,
378 const Alloc& a);
379 template<class Alloc>
380 constexpr flat_multiset(sorted_equivalent_t, const container_type& cont, const Alloc& a);
381 template<class Alloc>
382 constexpr flat_multiset(sorted_equivalent_t, const container_type& cont,
383 const key_compare& comp, const Alloc& a);
384 template<class Alloc>
385 constexpr flat_multiset(const flat_multiset&, const Alloc& a);
386 template<class Alloc>
387 constexpr flat_multiset(flat_multiset&&, const Alloc& a);
388 template<class InputIterator, class Alloc>
389 constexpr flat_multiset(InputIterator first, InputIterator last, const Alloc& a);
390 template<class InputIterator, class Alloc>
391 constexpr flat_multiset(InputIterator first, InputIterator last,
392 const key_compare& comp, const Alloc& a);
393 template<class InputIterator, class Alloc>
394 constexpr flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
395 const Alloc& a);
396 template<class InputIterator, class Alloc>
397 constexpr flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
398 const key_compare& comp, const Alloc& a);
399 template<container-compatible-range<value_type> R, class Alloc>
400 constexpr flat_multiset(from_range_t, R&& rg, const Alloc& a);
401 template<container-compatible-range<value_type> R, class Alloc>
402 constexpr flat_multiset(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
403 template<class Alloc>
404 constexpr flat_multiset(initializer_list<value_type> il, const Alloc& a);
405 template<class Alloc>
406 constexpr flat_multiset(initializer_list<value_type> il, const key_compare& comp,
407 const Alloc& a);
408 template<class Alloc>
409 constexpr flat_multiset(sorted_equivalent_t, initializer_list<value_type> il,
410 const Alloc& a);
411 template<class Alloc>
412 constexpr flat_multiset(sorted_equivalent_t, initializer_list<value_type> il,
413 const key_compare& comp, const Alloc& a);
414
415 constexpr flat_multiset& operator=(initializer_list<value_type>);
416
417 // iterators
418 constexpr iterator begin() noexcept;
419 constexpr const_iterator begin() const noexcept;
420 constexpr iterator end() noexcept;
421 constexpr const_iterator end() const noexcept;
422
423 constexpr reverse_iterator rbegin() noexcept;
424 constexpr const_reverse_iterator rbegin() const noexcept;
425 constexpr reverse_iterator rend() noexcept;
426 constexpr const_reverse_iterator rend() const noexcept;
427
428 constexpr const_iterator cbegin() const noexcept;
429 constexpr const_iterator cend() const noexcept;
430 constexpr const_reverse_iterator crbegin() const noexcept;
431 constexpr const_reverse_iterator crend() const noexcept;
432
433 // capacity
434 constexpr bool empty() const noexcept;
435 constexpr size_type size() const noexcept;
436 constexpr size_type max_size() const noexcept;
437
438 // [flat.multiset.modifiers], modifiers
439 template<class... Args> constexpr iterator emplace(Args&&... args);
440 template<class... Args>
441 constexpr iterator emplace_hint(const_iterator position, Args&&... args);
442
443 constexpr iterator insert(const value_type& x)
444 { return emplace(x); }
445 constexpr iterator insert(value_type&& x)
446 { return emplace(std::move(x)); }
447 constexpr iterator insert(const_iterator position, const value_type& x)
448 { return emplace_hint(position, x); }
449 constexpr iterator insert(const_iterator position, value_type&& x)
450 { return emplace_hint(position, std::move(x)); }
451
452 template<class InputIterator>
453 constexpr void insert(InputIterator first, InputIterator last);
454 template<class InputIterator>
455 constexpr void insert(sorted_equivalent_t, InputIterator first, InputIterator last);
456 template<container-compatible-range<value_type> R>
457 constexpr void insert_range(R&& rg);
458 template<container-compatible-range<value_type> R>
459 constexpr void insert_range(sorted_equivalent_t, R&& rg);
460
461 constexpr void insert(initializer_list<value_type> il)
462 { insert(il.begin(), il.end()); }
463 constexpr void insert(sorted_equivalent_t, initializer_list<value_type> il)
464 { insert(sorted_equivalent, il.begin(), il.end()); }
465
466 constexpr container_type extract() &&;
467 constexpr void replace(container_type&&);
468
469 constexpr iterator erase(iterator position) requires (!same_as<iterator, const_iterator>);
470 constexpr iterator erase(const_iterator position);
471 constexpr size_type erase(const key_type& x);
472 template<class K> constexpr size_type erase(K&& x);
473 constexpr iterator erase(const_iterator first, const_iterator last);
474
475 constexpr void swap(flat_multiset& y) noexcept(see below);
476 constexpr void clear() noexcept;
477
478 // observers
479 constexpr key_compare key_comp() const;
480 constexpr value_compare value_comp() const;
481
482 // set operations
483 constexpr iterator find(const key_type& x);
484 constexpr const_iterator find(const key_type& x) const;
485 template<class K> constexpr iterator find(const K& x);
486 template<class K> constexpr const_iterator find(const K& x) const;
487
488 constexpr size_type count(const key_type& x) const;
489 template<class K> constexpr size_type count(const K& x) const;
490
491 constexpr bool contains(const key_type& x) const;
492 template<class K> constexpr bool contains(const K& x) const;
493
494 constexpr iterator lower_bound(const key_type& x);
495 constexpr const_iterator lower_bound(const key_type& x) const;
496 template<class K> constexpr iterator lower_bound(const K& x);
497 template<class K> constexpr const_iterator lower_bound(const K& x) const;
498
499 constexpr iterator upper_bound(const key_type& x);
500 constexpr const_iterator upper_bound(const key_type& x) const;
501 template<class K> constexpr iterator upper_bound(const K& x);
502 template<class K> constexpr const_iterator upper_bound(const K& x) const;
503
504 constexpr pair<iterator, iterator> equal_range(const key_type& x);
505 constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
506 template<class K>
507 constexpr pair<iterator, iterator> equal_range(const K& x);
508 template<class K>
509 constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
510
511 friend constexpr bool operator==(const flat_multiset& x, const flat_multiset& y);
512
513 friend constexpr synth-three-way-result<value_type>
514 operator<=>(const flat_multiset& x, const flat_multiset& y);
515
516 friend constexpr void swap(flat_multiset& x, flat_multiset& y)
517 noexcept(noexcept(x.swap(y)))
518 { x.swap(y); }
519
520 private:
521 container_type c; // exposition only
522 key_compare compare; // exposition only
523 };
524
525 template<class KeyContainer, class Compare = less<typename KeyContainer::value_type>>
526 flat_multiset(KeyContainer, Compare = Compare())
527 -> flat_multiset<typename KeyContainer::value_type, Compare, KeyContainer>;
528 template<class KeyContainer, class Allocator>
529 flat_multiset(KeyContainer, Allocator)
530 -> flat_multiset<typename KeyContainer::value_type,
531 less<typename KeyContainer::value_type>, KeyContainer>;
532 template<class KeyContainer, class Compare, class Allocator>
533 flat_multiset(KeyContainer, Compare, Allocator)
534 -> flat_multiset<typename KeyContainer::value_type, Compare, KeyContainer>;
535
536 template<class KeyContainer, class Compare = less<typename KeyContainer::value_type>>
537 flat_multiset(sorted_equivalent_t, KeyContainer, Compare = Compare())
538 -> flat_multiset<typename KeyContainer::value_type, Compare, KeyContainer>;
539 template<class KeyContainer, class Allocator>
540 flat_multiset(sorted_equivalent_t, KeyContainer, Allocator)
541 -> flat_multiset<typename KeyContainer::value_type,
542 less<typename KeyContainer::value_type>, KeyContainer>;
543 template<class KeyContainer, class Compare, class Allocator>
544 flat_multiset(sorted_equivalent_t, KeyContainer, Compare, Allocator)
545 -> flat_multiset<typename KeyContainer::value_type, Compare, KeyContainer>;
546
547 template<class InputIterator, class Compare = less<iter-value-type<InputIterator>>>
548 flat_multiset(InputIterator, InputIterator, Compare = Compare())
549 -> flat_multiset<iter-value-type<InputIterator>, Compare>;
550
551 template<class InputIterator, class Compare = less<iter-value-type<InputIterator>>>
552 flat_multiset(sorted_equivalent_t, InputIterator, InputIterator, Compare = Compare())
553 -> flat_multiset<iter-value-type<InputIterator>, Compare>;
554
555 template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
556 class Allocator = allocator<ranges::range_value_t<R>>>
557 flat_multiset(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
558 -> flat_multiset<ranges::range_value_t<R>, Compare,
559 vector<ranges::range_value_t<R>,
560 alloc-rebind<Allocator, ranges::range_value_t<R>>>>;
561
562 template<ranges::input_range R, class Allocator>
563 flat_multiset(from_range_t, R&&, Allocator)
564 -> flat_multiset<ranges::range_value_t<R>, less<ranges::range_value_t<R>>,
565 vector<ranges::range_value_t<R>,
566 alloc-rebind<Allocator, ranges::range_value_t<R>>>>;
567
568 template<class Key, class Compare = less<Key>>
569 flat_multiset(initializer_list<Key>, Compare = Compare())
570 -> flat_multiset<Key, Compare>;
571
572 template<class Key, class Compare = less<Key>>
573 flat_multiset(sorted_equivalent_t, initializer_list<Key>, Compare = Compare())
574 -> flat_multiset<Key, Compare>;
575
576 template<class Key, class Compare, class KeyContainer, class Allocator>
577 struct uses_allocator<flat_multiset<Key, Compare, KeyContainer>, Allocator>
578 : bool_constant<uses_allocator_v<KeyContainer, Allocator>> { };
579
580 // [flat.multiset.erasure], erasure for flat_multiset
581 template<class Key, class Compare, class KeyContainer, class Predicate>
582 typename flat_multiset<Key, Compare, KeyContainer>::size_type
583 erase_if(flat_multiset<Key, Compare, KeyContainer>& c, Predicate pred);
584}
585*/
586
587#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
588# include <__cxx03/__config>
589#else
590# include <__config>
591
592# if _LIBCPP_STD_VER >= 23
593# include <__flat_map/sorted_equivalent.h>
594# include <__flat_map/sorted_unique.h>
595# include <__flat_set/flat_multiset.h>
596# include <__flat_set/flat_set.h>
597# endif
598
599// for feature-test macros
600# include <version>
601
602// standard required includes
603
604// [iterator.range]
605# include <__iterator/access.h>
606# include <__iterator/data.h>
607# include <__iterator/empty.h>
608# include <__iterator/reverse_access.h>
609# include <__iterator/size.h>
610
611// [flat.set.syn]
612# include <compare>
613# include <initializer_list>
614
615# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
616# pragma GCC system_header
617# endif
618#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
619
620#endif // _LIBCPP_FLAT_SET