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_MAP
00031 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
00032
00033 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00034 # include <unordered_map>
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 _Key, typename _Tp,
00048 typename _Hash = std::hash<_Key>,
00049 typename _Pred = std::equal_to<_Key>,
00050 typename _Alloc = std::allocator<_Key> >
00051 class unordered_map
00052 : public _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
00053 public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash,
00054 _Pred, _Alloc> >
00055 {
00056 typedef _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash,
00057 _Pred, _Alloc> _Base;
00058 typedef __gnu_debug::_Safe_sequence<unordered_map> _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_map> iterator;
00071 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
00072 unordered_map> const_iterator;
00073
00074 explicit
00075 unordered_map(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_map(_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_map(const unordered_map& __x)
00091 : _Base(__x), _Safe_base() { }
00092
00093 unordered_map(const _Base& __x)
00094 : _Base(__x), _Safe_base() { }
00095
00096 unordered_map(unordered_map&& __x)
00097 : _Base(std::forward<unordered_map>(__x)), _Safe_base() { }
00098
00099 unordered_map(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_map&
00107 operator=(const unordered_map& __x)
00108 {
00109 *static_cast<_Base*>(this) = __x;
00110 this->_M_invalidate_all();
00111 return *this;
00112 }
00113
00114 unordered_map&
00115 operator=(unordered_map&& __x)
00116 {
00117
00118 clear();
00119 swap(__x);
00120 return *this;
00121 }
00122
00123 unordered_map&
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_map&& __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 _Key, typename _Tp, typename _Hash,
00311 typename _Pred, typename _Alloc>
00312 inline void
00313 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00314 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00315 { __x.swap(__y); }
00316
00317 template<typename _Key, typename _Tp, typename _Hash,
00318 typename _Pred, typename _Alloc>
00319 inline void
00320 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&& __x,
00321 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00322 { __x.swap(__y); }
00323
00324 template<typename _Key, typename _Tp, typename _Hash,
00325 typename _Pred, typename _Alloc>
00326 inline void
00327 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00328 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&& __y)
00329 { __x.swap(__y); }
00330
00331
00332 template<typename _Key, typename _Tp,
00333 typename _Hash = std::hash<_Key>,
00334 typename _Pred = std::equal_to<_Key>,
00335 typename _Alloc = std::allocator<_Key> >
00336 class unordered_multimap
00337 : public _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,
00338 _Pred, _Alloc>,
00339 public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,
00340 _Pred, _Alloc> >
00341 {
00342 typedef _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,
00343 _Pred, _Alloc> _Base;
00344 typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base;
00345
00346 public:
00347 typedef typename _Base::size_type size_type;
00348 typedef typename _Base::hasher hasher;
00349 typedef typename _Base::key_equal key_equal;
00350 typedef typename _Base::allocator_type allocator_type;
00351
00352 typedef typename _Base::key_type key_type;
00353 typedef typename _Base::value_type value_type;
00354
00355 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
00356 unordered_multimap> iterator;
00357 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
00358 unordered_multimap> const_iterator;
00359
00360 explicit
00361 unordered_multimap(size_type __n = 10,
00362 const hasher& __hf = hasher(),
00363 const key_equal& __eql = key_equal(),
00364 const allocator_type& __a = allocator_type())
00365 : _Base(__n, __hf, __eql, __a) { }
00366
00367 template<typename _InputIterator>
00368 unordered_multimap(_InputIterator __f, _InputIterator __l,
00369 size_type __n = 10,
00370 const hasher& __hf = hasher(),
00371 const key_equal& __eql = key_equal(),
00372 const allocator_type& __a = allocator_type())
00373 : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
00374 __hf, __eql, __a), _Safe_base() { }
00375
00376 unordered_multimap(const unordered_multimap& __x)
00377 : _Base(__x), _Safe_base() { }
00378
00379 unordered_multimap(const _Base& __x)
00380 : _Base(__x), _Safe_base() { }
00381
00382 unordered_multimap(unordered_multimap&& __x)
00383 : _Base(std::forward<unordered_multimap>(__x)), _Safe_base() { }
00384
00385 unordered_multimap(initializer_list<value_type> __l,
00386 size_type __n = 10,
00387 const hasher& __hf = hasher(),
00388 const key_equal& __eql = key_equal(),
00389 const allocator_type& __a = allocator_type())
00390 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
00391
00392 unordered_multimap&
00393 operator=(const unordered_multimap& __x)
00394 {
00395 *static_cast<_Base*>(this) = __x;
00396 this->_M_invalidate_all();
00397 return *this;
00398 }
00399
00400 unordered_multimap&
00401 operator=(unordered_multimap&& __x)
00402 {
00403
00404 clear();
00405 swap(__x);
00406 return *this;
00407 }
00408
00409 unordered_multimap&
00410 operator=(initializer_list<value_type> __l)
00411 {
00412 this->clear();
00413 this->insert(__l);
00414 return *this;
00415 }
00416
00417 void
00418 swap(unordered_multimap&& __x)
00419 {
00420 _Base::swap(__x);
00421 _Safe_base::_M_swap(__x);
00422 }
00423
00424 void
00425 clear()
00426 {
00427 _Base::clear();
00428 this->_M_invalidate_all();
00429 }
00430
00431 iterator
00432 begin()
00433 { return iterator(_Base::begin(), this); }
00434
00435 const_iterator
00436 begin() const
00437 { return const_iterator(_Base::begin(), this); }
00438
00439 iterator
00440 end()
00441 { return iterator(_Base::end(), this); }
00442
00443 const_iterator
00444 end() const
00445 { return const_iterator(_Base::end(), this); }
00446
00447 const_iterator
00448 cbegin() const
00449 { return const_iterator(_Base::begin(), this); }
00450
00451 const_iterator
00452 cend() const
00453 { return const_iterator(_Base::end(), this); }
00454
00455
00456 using _Base::begin;
00457 using _Base::end;
00458 using _Base::cbegin;
00459 using _Base::cend;
00460
00461 iterator
00462 insert(const value_type& __obj)
00463 { return iterator(_Base::insert(__obj), this); }
00464
00465 iterator
00466 insert(iterator, const value_type& __obj)
00467 { return iterator(_Base::insert(__obj), this); }
00468
00469 const_iterator
00470 insert(const_iterator, const value_type& __obj)
00471 { return const_iterator(_Base::insert(__obj), this); }
00472
00473 void
00474 insert(std::initializer_list<value_type> __l)
00475 { _Base::insert(__l); }
00476
00477 template<typename _InputIterator>
00478 void
00479 insert(_InputIterator __first, _InputIterator __last)
00480 {
00481 __glibcxx_check_valid_range(__first, __last);
00482 _Base::insert(__first, __last);
00483 }
00484
00485 iterator
00486 find(const key_type& __key)
00487 { return iterator(_Base::find(__key), this); }
00488
00489 const_iterator
00490 find(const key_type& __key) const
00491 { return const_iterator(_Base::find(__key), this); }
00492
00493 std::pair<iterator, iterator>
00494 equal_range(const key_type& __key)
00495 {
00496 typedef typename _Base::iterator _Base_iterator;
00497 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
00498 __pair_type __res = _Base::equal_range(__key);
00499 return std::make_pair(iterator(__res.first, this),
00500 iterator(__res.second, this));
00501 }
00502
00503 std::pair<const_iterator, const_iterator>
00504 equal_range(const key_type& __key) const
00505 {
00506 typedef typename _Base::const_iterator _Base_iterator;
00507 typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
00508 __pair_type __res = _Base::equal_range(__key);
00509 return std::make_pair(const_iterator(__res.first, this),
00510 const_iterator(__res.second, this));
00511 }
00512
00513 size_type
00514 erase(const key_type& __key)
00515 {
00516 size_type __ret(0);
00517 iterator __victim(_Base::find(__key), this);
00518 if (__victim != end())
00519 {
00520 this->erase(__victim);
00521 __ret = 1;
00522 }
00523 return __ret;
00524 }
00525
00526 iterator
00527 erase(iterator __it)
00528 {
00529 __glibcxx_check_erase(__it);
00530 __it._M_invalidate();
00531 return iterator(_Base::erase(__it.base()), this);
00532 }
00533
00534 const_iterator
00535 erase(const_iterator __it)
00536 {
00537 __glibcxx_check_erase(__it);
00538 __it._M_invalidate();
00539 return const_iterator(_Base::erase(__it.base()), this);
00540 }
00541
00542 iterator
00543 erase(iterator __first, iterator __last)
00544 {
00545 __glibcxx_check_erase_range(__first, __last);
00546 for (iterator __tmp = __first; __tmp != __last;)
00547 {
00548 iterator __victim = __tmp++;
00549 __victim._M_invalidate();
00550 }
00551 return iterator(_Base::erase(__first.base(),
00552 __last.base()), this);
00553 }
00554
00555 const_iterator
00556 erase(const_iterator __first, const_iterator __last)
00557 {
00558 __glibcxx_check_erase_range(__first, __last);
00559 for (const_iterator __tmp = __first; __tmp != __last;)
00560 {
00561 const_iterator __victim = __tmp++;
00562 __victim._M_invalidate();
00563 }
00564 return const_iterator(_Base::erase(__first.base(),
00565 __last.base()), this);
00566 }
00567
00568 _Base&
00569 _M_base() { return *this; }
00570
00571 const _Base&
00572 _M_base() const { return *this; }
00573
00574 private:
00575 void
00576 _M_invalidate_all()
00577 {
00578 typedef typename _Base::const_iterator _Base_const_iterator;
00579 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00580 this->_M_invalidate_if(_Not_equal(_M_base().end()));
00581 }
00582 };
00583
00584 template<typename _Key, typename _Tp, typename _Hash,
00585 typename _Pred, typename _Alloc>
00586 inline void
00587 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00588 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00589 { __x.swap(__y); }
00590
00591 template<typename _Key, typename _Tp, typename _Hash,
00592 typename _Pred, typename _Alloc>
00593 inline void
00594 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&& __x,
00595 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00596 { __x.swap(__y); }
00597
00598 template<typename _Key, typename _Tp, typename _Hash,
00599 typename _Pred, typename _Alloc>
00600 inline void
00601 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00602 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&& __y)
00603 { __x.swap(__y); }
00604
00605 }
00606 }
00607
00608 #endif