libstdc++
debug/unordered_set
Go to the documentation of this file.
1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
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/unordered_set
27  * This file is a GNU debug extension to the Standard C++ Library.
28  */
29 
30 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
31 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
32 
33 #ifndef __GXX_EXPERIMENTAL_CXX0X__
34 # include <bits/c++0x_warning.h>
35 #else
36 # include <unordered_set>
37 
38 #include <debug/safe_sequence.h>
39 #include <debug/safe_iterator.h>
40 
41 namespace std _GLIBCXX_VISIBILITY(default)
42 {
43 namespace __debug
44 {
45  /// Class std::unordered_set with safety/checking/debug instrumentation.
46  template<typename _Value,
47  typename _Hash = std::hash<_Value>,
48  typename _Pred = std::equal_to<_Value>,
49  typename _Alloc = std::allocator<_Value> >
50  class unordered_set
51  : public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>,
52  public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash,
53  _Pred, _Alloc> >
54  {
55  typedef _GLIBCXX_STD_C::unordered_set<_Value, _Hash,
56  _Pred, _Alloc> _Base;
57  typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base;
58  typedef typename _Base::const_iterator _Base_const_iterator;
59  typedef typename _Base::iterator _Base_iterator;
60  typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
61 
62  public:
63  typedef typename _Base::size_type size_type;
64  typedef typename _Base::hasher hasher;
65  typedef typename _Base::key_equal key_equal;
66  typedef typename _Base::allocator_type allocator_type;
67 
68  typedef typename _Base::key_type key_type;
69  typedef typename _Base::value_type value_type;
70 
71  typedef __gnu_debug::_Safe_iterator<_Base_iterator,
72  unordered_set> iterator;
73  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
74  unordered_set> const_iterator;
75 
76  explicit
77  unordered_set(size_type __n = 10,
78  const hasher& __hf = hasher(),
79  const key_equal& __eql = key_equal(),
80  const allocator_type& __a = allocator_type())
81  : _Base(__n, __hf, __eql, __a) { }
82 
83  template<typename _InputIterator>
84  unordered_set(_InputIterator __first, _InputIterator __last,
85  size_type __n = 0,
86  const hasher& __hf = hasher(),
87  const key_equal& __eql = key_equal(),
88  const allocator_type& __a = allocator_type())
89  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
90  __last)),
91  __gnu_debug::__base(__last), __n,
92  __hf, __eql, __a), _Safe_base() { }
93 
94  unordered_set(const unordered_set& __x)
95  : _Base(__x), _Safe_base() { }
96 
97  unordered_set(const _Base& __x)
98  : _Base(__x), _Safe_base() { }
99 
100  unordered_set(unordered_set&& __x)
101  : _Base(std::move(__x)), _Safe_base() { }
102 
103  unordered_set(initializer_list<value_type> __l,
104  size_type __n = 0,
105  const hasher& __hf = hasher(),
106  const key_equal& __eql = key_equal(),
107  const allocator_type& __a = allocator_type())
108  : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
109 
110  unordered_set&
111  operator=(const unordered_set& __x)
112  {
113  *static_cast<_Base*>(this) = __x;
114  this->_M_invalidate_all();
115  return *this;
116  }
117 
118  unordered_set&
119  operator=(unordered_set&& __x)
120  {
121  // NB: DR 1204.
122  // NB: DR 675.
123  clear();
124  swap(__x);
125  return *this;
126  }
127 
128  unordered_set&
129  operator=(initializer_list<value_type> __l)
130  {
131  this->clear();
132  this->insert(__l);
133  return *this;
134  }
135 
136  void
137  swap(unordered_set& __x)
138  {
139  _Base::swap(__x);
140  _Safe_base::_M_swap(__x);
141  }
142 
143  void
144  clear()
145  {
146  _Base::clear();
147  this->_M_invalidate_all();
148  }
149 
150  iterator
151  begin()
152  { return iterator(_Base::begin(), this); }
153 
154  const_iterator
155  begin() const
156  { return const_iterator(_Base::begin(), this); }
157 
158  iterator
159  end()
160  { return iterator(_Base::end(), this); }
161 
162  const_iterator
163  end() const
164  { return const_iterator(_Base::end(), this); }
165 
166  const_iterator
167  cbegin() const
168  { return const_iterator(_Base::begin(), this); }
169 
170  const_iterator
171  cend() const
172  { return const_iterator(_Base::end(), this); }
173 
174  // local versions
175  using _Base::begin;
176  using _Base::end;
177  using _Base::cbegin;
178  using _Base::cend;
179 
180  std::pair<iterator, bool>
181  insert(const value_type& __obj)
182  {
183  typedef std::pair<_Base_iterator, bool> __pair_type;
184  __pair_type __res = _Base::insert(__obj);
185  return std::make_pair(iterator(__res.first, this), __res.second);
186  }
187 
188  iterator
189  insert(const_iterator __hint, const value_type& __obj)
190  {
191  __glibcxx_check_insert(__hint);
192  return iterator(_Base::insert(__hint.base(), __obj), this);
193  }
194 
195  std::pair<iterator, bool>
196  insert(value_type&& __obj)
197  {
198  typedef std::pair<typename _Base::iterator, bool> __pair_type;
199  __pair_type __res = _Base::insert(std::move(__obj));
200  return std::make_pair(iterator(__res.first, this), __res.second);
201  }
202 
203  iterator
204  insert(const_iterator __hint, value_type&& __obj)
205  {
206  __glibcxx_check_insert(__hint);
207  return iterator(_Base::insert(__hint.base(), std::move(__obj)), this);
208  }
209 
210  void
211  insert(std::initializer_list<value_type> __l)
212  { _Base::insert(__l); }
213 
214  template<typename _InputIterator>
215  void
216  insert(_InputIterator __first, _InputIterator __last)
217  {
218  __glibcxx_check_valid_range(__first, __last);
219  _Base::insert(__gnu_debug::__base(__first),
220  __gnu_debug::__base(__last));
221  }
222 
223  iterator
224  find(const key_type& __key)
225  { return iterator(_Base::find(__key), this); }
226 
227  const_iterator
228  find(const key_type& __key) const
229  { return const_iterator(_Base::find(__key), this); }
230 
231  std::pair<iterator, iterator>
232  equal_range(const key_type& __key)
233  {
234  typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
235  __pair_type __res = _Base::equal_range(__key);
236  return std::make_pair(iterator(__res.first, this),
237  iterator(__res.second, this));
238  }
239 
240  std::pair<const_iterator, const_iterator>
241  equal_range(const key_type& __key) const
242  {
243  std::pair<_Base_const_iterator, _Base_const_iterator>
244  __res = _Base::equal_range(__key);
245  return std::make_pair(const_iterator(__res.first, this),
246  const_iterator(__res.second, this));
247  }
248 
249  size_type
250  erase(const key_type& __key)
251  {
252  size_type __ret(0);
253  _Base_iterator __victim(_Base::find(__key));
254  if (__victim != _Base::end())
255  {
256  this->_M_invalidate_if(_Equal(__victim));
257  _Base::erase(__victim);
258  __ret = 1;
259  }
260  return __ret;
261  }
262 
263  iterator
264  erase(const_iterator __it)
265  {
266  __glibcxx_check_erase(__it);
267  this->_M_invalidate_if(_Equal(__it.base()));
268  return iterator(_Base::erase(__it.base()), this);
269  }
270 
271  iterator
272  erase(iterator __it)
273  { return erase(const_iterator(__it)); }
274 
275  iterator
276  erase(const_iterator __first, const_iterator __last)
277  {
278  __glibcxx_check_erase_range(__first, __last);
279  for (_Base_const_iterator __tmp = __first.base();
280  __tmp != __last.base(); ++__tmp)
281  {
282  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
283  _M_message(__gnu_debug::__msg_valid_range)
284  ._M_iterator(__first, "first")
285  ._M_iterator(__last, "last"));
286  this->_M_invalidate_if(_Equal(__tmp));
287  }
288  return iterator(_Base::erase(__first.base(),
289  __last.base()), this);
290  }
291 
292  _Base&
293  _M_base() { return *this; }
294 
295  const _Base&
296  _M_base() const { return *this; }
297 
298  private:
299  void
300  _M_invalidate_all()
301  {
302  typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
303  this->_M_invalidate_if(_Not_equal(_Base::end()));
304  }
305  };
306 
307  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
308  inline void
309  swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
310  unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
311  { __x.swap(__y); }
312 
313  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
314  inline bool
315  operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
316  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
317  { return __x._M_equal(__y); }
318 
319  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
320  inline bool
321  operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
322  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
323  { return !(__x == __y); }
324 
325 
326  /// Class std::unordered_multiset with safety/checking/debug instrumentation.
327  template<typename _Value,
328  typename _Hash = std::hash<_Value>,
329  typename _Pred = std::equal_to<_Value>,
330  typename _Alloc = std::allocator<_Value> >
331  class unordered_multiset
332  : public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
333  public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash,
334  _Pred, _Alloc> >
335  {
336  typedef _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash,
337  _Pred, _Alloc> _Base;
338  typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base;
339  typedef typename _Base::const_iterator _Base_const_iterator;
340  typedef typename _Base::iterator _Base_iterator;
341  typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
342 
343  public:
344  typedef typename _Base::size_type size_type;
345  typedef typename _Base::hasher hasher;
346  typedef typename _Base::key_equal key_equal;
347  typedef typename _Base::allocator_type allocator_type;
348 
349  typedef typename _Base::key_type key_type;
350  typedef typename _Base::value_type value_type;
351 
352  typedef __gnu_debug::_Safe_iterator<_Base_iterator,
353  unordered_multiset> iterator;
354  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
355  unordered_multiset> const_iterator;
356 
357  explicit
358  unordered_multiset(size_type __n = 10,
359  const hasher& __hf = hasher(),
360  const key_equal& __eql = key_equal(),
361  const allocator_type& __a = allocator_type())
362  : _Base(__n, __hf, __eql, __a) { }
363 
364  template<typename _InputIterator>
365  unordered_multiset(_InputIterator __first, _InputIterator __last,
366  size_type __n = 0,
367  const hasher& __hf = hasher(),
368  const key_equal& __eql = key_equal(),
369  const allocator_type& __a = allocator_type())
370  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
371  __last)),
372  __gnu_debug::__base(__last), __n,
373  __hf, __eql, __a), _Safe_base() { }
374 
375  unordered_multiset(const unordered_multiset& __x)
376  : _Base(__x), _Safe_base() { }
377 
378  unordered_multiset(const _Base& __x)
379  : _Base(__x), _Safe_base() { }
380 
381  unordered_multiset(unordered_multiset&& __x)
382  : _Base(std::move(__x)), _Safe_base() { }
383 
384  unordered_multiset(initializer_list<value_type> __l,
385  size_type __n = 0,
386  const hasher& __hf = hasher(),
387  const key_equal& __eql = key_equal(),
388  const allocator_type& __a = allocator_type())
389  : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
390 
391  unordered_multiset&
392  operator=(const unordered_multiset& __x)
393  {
394  *static_cast<_Base*>(this) = __x;
395  this->_M_invalidate_all();
396  return *this;
397  }
398 
399  unordered_multiset&
400  operator=(unordered_multiset&& __x)
401  {
402  // NB: DR 1204.
403  // NB: DR 675.
404  clear();
405  swap(__x);
406  return *this;
407  }
408 
409  unordered_multiset&
410  operator=(initializer_list<value_type> __l)
411  {
412  this->clear();
413  this->insert(__l);
414  return *this;
415  }
416 
417  void
418  swap(unordered_multiset& __x)
419  {
420  _Base::swap(__x);
421  _Safe_base::_M_swap(__x);
422  }
423 
424  void
425  clear()
426  {
427  _Base::clear();
428  this->_M_invalidate_all();
429  }
430 
431  iterator
432  begin()
433  { return iterator(_Base::begin(), this); }
434 
435  const_iterator
436  begin() const
437  { return const_iterator(_Base::begin(), this); }
438 
439  iterator
440  end()
441  { return iterator(_Base::end(), this); }
442 
443  const_iterator
444  end() const
445  { return const_iterator(_Base::end(), this); }
446 
447  const_iterator
448  cbegin() const
449  { return const_iterator(_Base::begin(), this); }
450 
451  const_iterator
452  cend() const
453  { return const_iterator(_Base::end(), this); }
454 
455  // local versions
456  using _Base::begin;
457  using _Base::end;
458  using _Base::cbegin;
459  using _Base::cend;
460 
461  iterator
462  insert(const value_type& __obj)
463  { return iterator(_Base::insert(__obj), this); }
464 
465  iterator
466  insert(const_iterator __hint, const value_type& __obj)
467  {
468  __glibcxx_check_insert(__hint);
469  return iterator(_Base::insert(__hint.base(), __obj), this);
470  }
471 
472  iterator
473  insert(value_type&& __obj)
474  { return iterator(_Base::insert(std::move(__obj)), this); }
475 
476  iterator
477  insert(const_iterator __hint, value_type&& __obj)
478  {
479  __glibcxx_check_insert(__hint);
480  return iterator(_Base::insert(__hint.base(), std::move(__obj)), this);
481  }
482 
483  void
484  insert(std::initializer_list<value_type> __l)
485  { _Base::insert(__l); }
486 
487  template<typename _InputIterator>
488  void
489  insert(_InputIterator __first, _InputIterator __last)
490  {
491  __glibcxx_check_valid_range(__first, __last);
492  _Base::insert(__gnu_debug::__base(__first),
493  __gnu_debug::__base(__last));
494  }
495 
496  iterator
497  find(const key_type& __key)
498  { return iterator(_Base::find(__key), this); }
499 
500  const_iterator
501  find(const key_type& __key) const
502  { return const_iterator(_Base::find(__key), this); }
503 
504  std::pair<iterator, iterator>
505  equal_range(const key_type& __key)
506  {
507  typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
508  __pair_type __res = _Base::equal_range(__key);
509  return std::make_pair(iterator(__res.first, this),
510  iterator(__res.second, this));
511  }
512 
513  std::pair<const_iterator, const_iterator>
514  equal_range(const key_type& __key) const
515  {
516  std::pair<_Base_const_iterator, _Base_const_iterator>
517  __res = _Base::equal_range(__key);
518  return std::make_pair(const_iterator(__res.first, this),
519  const_iterator(__res.second, this));
520  }
521 
522  size_type
523  erase(const key_type& __key)
524  {
525  size_type __ret(0);
526  std::pair<_Base_iterator, _Base_iterator> __pair =
527  _Base::equal_range(__key);
528  for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
529  {
530  this->_M_invalidate_if(_Equal(__victim));
531  _Base::erase(__victim++);
532  ++__ret;
533  }
534  return __ret;
535  }
536 
537  iterator
538  erase(const_iterator __it)
539  {
540  __glibcxx_check_erase(__it);
541  this->_M_invalidate_if(_Equal(__it.base()));
542  return iterator(_Base::erase(__it.base()), this);
543  }
544 
545  iterator
546  erase(iterator __it)
547  { return erase(const_iterator(__it)); }
548 
549  iterator
550  erase(const_iterator __first, const_iterator __last)
551  {
552  __glibcxx_check_erase_range(__first, __last);
553  for (_Base_const_iterator __tmp = __first.base();
554  __tmp != __last.base(); ++__tmp)
555  {
556  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
557  _M_message(__gnu_debug::__msg_valid_range)
558  ._M_iterator(__first, "first")
559  ._M_iterator(__last, "last"));
560  this->_M_invalidate_if(_Equal(__tmp));
561  }
562  return iterator(_Base::erase(__first.base(),
563  __last.base()), this);
564  }
565 
566  _Base&
567  _M_base() { return *this; }
568 
569  const _Base&
570  _M_base() const { return *this; }
571 
572  private:
573  void
574  _M_invalidate_all()
575  {
576  typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
577  this->_M_invalidate_if(_Not_equal(_Base::end()));
578  }
579  };
580 
581  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
582  inline void
583  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
584  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
585  { __x.swap(__y); }
586 
587  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
588  inline bool
589  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
590  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
591  { return __x._M_equal(__y); }
592 
593  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
594  inline bool
595  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
596  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
597  { return !(__x == __y); }
598 
599 } // namespace __debug
600 } // namespace std
601 
602 #endif // __GXX_EXPERIMENTAL_CXX0X__
603 
604 #endif
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:87
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:92
__gnu_debug::_Safe_sequence_base::_M_swap
void _M_swap(_Safe_sequence_base &__x)
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition: macros.h:64
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition: formatter.h:47
__gnu_debug::__base
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
Definition: safe_iterator.h:724
std::equal_to
One of the comparison functors.
Definition: stl_function.h:205
std::hash
Primary class template hash.
Definition: system_error:112
std::make_pair
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:262
std::__debug::unordered_set
Class std::unordered_set with safety/checking/debug instrumentation.
Definition: debug/unordered_set:50
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition: macros.h:126
std::initializer_list
initializer_list
Definition: initializer_list:45
std::unordered_set
A standard container composed of unique keys (containing at most one of each key value) in which the ...
Definition: unordered_set.h:249
__gnu_debug::_Safe_sequence
Base class for constructing a safe sequence type that tracks iterators that reference it...
Definition: formatter.h:50
_GLIBCXX_DEBUG_VERIFY
#define _GLIBCXX_DEBUG_VERIFY(_Condition, _ErrorMessage)
Definition: macros.h:42
__gnu_debug::_Safe_iterator::base
_Iterator base() const
Return the underlying iterator.
Definition: safe_iterator.h:364
std::__debug::unordered_multiset
Class std::unordered_multiset with safety/checking/debug instrumentation.
Definition: debug/unordered_set:331
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:154
std::allocator
The standard allocator, as per [20.4].Further details: http://gcc.gnu.org/onlinedocs/libstdc++/manual...
Definition: allocator.h:66
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:93
std::unordered_multiset
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
Definition: unordered_set.h:314