libstdc++
flat_set
Go to the documentation of this file.
1// <flat_set> -*- C++ -*-
2
3// Copyright The GNU Toolchain Authors.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file include/flat_set
26 * This is a Standard C++ Library header.
27 */
28
29#ifndef _GLIBCXX_FLAT_SET
30#define _GLIBCXX_FLAT_SET 1
31
32#ifdef _GLIBCXX_SYSHDR
33#pragma GCC system_header
34#endif
35
36#define __glibcxx_want_flat_set
37#include <bits/version.h>
38
39#ifdef __cpp_lib_flat_set // >= C++23
40
41#include <compare>
42#include <initializer_list>
43
44#include <exception>
45#include <functional> // not_fn
46#include <optional>
47#include <type_traits>
48#include <vector>
49#include <bits/functexcept.h>
50#include <bits/stl_algo.h>
51#include <bits/stl_function.h> // less
52#include <bits/stl_pair.h>
53#include <bits/uses_allocator_args.h> // make_obj_using_allocator
54#ifdef _GLIBCXX_DEBUG
55# include <bits/ranges_algo.h> // ranges::is_sorted
56#endif
57
58namespace std _GLIBCXX_VISIBILITY(default)
59{
60_GLIBCXX_BEGIN_NAMESPACE_VERSION
61
62 template<typename _Key, typename _Compare,
63 typename _KeyContainer>
64 class flat_set;
65
66 template<typename _Key, typename _Compare,
67 typename _KeyContainer>
68 class flat_multiset;
69
70 template<typename _Key, typename _Compare, typename _KeyContainer, bool _Multi>
71 class _Flat_set_impl
72 {
73 static_assert(is_same_v<_Key, typename _KeyContainer::value_type>);
74 static_assert(is_nothrow_swappable_v<_KeyContainer>);
75
76 using _Derived = __conditional_t<_Multi,
77 flat_multiset<_Key, _Compare, _KeyContainer>,
78 flat_set<_Key, _Compare, _KeyContainer>>;
79 using __sorted_t = __conditional_t<_Multi, sorted_equivalent_t, sorted_unique_t>;
80
81 public:
82 using key_type = _Key;
83 using value_type = _Key;
84 using key_compare = _Compare;
85 using value_compare = _Compare;
86 using reference = value_type&;
87 using const_reference = const value_type&;
88 using size_type = typename _KeyContainer::size_type;
89 using difference_type = typename _KeyContainer::difference_type;
90 using iterator = typename _KeyContainer::const_iterator;
91 using const_iterator = typename _KeyContainer::const_iterator;
92 using reverse_iterator = std::reverse_iterator<iterator>;
93 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
94 using container_type = _KeyContainer;
95
96 private:
97 using __emplace_result_t = __conditional_t<_Multi, iterator, pair<iterator, bool>>;
98
99 struct _ClearGuard
100 {
101 container_type* _M_cont;
102
103 _ClearGuard(container_type& __cont)
104 : _M_cont(std::__addressof(__cont))
105 { }
106
107 ~_ClearGuard()
108 {
109 if (_M_cont)
110 _M_cont->clear();
111 }
112
113 void
114 _M_disable()
115 { _M_cont = nullptr; }
116 };
117
118 _ClearGuard
119 _M_make_clear_guard()
120 { return _ClearGuard{this->_M_cont}; }
121
122 public:
123 // constructors
124 _Flat_set_impl() : _Flat_set_impl(key_compare()) { }
125
126 explicit
127 _Flat_set_impl(const key_compare& __comp)
128 : _M_cont(), _M_comp(__comp)
129 { }
130
131 _Flat_set_impl(container_type __cont, const key_compare& __comp = key_compare())
132 : _M_cont(std::move(__cont)), _M_comp(__comp)
133 { _M_sort_uniq(); }
134
135 _Flat_set_impl(__sorted_t,
136 container_type __cont, const key_compare& __comp = key_compare())
137 : _M_cont(std::move(__cont)), _M_comp(__comp)
138 { _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont, _M_comp)); }
139
140 template<__has_input_iter_cat _InputIterator>
141 _Flat_set_impl(_InputIterator __first, _InputIterator __last,
142 const key_compare& __comp = key_compare())
143 : _M_cont(), _M_comp(__comp)
144 { insert(__first, __last); }
145
146 template<__has_input_iter_cat _InputIterator>
147 _Flat_set_impl(__sorted_t __s,
148 _InputIterator __first, _InputIterator __last,
149 const key_compare& __comp = key_compare())
150 : _M_cont(), _M_comp(__comp)
151 { insert(__s, __first, __last); }
152
153 template<__detail::__container_compatible_range<value_type> _Rg>
154 _Flat_set_impl(from_range_t, _Rg&& __rg)
155 : _Flat_set_impl(from_range, std::forward<_Rg>(__rg), key_compare())
156 { }
157
158 template<__detail::__container_compatible_range<value_type> _Rg>
159 _Flat_set_impl(from_range_t, _Rg&& __rg, const key_compare& __comp)
160 : _Flat_set_impl(__comp)
161 { insert_range(std::forward<_Rg>(__rg)); }
162
163 _Flat_set_impl(initializer_list<value_type> __il,
164 const key_compare& __comp = key_compare())
165 : _Flat_set_impl(__il.begin(), __il.end(), __comp)
166 { }
167
168 _Flat_set_impl(__sorted_t __s,
169 initializer_list<value_type> __il,
170 const key_compare& __comp = key_compare())
171 : _Flat_set_impl(__s, __il.begin(), __il.end(), __comp)
172 { }
173
174 // constructors with allocators
175
176 template<__allocator_for<container_type> _Alloc>
177 explicit
178 _Flat_set_impl(const _Alloc& __a)
179 : _Flat_set_impl(key_compare(), __a)
180 { }
181
182 template<__allocator_for<container_type> _Alloc>
183 _Flat_set_impl(const key_compare& __comp, const _Alloc& __a)
184 : _M_cont(std::make_obj_using_allocator<container_type>(__a)),
185 _M_comp(__comp)
186 { }
187
188 template<__allocator_for<container_type> _Alloc>
189 _Flat_set_impl(const container_type& __cont, const _Alloc& __a)
190 : _Flat_set_impl(__cont, key_compare(), __a)
191 { }
192
193 template<__allocator_for<container_type> _Alloc>
194 _Flat_set_impl(const container_type& __cont, const key_compare& __comp,
195 const _Alloc& __a)
196 : _M_cont(std::make_obj_using_allocator<container_type>(__a, __cont)),
197 _M_comp(__comp)
198 { _M_sort_uniq(); }
199
200 template<__allocator_for<container_type> _Alloc>
201 _Flat_set_impl(__sorted_t __s, const container_type& __cont, const _Alloc& __a)
202 : _Flat_set_impl(__s, __cont, key_compare(), __a)
203 { }
204
205 template<__allocator_for<container_type> _Alloc>
206 _Flat_set_impl(__sorted_t, const container_type& __cont, const key_compare& __comp,
207 const _Alloc& __a)
208 : _M_cont(std::make_obj_using_allocator<container_type>(__a, __cont)),
209 _M_comp(__comp)
210 { _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont, _M_comp)); }
211
212 template<__allocator_for<container_type> _Alloc>
213 _Flat_set_impl(const _Derived& __x, const _Alloc& __a)
214 : _M_cont(std::make_obj_using_allocator<container_type>(__a, __x._M_cont)),
215 _M_comp(__x._M_comp)
216 { }
217
218 template<__allocator_for<container_type> _Alloc>
219 _Flat_set_impl(_Derived&& __x, const _Alloc& __a)
220 : _M_cont(std::make_obj_using_allocator<container_type>(__a, std::move(__x._M_cont))),
221 _M_comp(__x._M_comp)
222 { }
223
224 template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc>
225 _Flat_set_impl(_InputIterator __first, _InputIterator __last,
226 const _Alloc& __a)
227 : _Flat_set_impl(std::move(__first), std::move(__last), key_compare(), __a)
228 { }
229
230 template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc>
231 _Flat_set_impl(_InputIterator __first, _InputIterator __last,
232 const key_compare& __comp,
233 const _Alloc& __a)
234 : _Flat_set_impl(__comp, __a)
235 { insert(__first, __last); }
236
237 template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc>
238 _Flat_set_impl(__sorted_t __s,
239 _InputIterator __first, _InputIterator __last,
240 const _Alloc& __a)
241 : _Flat_set_impl(__s, std::move(__first), std::move(__last), key_compare(), __a)
242 { }
243
244 template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc>
245 _Flat_set_impl(__sorted_t __s,
246 _InputIterator __first, _InputIterator __last,
247 const key_compare& __comp,
248 const _Alloc& __a)
249 : _Flat_set_impl(__comp, __a)
250 { insert(__s, __first, __last); }
251
252 template<__detail::__container_compatible_range<value_type> _Rg,
253 __allocator_for<container_type> _Alloc>
254 _Flat_set_impl(from_range_t, _Rg&& __rg,
255 const _Alloc& __a)
256 : _Flat_set_impl(from_range, std::forward<_Rg>(__rg), key_compare(), __a)
257 { }
258
259 template<__detail::__container_compatible_range<value_type> _Rg,
260 __allocator_for<container_type> _Alloc>
261 _Flat_set_impl(from_range_t, _Rg&& __rg,
262 const key_compare& __comp,
263 const _Alloc& __a)
264 : _Flat_set_impl(__comp, __a)
265 { insert_range(std::forward<_Rg>(__rg)); }
266
267 template<__allocator_for<container_type> _Alloc>
268 _Flat_set_impl(initializer_list<value_type> __il,
269 const _Alloc& __a)
270 : _Flat_set_impl(__il, key_compare(), __a)
271 { }
272
273 template<__allocator_for<container_type> _Alloc>
274 _Flat_set_impl(initializer_list<value_type> __il,
275 const key_compare& __comp,
276 const _Alloc& __a)
277 : _Flat_set_impl(__il.begin(), __il.end(), __comp, __a)
278 { }
279
280 template<__allocator_for<container_type> _Alloc>
281 _Flat_set_impl(__sorted_t __s,
282 initializer_list<value_type> __il,
283 const _Alloc& __a)
284 : _Flat_set_impl(__s, __il.begin(), __il.end(), key_compare(), __a)
285 { }
286
287 template<__allocator_for<container_type> _Alloc>
288 _Flat_set_impl(__sorted_t __s,
289 initializer_list<value_type> __il,
290 const key_compare& __comp,
291 const _Alloc& __a)
292 : _Flat_set_impl(__s, __il.begin(), __il.end(), __comp, __a)
293 { }
294
295 _Derived&
296 operator=(initializer_list<value_type> __il)
297 {
298 auto __guard = _M_make_clear_guard();
299 _M_cont = __il;
300 _M_sort_uniq();
301 __guard._M_disable();
302 return static_cast<_Derived&>(*this);
303 }
304
305 // iterators
306 const_iterator
307 begin() const noexcept
308 { return _M_cont.begin(); }
309
310 const_iterator
311 end() const noexcept
312 { return _M_cont.end(); }
313
314 const_reverse_iterator
315 rbegin() const noexcept
316 { return const_reverse_iterator(end()); }
317
318 const_reverse_iterator
319 rend() const noexcept
320 { return const_reverse_iterator(begin()); }
321
322 const_iterator
323 cbegin() const noexcept
324 { return begin(); }
325
326 const_iterator
327 cend() const noexcept
328 { return end(); }
329
330 const_reverse_iterator
331 crbegin() const noexcept
332 { return rbegin(); }
333
334 const_reverse_iterator
335 crend() const noexcept
336 { return rend(); }
337
338 // capacity
339 [[nodiscard]]
340 bool
341 empty() const noexcept
342 { return _M_cont.empty(); }
343
344 size_type
345 size() const noexcept
346 { return _M_cont.size(); }
347
348 size_type
349 max_size() const noexcept
350 { return _M_cont.max_size(); }
351
352 // modifiers
353 template<typename _Arg, typename... _Args>
354 pair<iterator, bool>
355 _M_try_emplace(optional<const_iterator> __hint, _Arg&& __arg, _Args&&... __args)
356 {
357 // TODO: Simplify and audit the hint handling.
358 auto&& __k = [&] -> decltype(auto) {
359 if constexpr (sizeof...(_Args) == 0
360 && same_as<remove_cvref_t<_Arg>, value_type>)
361 return std::forward<_Arg>(__arg);
362 else
363 return value_type(std::forward<_Arg>(__arg),
364 std::forward<_Args>(__args)...);
365 }();
366 typename container_type::iterator __it;
367 int __r = -1, __s = -1;
368 if (__hint.has_value()
369 && (__hint == cbegin()
370 || (__r = !_M_comp(__k, (*__hint)[-1]))) // k >= hint[-1]
371 && (__hint == cend()
372 || (__s = !_M_comp((*__hint)[0], __k)))) // k <= hint[0]
373 {
374 __it = _M_cont.begin() + (*__hint - begin());
375 if constexpr (!_Multi)
376 if (__r == 1 && !_M_comp(__it[-1], __k)) // k == hint[-1]
377 return {__it - 1, false};
378 }
379 else
380 {
381 auto __first = _M_cont.begin();
382 auto __last = _M_cont.end();
383 if (__r == 1) // k >= hint[-1]
384 __first += *__hint - _M_cont.begin();
385 else if (__r == 0) // k < __hint[-1]
386 __last = __first + (*__hint - _M_cont.begin());
387 if constexpr (_Multi)
388 {
389 if (__s == 0) // hint[0] < k
390 // Insert before the leftmost equivalent key.
391 __it = std::lower_bound(__first, __last, __k, _M_comp);
392 else
393 // Insert after the rightmost equivalent key.
394 __it = std::upper_bound(std::make_reverse_iterator(__last),
395 std::make_reverse_iterator(__first),
396 __k, std::not_fn(_M_comp)).base();
397 }
398 else
399 __it = std::lower_bound(__first, __last, __k, _M_comp);
400 }
401
402 if constexpr (!_Multi)
403 if (__it != _M_cont.end() && !_M_comp(__k, __it[0]))
404 return {__it, false};
405
406 auto __guard = _M_make_clear_guard();
407 __it = _M_cont.insert(__it, std::forward<decltype(__k)>(__k));
408 __guard._M_disable();
409 return {__it, true};
410 }
411
412 template<typename... _Args>
413 pair<iterator, bool>
414 _M_try_emplace(optional<const_iterator> __hint)
415 { return _M_try_emplace(__hint, value_type()); }
416
417 template<typename... _Args>
418 requires is_constructible_v<value_type, _Args...>
419 __emplace_result_t
420 emplace(_Args&&... __args)
421 {
422 auto __r = _M_try_emplace(nullopt, std::forward<_Args>(__args)...);
423 if constexpr (_Multi)
424 return __r.first;
425 else
426 return __r;
427 }
428
429 template<typename... _Args>
430 iterator
431 emplace_hint(const_iterator __position, _Args&&... __args)
432 { return _M_try_emplace(__position, std::forward<_Args>(__args)...).first; }
433
434 __emplace_result_t
435 insert(const value_type& __x)
436 { return emplace(__x); }
437
438 __emplace_result_t
439 insert(value_type&& __x)
440 { return emplace(std::move(__x)); }
441
442 iterator
443 insert(const_iterator __position, const value_type& __x)
444 { return emplace_hint(__position, __x); }
445
446 iterator
447 insert(const_iterator __position, value_type&& __x)
448 { return emplace_hint(__position, std::move(__x)); }
449
450 template<typename _Arg>
451 requires is_constructible_v<value_type, _Arg>
452 __emplace_result_t
453 insert(_Arg&& __x)
454 { return emplace(std::forward<_Arg>(__x)); }
455
456 template<typename _Arg>
457 requires is_constructible_v<value_type, _Arg>
458 iterator
459 insert(const_iterator __position, _Arg&& __x)
460 { return emplace_hint(__position, std::forward<_Arg>(__x)); }
461
462 template<__has_input_iter_cat _InputIterator>
463 void
464 insert(_InputIterator __first, _InputIterator __last)
465 {
466 auto __guard = _M_make_clear_guard();
467 auto __it = _M_cont.insert(_M_cont.end(), __first, __last);
468 std::sort(__it, _M_cont.end(), _M_comp);
469 std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp);
470 if constexpr (!_Multi)
471 _M_unique();
472 __guard._M_disable();
473 }
474
475 template<__has_input_iter_cat _InputIterator>
476 void
477 insert(__sorted_t, _InputIterator __first, _InputIterator __last)
478 {
479 auto __guard = _M_make_clear_guard();
480 auto __it = _M_cont.insert(_M_cont.end(), __first, __last);
481 std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp);
482 if constexpr (!_Multi)
483 _M_unique();
484 __guard._M_disable();
485 }
486
487 template<__detail::__container_compatible_range<value_type> _Rg>
488 void
489 insert_range(_Rg&& __rg)
490 {
491 auto __guard = _M_make_clear_guard();
492 typename container_type::iterator __it;
493 if constexpr (requires { _M_cont.insert_range(_M_cont.end(), __rg); })
494 __it = _M_cont.insert_range(_M_cont.end(), __rg);
495 else if constexpr (ranges::common_range<_Rg>
496 && __has_input_iter_cat<ranges::iterator_t<_Rg>>)
497 __it = _M_cont.insert(_M_cont.end(), ranges::begin(__rg), ranges::end(__rg));
498 else
499 {
500 size_type __n = size();
501 auto __first = ranges::begin(__rg);
502 auto __last = ranges::end(__rg);
503 for (; __first != __last; ++__first)
504 _M_cont.emplace_back(*__first);
505 __it = _M_cont.begin() + __n;
506 }
507 std::sort(__it, _M_cont.end(), _M_comp);
508 std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp);
509 if constexpr (!_Multi)
510 _M_unique();
511 __guard._M_disable();
512 }
513
514 void
515 insert(initializer_list<value_type> __il)
516 { insert(__il.begin(), __il.end()); }
517
518 void
519 insert(__sorted_t __s, initializer_list<value_type> __il)
520 { insert(__s, __il.begin(), __il.end()); }
521
522 container_type
523 extract() &&
524 {
525 auto __guard = _M_make_clear_guard();
526 return std::move(_M_cont);
527 }
528
529 void
530 replace(container_type&& __cont)
531 {
532 _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(__cont, _M_comp));
533 auto __guard = _M_make_clear_guard();
534 _M_cont = std::move(__cont);
535 __guard._M_disable();
536 }
537
538 iterator
539 erase(const_iterator __position)
540 { return _M_cont.erase(__position); }
541
542 size_type
543 erase(const key_type& __x)
544 { return erase<const key_type&>(__x); }
545
546 template<typename _Key2>
547 requires same_as<remove_cvref_t<_Key2>, _Key>
548 || (__transparent_comparator<_Compare>
549 && !is_convertible_v<_Key2, iterator>
550 && !is_convertible_v<_Key2, const_iterator>)
551 size_type
552 erase(_Key2&& __x)
553 {
554 auto [__first, __last] = equal_range(std::forward<_Key2>(__x));
555 auto __n = __last - __first;
556 erase(__first, __last);
557 return __n;
558 }
559
560 iterator
561 erase(const_iterator __first, const_iterator __last)
562 { return _M_cont.erase(__first, __last); }
563
564 void
565 swap(_Derived& __x) noexcept
566 {
567 using std::swap;
568 swap(_M_cont, __x._M_cont);
569 swap(_M_comp, __x._M_comp);
570 }
571
572 void
573 clear() noexcept
574 { _M_cont.clear(); }
575
576 // observers
577 [[nodiscard]]
578 key_compare
579 key_comp() const
580 { return _M_comp; }
581
582 [[nodiscard]]
583 value_compare
584 value_comp() const
585 { return _M_comp; }
586
587 // set operations
588 [[nodiscard]]
589 iterator
590 find(const key_type& __x)
591 { return find<key_type>(__x); }
592
593 [[nodiscard]]
594 const_iterator
595 find(const key_type& __x) const
596 { return find<key_type>(__x); }
597
598 template<typename _Key2>
599 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
600 [[nodiscard]]
601 iterator
602 find(const _Key2& __x)
603 {
604 auto __it = lower_bound(__x);
605 if (__it != end() && !_M_comp(__x, *__it))
606 return __it;
607 else
608 return end();
609 }
610
611 template<typename _Key2>
612 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
613 [[nodiscard]]
614 const_iterator
615 find(const _Key2& __x) const
616 {
617 auto __it = lower_bound(__x);
618 if (__it != cend() && !_M_comp(__x, *__it))
619 return __it;
620 else
621 return cend();
622 }
623
624 [[nodiscard]]
625 size_type
626 count(const key_type& __x) const
627 { return count<key_type>(__x); }
628
629 template<typename _Key2>
630 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
631 [[nodiscard]]
632 size_type
633 count(const _Key2& __x) const
634 {
635 if constexpr (!_Multi)
636 return contains<_Key2>(__x);
637 else
638 {
639 auto [__first, __last] = equal_range(__x);
640 return __last - __first;
641 }
642 }
643
644 [[nodiscard]]
645 bool
646 contains(const key_type& __x) const
647 { return contains<key_type>(__x); }
648
649 template<typename _Key2>
650 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
651 [[nodiscard]]
652 bool
653 contains(const _Key2& __x) const
654 { return find(__x) != cend(); }
655
656 [[nodiscard]]
657 iterator
658 lower_bound(const key_type& __x)
659 { return lower_bound<key_type>(__x); }
660
661 [[nodiscard]]
662 const_iterator
663 lower_bound(const key_type& __x) const
664 { return lower_bound<key_type>(__x); }
665
666 template<typename _Key2>
667 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
668 [[nodiscard]]
669 iterator
670 lower_bound(const _Key2& __x)
671 { return std::lower_bound(begin(), end(), __x, _M_comp); }
672
673 template<typename _Key2>
674 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
675 [[nodiscard]]
676 const_iterator
677 lower_bound(const _Key2& __x) const
678 { return std::lower_bound(begin(), end(), __x, _M_comp); }
679
680 [[nodiscard]]
681 iterator
682 upper_bound(const key_type& __x)
683 { return upper_bound<key_type>(__x); }
684
685 [[nodiscard]]
686 const_iterator
687 upper_bound(const key_type& __x) const
688 { return upper_bound<key_type>(__x); }
689
690 template<typename _Key2>
691 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
692 [[nodiscard]]
693 iterator
694 upper_bound(const _Key2& __x)
695 { return std::upper_bound(begin(), end(), __x, _M_comp); }
696
697 template<typename _Key2>
698 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
699 [[nodiscard]]
700 const_iterator
701 upper_bound(const _Key2& __x) const
702 { return std::upper_bound(begin(), end(), __x, _M_comp); }
703
704 [[nodiscard]]
705 pair<iterator, iterator>
706 equal_range(const key_type& __x)
707 { return equal_range<key_type>(__x); }
708
709 [[nodiscard]]
710 pair<const_iterator, const_iterator>
711 equal_range(const key_type& __x) const
712 { return equal_range<key_type>(__x); }
713
714 template<typename _Key2>
715 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
716 [[nodiscard]]
717 pair<iterator, iterator>
718 equal_range(const _Key2& __x)
719 { return std::equal_range(begin(), end(), __x, _M_comp); }
720
721 template<typename _Key2>
722 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
723 [[nodiscard]]
724 pair<const_iterator, const_iterator>
725 equal_range(const _Key2& __x) const
726 { return std::equal_range(begin(), end(), __x, _M_comp); }
727
728 [[nodiscard]]
729 friend bool
730 operator==(const _Derived& __x, const _Derived& __y)
731 { return std::equal(__x.begin(), __x.end(), __y.begin(), __y.end()); }
732
733 template<typename _Up = value_type>
734 [[nodiscard]]
735 friend __detail::__synth3way_t<_Up>
736 operator<=>(const _Derived& __x, const _Derived& __y)
737 {
738 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
739 __y.begin(), __y.end(),
740 __detail::__synth3way);
741 }
742
743 friend void
744 swap(_Derived& __x, _Derived& __y) noexcept
745 { return __x.swap(__y); }
746
747 template<typename _Predicate>
748 size_type
749 _M_erase_if(_Predicate __pred)
750 {
751 auto __guard = _M_make_clear_guard();
752 auto __first = _M_cont.begin();
753 auto __last = _M_cont.end();
754 __first = std::remove_if(__first, __last, __pred);
755 auto __n = __last - __first;
756 erase(__first, __last);
757 __guard._M_disable();
758 return __n;
759 }
760
761 private:
762 container_type _M_cont;
763 [[no_unique_address]] _Compare _M_comp;
764
765 void
766 _M_sort_uniq()
767 {
768 std::sort(_M_cont.begin(), _M_cont.end(), _M_comp);
769 if constexpr (!_Multi)
770 _M_unique();
771 }
772
773 void
774 _M_unique() requires (!_Multi)
775 {
776 struct __key_equiv
777 {
778 __key_equiv(key_compare __c) : _M_comp(__c) { }
779
780 bool
781 operator()(const_reference __x, const_reference __y) const
782 { return !_M_comp(__x, __y) && !_M_comp(__y, __x); }
783
784 [[no_unique_address]] key_compare _M_comp;
785 };
786
787 auto __first = _M_cont.begin();
788 auto __last = _M_cont.end();
789 __first = std::unique(__first, __last, __key_equiv(_M_comp));
790 _M_cont.erase(__first, __last);
791 }
792 };
793
794 /* Class template flat_set - container adaptor
795 *
796 * @ingroup
797 */
798 template<typename _Key, typename _Compare = less<_Key>,
799 typename _KeyContainer = vector<_Key>>
800 class flat_set
801 : private _Flat_set_impl<_Key, _Compare, _KeyContainer, false>
802 {
803 using _Impl = _Flat_set_impl<_Key, _Compare, _KeyContainer, false>;
804 friend _Impl;
805
806 public:
807 // types
808 using typename _Impl::key_type;
809 using typename _Impl::value_type;
810 using typename _Impl::key_compare;
811 using typename _Impl::reference;
812 using typename _Impl::const_reference;
813 using typename _Impl::size_type;
814 using typename _Impl::difference_type;
815 using typename _Impl::iterator;
816 using typename _Impl::const_iterator;
817 using typename _Impl::reverse_iterator;
818 using typename _Impl::const_reverse_iterator;
819 using typename _Impl::container_type;
820 using typename _Impl::value_compare;
821
822 // constructors
823 using _Impl::_Impl;
824
825 // iterators
826 using _Impl::begin;
827 using _Impl::end;
828 using _Impl::rbegin;
829 using _Impl::rend;
830
831 using _Impl::cbegin;
832 using _Impl::cend;
833 using _Impl::crbegin;
834 using _Impl::crend;
835
836 // capacity
837 using _Impl::empty;
838 using _Impl::size;
839 using _Impl::max_size;
840
841 // modifiers
842 using _Impl::emplace;
843 using _Impl::emplace_hint;
844 using _Impl::insert;
845 using _Impl::insert_range;
846 using _Impl::extract;
847 using _Impl::replace;
848 using _Impl::erase;
849 using _Impl::swap;
850 using _Impl::clear;
851
852 // observers
853 using _Impl::key_comp;
854 using _Impl::value_comp;
855
856 // set operations
857 using _Impl::find;
858 using _Impl::count;
859 using _Impl::contains;
860 using _Impl::lower_bound;
861 using _Impl::upper_bound;
862 using _Impl::equal_range;
863
864 using _Impl::_M_erase_if;
865 };
866
867 template<typename _KeyContainer,
868 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
869 flat_set(_KeyContainer, _Compare = _Compare())
870 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
871
872 template<typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc>
873 flat_set(_KeyContainer, _Alloc)
874 -> flat_set<typename _KeyContainer::value_type,
875 less<typename _KeyContainer::value_type>, _KeyContainer>;
876
877 template<typename _KeyContainer, __not_allocator_like _Compare,
878 __allocator_for<_KeyContainer> _Alloc>
879 flat_set(_KeyContainer, _Compare, _Alloc)
880 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
881
882 template<typename _KeyContainer,
883 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
884 flat_set(sorted_unique_t, _KeyContainer, _Compare = _Compare())
885 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
886
887 template<typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc>
888 flat_set(sorted_unique_t, _KeyContainer, _Alloc)
889 -> flat_set<typename _KeyContainer::value_type,
890 less<typename _KeyContainer::value_type>, _KeyContainer>;
891
892 template<typename _KeyContainer, __not_allocator_like _Compare,
893 __allocator_for<_KeyContainer> _Alloc>
894 flat_set(sorted_unique_t, _KeyContainer, _Compare, _Alloc)
895 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
896
897 template<__has_input_iter_cat _InputIterator,
898 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
899 flat_set(_InputIterator, _InputIterator, _Compare = _Compare())
900 -> flat_set<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
901
902 template<__has_input_iter_cat _InputIterator,
903 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
904 flat_set(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())
905 -> flat_set<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
906
907 template<ranges::input_range _Rg,
908 __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>,
909 __allocator_like _Alloc = allocator<ranges::range_value_t<_Rg>>>
910 flat_set(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
911 -> flat_set<ranges::range_value_t<_Rg>, _Compare,
912 vector<ranges::range_value_t<_Rg>,
913 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>;
914
915 template<ranges::input_range _Rg, __allocator_like _Alloc>
916 flat_set(from_range_t, _Rg&&, _Alloc)
917 -> flat_set<ranges::range_value_t<_Rg>, less<ranges::range_value_t<_Rg>>,
918 vector<ranges::range_value_t<_Rg>,
919 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>;
920
921 template<typename _Key, __not_allocator_like _Compare = less<_Key>>
922 flat_set(initializer_list<_Key>, _Compare = _Compare())
923 -> flat_set<_Key, _Compare>;
924
925 template<typename _Key, __not_allocator_like _Compare = less<_Key>>
926 flat_set(sorted_unique_t, initializer_list<_Key>, _Compare = _Compare())
927 -> flat_set<_Key, _Compare>;
928
929 template<typename _Key, typename _Compare,
930 typename _KeyContainer, typename _Alloc>
931 struct uses_allocator<flat_set<_Key, _Compare, _KeyContainer>, _Alloc>
932 : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>>
933 { };
934
935 template<typename _Key, typename _Compare, typename _KeyContainer,
936 typename _Predicate>
937 typename flat_set<_Key, _Compare, _KeyContainer>::size_type
938 erase_if(flat_set<_Key, _Compare, _KeyContainer>& __c, _Predicate __pred)
939 { return __c._M_erase_if(std::move(__pred)); }
940
941 /* Class template flat_multiset - container adaptor
942 *
943 * @ingroup
944 */
945 template<typename _Key, typename _Compare = less<_Key>,
946 typename _KeyContainer = vector<_Key>>
947 class flat_multiset
948 : private _Flat_set_impl<_Key, _Compare, _KeyContainer, true>
949 {
950 using _Impl = _Flat_set_impl<_Key, _Compare, _KeyContainer, true>;
951 friend _Impl;
952
953 public:
954 // types
955 using typename _Impl::key_type;
956 using typename _Impl::value_type;
957 using typename _Impl::key_compare;
958 using typename _Impl::reference;
959 using typename _Impl::const_reference;
960 using typename _Impl::size_type;
961 using typename _Impl::difference_type;
962 using typename _Impl::iterator;
963 using typename _Impl::const_iterator;
964 using typename _Impl::reverse_iterator;
965 using typename _Impl::const_reverse_iterator;
966 using typename _Impl::container_type;
967 using typename _Impl::value_compare;
968
969 // constructors
970 using _Impl::_Impl;
971
972 // iterators
973 using _Impl::begin;
974 using _Impl::end;
975 using _Impl::rbegin;
976 using _Impl::rend;
977
978 using _Impl::cbegin;
979 using _Impl::cend;
980 using _Impl::crbegin;
981 using _Impl::crend;
982
983 // capacity
984 using _Impl::empty;
985 using _Impl::size;
986 using _Impl::max_size;
987
988 // modifiers
989 using _Impl::emplace;
990 using _Impl::emplace_hint;
991 using _Impl::insert;
992 using _Impl::insert_range;
993 using _Impl::extract;
994 using _Impl::replace;
995 using _Impl::erase;
996 using _Impl::swap;
997 using _Impl::clear;
998
999 // observers
1000 using _Impl::key_comp;
1001 using _Impl::value_comp;
1002
1003 // set operations
1004 using _Impl::find;
1005 using _Impl::count;
1006 using _Impl::contains;
1007 using _Impl::lower_bound;
1008 using _Impl::upper_bound;
1009 using _Impl::equal_range;
1010
1011 using _Impl::_M_erase_if;
1012 };
1013
1014 template<typename _KeyContainer,
1015 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
1016 flat_multiset(_KeyContainer, _Compare = _Compare())
1017 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1018
1019 template<typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc>
1020 flat_multiset(_KeyContainer, _Alloc)
1021 -> flat_multiset<typename _KeyContainer::value_type,
1022 less<typename _KeyContainer::value_type>, _KeyContainer>;
1023
1024 template<typename _KeyContainer, __not_allocator_like _Compare,
1025 __allocator_for<_KeyContainer> _Alloc>
1026 flat_multiset(_KeyContainer, _Compare, _Alloc)
1027 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1028
1029 template<typename _KeyContainer,
1030 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
1031 flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare = _Compare())
1032 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1033
1034 template<typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc>
1035 flat_multiset(sorted_equivalent_t, _KeyContainer, _Alloc)
1036 -> flat_multiset<typename _KeyContainer::value_type,
1037 less<typename _KeyContainer::value_type>, _KeyContainer>;
1038
1039 template<typename _KeyContainer, __not_allocator_like _Compare,
1040 __allocator_for<_KeyContainer> _Alloc>
1041 flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare, _Alloc)
1042 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1043
1044 template<__has_input_iter_cat _InputIterator,
1045 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
1046 flat_multiset(_InputIterator, _InputIterator, _Compare = _Compare())
1047 -> flat_multiset<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1048
1049 template<__has_input_iter_cat _InputIterator,
1050 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
1051 flat_multiset(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare())
1052 -> flat_multiset<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1053
1054 template<ranges::input_range _Rg,
1055 __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>,
1056 __allocator_like _Alloc = allocator<ranges::range_value_t<_Rg>>>
1057 flat_multiset(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
1058 -> flat_multiset<ranges::range_value_t<_Rg>, _Compare,
1059 vector<ranges::range_value_t<_Rg>,
1060 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>;
1061
1062 template<ranges::input_range _Rg, __allocator_like _Alloc>
1063 flat_multiset(from_range_t, _Rg&&, _Alloc)
1064 -> flat_multiset<ranges::range_value_t<_Rg>, less<ranges::range_value_t<_Rg>>,
1065 vector<ranges::range_value_t<_Rg>,
1066 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>;
1067
1068 template<typename _Key, __not_allocator_like _Compare = less<_Key>>
1069 flat_multiset(initializer_list<_Key>, _Compare = _Compare())
1070 -> flat_multiset<_Key, _Compare>;
1071
1072 template<typename _Key, __not_allocator_like _Compare = less<_Key>>
1073 flat_multiset(sorted_equivalent_t, initializer_list<_Key>, _Compare = _Compare())
1074 -> flat_multiset<_Key, _Compare>;
1075
1076 template<typename _Key, typename _Compare,
1077 typename _KeyContainer, typename _Alloc>
1078 struct uses_allocator<flat_multiset<_Key, _Compare, _KeyContainer>, _Alloc>
1079 : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>>
1080 { };
1081
1082 template<typename _Key, typename _Compare, typename _KeyContainer,
1083 typename _Predicate>
1084 typename flat_multiset<_Key, _Compare, _KeyContainer>::size_type
1085 erase_if(flat_multiset<_Key, _Compare, _KeyContainer>& __c, _Predicate __pred)
1086 { return __c._M_erase_if(std::move(__pred)); }
1087
1088_GLIBCXX_END_NAMESPACE_VERSION
1089} // namespace std
1090#endif // __cpp_lib_flat_set
1091#endif // _GLIBCXX_FLAT_SET