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 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00034 # include <bits/c++0x_warning.h>
00035 #else
00036 # include <unordered_map>
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 _Key, typename _Tp,
00047 typename _Hash = std::hash<_Key>,
00048 typename _Pred = std::equal_to<_Key>,
00049 typename _Alloc = std::allocator<_Key> >
00050 class unordered_map
00051 : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
00052 public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash,
00053 _Pred, _Alloc> >
00054 {
00055 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
00056 _Pred, _Alloc> _Base;
00057 typedef __gnu_debug::_Safe_sequence<unordered_map> _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_map> iterator;
00073 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00074 unordered_map> const_iterator;
00075
00076 explicit
00077 unordered_map(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_map(_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_map(const unordered_map& __x)
00095 : _Base(__x), _Safe_base() { }
00096
00097 unordered_map(const _Base& __x)
00098 : _Base(__x), _Safe_base() { }
00099
00100 unordered_map(unordered_map&& __x)
00101 : _Base(std::move(__x)), _Safe_base() { }
00102
00103 unordered_map(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_map&
00111 operator=(const unordered_map& __x)
00112 {
00113 *static_cast<_Base*>(this) = __x;
00114 this->_M_invalidate_all();
00115 return *this;
00116 }
00117
00118 unordered_map&
00119 operator=(unordered_map&& __x)
00120 {
00121
00122
00123 clear();
00124 swap(__x);
00125 return *this;
00126 }
00127
00128 unordered_map&
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_map& __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 std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
00184 return std::make_pair(iterator(__res.first, this), __res.second);
00185 }
00186
00187 iterator
00188 insert(const_iterator __hint, const value_type& __obj)
00189 {
00190 __glibcxx_check_insert(__hint);
00191 return iterator(_Base::insert(__hint.base(), __obj), this);
00192 }
00193
00194 template<typename _Pair, typename = typename
00195 std::enable_if<std::is_convertible<_Pair,
00196 value_type>::value>::type>
00197 std::pair<iterator, bool>
00198 insert(_Pair&& __obj)
00199 {
00200 std::pair<_Base_iterator, bool> __res =
00201 _Base::insert(std::forward<_Pair>(__obj));
00202 return std::make_pair(iterator(__res.first, this), __res.second);
00203 }
00204
00205 template<typename _Pair, typename = typename
00206 std::enable_if<std::is_convertible<_Pair,
00207 value_type>::value>::type>
00208 iterator
00209 insert(const_iterator __hint, _Pair&& __obj)
00210 {
00211 __glibcxx_check_insert(__hint);
00212 return iterator(_Base::insert(__hint.base(),
00213 std::forward<_Pair>(__obj)),
00214 this);
00215 }
00216
00217 void
00218 insert(std::initializer_list<value_type> __l)
00219 { _Base::insert(__l); }
00220
00221 template<typename _InputIterator>
00222 void
00223 insert(_InputIterator __first, _InputIterator __last)
00224 {
00225 __glibcxx_check_valid_range(__first, __last);
00226 _Base::insert(__gnu_debug::__base(__first),
00227 __gnu_debug::__base(__last));
00228 }
00229
00230 iterator
00231 find(const key_type& __key)
00232 { return iterator(_Base::find(__key), this); }
00233
00234 const_iterator
00235 find(const key_type& __key) const
00236 { return const_iterator(_Base::find(__key), this); }
00237
00238 std::pair<iterator, iterator>
00239 equal_range(const key_type& __key)
00240 {
00241 std::pair<_Base_iterator, _Base_iterator> __res =
00242 _Base::equal_range(__key);
00243 return std::make_pair(iterator(__res.first, this),
00244 iterator(__res.second, this));
00245 }
00246
00247 std::pair<const_iterator, const_iterator>
00248 equal_range(const key_type& __key) const
00249 {
00250 std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00251 _Base::equal_range(__key);
00252 return std::make_pair(const_iterator(__res.first, this),
00253 const_iterator(__res.second, this));
00254 }
00255
00256 size_type
00257 erase(const key_type& __key)
00258 {
00259 size_type __ret(0);
00260 _Base_iterator __victim(_Base::find(__key));
00261 if (__victim != _Base::end())
00262 {
00263 this->_M_invalidate_if(_Equal(__victim));
00264 _Base::erase(__victim);
00265 __ret = 1;
00266 }
00267 return __ret;
00268 }
00269
00270 iterator
00271 erase(const_iterator __it)
00272 {
00273 __glibcxx_check_erase(__it);
00274 this->_M_invalidate_if(_Equal(__it.base()));
00275 return iterator(_Base::erase(__it.base()), this);
00276 }
00277
00278 iterator
00279 erase(const_iterator __first, const_iterator __last)
00280 {
00281 __glibcxx_check_erase_range(__first, __last);
00282 for (_Base_const_iterator __tmp = __first.base();
00283 __tmp != __last.base(); ++__tmp)
00284 {
00285 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00286 _M_message(__gnu_debug::__msg_valid_range)
00287 ._M_iterator(__first, "first")
00288 ._M_iterator(__last, "last"));
00289 this->_M_invalidate_if(_Equal(__tmp));
00290 }
00291 return iterator(_Base::erase(__first.base(),
00292 __last.base()), this);
00293 }
00294
00295 _Base&
00296 _M_base() { return *this; }
00297
00298 const _Base&
00299 _M_base() const { return *this; }
00300
00301 private:
00302 void
00303 _M_invalidate_all()
00304 {
00305 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00306 this->_M_invalidate_if(_Not_equal(_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 bool
00320 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00321 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00322 { return __x._M_equal(__y); }
00323
00324 template<typename _Key, typename _Tp, typename _Hash,
00325 typename _Pred, typename _Alloc>
00326 inline bool
00327 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00328 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00329 { return !(__x == __y); }
00330
00331
00332
00333 template<typename _Key, typename _Tp,
00334 typename _Hash = std::hash<_Key>,
00335 typename _Pred = std::equal_to<_Key>,
00336 typename _Alloc = std::allocator<_Key> >
00337 class unordered_multimap
00338 : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
00339 _Pred, _Alloc>,
00340 public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,
00341 _Pred, _Alloc> >
00342 {
00343 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
00344 _Pred, _Alloc> _Base;
00345 typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base;
00346 typedef typename _Base::const_iterator _Base_const_iterator;
00347 typedef typename _Base::iterator _Base_iterator;
00348 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00349
00350 public:
00351 typedef typename _Base::size_type size_type;
00352 typedef typename _Base::hasher hasher;
00353 typedef typename _Base::key_equal key_equal;
00354 typedef typename _Base::allocator_type allocator_type;
00355
00356 typedef typename _Base::key_type key_type;
00357 typedef typename _Base::value_type value_type;
00358
00359 typedef __gnu_debug::_Safe_iterator<_Base_iterator,
00360 unordered_multimap> iterator;
00361 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00362 unordered_multimap> const_iterator;
00363
00364 explicit
00365 unordered_multimap(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(__n, __hf, __eql, __a) { }
00370
00371 template<typename _InputIterator>
00372 unordered_multimap(_InputIterator __first, _InputIterator __last,
00373 size_type __n = 0,
00374 const hasher& __hf = hasher(),
00375 const key_equal& __eql = key_equal(),
00376 const allocator_type& __a = allocator_type())
00377 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00378 __last)),
00379 __gnu_debug::__base(__last), __n,
00380 __hf, __eql, __a), _Safe_base() { }
00381
00382 unordered_multimap(const unordered_multimap& __x)
00383 : _Base(__x), _Safe_base() { }
00384
00385 unordered_multimap(const _Base& __x)
00386 : _Base(__x), _Safe_base() { }
00387
00388 unordered_multimap(unordered_multimap&& __x)
00389 : _Base(std::move(__x)), _Safe_base() { }
00390
00391 unordered_multimap(initializer_list<value_type> __l,
00392 size_type __n = 0,
00393 const hasher& __hf = hasher(),
00394 const key_equal& __eql = key_equal(),
00395 const allocator_type& __a = allocator_type())
00396 : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
00397
00398 unordered_multimap&
00399 operator=(const unordered_multimap& __x)
00400 {
00401 *static_cast<_Base*>(this) = __x;
00402 this->_M_invalidate_all();
00403 return *this;
00404 }
00405
00406 unordered_multimap&
00407 operator=(unordered_multimap&& __x)
00408 {
00409
00410
00411 clear();
00412 swap(__x);
00413 return *this;
00414 }
00415
00416 unordered_multimap&
00417 operator=(initializer_list<value_type> __l)
00418 {
00419 this->clear();
00420 this->insert(__l);
00421 return *this;
00422 }
00423
00424 void
00425 swap(unordered_multimap& __x)
00426 {
00427 _Base::swap(__x);
00428 _Safe_base::_M_swap(__x);
00429 }
00430
00431 void
00432 clear()
00433 {
00434 _Base::clear();
00435 this->_M_invalidate_all();
00436 }
00437
00438 iterator
00439 begin()
00440 { return iterator(_Base::begin(), this); }
00441
00442 const_iterator
00443 begin() const
00444 { return const_iterator(_Base::begin(), this); }
00445
00446 iterator
00447 end()
00448 { return iterator(_Base::end(), this); }
00449
00450 const_iterator
00451 end() const
00452 { return const_iterator(_Base::end(), this); }
00453
00454 const_iterator
00455 cbegin() const
00456 { return const_iterator(_Base::begin(), this); }
00457
00458 const_iterator
00459 cend() const
00460 { return const_iterator(_Base::end(), this); }
00461
00462
00463 using _Base::begin;
00464 using _Base::end;
00465 using _Base::cbegin;
00466 using _Base::cend;
00467
00468 iterator
00469 insert(const value_type& __obj)
00470 { return iterator(_Base::insert(__obj), this); }
00471
00472 iterator
00473 insert(const_iterator __hint, const value_type& __obj)
00474 {
00475 __glibcxx_check_insert(__hint);
00476 return iterator(_Base::insert(__hint.base(), __obj), this);
00477 }
00478
00479 template<typename _Pair, typename = typename
00480 std::enable_if<std::is_convertible<_Pair,
00481 value_type>::value>::type>
00482 iterator
00483 insert(_Pair&& __obj)
00484 { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); }
00485
00486 template<typename _Pair, typename = typename
00487 std::enable_if<std::is_convertible<_Pair,
00488 value_type>::value>::type>
00489 iterator
00490 insert(const_iterator __hint, _Pair&& __obj)
00491 {
00492 __glibcxx_check_insert(__hint);
00493 return iterator(_Base::insert(__hint.base(),
00494 std::forward<_Pair>(__obj)),
00495 this);
00496 }
00497
00498 void
00499 insert(std::initializer_list<value_type> __l)
00500 { _Base::insert(__l); }
00501
00502 template<typename _InputIterator>
00503 void
00504 insert(_InputIterator __first, _InputIterator __last)
00505 {
00506 __glibcxx_check_valid_range(__first, __last);
00507 _Base::insert(__gnu_debug::__base(__first),
00508 __gnu_debug::__base(__last));
00509 }
00510
00511 iterator
00512 find(const key_type& __key)
00513 { return iterator(_Base::find(__key), this); }
00514
00515 const_iterator
00516 find(const key_type& __key) const
00517 { return const_iterator(_Base::find(__key), this); }
00518
00519 std::pair<iterator, iterator>
00520 equal_range(const key_type& __key)
00521 {
00522 std::pair<_Base_iterator, _Base_iterator> __res =
00523 _Base::equal_range(__key);
00524 return std::make_pair(iterator(__res.first, this),
00525 iterator(__res.second, this));
00526 }
00527
00528 std::pair<const_iterator, const_iterator>
00529 equal_range(const key_type& __key) const
00530 {
00531 std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00532 _Base::equal_range(__key);
00533 return std::make_pair(const_iterator(__res.first, this),
00534 const_iterator(__res.second, this));
00535 }
00536
00537 size_type
00538 erase(const key_type& __key)
00539 {
00540 size_type __ret(0);
00541 std::pair<_Base_iterator, _Base_iterator> __pair =
00542 _Base::equal_range(__key);
00543 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
00544 {
00545 this->_M_invalidate_if(_Equal(__victim));
00546 _Base::erase(__victim++);
00547 ++__ret;
00548 }
00549 return __ret;
00550 }
00551
00552 iterator
00553 erase(const_iterator __it)
00554 {
00555 __glibcxx_check_erase(__it);
00556 this->_M_invalidate_if(_Equal(__it.base()));
00557 return iterator(_Base::erase(__it.base()), this);
00558 }
00559
00560 iterator
00561 erase(const_iterator __first, const_iterator __last)
00562 {
00563 __glibcxx_check_erase_range(__first, __last);
00564 for (_Base_const_iterator __tmp = __first.base();
00565 __tmp != __last.base(); ++__tmp)
00566 {
00567 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00568 _M_message(__gnu_debug::__msg_valid_range)
00569 ._M_iterator(__first, "first")
00570 ._M_iterator(__last, "last"));
00571 this->_M_invalidate_if(_Equal(__tmp));
00572 }
00573 return iterator(_Base::erase(__first.base(),
00574 __last.base()), this);
00575 }
00576
00577 _Base&
00578 _M_base() { return *this; }
00579
00580 const _Base&
00581 _M_base() const { return *this; }
00582
00583 private:
00584 void
00585 _M_invalidate_all()
00586 {
00587 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00588 this->_M_invalidate_if(_Not_equal(_Base::end()));
00589 }
00590 };
00591
00592 template<typename _Key, typename _Tp, typename _Hash,
00593 typename _Pred, typename _Alloc>
00594 inline void
00595 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00596 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00597 { __x.swap(__y); }
00598
00599 template<typename _Key, typename _Tp, typename _Hash,
00600 typename _Pred, typename _Alloc>
00601 inline bool
00602 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00603 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00604 { return __x._M_equal(__y); }
00605
00606 template<typename _Key, typename _Tp, typename _Hash,
00607 typename _Pred, typename _Alloc>
00608 inline bool
00609 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00610 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00611 { return !(__x == __y); }
00612
00613 }
00614 }
00615
00616 #endif // __GXX_EXPERIMENTAL_CXX0X__
00617
00618 #endif