1 // -*- C++ -*- 2 //===-------------------------- unordered_set -----------------------------===// 3 // 4 // The LLVM Compiler Infrastructure 5 // 6 // This file is dual licensed under the MIT and the University of Illinois Open 7 // Source Licenses. See LICENSE.TXT for details. 8 // 9 //===----------------------------------------------------------------------===// 10 11 #ifndef _LIBCPP_UNORDERED_SET 12 #define _LIBCPP_UNORDERED_SET 13 14 /* 15 16 unordered_set synopsis 17 18 #include <initializer_list> 19 20 namespace std 21 { 22 23 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 24 class Alloc = allocator<Value>> 25 class unordered_set 26 { 27 public: 28 // types 29 typedef Value key_type; 30 typedef key_type value_type; 31 typedef Hash hasher; 32 typedef Pred key_equal; 33 typedef Alloc allocator_type; 34 typedef value_type& reference; 35 typedef const value_type& const_reference; 36 typedef typename allocator_traits<allocator_type>::pointer pointer; 37 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 38 typedef typename allocator_traits<allocator_type>::size_type size_type; 39 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 40 41 typedef /unspecified/ iterator; 42 typedef /unspecified/ const_iterator; 43 typedef /unspecified/ local_iterator; 44 typedef /unspecified/ const_local_iterator; 45 46 unordered_set() 47 noexcept( 48 is_nothrow_default_constructible<hasher>::value && 49 is_nothrow_default_constructible<key_equal>::value && 50 is_nothrow_default_constructible<allocator_type>::value); 51 explicit unordered_set(size_type n, const hasher& hf = hasher(), 52 const key_equal& eql = key_equal(), 53 const allocator_type& a = allocator_type()); 54 template <class InputIterator> 55 unordered_set(InputIterator f, InputIterator l, 56 size_type n = 0, const hasher& hf = hasher(), 57 const key_equal& eql = key_equal(), 58 const allocator_type& a = allocator_type()); 59 explicit unordered_set(const allocator_type&); 60 unordered_set(const unordered_set&); 61 unordered_set(const unordered_set&, const Allocator&); 62 unordered_set(unordered_set&&) 63 noexcept( 64 is_nothrow_move_constructible<hasher>::value && 65 is_nothrow_move_constructible<key_equal>::value && 66 is_nothrow_move_constructible<allocator_type>::value); 67 unordered_set(unordered_set&&, const Allocator&); 68 unordered_set(initializer_list<value_type>, size_type n = 0, 69 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 70 const allocator_type& a = allocator_type()); 71 unordered_set(size_type n, const allocator_type& a); // C++14 72 unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14 73 template <class InputIterator> 74 unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 75 template <class InputIterator> 76 unordered_set(InputIterator f, InputIterator l, size_type n, 77 const hasher& hf, const allocator_type& a); // C++14 78 unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 79 unordered_set(initializer_list<value_type> il, size_type n, 80 const hasher& hf, const allocator_type& a); // C++14 81 ~unordered_set(); 82 unordered_set& operator=(const unordered_set&); 83 unordered_set& operator=(unordered_set&&) 84 noexcept( 85 allocator_type::propagate_on_container_move_assignment::value && 86 is_nothrow_move_assignable<allocator_type>::value && 87 is_nothrow_move_assignable<hasher>::value && 88 is_nothrow_move_assignable<key_equal>::value); 89 unordered_set& operator=(initializer_list<value_type>); 90 91 allocator_type get_allocator() const noexcept; 92 93 bool empty() const noexcept; 94 size_type size() const noexcept; 95 size_type max_size() const noexcept; 96 97 iterator begin() noexcept; 98 iterator end() noexcept; 99 const_iterator begin() const noexcept; 100 const_iterator end() const noexcept; 101 const_iterator cbegin() const noexcept; 102 const_iterator cend() const noexcept; 103 104 template <class... Args> 105 pair<iterator, bool> emplace(Args&&... args); 106 template <class... Args> 107 iterator emplace_hint(const_iterator position, Args&&... args); 108 pair<iterator, bool> insert(const value_type& obj); 109 pair<iterator, bool> insert(value_type&& obj); 110 iterator insert(const_iterator hint, const value_type& obj); 111 iterator insert(const_iterator hint, value_type&& obj); 112 template <class InputIterator> 113 void insert(InputIterator first, InputIterator last); 114 void insert(initializer_list<value_type>); 115 116 iterator erase(const_iterator position); 117 size_type erase(const key_type& k); 118 iterator erase(const_iterator first, const_iterator last); 119 void clear() noexcept; 120 121 void swap(unordered_set&) 122 noexcept( 123 (!allocator_type::propagate_on_container_swap::value || 124 __is_nothrow_swappable<allocator_type>::value) && 125 __is_nothrow_swappable<hasher>::value && 126 __is_nothrow_swappable<key_equal>::value); 127 128 hasher hash_function() const; 129 key_equal key_eq() const; 130 131 iterator find(const key_type& k); 132 const_iterator find(const key_type& k) const; 133 size_type count(const key_type& k) const; 134 pair<iterator, iterator> equal_range(const key_type& k); 135 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 136 137 size_type bucket_count() const noexcept; 138 size_type max_bucket_count() const noexcept; 139 140 size_type bucket_size(size_type n) const; 141 size_type bucket(const key_type& k) const; 142 143 local_iterator begin(size_type n); 144 local_iterator end(size_type n); 145 const_local_iterator begin(size_type n) const; 146 const_local_iterator end(size_type n) const; 147 const_local_iterator cbegin(size_type n) const; 148 const_local_iterator cend(size_type n) const; 149 150 float load_factor() const noexcept; 151 float max_load_factor() const noexcept; 152 void max_load_factor(float z); 153 void rehash(size_type n); 154 void reserve(size_type n); 155 }; 156 157 template <class Value, class Hash, class Pred, class Alloc> 158 void swap(unordered_set<Value, Hash, Pred, Alloc>& x, 159 unordered_set<Value, Hash, Pred, Alloc>& y) 160 noexcept(noexcept(x.swap(y))); 161 162 template <class Value, class Hash, class Pred, class Alloc> 163 bool 164 operator==(const unordered_set<Value, Hash, Pred, Alloc>& x, 165 const unordered_set<Value, Hash, Pred, Alloc>& y); 166 167 template <class Value, class Hash, class Pred, class Alloc> 168 bool 169 operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x, 170 const unordered_set<Value, Hash, Pred, Alloc>& y); 171 172 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 173 class Alloc = allocator<Value>> 174 class unordered_multiset 175 { 176 public: 177 // types 178 typedef Value key_type; 179 typedef key_type value_type; 180 typedef Hash hasher; 181 typedef Pred key_equal; 182 typedef Alloc allocator_type; 183 typedef value_type& reference; 184 typedef const value_type& const_reference; 185 typedef typename allocator_traits<allocator_type>::pointer pointer; 186 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 187 typedef typename allocator_traits<allocator_type>::size_type size_type; 188 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 189 190 typedef /unspecified/ iterator; 191 typedef /unspecified/ const_iterator; 192 typedef /unspecified/ local_iterator; 193 typedef /unspecified/ const_local_iterator; 194 195 unordered_multiset() 196 noexcept( 197 is_nothrow_default_constructible<hasher>::value && 198 is_nothrow_default_constructible<key_equal>::value && 199 is_nothrow_default_constructible<allocator_type>::value); 200 explicit unordered_multiset(size_type n, const hasher& hf = hasher(), 201 const key_equal& eql = key_equal(), 202 const allocator_type& a = allocator_type()); 203 template <class InputIterator> 204 unordered_multiset(InputIterator f, InputIterator l, 205 size_type n = 0, const hasher& hf = hasher(), 206 const key_equal& eql = key_equal(), 207 const allocator_type& a = allocator_type()); 208 explicit unordered_multiset(const allocator_type&); 209 unordered_multiset(const unordered_multiset&); 210 unordered_multiset(const unordered_multiset&, const Allocator&); 211 unordered_multiset(unordered_multiset&&) 212 noexcept( 213 is_nothrow_move_constructible<hasher>::value && 214 is_nothrow_move_constructible<key_equal>::value && 215 is_nothrow_move_constructible<allocator_type>::value); 216 unordered_multiset(unordered_multiset&&, const Allocator&); 217 unordered_multiset(initializer_list<value_type>, size_type n = /see below/, 218 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 219 const allocator_type& a = allocator_type()); 220 unordered_multiset(size_type n, const allocator_type& a); // C++14 221 unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14 222 template <class InputIterator> 223 unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 224 template <class InputIterator> 225 unordered_multiset(InputIterator f, InputIterator l, size_type n, 226 const hasher& hf, const allocator_type& a); // C++14 227 unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 228 unordered_multiset(initializer_list<value_type> il, size_type n, 229 const hasher& hf, const allocator_type& a); // C++14 230 ~unordered_multiset(); 231 unordered_multiset& operator=(const unordered_multiset&); 232 unordered_multiset& operator=(unordered_multiset&&) 233 noexcept( 234 allocator_type::propagate_on_container_move_assignment::value && 235 is_nothrow_move_assignable<allocator_type>::value && 236 is_nothrow_move_assignable<hasher>::value && 237 is_nothrow_move_assignable<key_equal>::value); 238 unordered_multiset& operator=(initializer_list<value_type>); 239 240 allocator_type get_allocator() const noexcept; 241 242 bool empty() const noexcept; 243 size_type size() const noexcept; 244 size_type max_size() const noexcept; 245 246 iterator begin() noexcept; 247 iterator end() noexcept; 248 const_iterator begin() const noexcept; 249 const_iterator end() const noexcept; 250 const_iterator cbegin() const noexcept; 251 const_iterator cend() const noexcept; 252 253 template <class... Args> 254 iterator emplace(Args&&... args); 255 template <class... Args> 256 iterator emplace_hint(const_iterator position, Args&&... args); 257 iterator insert(const value_type& obj); 258 iterator insert(value_type&& obj); 259 iterator insert(const_iterator hint, const value_type& obj); 260 iterator insert(const_iterator hint, value_type&& obj); 261 template <class InputIterator> 262 void insert(InputIterator first, InputIterator last); 263 void insert(initializer_list<value_type>); 264 265 iterator erase(const_iterator position); 266 size_type erase(const key_type& k); 267 iterator erase(const_iterator first, const_iterator last); 268 void clear() noexcept; 269 270 void swap(unordered_multiset&) 271 noexcept( 272 (!allocator_type::propagate_on_container_swap::value || 273 __is_nothrow_swappable<allocator_type>::value) && 274 __is_nothrow_swappable<hasher>::value && 275 __is_nothrow_swappable<key_equal>::value); 276 277 hasher hash_function() const; 278 key_equal key_eq() const; 279 280 iterator find(const key_type& k); 281 const_iterator find(const key_type& k) const; 282 size_type count(const key_type& k) const; 283 pair<iterator, iterator> equal_range(const key_type& k); 284 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 285 286 size_type bucket_count() const noexcept; 287 size_type max_bucket_count() const noexcept; 288 289 size_type bucket_size(size_type n) const; 290 size_type bucket(const key_type& k) const; 291 292 local_iterator begin(size_type n); 293 local_iterator end(size_type n); 294 const_local_iterator begin(size_type n) const; 295 const_local_iterator end(size_type n) const; 296 const_local_iterator cbegin(size_type n) const; 297 const_local_iterator cend(size_type n) const; 298 299 float load_factor() const noexcept; 300 float max_load_factor() const noexcept; 301 void max_load_factor(float z); 302 void rehash(size_type n); 303 void reserve(size_type n); 304 }; 305 306 template <class Value, class Hash, class Pred, class Alloc> 307 void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x, 308 unordered_multiset<Value, Hash, Pred, Alloc>& y) 309 noexcept(noexcept(x.swap(y))); 310 311 template <class Value, class Hash, class Pred, class Alloc> 312 bool 313 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 314 const unordered_multiset<Value, Hash, Pred, Alloc>& y); 315 316 template <class Value, class Hash, class Pred, class Alloc> 317 bool 318 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 319 const unordered_multiset<Value, Hash, Pred, Alloc>& y); 320 } // std 321 322 */ 323 324 #include <__config> 325 #include <__hash_table> 326 #include <functional> 327 328 #include <__debug> 329 330 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 331 #pragma GCC system_header 332 #endif 333 334 _LIBCPP_BEGIN_NAMESPACE_STD 335 336 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 337 class _Alloc = allocator<_Value> > 338 class _LIBCPP_TYPE_VIS_ONLY unordered_set 339 { 340 public: 341 // types 342 typedef _Value key_type; 343 typedef key_type value_type; 344 typedef _Hash hasher; 345 typedef _Pred key_equal; 346 typedef _Alloc allocator_type; 347 typedef value_type& reference; 348 typedef const value_type& const_reference; 349 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 350 "Invalid allocator::value_type"); 351 352 private: 353 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 354 355 __table __table_; 356 357 public: 358 typedef typename __table::pointer pointer; 359 typedef typename __table::const_pointer const_pointer; 360 typedef typename __table::size_type size_type; 361 typedef typename __table::difference_type difference_type; 362 363 typedef typename __table::const_iterator iterator; 364 typedef typename __table::const_iterator const_iterator; 365 typedef typename __table::const_local_iterator local_iterator; 366 typedef typename __table::const_local_iterator const_local_iterator; 367 368 _LIBCPP_INLINE_VISIBILITY 369 unordered_set() 370 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 371 { 372 #if _LIBCPP_DEBUG_LEVEL >= 2 373 __get_db()->__insert_c(this); 374 #endif 375 } 376 explicit unordered_set(size_type __n, const hasher& __hf = hasher(), 377 const key_equal& __eql = key_equal()); 378 #if _LIBCPP_STD_VER > 11 379 inline _LIBCPP_INLINE_VISIBILITY 380 unordered_set(size_type __n, const allocator_type& __a) 381 : unordered_set(__n, hasher(), key_equal(), __a) {} 382 inline _LIBCPP_INLINE_VISIBILITY 383 unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a) 384 : unordered_set(__n, __hf, key_equal(), __a) {} 385 #endif 386 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, 387 const allocator_type& __a); 388 template <class _InputIterator> 389 unordered_set(_InputIterator __first, _InputIterator __last); 390 template <class _InputIterator> 391 unordered_set(_InputIterator __first, _InputIterator __last, 392 size_type __n, const hasher& __hf = hasher(), 393 const key_equal& __eql = key_equal()); 394 template <class _InputIterator> 395 unordered_set(_InputIterator __first, _InputIterator __last, 396 size_type __n, const hasher& __hf, const key_equal& __eql, 397 const allocator_type& __a); 398 #if _LIBCPP_STD_VER > 11 399 template <class _InputIterator> 400 inline _LIBCPP_INLINE_VISIBILITY 401 unordered_set(_InputIterator __first, _InputIterator __last, 402 size_type __n, const allocator_type& __a) 403 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} 404 template <class _InputIterator> 405 unordered_set(_InputIterator __first, _InputIterator __last, 406 size_type __n, const hasher& __hf, const allocator_type& __a) 407 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} 408 #endif 409 explicit unordered_set(const allocator_type& __a); 410 unordered_set(const unordered_set& __u); 411 unordered_set(const unordered_set& __u, const allocator_type& __a); 412 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 413 unordered_set(unordered_set&& __u) 414 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 415 unordered_set(unordered_set&& __u, const allocator_type& __a); 416 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 417 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 418 unordered_set(initializer_list<value_type> __il); 419 unordered_set(initializer_list<value_type> __il, size_type __n, 420 const hasher& __hf = hasher(), 421 const key_equal& __eql = key_equal()); 422 unordered_set(initializer_list<value_type> __il, size_type __n, 423 const hasher& __hf, const key_equal& __eql, 424 const allocator_type& __a); 425 #if _LIBCPP_STD_VER > 11 426 inline _LIBCPP_INLINE_VISIBILITY 427 unordered_set(initializer_list<value_type> __il, size_type __n, 428 const allocator_type& __a) 429 : unordered_set(__il, __n, hasher(), key_equal(), __a) {} 430 inline _LIBCPP_INLINE_VISIBILITY 431 unordered_set(initializer_list<value_type> __il, size_type __n, 432 const hasher& __hf, const allocator_type& __a) 433 : unordered_set(__il, __n, __hf, key_equal(), __a) {} 434 #endif 435 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 436 // ~unordered_set() = default; 437 _LIBCPP_INLINE_VISIBILITY 438 unordered_set& operator=(const unordered_set& __u) 439 { 440 __table_ = __u.__table_; 441 return *this; 442 } 443 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 444 unordered_set& operator=(unordered_set&& __u) 445 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 446 #endif 447 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 448 unordered_set& operator=(initializer_list<value_type> __il); 449 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 450 451 _LIBCPP_INLINE_VISIBILITY 452 allocator_type get_allocator() const _NOEXCEPT 453 {return allocator_type(__table_.__node_alloc());} 454 455 _LIBCPP_INLINE_VISIBILITY 456 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 457 _LIBCPP_INLINE_VISIBILITY 458 size_type size() const _NOEXCEPT {return __table_.size();} 459 _LIBCPP_INLINE_VISIBILITY 460 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 461 462 _LIBCPP_INLINE_VISIBILITY 463 iterator begin() _NOEXCEPT {return __table_.begin();} 464 _LIBCPP_INLINE_VISIBILITY 465 iterator end() _NOEXCEPT {return __table_.end();} 466 _LIBCPP_INLINE_VISIBILITY 467 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 468 _LIBCPP_INLINE_VISIBILITY 469 const_iterator end() const _NOEXCEPT {return __table_.end();} 470 _LIBCPP_INLINE_VISIBILITY 471 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 472 _LIBCPP_INLINE_VISIBILITY 473 const_iterator cend() const _NOEXCEPT {return __table_.end();} 474 475 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 476 template <class... _Args> 477 _LIBCPP_INLINE_VISIBILITY 478 pair<iterator, bool> emplace(_Args&&... __args) 479 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 480 template <class... _Args> 481 _LIBCPP_INLINE_VISIBILITY 482 #if _LIBCPP_DEBUG_LEVEL >= 2 483 iterator emplace_hint(const_iterator __p, _Args&&... __args) 484 { 485 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 486 "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not" 487 " referring to this unordered_set"); 488 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 489 } 490 #else 491 iterator emplace_hint(const_iterator, _Args&&... __args) 492 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;} 493 #endif 494 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 495 _LIBCPP_INLINE_VISIBILITY 496 pair<iterator, bool> insert(const value_type& __x) 497 {return __table_.__insert_unique(__x);} 498 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 499 _LIBCPP_INLINE_VISIBILITY 500 pair<iterator, bool> insert(value_type&& __x) 501 {return __table_.__insert_unique(_VSTD::move(__x));} 502 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 503 _LIBCPP_INLINE_VISIBILITY 504 #if _LIBCPP_DEBUG_LEVEL >= 2 505 iterator insert(const_iterator __p, const value_type& __x) 506 { 507 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 508 "unordered_set::insert(const_iterator, const value_type&) called with an iterator not" 509 " referring to this unordered_set"); 510 return insert(__x).first; 511 } 512 #else 513 iterator insert(const_iterator, const value_type& __x) 514 {return insert(__x).first;} 515 #endif 516 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 517 _LIBCPP_INLINE_VISIBILITY 518 #if _LIBCPP_DEBUG_LEVEL >= 2 519 iterator insert(const_iterator __p, value_type&& __x) 520 { 521 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 522 "unordered_set::insert(const_iterator, value_type&&) called with an iterator not" 523 " referring to this unordered_set"); 524 return insert(_VSTD::move(__x)).first; 525 } 526 #else 527 iterator insert(const_iterator, value_type&& __x) 528 {return insert(_VSTD::move(__x)).first;} 529 #endif 530 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 531 template <class _InputIterator> 532 void insert(_InputIterator __first, _InputIterator __last); 533 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 534 _LIBCPP_INLINE_VISIBILITY 535 void insert(initializer_list<value_type> __il) 536 {insert(__il.begin(), __il.end());} 537 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 538 539 _LIBCPP_INLINE_VISIBILITY 540 iterator erase(const_iterator __p) {return __table_.erase(__p);} 541 _LIBCPP_INLINE_VISIBILITY 542 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 543 _LIBCPP_INLINE_VISIBILITY 544 iterator erase(const_iterator __first, const_iterator __last) 545 {return __table_.erase(__first, __last);} 546 _LIBCPP_INLINE_VISIBILITY 547 void clear() _NOEXCEPT {__table_.clear();} 548 549 _LIBCPP_INLINE_VISIBILITY 550 void swap(unordered_set& __u) 551 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 552 {__table_.swap(__u.__table_);} 553 554 _LIBCPP_INLINE_VISIBILITY 555 hasher hash_function() const {return __table_.hash_function();} 556 _LIBCPP_INLINE_VISIBILITY 557 key_equal key_eq() const {return __table_.key_eq();} 558 559 _LIBCPP_INLINE_VISIBILITY 560 iterator find(const key_type& __k) {return __table_.find(__k);} 561 _LIBCPP_INLINE_VISIBILITY 562 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 563 _LIBCPP_INLINE_VISIBILITY 564 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 565 _LIBCPP_INLINE_VISIBILITY 566 pair<iterator, iterator> equal_range(const key_type& __k) 567 {return __table_.__equal_range_unique(__k);} 568 _LIBCPP_INLINE_VISIBILITY 569 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 570 {return __table_.__equal_range_unique(__k);} 571 572 _LIBCPP_INLINE_VISIBILITY 573 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 574 _LIBCPP_INLINE_VISIBILITY 575 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 576 577 _LIBCPP_INLINE_VISIBILITY 578 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 579 _LIBCPP_INLINE_VISIBILITY 580 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 581 582 _LIBCPP_INLINE_VISIBILITY 583 local_iterator begin(size_type __n) {return __table_.begin(__n);} 584 _LIBCPP_INLINE_VISIBILITY 585 local_iterator end(size_type __n) {return __table_.end(__n);} 586 _LIBCPP_INLINE_VISIBILITY 587 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 588 _LIBCPP_INLINE_VISIBILITY 589 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 590 _LIBCPP_INLINE_VISIBILITY 591 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 592 _LIBCPP_INLINE_VISIBILITY 593 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 594 595 _LIBCPP_INLINE_VISIBILITY 596 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 597 _LIBCPP_INLINE_VISIBILITY 598 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 599 _LIBCPP_INLINE_VISIBILITY 600 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 601 _LIBCPP_INLINE_VISIBILITY 602 void rehash(size_type __n) {__table_.rehash(__n);} 603 _LIBCPP_INLINE_VISIBILITY 604 void reserve(size_type __n) {__table_.reserve(__n);} 605 606 #if _LIBCPP_DEBUG_LEVEL >= 2 607 608 bool __dereferenceable(const const_iterator* __i) const 609 {return __table_.__dereferenceable(__i);} 610 bool __decrementable(const const_iterator* __i) const 611 {return __table_.__decrementable(__i);} 612 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 613 {return __table_.__addable(__i, __n);} 614 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 615 {return __table_.__addable(__i, __n);} 616 617 #endif // _LIBCPP_DEBUG_LEVEL >= 2 618 619 }; 620 621 template <class _Value, class _Hash, class _Pred, class _Alloc> 622 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 623 const hasher& __hf, const key_equal& __eql) 624 : __table_(__hf, __eql) 625 { 626 #if _LIBCPP_DEBUG_LEVEL >= 2 627 __get_db()->__insert_c(this); 628 #endif 629 __table_.rehash(__n); 630 } 631 632 template <class _Value, class _Hash, class _Pred, class _Alloc> 633 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 634 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 635 : __table_(__hf, __eql, __a) 636 { 637 #if _LIBCPP_DEBUG_LEVEL >= 2 638 __get_db()->__insert_c(this); 639 #endif 640 __table_.rehash(__n); 641 } 642 643 template <class _Value, class _Hash, class _Pred, class _Alloc> 644 template <class _InputIterator> 645 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 646 _InputIterator __first, _InputIterator __last) 647 { 648 #if _LIBCPP_DEBUG_LEVEL >= 2 649 __get_db()->__insert_c(this); 650 #endif 651 insert(__first, __last); 652 } 653 654 template <class _Value, class _Hash, class _Pred, class _Alloc> 655 template <class _InputIterator> 656 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 657 _InputIterator __first, _InputIterator __last, size_type __n, 658 const hasher& __hf, const key_equal& __eql) 659 : __table_(__hf, __eql) 660 { 661 #if _LIBCPP_DEBUG_LEVEL >= 2 662 __get_db()->__insert_c(this); 663 #endif 664 __table_.rehash(__n); 665 insert(__first, __last); 666 } 667 668 template <class _Value, class _Hash, class _Pred, class _Alloc> 669 template <class _InputIterator> 670 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 671 _InputIterator __first, _InputIterator __last, size_type __n, 672 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 673 : __table_(__hf, __eql, __a) 674 { 675 #if _LIBCPP_DEBUG_LEVEL >= 2 676 __get_db()->__insert_c(this); 677 #endif 678 __table_.rehash(__n); 679 insert(__first, __last); 680 } 681 682 template <class _Value, class _Hash, class _Pred, class _Alloc> 683 inline _LIBCPP_INLINE_VISIBILITY 684 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 685 const allocator_type& __a) 686 : __table_(__a) 687 { 688 #if _LIBCPP_DEBUG_LEVEL >= 2 689 __get_db()->__insert_c(this); 690 #endif 691 } 692 693 template <class _Value, class _Hash, class _Pred, class _Alloc> 694 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 695 const unordered_set& __u) 696 : __table_(__u.__table_) 697 { 698 #if _LIBCPP_DEBUG_LEVEL >= 2 699 __get_db()->__insert_c(this); 700 #endif 701 __table_.rehash(__u.bucket_count()); 702 insert(__u.begin(), __u.end()); 703 } 704 705 template <class _Value, class _Hash, class _Pred, class _Alloc> 706 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 707 const unordered_set& __u, const allocator_type& __a) 708 : __table_(__u.__table_, __a) 709 { 710 #if _LIBCPP_DEBUG_LEVEL >= 2 711 __get_db()->__insert_c(this); 712 #endif 713 __table_.rehash(__u.bucket_count()); 714 insert(__u.begin(), __u.end()); 715 } 716 717 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 718 719 template <class _Value, class _Hash, class _Pred, class _Alloc> 720 inline _LIBCPP_INLINE_VISIBILITY 721 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 722 unordered_set&& __u) 723 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 724 : __table_(_VSTD::move(__u.__table_)) 725 { 726 #if _LIBCPP_DEBUG_LEVEL >= 2 727 __get_db()->__insert_c(this); 728 __get_db()->swap(this, &__u); 729 #endif 730 } 731 732 template <class _Value, class _Hash, class _Pred, class _Alloc> 733 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 734 unordered_set&& __u, const allocator_type& __a) 735 : __table_(_VSTD::move(__u.__table_), __a) 736 { 737 #if _LIBCPP_DEBUG_LEVEL >= 2 738 __get_db()->__insert_c(this); 739 #endif 740 if (__a != __u.get_allocator()) 741 { 742 iterator __i = __u.begin(); 743 while (__u.size() != 0) 744 __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 745 } 746 #if _LIBCPP_DEBUG_LEVEL >= 2 747 else 748 __get_db()->swap(this, &__u); 749 #endif 750 } 751 752 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 753 754 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 755 756 template <class _Value, class _Hash, class _Pred, class _Alloc> 757 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 758 initializer_list<value_type> __il) 759 { 760 #if _LIBCPP_DEBUG_LEVEL >= 2 761 __get_db()->__insert_c(this); 762 #endif 763 insert(__il.begin(), __il.end()); 764 } 765 766 template <class _Value, class _Hash, class _Pred, class _Alloc> 767 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 768 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 769 const key_equal& __eql) 770 : __table_(__hf, __eql) 771 { 772 #if _LIBCPP_DEBUG_LEVEL >= 2 773 __get_db()->__insert_c(this); 774 #endif 775 __table_.rehash(__n); 776 insert(__il.begin(), __il.end()); 777 } 778 779 template <class _Value, class _Hash, class _Pred, class _Alloc> 780 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 781 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 782 const key_equal& __eql, const allocator_type& __a) 783 : __table_(__hf, __eql, __a) 784 { 785 #if _LIBCPP_DEBUG_LEVEL >= 2 786 __get_db()->__insert_c(this); 787 #endif 788 __table_.rehash(__n); 789 insert(__il.begin(), __il.end()); 790 } 791 792 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 793 794 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 795 796 template <class _Value, class _Hash, class _Pred, class _Alloc> 797 inline _LIBCPP_INLINE_VISIBILITY 798 unordered_set<_Value, _Hash, _Pred, _Alloc>& 799 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 800 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 801 { 802 __table_ = _VSTD::move(__u.__table_); 803 return *this; 804 } 805 806 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 807 808 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 809 810 template <class _Value, class _Hash, class _Pred, class _Alloc> 811 inline _LIBCPP_INLINE_VISIBILITY 812 unordered_set<_Value, _Hash, _Pred, _Alloc>& 813 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=( 814 initializer_list<value_type> __il) 815 { 816 __table_.__assign_unique(__il.begin(), __il.end()); 817 return *this; 818 } 819 820 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 821 822 template <class _Value, class _Hash, class _Pred, class _Alloc> 823 template <class _InputIterator> 824 inline _LIBCPP_INLINE_VISIBILITY 825 void 826 unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 827 _InputIterator __last) 828 { 829 for (; __first != __last; ++__first) 830 __table_.__insert_unique(*__first); 831 } 832 833 template <class _Value, class _Hash, class _Pred, class _Alloc> 834 inline _LIBCPP_INLINE_VISIBILITY 835 void 836 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 837 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 838 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 839 { 840 __x.swap(__y); 841 } 842 843 template <class _Value, class _Hash, class _Pred, class _Alloc> 844 bool 845 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 846 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 847 { 848 if (__x.size() != __y.size()) 849 return false; 850 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 851 const_iterator; 852 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 853 __i != __ex; ++__i) 854 { 855 const_iterator __j = __y.find(*__i); 856 if (__j == __ey || !(*__i == *__j)) 857 return false; 858 } 859 return true; 860 } 861 862 template <class _Value, class _Hash, class _Pred, class _Alloc> 863 inline _LIBCPP_INLINE_VISIBILITY 864 bool 865 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 866 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 867 { 868 return !(__x == __y); 869 } 870 871 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 872 class _Alloc = allocator<_Value> > 873 class _LIBCPP_TYPE_VIS_ONLY unordered_multiset 874 { 875 public: 876 // types 877 typedef _Value key_type; 878 typedef key_type value_type; 879 typedef _Hash hasher; 880 typedef _Pred key_equal; 881 typedef _Alloc allocator_type; 882 typedef value_type& reference; 883 typedef const value_type& const_reference; 884 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 885 "Invalid allocator::value_type"); 886 887 private: 888 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 889 890 __table __table_; 891 892 public: 893 typedef typename __table::pointer pointer; 894 typedef typename __table::const_pointer const_pointer; 895 typedef typename __table::size_type size_type; 896 typedef typename __table::difference_type difference_type; 897 898 typedef typename __table::const_iterator iterator; 899 typedef typename __table::const_iterator const_iterator; 900 typedef typename __table::const_local_iterator local_iterator; 901 typedef typename __table::const_local_iterator const_local_iterator; 902 903 _LIBCPP_INLINE_VISIBILITY 904 unordered_multiset() 905 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 906 { 907 #if _LIBCPP_DEBUG_LEVEL >= 2 908 __get_db()->__insert_c(this); 909 #endif 910 } 911 explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(), 912 const key_equal& __eql = key_equal()); 913 unordered_multiset(size_type __n, const hasher& __hf, 914 const key_equal& __eql, const allocator_type& __a); 915 #if _LIBCPP_STD_VER > 11 916 inline _LIBCPP_INLINE_VISIBILITY 917 unordered_multiset(size_type __n, const allocator_type& __a) 918 : unordered_multiset(__n, hasher(), key_equal(), __a) {} 919 inline _LIBCPP_INLINE_VISIBILITY 920 unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) 921 : unordered_multiset(__n, __hf, key_equal(), __a) {} 922 #endif 923 template <class _InputIterator> 924 unordered_multiset(_InputIterator __first, _InputIterator __last); 925 template <class _InputIterator> 926 unordered_multiset(_InputIterator __first, _InputIterator __last, 927 size_type __n, const hasher& __hf = hasher(), 928 const key_equal& __eql = key_equal()); 929 template <class _InputIterator> 930 unordered_multiset(_InputIterator __first, _InputIterator __last, 931 size_type __n , const hasher& __hf, 932 const key_equal& __eql, const allocator_type& __a); 933 #if _LIBCPP_STD_VER > 11 934 template <class _InputIterator> 935 inline _LIBCPP_INLINE_VISIBILITY 936 unordered_multiset(_InputIterator __first, _InputIterator __last, 937 size_type __n, const allocator_type& __a) 938 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} 939 template <class _InputIterator> 940 inline _LIBCPP_INLINE_VISIBILITY 941 unordered_multiset(_InputIterator __first, _InputIterator __last, 942 size_type __n, const hasher& __hf, const allocator_type& __a) 943 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} 944 #endif 945 explicit unordered_multiset(const allocator_type& __a); 946 unordered_multiset(const unordered_multiset& __u); 947 unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 948 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 949 unordered_multiset(unordered_multiset&& __u) 950 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 951 unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 952 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 953 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 954 unordered_multiset(initializer_list<value_type> __il); 955 unordered_multiset(initializer_list<value_type> __il, size_type __n, 956 const hasher& __hf = hasher(), 957 const key_equal& __eql = key_equal()); 958 unordered_multiset(initializer_list<value_type> __il, size_type __n, 959 const hasher& __hf, const key_equal& __eql, 960 const allocator_type& __a); 961 #if _LIBCPP_STD_VER > 11 962 inline _LIBCPP_INLINE_VISIBILITY 963 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 964 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} 965 inline _LIBCPP_INLINE_VISIBILITY 966 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 967 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} 968 #endif 969 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 970 // ~unordered_multiset() = default; 971 _LIBCPP_INLINE_VISIBILITY 972 unordered_multiset& operator=(const unordered_multiset& __u) 973 { 974 __table_ = __u.__table_; 975 return *this; 976 } 977 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 978 unordered_multiset& operator=(unordered_multiset&& __u) 979 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 980 #endif 981 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 982 unordered_multiset& operator=(initializer_list<value_type> __il); 983 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 984 985 _LIBCPP_INLINE_VISIBILITY 986 allocator_type get_allocator() const _NOEXCEPT 987 {return allocator_type(__table_.__node_alloc());} 988 989 _LIBCPP_INLINE_VISIBILITY 990 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 991 _LIBCPP_INLINE_VISIBILITY 992 size_type size() const _NOEXCEPT {return __table_.size();} 993 _LIBCPP_INLINE_VISIBILITY 994 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 995 996 _LIBCPP_INLINE_VISIBILITY 997 iterator begin() _NOEXCEPT {return __table_.begin();} 998 _LIBCPP_INLINE_VISIBILITY 999 iterator end() _NOEXCEPT {return __table_.end();} 1000 _LIBCPP_INLINE_VISIBILITY 1001 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1002 _LIBCPP_INLINE_VISIBILITY 1003 const_iterator end() const _NOEXCEPT {return __table_.end();} 1004 _LIBCPP_INLINE_VISIBILITY 1005 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1006 _LIBCPP_INLINE_VISIBILITY 1007 const_iterator cend() const _NOEXCEPT {return __table_.end();} 1008 1009 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1010 template <class... _Args> 1011 _LIBCPP_INLINE_VISIBILITY 1012 iterator emplace(_Args&&... __args) 1013 {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 1014 template <class... _Args> 1015 _LIBCPP_INLINE_VISIBILITY 1016 iterator emplace_hint(const_iterator __p, _Args&&... __args) 1017 {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1018 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1019 _LIBCPP_INLINE_VISIBILITY 1020 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1021 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1022 _LIBCPP_INLINE_VISIBILITY 1023 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} 1024 #endif 1025 _LIBCPP_INLINE_VISIBILITY 1026 iterator insert(const_iterator __p, const value_type& __x) 1027 {return __table_.__insert_multi(__p, __x);} 1028 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1029 _LIBCPP_INLINE_VISIBILITY 1030 iterator insert(const_iterator __p, value_type&& __x) 1031 {return __table_.__insert_multi(__p, _VSTD::move(__x));} 1032 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1033 template <class _InputIterator> 1034 void insert(_InputIterator __first, _InputIterator __last); 1035 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1036 _LIBCPP_INLINE_VISIBILITY 1037 void insert(initializer_list<value_type> __il) 1038 {insert(__il.begin(), __il.end());} 1039 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1040 1041 _LIBCPP_INLINE_VISIBILITY 1042 iterator erase(const_iterator __p) {return __table_.erase(__p);} 1043 _LIBCPP_INLINE_VISIBILITY 1044 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1045 _LIBCPP_INLINE_VISIBILITY 1046 iterator erase(const_iterator __first, const_iterator __last) 1047 {return __table_.erase(__first, __last);} 1048 _LIBCPP_INLINE_VISIBILITY 1049 void clear() _NOEXCEPT {__table_.clear();} 1050 1051 _LIBCPP_INLINE_VISIBILITY 1052 void swap(unordered_multiset& __u) 1053 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1054 {__table_.swap(__u.__table_);} 1055 1056 _LIBCPP_INLINE_VISIBILITY 1057 hasher hash_function() const {return __table_.hash_function();} 1058 _LIBCPP_INLINE_VISIBILITY 1059 key_equal key_eq() const {return __table_.key_eq();} 1060 1061 _LIBCPP_INLINE_VISIBILITY 1062 iterator find(const key_type& __k) {return __table_.find(__k);} 1063 _LIBCPP_INLINE_VISIBILITY 1064 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1065 _LIBCPP_INLINE_VISIBILITY 1066 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1067 _LIBCPP_INLINE_VISIBILITY 1068 pair<iterator, iterator> equal_range(const key_type& __k) 1069 {return __table_.__equal_range_multi(__k);} 1070 _LIBCPP_INLINE_VISIBILITY 1071 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1072 {return __table_.__equal_range_multi(__k);} 1073 1074 _LIBCPP_INLINE_VISIBILITY 1075 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1076 _LIBCPP_INLINE_VISIBILITY 1077 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 1078 1079 _LIBCPP_INLINE_VISIBILITY 1080 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 1081 _LIBCPP_INLINE_VISIBILITY 1082 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1083 1084 _LIBCPP_INLINE_VISIBILITY 1085 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1086 _LIBCPP_INLINE_VISIBILITY 1087 local_iterator end(size_type __n) {return __table_.end(__n);} 1088 _LIBCPP_INLINE_VISIBILITY 1089 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1090 _LIBCPP_INLINE_VISIBILITY 1091 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1092 _LIBCPP_INLINE_VISIBILITY 1093 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1094 _LIBCPP_INLINE_VISIBILITY 1095 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1096 1097 _LIBCPP_INLINE_VISIBILITY 1098 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1099 _LIBCPP_INLINE_VISIBILITY 1100 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1101 _LIBCPP_INLINE_VISIBILITY 1102 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1103 _LIBCPP_INLINE_VISIBILITY 1104 void rehash(size_type __n) {__table_.rehash(__n);} 1105 _LIBCPP_INLINE_VISIBILITY 1106 void reserve(size_type __n) {__table_.reserve(__n);} 1107 1108 #if _LIBCPP_DEBUG_LEVEL >= 2 1109 1110 bool __dereferenceable(const const_iterator* __i) const 1111 {return __table_.__dereferenceable(__i);} 1112 bool __decrementable(const const_iterator* __i) const 1113 {return __table_.__decrementable(__i);} 1114 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1115 {return __table_.__addable(__i, __n);} 1116 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1117 {return __table_.__addable(__i, __n);} 1118 1119 #endif // _LIBCPP_DEBUG_LEVEL >= 2 1120 1121 }; 1122 1123 template <class _Value, class _Hash, class _Pred, class _Alloc> 1124 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1125 size_type __n, const hasher& __hf, const key_equal& __eql) 1126 : __table_(__hf, __eql) 1127 { 1128 #if _LIBCPP_DEBUG_LEVEL >= 2 1129 __get_db()->__insert_c(this); 1130 #endif 1131 __table_.rehash(__n); 1132 } 1133 1134 template <class _Value, class _Hash, class _Pred, class _Alloc> 1135 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1136 size_type __n, const hasher& __hf, const key_equal& __eql, 1137 const allocator_type& __a) 1138 : __table_(__hf, __eql, __a) 1139 { 1140 #if _LIBCPP_DEBUG_LEVEL >= 2 1141 __get_db()->__insert_c(this); 1142 #endif 1143 __table_.rehash(__n); 1144 } 1145 1146 template <class _Value, class _Hash, class _Pred, class _Alloc> 1147 template <class _InputIterator> 1148 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1149 _InputIterator __first, _InputIterator __last) 1150 { 1151 #if _LIBCPP_DEBUG_LEVEL >= 2 1152 __get_db()->__insert_c(this); 1153 #endif 1154 insert(__first, __last); 1155 } 1156 1157 template <class _Value, class _Hash, class _Pred, class _Alloc> 1158 template <class _InputIterator> 1159 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1160 _InputIterator __first, _InputIterator __last, size_type __n, 1161 const hasher& __hf, const key_equal& __eql) 1162 : __table_(__hf, __eql) 1163 { 1164 #if _LIBCPP_DEBUG_LEVEL >= 2 1165 __get_db()->__insert_c(this); 1166 #endif 1167 __table_.rehash(__n); 1168 insert(__first, __last); 1169 } 1170 1171 template <class _Value, class _Hash, class _Pred, class _Alloc> 1172 template <class _InputIterator> 1173 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1174 _InputIterator __first, _InputIterator __last, size_type __n, 1175 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1176 : __table_(__hf, __eql, __a) 1177 { 1178 #if _LIBCPP_DEBUG_LEVEL >= 2 1179 __get_db()->__insert_c(this); 1180 #endif 1181 __table_.rehash(__n); 1182 insert(__first, __last); 1183 } 1184 1185 template <class _Value, class _Hash, class _Pred, class _Alloc> 1186 inline _LIBCPP_INLINE_VISIBILITY 1187 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1188 const allocator_type& __a) 1189 : __table_(__a) 1190 { 1191 #if _LIBCPP_DEBUG_LEVEL >= 2 1192 __get_db()->__insert_c(this); 1193 #endif 1194 } 1195 1196 template <class _Value, class _Hash, class _Pred, class _Alloc> 1197 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1198 const unordered_multiset& __u) 1199 : __table_(__u.__table_) 1200 { 1201 #if _LIBCPP_DEBUG_LEVEL >= 2 1202 __get_db()->__insert_c(this); 1203 #endif 1204 __table_.rehash(__u.bucket_count()); 1205 insert(__u.begin(), __u.end()); 1206 } 1207 1208 template <class _Value, class _Hash, class _Pred, class _Alloc> 1209 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1210 const unordered_multiset& __u, const allocator_type& __a) 1211 : __table_(__u.__table_, __a) 1212 { 1213 #if _LIBCPP_DEBUG_LEVEL >= 2 1214 __get_db()->__insert_c(this); 1215 #endif 1216 __table_.rehash(__u.bucket_count()); 1217 insert(__u.begin(), __u.end()); 1218 } 1219 1220 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1221 1222 template <class _Value, class _Hash, class _Pred, class _Alloc> 1223 inline _LIBCPP_INLINE_VISIBILITY 1224 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1225 unordered_multiset&& __u) 1226 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1227 : __table_(_VSTD::move(__u.__table_)) 1228 { 1229 #if _LIBCPP_DEBUG_LEVEL >= 2 1230 __get_db()->__insert_c(this); 1231 __get_db()->swap(this, &__u); 1232 #endif 1233 } 1234 1235 template <class _Value, class _Hash, class _Pred, class _Alloc> 1236 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1237 unordered_multiset&& __u, const allocator_type& __a) 1238 : __table_(_VSTD::move(__u.__table_), __a) 1239 { 1240 #if _LIBCPP_DEBUG_LEVEL >= 2 1241 __get_db()->__insert_c(this); 1242 #endif 1243 if (__a != __u.get_allocator()) 1244 { 1245 iterator __i = __u.begin(); 1246 while (__u.size() != 0) 1247 __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 1248 } 1249 #if _LIBCPP_DEBUG_LEVEL >= 2 1250 else 1251 __get_db()->swap(this, &__u); 1252 #endif 1253 } 1254 1255 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1256 1257 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1258 1259 template <class _Value, class _Hash, class _Pred, class _Alloc> 1260 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1261 initializer_list<value_type> __il) 1262 { 1263 #if _LIBCPP_DEBUG_LEVEL >= 2 1264 __get_db()->__insert_c(this); 1265 #endif 1266 insert(__il.begin(), __il.end()); 1267 } 1268 1269 template <class _Value, class _Hash, class _Pred, class _Alloc> 1270 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1271 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1272 const key_equal& __eql) 1273 : __table_(__hf, __eql) 1274 { 1275 #if _LIBCPP_DEBUG_LEVEL >= 2 1276 __get_db()->__insert_c(this); 1277 #endif 1278 __table_.rehash(__n); 1279 insert(__il.begin(), __il.end()); 1280 } 1281 1282 template <class _Value, class _Hash, class _Pred, class _Alloc> 1283 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1284 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1285 const key_equal& __eql, const allocator_type& __a) 1286 : __table_(__hf, __eql, __a) 1287 { 1288 #if _LIBCPP_DEBUG_LEVEL >= 2 1289 __get_db()->__insert_c(this); 1290 #endif 1291 __table_.rehash(__n); 1292 insert(__il.begin(), __il.end()); 1293 } 1294 1295 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1296 1297 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1298 1299 template <class _Value, class _Hash, class _Pred, class _Alloc> 1300 inline _LIBCPP_INLINE_VISIBILITY 1301 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1302 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1303 unordered_multiset&& __u) 1304 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1305 { 1306 __table_ = _VSTD::move(__u.__table_); 1307 return *this; 1308 } 1309 1310 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1311 1312 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1313 1314 template <class _Value, class _Hash, class _Pred, class _Alloc> 1315 inline 1316 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1317 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1318 initializer_list<value_type> __il) 1319 { 1320 __table_.__assign_multi(__il.begin(), __il.end()); 1321 return *this; 1322 } 1323 1324 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1325 1326 template <class _Value, class _Hash, class _Pred, class _Alloc> 1327 template <class _InputIterator> 1328 inline _LIBCPP_INLINE_VISIBILITY 1329 void 1330 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1331 _InputIterator __last) 1332 { 1333 for (; __first != __last; ++__first) 1334 __table_.__insert_multi(*__first); 1335 } 1336 1337 template <class _Value, class _Hash, class _Pred, class _Alloc> 1338 inline _LIBCPP_INLINE_VISIBILITY 1339 void 1340 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1341 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1342 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1343 { 1344 __x.swap(__y); 1345 } 1346 1347 template <class _Value, class _Hash, class _Pred, class _Alloc> 1348 bool 1349 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1350 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1351 { 1352 if (__x.size() != __y.size()) 1353 return false; 1354 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 1355 const_iterator; 1356 typedef pair<const_iterator, const_iterator> _EqRng; 1357 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 1358 { 1359 _EqRng __xeq = __x.equal_range(*__i); 1360 _EqRng __yeq = __y.equal_range(*__i); 1361 if (_VSTD::distance(__xeq.first, __xeq.second) != 1362 _VSTD::distance(__yeq.first, __yeq.second) || 1363 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1364 return false; 1365 __i = __xeq.second; 1366 } 1367 return true; 1368 } 1369 1370 template <class _Value, class _Hash, class _Pred, class _Alloc> 1371 inline _LIBCPP_INLINE_VISIBILITY 1372 bool 1373 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1374 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1375 { 1376 return !(__x == __y); 1377 } 1378 1379 _LIBCPP_END_NAMESPACE_STD 1380 1381 #endif // _LIBCPP_UNORDERED_SET 1382
