libstdc++
debug/set.h
Go to the documentation of this file.
1 // Debugging set implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2014 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_iterator.h>
34 #include <utility>
35 
36 namespace std _GLIBCXX_VISIBILITY(default)
37 {
38 namespace __debug
39 {
40  /// Class std::set with safety/checking/debug instrumentation.
41  template<typename _Key, typename _Compare = std::less<_Key>,
42  typename _Allocator = std::allocator<_Key> >
43  class set
44  : public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>,
45  public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
46  {
47  typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;
48 
50  typedef typename _Base::iterator _Base_iterator;
52  public:
53  // types:
54  typedef _Key key_type;
55  typedef _Key value_type;
56  typedef _Compare key_compare;
57  typedef _Compare value_compare;
58  typedef _Allocator allocator_type;
59  typedef typename _Base::reference reference;
60  typedef typename _Base::const_reference const_reference;
61 
63  iterator;
66 
67  typedef typename _Base::size_type size_type;
68  typedef typename _Base::difference_type difference_type;
69  typedef typename _Base::pointer pointer;
70  typedef typename _Base::const_pointer const_pointer;
73 
74  // 23.3.3.1 construct/copy/destroy:
75  explicit set(const _Compare& __comp = _Compare(),
76  const _Allocator& __a = _Allocator())
77  : _Base(__comp, __a) { }
78 
79  template<typename _InputIterator>
80  set(_InputIterator __first, _InputIterator __last,
81  const _Compare& __comp = _Compare(),
82  const _Allocator& __a = _Allocator())
83  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
84  __last)),
85  __gnu_debug::__base(__last),
86  __comp, __a) { }
87 
88  set(const set& __x)
89  : _Base(__x) { }
90 
91  set(const _Base& __x)
92  : _Base(__x) { }
93 
94 #if __cplusplus >= 201103L
95  set(set&& __x)
96  noexcept(is_nothrow_copy_constructible<_Compare>::value)
97  : _Base(std::move(__x))
98  { this->_M_swap(__x); }
99 
101  const _Compare& __comp = _Compare(),
102  const allocator_type& __a = allocator_type())
103  : _Base(__l, __comp, __a) { }
104 #endif
105 
106  ~set() _GLIBCXX_NOEXCEPT { }
107 
108  set&
109  operator=(const set& __x)
110  {
111  *static_cast<_Base*>(this) = __x;
112  this->_M_invalidate_all();
113  return *this;
114  }
115 
116 #if __cplusplus >= 201103L
117  set&
118  operator=(set&& __x)
119  {
120  // NB: DR 1204.
121  // NB: DR 675.
122  __glibcxx_check_self_move_assign(__x);
123  clear();
124  swap(__x);
125  return *this;
126  }
127 
128  set&
129  operator=(initializer_list<value_type> __l)
130  {
131  this->clear();
132  this->insert(__l);
133  return *this;
134  }
135 #endif
136 
137  using _Base::get_allocator;
138 
139  // iterators:
140  iterator
141  begin() _GLIBCXX_NOEXCEPT
142  { return iterator(_Base::begin(), this); }
143 
145  begin() const _GLIBCXX_NOEXCEPT
146  { return const_iterator(_Base::begin(), this); }
147 
148  iterator
149  end() _GLIBCXX_NOEXCEPT
150  { return iterator(_Base::end(), this); }
151 
153  end() const _GLIBCXX_NOEXCEPT
154  { return const_iterator(_Base::end(), this); }
155 
157  rbegin() _GLIBCXX_NOEXCEPT
158  { return reverse_iterator(end()); }
159 
161  rbegin() const _GLIBCXX_NOEXCEPT
162  { return const_reverse_iterator(end()); }
163 
165  rend() _GLIBCXX_NOEXCEPT
166  { return reverse_iterator(begin()); }
167 
169  rend() const _GLIBCXX_NOEXCEPT
170  { return const_reverse_iterator(begin()); }
171 
172 #if __cplusplus >= 201103L
174  cbegin() const noexcept
175  { return const_iterator(_Base::begin(), this); }
176 
178  cend() const noexcept
179  { return const_iterator(_Base::end(), this); }
180 
182  crbegin() const noexcept
183  { return const_reverse_iterator(end()); }
184 
186  crend() const noexcept
187  { return const_reverse_iterator(begin()); }
188 #endif
189 
190  // capacity:
191  using _Base::empty;
192  using _Base::size;
193  using _Base::max_size;
194 
195  // modifiers:
196 #if __cplusplus >= 201103L
197  template<typename... _Args>
199  emplace(_Args&&... __args)
200  {
201  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
202  return std::pair<iterator, bool>(iterator(__res.first, this),
203  __res.second);
204  }
205 
206  template<typename... _Args>
207  iterator
208  emplace_hint(const_iterator __pos, _Args&&... __args)
209  {
210  __glibcxx_check_insert(__pos);
211  return iterator(_Base::emplace_hint(__pos.base(),
212  std::forward<_Args>(__args)...),
213  this);
214  }
215 #endif
216 
218  insert(const value_type& __x)
219  {
220  std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
221  return std::pair<iterator, bool>(iterator(__res.first, this),
222  __res.second);
223  }
224 
225 #if __cplusplus >= 201103L
227  insert(value_type&& __x)
228  {
230  = _Base::insert(std::move(__x));
231  return std::pair<iterator, bool>(iterator(__res.first, this),
232  __res.second);
233  }
234 #endif
235 
236  iterator
237  insert(const_iterator __position, const value_type& __x)
238  {
239  __glibcxx_check_insert(__position);
240  return iterator(_Base::insert(__position.base(), __x), this);
241  }
242 
243 #if __cplusplus >= 201103L
244  iterator
245  insert(const_iterator __position, value_type&& __x)
246  {
247  __glibcxx_check_insert(__position);
248  return iterator(_Base::insert(__position.base(), std::move(__x)),
249  this);
250  }
251 #endif
252 
253  template <typename _InputIterator>
254  void
255  insert(_InputIterator __first, _InputIterator __last)
256  {
257  __glibcxx_check_valid_range(__first, __last);
258  _Base::insert(__gnu_debug::__base(__first),
259  __gnu_debug::__base(__last));
260  }
261 
262 #if __cplusplus >= 201103L
263  void
264  insert(initializer_list<value_type> __l)
265  { _Base::insert(__l); }
266 #endif
267 
268 #if __cplusplus >= 201103L
269  iterator
270  erase(const_iterator __position)
271  {
272  __glibcxx_check_erase(__position);
273  this->_M_invalidate_if(_Equal(__position.base()));
274  return iterator(_Base::erase(__position.base()), this);
275  }
276 #else
277  void
278  erase(iterator __position)
279  {
280  __glibcxx_check_erase(__position);
281  this->_M_invalidate_if(_Equal(__position.base()));
282  _Base::erase(__position.base());
283  }
284 #endif
285 
286  size_type
287  erase(const key_type& __x)
288  {
289  _Base_iterator __victim = _Base::find(__x);
290  if (__victim == _Base::end())
291  return 0;
292  else
293  {
294  this->_M_invalidate_if(_Equal(__victim));
295  _Base::erase(__victim);
296  return 1;
297  }
298  }
299 
300 #if __cplusplus >= 201103L
301  iterator
302  erase(const_iterator __first, const_iterator __last)
303  {
304  // _GLIBCXX_RESOLVE_LIB_DEFECTS
305  // 151. can't currently clear() empty container
306  __glibcxx_check_erase_range(__first, __last);
307  for (_Base_const_iterator __victim = __first.base();
308  __victim != __last.base(); ++__victim)
309  {
310  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
311  _M_message(__gnu_debug::__msg_valid_range)
312  ._M_iterator(__first, "first")
313  ._M_iterator(__last, "last"));
314  this->_M_invalidate_if(_Equal(__victim));
315  }
316  return iterator(_Base::erase(__first.base(), __last.base()), this);
317  }
318 #else
319  void
320  erase(iterator __first, iterator __last)
321  {
322  // _GLIBCXX_RESOLVE_LIB_DEFECTS
323  // 151. can't currently clear() empty container
324  __glibcxx_check_erase_range(__first, __last);
325  for (_Base_iterator __victim = __first.base();
326  __victim != __last.base(); ++__victim)
327  {
328  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
329  _M_message(__gnu_debug::__msg_valid_range)
330  ._M_iterator(__first, "first")
331  ._M_iterator(__last, "last"));
332  this->_M_invalidate_if(_Equal(__victim));
333  }
334  _Base::erase(__first.base(), __last.base());
335  }
336 #endif
337 
338  void
339  swap(set& __x)
340  {
341  _Base::swap(__x);
342  this->_M_swap(__x);
343  }
344 
345  void
346  clear() _GLIBCXX_NOEXCEPT
347  {
348  this->_M_invalidate_all();
349  _Base::clear();
350  }
351 
352  // observers:
353  using _Base::key_comp;
354  using _Base::value_comp;
355 
356  // set operations:
357  iterator
358  find(const key_type& __x)
359  { return iterator(_Base::find(__x), this); }
360 
361  // _GLIBCXX_RESOLVE_LIB_DEFECTS
362  // 214. set::find() missing const overload
364  find(const key_type& __x) const
365  { return const_iterator(_Base::find(__x), this); }
366 
367  using _Base::count;
368 
369  iterator
370  lower_bound(const key_type& __x)
371  { return iterator(_Base::lower_bound(__x), this); }
372 
373  // _GLIBCXX_RESOLVE_LIB_DEFECTS
374  // 214. set::find() missing const overload
376  lower_bound(const key_type& __x) const
377  { return const_iterator(_Base::lower_bound(__x), this); }
378 
379  iterator
380  upper_bound(const key_type& __x)
381  { return iterator(_Base::upper_bound(__x), this); }
382 
383  // _GLIBCXX_RESOLVE_LIB_DEFECTS
384  // 214. set::find() missing const overload
386  upper_bound(const key_type& __x) const
387  { return const_iterator(_Base::upper_bound(__x), this); }
388 
390  equal_range(const key_type& __x)
391  {
393  _Base::equal_range(__x);
394  return std::make_pair(iterator(__res.first, this),
395  iterator(__res.second, this));
396  }
397 
398  // _GLIBCXX_RESOLVE_LIB_DEFECTS
399  // 214. set::find() missing const overload
401  equal_range(const key_type& __x) const
402  {
404  _Base::equal_range(__x);
405  return std::make_pair(const_iterator(__res.first, this),
406  const_iterator(__res.second, this));
407  }
408 
409  _Base&
410  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
411 
412  const _Base&
413  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
414 
415  private:
416  void
417  _M_invalidate_all()
418  {
420  this->_M_invalidate_if(_Not_equal(_M_base().end()));
421  }
422  };
423 
424  template<typename _Key, typename _Compare, typename _Allocator>
425  inline bool
426  operator==(const set<_Key, _Compare, _Allocator>& __lhs,
427  const set<_Key, _Compare, _Allocator>& __rhs)
428  { return __lhs._M_base() == __rhs._M_base(); }
429 
430  template<typename _Key, typename _Compare, typename _Allocator>
431  inline bool
432  operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
433  const set<_Key, _Compare, _Allocator>& __rhs)
434  { return __lhs._M_base() != __rhs._M_base(); }
435 
436  template<typename _Key, typename _Compare, typename _Allocator>
437  inline bool
438  operator<(const set<_Key, _Compare, _Allocator>& __lhs,
439  const set<_Key, _Compare, _Allocator>& __rhs)
440  { return __lhs._M_base() < __rhs._M_base(); }
441 
442  template<typename _Key, typename _Compare, typename _Allocator>
443  inline bool
444  operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
445  const set<_Key, _Compare, _Allocator>& __rhs)
446  { return __lhs._M_base() <= __rhs._M_base(); }
447 
448  template<typename _Key, typename _Compare, typename _Allocator>
449  inline bool
450  operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
451  const set<_Key, _Compare, _Allocator>& __rhs)
452  { return __lhs._M_base() >= __rhs._M_base(); }
453 
454  template<typename _Key, typename _Compare, typename _Allocator>
455  inline bool
456  operator>(const set<_Key, _Compare, _Allocator>& __lhs,
457  const set<_Key, _Compare, _Allocator>& __rhs)
458  { return __lhs._M_base() > __rhs._M_base(); }
459 
460  template<typename _Key, typename _Compare, typename _Allocator>
461  void
462  swap(set<_Key, _Compare, _Allocator>& __x,
463  set<_Key, _Compare, _Allocator>& __y)
464  { return __x.swap(__y); }
465 
466 } // namespace __debug
467 } // namespace std
468 
469 #endif
void _M_swap(_Safe_sequence_base &__x)
_T2 second
first is a copy of the first object
Definition: stl_pair.h:102
#define __glibcxx_check_insert(_Position)
Definition: macros.h:73
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:276
_T1 first
second_type is the second bound type
Definition: stl_pair.h:101
constexpr size_t size() const noexcept
Returns the total number of bits.
Definition: bitset:1293
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
Class std::set with safety/checking/debug instrumentation.
Definition: debug/set.h:43
size_t count() const noexcept
Returns the number of bits which are set.
Definition: bitset:1288
_Iterator base() const noexcept
Return the underlying iterator.
bitset< _Nb > & set() noexcept
Sets every bit to true.
Definition: bitset:1068
#define __glibcxx_check_erase(_Position)
Definition: macros.h:141
void swap(function< _Res(_Args...)> &__x, function< _Res(_Args...)> &__y)
Swap the targets of two polymorphic function object wrappers.
Definition: functional:2534
initializer_list
Base class for constructing a safe sequence type that tracks iterators that reference it...
Definition: formatter.h:52
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
Definition: functions.h:558
Safe iterator wrapper.
Definition: formatter.h:46
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:169
A standard container made up of unique keys, which can be retrieved in logarithmic time...
Definition: stl_set.h:90