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
00031
00032
00033
00034 #ifndef _GLIBCXX_PROFILE_UNORDERED_MAP
00035 #define _GLIBCXX_PROFILE_UNORDERED_MAP 1
00036
00037 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00038 # include <bits/c++0x_warning.h>
00039 #else
00040 # include <unordered_map>
00041
00042 #include <profile/base.h>
00043
00044 #define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
00045 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00046
00047 namespace std _GLIBCXX_VISIBILITY(default)
00048 {
00049 namespace __profile
00050 {
00051
00052 template<typename _Key, typename _Tp,
00053 typename _Hash = std::hash<_Key>,
00054 typename _Pred = std::equal_to<_Key>,
00055 typename _Alloc = std::allocator<_Key> >
00056 class unordered_map
00057 : public _GLIBCXX_STD_BASE
00058 {
00059 typedef typename _GLIBCXX_STD_BASE _Base;
00060
00061 public:
00062 typedef typename _Base::size_type size_type;
00063 typedef typename _Base::hasher hasher;
00064 typedef typename _Base::key_equal key_equal;
00065 typedef typename _Base::allocator_type allocator_type;
00066 typedef typename _Base::key_type key_type;
00067 typedef typename _Base::value_type value_type;
00068 typedef typename _Base::difference_type difference_type;
00069 typedef typename _Base::reference reference;
00070 typedef typename _Base::const_reference const_reference;
00071 typedef typename _Base::mapped_type mapped_type;
00072
00073 typedef typename _Base::iterator iterator;
00074 typedef typename _Base::const_iterator 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 __profcxx_hashtable_construct(this, _Base::bucket_count());
00084 __profcxx_hashtable_construct2(this);
00085 }
00086
00087 template<typename _InputIterator>
00088 unordered_map(_InputIterator __f, _InputIterator __l,
00089 size_type __n = 0,
00090 const hasher& __hf = hasher(),
00091 const key_equal& __eql = key_equal(),
00092 const allocator_type& __a = allocator_type())
00093 : _Base(__f, __l, __n, __hf, __eql, __a)
00094 {
00095 __profcxx_hashtable_construct(this, _Base::bucket_count());
00096 __profcxx_hashtable_construct2(this);
00097 }
00098
00099 unordered_map(const _Base& __x)
00100 : _Base(__x)
00101 {
00102 __profcxx_hashtable_construct(this, _Base::bucket_count());
00103 __profcxx_hashtable_construct2(this);
00104 }
00105
00106 unordered_map(unordered_map&& __x)
00107 : _Base(std::move(__x))
00108 {
00109 __profcxx_hashtable_construct(this, _Base::bucket_count());
00110 __profcxx_hashtable_construct2(this);
00111 }
00112
00113 unordered_map(initializer_list<value_type> __l,
00114 size_type __n = 0,
00115 const hasher& __hf = hasher(),
00116 const key_equal& __eql = key_equal(),
00117 const allocator_type& __a = allocator_type())
00118 : _Base(__l, __n, __hf, __eql, __a) { }
00119
00120 unordered_map&
00121 operator=(const unordered_map& __x)
00122 {
00123 *static_cast<_Base*>(this) = __x;
00124 return *this;
00125 }
00126
00127 unordered_map&
00128 operator=(unordered_map&& __x)
00129 {
00130
00131
00132 this->clear();
00133 this->swap(__x);
00134 return *this;
00135 }
00136
00137 unordered_map&
00138 operator=(initializer_list<value_type> __l)
00139 {
00140 this->clear();
00141 this->insert(__l);
00142 return *this;
00143 }
00144
00145 ~unordered_map()
00146 {
00147 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
00148 _Base::size());
00149 _M_profile_destruct();
00150 }
00151
00152 _Base&
00153 _M_base() { return *this; }
00154
00155 const _Base&
00156 _M_base() const { return *this; }
00157
00158
00159 void
00160 clear()
00161 {
00162 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
00163 _Base::size());
00164 _M_profile_destruct();
00165 _Base::clear();
00166 }
00167
00168 void
00169 insert(std::initializer_list<value_type> __l)
00170 {
00171 size_type __old_size = _Base::bucket_count();
00172 _Base::insert(__l);
00173 _M_profile_resize(__old_size);
00174 }
00175
00176 std::pair<iterator, bool>
00177 insert(const value_type& __obj)
00178 {
00179 size_type __old_size = _Base::bucket_count();
00180 std::pair<iterator, bool> __res = _Base::insert(__obj);
00181 _M_profile_resize(__old_size);
00182 return __res;
00183 }
00184
00185 iterator
00186 insert(const_iterator __iter, const value_type& __v)
00187 {
00188 size_type __old_size = _Base::bucket_count();
00189 iterator __res = _Base::insert(__iter, __v);
00190 _M_profile_resize(__old_size);
00191 return __res;
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 size_type __old_size = _Base::bucket_count();
00201 std::pair<iterator, bool> __res
00202 = _Base::insert(std::forward<_Pair>(__obj));
00203 _M_profile_resize(__old_size);
00204 return __res;
00205 }
00206
00207 template<typename _Pair, typename = typename
00208 std::enable_if<std::is_convertible<_Pair,
00209 value_type>::value>::type>
00210 iterator
00211 insert(const_iterator __iter, _Pair&& __v)
00212 {
00213 size_type __old_size = _Base::bucket_count();
00214 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
00215 _M_profile_resize(__old_size);
00216 return __res;
00217 }
00218
00219 template<typename _InputIter>
00220 void
00221 insert(_InputIter __first, _InputIter __last)
00222 {
00223 size_type __old_size = _Base::bucket_count();
00224 _Base::insert(__first, __last);
00225 _M_profile_resize(__old_size);
00226 }
00227
00228 void
00229 insert(const value_type* __first, const value_type* __last)
00230 {
00231 size_type __old_size = _Base::bucket_count();
00232 _Base::insert(__first, __last);
00233 _M_profile_resize(__old_size);
00234 }
00235
00236
00237 mapped_type&
00238 operator[](const _Key& __k)
00239 {
00240 size_type __old_size = _Base::bucket_count();
00241 mapped_type& __res = _M_base()[__k];
00242 _M_profile_resize(__old_size);
00243 return __res;
00244 }
00245
00246 mapped_type&
00247 operator[](_Key&& __k)
00248 {
00249 size_type __old_size = _Base::bucket_count();
00250 mapped_type& __res = _M_base()[std::move(__k)];
00251 _M_profile_resize(__old_size);
00252 return __res;
00253 }
00254
00255 void
00256 swap(unordered_map& __x)
00257 { _Base::swap(__x); }
00258
00259 void rehash(size_type __n)
00260 {
00261 size_type __old_size = _Base::bucket_count();
00262 _Base::rehash(__n);
00263 _M_profile_resize(__old_size);
00264 }
00265
00266 private:
00267 void
00268 _M_profile_resize(size_type __old_size)
00269 {
00270 size_type __new_size = _Base::bucket_count();
00271 if (__old_size != __new_size)
00272 __profcxx_hashtable_resize(this, __old_size, __new_size);
00273 }
00274
00275 void
00276 _M_profile_destruct()
00277 {
00278 size_type __hops = 0, __lc = 0, __chain = 0;
00279 for (iterator __it = _M_base().begin(); __it != _M_base().end();
00280 ++__it)
00281 {
00282 while (__it._M_cur_node->_M_next)
00283 {
00284 ++__chain;
00285 ++__it;
00286 }
00287 if (__chain)
00288 {
00289 ++__chain;
00290 __lc = __lc > __chain ? __lc : __chain;
00291 __hops += __chain * (__chain - 1) / 2;
00292 __chain = 0;
00293 }
00294 }
00295 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
00296 }
00297 };
00298
00299 template<typename _Key, typename _Tp, typename _Hash,
00300 typename _Pred, typename _Alloc>
00301 inline void
00302 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00303 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00304 { __x.swap(__y); }
00305
00306 template<typename _Key, typename _Tp, typename _Hash,
00307 typename _Pred, typename _Alloc>
00308 inline bool
00309 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00310 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00311 { return __x._M_equal(__y); }
00312
00313 template<typename _Key, typename _Tp, typename _Hash,
00314 typename _Pred, typename _Alloc>
00315 inline bool
00316 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00317 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00318 { return !(__x == __y); }
00319
00320 #undef _GLIBCXX_BASE
00321 #undef _GLIBCXX_STD_BASE
00322 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
00323 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00324
00325
00326 template<typename _Key, typename _Tp,
00327 typename _Hash = std::hash<_Key>,
00328 typename _Pred = std::equal_to<_Key>,
00329 typename _Alloc = std::allocator<_Key> >
00330 class unordered_multimap
00331 : public _GLIBCXX_STD_BASE
00332 {
00333 typedef typename _GLIBCXX_STD_BASE _Base;
00334
00335 public:
00336 typedef typename _Base::size_type size_type;
00337 typedef typename _Base::hasher hasher;
00338 typedef typename _Base::key_equal key_equal;
00339 typedef typename _Base::allocator_type allocator_type;
00340 typedef typename _Base::key_type key_type;
00341 typedef typename _Base::value_type value_type;
00342 typedef typename _Base::difference_type difference_type;
00343 typedef typename _Base::reference reference;
00344 typedef typename _Base::const_reference const_reference;
00345
00346 typedef typename _Base::iterator iterator;
00347 typedef typename _Base::const_iterator const_iterator;
00348
00349 explicit
00350 unordered_multimap(size_type __n = 10,
00351 const hasher& __hf = hasher(),
00352 const key_equal& __eql = key_equal(),
00353 const allocator_type& __a = allocator_type())
00354 : _Base(__n, __hf, __eql, __a)
00355 {
00356 __profcxx_hashtable_construct(this, _Base::bucket_count());
00357 }
00358 template<typename _InputIterator>
00359 unordered_multimap(_InputIterator __f, _InputIterator __l,
00360 size_type __n = 0,
00361 const hasher& __hf = hasher(),
00362 const key_equal& __eql = key_equal(),
00363 const allocator_type& __a = allocator_type())
00364 : _Base(__f, __l, __n, __hf, __eql, __a)
00365 {
00366 __profcxx_hashtable_construct(this, _Base::bucket_count());
00367 }
00368
00369 unordered_multimap(const _Base& __x)
00370 : _Base(__x)
00371 {
00372 __profcxx_hashtable_construct(this, _Base::bucket_count());
00373 }
00374
00375 unordered_multimap(unordered_multimap&& __x)
00376 : _Base(std::move(__x))
00377 {
00378 __profcxx_hashtable_construct(this, _Base::bucket_count());
00379 }
00380
00381 unordered_multimap(initializer_list<value_type> __l,
00382 size_type __n = 0,
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) { }
00387
00388 unordered_multimap&
00389 operator=(const unordered_multimap& __x)
00390 {
00391 *static_cast<_Base*>(this) = __x;
00392 return *this;
00393 }
00394
00395 unordered_multimap&
00396 operator=(unordered_multimap&& __x)
00397 {
00398
00399
00400 this->clear();
00401 this->swap(__x);
00402 return *this;
00403 }
00404
00405 unordered_multimap&
00406 operator=(initializer_list<value_type> __l)
00407 {
00408 this->clear();
00409 this->insert(__l);
00410 return *this;
00411 }
00412
00413 ~unordered_multimap()
00414 {
00415 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
00416 _Base::size());
00417 _M_profile_destruct();
00418 }
00419
00420 _Base&
00421 _M_base() { return *this; }
00422
00423 const _Base&
00424 _M_base() const { return *this; }
00425
00426
00427 void
00428 clear()
00429 {
00430 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
00431 _Base::size());
00432 _M_profile_destruct();
00433 _Base::clear();
00434 }
00435
00436 void
00437 insert(std::initializer_list<value_type> __l)
00438 {
00439 size_type __old_size = _Base::bucket_count();
00440 _Base::insert(__l);
00441 _M_profile_resize(__old_size, _Base::bucket_count());
00442 }
00443
00444 iterator
00445 insert(const value_type& __obj)
00446 {
00447 size_type __old_size = _Base::bucket_count();
00448 iterator __res = _Base::insert(__obj);
00449 _M_profile_resize(__old_size, _Base::bucket_count());
00450 return __res;
00451 }
00452
00453 iterator
00454 insert(const_iterator __iter, const value_type& __v)
00455 {
00456 size_type __old_size = _Base::bucket_count();
00457 iterator __res = _Base::insert(__iter, __v);
00458 _M_profile_resize(__old_size, _Base::bucket_count());
00459 return __res;
00460 }
00461
00462 template<typename _Pair, typename = typename
00463 std::enable_if<std::is_convertible<_Pair,
00464 value_type>::value>::type>
00465 iterator
00466 insert(_Pair&& __obj)
00467 {
00468 size_type __old_size = _Base::bucket_count();
00469 iterator __res = _Base::insert(std::forward<_Pair>(__obj));
00470 _M_profile_resize(__old_size, _Base::bucket_count());
00471 return __res;
00472 }
00473
00474 template<typename _Pair, typename = typename
00475 std::enable_if<std::is_convertible<_Pair,
00476 value_type>::value>::type>
00477 iterator
00478 insert(const_iterator __iter, _Pair&& __v)
00479 {
00480 size_type __old_size = _Base::bucket_count();
00481 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
00482 _M_profile_resize(__old_size, _Base::bucket_count());
00483 return __res;
00484 }
00485
00486 template<typename _InputIter>
00487 void
00488 insert(_InputIter __first, _InputIter __last)
00489 {
00490 size_type __old_size = _Base::bucket_count();
00491 _Base::insert(__first, __last);
00492 _M_profile_resize(__old_size, _Base::bucket_count());
00493 }
00494
00495 void
00496 insert(const value_type* __first, const value_type* __last)
00497 {
00498 size_type __old_size = _Base::bucket_count();
00499 _Base::insert(__first, __last);
00500 _M_profile_resize(__old_size, _Base::bucket_count());
00501 }
00502
00503 void
00504 swap(unordered_multimap& __x)
00505 { _Base::swap(__x); }
00506
00507 void rehash(size_type __n)
00508 {
00509 size_type __old_size = _Base::bucket_count();
00510 _Base::rehash(__n);
00511 _M_profile_resize(__old_size, _Base::bucket_count());
00512 }
00513
00514 private:
00515 void
00516 _M_profile_resize(size_type __old_size, size_type __new_size)
00517 {
00518 if (__old_size != __new_size)
00519 __profcxx_hashtable_resize(this, __old_size, __new_size);
00520 }
00521
00522 void
00523 _M_profile_destruct()
00524 {
00525 size_type __hops = 0, __lc = 0, __chain = 0;
00526 for (iterator __it = _M_base().begin(); __it != _M_base().end();
00527 ++__it)
00528 {
00529 while (__it._M_cur_node->_M_next)
00530 {
00531 ++__chain;
00532 ++__it;
00533 }
00534 if (__chain)
00535 {
00536 ++__chain;
00537 __lc = __lc > __chain ? __lc : __chain;
00538 __hops += __chain * (__chain - 1) / 2;
00539 __chain = 0;
00540 }
00541 }
00542 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
00543 }
00544
00545 };
00546
00547 template<typename _Key, typename _Tp, typename _Hash,
00548 typename _Pred, typename _Alloc>
00549 inline void
00550 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00551 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00552 { __x.swap(__y); }
00553
00554 template<typename _Key, typename _Tp, typename _Hash,
00555 typename _Pred, typename _Alloc>
00556 inline bool
00557 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00558 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00559 { return __x._M_equal(__y); }
00560
00561 template<typename _Key, typename _Tp, typename _Hash,
00562 typename _Pred, typename _Alloc>
00563 inline bool
00564 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00565 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00566 { return !(__x == __y); }
00567
00568 }
00569 }
00570
00571 #undef _GLIBCXX_BASE
00572 #undef _GLIBCXX_STD_BASE
00573
00574 #endif // __GXX_EXPERIMENTAL_CXX0X__
00575
00576 #endif