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