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