libstdc++
debug/set.h
Go to the documentation of this file.
1 // Debugging set implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2016 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
45  : public __gnu_debug::_Safe_container<
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;
51  typedef __gnu_debug::_Safe_container<
52  set, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe;
53 
54  typedef typename _Base::const_iterator _Base_const_iterator;
55  typedef typename _Base::iterator _Base_iterator;
56  typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
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 
68  typedef __gnu_debug::_Safe_iterator<_Base_iterator, set>
69  iterator;
70  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set>
71  const_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;
77  typedef std::reverse_iterator<iterator> reverse_iterator;
78  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
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 
94  set(initializer_list<value_type> __l,
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 
170  const_iterator
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 
178  const_iterator
179  end() const _GLIBCXX_NOEXCEPT
180  { return const_iterator(_Base::end(), this); }
181 
182  reverse_iterator
183  rbegin() _GLIBCXX_NOEXCEPT
184  { return reverse_iterator(end()); }
185 
186  const_reverse_iterator
187  rbegin() const _GLIBCXX_NOEXCEPT
188  { return const_reverse_iterator(end()); }
189 
190  reverse_iterator
191  rend() _GLIBCXX_NOEXCEPT
192  { return reverse_iterator(begin()); }
193 
194  const_reverse_iterator
195  rend() const _GLIBCXX_NOEXCEPT
196  { return const_reverse_iterator(begin()); }
197 
198 #if __cplusplus >= 201103L
199  const_iterator
200  cbegin() const noexcept
201  { return const_iterator(_Base::begin(), this); }
202 
203  const_iterator
204  cend() const noexcept
205  { return const_iterator(_Base::end(), this); }
206 
207  const_reverse_iterator
208  crbegin() const noexcept
209  { return const_reverse_iterator(end()); }
210 
211  const_reverse_iterator
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>
224  std::pair<iterator, bool>
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 
243  std::pair<iterator, bool>
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
252  std::pair<iterator, bool>
253  insert(value_type&& __x)
254  {
255  std::pair<_Base_iterator, bool> __res
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  {
283  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
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 >= 201103L
300  iterator
301  erase(const_iterator __position)
302  {
303  __glibcxx_check_erase(__position);
304  this->_M_invalidate_if(_Equal(__position.base()));
305  return iterator(_Base::erase(__position.base()), this);
306  }
307 #else
308  void
309  erase(iterator __position)
310  {
311  __glibcxx_check_erase(__position);
312  this->_M_invalidate_if(_Equal(__position.base()));
313  _Base::erase(__position.base());
314  }
315 #endif
316 
317  size_type
318  erase(const key_type& __x)
319  {
320  _Base_iterator __victim = _Base::find(__x);
321  if (__victim == _Base::end())
322  return 0;
323  else
324  {
325  this->_M_invalidate_if(_Equal(__victim));
326  _Base::erase(__victim);
327  return 1;
328  }
329  }
330 
331 #if __cplusplus >= 201103L
332  iterator
333  erase(const_iterator __first, const_iterator __last)
334  {
335  // _GLIBCXX_RESOLVE_LIB_DEFECTS
336  // 151. can't currently clear() empty container
337  __glibcxx_check_erase_range(__first, __last);
338  for (_Base_const_iterator __victim = __first.base();
339  __victim != __last.base(); ++__victim)
340  {
341  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
342  _M_message(__gnu_debug::__msg_valid_range)
343  ._M_iterator(__first, "first")
344  ._M_iterator(__last, "last"));
345  this->_M_invalidate_if(_Equal(__victim));
346  }
347  return iterator(_Base::erase(__first.base(), __last.base()), this);
348  }
349 #else
350  void
351  erase(iterator __first, iterator __last)
352  {
353  // _GLIBCXX_RESOLVE_LIB_DEFECTS
354  // 151. can't currently clear() empty container
355  __glibcxx_check_erase_range(__first, __last);
356  for (_Base_iterator __victim = __first.base();
357  __victim != __last.base(); ++__victim)
358  {
359  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
360  _M_message(__gnu_debug::__msg_valid_range)
361  ._M_iterator(__first, "first")
362  ._M_iterator(__last, "last"));
363  this->_M_invalidate_if(_Equal(__victim));
364  }
365  _Base::erase(__first.base(), __last.base());
366  }
367 #endif
368 
369  void
370  swap(set& __x)
371  _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
372  {
373  _Safe::_M_swap(__x);
374  _Base::swap(__x);
375  }
376 
377  void
378  clear() _GLIBCXX_NOEXCEPT
379  {
380  this->_M_invalidate_all();
381  _Base::clear();
382  }
383 
384  // observers:
385  using _Base::key_comp;
386  using _Base::value_comp;
387 
388  // set operations:
389  iterator
390  find(const key_type& __x)
391  { return iterator(_Base::find(__x), this); }
392 
393  // _GLIBCXX_RESOLVE_LIB_DEFECTS
394  // 214. set::find() missing const overload
395  const_iterator
396  find(const key_type& __x) const
397  { return const_iterator(_Base::find(__x), this); }
398 
399 #if __cplusplus > 201103L
400  template<typename _Kt,
401  typename _Req =
402  typename __has_is_transparent<_Compare, _Kt>::type>
403  iterator
404  find(const _Kt& __x)
405  { return { _Base::find(__x), this }; }
406 
407  template<typename _Kt,
408  typename _Req =
409  typename __has_is_transparent<_Compare, _Kt>::type>
410  const_iterator
411  find(const _Kt& __x) const
412  { return { _Base::find(__x), this }; }
413 #endif
414 
415  using _Base::count;
416 
417  iterator
418  lower_bound(const key_type& __x)
419  { return iterator(_Base::lower_bound(__x), this); }
420 
421  // _GLIBCXX_RESOLVE_LIB_DEFECTS
422  // 214. set::find() missing const overload
423  const_iterator
424  lower_bound(const key_type& __x) const
425  { return const_iterator(_Base::lower_bound(__x), this); }
426 
427 #if __cplusplus > 201103L
428  template<typename _Kt,
429  typename _Req =
430  typename __has_is_transparent<_Compare, _Kt>::type>
431  iterator
432  lower_bound(const _Kt& __x)
433  { return { _Base::lower_bound(__x), this }; }
434 
435  template<typename _Kt,
436  typename _Req =
437  typename __has_is_transparent<_Compare, _Kt>::type>
438  const_iterator
439  lower_bound(const _Kt& __x) const
440  { return { _Base::lower_bound(__x), this }; }
441 #endif
442 
443  iterator
444  upper_bound(const key_type& __x)
445  { return iterator(_Base::upper_bound(__x), this); }
446 
447  // _GLIBCXX_RESOLVE_LIB_DEFECTS
448  // 214. set::find() missing const overload
449  const_iterator
450  upper_bound(const key_type& __x) const
451  { return const_iterator(_Base::upper_bound(__x), this); }
452 
453 #if __cplusplus > 201103L
454  template<typename _Kt,
455  typename _Req =
456  typename __has_is_transparent<_Compare, _Kt>::type>
457  iterator
458  upper_bound(const _Kt& __x)
459  { return { _Base::upper_bound(__x), this }; }
460 
461  template<typename _Kt,
462  typename _Req =
463  typename __has_is_transparent<_Compare, _Kt>::type>
464  const_iterator
465  upper_bound(const _Kt& __x) const
466  { return { _Base::upper_bound(__x), this }; }
467 #endif
468 
469  std::pair<iterator, iterator>
470  equal_range(const key_type& __x)
471  {
472  std::pair<_Base_iterator, _Base_iterator> __res =
473  _Base::equal_range(__x);
474  return std::make_pair(iterator(__res.first, this),
475  iterator(__res.second, this));
476  }
477 
478  // _GLIBCXX_RESOLVE_LIB_DEFECTS
479  // 214. set::find() missing const overload
480  std::pair<const_iterator, const_iterator>
481  equal_range(const key_type& __x) const
482  {
483  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
484  _Base::equal_range(__x);
485  return std::make_pair(const_iterator(__res.first, this),
486  const_iterator(__res.second, this));
487  }
488 
489 #if __cplusplus > 201103L
490  template<typename _Kt,
491  typename _Req =
492  typename __has_is_transparent<_Compare, _Kt>::type>
493  std::pair<iterator, iterator>
494  equal_range(const _Kt& __x)
495  {
496  auto __res = _Base::equal_range(__x);
497  return { { __res.first, this }, { __res.second, this } };
498  }
499 
500  template<typename _Kt,
501  typename _Req =
502  typename __has_is_transparent<_Compare, _Kt>::type>
503  std::pair<const_iterator, const_iterator>
504  equal_range(const _Kt& __x) const
505  {
506  auto __res = _Base::equal_range(__x);
507  return { { __res.first, this }, { __res.second, this } };
508  }
509 #endif
510 
511  _Base&
512  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
513 
514  const _Base&
515  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
516  };
517 
518  template<typename _Key, typename _Compare, typename _Allocator>
519  inline bool
520  operator==(const set<_Key, _Compare, _Allocator>& __lhs,
521  const set<_Key, _Compare, _Allocator>& __rhs)
522  { return __lhs._M_base() == __rhs._M_base(); }
523 
524  template<typename _Key, typename _Compare, typename _Allocator>
525  inline bool
526  operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
527  const set<_Key, _Compare, _Allocator>& __rhs)
528  { return __lhs._M_base() != __rhs._M_base(); }
529 
530  template<typename _Key, typename _Compare, typename _Allocator>
531  inline bool
532  operator<(const set<_Key, _Compare, _Allocator>& __lhs,
533  const set<_Key, _Compare, _Allocator>& __rhs)
534  { return __lhs._M_base() < __rhs._M_base(); }
535 
536  template<typename _Key, typename _Compare, typename _Allocator>
537  inline bool
538  operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
539  const set<_Key, _Compare, _Allocator>& __rhs)
540  { return __lhs._M_base() <= __rhs._M_base(); }
541 
542  template<typename _Key, typename _Compare, typename _Allocator>
543  inline bool
544  operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
545  const set<_Key, _Compare, _Allocator>& __rhs)
546  { return __lhs._M_base() >= __rhs._M_base(); }
547 
548  template<typename _Key, typename _Compare, typename _Allocator>
549  inline bool
550  operator>(const set<_Key, _Compare, _Allocator>& __lhs,
551  const set<_Key, _Compare, _Allocator>& __rhs)
552  { return __lhs._M_base() > __rhs._M_base(); }
553 
554  template<typename _Key, typename _Compare, typename _Allocator>
555  void
556  swap(set<_Key, _Compare, _Allocator>& __x,
557  set<_Key, _Compare, _Allocator>& __y)
558  _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
559  { return __x.swap(__y); }
560 
561 } // namespace __debug
562 } // namespace std
563 
564 #endif
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:196
__gnu_debug::_Safe_container
Safe class dealing with some allocator dependent operations.
Definition: safe_container.h:41
__gnu_debug::_Safe_iterator::base
_Iterator & base() noexcept
Return the underlying iterator.
Definition: safe_iterator.h:404
std::initializer_list
initializer_list
Definition: initializer_list:47
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:195
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition: macros.h:145
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition: formatter.h:56
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:173
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:190
std::make_pair
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:493
__gnu_debug::_Safe_node_sequence
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...
Definition: safe_sequence.h:131
std::__debug::set
Class std::set with safety/checking/debug instrumentation.
Definition: debug/set.h:44
std
ISO C++ entities toplevel namespace is std.
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition: macros.h:79