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