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 _GLIBCXX26_CONSTEXPR
489 pair<iterator, bool>
490 _M_try_emplace(optional<const_iterator> __hint)
491 { return _M_try_emplace(__hint, value_type()); }
492
493 template<typename... _Args>
494 requires is_constructible_v<value_type, _Args...>
495 _GLIBCXX26_CONSTEXPR
496 __emplace_result_t
497 emplace(_Args&&... __args)
498 {
499 auto __r = _M_try_emplace(nullopt, std::forward<_Args>(__args)...);
500 if constexpr (_Multi)
501 return __r.first;
502 else
503 return __r;
504 }
505
506 template<typename... _Args>
507 _GLIBCXX26_CONSTEXPR
508 iterator
509 emplace_hint(const_iterator __position, _Args&&... __args)
510 { return _M_try_emplace(__position, std::forward<_Args>(__args)...).first; }
511
512 _GLIBCXX26_CONSTEXPR
513 __emplace_result_t
514 insert(const value_type& __x)
515 { return emplace(__x); }
516
517 _GLIBCXX26_CONSTEXPR
518 __emplace_result_t
519 insert(value_type&& __x)
520 { return emplace(std::move(__x)); }
521
522 _GLIBCXX26_CONSTEXPR
523 iterator
524 insert(const_iterator __position, const value_type& __x)
525 { return emplace_hint(__position, __x); }
526
527 _GLIBCXX26_CONSTEXPR
528 iterator
529 insert(const_iterator __position, value_type&& __x)
530 { return emplace_hint(__position, std::move(__x)); }
531
532 template<typename _Arg>
533 requires is_constructible_v<value_type, _Arg>
534 _GLIBCXX26_CONSTEXPR
535 __emplace_result_t
536 insert(_Arg&& __x)
537 { return emplace(std::forward<_Arg>(__x)); }
538
539 template<typename _Arg>
540 requires is_constructible_v<value_type, _Arg>
541 _GLIBCXX26_CONSTEXPR
542 iterator
543 insert(const_iterator __position, _Arg&& __x)
544 { return emplace_hint(__position, std::forward<_Arg>(__x)); }
545
546 template<__has_input_iter_cat _InputIterator>
547 _GLIBCXX26_CONSTEXPR
548 void
549 insert(_InputIterator __first, _InputIterator __last)
550 {
551 auto __guard = _M_make_clear_guard();
552 auto __it = _M_cont.insert(_M_cont.end(), __first, __last);
553 std::sort(__it, _M_cont.end(), _M_comp);
554 std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp);
555 if constexpr (!_Multi)
556 _M_unique();
557 __guard._M_disable();
558 }
559
560 template<__has_input_iter_cat _InputIterator>
561 _GLIBCXX26_CONSTEXPR
562 void
563 insert(__sorted_t, _InputIterator __first, _InputIterator __last)
564 {
565 auto __guard = _M_make_clear_guard();
566 auto __it = _M_cont.insert(_M_cont.end(), __first, __last);
567 std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp);
568 if constexpr (!_Multi)
569 _M_unique();
570 __guard._M_disable();
571 }
572
573 template<typename _Rg>
574 _GLIBCXX26_CONSTEXPR
575 void
576 _M_insert_range(_Rg&& __rg, bool __is_sorted = false)
577 {
578 auto __guard = _M_make_clear_guard();
579 typename container_type::iterator __it;
580 if constexpr (requires { _M_cont.insert_range(_M_cont.end(), __rg); })
581 __it = _M_cont.insert_range(_M_cont.end(), __rg);
582 else if constexpr (ranges::common_range<_Rg>
583 && __has_input_iter_cat<ranges::iterator_t<_Rg>>)
584 __it = _M_cont.insert(_M_cont.end(), ranges::begin(__rg), ranges::end(__rg));
585 else
586 {
587 size_type __n = size();
588 auto __first = ranges::begin(__rg);
589 auto __last = ranges::end(__rg);
590 for (; __first != __last; ++__first)
591 _M_cont.emplace_back(*__first);
592 __it = _M_cont.begin() + __n;
593 }
594 if (__is_sorted)
595 _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(__it, _M_cont.end(), _M_comp));
596 else
597 std::sort(__it, _M_cont.end(), _M_comp);
598 std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp);
599 if constexpr (!_Multi)
600 _M_unique();
601 __guard._M_disable();
602 }
603
604 template<__detail::__container_compatible_range<value_type> _Rg>
605 _GLIBCXX26_CONSTEXPR
606 void
607 insert_range(_Rg&& __rg)
608 { _M_insert_range(std::forward<_Rg>(__rg)); }
609
610 template<__detail::__container_compatible_range<value_type> _Rg>
611 _GLIBCXX26_CONSTEXPR
612 void
613 insert_range(__sorted_t, _Rg&& __rg)
614 { _M_insert_range(std::forward<_Rg>(__rg), true); }
615
616 _GLIBCXX26_CONSTEXPR
617 void
618 insert(initializer_list<value_type> __il)
619 { insert(__il.begin(), __il.end()); }
620
621 _GLIBCXX26_CONSTEXPR
622 void
623 insert(__sorted_t __s, initializer_list<value_type> __il)
624 { insert(__s, __il.begin(), __il.end()); }
625
626 _GLIBCXX26_CONSTEXPR
627 container_type
628 extract() &&
629 {
630 auto __guard = _M_make_clear_guard();
631 return std::move(_M_cont);
632 }
633
634 _GLIBCXX26_CONSTEXPR
635 void
636 replace(container_type&& __cont)
637 {
638 _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(__cont, _M_comp));
639 auto __guard = _M_make_clear_guard();
640 _M_cont = std::move(__cont);
641 __guard._M_disable();
642 }
643
644 _GLIBCXX26_CONSTEXPR
645 iterator
646 erase(const_iterator __position)
647 { return _M_cont.erase(__position); }
648
649 _GLIBCXX26_CONSTEXPR
650 size_type
651 erase(const key_type& __x)
652 { return erase<const key_type&>(__x); }
653
654 template<typename _Key2>
655 requires same_as<remove_cvref_t<_Key2>, _Key>
656 || (__transparent_comparator<_Compare>
657 && !is_convertible_v<_Key2, iterator>
658 && !is_convertible_v<_Key2, const_iterator>)
659 _GLIBCXX26_CONSTEXPR
660 size_type
661 erase(_Key2&& __x)
662 {
663 auto [__first, __last] = equal_range(std::forward<_Key2>(__x));
664 auto __n = __last - __first;
665 erase(__first, __last);
666 return __n;
667 }
668
669 _GLIBCXX26_CONSTEXPR
670 iterator
671 erase(const_iterator __first, const_iterator __last)
672 { return _M_cont.erase(__first, __last); }
673
674 _GLIBCXX26_CONSTEXPR
675 void
676 swap(_Derived& __y)
677 noexcept(is_nothrow_swappable_v<container_type>
678 && is_nothrow_swappable_v<key_compare>)
679 {
680 auto __guard = _M_make_clear_guard();
681 auto __guard_y = _ClearGuard{__y._M_cont};
682 ranges::swap(_M_cont, __y._M_cont);
683 ranges::swap(_M_comp, __y._M_comp);
684 __guard._M_disable();
685 __guard_y._M_disable();
686 }
687
688 _GLIBCXX26_CONSTEXPR
689 void
690 clear() noexcept
691 { _M_cont.clear(); }
692
693 // observers
694 [[nodiscard]]
695 _GLIBCXX26_CONSTEXPR
696 key_compare
697 key_comp() const
698 { return _M_comp; }
699
700 [[nodiscard]]
701 _GLIBCXX26_CONSTEXPR
702 value_compare
703 value_comp() const
704 { return _M_comp; }
705
706 // set operations
707 [[nodiscard]]
708 _GLIBCXX26_CONSTEXPR
709 iterator
710 find(const key_type& __x)
711 { return find<key_type>(__x); }
712
713 [[nodiscard]]
714 _GLIBCXX26_CONSTEXPR
715 const_iterator
716 find(const key_type& __x) const
717 { return find<key_type>(__x); }
718
719 template<typename _Key2>
720 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
721 [[nodiscard]]
722 _GLIBCXX26_CONSTEXPR
723 iterator
724 find(const _Key2& __x)
725 {
726 auto __it = lower_bound(__x);
727 if (__it != end() && !_M_comp(__x, *__it))
728 return __it;
729 else
730 return end();
731 }
732
733 template<typename _Key2>
734 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
735 [[nodiscard]]
736 _GLIBCXX26_CONSTEXPR
737 const_iterator
738 find(const _Key2& __x) const
739 {
740 auto __it = lower_bound(__x);
741 if (__it != cend() && !_M_comp(__x, *__it))
742 return __it;
743 else
744 return cend();
745 }
746
747 [[nodiscard]]
748 _GLIBCXX26_CONSTEXPR
749 size_type
750 count(const key_type& __x) const
751 { return count<key_type>(__x); }
752
753 template<typename _Key2>
754 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
755 [[nodiscard]]
756 _GLIBCXX26_CONSTEXPR
757 size_type
758 count(const _Key2& __x) const
759 {
760 if constexpr (!_Multi)
761 return contains<_Key2>(__x);
762 else
763 {
764 auto [__first, __last] = equal_range(__x);
765 return __last - __first;
766 }
767 }
768
769 [[nodiscard]]
770 _GLIBCXX26_CONSTEXPR
771 bool
772 contains(const key_type& __x) const
773 { return contains<key_type>(__x); }
774
775 template<typename _Key2>
776 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
777 [[nodiscard]]
778 _GLIBCXX26_CONSTEXPR
779 bool
780 contains(const _Key2& __x) const
781 { return find(__x) != cend(); }
782
783 [[nodiscard]]
784 _GLIBCXX26_CONSTEXPR
785 iterator
786 lower_bound(const key_type& __x)
787 { return lower_bound<key_type>(__x); }
788
789 [[nodiscard]]
790 _GLIBCXX26_CONSTEXPR
791 const_iterator
792 lower_bound(const key_type& __x) const
793 { return lower_bound<key_type>(__x); }
794
795 template<typename _Key2>
796 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
797 [[nodiscard]]
798 _GLIBCXX26_CONSTEXPR
799 iterator
800 lower_bound(const _Key2& __x)
801 { return std::lower_bound(begin(), end(), __x, _M_comp); }
802
803 template<typename _Key2>
804 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
805 [[nodiscard]]
806 _GLIBCXX26_CONSTEXPR
807 const_iterator
808 lower_bound(const _Key2& __x) const
809 { return std::lower_bound(begin(), end(), __x, _M_comp); }
810
811 [[nodiscard]]
812 _GLIBCXX26_CONSTEXPR
813 iterator
814 upper_bound(const key_type& __x)
815 { return upper_bound<key_type>(__x); }
816
817 [[nodiscard]]
818 _GLIBCXX26_CONSTEXPR
819 const_iterator
820 upper_bound(const key_type& __x) const
821 { return upper_bound<key_type>(__x); }
822
823 template<typename _Key2>
824 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
825 [[nodiscard]]
826 _GLIBCXX26_CONSTEXPR
827 iterator
828 upper_bound(const _Key2& __x)
829 { return std::upper_bound(begin(), end(), __x, _M_comp); }
830
831 template<typename _Key2>
832 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
833 [[nodiscard]]
834 _GLIBCXX26_CONSTEXPR
835 const_iterator
836 upper_bound(const _Key2& __x) const
837 { return std::upper_bound(begin(), end(), __x, _M_comp); }
838
839 [[nodiscard]]
840 _GLIBCXX26_CONSTEXPR
841 pair<iterator, iterator>
842 equal_range(const key_type& __x)
843 { return equal_range<key_type>(__x); }
844
845 [[nodiscard]]
846 _GLIBCXX26_CONSTEXPR
847 pair<const_iterator, const_iterator>
848 equal_range(const key_type& __x) const
849 { return equal_range<key_type>(__x); }
850
851 template<typename _Key2>
852 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
853 [[nodiscard]]
854 _GLIBCXX26_CONSTEXPR
855 pair<iterator, iterator>
856 equal_range(const _Key2& __x)
857 { return std::equal_range(begin(), end(), __x, _M_comp); }
858
859 template<typename _Key2>
860 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
861 [[nodiscard]]
862 _GLIBCXX26_CONSTEXPR
863 pair<const_iterator, const_iterator>
864 equal_range(const _Key2& __x) const
865 { return std::equal_range(begin(), end(), __x, _M_comp); }
866
867 [[nodiscard]]
868 friend _GLIBCXX26_CONSTEXPR bool
869 operator==(const _Derived& __x, const _Derived& __y)
870 { return std::equal(__x.begin(), __x.end(), __y.begin(), __y.end()); }
871
872 template<typename _Up = value_type>
873 [[nodiscard]]
874 friend _GLIBCXX26_CONSTEXPR __detail::__synth3way_t<_Up>
875 operator<=>(const _Derived& __x, const _Derived& __y)
876 {
877 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
878 __y.begin(), __y.end(),
879 __detail::__synth3way);
880 }
881
882 friend _GLIBCXX26_CONSTEXPR void
883 swap(_Derived& __x, _Derived& __y) noexcept(noexcept(__x.swap(__y)))
884 { return __x.swap(__y); }
885
886 template<typename _Predicate>
887 _GLIBCXX26_CONSTEXPR
888 size_type
889 _M_erase_if(_Predicate __pred)
890 {
891 auto __guard = _M_make_clear_guard();
892 auto __first = _M_cont.begin();
893 auto __last = _M_cont.end();
894 __first = std::remove_if(__first, __last, __pred);
895 auto __n = __last - __first;
896 erase(__first, __last);
897 __guard._M_disable();
898 return __n;
899 }
900
901 private:
902 container_type _M_cont;
903 [[no_unique_address]] _Compare _M_comp;
904
905 _GLIBCXX26_CONSTEXPR
906 void
907 _M_sort_uniq()
908 {
909 std::sort(_M_cont.begin(), _M_cont.end(), _M_comp);
910 if constexpr (!_Multi)
911 _M_unique();
912 }
913
914 _GLIBCXX26_CONSTEXPR
915 void
916 _M_unique() requires (!_Multi)
917 {
918 struct __key_equiv
919 {
920 _GLIBCXX26_CONSTEXPR
921 __key_equiv(key_compare __c) : _M_comp(__c) { }
922
923 _GLIBCXX26_CONSTEXPR
924 bool
925 operator()(const_reference __x, const_reference __y) const
926 { return !_M_comp(__x, __y) && !_M_comp(__y, __x); }
927
928 [[no_unique_address]] key_compare _M_comp;
929 };
930
931 auto __first = _M_cont.begin();
932 auto __last = _M_cont.end();
933 __first = std::unique(__first, __last, __key_equiv(_M_comp));
934 _M_cont.erase(__first, __last);
935 }
936 };
937
938 /* Class template flat_set - container adaptor
939 *
940 * @ingroup
941 */
942 template<typename _Key, typename _Compare = less<_Key>,
943 typename _KeyContainer = vector<_Key>>
944 class flat_set
945 : private _Flat_set_impl<_Key, _Compare, _KeyContainer, false>
946 {
947 using _Impl = _Flat_set_impl<_Key, _Compare, _KeyContainer, false>;
948 friend _Impl;
949
950 public:
951 // types
952 using typename _Impl::key_type;
953 using typename _Impl::value_type;
954 using typename _Impl::key_compare;
955 using typename _Impl::reference;
956 using typename _Impl::const_reference;
957 using typename _Impl::size_type;
958 using typename _Impl::difference_type;
959 using typename _Impl::iterator;
960 using typename _Impl::const_iterator;
961 using typename _Impl::reverse_iterator;
962 using typename _Impl::const_reverse_iterator;
963 using typename _Impl::container_type;
964 using typename _Impl::value_compare;
965
966 // constructors
967 using _Impl::_Impl;
968
969 // operator=(initializer_list<value_type>)
970 // Although this also brings in the base move/copy assignment operators,
971 // they will be hidden by our synthesized ones.
972 using _Impl::operator=;
973
974 // iterators
975 using _Impl::begin;
976 using _Impl::end;
977 using _Impl::rbegin;
978 using _Impl::rend;
979
980 using _Impl::cbegin;
981 using _Impl::cend;
982 using _Impl::crbegin;
983 using _Impl::crend;
984
985 // capacity
986 using _Impl::empty;
987 using _Impl::size;
988 using _Impl::max_size;
989
990 // modifiers
991 using _Impl::emplace;
992 using _Impl::emplace_hint;
993 using _Impl::insert;
994 using _Impl::insert_range;
995 using _Impl::extract;
996 using _Impl::replace;
997 using _Impl::erase;
998 using _Impl::swap;
999 using _Impl::clear;
1000
1001 // observers
1002 using _Impl::key_comp;
1003 using _Impl::value_comp;
1004
1005 // set operations
1006 using _Impl::find;
1007 using _Impl::count;
1008 using _Impl::contains;
1009 using _Impl::lower_bound;
1010 using _Impl::upper_bound;
1011 using _Impl::equal_range;
1012
1013 using _Impl::_M_erase_if;
1014 };
1015
1016 template<typename _KeyContainer,
1017 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
1018 flat_set(_KeyContainer, _Compare = _Compare())
1019 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1020
1021 template<typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc>
1022 flat_set(_KeyContainer, _Alloc)
1023 -> flat_set<typename _KeyContainer::value_type,
1024 less<typename _KeyContainer::value_type>, _KeyContainer>;
1025
1026 template<typename _KeyContainer, __not_allocator_like _Compare,
1027 __allocator_for<_KeyContainer> _Alloc>
1028 flat_set(_KeyContainer, _Compare, _Alloc)
1029 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1030
1031 template<typename _KeyContainer,
1032 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
1033 flat_set(sorted_unique_t, _KeyContainer, _Compare = _Compare())
1034 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1035
1036 template<typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc>
1037 flat_set(sorted_unique_t, _KeyContainer, _Alloc)
1038 -> flat_set<typename _KeyContainer::value_type,
1039 less<typename _KeyContainer::value_type>, _KeyContainer>;
1040
1041 template<typename _KeyContainer, __not_allocator_like _Compare,
1042 __allocator_for<_KeyContainer> _Alloc>
1043 flat_set(sorted_unique_t, _KeyContainer, _Compare, _Alloc)
1044 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1045
1046 template<__has_input_iter_cat _InputIterator,
1047 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
1048 flat_set(_InputIterator, _InputIterator, _Compare = _Compare())
1049 -> flat_set<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1050
1051 template<__has_input_iter_cat _InputIterator,
1052 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
1053 flat_set(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())
1054 -> flat_set<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1055
1056 template<ranges::input_range _Rg,
1057 __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>,
1058 __allocator_like _Alloc = allocator<ranges::range_value_t<_Rg>>>
1059 flat_set(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
1060 -> flat_set<ranges::range_value_t<_Rg>, _Compare,
1061 vector<ranges::range_value_t<_Rg>,
1062 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>;
1063
1064 template<ranges::input_range _Rg, __allocator_like _Alloc>
1065 flat_set(from_range_t, _Rg&&, _Alloc)
1066 -> flat_set<ranges::range_value_t<_Rg>, less<ranges::range_value_t<_Rg>>,
1067 vector<ranges::range_value_t<_Rg>,
1068 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>;
1069
1070 template<typename _Key, __not_allocator_like _Compare = less<_Key>>
1071 flat_set(initializer_list<_Key>, _Compare = _Compare())
1072 -> flat_set<_Key, _Compare>;
1073
1074 template<typename _Key, __not_allocator_like _Compare = less<_Key>>
1075 flat_set(sorted_unique_t, initializer_list<_Key>, _Compare = _Compare())
1076 -> flat_set<_Key, _Compare>;
1077
1078 template<typename _Key, typename _Compare,
1079 typename _KeyContainer, typename _Alloc>
1080 struct uses_allocator<flat_set<_Key, _Compare, _KeyContainer>, _Alloc>
1081 : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>>
1082 { };
1083
1084 template<typename _Key, typename _Compare, typename _KeyContainer,
1085 typename _Predicate>
1086 _GLIBCXX26_CONSTEXPR
1087 typename flat_set<_Key, _Compare, _KeyContainer>::size_type
1088 erase_if(flat_set<_Key, _Compare, _KeyContainer>& __c, _Predicate __pred)
1089 { return __c._M_erase_if(std::move(__pred)); }
1090
1091 /* Class template flat_multiset - container adaptor
1092 *
1093 * @ingroup
1094 */
1095 template<typename _Key, typename _Compare = less<_Key>,
1096 typename _KeyContainer = vector<_Key>>
1097 class flat_multiset
1098 : private _Flat_set_impl<_Key, _Compare, _KeyContainer, true>
1099 {
1100 using _Impl = _Flat_set_impl<_Key, _Compare, _KeyContainer, true>;
1101 friend _Impl;
1102
1103 public:
1104 // types
1105 using typename _Impl::key_type;
1106 using typename _Impl::value_type;
1107 using typename _Impl::key_compare;
1108 using typename _Impl::reference;
1109 using typename _Impl::const_reference;
1110 using typename _Impl::size_type;
1111 using typename _Impl::difference_type;
1112 using typename _Impl::iterator;
1113 using typename _Impl::const_iterator;
1114 using typename _Impl::reverse_iterator;
1115 using typename _Impl::const_reverse_iterator;
1116 using typename _Impl::container_type;
1117 using typename _Impl::value_compare;
1118
1119 // constructors
1120 using _Impl::_Impl;
1121
1122 // operator=(initializer_list<value_type>)
1123 // Although this also brings in the base move/copy assignment operators,
1124 // they will be hidden by our synthesized ones.
1125 using _Impl::operator=;
1126
1127 // iterators
1128 using _Impl::begin;
1129 using _Impl::end;
1130 using _Impl::rbegin;
1131 using _Impl::rend;
1132
1133 using _Impl::cbegin;
1134 using _Impl::cend;
1135 using _Impl::crbegin;
1136 using _Impl::crend;
1137
1138 // capacity
1139 using _Impl::empty;
1140 using _Impl::size;
1141 using _Impl::max_size;
1142
1143 // modifiers
1144 using _Impl::emplace;
1145 using _Impl::emplace_hint;
1146 using _Impl::insert;
1147 using _Impl::insert_range;
1148 using _Impl::extract;
1149 using _Impl::replace;
1150 using _Impl::erase;
1151 using _Impl::swap;
1152 using _Impl::clear;
1153
1154 // observers
1155 using _Impl::key_comp;
1156 using _Impl::value_comp;
1157
1158 // set operations
1159 using _Impl::find;
1160 using _Impl::count;
1161 using _Impl::contains;
1162 using _Impl::lower_bound;
1163 using _Impl::upper_bound;
1164 using _Impl::equal_range;
1165
1166 using _Impl::_M_erase_if;
1167 };
1168
1169 template<typename _KeyContainer,
1170 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
1171 flat_multiset(_KeyContainer, _Compare = _Compare())
1172 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1173
1174 template<typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc>
1175 flat_multiset(_KeyContainer, _Alloc)
1176 -> flat_multiset<typename _KeyContainer::value_type,
1177 less<typename _KeyContainer::value_type>, _KeyContainer>;
1178
1179 template<typename _KeyContainer, __not_allocator_like _Compare,
1180 __allocator_for<_KeyContainer> _Alloc>
1181 flat_multiset(_KeyContainer, _Compare, _Alloc)
1182 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1183
1184 template<typename _KeyContainer,
1185 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
1186 flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare = _Compare())
1187 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1188
1189 template<typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc>
1190 flat_multiset(sorted_equivalent_t, _KeyContainer, _Alloc)
1191 -> flat_multiset<typename _KeyContainer::value_type,
1192 less<typename _KeyContainer::value_type>, _KeyContainer>;
1193
1194 template<typename _KeyContainer, __not_allocator_like _Compare,
1195 __allocator_for<_KeyContainer> _Alloc>
1196 flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare, _Alloc)
1197 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1198
1199 template<__has_input_iter_cat _InputIterator,
1200 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
1201 flat_multiset(_InputIterator, _InputIterator, _Compare = _Compare())
1202 -> flat_multiset<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1203
1204 template<__has_input_iter_cat _InputIterator,
1205 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
1206 flat_multiset(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare())
1207 -> flat_multiset<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1208
1209 template<ranges::input_range _Rg,
1210 __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>,
1211 __allocator_like _Alloc = allocator<ranges::range_value_t<_Rg>>>
1212 flat_multiset(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
1213 -> flat_multiset<ranges::range_value_t<_Rg>, _Compare,
1214 vector<ranges::range_value_t<_Rg>,
1215 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>;
1216
1217 template<ranges::input_range _Rg, __allocator_like _Alloc>
1218 flat_multiset(from_range_t, _Rg&&, _Alloc)
1219 -> flat_multiset<ranges::range_value_t<_Rg>, less<ranges::range_value_t<_Rg>>,
1220 vector<ranges::range_value_t<_Rg>,
1221 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>;
1222
1223 template<typename _Key, __not_allocator_like _Compare = less<_Key>>
1224 flat_multiset(initializer_list<_Key>, _Compare = _Compare())
1225 -> flat_multiset<_Key, _Compare>;
1226
1227 template<typename _Key, __not_allocator_like _Compare = less<_Key>>
1228 flat_multiset(sorted_equivalent_t, initializer_list<_Key>, _Compare = _Compare())
1229 -> flat_multiset<_Key, _Compare>;
1230
1231 template<typename _Key, typename _Compare,
1232 typename _KeyContainer, typename _Alloc>
1233 struct uses_allocator<flat_multiset<_Key, _Compare, _KeyContainer>, _Alloc>
1234 : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>>
1235 { };
1236
1237 template<typename _Key, typename _Compare, typename _KeyContainer,
1238 typename _Predicate>
1239 _GLIBCXX26_CONSTEXPR
1240 typename flat_multiset<_Key, _Compare, _KeyContainer>::size_type
1241 erase_if(flat_multiset<_Key, _Compare, _KeyContainer>& __c, _Predicate __pred)
1242 { return __c._M_erase_if(std::move(__pred)); }
1243
1244_GLIBCXX_END_NAMESPACE_VERSION
1245} // namespace std
1246#endif // __cpp_lib_flat_set
1247#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:1875
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:53
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