1// Profiling unordered_set/unordered_multiset implementation -*- C++ -*- 2 3// Copyright (C) 2009-2015 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 3, or (at your option) 9// any later version. 10// 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License along 21// with this library; see the file COPYING3. If not see 22// <http://www.gnu.org/licenses/>. 23 24/** @file profile/unordered_set 25 * This file is a GNU profile extension to the Standard C++ Library. 26 */ 27 28#ifndef _GLIBCXX_PROFILE_UNORDERED_SET 29#define _GLIBCXX_PROFILE_UNORDERED_SET 1 30 31#if __cplusplus < 201103L 32# include <bits/c++0x_warning.h> 33#else 34# include <unordered_set> 35 36#include <profile/base.h> 37#include <profile/unordered_base.h> 38 39#define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc> 40#define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 41 42namespace std _GLIBCXX_VISIBILITY(default) 43{ 44namespace __profile 45{ 46 /** @brief Unordered_set wrapper with performance instrumentation. */ 47 template<typename _Key, 48 typename _Hash = std::hash<_Key>, 49 typename _Pred = std::equal_to<_Key>, 50 typename _Alloc = std::allocator<_Key> > 51 class unordered_set 52 : public _GLIBCXX_STD_BASE, 53 public _Unordered_profile<unordered_set<_Key, _Hash, _Pred, _Alloc>, 54 true> 55 { 56 typedef _GLIBCXX_STD_BASE _Base; 57 58 _Base& 59 _M_base() noexcept { return *this; } 60 61 const _Base& 62 _M_base() const noexcept { return *this; } 63 64 public: 65 typedef typename _Base::size_type size_type; 66 typedef typename _Base::hasher hasher; 67 typedef typename _Base::key_equal key_equal; 68 typedef typename _Base::allocator_type allocator_type; 69 typedef typename _Base::key_type key_type; 70 typedef typename _Base::value_type value_type; 71 typedef typename _Base::difference_type difference_type; 72 typedef typename _Base::reference reference; 73 typedef typename _Base::const_reference const_reference; 74 75 typedef typename _Base::iterator iterator; 76 typedef typename _Base::const_iterator const_iterator; 77 78 unordered_set() = default; 79 80 explicit 81 unordered_set(size_type __n, 82 const hasher& __hf = hasher(), 83 const key_equal& __eql = key_equal(), 84 const allocator_type& __a = allocator_type()) 85 : _Base(__n, __hf, __eql, __a) 86 { } 87 88 template<typename _InputIterator> 89 unordered_set(_InputIterator __f, _InputIterator __l, 90 size_type __n = 0, 91 const hasher& __hf = hasher(), 92 const key_equal& __eql = key_equal(), 93 const allocator_type& __a = allocator_type()) 94 : _Base(__f, __l, __n, __hf, __eql, __a) 95 { } 96 97 unordered_set(const unordered_set&) = default; 98 99 unordered_set(const _Base& __x) 100 : _Base(__x) 101 { } 102 103 unordered_set(unordered_set&&) = default; 104 105 explicit 106 unordered_set(const allocator_type& __a) 107 : _Base(__a) 108 { } 109 110 unordered_set(const unordered_set& __uset, 111 const allocator_type& __a) 112 : _Base(__uset._M_base(), __a) 113 { } 114 115 unordered_set(unordered_set&& __uset, 116 const allocator_type& __a) 117 : _Base(std::move(__uset._M_base()), __a) 118 { } 119 120 unordered_set(initializer_list<value_type> __l, 121 size_type __n = 0, 122 const hasher& __hf = hasher(), 123 const key_equal& __eql = key_equal(), 124 const allocator_type& __a = allocator_type()) 125 : _Base(__l, __n, __hf, __eql, __a) 126 { } 127 128 unordered_set(size_type __n, const allocator_type& __a) 129 : unordered_set(__n, hasher(), key_equal(), __a) 130 { } 131 132 unordered_set(size_type __n, const hasher& __hf, 133 const allocator_type& __a) 134 : unordered_set(__n, __hf, key_equal(), __a) 135 { } 136 137 template<typename _InputIterator> 138 unordered_set(_InputIterator __first, _InputIterator __last, 139 size_type __n, 140 const allocator_type& __a) 141 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) 142 { } 143 144 template<typename _InputIterator> 145 unordered_set(_InputIterator __first, _InputIterator __last, 146 size_type __n, const hasher& __hf, 147 const allocator_type& __a) 148 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) 149 { } 150 151 unordered_set(initializer_list<value_type> __l, 152 size_type __n, 153 const allocator_type& __a) 154 : unordered_set(__l, __n, hasher(), key_equal(), __a) 155 { } 156 157 unordered_set(initializer_list<value_type> __l, 158 size_type __n, const hasher& __hf, 159 const allocator_type& __a) 160 : unordered_set(__l, __n, __hf, key_equal(), __a) 161 { } 162 163 unordered_set& 164 operator=(const unordered_set&) = default; 165 166 unordered_set& 167 operator=(unordered_set&&) = default; 168 169 unordered_set& 170 operator=(initializer_list<value_type> __l) 171 { 172 this->_M_profile_destruct(); 173 _M_base() = __l; 174 this->_M_profile_construct(); 175 return *this; 176 } 177 178 void 179 swap(unordered_set& __x) 180 noexcept( noexcept(__x._M_base().swap(__x)) ) 181 { 182 _Base::swap(__x); 183 this->_M_swap(__x); 184 } 185 186 void 187 clear() noexcept 188 { 189 this->_M_profile_destruct(); 190 _Base::clear(); 191 this->_M_profile_construct(); 192 } 193 194 template<typename... _Args> 195 std::pair<iterator, bool> 196 emplace(_Args&&... __args) 197 { 198 size_type __old_size = _Base::bucket_count(); 199 std::pair<iterator, bool> __res 200 = _Base::emplace(std::forward<_Args>(__args)...); 201 this->_M_profile_resize(__old_size); 202 return __res; 203 } 204 205 template<typename... _Args> 206 iterator 207 emplace_hint(const_iterator __it, _Args&&... __args) 208 { 209 size_type __old_size = _Base::bucket_count(); 210 iterator __res 211 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 212 this->_M_profile_resize(__old_size); 213 return __res; 214 } 215 216 void 217 insert(std::initializer_list<value_type> __l) 218 { 219 size_type __old_size = _Base::bucket_count(); 220 _Base::insert(__l); 221 this->_M_profile_resize(__old_size); 222 } 223 224 std::pair<iterator, bool> 225 insert(const value_type& __obj) 226 { 227 size_type __old_size = _Base::bucket_count(); 228 std::pair<iterator, bool> __res = _Base::insert(__obj); 229 this->_M_profile_resize(__old_size); 230 return __res; 231 } 232 233 iterator 234 insert(const_iterator __iter, const value_type& __v) 235 { 236 size_type __old_size = _Base::bucket_count(); 237 iterator __res = _Base::insert(__iter, __v); 238 this->_M_profile_resize(__old_size); 239 return __res; 240 } 241 242 std::pair<iterator, bool> 243 insert(value_type&& __obj) 244 { 245 size_type __old_size = _Base::bucket_count(); 246 std::pair<iterator, bool> __res = _Base::insert(std::move(__obj)); 247 this->_M_profile_resize(__old_size); 248 return __res; 249 } 250 251 iterator 252 insert(const_iterator __iter, value_type&& __v) 253 { 254 size_type __old_size = _Base::bucket_count(); 255 iterator __res = _Base::insert(__iter, std::move(__v)); 256 this->_M_profile_resize(__old_size); 257 return __res; 258 } 259 260 template<typename _InputIter> 261 void 262 insert(_InputIter __first, _InputIter __last) 263 { 264 size_type __old_size = _Base::bucket_count(); 265 _Base::insert(__first, __last); 266 this->_M_profile_resize(__old_size); 267 } 268 269 void 270 rehash(size_type __n) 271 { 272 size_type __old_size = _Base::bucket_count(); 273 _Base::rehash(__n); 274 this->_M_profile_resize(__old_size); 275 } 276 }; 277 278 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc> 279 inline void 280 swap(unordered_set<_Key, _Hash, _Pred, _Alloc>& __x, 281 unordered_set<_Key, _Hash, _Pred, _Alloc>& __y) 282 { __x.swap(__y); } 283 284 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc> 285 inline bool 286 operator==(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x, 287 const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y) 288 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 289 290 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc> 291 inline bool 292 operator!=(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x, 293 const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y) 294 { return !(__x == __y); } 295 296#undef _GLIBCXX_BASE 297#undef _GLIBCXX_STD_BASE 298#define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 299#define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc> 300 301 /** @brief Unordered_multiset wrapper with performance instrumentation. */ 302 template<typename _Value, 303 typename _Hash = std::hash<_Value>, 304 typename _Pred = std::equal_to<_Value>, 305 typename _Alloc = std::allocator<_Value> > 306 class unordered_multiset 307 : public _GLIBCXX_STD_BASE, 308 public _Unordered_profile<unordered_multiset<_Value, 309 _Hash, _Pred, _Alloc>, 310 false> 311 { 312 typedef _GLIBCXX_STD_BASE _Base; 313 314 _Base& 315 _M_base() noexcept { return *this; } 316 317 const _Base& 318 _M_base() const noexcept { return *this; } 319 320 public: 321 typedef typename _Base::size_type size_type; 322 typedef typename _Base::hasher hasher; 323 typedef typename _Base::key_equal key_equal; 324 typedef typename _Base::allocator_type allocator_type; 325 typedef typename _Base::key_type key_type; 326 typedef typename _Base::value_type value_type; 327 typedef typename _Base::difference_type difference_type; 328 typedef typename _Base::reference reference; 329 typedef typename _Base::const_reference const_reference; 330 331 typedef typename _Base::iterator iterator; 332 typedef typename _Base::const_iterator const_iterator; 333 334 unordered_multiset() = default; 335 336 explicit 337 unordered_multiset(size_type __n, 338 const hasher& __hf = hasher(), 339 const key_equal& __eql = key_equal(), 340 const allocator_type& __a = allocator_type()) 341 : _Base(__n, __hf, __eql, __a) 342 { } 343 344 template<typename _InputIterator> 345 unordered_multiset(_InputIterator __f, _InputIterator __l, 346 size_type __n = 0, 347 const hasher& __hf = hasher(), 348 const key_equal& __eql = key_equal(), 349 const allocator_type& __a = allocator_type()) 350 : _Base(__f, __l, __n, __hf, __eql, __a) 351 { } 352 353 unordered_multiset(const unordered_multiset&) = default; 354 355 unordered_multiset(const _Base& __x) 356 : _Base(__x) 357 { } 358 359 unordered_multiset(unordered_multiset&&) = default; 360 361 explicit 362 unordered_multiset(const allocator_type& __a) 363 : _Base(__a) 364 { } 365 366 unordered_multiset(const unordered_multiset& __umset, 367 const allocator_type& __a) 368 : _Base(__umset._M_base(), __a) 369 { } 370 371 unordered_multiset(unordered_multiset&& __umset, 372 const allocator_type& __a) 373 : _Base(std::move(__umset._M_base()), __a) 374 { } 375 376 unordered_multiset(initializer_list<value_type> __l, 377 size_type __n = 0, 378 const hasher& __hf = hasher(), 379 const key_equal& __eql = key_equal(), 380 const allocator_type& __a = allocator_type()) 381 : _Base(__l, __n, __hf, __eql, __a) 382 { } 383 384 unordered_multiset(size_type __n, const allocator_type& __a) 385 : unordered_multiset(__n, hasher(), key_equal(), __a) 386 { } 387 388 unordered_multiset(size_type __n, const hasher& __hf, 389 const allocator_type& __a) 390 : unordered_multiset(__n, __hf, key_equal(), __a) 391 { } 392 393 template<typename _InputIterator> 394 unordered_multiset(_InputIterator __first, _InputIterator __last, 395 size_type __n, 396 const allocator_type& __a) 397 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) 398 { } 399 400 template<typename _InputIterator> 401 unordered_multiset(_InputIterator __first, _InputIterator __last, 402 size_type __n, const hasher& __hf, 403 const allocator_type& __a) 404 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) 405 { } 406 407 unordered_multiset(initializer_list<value_type> __l, 408 size_type __n, 409 const allocator_type& __a) 410 : unordered_multiset(__l, __n, hasher(), key_equal(), __a) 411 { } 412 413 unordered_multiset(initializer_list<value_type> __l, 414 size_type __n, const hasher& __hf, 415 const allocator_type& __a) 416 : unordered_multiset(__l, __n, __hf, key_equal(), __a) 417 { } 418 419 unordered_multiset& 420 operator=(const unordered_multiset&) = default; 421 422 unordered_multiset& 423 operator=(unordered_multiset&&) = default; 424 425 unordered_multiset& 426 operator=(initializer_list<value_type> __l) 427 { 428 this->_M_profile_destruct(); 429 _M_base() = __l; 430 this->_M_profile_construct(); 431 return *this; 432 } 433 434 void 435 swap(unordered_multiset& __x) 436 noexcept( noexcept(__x._M_base().swap(__x)) ) 437 { 438 _Base::swap(__x); 439 this->_M_swap(__x); 440 } 441 442 void 443 clear() noexcept 444 { 445 this->_M_profile_destruct(); 446 _Base::clear(); 447 this->_M_profile_construct(); 448 } 449 450 template<typename... _Args> 451 iterator 452 emplace(_Args&&... __args) 453 { 454 size_type __old_size = _Base::bucket_count(); 455 iterator __res = _Base::emplace(std::forward<_Args>(__args)...); 456 this->_M_profile_resize(__old_size); 457 return __res; 458 } 459 460 template<typename... _Args> 461 iterator 462 emplace_hint(const_iterator __it, _Args&&... __args) 463 { 464 size_type __old_size = _Base::bucket_count(); 465 iterator __res 466 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 467 this->_M_profile_resize(__old_size); 468 return __res; 469 } 470 471 void 472 insert(std::initializer_list<value_type> __l) 473 { 474 size_type __old_size = _Base::bucket_count(); 475 _Base::insert(__l); 476 this->_M_profile_resize(__old_size); 477 } 478 479 iterator 480 insert(const value_type& __obj) 481 { 482 size_type __old_size = _Base::bucket_count(); 483 iterator __res = _Base::insert(__obj); 484 this->_M_profile_resize(__old_size); 485 return __res; 486 } 487 488 iterator 489 insert(const_iterator __iter, const value_type& __v) 490 { 491 size_type __old_size = _Base::bucket_count(); 492 iterator __res = _Base::insert(__iter, __v); 493 this->_M_profile_resize(__old_size); 494 return __res; 495 } 496 497 iterator 498 insert(value_type&& __obj) 499 { 500 size_type __old_size = _Base::bucket_count(); 501 iterator __res = _Base::insert(std::move(__obj)); 502 this->_M_profile_resize(__old_size); 503 return __res; 504 } 505 506 iterator 507 insert(const_iterator __iter, value_type&& __v) 508 { 509 size_type __old_size = _Base::bucket_count(); 510 iterator __res = _Base::insert(__iter, std::move(__v)); 511 this->_M_profile_resize(__old_size); 512 return __res; 513 } 514 515 template<typename _InputIter> 516 void 517 insert(_InputIter __first, _InputIter __last) 518 { 519 size_type __old_size = _Base::bucket_count(); 520 _Base::insert(__first, __last); 521 this->_M_profile_resize(__old_size); 522 } 523 524 void 525 rehash(size_type __n) 526 { 527 size_type __old_size = _Base::bucket_count(); 528 _Base::rehash(__n); 529 this->_M_profile_resize(__old_size); 530 } 531 }; 532 533 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 534 inline void 535 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 536 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 537 { __x.swap(__y); } 538 539 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 540 inline bool 541 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 542 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 543 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 544 545 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 546 inline bool 547 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 548 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 549 { return !(__x == __y); } 550 551} // namespace __profile 552} // namespace std 553 554#undef _GLIBCXX_BASE 555#undef _GLIBCXX_STD_BASE 556 557#endif // C++11 558 559#endif 560