1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
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 template<typename _Value,
48 typename _Hash = std::hash<_Value>,
49 typename _Pred = std::equal_to<_Value>,
50 typename _Alloc = std::allocator<_Value> >
52 : public _GLIBCXX_STD_D::unordered_set<_Value, _Hash, _Pred, _Alloc>,
53 public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash,
56 typedef _GLIBCXX_STD_D::unordered_set<_Value, _Hash,
58 typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base;
61 typedef typename _Base::size_type size_type;
62 typedef typename _Base::hasher hasher;
63 typedef typename _Base::key_equal key_equal;
64 typedef typename _Base::allocator_type allocator_type;
66 typedef typename _Base::key_type key_type;
67 typedef typename _Base::value_type value_type;
69 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
70 unordered_set> iterator;
71 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
72 unordered_set> const_iterator;
75 unordered_set(size_type __n = 10,
76 const hasher& __hf = hasher(),
77 const key_equal& __eql = key_equal(),
78 const allocator_type& __a = allocator_type())
79 : _Base(__n, __hf, __eql, __a) { }
81 template<typename _InputIterator>
82 unordered_set(_InputIterator __f, _InputIterator __l,
84 const hasher& __hf = hasher(),
85 const key_equal& __eql = key_equal(),
86 const allocator_type& __a = allocator_type())
87 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
88 __hf, __eql, __a), _Safe_base() { }
90 unordered_set(const unordered_set& __x)
91 : _Base(__x), _Safe_base() { }
93 unordered_set(const _Base& __x)
94 : _Base(__x), _Safe_base() { }
96 unordered_set(unordered_set&& __x)
97 : _Base(std::forward<unordered_set>(__x)), _Safe_base() { }
99 unordered_set(initializer_list<value_type> __l,
101 const hasher& __hf = hasher(),
102 const key_equal& __eql = key_equal(),
103 const allocator_type& __a = allocator_type())
104 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
107 operator=(const unordered_set& __x)
109 *static_cast<_Base*>(this) = __x;
110 this->_M_invalidate_all();
115 operator=(unordered_set&& __x)
124 operator=(initializer_list<value_type> __l)
132 swap(unordered_set&& __x)
135 _Safe_base::_M_swap(__x);
142 this->_M_invalidate_all();
147 { return iterator(_Base::begin(), this); }
151 { return const_iterator(_Base::begin(), this); }
155 { return iterator(_Base::end(), this); }
159 { return const_iterator(_Base::end(), this); }
163 { return const_iterator(_Base::begin(), this); }
167 { return const_iterator(_Base::end(), this); }
175 std::pair<iterator, bool>
176 insert(const value_type& __obj)
178 typedef std::pair<typename _Base::iterator, bool> __pair_type;
179 __pair_type __res = _Base::insert(__obj);
180 return std::make_pair(iterator(__res.first, this), __res.second);
184 insert(iterator, const value_type& __obj)
186 typedef std::pair<typename _Base::iterator, bool> __pair_type;
187 __pair_type __res = _Base::insert(__obj);
188 return iterator(__res.first, this);
192 insert(const_iterator, const value_type& __obj)
194 typedef std::pair<typename _Base::iterator, bool> __pair_type;
195 __pair_type __res = _Base::insert(__obj);
196 return const_iterator(__res.first, this);
200 insert(std::initializer_list<value_type> __l)
201 { _Base::insert(__l); }
203 template<typename _InputIterator>
205 insert(_InputIterator __first, _InputIterator __last)
207 __glibcxx_check_valid_range(__first, __last);
208 _Base::insert(__first, __last);
212 find(const key_type& __key)
213 { return iterator(_Base::find(__key), this); }
216 find(const key_type& __key) const
217 { return const_iterator(_Base::find(__key), this); }
219 std::pair<iterator, iterator>
220 equal_range(const key_type& __key)
222 typedef typename _Base::iterator _Base_iterator;
223 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
224 __pair_type __res = _Base::equal_range(__key);
225 return std::make_pair(iterator(__res.first, this),
226 iterator(__res.second, this));
229 std::pair<const_iterator, const_iterator>
230 equal_range(const key_type& __key) const
232 typedef typename _Base::const_iterator _Base_iterator;
233 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
234 __pair_type __res = _Base::equal_range(__key);
235 return std::make_pair(const_iterator(__res.first, this),
236 const_iterator(__res.second, this));
240 erase(const key_type& __key)
243 iterator __victim(_Base::find(__key), this);
244 if (__victim != end())
246 this->erase(__victim);
255 __glibcxx_check_erase(__it);
256 __it._M_invalidate();
257 return iterator(_Base::erase(__it.base()), this);
261 erase(const_iterator __it)
263 __glibcxx_check_erase(__it);
264 __it._M_invalidate();
265 return const_iterator(_Base::erase(__it.base()), this);
269 erase(iterator __first, iterator __last)
271 __glibcxx_check_erase_range(__first, __last);
272 for (iterator __tmp = __first; __tmp != __last;)
274 iterator __victim = __tmp++;
275 __victim._M_invalidate();
277 return iterator(_Base::erase(__first.base(),
278 __last.base()), this);
282 erase(const_iterator __first, const_iterator __last)
284 __glibcxx_check_erase_range(__first, __last);
285 for (const_iterator __tmp = __first; __tmp != __last;)
287 const_iterator __victim = __tmp++;
288 __victim._M_invalidate();
290 return const_iterator(_Base::erase(__first.base(),
291 __last.base()), this);
295 _M_base() { return *this; }
298 _M_base() const { return *this; }
304 typedef typename _Base::const_iterator _Base_const_iterator;
305 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
306 this->_M_invalidate_if(_Not_equal(_M_base().end()));
310 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
312 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
313 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
316 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
318 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>&& __x,
319 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
322 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
324 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
325 unordered_set<_Value, _Hash, _Pred, _Alloc>&& __y)
329 template<typename _Value,
330 typename _Hash = std::hash<_Value>,
331 typename _Pred = std::equal_to<_Value>,
332 typename _Alloc = std::allocator<_Value> >
333 class unordered_multiset
334 : public _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
335 public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash,
338 typedef _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash,
339 _Pred, _Alloc> _Base;
340 typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base;
343 typedef typename _Base::size_type size_type;
344 typedef typename _Base::hasher hasher;
345 typedef typename _Base::key_equal key_equal;
346 typedef typename _Base::allocator_type allocator_type;
348 typedef typename _Base::key_type key_type;
349 typedef typename _Base::value_type value_type;
351 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
352 unordered_multiset> iterator;
353 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
354 unordered_multiset> const_iterator;
357 unordered_multiset(size_type __n = 10,
358 const hasher& __hf = hasher(),
359 const key_equal& __eql = key_equal(),
360 const allocator_type& __a = allocator_type())
361 : _Base(__n, __hf, __eql, __a) { }
363 template<typename _InputIterator>
364 unordered_multiset(_InputIterator __f, _InputIterator __l,
366 const hasher& __hf = hasher(),
367 const key_equal& __eql = key_equal(),
368 const allocator_type& __a = allocator_type())
369 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
370 __hf, __eql, __a), _Safe_base() { }
372 unordered_multiset(const unordered_multiset& __x)
373 : _Base(__x), _Safe_base() { }
375 unordered_multiset(const _Base& __x)
376 : _Base(__x), _Safe_base() { }
378 unordered_multiset(unordered_multiset&& __x)
379 : _Base(std::forward<unordered_multiset>(__x)), _Safe_base() { }
381 unordered_multiset(initializer_list<value_type> __l,
383 const hasher& __hf = hasher(),
384 const key_equal& __eql = key_equal(),
385 const allocator_type& __a = allocator_type())
386 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
389 operator=(const unordered_multiset& __x)
391 *static_cast<_Base*>(this) = __x;
392 this->_M_invalidate_all();
397 operator=(unordered_multiset&& __x)
406 operator=(initializer_list<value_type> __l)
414 swap(unordered_multiset&& __x)
417 _Safe_base::_M_swap(__x);
424 this->_M_invalidate_all();
429 { return iterator(_Base::begin(), this); }
433 { return const_iterator(_Base::begin(), this); }
437 { return iterator(_Base::end(), this); }
441 { return const_iterator(_Base::end(), this); }
445 { return const_iterator(_Base::begin(), this); }
449 { return const_iterator(_Base::end(), this); }
458 insert(const value_type& __obj)
459 { return iterator(_Base::insert(__obj), this); }
462 insert(iterator, const value_type& __obj)
463 { return iterator(_Base::insert(__obj), this); }
466 insert(const_iterator, const value_type& __obj)
467 { return const_iterator(_Base::insert(__obj), this); }
470 insert(std::initializer_list<value_type> __l)
471 { _Base::insert(__l); }
473 template<typename _InputIterator>
475 insert(_InputIterator __first, _InputIterator __last)
477 __glibcxx_check_valid_range(__first, __last);
478 _Base::insert(__first, __last);
482 find(const key_type& __key)
483 { return iterator(_Base::find(__key), this); }
486 find(const key_type& __key) const
487 { return const_iterator(_Base::find(__key), this); }
489 std::pair<iterator, iterator>
490 equal_range(const key_type& __key)
492 typedef typename _Base::iterator _Base_iterator;
493 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
494 __pair_type __res = _Base::equal_range(__key);
495 return std::make_pair(iterator(__res.first, this),
496 iterator(__res.second, this));
499 std::pair<const_iterator, const_iterator>
500 equal_range(const key_type& __key) const
502 typedef typename _Base::const_iterator _Base_iterator;
503 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
504 __pair_type __res = _Base::equal_range(__key);
505 return std::make_pair(const_iterator(__res.first, this),
506 const_iterator(__res.second, this));
510 erase(const key_type& __key)
513 iterator __victim(_Base::find(__key), this);
514 if (__victim != end())
516 this->erase(__victim);
525 __glibcxx_check_erase(__it);
526 __it._M_invalidate();
527 return iterator(_Base::erase(__it.base()), this);
531 erase(const_iterator __it)
533 __glibcxx_check_erase(__it);
534 __it._M_invalidate();
535 return const_iterator(_Base::erase(__it.base()), this);
539 erase(iterator __first, iterator __last)
541 __glibcxx_check_erase_range(__first, __last);
542 for (iterator __tmp = __first; __tmp != __last;)
544 iterator __victim = __tmp++;
545 __victim._M_invalidate();
547 return iterator(_Base::erase(__first.base(),
548 __last.base()), this);
552 erase(const_iterator __first, const_iterator __last)
554 __glibcxx_check_erase_range(__first, __last);
555 for (const_iterator __tmp = __first; __tmp != __last;)
557 const_iterator __victim = __tmp++;
558 __victim._M_invalidate();
560 return const_iterator(_Base::erase(__first.base(),
561 __last.base()), this);
565 _M_base() { return *this; }
568 _M_base() const { return *this; }
574 typedef typename _Base::const_iterator _Base_const_iterator;
575 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
576 this->_M_invalidate_if(_Not_equal(_M_base().end()));
580 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
582 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
583 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
586 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
588 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>&& __x,
589 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
592 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
594 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
595 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&& __y)
598 } // namespace __debug