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