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