1 // Debugging unordered_set/unordered_multiset 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_set
27 * This file is a GNU debug extension to the Standard C++ Library.
30 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
31 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
33 #ifdef __GXX_EXPERIMENTAL_CXX0X__
34 # include <unordered_set>
36 # include <c++0x_warning.h>
39 #include <debug/safe_sequence.h>
40 #include <debug/safe_iterator.h>
41 #include <initializer_list>
47 /// Class std::unordered_set with safety/checking/debug instrumentation.
48 template<typename _Value,
49 typename _Hash = std::hash<_Value>,
50 typename _Pred = std::equal_to<_Value>,
51 typename _Alloc = std::allocator<_Value> >
53 : public _GLIBCXX_STD_D::unordered_set<_Value, _Hash, _Pred, _Alloc>,
54 public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash,
57 typedef _GLIBCXX_STD_D::unordered_set<_Value, _Hash,
59 typedef __gnu_debug::_Safe_sequence<unordered_set> _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_set> iterator;
72 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
73 unordered_set> const_iterator;
76 unordered_set(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_set(_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_set(const unordered_set& __x)
92 : _Base(__x), _Safe_base() { }
94 unordered_set(const _Base& __x)
95 : _Base(__x), _Safe_base() { }
97 unordered_set(unordered_set&& __x)
98 : _Base(std::forward<unordered_set>(__x)), _Safe_base() { }
100 unordered_set(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_set& __x)
110 *static_cast<_Base*>(this) = __x;
111 this->_M_invalidate_all();
116 operator=(unordered_set&& __x)
128 operator=(initializer_list<value_type> __l)
136 swap(unordered_set& __x)
139 _Safe_base::_M_swap(__x);
146 this->_M_invalidate_all();
151 { return iterator(_Base::begin(), this); }
155 { return const_iterator(_Base::begin(), this); }
159 { return iterator(_Base::end(), this); }
163 { return const_iterator(_Base::end(), this); }
167 { return const_iterator(_Base::begin(), this); }
171 { return const_iterator(_Base::end(), this); }
179 std::pair<iterator, bool>
180 insert(const value_type& __obj)
182 typedef std::pair<typename _Base::iterator, bool> __pair_type;
183 __pair_type __res = _Base::insert(__obj);
184 return std::make_pair(iterator(__res.first, this), __res.second);
188 insert(iterator, const value_type& __obj)
190 typedef std::pair<typename _Base::iterator, bool> __pair_type;
191 __pair_type __res = _Base::insert(__obj);
192 return iterator(__res.first, this);
196 insert(const_iterator, const value_type& __obj)
198 typedef std::pair<typename _Base::iterator, bool> __pair_type;
199 __pair_type __res = _Base::insert(__obj);
200 return const_iterator(__res.first, this);
204 insert(std::initializer_list<value_type> __l)
205 { _Base::insert(__l); }
207 template<typename _InputIterator>
209 insert(_InputIterator __first, _InputIterator __last)
211 __glibcxx_check_valid_range(__first, __last);
212 _Base::insert(__first, __last);
216 find(const key_type& __key)
217 { return iterator(_Base::find(__key), this); }
220 find(const key_type& __key) const
221 { return const_iterator(_Base::find(__key), this); }
223 std::pair<iterator, iterator>
224 equal_range(const key_type& __key)
226 typedef typename _Base::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(iterator(__res.first, this),
230 iterator(__res.second, this));
233 std::pair<const_iterator, const_iterator>
234 equal_range(const key_type& __key) const
236 typedef typename _Base::const_iterator _Base_iterator;
237 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
238 __pair_type __res = _Base::equal_range(__key);
239 return std::make_pair(const_iterator(__res.first, this),
240 const_iterator(__res.second, this));
244 erase(const key_type& __key)
247 iterator __victim(_Base::find(__key), this);
248 if (__victim != end())
250 this->erase(__victim);
259 __glibcxx_check_erase(__it);
260 __it._M_invalidate();
261 return iterator(_Base::erase(__it.base()), this);
265 erase(const_iterator __it)
267 __glibcxx_check_erase(__it);
268 __it._M_invalidate();
269 return const_iterator(_Base::erase(__it.base()), this);
273 erase(iterator __first, iterator __last)
275 __glibcxx_check_erase_range(__first, __last);
276 for (iterator __tmp = __first; __tmp != __last;)
278 iterator __victim = __tmp++;
279 __victim._M_invalidate();
281 return iterator(_Base::erase(__first.base(),
282 __last.base()), this);
286 erase(const_iterator __first, const_iterator __last)
288 __glibcxx_check_erase_range(__first, __last);
289 for (const_iterator __tmp = __first; __tmp != __last;)
291 const_iterator __victim = __tmp++;
292 __victim._M_invalidate();
294 return const_iterator(_Base::erase(__first.base(),
295 __last.base()), this);
299 _M_base() { return *this; }
302 _M_base() const { return *this; }
308 typedef typename _Base::const_iterator _Base_const_iterator;
309 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
310 this->_M_invalidate_if(_Not_equal(_M_base().end()));
314 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
316 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
317 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
321 /// Class std::unordered_multiset with safety/checking/debug instrumentation.
322 template<typename _Value,
323 typename _Hash = std::hash<_Value>,
324 typename _Pred = std::equal_to<_Value>,
325 typename _Alloc = std::allocator<_Value> >
326 class unordered_multiset
327 : public _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
328 public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash,
331 typedef _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash,
332 _Pred, _Alloc> _Base;
333 typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base;
336 typedef typename _Base::size_type size_type;
337 typedef typename _Base::hasher hasher;
338 typedef typename _Base::key_equal key_equal;
339 typedef typename _Base::allocator_type allocator_type;
341 typedef typename _Base::key_type key_type;
342 typedef typename _Base::value_type value_type;
344 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
345 unordered_multiset> iterator;
346 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
347 unordered_multiset> const_iterator;
350 unordered_multiset(size_type __n = 10,
351 const hasher& __hf = hasher(),
352 const key_equal& __eql = key_equal(),
353 const allocator_type& __a = allocator_type())
354 : _Base(__n, __hf, __eql, __a) { }
356 template<typename _InputIterator>
357 unordered_multiset(_InputIterator __f, _InputIterator __l,
359 const hasher& __hf = hasher(),
360 const key_equal& __eql = key_equal(),
361 const allocator_type& __a = allocator_type())
362 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
363 __hf, __eql, __a), _Safe_base() { }
365 unordered_multiset(const unordered_multiset& __x)
366 : _Base(__x), _Safe_base() { }
368 unordered_multiset(const _Base& __x)
369 : _Base(__x), _Safe_base() { }
371 unordered_multiset(unordered_multiset&& __x)
372 : _Base(std::forward<unordered_multiset>(__x)), _Safe_base() { }
374 unordered_multiset(initializer_list<value_type> __l,
376 const hasher& __hf = hasher(),
377 const key_equal& __eql = key_equal(),
378 const allocator_type& __a = allocator_type())
379 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
382 operator=(const unordered_multiset& __x)
384 *static_cast<_Base*>(this) = __x;
385 this->_M_invalidate_all();
390 operator=(unordered_multiset&& __x)
399 operator=(initializer_list<value_type> __l)
407 swap(unordered_multiset& __x)
410 _Safe_base::_M_swap(__x);
417 this->_M_invalidate_all();
422 { return iterator(_Base::begin(), this); }
426 { return const_iterator(_Base::begin(), this); }
430 { return iterator(_Base::end(), this); }
434 { return const_iterator(_Base::end(), this); }
438 { return const_iterator(_Base::begin(), this); }
442 { return const_iterator(_Base::end(), this); }
451 insert(const value_type& __obj)
452 { return iterator(_Base::insert(__obj), this); }
455 insert(iterator, const value_type& __obj)
456 { return iterator(_Base::insert(__obj), this); }
459 insert(const_iterator, const value_type& __obj)
460 { return const_iterator(_Base::insert(__obj), this); }
463 insert(std::initializer_list<value_type> __l)
464 { _Base::insert(__l); }
466 template<typename _InputIterator>
468 insert(_InputIterator __first, _InputIterator __last)
470 __glibcxx_check_valid_range(__first, __last);
471 _Base::insert(__first, __last);
475 find(const key_type& __key)
476 { return iterator(_Base::find(__key), this); }
479 find(const key_type& __key) const
480 { return const_iterator(_Base::find(__key), this); }
482 std::pair<iterator, iterator>
483 equal_range(const key_type& __key)
485 typedef typename _Base::iterator _Base_iterator;
486 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
487 __pair_type __res = _Base::equal_range(__key);
488 return std::make_pair(iterator(__res.first, this),
489 iterator(__res.second, this));
492 std::pair<const_iterator, const_iterator>
493 equal_range(const key_type& __key) const
495 typedef typename _Base::const_iterator _Base_iterator;
496 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
497 __pair_type __res = _Base::equal_range(__key);
498 return std::make_pair(const_iterator(__res.first, this),
499 const_iterator(__res.second, this));
503 erase(const key_type& __key)
506 iterator __victim(_Base::find(__key), this);
507 if (__victim != end())
509 this->erase(__victim);
518 __glibcxx_check_erase(__it);
519 __it._M_invalidate();
520 return iterator(_Base::erase(__it.base()), this);
524 erase(const_iterator __it)
526 __glibcxx_check_erase(__it);
527 __it._M_invalidate();
528 return const_iterator(_Base::erase(__it.base()), this);
532 erase(iterator __first, iterator __last)
534 __glibcxx_check_erase_range(__first, __last);
535 for (iterator __tmp = __first; __tmp != __last;)
537 iterator __victim = __tmp++;
538 __victim._M_invalidate();
540 return iterator(_Base::erase(__first.base(),
541 __last.base()), this);
545 erase(const_iterator __first, const_iterator __last)
547 __glibcxx_check_erase_range(__first, __last);
548 for (const_iterator __tmp = __first; __tmp != __last;)
550 const_iterator __victim = __tmp++;
551 __victim._M_invalidate();
553 return const_iterator(_Base::erase(__first.base(),
554 __last.base()), this);
558 _M_base() { return *this; }
561 _M_base() const { return *this; }
567 typedef typename _Base::const_iterator _Base_const_iterator;
568 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
569 this->_M_invalidate_if(_Not_equal(_M_base().end()));
573 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
575 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
576 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
579 } // namespace __debug