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