libstdc++
set.h
Go to the documentation of this file.
1 // Debugging set implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2020 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 <utility>
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  public:
62  // types:
63  typedef _Key key_type;
64  typedef _Key value_type;
65  typedef _Compare key_compare;
66  typedef _Compare value_compare;
67  typedef _Allocator allocator_type;
68  typedef typename _Base::reference reference;
69  typedef typename _Base::const_reference const_reference;
70 
72  iterator;
75 
76  typedef typename _Base::size_type size_type;
77  typedef typename _Base::difference_type difference_type;
78  typedef typename _Base::pointer pointer;
79  typedef typename _Base::const_pointer const_pointer;
82 
83  // 23.3.3.1 construct/copy/destroy:
84 
85 #if __cplusplus < 201103L
86  set() : _Base() { }
87 
88  set(const set& __x)
89  : _Base(__x) { }
90 
91  ~set() { }
92 #else
93  set() = default;
94  set(const set&) = default;
95  set(set&&) = default;
96 
98  const _Compare& __comp = _Compare(),
99  const allocator_type& __a = allocator_type())
100  : _Base(__l, __comp, __a) { }
101 
102  explicit
103  set(const allocator_type& __a)
104  : _Base(__a) { }
105 
106  set(const set& __x, const allocator_type& __a)
107  : _Base(__x, __a) { }
108 
109  set(set&& __x, const allocator_type& __a)
110  noexcept( noexcept(_Base(std::move(__x._M_base()), __a)) )
111  : _Safe(std::move(__x._M_safe()), __a),
112  _Base(std::move(__x._M_base()), __a) { }
113 
114  set(initializer_list<value_type> __l, const allocator_type& __a)
115  : _Base(__l, __a) { }
116 
117  template<typename _InputIterator>
118  set(_InputIterator __first, _InputIterator __last,
119  const allocator_type& __a)
121  __glibcxx_check_valid_constructor_range(__first, __last)),
122  __gnu_debug::__base(__last), __a) { }
123 
124  ~set() = default;
125 #endif
126 
127  explicit set(const _Compare& __comp,
128  const _Allocator& __a = _Allocator())
129  : _Base(__comp, __a) { }
130 
131  template<typename _InputIterator>
132  set(_InputIterator __first, _InputIterator __last,
133  const _Compare& __comp = _Compare(),
134  const _Allocator& __a = _Allocator())
136  __glibcxx_check_valid_constructor_range(__first, __last)),
137  __gnu_debug::__base(__last),
138  __comp, __a) { }
139 
140  set(const _Base& __x)
141  : _Base(__x) { }
142 
143 #if __cplusplus < 201103L
144  set&
145  operator=(const set& __x)
146  {
147  this->_M_safe() = __x;
148  _M_base() = __x;
149  return *this;
150  }
151 #else
152  set&
153  operator=(const set&) = default;
154 
155  set&
156  operator=(set&&) = default;
157 
158  set&
159  operator=(initializer_list<value_type> __l)
160  {
161  _M_base() = __l;
162  this->_M_invalidate_all();
163  return *this;
164  }
165 #endif
166 
167  using _Base::get_allocator;
168 
169  // iterators:
170  iterator
171  begin() _GLIBCXX_NOEXCEPT
172  { return iterator(_Base::begin(), this); }
173 
175  begin() const _GLIBCXX_NOEXCEPT
176  { return const_iterator(_Base::begin(), this); }
177 
178  iterator
179  end() _GLIBCXX_NOEXCEPT
180  { return iterator(_Base::end(), this); }
181 
183  end() const _GLIBCXX_NOEXCEPT
184  { return const_iterator(_Base::end(), this); }
185 
187  rbegin() _GLIBCXX_NOEXCEPT
188  { return reverse_iterator(end()); }
189 
191  rbegin() const _GLIBCXX_NOEXCEPT
192  { return const_reverse_iterator(end()); }
193 
195  rend() _GLIBCXX_NOEXCEPT
196  { return reverse_iterator(begin()); }
197 
199  rend() const _GLIBCXX_NOEXCEPT
200  { return const_reverse_iterator(begin()); }
201 
202 #if __cplusplus >= 201103L
204  cbegin() const noexcept
205  { return const_iterator(_Base::begin(), this); }
206 
208  cend() const noexcept
209  { return const_iterator(_Base::end(), this); }
210 
212  crbegin() const noexcept
213  { return const_reverse_iterator(end()); }
214 
216  crend() const noexcept
217  { return const_reverse_iterator(begin()); }
218 #endif
219 
220  // capacity:
221  using _Base::empty;
222  using _Base::size;
223  using _Base::max_size;
224 
225  // modifiers:
226 #if __cplusplus >= 201103L
227  template<typename... _Args>
229  emplace(_Args&&... __args)
230  {
231  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
232  return { { __res.first, this }, __res.second };
233  }
234 
235  template<typename... _Args>
236  iterator
237  emplace_hint(const_iterator __pos, _Args&&... __args)
238  {
239  __glibcxx_check_insert(__pos);
240  return
241  {
242  _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
243  this
244  };
245  }
246 #endif
247 
249  insert(const value_type& __x)
250  {
251  std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
252  return std::pair<iterator, bool>(iterator(__res.first, this),
253  __res.second);
254  }
255 
256 #if __cplusplus >= 201103L
258  insert(value_type&& __x)
259  {
260  auto __res = _Base::insert(std::move(__x));
261  return { { __res.first, this }, __res.second };
262  }
263 #endif
264 
265  iterator
266  insert(const_iterator __position, const value_type& __x)
267  {
268  __glibcxx_check_insert(__position);
269  return iterator(_Base::insert(__position.base(), __x), this);
270  }
271 
272 #if __cplusplus >= 201103L
273  iterator
274  insert(const_iterator __position, value_type&& __x)
275  {
276  __glibcxx_check_insert(__position);
277  return { _Base::insert(__position.base(), std::move(__x)), this };
278  }
279 #endif
280 
281  template <typename _InputIterator>
282  void
283  insert(_InputIterator __first, _InputIterator __last)
284  {
286  __glibcxx_check_valid_range2(__first, __last, __dist);
287 
288  if (__dist.second >= __gnu_debug::__dp_sign)
289  _Base::insert(__gnu_debug::__unsafe(__first),
290  __gnu_debug::__unsafe(__last));
291  else
292  _Base::insert(__first, __last);
293  }
294 
295 #if __cplusplus >= 201103L
296  void
297  insert(initializer_list<value_type> __l)
298  { _Base::insert(__l); }
299 #endif
300 
301 #if __cplusplus > 201402L
302  using node_type = typename _Base::node_type;
303  using insert_return_type = _Node_insert_return<iterator, node_type>;
304 
305  node_type
306  extract(const_iterator __position)
307  {
308  __glibcxx_check_erase(__position);
309  this->_M_invalidate_if(_Equal(__position.base()));
310  return _Base::extract(__position.base());
311  }
312 
313  node_type
314  extract(const key_type& __key)
315  {
316  const auto __position = find(__key);
317  if (__position != end())
318  return extract(__position);
319  return {};
320  }
321 
322  insert_return_type
323  insert(node_type&& __nh)
324  {
325  auto __ret = _Base::insert(std::move(__nh));
326  iterator __pos = iterator(__ret.position, this);
327  return { __pos, __ret.inserted, std::move(__ret.node) };
328  }
329 
330  iterator
331  insert(const_iterator __hint, node_type&& __nh)
332  {
333  __glibcxx_check_insert(__hint);
334  return { _Base::insert(__hint.base(), std::move(__nh)), this };
335  }
336 
337  using _Base::merge;
338 #endif // C++17
339 
340 #if __cplusplus >= 201103L
341  _GLIBCXX_ABI_TAG_CXX11
342  iterator
343  erase(const_iterator __position)
344  {
345  __glibcxx_check_erase(__position);
346  this->_M_invalidate_if(_Equal(__position.base()));
347  return { _Base::erase(__position.base()), this };
348  }
349 #else
350  void
351  erase(iterator __position)
352  {
353  __glibcxx_check_erase(__position);
354  this->_M_invalidate_if(_Equal(__position.base()));
355  _Base::erase(__position.base());
356  }
357 #endif
358 
359  size_type
360  erase(const key_type& __x)
361  {
362  _Base_iterator __victim = _Base::find(__x);
363  if (__victim == _Base::end())
364  return 0;
365  else
366  {
367  this->_M_invalidate_if(_Equal(__victim));
368  _Base::erase(__victim);
369  return 1;
370  }
371  }
372 
373 #if __cplusplus >= 201103L
374  _GLIBCXX_ABI_TAG_CXX11
375  iterator
376  erase(const_iterator __first, const_iterator __last)
377  {
378  // _GLIBCXX_RESOLVE_LIB_DEFECTS
379  // 151. can't currently clear() empty container
380  __glibcxx_check_erase_range(__first, __last);
381  for (_Base_const_iterator __victim = __first.base();
382  __victim != __last.base(); ++__victim)
383  {
384  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
385  _M_message(__gnu_debug::__msg_valid_range)
386  ._M_iterator(__first, "first")
387  ._M_iterator(__last, "last"));
388  this->_M_invalidate_if(_Equal(__victim));
389  }
390 
391  return { _Base::erase(__first.base(), __last.base()), this };
392  }
393 #else
394  void
395  erase(iterator __first, iterator __last)
396  {
397  // _GLIBCXX_RESOLVE_LIB_DEFECTS
398  // 151. can't currently clear() empty container
399  __glibcxx_check_erase_range(__first, __last);
400  for (_Base_iterator __victim = __first.base();
401  __victim != __last.base(); ++__victim)
402  {
403  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
404  _M_message(__gnu_debug::__msg_valid_range)
405  ._M_iterator(__first, "first")
406  ._M_iterator(__last, "last"));
407  this->_M_invalidate_if(_Equal(__victim));
408  }
409  _Base::erase(__first.base(), __last.base());
410  }
411 #endif
412 
413  void
414  swap(set& __x)
415  _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
416  {
417  _Safe::_M_swap(__x);
418  _Base::swap(__x);
419  }
420 
421  void
422  clear() _GLIBCXX_NOEXCEPT
423  {
424  this->_M_invalidate_all();
425  _Base::clear();
426  }
427 
428  // observers:
429  using _Base::key_comp;
430  using _Base::value_comp;
431 
432  // set operations:
433  iterator
434  find(const key_type& __x)
435  { return iterator(_Base::find(__x), this); }
436 
437  // _GLIBCXX_RESOLVE_LIB_DEFECTS
438  // 214. set::find() missing const overload
440  find(const key_type& __x) const
441  { return const_iterator(_Base::find(__x), this); }
442 
443 #if __cplusplus > 201103L
444  template<typename _Kt,
445  typename _Req =
446  typename __has_is_transparent<_Compare, _Kt>::type>
447  iterator
448  find(const _Kt& __x)
449  { return { _Base::find(__x), this }; }
450 
451  template<typename _Kt,
452  typename _Req =
453  typename __has_is_transparent<_Compare, _Kt>::type>
455  find(const _Kt& __x) const
456  { return { _Base::find(__x), this }; }
457 #endif
458 
459  using _Base::count;
460 
461  iterator
462  lower_bound(const key_type& __x)
463  { return iterator(_Base::lower_bound(__x), this); }
464 
465  // _GLIBCXX_RESOLVE_LIB_DEFECTS
466  // 214. set::find() missing const overload
468  lower_bound(const key_type& __x) const
469  { return const_iterator(_Base::lower_bound(__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  lower_bound(const _Kt& __x)
477  { return { _Base::lower_bound(__x), this }; }
478 
479  template<typename _Kt,
480  typename _Req =
481  typename __has_is_transparent<_Compare, _Kt>::type>
483  lower_bound(const _Kt& __x) const
484  { return { _Base::lower_bound(__x), this }; }
485 #endif
486 
487  iterator
488  upper_bound(const key_type& __x)
489  { return iterator(_Base::upper_bound(__x), this); }
490 
491  // _GLIBCXX_RESOLVE_LIB_DEFECTS
492  // 214. set::find() missing const overload
494  upper_bound(const key_type& __x) const
495  { return const_iterator(_Base::upper_bound(__x), this); }
496 
497 #if __cplusplus > 201103L
498  template<typename _Kt,
499  typename _Req =
500  typename __has_is_transparent<_Compare, _Kt>::type>
501  iterator
502  upper_bound(const _Kt& __x)
503  { return { _Base::upper_bound(__x), this }; }
504 
505  template<typename _Kt,
506  typename _Req =
507  typename __has_is_transparent<_Compare, _Kt>::type>
509  upper_bound(const _Kt& __x) const
510  { return { _Base::upper_bound(__x), this }; }
511 #endif
512 
514  equal_range(const key_type& __x)
515  {
517  _Base::equal_range(__x);
518  return std::make_pair(iterator(__res.first, this),
519  iterator(__res.second, this));
520  }
521 
522  // _GLIBCXX_RESOLVE_LIB_DEFECTS
523  // 214. set::find() missing const overload
525  equal_range(const key_type& __x) const
526  {
528  _Base::equal_range(__x);
529  return std::make_pair(const_iterator(__res.first, this),
530  const_iterator(__res.second, this));
531  }
532 
533 #if __cplusplus > 201103L
534  template<typename _Kt,
535  typename _Req =
536  typename __has_is_transparent<_Compare, _Kt>::type>
538  equal_range(const _Kt& __x)
539  {
540  auto __res = _Base::equal_range(__x);
541  return { { __res.first, this }, { __res.second, this } };
542  }
543 
544  template<typename _Kt,
545  typename _Req =
546  typename __has_is_transparent<_Compare, _Kt>::type>
548  equal_range(const _Kt& __x) const
549  {
550  auto __res = _Base::equal_range(__x);
551  return { { __res.first, this }, { __res.second, this } };
552  }
553 #endif
554 
555  _Base&
556  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
557 
558  const _Base&
559  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
560  };
561 
562 #if __cpp_deduction_guides >= 201606
563 
564  template<typename _InputIterator,
565  typename _Compare =
567  typename _Allocator =
569  typename = _RequireInputIter<_InputIterator>,
570  typename = _RequireNotAllocator<_Compare>,
571  typename = _RequireAllocator<_Allocator>>
572  set(_InputIterator, _InputIterator,
573  _Compare = _Compare(), _Allocator = _Allocator())
575  _Compare, _Allocator>;
576 
577  template<typename _Key, typename _Compare = less<_Key>,
578  typename _Allocator = allocator<_Key>,
579  typename = _RequireNotAllocator<_Compare>,
580  typename = _RequireAllocator<_Allocator>>
582  _Compare = _Compare(), _Allocator = _Allocator())
584 
585  template<typename _InputIterator, typename _Allocator,
586  typename = _RequireInputIter<_InputIterator>,
587  typename = _RequireAllocator<_Allocator>>
588  set(_InputIterator, _InputIterator, _Allocator)
591  _Allocator>;
592 
593  template<typename _Key, typename _Allocator,
594  typename = _RequireAllocator<_Allocator>>
595  set(initializer_list<_Key>, _Allocator)
596  -> set<_Key, less<_Key>, _Allocator>;
597 
598 #endif // deduction guides
599 
600  template<typename _Key, typename _Compare, typename _Allocator>
601  inline bool
602  operator==(const set<_Key, _Compare, _Allocator>& __lhs,
603  const set<_Key, _Compare, _Allocator>& __rhs)
604  { return __lhs._M_base() == __rhs._M_base(); }
605 
606 #if __cpp_lib_three_way_comparison
607  template<typename _Key, typename _Compare, typename _Alloc>
608  inline __detail::__synth3way_t<_Key>
609  operator<=>(const set<_Key, _Compare, _Alloc>& __lhs,
610  const set<_Key, _Compare, _Alloc>& __rhs)
611  { return __lhs._M_base() <=> __rhs._M_base(); }
612 #else
613  template<typename _Key, typename _Compare, typename _Allocator>
614  inline bool
615  operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
616  const set<_Key, _Compare, _Allocator>& __rhs)
617  { return __lhs._M_base() != __rhs._M_base(); }
618 
619  template<typename _Key, typename _Compare, typename _Allocator>
620  inline bool
621  operator<(const set<_Key, _Compare, _Allocator>& __lhs,
622  const set<_Key, _Compare, _Allocator>& __rhs)
623  { return __lhs._M_base() < __rhs._M_base(); }
624 
625  template<typename _Key, typename _Compare, typename _Allocator>
626  inline bool
627  operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
628  const set<_Key, _Compare, _Allocator>& __rhs)
629  { return __lhs._M_base() <= __rhs._M_base(); }
630 
631  template<typename _Key, typename _Compare, typename _Allocator>
632  inline bool
633  operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
634  const set<_Key, _Compare, _Allocator>& __rhs)
635  { return __lhs._M_base() >= __rhs._M_base(); }
636 
637  template<typename _Key, typename _Compare, typename _Allocator>
638  inline bool
639  operator>(const set<_Key, _Compare, _Allocator>& __lhs,
640  const set<_Key, _Compare, _Allocator>& __rhs)
641  { return __lhs._M_base() > __rhs._M_base(); }
642 #endif // three-way comparison
643 
644  template<typename _Key, typename _Compare, typename _Allocator>
645  void
646  swap(set<_Key, _Compare, _Allocator>& __x,
647  set<_Key, _Compare, _Allocator>& __y)
648  _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
649  { return __x.swap(__y); }
650 
651 } // namespace __debug
652 } // namespace std
653 
654 #endif
#define __glibcxx_check_insert(_Position)
Definition: macros.h:156
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:250
#define __glibcxx_check_erase(_Position)
Definition: macros.h:222
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
ISO C++ entities toplevel namespace is std.
constexpr _Iterator __base(_Iterator __it)
initializer_list
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:123
One of the comparison functors.
Definition: stl_function.h:382
A standard container made up of unique keys, which can be retrieved in logarithmic time.
Definition: stl_set.h:95
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213
_T1 first
The first member.
Definition: stl_pair.h:217
_T2 second
The second member.
Definition: stl_pair.h:218
Safe iterator wrapper.
_Iterator & base() noexcept
Return the underlying iterator.
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