libstdc++
debug/unordered_map
Go to the documentation of this file.
1 // Debugging unordered_map/unordered_multimap 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_map
27  * This file is a GNU debug extension to the Standard C++ Library.
28  */
29 
30 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
31 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
32 
33 #ifndef __GXX_EXPERIMENTAL_CXX0X__
34 # include <bits/c++0x_warning.h>
35 #else
36 # include <unordered_map>
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_map with safety/checking/debug instrumentation.
46  template<typename _Key, typename _Tp,
47  typename _Hash = std::hash<_Key>,
48  typename _Pred = std::equal_to<_Key>,
49  typename _Alloc = std::allocator<_Key> >
50  class unordered_map
51  : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
52  public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash,
53  _Pred, _Alloc> >
54  {
55  typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
56  _Pred, _Alloc> _Base;
57  typedef __gnu_debug::_Safe_sequence<unordered_map> _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_map> iterator;
73  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
74  unordered_map> const_iterator;
75 
76  explicit
77  unordered_map(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_map(_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_map(const unordered_map& __x)
95  : _Base(__x), _Safe_base() { }
96 
97  unordered_map(const _Base& __x)
98  : _Base(__x), _Safe_base() { }
99 
100  unordered_map(unordered_map&& __x)
101  : _Base(std::move(__x)), _Safe_base() { }
102 
103  unordered_map(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_map&
111  operator=(const unordered_map& __x)
112  {
113  *static_cast<_Base*>(this) = __x;
114  this->_M_invalidate_all();
115  return *this;
116  }
117 
118  unordered_map&
119  operator=(unordered_map&& __x)
120  {
121  // NB: DR 1204.
122  // NB: DR 675.
123  clear();
124  swap(__x);
125  return *this;
126  }
127 
128  unordered_map&
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_map& __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  std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
184  return std::make_pair(iterator(__res.first, this), __res.second);
185  }
186 
187  iterator
188  insert(const_iterator __hint, const value_type& __obj)
189  {
190  __glibcxx_check_insert(__hint);
191  return iterator(_Base::insert(__hint.base(), __obj), this);
192  }
193 
194  template<typename _Pair, typename = typename
195  std::enable_if<std::is_convertible<_Pair,
196  value_type>::value>::type>
197  std::pair<iterator, bool>
198  insert(_Pair&& __obj)
199  {
200  std::pair<_Base_iterator, bool> __res =
201  _Base::insert(std::forward<_Pair>(__obj));
202  return std::make_pair(iterator(__res.first, this), __res.second);
203  }
204 
205  template<typename _Pair, typename = typename
206  std::enable_if<std::is_convertible<_Pair,
207  value_type>::value>::type>
208  iterator
209  insert(const_iterator __hint, _Pair&& __obj)
210  {
211  __glibcxx_check_insert(__hint);
212  return iterator(_Base::insert(__hint.base(),
213  std::forward<_Pair>(__obj)),
214  this);
215  }
216 
217  void
218  insert(std::initializer_list<value_type> __l)
219  { _Base::insert(__l); }
220 
221  template<typename _InputIterator>
222  void
223  insert(_InputIterator __first, _InputIterator __last)
224  {
225  __glibcxx_check_valid_range(__first, __last);
226  _Base::insert(__gnu_debug::__base(__first),
227  __gnu_debug::__base(__last));
228  }
229 
230  iterator
231  find(const key_type& __key)
232  { return iterator(_Base::find(__key), this); }
233 
234  const_iterator
235  find(const key_type& __key) const
236  { return const_iterator(_Base::find(__key), this); }
237 
238  std::pair<iterator, iterator>
239  equal_range(const key_type& __key)
240  {
241  std::pair<_Base_iterator, _Base_iterator> __res =
242  _Base::equal_range(__key);
243  return std::make_pair(iterator(__res.first, this),
244  iterator(__res.second, this));
245  }
246 
247  std::pair<const_iterator, const_iterator>
248  equal_range(const key_type& __key) const
249  {
250  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
251  _Base::equal_range(__key);
252  return std::make_pair(const_iterator(__res.first, this),
253  const_iterator(__res.second, this));
254  }
255 
256  size_type
257  erase(const key_type& __key)
258  {
259  size_type __ret(0);
260  _Base_iterator __victim(_Base::find(__key));
261  if (__victim != _Base::end())
262  {
263  this->_M_invalidate_if(_Equal(__victim));
264  _Base::erase(__victim);
265  __ret = 1;
266  }
267  return __ret;
268  }
269 
270  iterator
271  erase(const_iterator __it)
272  {
273  __glibcxx_check_erase(__it);
274  this->_M_invalidate_if(_Equal(__it.base()));
275  return iterator(_Base::erase(__it.base()), this);
276  }
277 
278  iterator
279  erase(iterator __it)
280  { return erase(const_iterator(__it)); }
281 
282  iterator
283  erase(const_iterator __first, const_iterator __last)
284  {
285  __glibcxx_check_erase_range(__first, __last);
286  for (_Base_const_iterator __tmp = __first.base();
287  __tmp != __last.base(); ++__tmp)
288  {
289  _GLIBCXX_DEBUG_VERIFY(__tmp != _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(__tmp));
294  }
295  return iterator(_Base::erase(__first.base(),
296  __last.base()), this);
297  }
298 
299  _Base&
300  _M_base() { return *this; }
301 
302  const _Base&
303  _M_base() const { return *this; }
304 
305  private:
306  void
307  _M_invalidate_all()
308  {
309  typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
310  this->_M_invalidate_if(_Not_equal(_Base::end()));
311  }
312  };
313 
314  template<typename _Key, typename _Tp, typename _Hash,
315  typename _Pred, typename _Alloc>
316  inline void
317  swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
318  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
319  { __x.swap(__y); }
320 
321  template<typename _Key, typename _Tp, typename _Hash,
322  typename _Pred, typename _Alloc>
323  inline bool
324  operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
325  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
326  { return __x._M_equal(__y); }
327 
328  template<typename _Key, typename _Tp, typename _Hash,
329  typename _Pred, typename _Alloc>
330  inline bool
331  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
332  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
333  { return !(__x == __y); }
334 
335 
336  /// Class std::unordered_multimap with safety/checking/debug instrumentation.
337  template<typename _Key, typename _Tp,
338  typename _Hash = std::hash<_Key>,
339  typename _Pred = std::equal_to<_Key>,
340  typename _Alloc = std::allocator<_Key> >
341  class unordered_multimap
342  : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
343  _Pred, _Alloc>,
344  public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,
345  _Pred, _Alloc> >
346  {
347  typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
348  _Pred, _Alloc> _Base;
349  typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base;
350  typedef typename _Base::const_iterator _Base_const_iterator;
351  typedef typename _Base::iterator _Base_iterator;
352  typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
353 
354  public:
355  typedef typename _Base::size_type size_type;
356  typedef typename _Base::hasher hasher;
357  typedef typename _Base::key_equal key_equal;
358  typedef typename _Base::allocator_type allocator_type;
359 
360  typedef typename _Base::key_type key_type;
361  typedef typename _Base::value_type value_type;
362 
363  typedef __gnu_debug::_Safe_iterator<_Base_iterator,
364  unordered_multimap> iterator;
365  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
366  unordered_multimap> const_iterator;
367 
368  explicit
369  unordered_multimap(size_type __n = 10,
370  const hasher& __hf = hasher(),
371  const key_equal& __eql = key_equal(),
372  const allocator_type& __a = allocator_type())
373  : _Base(__n, __hf, __eql, __a) { }
374 
375  template<typename _InputIterator>
376  unordered_multimap(_InputIterator __first, _InputIterator __last,
377  size_type __n = 0,
378  const hasher& __hf = hasher(),
379  const key_equal& __eql = key_equal(),
380  const allocator_type& __a = allocator_type())
381  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
382  __last)),
383  __gnu_debug::__base(__last), __n,
384  __hf, __eql, __a), _Safe_base() { }
385 
386  unordered_multimap(const unordered_multimap& __x)
387  : _Base(__x), _Safe_base() { }
388 
389  unordered_multimap(const _Base& __x)
390  : _Base(__x), _Safe_base() { }
391 
392  unordered_multimap(unordered_multimap&& __x)
393  : _Base(std::move(__x)), _Safe_base() { }
394 
395  unordered_multimap(initializer_list<value_type> __l,
396  size_type __n = 0,
397  const hasher& __hf = hasher(),
398  const key_equal& __eql = key_equal(),
399  const allocator_type& __a = allocator_type())
400  : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
401 
402  unordered_multimap&
403  operator=(const unordered_multimap& __x)
404  {
405  *static_cast<_Base*>(this) = __x;
406  this->_M_invalidate_all();
407  return *this;
408  }
409 
410  unordered_multimap&
411  operator=(unordered_multimap&& __x)
412  {
413  // NB: DR 1204.
414  // NB: DR 675.
415  clear();
416  swap(__x);
417  return *this;
418  }
419 
420  unordered_multimap&
421  operator=(initializer_list<value_type> __l)
422  {
423  this->clear();
424  this->insert(__l);
425  return *this;
426  }
427 
428  void
429  swap(unordered_multimap& __x)
430  {
431  _Base::swap(__x);
432  _Safe_base::_M_swap(__x);
433  }
434 
435  void
436  clear()
437  {
438  _Base::clear();
439  this->_M_invalidate_all();
440  }
441 
442  iterator
443  begin()
444  { return iterator(_Base::begin(), this); }
445 
446  const_iterator
447  begin() const
448  { return const_iterator(_Base::begin(), this); }
449 
450  iterator
451  end()
452  { return iterator(_Base::end(), this); }
453 
454  const_iterator
455  end() const
456  { return const_iterator(_Base::end(), this); }
457 
458  const_iterator
459  cbegin() const
460  { return const_iterator(_Base::begin(), this); }
461 
462  const_iterator
463  cend() const
464  { return const_iterator(_Base::end(), this); }
465 
466  // local versions
467  using _Base::begin;
468  using _Base::end;
469  using _Base::cbegin;
470  using _Base::cend;
471 
472  iterator
473  insert(const value_type& __obj)
474  { return iterator(_Base::insert(__obj), this); }
475 
476  iterator
477  insert(const_iterator __hint, const value_type& __obj)
478  {
479  __glibcxx_check_insert(__hint);
480  return iterator(_Base::insert(__hint.base(), __obj), this);
481  }
482 
483  template<typename _Pair, typename = typename
484  std::enable_if<std::is_convertible<_Pair,
485  value_type>::value>::type>
486  iterator
487  insert(_Pair&& __obj)
488  { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); }
489 
490  template<typename _Pair, typename = typename
491  std::enable_if<std::is_convertible<_Pair,
492  value_type>::value>::type>
493  iterator
494  insert(const_iterator __hint, _Pair&& __obj)
495  {
496  __glibcxx_check_insert(__hint);
497  return iterator(_Base::insert(__hint.base(),
498  std::forward<_Pair>(__obj)),
499  this);
500  }
501 
502  void
503  insert(std::initializer_list<value_type> __l)
504  { _Base::insert(__l); }
505 
506  template<typename _InputIterator>
507  void
508  insert(_InputIterator __first, _InputIterator __last)
509  {
510  __glibcxx_check_valid_range(__first, __last);
511  _Base::insert(__gnu_debug::__base(__first),
512  __gnu_debug::__base(__last));
513  }
514 
515  iterator
516  find(const key_type& __key)
517  { return iterator(_Base::find(__key), this); }
518 
519  const_iterator
520  find(const key_type& __key) const
521  { return const_iterator(_Base::find(__key), this); }
522 
523  std::pair<iterator, iterator>
524  equal_range(const key_type& __key)
525  {
526  std::pair<_Base_iterator, _Base_iterator> __res =
527  _Base::equal_range(__key);
528  return std::make_pair(iterator(__res.first, this),
529  iterator(__res.second, this));
530  }
531 
532  std::pair<const_iterator, const_iterator>
533  equal_range(const key_type& __key) const
534  {
535  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
536  _Base::equal_range(__key);
537  return std::make_pair(const_iterator(__res.first, this),
538  const_iterator(__res.second, this));
539  }
540 
541  size_type
542  erase(const key_type& __key)
543  {
544  size_type __ret(0);
545  std::pair<_Base_iterator, _Base_iterator> __pair =
546  _Base::equal_range(__key);
547  for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
548  {
549  this->_M_invalidate_if(_Equal(__victim));
550  _Base::erase(__victim++);
551  ++__ret;
552  }
553  return __ret;
554  }
555 
556  iterator
557  erase(const_iterator __it)
558  {
559  __glibcxx_check_erase(__it);
560  this->_M_invalidate_if(_Equal(__it.base()));
561  return iterator(_Base::erase(__it.base()), this);
562  }
563 
564  iterator
565  erase(iterator __it)
566  { return erase(const_iterator(__it)); }
567 
568  iterator
569  erase(const_iterator __first, const_iterator __last)
570  {
571  __glibcxx_check_erase_range(__first, __last);
572  for (_Base_const_iterator __tmp = __first.base();
573  __tmp != __last.base(); ++__tmp)
574  {
575  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
576  _M_message(__gnu_debug::__msg_valid_range)
577  ._M_iterator(__first, "first")
578  ._M_iterator(__last, "last"));
579  this->_M_invalidate_if(_Equal(__tmp));
580  }
581  return iterator(_Base::erase(__first.base(),
582  __last.base()), this);
583  }
584 
585  _Base&
586  _M_base() { return *this; }
587 
588  const _Base&
589  _M_base() const { return *this; }
590 
591  private:
592  void
593  _M_invalidate_all()
594  {
595  typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
596  this->_M_invalidate_if(_Not_equal(_Base::end()));
597  }
598  };
599 
600  template<typename _Key, typename _Tp, typename _Hash,
601  typename _Pred, typename _Alloc>
602  inline void
603  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
604  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
605  { __x.swap(__y); }
606 
607  template<typename _Key, typename _Tp, typename _Hash,
608  typename _Pred, typename _Alloc>
609  inline bool
610  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
611  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
612  { return __x._M_equal(__y); }
613 
614  template<typename _Key, typename _Tp, typename _Hash,
615  typename _Pred, typename _Alloc>
616  inline bool
617  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
618  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
619  { return !(__x == __y); }
620 
621 } // namespace __debug
622 } // namespace std
623 
624 #endif // __GXX_EXPERIMENTAL_CXX0X__
625 
626 #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)
std::__debug::unordered_multimap
Class std::unordered_multimap with safety/checking/debug instrumentation.
Definition: debug/unordered_map:341
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition: macros.h:64
std::unordered_multimap
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
Definition: unordered_map.h:324
__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::__debug::unordered_map
Class std::unordered_map with safety/checking/debug instrumentation.
Definition: debug/unordered_map:50
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
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition: macros.h:126
std::unordered_map
A standard container composed of unique keys (containing at most one of each key value) that associat...
Definition: unordered_map.h:256
std::initializer_list
initializer_list
Definition: initializer_list:45
__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::enable_if
enable_if
Definition: type_traits:836
__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::is_convertible
is_convertible
Definition: type_traits:789