libstdc++
debug/set.h
Go to the documentation of this file.
1 // Debugging set implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2015 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 
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>
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  {
283  __glibcxx_check_valid_range(__first, __last);
284  _Base::insert(__gnu_debug::__base(__first),
285  __gnu_debug::__base(__last));
286  }
287 
288 #if __cplusplus >= 201103L
289  void
290  insert(initializer_list<value_type> __l)
291  { _Base::insert(__l); }
292 #endif
293 
294 #if __cplusplus >= 201103L
295  iterator
296  erase(const_iterator __position)
297  {
298  __glibcxx_check_erase(__position);
299  this->_M_invalidate_if(_Equal(__position.base()));
300  return iterator(_Base::erase(__position.base()), this);
301  }
302 #else
303  void
304  erase(iterator __position)
305  {
306  __glibcxx_check_erase(__position);
307  this->_M_invalidate_if(_Equal(__position.base()));
308  _Base::erase(__position.base());
309  }
310 #endif
311 
312  size_type
313  erase(const key_type& __x)
314  {
315  _Base_iterator __victim = _Base::find(__x);
316  if (__victim == _Base::end())
317  return 0;
318  else
319  {
320  this->_M_invalidate_if(_Equal(__victim));
321  _Base::erase(__victim);
322  return 1;
323  }
324  }
325 
326 #if __cplusplus >= 201103L
327  iterator
328  erase(const_iterator __first, const_iterator __last)
329  {
330  // _GLIBCXX_RESOLVE_LIB_DEFECTS
331  // 151. can't currently clear() empty container
332  __glibcxx_check_erase_range(__first, __last);
333  for (_Base_const_iterator __victim = __first.base();
334  __victim != __last.base(); ++__victim)
335  {
336  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
337  _M_message(__gnu_debug::__msg_valid_range)
338  ._M_iterator(__first, "first")
339  ._M_iterator(__last, "last"));
340  this->_M_invalidate_if(_Equal(__victim));
341  }
342  return iterator(_Base::erase(__first.base(), __last.base()), this);
343  }
344 #else
345  void
346  erase(iterator __first, iterator __last)
347  {
348  // _GLIBCXX_RESOLVE_LIB_DEFECTS
349  // 151. can't currently clear() empty container
350  __glibcxx_check_erase_range(__first, __last);
351  for (_Base_iterator __victim = __first.base();
352  __victim != __last.base(); ++__victim)
353  {
354  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
355  _M_message(__gnu_debug::__msg_valid_range)
356  ._M_iterator(__first, "first")
357  ._M_iterator(__last, "last"));
358  this->_M_invalidate_if(_Equal(__victim));
359  }
360  _Base::erase(__first.base(), __last.base());
361  }
362 #endif
363 
364  void
365  swap(set& __x)
366 #if __cplusplus >= 201103L
367  noexcept( noexcept(declval<_Base>().swap(__x)) )
368 #endif
369  {
370  _Safe::_M_swap(__x);
371  _Base::swap(__x);
372  }
373 
374  void
375  clear() _GLIBCXX_NOEXCEPT
376  {
377  this->_M_invalidate_all();
378  _Base::clear();
379  }
380 
381  // observers:
382  using _Base::key_comp;
383  using _Base::value_comp;
384 
385  // set operations:
386  iterator
387  find(const key_type& __x)
388  { return iterator(_Base::find(__x), this); }
389 
390  // _GLIBCXX_RESOLVE_LIB_DEFECTS
391  // 214. set::find() missing const overload
392  const_iterator
393  find(const key_type& __x) const
394  { return const_iterator(_Base::find(__x), this); }
395 
396  using _Base::count;
397 
398  iterator
399  lower_bound(const key_type& __x)
400  { return iterator(_Base::lower_bound(__x), this); }
401 
402  // _GLIBCXX_RESOLVE_LIB_DEFECTS
403  // 214. set::find() missing const overload
404  const_iterator
405  lower_bound(const key_type& __x) const
406  { return const_iterator(_Base::lower_bound(__x), this); }
407 
408  iterator
409  upper_bound(const key_type& __x)
410  { return iterator(_Base::upper_bound(__x), this); }
411 
412  // _GLIBCXX_RESOLVE_LIB_DEFECTS
413  // 214. set::find() missing const overload
414  const_iterator
415  upper_bound(const key_type& __x) const
416  { return const_iterator(_Base::upper_bound(__x), this); }
417 
419  equal_range(const key_type& __x)
420  {
422  _Base::equal_range(__x);
423  return std::make_pair(iterator(__res.first, this),
424  iterator(__res.second, this));
425  }
426 
427  // _GLIBCXX_RESOLVE_LIB_DEFECTS
428  // 214. set::find() missing const overload
430  equal_range(const key_type& __x) const
431  {
433  _Base::equal_range(__x);
434  return std::make_pair(const_iterator(__res.first, this),
435  const_iterator(__res.second, this));
436  }
437 
438  _Base&
439  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
440 
441  const _Base&
442  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
443  };
444 
445  template<typename _Key, typename _Compare, typename _Allocator>
446  inline bool
447  operator==(const set<_Key, _Compare, _Allocator>& __lhs,
448  const set<_Key, _Compare, _Allocator>& __rhs)
449  { return __lhs._M_base() == __rhs._M_base(); }
450 
451  template<typename _Key, typename _Compare, typename _Allocator>
452  inline bool
453  operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
454  const set<_Key, _Compare, _Allocator>& __rhs)
455  { return __lhs._M_base() != __rhs._M_base(); }
456 
457  template<typename _Key, typename _Compare, typename _Allocator>
458  inline bool
459  operator<(const set<_Key, _Compare, _Allocator>& __lhs,
460  const set<_Key, _Compare, _Allocator>& __rhs)
461  { return __lhs._M_base() < __rhs._M_base(); }
462 
463  template<typename _Key, typename _Compare, typename _Allocator>
464  inline bool
465  operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
466  const set<_Key, _Compare, _Allocator>& __rhs)
467  { return __lhs._M_base() <= __rhs._M_base(); }
468 
469  template<typename _Key, typename _Compare, typename _Allocator>
470  inline bool
471  operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
472  const set<_Key, _Compare, _Allocator>& __rhs)
473  { return __lhs._M_base() >= __rhs._M_base(); }
474 
475  template<typename _Key, typename _Compare, typename _Allocator>
476  inline bool
477  operator>(const set<_Key, _Compare, _Allocator>& __lhs,
478  const set<_Key, _Compare, _Allocator>& __rhs)
479  { return __lhs._M_base() > __rhs._M_base(); }
480 
481  template<typename _Key, typename _Compare, typename _Allocator>
482  void
485  { return __x.swap(__y); }
486 
487 } // namespace __debug
488 } // namespace std
489 
490 #endif
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: debug/set.h:44
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
_Iterator & base() noexcept
Return the underlying iterator.
#define __glibcxx_check_erase(_Position)
Definition: macros.h:139
Safe class dealing with some allocator dependent operations.
initializer_list
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:167
_T2 second
first is a copy of the first object
Definition: stl_pair.h:102
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
Definition: functions.h:558
Safe iterator wrapper.
Definition: formatter.h:46
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
_T1 first
second_type is the second bound type
Definition: stl_pair.h:101
ISO C++ entities toplevel namespace is std.
#define __glibcxx_check_insert(_Position)
Definition: macros.h:73