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
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_D::unordered_set<_Value, _Hash, _Pred, _Alloc>,
00052 public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash,
00053 _Pred, _Alloc> >
00054 {
00055 typedef _GLIBCXX_STD_D::unordered_set<_Value, _Hash,
00056 _Pred, _Alloc> _Base;
00057 typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base;
00058
00059 public:
00060 typedef typename _Base::size_type size_type;
00061 typedef typename _Base::hasher hasher;
00062 typedef typename _Base::key_equal key_equal;
00063 typedef typename _Base::allocator_type allocator_type;
00064
00065 typedef typename _Base::key_type key_type;
00066 typedef typename _Base::value_type value_type;
00067
00068 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
00069 unordered_set> iterator;
00070 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
00071 unordered_set> const_iterator;
00072
00073 explicit
00074 unordered_set(size_type __n = 10,
00075 const hasher& __hf = hasher(),
00076 const key_equal& __eql = key_equal(),
00077 const allocator_type& __a = allocator_type())
00078 : _Base(__n, __hf, __eql, __a) { }
00079
00080 template<typename _InputIterator>
00081 unordered_set(_InputIterator __f, _InputIterator __l,
00082 size_type __n = 10,
00083 const hasher& __hf = hasher(),
00084 const key_equal& __eql = key_equal(),
00085 const allocator_type& __a = allocator_type())
00086 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
00087 __hf, __eql, __a), _Safe_base() { }
00088
00089 unordered_set(const unordered_set& __x)
00090 : _Base(__x), _Safe_base() { }
00091
00092 unordered_set(const _Base& __x)
00093 : _Base(__x), _Safe_base() { }
00094
00095 unordered_set(unordered_set&& __x)
00096 : _Base(std::forward<unordered_set>(__x)), _Safe_base() { }
00097
00098 unordered_set(initializer_list<value_type> __l,
00099 size_type __n = 10,
00100 const hasher& __hf = hasher(),
00101 const key_equal& __eql = key_equal(),
00102 const allocator_type& __a = allocator_type())
00103 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
00104
00105 unordered_set&
00106 operator=(const unordered_set& __x)
00107 {
00108 *static_cast<_Base*>(this) = __x;
00109 this->_M_invalidate_all();
00110 return *this;
00111 }
00112
00113 unordered_set&
00114 operator=(unordered_set&& __x)
00115 {
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(const_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 void
00192 insert(std::initializer_list<value_type> __l)
00193 { _Base::insert(__l); }
00194
00195 template<typename _InputIterator>
00196 void
00197 insert(_InputIterator __first, _InputIterator __last)
00198 {
00199 __glibcxx_check_valid_range(__first, __last);
00200 _Base::insert(__first, __last);
00201 }
00202
00203 iterator
00204 find(const key_type& __key)
00205 { return iterator(_Base::find(__key), this); }
00206
00207 const_iterator
00208 find(const key_type& __key) const
00209 { return const_iterator(_Base::find(__key), this); }
00210
00211 std::pair<iterator, iterator>
00212 equal_range(const key_type& __key)
00213 {
00214 typedef typename _Base::iterator _Base_iterator;
00215 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
00216 __pair_type __res = _Base::equal_range(__key);
00217 return std::make_pair(iterator(__res.first, this),
00218 iterator(__res.second, this));
00219 }
00220
00221 std::pair<const_iterator, const_iterator>
00222 equal_range(const key_type& __key) const
00223 {
00224 typedef typename _Base::const_iterator _Base_iterator;
00225 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
00226 __pair_type __res = _Base::equal_range(__key);
00227 return std::make_pair(const_iterator(__res.first, this),
00228 const_iterator(__res.second, this));
00229 }
00230
00231 size_type
00232 erase(const key_type& __key)
00233 {
00234 size_type __ret(0);
00235 iterator __victim(_Base::find(__key), this);
00236 if (__victim != end())
00237 {
00238 this->erase(__victim);
00239 __ret = 1;
00240 }
00241 return __ret;
00242 }
00243
00244 iterator
00245 erase(const_iterator __it)
00246 {
00247 __glibcxx_check_erase(__it);
00248 __it._M_invalidate();
00249 return iterator(_Base::erase(__it.base()), this);
00250 }
00251
00252 iterator
00253 erase(const_iterator __first, const_iterator __last)
00254 {
00255 __glibcxx_check_erase_range(__first, __last);
00256 for (const_iterator __tmp = __first; __tmp != __last;)
00257 {
00258 const_iterator __victim = __tmp++;
00259 __victim._M_invalidate();
00260 }
00261 return iterator(_Base::erase(__first.base(),
00262 __last.base()), this);
00263 }
00264
00265 _Base&
00266 _M_base() { return *this; }
00267
00268 const _Base&
00269 _M_base() const { return *this; }
00270
00271 private:
00272 void
00273 _M_invalidate_all()
00274 {
00275 typedef typename _Base::const_iterator _Base_const_iterator;
00276 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00277 this->_M_invalidate_if(_Not_equal(_M_base().end()));
00278 }
00279 };
00280
00281 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00282 inline void
00283 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00284 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00285 { __x.swap(__y); }
00286
00287 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00288 inline bool
00289 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00290 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00291 { return __x._M_equal(__y); }
00292
00293 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00294 inline bool
00295 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
00296 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
00297 { return !(__x == __y); }
00298
00299
00300
00301 template<typename _Value,
00302 typename _Hash = std::hash<_Value>,
00303 typename _Pred = std::equal_to<_Value>,
00304 typename _Alloc = std::allocator<_Value> >
00305 class unordered_multiset
00306 : public _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
00307 public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash,
00308 _Pred, _Alloc> >
00309 {
00310 typedef _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash,
00311 _Pred, _Alloc> _Base;
00312 typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base;
00313
00314 public:
00315 typedef typename _Base::size_type size_type;
00316 typedef typename _Base::hasher hasher;
00317 typedef typename _Base::key_equal key_equal;
00318 typedef typename _Base::allocator_type allocator_type;
00319
00320 typedef typename _Base::key_type key_type;
00321 typedef typename _Base::value_type value_type;
00322
00323 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
00324 unordered_multiset> iterator;
00325 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
00326 unordered_multiset> const_iterator;
00327
00328 explicit
00329 unordered_multiset(size_type __n = 10,
00330 const hasher& __hf = hasher(),
00331 const key_equal& __eql = key_equal(),
00332 const allocator_type& __a = allocator_type())
00333 : _Base(__n, __hf, __eql, __a) { }
00334
00335 template<typename _InputIterator>
00336 unordered_multiset(_InputIterator __f, _InputIterator __l,
00337 size_type __n = 10,
00338 const hasher& __hf = hasher(),
00339 const key_equal& __eql = key_equal(),
00340 const allocator_type& __a = allocator_type())
00341 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
00342 __hf, __eql, __a), _Safe_base() { }
00343
00344 unordered_multiset(const unordered_multiset& __x)
00345 : _Base(__x), _Safe_base() { }
00346
00347 unordered_multiset(const _Base& __x)
00348 : _Base(__x), _Safe_base() { }
00349
00350 unordered_multiset(unordered_multiset&& __x)
00351 : _Base(std::forward<unordered_multiset>(__x)), _Safe_base() { }
00352
00353 unordered_multiset(initializer_list<value_type> __l,
00354 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(__l, __n, __hf, __eql, __a), _Safe_base() { }
00359
00360 unordered_multiset&
00361 operator=(const unordered_multiset& __x)
00362 {
00363 *static_cast<_Base*>(this) = __x;
00364 this->_M_invalidate_all();
00365 return *this;
00366 }
00367
00368 unordered_multiset&
00369 operator=(unordered_multiset&& __x)
00370 {
00371
00372
00373 clear();
00374 swap(__x);
00375 return *this;
00376 }
00377
00378 unordered_multiset&
00379 operator=(initializer_list<value_type> __l)
00380 {
00381 this->clear();
00382 this->insert(__l);
00383 return *this;
00384 }
00385
00386 void
00387 swap(unordered_multiset& __x)
00388 {
00389 _Base::swap(__x);
00390 _Safe_base::_M_swap(__x);
00391 }
00392
00393 void
00394 clear()
00395 {
00396 _Base::clear();
00397 this->_M_invalidate_all();
00398 }
00399
00400 iterator
00401 begin()
00402 { return iterator(_Base::begin(), this); }
00403
00404 const_iterator
00405 begin() const
00406 { return const_iterator(_Base::begin(), this); }
00407
00408 iterator
00409 end()
00410 { return iterator(_Base::end(), this); }
00411
00412 const_iterator
00413 end() const
00414 { return const_iterator(_Base::end(), this); }
00415
00416 const_iterator
00417 cbegin() const
00418 { return const_iterator(_Base::begin(), this); }
00419
00420 const_iterator
00421 cend() const
00422 { return const_iterator(_Base::end(), this); }
00423
00424
00425 using _Base::begin;
00426 using _Base::end;
00427 using _Base::cbegin;
00428 using _Base::cend;
00429
00430 iterator
00431 insert(const value_type& __obj)
00432 { return iterator(_Base::insert(__obj), this); }
00433
00434 iterator
00435 insert(const_iterator, const value_type& __obj)
00436 { return iterator(_Base::insert(__obj), this); }
00437
00438 void
00439 insert(std::initializer_list<value_type> __l)
00440 { _Base::insert(__l); }
00441
00442 template<typename _InputIterator>
00443 void
00444 insert(_InputIterator __first, _InputIterator __last)
00445 {
00446 __glibcxx_check_valid_range(__first, __last);
00447 _Base::insert(__first, __last);
00448 }
00449
00450 iterator
00451 find(const key_type& __key)
00452 { return iterator(_Base::find(__key), this); }
00453
00454 const_iterator
00455 find(const key_type& __key) const
00456 { return const_iterator(_Base::find(__key), this); }
00457
00458 std::pair<iterator, iterator>
00459 equal_range(const key_type& __key)
00460 {
00461 typedef typename _Base::iterator _Base_iterator;
00462 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
00463 __pair_type __res = _Base::equal_range(__key);
00464 return std::make_pair(iterator(__res.first, this),
00465 iterator(__res.second, this));
00466 }
00467
00468 std::pair<const_iterator, const_iterator>
00469 equal_range(const key_type& __key) const
00470 {
00471 typedef typename _Base::const_iterator _Base_iterator;
00472 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
00473 __pair_type __res = _Base::equal_range(__key);
00474 return std::make_pair(const_iterator(__res.first, this),
00475 const_iterator(__res.second, this));
00476 }
00477
00478 size_type
00479 erase(const key_type& __key)
00480 {
00481 size_type __ret(0);
00482 iterator __victim(_Base::find(__key), this);
00483 if (__victim != end())
00484 {
00485 this->erase(__victim);
00486 __ret = 1;
00487 }
00488 return __ret;
00489 }
00490
00491 iterator
00492 erase(const_iterator __it)
00493 {
00494 __glibcxx_check_erase(__it);
00495 __it._M_invalidate();
00496 return iterator(_Base::erase(__it.base()), this);
00497 }
00498
00499 iterator
00500 erase(const_iterator __first, const_iterator __last)
00501 {
00502 __glibcxx_check_erase_range(__first, __last);
00503 for (const_iterator __tmp = __first; __tmp != __last;)
00504 {
00505 const_iterator __victim = __tmp++;
00506 __victim._M_invalidate();
00507 }
00508 return iterator(_Base::erase(__first.base(),
00509 __last.base()), this);
00510 }
00511
00512 _Base&
00513 _M_base() { return *this; }
00514
00515 const _Base&
00516 _M_base() const { return *this; }
00517
00518 private:
00519 void
00520 _M_invalidate_all()
00521 {
00522 typedef typename _Base::const_iterator _Base_const_iterator;
00523 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00524 this->_M_invalidate_if(_Not_equal(_M_base().end()));
00525 }
00526 };
00527
00528 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00529 inline void
00530 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00531 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00532 { __x.swap(__y); }
00533
00534 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00535 inline bool
00536 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00537 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00538 { return __x._M_equal(__y); }
00539
00540 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
00541 inline bool
00542 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
00543 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
00544 { return !(__x == __y); }
00545
00546 }
00547 }
00548
00549 #endif // __GXX_EXPERIMENTAL_CXX0X__
00550
00551 #endif