00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
00031 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
00032
00033 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00034 # include <bits/c++0x_warning.h>
00035 #else
00036 # include <unordered_set>
00037
00038 #include <debug/safe_sequence.h>
00039 #include <debug/safe_iterator.h>
00040
00041 namespace std _GLIBCXX_VISIBILITY(default)
00042 {
00043 namespace __debug
00044 {
00045
00046 template<typename _Value,
00047 typename _Hash = std::hash<_Value>,
00048 typename _Pred = std::equal_to<_Value>,
00049 typename _Alloc = std::allocator<_Value> >
00050 class unordered_set
00051 : public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>,
00052 public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash,
00053 _Pred, _Alloc> >
00054 {
00055 typedef _GLIBCXX_STD_C::unordered_set<_Value, _Hash,
00056 _Pred, _Alloc> _Base;
00057 typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base;
00058 typedef typename _Base::const_iterator _Base_const_iterator;
00059 typedef typename _Base::iterator _Base_iterator;
00060 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00061
00062 public:
00063 typedef typename _Base::size_type size_type;
00064 typedef typename _Base::hasher hasher;
00065 typedef typename _Base::key_equal key_equal;
00066 typedef typename _Base::allocator_type allocator_type;
00067
00068 typedef typename _Base::key_type key_type;
00069 typedef typename _Base::value_type value_type;
00070
00071 typedef __gnu_debug::_Safe_iterator<_Base_iterator,
00072 unordered_set> iterator;
00073 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00074 unordered_set> const_iterator;
00075
00076 explicit
00077 unordered_set(size_type __n = 10,
00078 const hasher& __hf = hasher(),
00079 const key_equal& __eql = key_equal(),
00080 const allocator_type& __a = allocator_type())
00081 : _Base(__n, __hf, __eql, __a) { }
00082
00083 template<typename _InputIterator>
00084 unordered_set(_InputIterator __first, _InputIterator __last,
00085 size_type __n = 0,
00086 const hasher& __hf = hasher(),
00087 const key_equal& __eql = key_equal(),
00088 const allocator_type& __a = allocator_type())
00089 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00090 __last)),
00091 __gnu_debug::__base(__last), __n,
00092 __hf, __eql, __a), _Safe_base() { }
00093
00094 unordered_set(const unordered_set& __x)
00095 : _Base(__x), _Safe_base() { }
00096
00097 unordered_set(const _Base& __x)
00098 : _Base(__x), _Safe_base() { }
00099
00100 unordered_set(unordered_set&& __x)
00101 : _Base(std::move(__x)), _Safe_base() { }
00102
00103 unordered_set(initializer_list<value_type> __l,
00104 size_type __n = 0,
00105 const hasher& __hf = hasher(),
00106 const key_equal& __eql = key_equal(),
00107 const allocator_type& __a = allocator_type())
00108 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
00109
00110 unordered_set&
00111 operator=(const unordered_set& __x)
00112 {
00113 *static_cast<_Base*>(this) = __x;
00114 this->_M_invalidate_all();
00115 return *this;
00116 }
00117
00118 unordered_set&
00119 operator=(unordered_set&& __x)
00120 {
00121
00122
00123 clear();
00124 swap(__x);
00125 return *this;
00126 }
00127
00128 unordered_set&
00129 operator=(initializer_list<value_type> __l)
00130 {
00131 this->clear();
00132 this->insert(__l);
00133 return *this;
00134 }
00135
00136 void
00137 swap(unordered_set& __x)
00138 {
00139 _Base::swap(__x);
00140 _Safe_base::_M_swap(__x);
00141 }
00142
00143 void
00144 clear()
00145 {
00146 _Base::clear();
00147 this->_M_invalidate_all();
00148 }
00149
00150 iterator
00151 begin()
00152 { return iterator(_Base::begin(), this); }
00153
00154 const_iterator
00155 begin() const
00156 { return const_iterator(_Base::begin(), this); }
00157
00158 iterator
00159 end()
00160 { return iterator(_Base::end(), this); }
00161
00162 const_iterator
00163 end() const
00164 { return const_iterator(_Base::end(), this); }
00165
00166 const_iterator
00167 cbegin() const
00168 { return const_iterator(_Base::begin(), this); }
00169
00170 const_iterator
00171 cend() const
00172 { return const_iterator(_Base::end(), this); }
00173
00174
00175 using _Base::begin;
00176 using _Base::end;
00177 using _Base::cbegin;
00178 using _Base::cend;
00179
00180 std::pair<iterator, bool>
00181 insert(const value_type& __obj)
00182 {
00183 typedef std::pair<_Base_iterator, bool> __pair_type;
00184 __pair_type __res = _Base::insert(__obj);
00185 return std::make_pair(iterator(__res.first, this), __res.second);
00186 }
00187
00188 iterator
00189 insert(const_iterator __hint, const value_type& __obj)
00190 {
00191 __glibcxx_check_insert(__hint);
00192 return iterator(_Base::insert(__hint.base(), __obj), this);
00193 }
00194
00195 std::pair<iterator, bool>
00196 insert(value_type&& __obj)
00197 {
00198 typedef std::pair<typename _Base::iterator, bool> __pair_type;
00199 __pair_type __res = _Base::insert(std::move(__obj));
00200 return std::make_pair(iterator(__res.first, this), __res.second);
00201 }
00202
00203 iterator
00204 insert(const_iterator __hint, value_type&& __obj)
00205 {
00206 __glibcxx_check_insert(__hint);
00207 return iterator(_Base::insert(__hint.base(), std::move(__obj)), this);
00208 }
00209
00210 void
00211 insert(std::initializer_list<value_type> __l)
00212 { _Base::insert(__l); }
00213
00214 template<typename _InputIterator>
00215 void
00216 insert(_InputIterator __first, _InputIterator __last)
00217 {
00218 __glibcxx_check_valid_range(__first, __last);
00219 _Base::insert(__gnu_debug::__base(__first),
00220 __gnu_debug::__base(__last));
00221 }
00222
00223 iterator
00224 find(const key_type& __key)
00225 { return iterator(_Base::find(__key), this); }
00226
00227 const_iterator
00228 find(const key_type& __key) const
00229 { return const_iterator(_Base::find(__key), this); }
00230
00231 std::pair<iterator, iterator>
00232 equal_range(const key_type& __key)
00233 {
00234 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
00235 __pair_type __res = _Base::equal_range(__key);
00236 return std::make_pair(iterator(__res.first, this),
00237 iterator(__res.second, this));
00238 }
00239
00240 std::pair<const_iterator, const_iterator>
00241 equal_range(const key_type& __key) const
00242 {
00243 std::pair<_Base_const_iterator, _Base_const_iterator>
00244 __res = _Base::equal_range(__key);
00245 return std::make_pair(const_iterator(__res.first, this),
00246 const_iterator(__res.second, this));
00247 }
00248
00249 size_type
00250 erase(const key_type& __key)
00251 {
00252 size_type __ret(0);
00253 _Base_iterator __victim(_Base::find(__key));
00254 if (__victim != _Base::end())
00255 {
00256 this->_M_invalidate_if(_Equal(__victim));
00257 _Base::erase(__victim);
00258 __ret = 1;
00259 }
00260 return __ret;
00261 }
00262
00263 iterator
00264 erase(const_iterator __it)
00265 {
00266 __glibcxx_check_erase(__it);
00267 this->_M_invalidate_if(_Equal(__it.base()));
00268 return iterator(_Base::erase(__it.base()), this);
00269 }
00270
00271 iterator
00272 erase(const_iterator __first, const_iterator __last)
00273 {
00274 __glibcxx_check_erase_range(__first, __last);
00275 for (_Base_const_iterator __tmp = __first.base();
00276 __tmp != __last.base(); ++__tmp)
00277 {
00278 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00279 _M_message(__gnu_debug::__msg_valid_range)
00280 ._M_iterator(__first, "first")
00281 ._M_iterator(__last, "last"));
00282 this->_M_invalidate_if(_Equal(__tmp));
00283 }
00284 return iterator(_Base::erase(__first.base(),
00285 __last.base()), this);
00286 }
00287
00288 _Base&
00289 _M_base() { return *this; }
00290
00291 const _Base&
00292 _M_base() const { return *this; }
00293
00294 private:
00295 void
00296 _M_invalidate_all()
00297 {
00298 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00299 this->_M_invalidate_if(_Not_equal(_Base::end()));
00300 }
00301 };
00302
00303 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00304 inline void
00305 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00306 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00307 { __x.swap(__y); }
00308
00309 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00310 inline bool
00311 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00312 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00313 { return __x._M_equal(__y); }
00314
00315 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00316 inline bool
00317 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00318 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00319 { return !(__x == __y); }
00320
00321
00322
00323 template<typename _Value,
00324 typename _Hash = std::hash<_Value>,
00325 typename _Pred = std::equal_to<_Value>,
00326 typename _Alloc = std::allocator<_Value> >
00327 class unordered_multiset
00328 : public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
00329 public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash,
00330 _Pred, _Alloc> >
00331 {
00332 typedef _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash,
00333 _Pred, _Alloc> _Base;
00334 typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base;
00335 typedef typename _Base::const_iterator _Base_const_iterator;
00336 typedef typename _Base::iterator _Base_iterator;
00337 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00338
00339 public:
00340 typedef typename _Base::size_type size_type;
00341 typedef typename _Base::hasher hasher;
00342 typedef typename _Base::key_equal key_equal;
00343 typedef typename _Base::allocator_type allocator_type;
00344
00345 typedef typename _Base::key_type key_type;
00346 typedef typename _Base::value_type value_type;
00347
00348 typedef __gnu_debug::_Safe_iterator<_Base_iterator,
00349 unordered_multiset> iterator;
00350 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00351 unordered_multiset> const_iterator;
00352
00353 explicit
00354 unordered_multiset(size_type __n = 10,
00355 const hasher& __hf = hasher(),
00356 const key_equal& __eql = key_equal(),
00357 const allocator_type& __a = allocator_type())
00358 : _Base(__n, __hf, __eql, __a) { }
00359
00360 template<typename _InputIterator>
00361 unordered_multiset(_InputIterator __first, _InputIterator __last,
00362 size_type __n = 0,
00363 const hasher& __hf = hasher(),
00364 const key_equal& __eql = key_equal(),
00365 const allocator_type& __a = allocator_type())
00366 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00367 __last)),
00368 __gnu_debug::__base(__last), __n,
00369 __hf, __eql, __a), _Safe_base() { }
00370
00371 unordered_multiset(const unordered_multiset& __x)
00372 : _Base(__x), _Safe_base() { }
00373
00374 unordered_multiset(const _Base& __x)
00375 : _Base(__x), _Safe_base() { }
00376
00377 unordered_multiset(unordered_multiset&& __x)
00378 : _Base(std::move(__x)), _Safe_base() { }
00379
00380 unordered_multiset(initializer_list<value_type> __l,
00381 size_type __n = 0,
00382 const hasher& __hf = hasher(),
00383 const key_equal& __eql = key_equal(),
00384 const allocator_type& __a = allocator_type())
00385 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
00386
00387 unordered_multiset&
00388 operator=(const unordered_multiset& __x)
00389 {
00390 *static_cast<_Base*>(this) = __x;
00391 this->_M_invalidate_all();
00392 return *this;
00393 }
00394
00395 unordered_multiset&
00396 operator=(unordered_multiset&& __x)
00397 {
00398
00399
00400 clear();
00401 swap(__x);
00402 return *this;
00403 }
00404
00405 unordered_multiset&
00406 operator=(initializer_list<value_type> __l)
00407 {
00408 this->clear();
00409 this->insert(__l);
00410 return *this;
00411 }
00412
00413 void
00414 swap(unordered_multiset& __x)
00415 {
00416 _Base::swap(__x);
00417 _Safe_base::_M_swap(__x);
00418 }
00419
00420 void
00421 clear()
00422 {
00423 _Base::clear();
00424 this->_M_invalidate_all();
00425 }
00426
00427 iterator
00428 begin()
00429 { return iterator(_Base::begin(), this); }
00430
00431 const_iterator
00432 begin() const
00433 { return const_iterator(_Base::begin(), this); }
00434
00435 iterator
00436 end()
00437 { return iterator(_Base::end(), this); }
00438
00439 const_iterator
00440 end() const
00441 { return const_iterator(_Base::end(), this); }
00442
00443 const_iterator
00444 cbegin() const
00445 { return const_iterator(_Base::begin(), this); }
00446
00447 const_iterator
00448 cend() const
00449 { return const_iterator(_Base::end(), this); }
00450
00451
00452 using _Base::begin;
00453 using _Base::end;
00454 using _Base::cbegin;
00455 using _Base::cend;
00456
00457 iterator
00458 insert(const value_type& __obj)
00459 { return iterator(_Base::insert(__obj), this); }
00460
00461 iterator
00462 insert(const_iterator __hint, const value_type& __obj)
00463 {
00464 __glibcxx_check_insert(__hint);
00465 return iterator(_Base::insert(__hint.base(), __obj), this);
00466 }
00467
00468 iterator
00469 insert(value_type&& __obj)
00470 { return iterator(_Base::insert(std::move(__obj)), this); }
00471
00472 iterator
00473 insert(const_iterator __hint, value_type&& __obj)
00474 {
00475 __glibcxx_check_insert(__hint);
00476 return iterator(_Base::insert(__hint.base(), std::move(__obj)), this);
00477 }
00478
00479 void
00480 insert(std::initializer_list<value_type> __l)
00481 { _Base::insert(__l); }
00482
00483 template<typename _InputIterator>
00484 void
00485 insert(_InputIterator __first, _InputIterator __last)
00486 {
00487 __glibcxx_check_valid_range(__first, __last);
00488 _Base::insert(__gnu_debug::__base(__first),
00489 __gnu_debug::__base(__last));
00490 }
00491
00492 iterator
00493 find(const key_type& __key)
00494 { return iterator(_Base::find(__key), this); }
00495
00496 const_iterator
00497 find(const key_type& __key) const
00498 { return const_iterator(_Base::find(__key), this); }
00499
00500 std::pair<iterator, iterator>
00501 equal_range(const key_type& __key)
00502 {
00503 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
00504 __pair_type __res = _Base::equal_range(__key);
00505 return std::make_pair(iterator(__res.first, this),
00506 iterator(__res.second, this));
00507 }
00508
00509 std::pair<const_iterator, const_iterator>
00510 equal_range(const key_type& __key) const
00511 {
00512 std::pair<_Base_const_iterator, _Base_const_iterator>
00513 __res = _Base::equal_range(__key);
00514 return std::make_pair(const_iterator(__res.first, this),
00515 const_iterator(__res.second, this));
00516 }
00517
00518 size_type
00519 erase(const key_type& __key)
00520 {
00521 size_type __ret(0);
00522 std::pair<_Base_iterator, _Base_iterator> __pair =
00523 _Base::equal_range(__key);
00524 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
00525 {
00526 this->_M_invalidate_if(_Equal(__victim));
00527 _Base::erase(__victim++);
00528 ++__ret;
00529 }
00530 return __ret;
00531 }
00532
00533 iterator
00534 erase(const_iterator __it)
00535 {
00536 __glibcxx_check_erase(__it);
00537 this->_M_invalidate_if(_Equal(__it.base()));
00538 return iterator(_Base::erase(__it.base()), this);
00539 }
00540
00541 iterator
00542 erase(const_iterator __first, const_iterator __last)
00543 {
00544 __glibcxx_check_erase_range(__first, __last);
00545 for (_Base_const_iterator __tmp = __first.base();
00546 __tmp != __last.base(); ++__tmp)
00547 {
00548 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00549 _M_message(__gnu_debug::__msg_valid_range)
00550 ._M_iterator(__first, "first")
00551 ._M_iterator(__last, "last"));
00552 this->_M_invalidate_if(_Equal(__tmp));
00553 }
00554 return iterator(_Base::erase(__first.base(),
00555 __last.base()), this);
00556 }
00557
00558 _Base&
00559 _M_base() { return *this; }
00560
00561 const _Base&
00562 _M_base() const { return *this; }
00563
00564 private:
00565 void
00566 _M_invalidate_all()
00567 {
00568 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00569 this->_M_invalidate_if(_Not_equal(_Base::end()));
00570 }
00571 };
00572
00573 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00574 inline void
00575 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00576 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00577 { __x.swap(__y); }
00578
00579 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00580 inline bool
00581 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00582 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00583 { return __x._M_equal(__y); }
00584
00585 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00586 inline bool
00587 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00588 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00589 { return !(__x == __y); }
00590
00591 }
00592 }
00593
00594 #endif // __GXX_EXPERIMENTAL_CXX0X__
00595
00596 #endif