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