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 /// 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)
125 operator=(initializer_list<value_type> __l)
133 swap(unordered_set& __x)
136 _Safe_base::_M_swap(__x);
143 this->_M_invalidate_all();
148 { return iterator(_Base::begin(), this); }
152 { return const_iterator(_Base::begin(), this); }
156 { return iterator(_Base::end(), this); }
160 { return const_iterator(_Base::end(), this); }
164 { return const_iterator(_Base::begin(), this); }
168 { return const_iterator(_Base::end(), this); }
176 std::pair<iterator, bool>
177 insert(const value_type& __obj)
179 typedef std::pair<typename _Base::iterator, bool> __pair_type;
180 __pair_type __res = _Base::insert(__obj);
181 return std::make_pair(iterator(__res.first, this), __res.second);
185 insert(iterator, const value_type& __obj)
187 typedef std::pair<typename _Base::iterator, bool> __pair_type;
188 __pair_type __res = _Base::insert(__obj);
189 return iterator(__res.first, this);
193 insert(const_iterator, const value_type& __obj)
195 typedef std::pair<typename _Base::iterator, bool> __pair_type;
196 __pair_type __res = _Base::insert(__obj);
197 return const_iterator(__res.first, this);
201 insert(std::initializer_list<value_type> __l)
202 { _Base::insert(__l); }
204 template<typename _InputIterator>
206 insert(_InputIterator __first, _InputIterator __last)
208 __glibcxx_check_valid_range(__first, __last);
209 _Base::insert(__first, __last);
213 find(const key_type& __key)
214 { return iterator(_Base::find(__key), this); }
217 find(const key_type& __key) const
218 { return const_iterator(_Base::find(__key), this); }
220 std::pair<iterator, iterator>
221 equal_range(const key_type& __key)
223 typedef typename _Base::iterator _Base_iterator;
224 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
225 __pair_type __res = _Base::equal_range(__key);
226 return std::make_pair(iterator(__res.first, this),
227 iterator(__res.second, this));
230 std::pair<const_iterator, const_iterator>
231 equal_range(const key_type& __key) const
233 typedef typename _Base::const_iterator _Base_iterator;
234 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
235 __pair_type __res = _Base::equal_range(__key);
236 return std::make_pair(const_iterator(__res.first, this),
237 const_iterator(__res.second, this));
241 erase(const key_type& __key)
244 iterator __victim(_Base::find(__key), this);
245 if (__victim != end())
247 this->erase(__victim);
256 __glibcxx_check_erase(__it);
257 __it._M_invalidate();
258 return iterator(_Base::erase(__it.base()), this);
262 erase(const_iterator __it)
264 __glibcxx_check_erase(__it);
265 __it._M_invalidate();
266 return const_iterator(_Base::erase(__it.base()), this);
270 erase(iterator __first, iterator __last)
272 __glibcxx_check_erase_range(__first, __last);
273 for (iterator __tmp = __first; __tmp != __last;)
275 iterator __victim = __tmp++;
276 __victim._M_invalidate();
278 return iterator(_Base::erase(__first.base(),
279 __last.base()), this);
283 erase(const_iterator __first, const_iterator __last)
285 __glibcxx_check_erase_range(__first, __last);
286 for (const_iterator __tmp = __first; __tmp != __last;)
288 const_iterator __victim = __tmp++;
289 __victim._M_invalidate();
291 return const_iterator(_Base::erase(__first.base(),
292 __last.base()), this);
296 _M_base() { return *this; }
299 _M_base() const { return *this; }
305 typedef typename _Base::const_iterator _Base_const_iterator;
306 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
307 this->_M_invalidate_if(_Not_equal(_M_base().end()));
311 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
313 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
314 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
318 /// Class std::unordered_multiset with safety/checking/debug instrumentation.
319 template<typename _Value,
320 typename _Hash = std::hash<_Value>,
321 typename _Pred = std::equal_to<_Value>,
322 typename _Alloc = std::allocator<_Value> >
323 class unordered_multiset
324 : public _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
325 public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash,
328 typedef _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash,
329 _Pred, _Alloc> _Base;
330 typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base;
333 typedef typename _Base::size_type size_type;
334 typedef typename _Base::hasher hasher;
335 typedef typename _Base::key_equal key_equal;
336 typedef typename _Base::allocator_type allocator_type;
338 typedef typename _Base::key_type key_type;
339 typedef typename _Base::value_type value_type;
341 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
342 unordered_multiset> iterator;
343 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
344 unordered_multiset> const_iterator;
347 unordered_multiset(size_type __n = 10,
348 const hasher& __hf = hasher(),
349 const key_equal& __eql = key_equal(),
350 const allocator_type& __a = allocator_type())
351 : _Base(__n, __hf, __eql, __a) { }
353 template<typename _InputIterator>
354 unordered_multiset(_InputIterator __f, _InputIterator __l,
356 const hasher& __hf = hasher(),
357 const key_equal& __eql = key_equal(),
358 const allocator_type& __a = allocator_type())
359 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
360 __hf, __eql, __a), _Safe_base() { }
362 unordered_multiset(const unordered_multiset& __x)
363 : _Base(__x), _Safe_base() { }
365 unordered_multiset(const _Base& __x)
366 : _Base(__x), _Safe_base() { }
368 unordered_multiset(unordered_multiset&& __x)
369 : _Base(std::forward<unordered_multiset>(__x)), _Safe_base() { }
371 unordered_multiset(initializer_list<value_type> __l,
373 const hasher& __hf = hasher(),
374 const key_equal& __eql = key_equal(),
375 const allocator_type& __a = allocator_type())
376 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
379 operator=(const unordered_multiset& __x)
381 *static_cast<_Base*>(this) = __x;
382 this->_M_invalidate_all();
387 operator=(unordered_multiset&& __x)
396 operator=(initializer_list<value_type> __l)
404 swap(unordered_multiset& __x)
407 _Safe_base::_M_swap(__x);
414 this->_M_invalidate_all();
419 { return iterator(_Base::begin(), this); }
423 { return const_iterator(_Base::begin(), this); }
427 { return iterator(_Base::end(), this); }
431 { return const_iterator(_Base::end(), this); }
435 { return const_iterator(_Base::begin(), this); }
439 { return const_iterator(_Base::end(), this); }
448 insert(const value_type& __obj)
449 { return iterator(_Base::insert(__obj), this); }
452 insert(iterator, const value_type& __obj)
453 { return iterator(_Base::insert(__obj), this); }
456 insert(const_iterator, const value_type& __obj)
457 { return const_iterator(_Base::insert(__obj), this); }
460 insert(std::initializer_list<value_type> __l)
461 { _Base::insert(__l); }
463 template<typename _InputIterator>
465 insert(_InputIterator __first, _InputIterator __last)
467 __glibcxx_check_valid_range(__first, __last);
468 _Base::insert(__first, __last);
472 find(const key_type& __key)
473 { return iterator(_Base::find(__key), this); }
476 find(const key_type& __key) const
477 { return const_iterator(_Base::find(__key), this); }
479 std::pair<iterator, iterator>
480 equal_range(const key_type& __key)
482 typedef typename _Base::iterator _Base_iterator;
483 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
484 __pair_type __res = _Base::equal_range(__key);
485 return std::make_pair(iterator(__res.first, this),
486 iterator(__res.second, this));
489 std::pair<const_iterator, const_iterator>
490 equal_range(const key_type& __key) const
492 typedef typename _Base::const_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(const_iterator(__res.first, this),
496 const_iterator(__res.second, this));
500 erase(const key_type& __key)
503 iterator __victim(_Base::find(__key), this);
504 if (__victim != end())
506 this->erase(__victim);
515 __glibcxx_check_erase(__it);
516 __it._M_invalidate();
517 return iterator(_Base::erase(__it.base()), this);
521 erase(const_iterator __it)
523 __glibcxx_check_erase(__it);
524 __it._M_invalidate();
525 return const_iterator(_Base::erase(__it.base()), this);
529 erase(iterator __first, iterator __last)
531 __glibcxx_check_erase_range(__first, __last);
532 for (iterator __tmp = __first; __tmp != __last;)
534 iterator __victim = __tmp++;
535 __victim._M_invalidate();
537 return iterator(_Base::erase(__first.base(),
538 __last.base()), this);
542 erase(const_iterator __first, const_iterator __last)
544 __glibcxx_check_erase_range(__first, __last);
545 for (const_iterator __tmp = __first; __tmp != __last;)
547 const_iterator __victim = __tmp++;
548 __victim._M_invalidate();
550 return const_iterator(_Base::erase(__first.base(),
551 __last.base()), this);
555 _M_base() { return *this; }
558 _M_base() const { return *this; }
564 typedef typename _Base::const_iterator _Base_const_iterator;
565 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
566 this->_M_invalidate_if(_Not_equal(_M_base().end()));
570 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
572 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
573 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
576 } // namespace __debug