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_PR::_GLIBCXX_BASE
00046
00047 namespace std
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 = 10,
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::forward<_Base>(__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 = 10,
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, _Base::bucket_count());
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, _Base::bucket_count());
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, _Base::bucket_count());
00191 return __res;
00192 }
00193
00194 template<typename _InputIter>
00195 void
00196 insert(_InputIter __first, _InputIter __last)
00197 {
00198 size_type __old_size = _Base::bucket_count();
00199 _Base::insert(__first, __last);
00200 _M_profile_resize(__old_size, _Base::bucket_count());
00201 }
00202
00203 void
00204 insert(const value_type* __first, const value_type* __last)
00205 {
00206 size_type __old_size = _Base::bucket_count();
00207 _Base::insert(__first, __last);
00208 _M_profile_resize(__old_size, _Base::bucket_count());
00209 }
00210
00211
00212 mapped_type&
00213 operator[](const _Key& _k)
00214 {
00215 size_type __old_size = _Base::bucket_count();
00216 mapped_type& __res = _M_base()[_k];
00217 size_type __new_size = _Base::bucket_count();
00218 _M_profile_resize(__old_size, _Base::bucket_count());
00219 return __res;
00220 }
00221
00222 void
00223 swap(unordered_map& __x)
00224 { _Base::swap(__x); }
00225
00226 void rehash(size_type __n)
00227 {
00228 size_type __old_size = _Base::bucket_count();
00229 _Base::rehash(__n);
00230 _M_profile_resize(__old_size, _Base::bucket_count());
00231 }
00232
00233 private:
00234 void
00235 _M_profile_resize(size_type __old_size, size_type __new_size)
00236 {
00237 if (__old_size != __new_size)
00238 __profcxx_hashtable_resize(this, __old_size, __new_size);
00239 }
00240
00241 void
00242 _M_profile_destruct()
00243 {
00244 size_type __hops = 0, __lc = 0, __chain = 0;
00245 for (iterator __it = _M_base().begin(); __it != _M_base().end();
00246 ++__it)
00247 {
00248 while (__it._M_cur_node->_M_next)
00249 {
00250 ++__chain;
00251 ++__it;
00252 }
00253 if (__chain)
00254 {
00255 ++__chain;
00256 __lc = __lc > __chain ? __lc : __chain;
00257 __hops += __chain * (__chain - 1) / 2;
00258 __chain = 0;
00259 }
00260 }
00261 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
00262 }
00263 };
00264
00265 template<typename _Key, typename _Tp, typename _Hash,
00266 typename _Pred, typename _Alloc>
00267 inline void
00268 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00269 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00270 { __x.swap(__y); }
00271
00272 template<typename _Key, typename _Tp, typename _Hash,
00273 typename _Pred, typename _Alloc>
00274 inline bool
00275 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00276 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00277 { return __x._M_equal(__y); }
00278
00279 template<typename _Key, typename _Tp, typename _Hash,
00280 typename _Pred, typename _Alloc>
00281 inline bool
00282 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00283 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00284 { return !(__x == __y); }
00285
00286 #undef _GLIBCXX_BASE
00287 #undef _GLIBCXX_STD_BASE
00288 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
00289 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE
00290
00291
00292 template<typename _Key, typename _Tp,
00293 typename _Hash = std::hash<_Key>,
00294 typename _Pred = std::equal_to<_Key>,
00295 typename _Alloc = std::allocator<_Key> >
00296 class unordered_multimap
00297 : public _GLIBCXX_STD_BASE
00298 {
00299 typedef typename _GLIBCXX_STD_BASE _Base;
00300
00301 public:
00302 typedef typename _Base::size_type size_type;
00303 typedef typename _Base::hasher hasher;
00304 typedef typename _Base::key_equal key_equal;
00305 typedef typename _Base::allocator_type allocator_type;
00306 typedef typename _Base::key_type key_type;
00307 typedef typename _Base::value_type value_type;
00308 typedef typename _Base::difference_type difference_type;
00309 typedef typename _Base::reference reference;
00310 typedef typename _Base::const_reference const_reference;
00311
00312 typedef typename _Base::iterator iterator;
00313 typedef typename _Base::const_iterator const_iterator;
00314
00315 explicit
00316 unordered_multimap(size_type __n = 10,
00317 const hasher& __hf = hasher(),
00318 const key_equal& __eql = key_equal(),
00319 const allocator_type& __a = allocator_type())
00320 : _Base(__n, __hf, __eql, __a)
00321 {
00322 __profcxx_hashtable_construct(this, _Base::bucket_count());
00323 }
00324 template<typename _InputIterator>
00325 unordered_multimap(_InputIterator __f, _InputIterator __l,
00326 size_type __n = 10,
00327 const hasher& __hf = hasher(),
00328 const key_equal& __eql = key_equal(),
00329 const allocator_type& __a = allocator_type())
00330 : _Base(__f, __l, __n, __hf, __eql, __a)
00331 {
00332 __profcxx_hashtable_construct(this, _Base::bucket_count());
00333 }
00334
00335 unordered_multimap(const _Base& __x)
00336 : _Base(__x)
00337 {
00338 __profcxx_hashtable_construct(this, _Base::bucket_count());
00339 }
00340
00341 unordered_multimap(unordered_multimap&& __x)
00342 : _Base(std::forward<_Base>(__x))
00343 {
00344 __profcxx_hashtable_construct(this, _Base::bucket_count());
00345 }
00346
00347 unordered_multimap(initializer_list<value_type> __l,
00348 size_type __n = 10,
00349 const hasher& __hf = hasher(),
00350 const key_equal& __eql = key_equal(),
00351 const allocator_type& __a = allocator_type())
00352 : _Base(__l, __n, __hf, __eql, __a) { }
00353
00354 unordered_multimap&
00355 operator=(const unordered_multimap& __x)
00356 {
00357 *static_cast<_Base*>(this) = __x;
00358 return *this;
00359 }
00360
00361 unordered_multimap&
00362 operator=(unordered_multimap&& __x)
00363 {
00364
00365
00366 this->clear();
00367 this->swap(__x);
00368 return *this;
00369 }
00370
00371 unordered_multimap&
00372 operator=(initializer_list<value_type> __l)
00373 {
00374 this->clear();
00375 this->insert(__l);
00376 return *this;
00377 }
00378
00379 ~unordered_multimap()
00380 {
00381 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
00382 _Base::size());
00383 _M_profile_destruct();
00384 }
00385
00386 _Base&
00387 _M_base() { return *this; }
00388
00389 const _Base&
00390 _M_base() const { return *this; }
00391
00392
00393 void
00394 clear()
00395 {
00396 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
00397 _Base::size());
00398 _M_profile_destruct();
00399 _Base::clear();
00400 }
00401
00402 void
00403 insert(std::initializer_list<value_type> __l)
00404 {
00405 size_type __old_size = _Base::bucket_count();
00406 _Base::insert(__l);
00407 _M_profile_resize(__old_size, _Base::bucket_count());
00408 }
00409
00410 iterator
00411 insert(const value_type& __obj)
00412 {
00413 size_type __old_size = _Base::bucket_count();
00414 iterator __res = _Base::insert(__obj);
00415 _M_profile_resize(__old_size, _Base::bucket_count());
00416 return __res;
00417 }
00418
00419 iterator
00420 insert(const_iterator __iter, const value_type& __v)
00421 {
00422 size_type __old_size = _Base::bucket_count();
00423 iterator __res =_Base::insert(__iter, __v);
00424 _M_profile_resize(__old_size, _Base::bucket_count());
00425 return __res;
00426 }
00427
00428 template<typename _InputIter>
00429 void
00430 insert(_InputIter __first, _InputIter __last)
00431 {
00432 size_type __old_size = _Base::bucket_count();
00433 _Base::insert(__first, __last);
00434 _M_profile_resize(__old_size, _Base::bucket_count());
00435 }
00436
00437 void
00438 insert(const value_type* __first, const value_type* __last)
00439 {
00440 size_type __old_size = _Base::bucket_count();
00441 _Base::insert(__first, __last);
00442 _M_profile_resize(__old_size, _Base::bucket_count());
00443 }
00444
00445 void
00446 swap(unordered_multimap& __x)
00447 { _Base::swap(__x); }
00448
00449 void rehash(size_type __n)
00450 {
00451 size_type __old_size = _Base::bucket_count();
00452 _Base::rehash(__n);
00453 _M_profile_resize(__old_size, _Base::bucket_count());
00454 }
00455
00456 private:
00457 void
00458 _M_profile_resize(size_type __old_size, size_type __new_size)
00459 {
00460 if (__old_size != __new_size)
00461 __profcxx_hashtable_resize(this, __old_size, __new_size);
00462 }
00463
00464 void
00465 _M_profile_destruct()
00466 {
00467 size_type __hops = 0, __lc = 0, __chain = 0;
00468 for (iterator __it = _M_base().begin(); __it != _M_base().end();
00469 ++__it)
00470 {
00471 while (__it._M_cur_node->_M_next)
00472 {
00473 ++__chain;
00474 ++__it;
00475 }
00476 if (__chain)
00477 {
00478 ++__chain;
00479 __lc = __lc > __chain ? __lc : __chain;
00480 __hops += __chain * (__chain - 1) / 2;
00481 __chain = 0;
00482 }
00483 }
00484 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
00485 }
00486
00487 };
00488
00489 template<typename _Key, typename _Tp, typename _Hash,
00490 typename _Pred, typename _Alloc>
00491 inline void
00492 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00493 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00494 { __x.swap(__y); }
00495
00496 template<typename _Key, typename _Tp, typename _Hash,
00497 typename _Pred, typename _Alloc>
00498 inline bool
00499 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00500 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00501 { return __x._M_equal(__y); }
00502
00503 template<typename _Key, typename _Tp, typename _Hash,
00504 typename _Pred, typename _Alloc>
00505 inline bool
00506 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00507 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00508 { return !(__x == __y); }
00509
00510 }
00511 }
00512
00513 #undef _GLIBCXX_BASE
00514 #undef _GLIBCXX_STD_BASE
00515
00516 #endif // __GXX_EXPERIMENTAL_CXX0X__
00517
00518 #endif