libstdc++
set.h
Go to the documentation of this file.
1 // Debugging set implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2025 Free Software Foundation, Inc.
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 debug/set.h
26  * This file is a GNU debug extension to the Standard C++ Library.
27  */
28 
29 #ifndef _GLIBCXX_DEBUG_SET_H
30 #define _GLIBCXX_DEBUG_SET_H 1
31 
32 #include <debug/safe_sequence.h>
33 #include <debug/safe_container.h>
34 #include <debug/safe_iterator.h>
35 #include <bits/stl_pair.h>
36 
37 namespace std _GLIBCXX_VISIBILITY(default)
38 {
39 namespace __debug
40 {
41  /// Class std::set with safety/checking/debug instrumentation.
42  template<typename _Key, typename _Compare = std::less<_Key>,
43  typename _Allocator = std::allocator<_Key> >
44  class set
46  set<_Key, _Compare, _Allocator>, _Allocator,
47  __gnu_debug::_Safe_node_sequence>,
48  public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>
49  {
50  typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;
53 
55  typedef typename _Base::iterator _Base_iterator;
57 
58  template<typename _ItT, typename _SeqT, typename _CatT>
59  friend class ::__gnu_debug::_Safe_iterator;
60 
61  // Reference wrapper for base class. Disambiguates set(const _Base&)
62  // from copy constructor by requiring a user-defined conversion.
63  // See PR libstdc++/90102.
64  struct _Base_ref
65  {
66  _Base_ref(const _Base& __r) : _M_ref(__r) { }
67 
68  const _Base& _M_ref;
69  };
70 
71  public:
72  // types:
73  typedef _Key key_type;
74  typedef _Key value_type;
75  typedef _Compare key_compare;
76  typedef _Compare value_compare;
77  typedef _Allocator allocator_type;
78  typedef typename _Base::reference reference;
79  typedef typename _Base::const_reference const_reference;
80 
82  iterator;
85 
86  typedef typename _Base::size_type size_type;
87  typedef typename _Base::difference_type difference_type;
88  typedef typename _Base::pointer pointer;
89  typedef typename _Base::const_pointer const_pointer;
92 
93  // 23.3.3.1 construct/copy/destroy:
94 
95 #if __cplusplus < 201103L
96  set() : _Base() { }
97 
98  set(const set& __x)
99  : _Base(__x) { }
100 
101  ~set() { }
102 #else
103  set() = default;
104  set(const set&) = default;
105  set(set&&) = default;
106 
108  const _Compare& __comp = _Compare(),
109  const allocator_type& __a = allocator_type())
110  : _Base(__l, __comp, __a) { }
111 
112  explicit
113  set(const allocator_type& __a)
114  : _Base(__a) { }
115 
116  set(const set& __x, const __type_identity_t<allocator_type>& __a)
117  : _Base(__x, __a) { }
118 
119  set(set&& __x, const __type_identity_t<allocator_type>& __a)
120  noexcept( noexcept(_Base(std::move(__x), __a)) )
121  : _Safe(std::move(__x), __a),
122  _Base(std::move(__x), __a) { }
123 
124  set(initializer_list<value_type> __l, const allocator_type& __a)
125  : _Base(__l, __a) { }
126 
127  template<typename _InputIterator>
128  set(_InputIterator __first, _InputIterator __last,
129  const allocator_type& __a)
131  __glibcxx_check_valid_constructor_range(__first, __last)),
132  __gnu_debug::__base(__last), __a) { }
133 
134 #if __glibcxx_containers_ranges // C++ >= 23
135  /**
136  * @brief Construct a set from a range.
137  * @since C++23
138  */
139  template<std::__detail::__container_compatible_range<_Key> _Rg>
140  set(std::from_range_t __t, _Rg&& __rg,
141  const _Compare& __c,
142  const allocator_type& __a = allocator_type())
143  : _Base(__t, std::forward<_Rg>(__rg), __c, __a)
144  { }
145 
146  template<std::__detail::__container_compatible_range<_Key> _Rg>
147  set(std::from_range_t __t, _Rg&& __rg,
148  const allocator_type& __a = allocator_type())
149  : _Base(__t, std::forward<_Rg>(__rg), __a)
150  { }
151 #endif
152 
153  ~set() = default;
154 #endif
155 
156  explicit set(const _Compare& __comp,
157  const _Allocator& __a = _Allocator())
158  : _Base(__comp, __a) { }
159 
160  template<typename _InputIterator>
161  set(_InputIterator __first, _InputIterator __last,
162  const _Compare& __comp = _Compare(),
163  const _Allocator& __a = _Allocator())
165  __glibcxx_check_valid_constructor_range(__first, __last)),
166  __gnu_debug::__base(__last),
167  __comp, __a) { }
168 
169  set(_Base_ref __x)
170  : _Base(__x._M_ref) { }
171 
172 #if __cplusplus >= 201103L
173  set&
174  operator=(const set&) = default;
175 
176  set&
177  operator=(set&&) = default;
178 
179  set&
180  operator=(initializer_list<value_type> __l)
181  {
182  _Base::operator=(__l);
183  this->_M_invalidate_all();
184  return *this;
185  }
186 #endif
187 
188  using _Base::get_allocator;
189 
190  // iterators:
191  iterator
192  begin() _GLIBCXX_NOEXCEPT
193  { return iterator(_Base::begin(), this); }
194 
196  begin() const _GLIBCXX_NOEXCEPT
197  { return const_iterator(_Base::begin(), this); }
198 
199  iterator
200  end() _GLIBCXX_NOEXCEPT
201  { return iterator(_Base::end(), this); }
202 
204  end() const _GLIBCXX_NOEXCEPT
205  { return const_iterator(_Base::end(), this); }
206 
208  rbegin() _GLIBCXX_NOEXCEPT
209  { return reverse_iterator(end()); }
210 
212  rbegin() const _GLIBCXX_NOEXCEPT
213  { return const_reverse_iterator(end()); }
214 
216  rend() _GLIBCXX_NOEXCEPT
217  { return reverse_iterator(begin()); }
218 
220  rend() const _GLIBCXX_NOEXCEPT
221  { return const_reverse_iterator(begin()); }
222 
223 #if __cplusplus >= 201103L
225  cbegin() const noexcept
226  { return const_iterator(_Base::begin(), this); }
227 
229  cend() const noexcept
230  { return const_iterator(_Base::end(), this); }
231 
233  crbegin() const noexcept
234  { return const_reverse_iterator(end()); }
235 
237  crend() const noexcept
238  { return const_reverse_iterator(begin()); }
239 #endif
240 
241  // capacity:
242  using _Base::empty;
243  using _Base::size;
244  using _Base::max_size;
245 
246  // modifiers:
247 #if __cplusplus >= 201103L
248  template<typename... _Args>
250  emplace(_Args&&... __args)
251  {
252  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
253  return { { __res.first, this }, __res.second };
254  }
255 
256  template<typename... _Args>
257  iterator
258  emplace_hint(const_iterator __pos, _Args&&... __args)
259  {
260  __glibcxx_check_insert(__pos);
261  return
262  {
263  _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
264  this
265  };
266  }
267 #endif
268 
270  insert(const value_type& __x)
271  {
272  std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
273  return std::pair<iterator, bool>(iterator(__res.first, this),
274  __res.second);
275  }
276 
277 #if __cplusplus >= 201103L
279  insert(value_type&& __x)
280  {
281  auto __res = _Base::insert(std::move(__x));
282  return { { __res.first, this }, __res.second };
283  }
284 #endif
285 
286  iterator
287  insert(const_iterator __position, const value_type& __x)
288  {
289  __glibcxx_check_insert(__position);
290  return iterator(_Base::insert(__position.base(), __x), this);
291  }
292 
293 #if __cplusplus >= 201103L
294  iterator
295  insert(const_iterator __position, value_type&& __x)
296  {
297  __glibcxx_check_insert(__position);
298  return { _Base::insert(__position.base(), std::move(__x)), this };
299  }
300 #endif
301 
302  template <typename _InputIterator>
303  void
304  insert(_InputIterator __first, _InputIterator __last)
305  {
307  __glibcxx_check_valid_range2(__first, __last, __dist);
308 
309  if (__dist.second >= __gnu_debug::__dp_sign)
310  _Base::insert(__gnu_debug::__unsafe(__first),
311  __gnu_debug::__unsafe(__last));
312  else
313  _Base::insert(__first, __last);
314  }
315 
316 #if __cplusplus >= 201103L
317  void
318  insert(initializer_list<value_type> __l)
319  { _Base::insert(__l); }
320 #endif
321 
322 #if __cplusplus > 201402L
323  using node_type = typename _Base::node_type;
325 
326  node_type
327  extract(const_iterator __position)
328  {
329  __glibcxx_check_erase(__position);
330  this->_M_invalidate_if(_Equal(__position.base()));
331  return _Base::extract(__position.base());
332  }
333 
334  node_type
335  extract(const key_type& __key)
336  {
337  const auto __position = find(__key);
338  if (__position != end())
339  return extract(__position);
340  return {};
341  }
342 
344  insert(node_type&& __nh)
345  {
346  auto __ret = _Base::insert(std::move(__nh));
347  iterator __pos = iterator(__ret.position, this);
348  return { __pos, __ret.inserted, std::move(__ret.node) };
349  }
350 
351  iterator
352  insert(const_iterator __hint, node_type&& __nh)
353  {
354  __glibcxx_check_insert(__hint);
355  return { _Base::insert(__hint.base(), std::move(__nh)), this };
356  }
357 
358  using _Base::merge;
359 #endif // C++17
360 
361 #if __cplusplus >= 201103L
362  _GLIBCXX_ABI_TAG_CXX11
363  iterator
364  erase(const_iterator __position)
365  {
366  __glibcxx_check_erase(__position);
367  return { erase(__position.base()), this };
368  }
369 
371  erase(_Base_const_iterator __position)
372  {
373  __glibcxx_check_erase2(__position);
374  this->_M_invalidate_if(_Equal(__position));
375  return _Base::erase(__position);
376  }
377 #else
378  void
379  erase(iterator __position)
380  {
381  __glibcxx_check_erase(__position);
382  this->_M_invalidate_if(_Equal(__position.base()));
383  _Base::erase(__position.base());
384  }
385 #endif
386 
387  size_type
388  erase(const key_type& __x)
389  {
390  _Base_iterator __victim = _Base::find(__x);
391  if (__victim == _Base::end())
392  return 0;
393  else
394  {
395  this->_M_invalidate_if(_Equal(__victim));
396  _Base::erase(__victim);
397  return 1;
398  }
399  }
400 
401 #if __cplusplus >= 201103L
402  _GLIBCXX_ABI_TAG_CXX11
403  iterator
404  erase(const_iterator __first, const_iterator __last)
405  {
406  // _GLIBCXX_RESOLVE_LIB_DEFECTS
407  // 151. can't currently clear() empty container
408  __glibcxx_check_erase_range(__first, __last);
409  for (_Base_const_iterator __victim = __first.base();
410  __victim != __last.base(); ++__victim)
411  {
412  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
413  _M_message(__gnu_debug::__msg_valid_range)
414  ._M_iterator(__first, "first")
415  ._M_iterator(__last, "last"));
416  this->_M_invalidate_if(_Equal(__victim));
417  }
418 
419  return { _Base::erase(__first.base(), __last.base()), this };
420  }
421 #else
422  void
423  erase(iterator __first, iterator __last)
424  {
425  // _GLIBCXX_RESOLVE_LIB_DEFECTS
426  // 151. can't currently clear() empty container
427  __glibcxx_check_erase_range(__first, __last);
428  for (_Base_iterator __victim = __first.base();
429  __victim != __last.base(); ++__victim)
430  {
431  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
432  _M_message(__gnu_debug::__msg_valid_range)
433  ._M_iterator(__first, "first")
434  ._M_iterator(__last, "last"));
435  this->_M_invalidate_if(_Equal(__victim));
436  }
437  _Base::erase(__first.base(), __last.base());
438  }
439 #endif
440 
441  void
442  swap(set& __x)
443  _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
444  {
445  _Safe::_M_swap(__x);
446  _Base::swap(__x);
447  }
448 
449  void
450  clear() _GLIBCXX_NOEXCEPT
451  {
452  this->_M_invalidate_all();
453  _Base::clear();
454  }
455 
456  // observers:
457  using _Base::key_comp;
458  using _Base::value_comp;
459 
460  // set operations:
461  iterator
462  find(const key_type& __x)
463  { return iterator(_Base::find(__x), this); }
464 
465  // _GLIBCXX_RESOLVE_LIB_DEFECTS
466  // 214. set::find() missing const overload
468  find(const key_type& __x) const
469  { return const_iterator(_Base::find(__x), this); }
470 
471 #if __cplusplus > 201103L
472  template<typename _Kt,
473  typename _Req =
474  typename __has_is_transparent<_Compare, _Kt>::type>
475  iterator
476  find(const _Kt& __x)
477  { return { _Base::find(__x), this }; }
478 
479  template<typename _Kt,
480  typename _Req =
481  typename __has_is_transparent<_Compare, _Kt>::type>
483  find(const _Kt& __x) const
484  { return { _Base::find(__x), this }; }
485 #endif
486 
487  using _Base::count;
488 
489  iterator
490  lower_bound(const key_type& __x)
491  { return iterator(_Base::lower_bound(__x), this); }
492 
493  // _GLIBCXX_RESOLVE_LIB_DEFECTS
494  // 214. set::find() missing const overload
496  lower_bound(const key_type& __x) const
497  { return const_iterator(_Base::lower_bound(__x), this); }
498 
499 #if __cplusplus > 201103L
500  template<typename _Kt,
501  typename _Req =
502  typename __has_is_transparent<_Compare, _Kt>::type>
503  iterator
504  lower_bound(const _Kt& __x)
505  { return { _Base::lower_bound(__x), this }; }
506 
507  template<typename _Kt,
508  typename _Req =
509  typename __has_is_transparent<_Compare, _Kt>::type>
511  lower_bound(const _Kt& __x) const
512  { return { _Base::lower_bound(__x), this }; }
513 #endif
514 
515  iterator
516  upper_bound(const key_type& __x)
517  { return iterator(_Base::upper_bound(__x), this); }
518 
519  // _GLIBCXX_RESOLVE_LIB_DEFECTS
520  // 214. set::find() missing const overload
522  upper_bound(const key_type& __x) const
523  { return const_iterator(_Base::upper_bound(__x), this); }
524 
525 #if __cplusplus > 201103L
526  template<typename _Kt,
527  typename _Req =
528  typename __has_is_transparent<_Compare, _Kt>::type>
529  iterator
530  upper_bound(const _Kt& __x)
531  { return { _Base::upper_bound(__x), this }; }
532 
533  template<typename _Kt,
534  typename _Req =
535  typename __has_is_transparent<_Compare, _Kt>::type>
537  upper_bound(const _Kt& __x) const
538  { return { _Base::upper_bound(__x), this }; }
539 #endif
540 
542  equal_range(const key_type& __x)
543  {
545  _Base::equal_range(__x);
546  return std::make_pair(iterator(__res.first, this),
547  iterator(__res.second, this));
548  }
549 
550  // _GLIBCXX_RESOLVE_LIB_DEFECTS
551  // 214. set::find() missing const overload
553  equal_range(const key_type& __x) const
554  {
556  _Base::equal_range(__x);
557  return std::make_pair(const_iterator(__res.first, this),
558  const_iterator(__res.second, this));
559  }
560 
561 #if __cplusplus > 201103L
562  template<typename _Kt,
563  typename _Req =
564  typename __has_is_transparent<_Compare, _Kt>::type>
566  equal_range(const _Kt& __x)
567  {
568  auto __res = _Base::equal_range(__x);
569  return { { __res.first, this }, { __res.second, this } };
570  }
571 
572  template<typename _Kt,
573  typename _Req =
574  typename __has_is_transparent<_Compare, _Kt>::type>
576  equal_range(const _Kt& __x) const
577  {
578  auto __res = _Base::equal_range(__x);
579  return { { __res.first, this }, { __res.second, this } };
580  }
581 #endif
582 
583  _Base&
584  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
585 
586  const _Base&
587  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
588  };
589 
590 #if __cpp_deduction_guides >= 201606
591 
592  template<typename _InputIterator,
593  typename _Compare =
595  typename _Allocator =
597  typename = _RequireInputIter<_InputIterator>,
598  typename = _RequireNotAllocator<_Compare>,
599  typename = _RequireAllocator<_Allocator>>
600  set(_InputIterator, _InputIterator,
601  _Compare = _Compare(), _Allocator = _Allocator())
603  _Compare, _Allocator>;
604 
605  template<typename _Key, typename _Compare = less<_Key>,
606  typename _Allocator = allocator<_Key>,
607  typename = _RequireNotAllocator<_Compare>,
608  typename = _RequireAllocator<_Allocator>>
610  _Compare = _Compare(), _Allocator = _Allocator())
612 
613  template<typename _InputIterator, typename _Allocator,
614  typename = _RequireInputIter<_InputIterator>,
615  typename = _RequireAllocator<_Allocator>>
616  set(_InputIterator, _InputIterator, _Allocator)
619  _Allocator>;
620 
621  template<typename _Key, typename _Allocator,
622  typename = _RequireAllocator<_Allocator>>
623  set(initializer_list<_Key>, _Allocator)
624  -> set<_Key, less<_Key>, _Allocator>;
625 
626 #if __glibcxx_containers_ranges // C++ >= 23
627  template<ranges::input_range _Rg,
628  __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>,
629  __allocator_like _Alloc = std::allocator<ranges::range_value_t<_Rg>>>
630  set(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
631  -> set<ranges::range_value_t<_Rg>, _Compare, _Alloc>;
632 
633  template<ranges::input_range _Rg, __allocator_like _Alloc>
634  set(from_range_t, _Rg&&, _Alloc)
636 #endif
637 #endif // deduction guides
638 
639  template<typename _Key, typename _Compare, typename _Allocator>
640  inline bool
641  operator==(const set<_Key, _Compare, _Allocator>& __lhs,
642  const set<_Key, _Compare, _Allocator>& __rhs)
643  { return __lhs._M_base() == __rhs._M_base(); }
644 
645 #if __cpp_lib_three_way_comparison
646  template<typename _Key, typename _Compare, typename _Alloc>
647  inline __detail::__synth3way_t<_Key>
648  operator<=>(const set<_Key, _Compare, _Alloc>& __lhs,
649  const set<_Key, _Compare, _Alloc>& __rhs)
650  { return __lhs._M_base() <=> __rhs._M_base(); }
651 #else
652  template<typename _Key, typename _Compare, typename _Allocator>
653  inline bool
654  operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
655  const set<_Key, _Compare, _Allocator>& __rhs)
656  { return __lhs._M_base() != __rhs._M_base(); }
657 
658  template<typename _Key, typename _Compare, typename _Allocator>
659  inline bool
660  operator<(const set<_Key, _Compare, _Allocator>& __lhs,
661  const set<_Key, _Compare, _Allocator>& __rhs)
662  { return __lhs._M_base() < __rhs._M_base(); }
663 
664  template<typename _Key, typename _Compare, typename _Allocator>
665  inline bool
666  operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
667  const set<_Key, _Compare, _Allocator>& __rhs)
668  { return __lhs._M_base() <= __rhs._M_base(); }
669 
670  template<typename _Key, typename _Compare, typename _Allocator>
671  inline bool
672  operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
673  const set<_Key, _Compare, _Allocator>& __rhs)
674  { return __lhs._M_base() >= __rhs._M_base(); }
675 
676  template<typename _Key, typename _Compare, typename _Allocator>
677  inline bool
678  operator>(const set<_Key, _Compare, _Allocator>& __lhs,
679  const set<_Key, _Compare, _Allocator>& __rhs)
680  { return __lhs._M_base() > __rhs._M_base(); }
681 #endif // three-way comparison
682 
683  template<typename _Key, typename _Compare, typename _Allocator>
684  void
685  swap(set<_Key, _Compare, _Allocator>& __x,
686  set<_Key, _Compare, _Allocator>& __y)
687  _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
688  { return __x.swap(__y); }
689 
690 } // namespace __debug
691 } // namespace std
692 
693 #endif
#define __glibcxx_check_insert(_Position)
Definition: macros.h:143
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:245
#define __glibcxx_check_erase(_Position)
Definition: macros.h:209
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:859
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:873
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:826
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:866
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:138
ISO C++ entities toplevel namespace is std.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:294
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:274
constexpr _Iterator __base(_Iterator __it)
initializer_list
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:134
Safe iterator wrapper.
constexpr _Iterator & base() noexcept
Return the underlying iterator.
Return type of insert(node_handle&&) on unique maps/sets.
Definition: node_handle.h:398
One of the comparison functors.
Definition: stl_function.h:401
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:304
_T1 first
The first member.
Definition: stl_pair.h:308
_T2 second
The second member.
Definition: stl_pair.h:309
A standard container made up of unique keys, which can be retrieved in logarithmic time.
Definition: stl_set.h:100
void _M_invalidate_if(_Predicate __pred)
Safe class dealing with some allocator dependent operations.
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...
Class std::set with safety/checking/debug instrumentation.
Definition: set.h:49