1 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 // Free Software Foundation, Inc.
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)
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.
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.
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/>.
26 /** @file debug/unordered_map
27 * This file is a GNU debug extension to the Standard C++ Library.
30 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
31 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
33 #ifdef __GXX_EXPERIMENTAL_CXX0X__
34 # include <unordered_map>
36 # include <bits/c++0x_warning.h>
39 #include <debug/safe_sequence.h>
40 #include <debug/safe_iterator.h>
41 #include <initializer_list>
47 /// Class std::unordered_map with safety/checking/debug instrumentation.
48 template<typename _Key, typename _Tp,
49 typename _Hash = std::hash<_Key>,
50 typename _Pred = std::equal_to<_Key>,
51 typename _Alloc = std::allocator<_Key> >
53 : public _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
54 public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash,
57 typedef _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash,
59 typedef __gnu_debug::_Safe_sequence<unordered_map> _Safe_base;
62 typedef typename _Base::size_type size_type;
63 typedef typename _Base::hasher hasher;
64 typedef typename _Base::key_equal key_equal;
65 typedef typename _Base::allocator_type allocator_type;
67 typedef typename _Base::key_type key_type;
68 typedef typename _Base::value_type value_type;
70 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
71 unordered_map> iterator;
72 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
73 unordered_map> const_iterator;
76 unordered_map(size_type __n = 10,
77 const hasher& __hf = hasher(),
78 const key_equal& __eql = key_equal(),
79 const allocator_type& __a = allocator_type())
80 : _Base(__n, __hf, __eql, __a) { }
82 template<typename _InputIterator>
83 unordered_map(_InputIterator __f, _InputIterator __l,
85 const hasher& __hf = hasher(),
86 const key_equal& __eql = key_equal(),
87 const allocator_type& __a = allocator_type())
88 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
89 __hf, __eql, __a), _Safe_base() { }
91 unordered_map(const unordered_map& __x)
92 : _Base(__x), _Safe_base() { }
94 unordered_map(const _Base& __x)
95 : _Base(__x), _Safe_base() { }
97 unordered_map(unordered_map&& __x)
98 : _Base(std::forward<unordered_map>(__x)), _Safe_base() { }
100 unordered_map(initializer_list<value_type> __l,
102 const hasher& __hf = hasher(),
103 const key_equal& __eql = key_equal(),
104 const allocator_type& __a = allocator_type())
105 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
108 operator=(const unordered_map& __x)
110 *static_cast<_Base*>(this) = __x;
111 this->_M_invalidate_all();
116 operator=(unordered_map&& __x)
126 operator=(initializer_list<value_type> __l)
134 swap(unordered_map& __x)
137 _Safe_base::_M_swap(__x);
144 this->_M_invalidate_all();
149 { return iterator(_Base::begin(), this); }
153 { return const_iterator(_Base::begin(), this); }
157 { return iterator(_Base::end(), this); }
161 { return const_iterator(_Base::end(), this); }
165 { return const_iterator(_Base::begin(), this); }
169 { return const_iterator(_Base::end(), this); }
177 std::pair<iterator, bool>
178 insert(const value_type& __obj)
180 typedef std::pair<typename _Base::iterator, bool> __pair_type;
181 __pair_type __res = _Base::insert(__obj);
182 return std::make_pair(iterator(__res.first, this), __res.second);
186 insert(const_iterator, const value_type& __obj)
188 typedef std::pair<typename _Base::iterator, bool> __pair_type;
189 __pair_type __res = _Base::insert(__obj);
190 return iterator(__res.first, this);
194 insert(std::initializer_list<value_type> __l)
195 { _Base::insert(__l); }
197 template<typename _InputIterator>
199 insert(_InputIterator __first, _InputIterator __last)
201 __glibcxx_check_valid_range(__first, __last);
202 _Base::insert(__first, __last);
206 find(const key_type& __key)
207 { return iterator(_Base::find(__key), this); }
210 find(const key_type& __key) const
211 { return const_iterator(_Base::find(__key), this); }
213 std::pair<iterator, iterator>
214 equal_range(const key_type& __key)
216 typedef typename _Base::iterator _Base_iterator;
217 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
218 __pair_type __res = _Base::equal_range(__key);
219 return std::make_pair(iterator(__res.first, this),
220 iterator(__res.second, this));
223 std::pair<const_iterator, const_iterator>
224 equal_range(const key_type& __key) const
226 typedef typename _Base::const_iterator _Base_iterator;
227 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
228 __pair_type __res = _Base::equal_range(__key);
229 return std::make_pair(const_iterator(__res.first, this),
230 const_iterator(__res.second, this));
234 erase(const key_type& __key)
237 iterator __victim(_Base::find(__key), this);
238 if (__victim != end())
240 this->erase(__victim);
247 erase(const_iterator __it)
249 __glibcxx_check_erase(__it);
250 __it._M_invalidate();
251 return iterator(_Base::erase(__it.base()), this);
255 erase(const_iterator __first, const_iterator __last)
257 __glibcxx_check_erase_range(__first, __last);
258 for (const_iterator __tmp = __first; __tmp != __last;)
260 const_iterator __victim = __tmp++;
261 __victim._M_invalidate();
263 return iterator(_Base::erase(__first.base(),
264 __last.base()), this);
268 _M_base() { return *this; }
271 _M_base() const { return *this; }
277 typedef typename _Base::const_iterator _Base_const_iterator;
278 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
279 this->_M_invalidate_if(_Not_equal(_M_base().end()));
283 template<typename _Key, typename _Tp, typename _Hash,
284 typename _Pred, typename _Alloc>
286 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
287 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
290 template<typename _Key, typename _Tp, typename _Hash,
291 typename _Pred, typename _Alloc>
293 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
294 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
295 { return __x._M_equal(__y); }
297 template<typename _Key, typename _Tp, typename _Hash,
298 typename _Pred, typename _Alloc>
300 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
301 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
302 { return !(__x == __y); }
305 /// Class std::unordered_multimap with safety/checking/debug instrumentation.
306 template<typename _Key, typename _Tp,
307 typename _Hash = std::hash<_Key>,
308 typename _Pred = std::equal_to<_Key>,
309 typename _Alloc = std::allocator<_Key> >
310 class unordered_multimap
311 : public _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,
313 public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,
316 typedef _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,
317 _Pred, _Alloc> _Base;
318 typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base;
321 typedef typename _Base::size_type size_type;
322 typedef typename _Base::hasher hasher;
323 typedef typename _Base::key_equal key_equal;
324 typedef typename _Base::allocator_type allocator_type;
326 typedef typename _Base::key_type key_type;
327 typedef typename _Base::value_type value_type;
329 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
330 unordered_multimap> iterator;
331 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
332 unordered_multimap> const_iterator;
335 unordered_multimap(size_type __n = 10,
336 const hasher& __hf = hasher(),
337 const key_equal& __eql = key_equal(),
338 const allocator_type& __a = allocator_type())
339 : _Base(__n, __hf, __eql, __a) { }
341 template<typename _InputIterator>
342 unordered_multimap(_InputIterator __f, _InputIterator __l,
344 const hasher& __hf = hasher(),
345 const key_equal& __eql = key_equal(),
346 const allocator_type& __a = allocator_type())
347 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
348 __hf, __eql, __a), _Safe_base() { }
350 unordered_multimap(const unordered_multimap& __x)
351 : _Base(__x), _Safe_base() { }
353 unordered_multimap(const _Base& __x)
354 : _Base(__x), _Safe_base() { }
356 unordered_multimap(unordered_multimap&& __x)
357 : _Base(std::forward<unordered_multimap>(__x)), _Safe_base() { }
359 unordered_multimap(initializer_list<value_type> __l,
361 const hasher& __hf = hasher(),
362 const key_equal& __eql = key_equal(),
363 const allocator_type& __a = allocator_type())
364 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
367 operator=(const unordered_multimap& __x)
369 *static_cast<_Base*>(this) = __x;
370 this->_M_invalidate_all();
375 operator=(unordered_multimap&& __x)
385 operator=(initializer_list<value_type> __l)
393 swap(unordered_multimap& __x)
396 _Safe_base::_M_swap(__x);
403 this->_M_invalidate_all();
408 { return iterator(_Base::begin(), this); }
412 { return const_iterator(_Base::begin(), this); }
416 { return iterator(_Base::end(), this); }
420 { return const_iterator(_Base::end(), this); }
424 { return const_iterator(_Base::begin(), this); }
428 { return const_iterator(_Base::end(), this); }
437 insert(const value_type& __obj)
438 { return iterator(_Base::insert(__obj), this); }
441 insert(const_iterator, const value_type& __obj)
442 { return iterator(_Base::insert(__obj), this); }
445 insert(std::initializer_list<value_type> __l)
446 { _Base::insert(__l); }
448 template<typename _InputIterator>
450 insert(_InputIterator __first, _InputIterator __last)
452 __glibcxx_check_valid_range(__first, __last);
453 _Base::insert(__first, __last);
457 find(const key_type& __key)
458 { return iterator(_Base::find(__key), this); }
461 find(const key_type& __key) const
462 { return const_iterator(_Base::find(__key), this); }
464 std::pair<iterator, iterator>
465 equal_range(const key_type& __key)
467 typedef typename _Base::iterator _Base_iterator;
468 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
469 __pair_type __res = _Base::equal_range(__key);
470 return std::make_pair(iterator(__res.first, this),
471 iterator(__res.second, this));
474 std::pair<const_iterator, const_iterator>
475 equal_range(const key_type& __key) const
477 typedef typename _Base::const_iterator _Base_iterator;
478 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
479 __pair_type __res = _Base::equal_range(__key);
480 return std::make_pair(const_iterator(__res.first, this),
481 const_iterator(__res.second, this));
485 erase(const key_type& __key)
488 iterator __victim(_Base::find(__key), this);
489 if (__victim != end())
491 this->erase(__victim);
498 erase(const_iterator __it)
500 __glibcxx_check_erase(__it);
501 __it._M_invalidate();
502 return iterator(_Base::erase(__it.base()), this);
506 erase(const_iterator __first, const_iterator __last)
508 __glibcxx_check_erase_range(__first, __last);
509 for (const_iterator __tmp = __first; __tmp != __last;)
511 const_iterator __victim = __tmp++;
512 __victim._M_invalidate();
514 return iterator(_Base::erase(__first.base(),
515 __last.base()), this);
519 _M_base() { return *this; }
522 _M_base() const { return *this; }
528 typedef typename _Base::const_iterator _Base_const_iterator;
529 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
530 this->_M_invalidate_if(_Not_equal(_M_base().end()));
534 template<typename _Key, typename _Tp, typename _Hash,
535 typename _Pred, typename _Alloc>
537 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
538 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
541 template<typename _Key, typename _Tp, typename _Hash,
542 typename _Pred, typename _Alloc>
544 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
545 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
546 { return __x._M_equal(__y); }
548 template<typename _Key, typename _Tp, typename _Hash,
549 typename _Pred, typename _Alloc>
551 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
552 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
553 { return !(__x == __y); }
555 } // namespace __debug