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