1 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
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 2, 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 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
31 /** @file debug/unordered_map
32 * This file is a GNU debug extension to the Standard C++ Library.
35 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
36 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
38 #ifdef __GXX_EXPERIMENTAL_CXX0X__
39 # include <unordered_map>
41 # include <c++0x_warning.h>
44 #include <debug/safe_sequence.h>
45 #include <debug/safe_iterator.h>
46 #include <initializer_list>
52 template<typename _Key, typename _Tp,
53 typename _Hash = std::hash<_Key>,
54 typename _Pred = std::equal_to<_Key>,
55 typename _Alloc = std::allocator<_Key> >
57 : public _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
58 public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash,
61 typedef _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash,
63 typedef __gnu_debug::_Safe_sequence<unordered_map> _Safe_base;
66 typedef typename _Base::size_type size_type;
67 typedef typename _Base::hasher hasher;
68 typedef typename _Base::key_equal key_equal;
69 typedef typename _Base::allocator_type allocator_type;
71 typedef typename _Base::key_type key_type;
72 typedef typename _Base::value_type value_type;
74 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
75 unordered_map> iterator;
76 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
77 unordered_map> const_iterator;
80 unordered_map(size_type __n = 10,
81 const hasher& __hf = hasher(),
82 const key_equal& __eql = key_equal(),
83 const allocator_type& __a = allocator_type())
84 : _Base(__n, __hf, __eql, __a) { }
86 template<typename _InputIterator>
87 unordered_map(_InputIterator __f, _InputIterator __l,
89 const hasher& __hf = hasher(),
90 const key_equal& __eql = key_equal(),
91 const allocator_type& __a = allocator_type())
92 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
93 __hf, __eql, __a), _Safe_base() { }
95 unordered_map(const unordered_map& __x)
96 : _Base(__x), _Safe_base() { }
98 unordered_map(const _Base& __x)
99 : _Base(__x), _Safe_base() { }
101 unordered_map(unordered_map&& __x)
102 : _Base(std::forward<unordered_map>(__x)), _Safe_base() { }
104 unordered_map(initializer_list<value_type> __l,
106 const hasher& __hf = hasher(),
107 const key_equal& __eql = key_equal(),
108 const allocator_type& __a = allocator_type())
109 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
112 operator=(const unordered_map& __x)
114 *static_cast<_Base*>(this) = __x;
115 this->_M_invalidate_all();
120 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 typedef std::pair<typename _Base::iterator, bool> __pair_type;
184 __pair_type __res = _Base::insert(__obj);
185 return std::make_pair(iterator(__res.first, this), __res.second);
189 insert(iterator, const value_type& __obj)
191 typedef std::pair<typename _Base::iterator, bool> __pair_type;
192 __pair_type __res = _Base::insert(__obj);
193 return iterator(__res.first, this);
197 insert(const_iterator, const value_type& __obj)
199 typedef std::pair<typename _Base::iterator, bool> __pair_type;
200 __pair_type __res = _Base::insert(__obj);
201 return const_iterator(__res.first, this);
205 insert(std::initializer_list<value_type> __l)
206 { _Base::insert(__l); }
208 template<typename _InputIterator>
210 insert(_InputIterator __first, _InputIterator __last)
212 __glibcxx_check_valid_range(__first, __last);
213 _Base::insert(__first, __last);
217 find(const key_type& __key)
218 { return iterator(_Base::find(__key), this); }
221 find(const key_type& __key) const
222 { return const_iterator(_Base::find(__key), this); }
224 std::pair<iterator, iterator>
225 equal_range(const key_type& __key)
227 typedef typename _Base::iterator _Base_iterator;
228 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
229 __pair_type __res = _Base::equal_range(__key);
230 return std::make_pair(iterator(__res.first, this),
231 iterator(__res.second, this));
234 std::pair<const_iterator, const_iterator>
235 equal_range(const key_type& __key) const
237 typedef typename _Base::const_iterator _Base_iterator;
238 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
239 __pair_type __res = _Base::equal_range(__key);
240 return std::make_pair(const_iterator(__res.first, this),
241 const_iterator(__res.second, this));
245 erase(const key_type& __key)
248 iterator __victim(_Base::find(__key), this);
249 if (__victim != end())
251 this->erase(__victim);
260 __glibcxx_check_erase(__it);
261 __it._M_invalidate();
262 return iterator(_Base::erase(__it.base()), this);
266 erase(const_iterator __it)
268 __glibcxx_check_erase(__it);
269 __it._M_invalidate();
270 return const_iterator(_Base::erase(__it.base()), this);
274 erase(iterator __first, iterator __last)
276 __glibcxx_check_erase_range(__first, __last);
277 for (iterator __tmp = __first; __tmp != __last;)
279 iterator __victim = __tmp++;
280 __victim._M_invalidate();
282 return iterator(_Base::erase(__first.base(),
283 __last.base()), this);
287 erase(const_iterator __first, const_iterator __last)
289 __glibcxx_check_erase_range(__first, __last);
290 for (const_iterator __tmp = __first; __tmp != __last;)
292 const_iterator __victim = __tmp++;
293 __victim._M_invalidate();
295 return const_iterator(_Base::erase(__first.base(),
296 __last.base()), this);
300 _M_base() { return *this; }
303 _M_base() const { return *this; }
309 typedef typename _Base::const_iterator _Base_const_iterator;
310 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
311 this->_M_invalidate_if(_Not_equal(_M_base().end()));
315 template<typename _Key, typename _Tp, typename _Hash,
316 typename _Pred, typename _Alloc>
318 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
319 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
322 template<typename _Key, typename _Tp, typename _Hash,
323 typename _Pred, typename _Alloc>
325 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&& __x,
326 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
329 template<typename _Key, typename _Tp, typename _Hash,
330 typename _Pred, typename _Alloc>
332 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
333 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&& __y)
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_D::unordered_multimap<_Key, _Tp, _Hash,
344 public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,
347 typedef _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,
348 _Pred, _Alloc> _Base;
349 typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base;
352 typedef typename _Base::size_type size_type;
353 typedef typename _Base::hasher hasher;
354 typedef typename _Base::key_equal key_equal;
355 typedef typename _Base::allocator_type allocator_type;
357 typedef typename _Base::key_type key_type;
358 typedef typename _Base::value_type value_type;
360 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
361 unordered_multimap> iterator;
362 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
363 unordered_multimap> const_iterator;
366 unordered_multimap(size_type __n = 10,
367 const hasher& __hf = hasher(),
368 const key_equal& __eql = key_equal(),
369 const allocator_type& __a = allocator_type())
370 : _Base(__n, __hf, __eql, __a) { }
372 template<typename _InputIterator>
373 unordered_multimap(_InputIterator __f, _InputIterator __l,
375 const hasher& __hf = hasher(),
376 const key_equal& __eql = key_equal(),
377 const allocator_type& __a = allocator_type())
378 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
379 __hf, __eql, __a), _Safe_base() { }
381 unordered_multimap(const unordered_multimap& __x)
382 : _Base(__x), _Safe_base() { }
384 unordered_multimap(const _Base& __x)
385 : _Base(__x), _Safe_base() { }
387 unordered_multimap(unordered_multimap&& __x)
388 : _Base(std::forward<unordered_multimap>(__x)), _Safe_base() { }
390 unordered_multimap(initializer_list<value_type> __l,
392 const hasher& __hf = hasher(),
393 const key_equal& __eql = key_equal(),
394 const allocator_type& __a = allocator_type())
395 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
398 operator=(const unordered_multimap& __x)
400 *static_cast<_Base*>(this) = __x;
401 this->_M_invalidate_all();
406 operator=(unordered_multimap&& __x)
415 operator=(initializer_list<value_type> __l)
423 swap(unordered_multimap&& __x)
426 _Safe_base::_M_swap(__x);
433 this->_M_invalidate_all();
438 { return iterator(_Base::begin(), this); }
442 { return const_iterator(_Base::begin(), this); }
446 { return iterator(_Base::end(), this); }
450 { return const_iterator(_Base::end(), this); }
454 { return const_iterator(_Base::begin(), this); }
458 { return const_iterator(_Base::end(), this); }
467 insert(const value_type& __obj)
468 { return iterator(_Base::insert(__obj), this); }
471 insert(iterator, const value_type& __obj)
472 { return iterator(_Base::insert(__obj), this); }
475 insert(const_iterator, const value_type& __obj)
476 { return const_iterator(_Base::insert(__obj), this); }
479 insert(std::initializer_list<value_type> __l)
480 { _Base::insert(__l); }
482 template<typename _InputIterator>
484 insert(_InputIterator __first, _InputIterator __last)
486 __glibcxx_check_valid_range(__first, __last);
487 _Base::insert(__first, __last);
491 find(const key_type& __key)
492 { return iterator(_Base::find(__key), this); }
495 find(const key_type& __key) const
496 { return const_iterator(_Base::find(__key), this); }
498 std::pair<iterator, iterator>
499 equal_range(const key_type& __key)
501 typedef typename _Base::iterator _Base_iterator;
502 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
503 __pair_type __res = _Base::equal_range(__key);
504 return std::make_pair(iterator(__res.first, this),
505 iterator(__res.second, this));
508 std::pair<const_iterator, const_iterator>
509 equal_range(const key_type& __key) const
511 typedef typename _Base::const_iterator _Base_iterator;
512 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
513 __pair_type __res = _Base::equal_range(__key);
514 return std::make_pair(const_iterator(__res.first, this),
515 const_iterator(__res.second, this));
519 erase(const key_type& __key)
522 iterator __victim(_Base::find(__key), this);
523 if (__victim != end())
525 this->erase(__victim);
534 __glibcxx_check_erase(__it);
535 __it._M_invalidate();
536 return iterator(_Base::erase(__it.base()), this);
540 erase(const_iterator __it)
542 __glibcxx_check_erase(__it);
543 __it._M_invalidate();
544 return const_iterator(_Base::erase(__it.base()), this);
548 erase(iterator __first, iterator __last)
550 __glibcxx_check_erase_range(__first, __last);
551 for (iterator __tmp = __first; __tmp != __last;)
553 iterator __victim = __tmp++;
554 __victim._M_invalidate();
556 return iterator(_Base::erase(__first.base(),
557 __last.base()), this);
561 erase(const_iterator __first, const_iterator __last)
563 __glibcxx_check_erase_range(__first, __last);
564 for (const_iterator __tmp = __first; __tmp != __last;)
566 const_iterator __victim = __tmp++;
567 __victim._M_invalidate();
569 return const_iterator(_Base::erase(__first.base(),
570 __last.base()), this);
574 _M_base() { return *this; }
577 _M_base() const { return *this; }
583 typedef typename _Base::const_iterator _Base_const_iterator;
584 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
585 this->_M_invalidate_if(_Not_equal(_M_base().end()));
589 template<typename _Key, typename _Tp, typename _Hash,
590 typename _Pred, typename _Alloc>
592 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
593 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
596 template<typename _Key, typename _Tp, typename _Hash,
597 typename _Pred, typename _Alloc>
599 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&& __x,
600 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
603 template<typename _Key, typename _Tp, typename _Hash,
604 typename _Pred, typename _Alloc>
606 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
607 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&& __y)
610 } // namespace __debug