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 #ifndef __GXX_EXPERIMENTAL_CXX0X__
34 # include <bits/c++0x_warning.h>
36 # include <unordered_map>
38 #include <debug/safe_sequence.h>
39 #include <debug/safe_iterator.h>
41 namespace std _GLIBCXX_VISIBILITY(default)
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> >
51 : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
52 public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash,
55 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
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;
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;
68 typedef typename _Base::key_type key_type;
69 typedef typename _Base::value_type value_type;
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;
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) { }
83 template<typename _InputIterator>
84 unordered_map(_InputIterator __first, _InputIterator __last,
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,
91 __gnu_debug::__base(__last), __n,
92 __hf, __eql, __a), _Safe_base() { }
94 unordered_map(const unordered_map& __x)
95 : _Base(__x), _Safe_base() { }
97 unordered_map(const _Base& __x)
98 : _Base(__x), _Safe_base() { }
100 unordered_map(unordered_map&& __x)
101 : _Base(std::move(__x)), _Safe_base() { }
103 unordered_map(initializer_list<value_type> __l,
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() { }
111 operator=(const unordered_map& __x)
113 *static_cast<_Base*>(this) = __x;
114 this->_M_invalidate_all();
119 operator=(unordered_map&& __x)
129 operator=(initializer_list<value_type> __l)
137 swap(unordered_map& __x)
140 _Safe_base::_M_swap(__x);
147 this->_M_invalidate_all();
152 { return iterator(_Base::begin(), this); }
156 { return const_iterator(_Base::begin(), this); }
160 { return iterator(_Base::end(), this); }
164 { return const_iterator(_Base::end(), this); }
168 { return const_iterator(_Base::begin(), this); }
172 { return const_iterator(_Base::end(), this); }
180 std::pair<iterator, bool>
181 insert(const value_type& __obj)
183 std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
184 return std::make_pair(iterator(__res.first, this), __res.second);
188 insert(const_iterator __hint, const value_type& __obj)
190 __glibcxx_check_insert(__hint);
191 return iterator(_Base::insert(__hint.base(), __obj), this);
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)
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);
205 template<typename _Pair, typename = typename
206 std::enable_if<std::is_convertible<_Pair,
207 value_type>::value>::type>
209 insert(const_iterator __hint, _Pair&& __obj)
211 __glibcxx_check_insert(__hint);
212 return iterator(_Base::insert(__hint.base(),
213 std::forward<_Pair>(__obj)),
218 insert(std::initializer_list<value_type> __l)
219 { _Base::insert(__l); }
221 template<typename _InputIterator>
223 insert(_InputIterator __first, _InputIterator __last)
225 __glibcxx_check_valid_range(__first, __last);
226 _Base::insert(__gnu_debug::__base(__first),
227 __gnu_debug::__base(__last));
231 find(const key_type& __key)
232 { return iterator(_Base::find(__key), this); }
235 find(const key_type& __key) const
236 { return const_iterator(_Base::find(__key), this); }
238 std::pair<iterator, iterator>
239 equal_range(const key_type& __key)
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));
247 std::pair<const_iterator, const_iterator>
248 equal_range(const key_type& __key) const
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));
257 erase(const key_type& __key)
260 _Base_iterator __victim(_Base::find(__key));
261 if (__victim != _Base::end())
263 this->_M_invalidate_if(_Equal(__victim));
264 _Base::erase(__victim);
271 erase(const_iterator __it)
273 __glibcxx_check_erase(__it);
274 this->_M_invalidate_if(_Equal(__it.base()));
275 return iterator(_Base::erase(__it.base()), this);
280 { return erase(const_iterator(__it)); }
283 erase(const_iterator __first, const_iterator __last)
285 __glibcxx_check_erase_range(__first, __last);
286 for (_Base_const_iterator __tmp = __first.base();
287 __tmp != __last.base(); ++__tmp)
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));
295 return iterator(_Base::erase(__first.base(),
296 __last.base()), this);
300 _M_base() { return *this; }
303 _M_base() const { return *this; }
309 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
310 this->_M_invalidate_if(_Not_equal(_Base::end()));
314 template<typename _Key, typename _Tp, typename _Hash,
315 typename _Pred, typename _Alloc>
317 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
318 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
321 template<typename _Key, typename _Tp, typename _Hash,
322 typename _Pred, typename _Alloc>
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); }
328 template<typename _Key, typename _Tp, typename _Hash,
329 typename _Pred, typename _Alloc>
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); }
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,
344 public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,
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;
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;
360 typedef typename _Base::key_type key_type;
361 typedef typename _Base::value_type value_type;
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;
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) { }
375 template<typename _InputIterator>
376 unordered_multimap(_InputIterator __first, _InputIterator __last,
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,
383 __gnu_debug::__base(__last), __n,
384 __hf, __eql, __a), _Safe_base() { }
386 unordered_multimap(const unordered_multimap& __x)
387 : _Base(__x), _Safe_base() { }
389 unordered_multimap(const _Base& __x)
390 : _Base(__x), _Safe_base() { }
392 unordered_multimap(unordered_multimap&& __x)
393 : _Base(std::move(__x)), _Safe_base() { }
395 unordered_multimap(initializer_list<value_type> __l,
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() { }
403 operator=(const unordered_multimap& __x)
405 *static_cast<_Base*>(this) = __x;
406 this->_M_invalidate_all();
411 operator=(unordered_multimap&& __x)
421 operator=(initializer_list<value_type> __l)
429 swap(unordered_multimap& __x)
432 _Safe_base::_M_swap(__x);
439 this->_M_invalidate_all();
444 { return iterator(_Base::begin(), this); }
448 { return const_iterator(_Base::begin(), this); }
452 { return iterator(_Base::end(), this); }
456 { return const_iterator(_Base::end(), this); }
460 { return const_iterator(_Base::begin(), this); }
464 { return const_iterator(_Base::end(), this); }
473 insert(const value_type& __obj)
474 { return iterator(_Base::insert(__obj), this); }
477 insert(const_iterator __hint, const value_type& __obj)
479 __glibcxx_check_insert(__hint);
480 return iterator(_Base::insert(__hint.base(), __obj), this);
483 template<typename _Pair, typename = typename
484 std::enable_if<std::is_convertible<_Pair,
485 value_type>::value>::type>
487 insert(_Pair&& __obj)
488 { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); }
490 template<typename _Pair, typename = typename
491 std::enable_if<std::is_convertible<_Pair,
492 value_type>::value>::type>
494 insert(const_iterator __hint, _Pair&& __obj)
496 __glibcxx_check_insert(__hint);
497 return iterator(_Base::insert(__hint.base(),
498 std::forward<_Pair>(__obj)),
503 insert(std::initializer_list<value_type> __l)
504 { _Base::insert(__l); }
506 template<typename _InputIterator>
508 insert(_InputIterator __first, _InputIterator __last)
510 __glibcxx_check_valid_range(__first, __last);
511 _Base::insert(__gnu_debug::__base(__first),
512 __gnu_debug::__base(__last));
516 find(const key_type& __key)
517 { return iterator(_Base::find(__key), this); }
520 find(const key_type& __key) const
521 { return const_iterator(_Base::find(__key), this); }
523 std::pair<iterator, iterator>
524 equal_range(const key_type& __key)
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));
532 std::pair<const_iterator, const_iterator>
533 equal_range(const key_type& __key) const
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));
542 erase(const key_type& __key)
545 std::pair<_Base_iterator, _Base_iterator> __pair =
546 _Base::equal_range(__key);
547 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
549 this->_M_invalidate_if(_Equal(__victim));
550 _Base::erase(__victim++);
557 erase(const_iterator __it)
559 __glibcxx_check_erase(__it);
560 this->_M_invalidate_if(_Equal(__it.base()));
561 return iterator(_Base::erase(__it.base()), this);
566 { return erase(const_iterator(__it)); }
569 erase(const_iterator __first, const_iterator __last)
571 __glibcxx_check_erase_range(__first, __last);
572 for (_Base_const_iterator __tmp = __first.base();
573 __tmp != __last.base(); ++__tmp)
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));
581 return iterator(_Base::erase(__first.base(),
582 __last.base()), this);
586 _M_base() { return *this; }
589 _M_base() const { return *this; }
595 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
596 this->_M_invalidate_if(_Not_equal(_Base::end()));
600 template<typename _Key, typename _Tp, typename _Hash,
601 typename _Pred, typename _Alloc>
603 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
604 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
607 template<typename _Key, typename _Tp, typename _Hash,
608 typename _Pred, typename _Alloc>
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); }
614 template<typename _Key, typename _Tp, typename _Hash,
615 typename _Pred, typename _Alloc>
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); }
621 } // namespace __debug
624 #endif // __GXX_EXPERIMENTAL_CXX0X__