libstdc++
debug/set.h
Go to the documentation of this file.
1 // Debugging set implementation -*- C++ -*-
2 
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /** @file debug/set.h
27  * This file is a GNU debug extension to the Standard C++ Library.
28  */
29 
30 #ifndef _GLIBCXX_DEBUG_SET_H
31 #define _GLIBCXX_DEBUG_SET_H 1
32 
33 #include <debug/safe_sequence.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 _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>,
46  public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
47  {
48  typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;
49 
50  typedef typename _Base::const_iterator _Base_const_iterator;
51  typedef typename _Base::iterator _Base_iterator;
52  typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
53  public:
54  // types:
55  typedef _Key key_type;
56  typedef _Key value_type;
57  typedef _Compare key_compare;
58  typedef _Compare value_compare;
59  typedef _Allocator allocator_type;
60  typedef typename _Base::reference reference;
61  typedef typename _Base::const_reference const_reference;
62 
63  typedef __gnu_debug::_Safe_iterator<_Base_iterator, set>
64  iterator;
65  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set>
66  const_iterator;
67 
68  typedef typename _Base::size_type size_type;
69  typedef typename _Base::difference_type difference_type;
70  typedef typename _Base::pointer pointer;
71  typedef typename _Base::const_pointer const_pointer;
72  typedef std::reverse_iterator<iterator> reverse_iterator;
73  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
74 
75  // 23.3.3.1 construct/copy/destroy:
76  explicit set(const _Compare& __comp = _Compare(),
77  const _Allocator& __a = _Allocator())
78  : _Base(__comp, __a) { }
79 
80  template<typename _InputIterator>
81  set(_InputIterator __first, _InputIterator __last,
82  const _Compare& __comp = _Compare(),
83  const _Allocator& __a = _Allocator())
84  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
85  __last)),
86  __gnu_debug::__base(__last),
87  __comp, __a) { }
88 
89  set(const set& __x)
90  : _Base(__x) { }
91 
92  set(const _Base& __x)
93  : _Base(__x) { }
94 
95 #ifdef __GXX_EXPERIMENTAL_CXX0X__
96  set(set&& __x)
97  noexcept(is_nothrow_copy_constructible<_Compare>::value)
98  : _Base(std::move(__x))
99  { this->_M_swap(__x); }
100 
101  set(initializer_list<value_type> __l,
102  const _Compare& __comp = _Compare(),
103  const allocator_type& __a = allocator_type())
104  : _Base(__l, __comp, __a) { }
105 #endif
106 
107  ~set() _GLIBCXX_NOEXCEPT { }
108 
109  set&
110  operator=(const set& __x)
111  {
112  *static_cast<_Base*>(this) = __x;
113  this->_M_invalidate_all();
114  return *this;
115  }
116 
117 #ifdef __GXX_EXPERIMENTAL_CXX0X__
118  set&
119  operator=(set&& __x)
120  {
121  // NB: DR 1204.
122  // NB: DR 675.
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 
144  const_iterator
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 
152  const_iterator
153  end() const _GLIBCXX_NOEXCEPT
154  { return const_iterator(_Base::end(), this); }
155 
156  reverse_iterator
157  rbegin() _GLIBCXX_NOEXCEPT
158  { return reverse_iterator(end()); }
159 
160  const_reverse_iterator
161  rbegin() const _GLIBCXX_NOEXCEPT
162  { return const_reverse_iterator(end()); }
163 
164  reverse_iterator
165  rend() _GLIBCXX_NOEXCEPT
166  { return reverse_iterator(begin()); }
167 
168  const_reverse_iterator
169  rend() const _GLIBCXX_NOEXCEPT
170  { return const_reverse_iterator(begin()); }
171 
172 #ifdef __GXX_EXPERIMENTAL_CXX0X__
173  const_iterator
174  cbegin() const noexcept
175  { return const_iterator(_Base::begin(), this); }
176 
177  const_iterator
178  cend() const noexcept
179  { return const_iterator(_Base::end(), this); }
180 
181  const_reverse_iterator
182  crbegin() const noexcept
183  { return const_reverse_iterator(end()); }
184 
185  const_reverse_iterator
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  std::pair<iterator, bool>
197  insert(const value_type& __x)
198  {
199  std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
200  return std::pair<iterator, bool>(iterator(__res.first, this),
201  __res.second);
202  }
203 
204 #ifdef __GXX_EXPERIMENTAL_CXX0X__
205  std::pair<iterator, bool>
206  insert(value_type&& __x)
207  {
208  std::pair<_Base_iterator, bool> __res
209  = _Base::insert(std::move(__x));
210  return std::pair<iterator, bool>(iterator(__res.first, this),
211  __res.second);
212  }
213 #endif
214 
215  iterator
216  insert(const_iterator __position, const value_type& __x)
217  {
218  __glibcxx_check_insert(__position);
219  return iterator(_Base::insert(__position.base(), __x), this);
220  }
221 
222 #ifdef __GXX_EXPERIMENTAL_CXX0X__
223  iterator
224  insert(const_iterator __position, value_type&& __x)
225  {
226  __glibcxx_check_insert(__position);
227  return iterator(_Base::insert(__position.base(), std::move(__x)),
228  this);
229  }
230 #endif
231 
232  template <typename _InputIterator>
233  void
234  insert(_InputIterator __first, _InputIterator __last)
235  {
236  __glibcxx_check_valid_range(__first, __last);
237  _Base::insert(__gnu_debug::__base(__first),
238  __gnu_debug::__base(__last));
239  }
240 
241 #ifdef __GXX_EXPERIMENTAL_CXX0X__
242  void
243  insert(initializer_list<value_type> __l)
244  { _Base::insert(__l); }
245 #endif
246 
247 #ifdef __GXX_EXPERIMENTAL_CXX0X__
248  iterator
249  erase(const_iterator __position)
250  {
251  __glibcxx_check_erase(__position);
252  this->_M_invalidate_if(_Equal(__position.base()));
253  return iterator(_Base::erase(__position.base()), this);
254  }
255 #else
256  void
257  erase(iterator __position)
258  {
259  __glibcxx_check_erase(__position);
260  this->_M_invalidate_if(_Equal(__position.base()));
261  _Base::erase(__position.base());
262  }
263 #endif
264 
265  size_type
266  erase(const key_type& __x)
267  {
268  _Base_iterator __victim = _Base::find(__x);
269  if (__victim == _Base::end())
270  return 0;
271  else
272  {
273  this->_M_invalidate_if(_Equal(__victim));
274  _Base::erase(__victim);
275  return 1;
276  }
277  }
278 
279 #ifdef __GXX_EXPERIMENTAL_CXX0X__
280  iterator
281  erase(const_iterator __first, const_iterator __last)
282  {
283  // _GLIBCXX_RESOLVE_LIB_DEFECTS
284  // 151. can't currently clear() empty container
285  __glibcxx_check_erase_range(__first, __last);
286  for (_Base_const_iterator __victim = __first.base();
287  __victim != __last.base(); ++__victim)
288  {
289  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
290  _M_message(__gnu_debug::__msg_valid_range)
291  ._M_iterator(__first, "first")
292  ._M_iterator(__last, "last"));
293  this->_M_invalidate_if(_Equal(__victim));
294  }
295  return iterator(_Base::erase(__first.base(), __last.base()), this);
296  }
297 #else
298  void
299  erase(iterator __first, iterator __last)
300  {
301  // _GLIBCXX_RESOLVE_LIB_DEFECTS
302  // 151. can't currently clear() empty container
303  __glibcxx_check_erase_range(__first, __last);
304  for (_Base_iterator __victim = __first.base();
305  __victim != __last.base(); ++__victim)
306  {
307  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
308  _M_message(__gnu_debug::__msg_valid_range)
309  ._M_iterator(__first, "first")
310  ._M_iterator(__last, "last"));
311  this->_M_invalidate_if(_Equal(__victim));
312  }
313  _Base::erase(__first.base(), __last.base());
314  }
315 #endif
316 
317  void
318  swap(set& __x)
319  {
320  _Base::swap(__x);
321  this->_M_swap(__x);
322  }
323 
324  void
325  clear() _GLIBCXX_NOEXCEPT
326  {
327  this->_M_invalidate_all();
328  _Base::clear();
329  }
330 
331  // observers:
332  using _Base::key_comp;
333  using _Base::value_comp;
334 
335  // set operations:
336  iterator
337  find(const key_type& __x)
338  { return iterator(_Base::find(__x), this); }
339 
340  // _GLIBCXX_RESOLVE_LIB_DEFECTS
341  // 214. set::find() missing const overload
342  const_iterator
343  find(const key_type& __x) const
344  { return const_iterator(_Base::find(__x), this); }
345 
346  using _Base::count;
347 
348  iterator
349  lower_bound(const key_type& __x)
350  { return iterator(_Base::lower_bound(__x), this); }
351 
352  // _GLIBCXX_RESOLVE_LIB_DEFECTS
353  // 214. set::find() missing const overload
354  const_iterator
355  lower_bound(const key_type& __x) const
356  { return const_iterator(_Base::lower_bound(__x), this); }
357 
358  iterator
359  upper_bound(const key_type& __x)
360  { return iterator(_Base::upper_bound(__x), this); }
361 
362  // _GLIBCXX_RESOLVE_LIB_DEFECTS
363  // 214. set::find() missing const overload
364  const_iterator
365  upper_bound(const key_type& __x) const
366  { return const_iterator(_Base::upper_bound(__x), this); }
367 
368  std::pair<iterator,iterator>
369  equal_range(const key_type& __x)
370  {
371  std::pair<_Base_iterator, _Base_iterator> __res =
372  _Base::equal_range(__x);
373  return std::make_pair(iterator(__res.first, this),
374  iterator(__res.second, this));
375  }
376 
377  // _GLIBCXX_RESOLVE_LIB_DEFECTS
378  // 214. set::find() missing const overload
379  std::pair<const_iterator,const_iterator>
380  equal_range(const key_type& __x) const
381  {
382  std::pair<_Base_iterator, _Base_iterator> __res =
383  _Base::equal_range(__x);
384  return std::make_pair(const_iterator(__res.first, this),
385  const_iterator(__res.second, this));
386  }
387 
388  _Base&
389  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
390 
391  const _Base&
392  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
393 
394  private:
395  void
396  _M_invalidate_all()
397  {
398  typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
399  this->_M_invalidate_if(_Not_equal(_M_base().end()));
400  }
401  };
402 
403  template<typename _Key, typename _Compare, typename _Allocator>
404  inline bool
405  operator==(const set<_Key, _Compare, _Allocator>& __lhs,
406  const set<_Key, _Compare, _Allocator>& __rhs)
407  { return __lhs._M_base() == __rhs._M_base(); }
408 
409  template<typename _Key, typename _Compare, typename _Allocator>
410  inline bool
411  operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
412  const set<_Key, _Compare, _Allocator>& __rhs)
413  { return __lhs._M_base() != __rhs._M_base(); }
414 
415  template<typename _Key, typename _Compare, typename _Allocator>
416  inline bool
417  operator<(const set<_Key, _Compare, _Allocator>& __lhs,
418  const set<_Key, _Compare, _Allocator>& __rhs)
419  { return __lhs._M_base() < __rhs._M_base(); }
420 
421  template<typename _Key, typename _Compare, typename _Allocator>
422  inline bool
423  operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
424  const set<_Key, _Compare, _Allocator>& __rhs)
425  { return __lhs._M_base() <= __rhs._M_base(); }
426 
427  template<typename _Key, typename _Compare, typename _Allocator>
428  inline bool
429  operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
430  const set<_Key, _Compare, _Allocator>& __rhs)
431  { return __lhs._M_base() >= __rhs._M_base(); }
432 
433  template<typename _Key, typename _Compare, typename _Allocator>
434  inline bool
435  operator>(const set<_Key, _Compare, _Allocator>& __lhs,
436  const set<_Key, _Compare, _Allocator>& __rhs)
437  { return __lhs._M_base() > __rhs._M_base(); }
438 
439  template<typename _Key, typename _Compare, typename _Allocator>
440  void
441  swap(set<_Key, _Compare, _Allocator>& __x,
442  set<_Key, _Compare, _Allocator>& __y)
443  { return __x.swap(__y); }
444 
445 } // namespace __debug
446 } // namespace std
447 
448 #endif