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_HAS_NO_RVALUE_REFERENCES 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 #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 _LIBCPP_INLINE_VISIBILITY 445 unordered_set& operator=(unordered_set&& __u) 446 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 447 #endif 448 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 449 _LIBCPP_INLINE_VISIBILITY 450 unordered_set& operator=(initializer_list<value_type> __il); 451 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 452 453 _LIBCPP_INLINE_VISIBILITY 454 allocator_type get_allocator() const _NOEXCEPT 455 {return allocator_type(__table_.__node_alloc());} 456 457 _LIBCPP_INLINE_VISIBILITY 458 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 459 _LIBCPP_INLINE_VISIBILITY 460 size_type size() const _NOEXCEPT {return __table_.size();} 461 _LIBCPP_INLINE_VISIBILITY 462 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 463 464 _LIBCPP_INLINE_VISIBILITY 465 iterator begin() _NOEXCEPT {return __table_.begin();} 466 _LIBCPP_INLINE_VISIBILITY 467 iterator end() _NOEXCEPT {return __table_.end();} 468 _LIBCPP_INLINE_VISIBILITY 469 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 470 _LIBCPP_INLINE_VISIBILITY 471 const_iterator end() const _NOEXCEPT {return __table_.end();} 472 _LIBCPP_INLINE_VISIBILITY 473 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 474 _LIBCPP_INLINE_VISIBILITY 475 const_iterator cend() const _NOEXCEPT {return __table_.end();} 476 477 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 478 template <class... _Args> 479 _LIBCPP_INLINE_VISIBILITY 480 pair<iterator, bool> emplace(_Args&&... __args) 481 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 482 template <class... _Args> 483 _LIBCPP_INLINE_VISIBILITY 484 #if _LIBCPP_DEBUG_LEVEL >= 2 485 iterator emplace_hint(const_iterator __p, _Args&&... __args) 486 { 487 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 488 "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not" 489 " referring to this unordered_set"); 490 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 491 } 492 #else 493 iterator emplace_hint(const_iterator, _Args&&... __args) 494 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;} 495 #endif 496 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 497 _LIBCPP_INLINE_VISIBILITY 498 pair<iterator, bool> insert(const value_type& __x) 499 {return __table_.__insert_unique(__x);} 500 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 501 _LIBCPP_INLINE_VISIBILITY 502 pair<iterator, bool> insert(value_type&& __x) 503 {return __table_.__insert_unique(_VSTD::move(__x));} 504 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 505 _LIBCPP_INLINE_VISIBILITY 506 #if _LIBCPP_DEBUG_LEVEL >= 2 507 iterator insert(const_iterator __p, const value_type& __x) 508 { 509 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 510 "unordered_set::insert(const_iterator, const value_type&) called with an iterator not" 511 " referring to this unordered_set"); 512 return insert(__x).first; 513 } 514 #else 515 iterator insert(const_iterator, const value_type& __x) 516 {return insert(__x).first;} 517 #endif 518 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 519 _LIBCPP_INLINE_VISIBILITY 520 #if _LIBCPP_DEBUG_LEVEL >= 2 521 iterator insert(const_iterator __p, value_type&& __x) 522 { 523 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 524 "unordered_set::insert(const_iterator, value_type&&) called with an iterator not" 525 " referring to this unordered_set"); 526 return insert(_VSTD::move(__x)).first; 527 } 528 #else 529 iterator insert(const_iterator, value_type&& __x) 530 {return insert(_VSTD::move(__x)).first;} 531 #endif 532 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 533 template <class _InputIterator> 534 _LIBCPP_INLINE_VISIBILITY 535 void insert(_InputIterator __first, _InputIterator __last); 536 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 537 _LIBCPP_INLINE_VISIBILITY 538 void insert(initializer_list<value_type> __il) 539 {insert(__il.begin(), __il.end());} 540 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 541 542 _LIBCPP_INLINE_VISIBILITY 543 iterator erase(const_iterator __p) {return __table_.erase(__p);} 544 _LIBCPP_INLINE_VISIBILITY 545 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 546 _LIBCPP_INLINE_VISIBILITY 547 iterator erase(const_iterator __first, const_iterator __last) 548 {return __table_.erase(__first, __last);} 549 _LIBCPP_INLINE_VISIBILITY 550 void clear() _NOEXCEPT {__table_.clear();} 551 552 _LIBCPP_INLINE_VISIBILITY 553 void swap(unordered_set& __u) 554 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 555 {__table_.swap(__u.__table_);} 556 557 _LIBCPP_INLINE_VISIBILITY 558 hasher hash_function() const {return __table_.hash_function();} 559 _LIBCPP_INLINE_VISIBILITY 560 key_equal key_eq() const {return __table_.key_eq();} 561 562 _LIBCPP_INLINE_VISIBILITY 563 iterator find(const key_type& __k) {return __table_.find(__k);} 564 _LIBCPP_INLINE_VISIBILITY 565 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 566 _LIBCPP_INLINE_VISIBILITY 567 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 568 _LIBCPP_INLINE_VISIBILITY 569 pair<iterator, iterator> equal_range(const key_type& __k) 570 {return __table_.__equal_range_unique(__k);} 571 _LIBCPP_INLINE_VISIBILITY 572 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 573 {return __table_.__equal_range_unique(__k);} 574 575 _LIBCPP_INLINE_VISIBILITY 576 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 577 _LIBCPP_INLINE_VISIBILITY 578 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 579 580 _LIBCPP_INLINE_VISIBILITY 581 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 582 _LIBCPP_INLINE_VISIBILITY 583 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 584 585 _LIBCPP_INLINE_VISIBILITY 586 local_iterator begin(size_type __n) {return __table_.begin(__n);} 587 _LIBCPP_INLINE_VISIBILITY 588 local_iterator end(size_type __n) {return __table_.end(__n);} 589 _LIBCPP_INLINE_VISIBILITY 590 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 591 _LIBCPP_INLINE_VISIBILITY 592 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 593 _LIBCPP_INLINE_VISIBILITY 594 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 595 _LIBCPP_INLINE_VISIBILITY 596 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 597 598 _LIBCPP_INLINE_VISIBILITY 599 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 600 _LIBCPP_INLINE_VISIBILITY 601 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 602 _LIBCPP_INLINE_VISIBILITY 603 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 604 _LIBCPP_INLINE_VISIBILITY 605 void rehash(size_type __n) {__table_.rehash(__n);} 606 _LIBCPP_INLINE_VISIBILITY 607 void reserve(size_type __n) {__table_.reserve(__n);} 608 609 #if _LIBCPP_DEBUG_LEVEL >= 2 610 611 bool __dereferenceable(const const_iterator* __i) const 612 {return __table_.__dereferenceable(__i);} 613 bool __decrementable(const const_iterator* __i) const 614 {return __table_.__decrementable(__i);} 615 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 616 {return __table_.__addable(__i, __n);} 617 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 618 {return __table_.__addable(__i, __n);} 619 620 #endif // _LIBCPP_DEBUG_LEVEL >= 2 621 622 }; 623 624 template <class _Value, class _Hash, class _Pred, class _Alloc> 625 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 626 const hasher& __hf, const key_equal& __eql) 627 : __table_(__hf, __eql) 628 { 629 #if _LIBCPP_DEBUG_LEVEL >= 2 630 __get_db()->__insert_c(this); 631 #endif 632 __table_.rehash(__n); 633 } 634 635 template <class _Value, class _Hash, class _Pred, class _Alloc> 636 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 637 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 638 : __table_(__hf, __eql, __a) 639 { 640 #if _LIBCPP_DEBUG_LEVEL >= 2 641 __get_db()->__insert_c(this); 642 #endif 643 __table_.rehash(__n); 644 } 645 646 template <class _Value, class _Hash, class _Pred, class _Alloc> 647 template <class _InputIterator> 648 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 649 _InputIterator __first, _InputIterator __last) 650 { 651 #if _LIBCPP_DEBUG_LEVEL >= 2 652 __get_db()->__insert_c(this); 653 #endif 654 insert(__first, __last); 655 } 656 657 template <class _Value, class _Hash, class _Pred, class _Alloc> 658 template <class _InputIterator> 659 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 660 _InputIterator __first, _InputIterator __last, size_type __n, 661 const hasher& __hf, const key_equal& __eql) 662 : __table_(__hf, __eql) 663 { 664 #if _LIBCPP_DEBUG_LEVEL >= 2 665 __get_db()->__insert_c(this); 666 #endif 667 __table_.rehash(__n); 668 insert(__first, __last); 669 } 670 671 template <class _Value, class _Hash, class _Pred, class _Alloc> 672 template <class _InputIterator> 673 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 674 _InputIterator __first, _InputIterator __last, size_type __n, 675 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 676 : __table_(__hf, __eql, __a) 677 { 678 #if _LIBCPP_DEBUG_LEVEL >= 2 679 __get_db()->__insert_c(this); 680 #endif 681 __table_.rehash(__n); 682 insert(__first, __last); 683 } 684 685 template <class _Value, class _Hash, class _Pred, class _Alloc> 686 inline 687 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 688 const allocator_type& __a) 689 : __table_(__a) 690 { 691 #if _LIBCPP_DEBUG_LEVEL >= 2 692 __get_db()->__insert_c(this); 693 #endif 694 } 695 696 template <class _Value, class _Hash, class _Pred, class _Alloc> 697 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 698 const unordered_set& __u) 699 : __table_(__u.__table_) 700 { 701 #if _LIBCPP_DEBUG_LEVEL >= 2 702 __get_db()->__insert_c(this); 703 #endif 704 __table_.rehash(__u.bucket_count()); 705 insert(__u.begin(), __u.end()); 706 } 707 708 template <class _Value, class _Hash, class _Pred, class _Alloc> 709 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 710 const unordered_set& __u, const allocator_type& __a) 711 : __table_(__u.__table_, __a) 712 { 713 #if _LIBCPP_DEBUG_LEVEL >= 2 714 __get_db()->__insert_c(this); 715 #endif 716 __table_.rehash(__u.bucket_count()); 717 insert(__u.begin(), __u.end()); 718 } 719 720 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 721 722 template <class _Value, class _Hash, class _Pred, class _Alloc> 723 inline 724 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 725 unordered_set&& __u) 726 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 727 : __table_(_VSTD::move(__u.__table_)) 728 { 729 #if _LIBCPP_DEBUG_LEVEL >= 2 730 __get_db()->__insert_c(this); 731 __get_db()->swap(this, &__u); 732 #endif 733 } 734 735 template <class _Value, class _Hash, class _Pred, class _Alloc> 736 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 737 unordered_set&& __u, const allocator_type& __a) 738 : __table_(_VSTD::move(__u.__table_), __a) 739 { 740 #if _LIBCPP_DEBUG_LEVEL >= 2 741 __get_db()->__insert_c(this); 742 #endif 743 if (__a != __u.get_allocator()) 744 { 745 iterator __i = __u.begin(); 746 while (__u.size() != 0) 747 __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 748 } 749 #if _LIBCPP_DEBUG_LEVEL >= 2 750 else 751 __get_db()->swap(this, &__u); 752 #endif 753 } 754 755 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 756 757 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 758 759 template <class _Value, class _Hash, class _Pred, class _Alloc> 760 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 761 initializer_list<value_type> __il) 762 { 763 #if _LIBCPP_DEBUG_LEVEL >= 2 764 __get_db()->__insert_c(this); 765 #endif 766 insert(__il.begin(), __il.end()); 767 } 768 769 template <class _Value, class _Hash, class _Pred, class _Alloc> 770 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 771 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 772 const key_equal& __eql) 773 : __table_(__hf, __eql) 774 { 775 #if _LIBCPP_DEBUG_LEVEL >= 2 776 __get_db()->__insert_c(this); 777 #endif 778 __table_.rehash(__n); 779 insert(__il.begin(), __il.end()); 780 } 781 782 template <class _Value, class _Hash, class _Pred, class _Alloc> 783 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 784 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 785 const key_equal& __eql, const allocator_type& __a) 786 : __table_(__hf, __eql, __a) 787 { 788 #if _LIBCPP_DEBUG_LEVEL >= 2 789 __get_db()->__insert_c(this); 790 #endif 791 __table_.rehash(__n); 792 insert(__il.begin(), __il.end()); 793 } 794 795 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 796 797 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 798 799 template <class _Value, class _Hash, class _Pred, class _Alloc> 800 inline 801 unordered_set<_Value, _Hash, _Pred, _Alloc>& 802 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 803 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 804 { 805 __table_ = _VSTD::move(__u.__table_); 806 return *this; 807 } 808 809 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 810 811 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 812 813 template <class _Value, class _Hash, class _Pred, class _Alloc> 814 inline 815 unordered_set<_Value, _Hash, _Pred, _Alloc>& 816 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=( 817 initializer_list<value_type> __il) 818 { 819 __table_.__assign_unique(__il.begin(), __il.end()); 820 return *this; 821 } 822 823 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 824 825 template <class _Value, class _Hash, class _Pred, class _Alloc> 826 template <class _InputIterator> 827 inline 828 void 829 unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 830 _InputIterator __last) 831 { 832 for (; __first != __last; ++__first) 833 __table_.__insert_unique(*__first); 834 } 835 836 template <class _Value, class _Hash, class _Pred, class _Alloc> 837 inline _LIBCPP_INLINE_VISIBILITY 838 void 839 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 840 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 841 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 842 { 843 __x.swap(__y); 844 } 845 846 template <class _Value, class _Hash, class _Pred, class _Alloc> 847 bool 848 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 849 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 850 { 851 if (__x.size() != __y.size()) 852 return false; 853 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 854 const_iterator; 855 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 856 __i != __ex; ++__i) 857 { 858 const_iterator __j = __y.find(*__i); 859 if (__j == __ey || !(*__i == *__j)) 860 return false; 861 } 862 return true; 863 } 864 865 template <class _Value, class _Hash, class _Pred, class _Alloc> 866 inline _LIBCPP_INLINE_VISIBILITY 867 bool 868 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 869 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 870 { 871 return !(__x == __y); 872 } 873 874 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 875 class _Alloc = allocator<_Value> > 876 class _LIBCPP_TEMPLATE_VIS unordered_multiset 877 { 878 public: 879 // types 880 typedef _Value key_type; 881 typedef key_type value_type; 882 typedef _Hash hasher; 883 typedef _Pred key_equal; 884 typedef _Alloc allocator_type; 885 typedef value_type& reference; 886 typedef const value_type& const_reference; 887 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 888 "Invalid allocator::value_type"); 889 890 private: 891 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 892 893 __table __table_; 894 895 public: 896 typedef typename __table::pointer pointer; 897 typedef typename __table::const_pointer const_pointer; 898 typedef typename __table::size_type size_type; 899 typedef typename __table::difference_type difference_type; 900 901 typedef typename __table::const_iterator iterator; 902 typedef typename __table::const_iterator const_iterator; 903 typedef typename __table::const_local_iterator local_iterator; 904 typedef typename __table::const_local_iterator const_local_iterator; 905 906 _LIBCPP_INLINE_VISIBILITY 907 unordered_multiset() 908 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 909 { 910 #if _LIBCPP_DEBUG_LEVEL >= 2 911 __get_db()->__insert_c(this); 912 #endif 913 } 914 explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(), 915 const key_equal& __eql = key_equal()); 916 unordered_multiset(size_type __n, const hasher& __hf, 917 const key_equal& __eql, const allocator_type& __a); 918 #if _LIBCPP_STD_VER > 11 919 inline _LIBCPP_INLINE_VISIBILITY 920 unordered_multiset(size_type __n, const allocator_type& __a) 921 : unordered_multiset(__n, hasher(), key_equal(), __a) {} 922 inline _LIBCPP_INLINE_VISIBILITY 923 unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) 924 : unordered_multiset(__n, __hf, key_equal(), __a) {} 925 #endif 926 template <class _InputIterator> 927 unordered_multiset(_InputIterator __first, _InputIterator __last); 928 template <class _InputIterator> 929 unordered_multiset(_InputIterator __first, _InputIterator __last, 930 size_type __n, const hasher& __hf = hasher(), 931 const key_equal& __eql = key_equal()); 932 template <class _InputIterator> 933 unordered_multiset(_InputIterator __first, _InputIterator __last, 934 size_type __n , const hasher& __hf, 935 const key_equal& __eql, const allocator_type& __a); 936 #if _LIBCPP_STD_VER > 11 937 template <class _InputIterator> 938 inline _LIBCPP_INLINE_VISIBILITY 939 unordered_multiset(_InputIterator __first, _InputIterator __last, 940 size_type __n, const allocator_type& __a) 941 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} 942 template <class _InputIterator> 943 inline _LIBCPP_INLINE_VISIBILITY 944 unordered_multiset(_InputIterator __first, _InputIterator __last, 945 size_type __n, const hasher& __hf, const allocator_type& __a) 946 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} 947 #endif 948 _LIBCPP_INLINE_VISIBILITY 949 explicit unordered_multiset(const allocator_type& __a); 950 unordered_multiset(const unordered_multiset& __u); 951 unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 952 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 953 _LIBCPP_INLINE_VISIBILITY 954 unordered_multiset(unordered_multiset&& __u) 955 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 956 unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 957 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 958 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 959 unordered_multiset(initializer_list<value_type> __il); 960 unordered_multiset(initializer_list<value_type> __il, size_type __n, 961 const hasher& __hf = hasher(), 962 const key_equal& __eql = key_equal()); 963 unordered_multiset(initializer_list<value_type> __il, size_type __n, 964 const hasher& __hf, const key_equal& __eql, 965 const allocator_type& __a); 966 #if _LIBCPP_STD_VER > 11 967 inline _LIBCPP_INLINE_VISIBILITY 968 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 969 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} 970 inline _LIBCPP_INLINE_VISIBILITY 971 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 972 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} 973 #endif 974 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 975 // ~unordered_multiset() = default; 976 _LIBCPP_INLINE_VISIBILITY 977 unordered_multiset& operator=(const unordered_multiset& __u) 978 { 979 __table_ = __u.__table_; 980 return *this; 981 } 982 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 983 _LIBCPP_INLINE_VISIBILITY 984 unordered_multiset& operator=(unordered_multiset&& __u) 985 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 986 #endif 987 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 988 unordered_multiset& operator=(initializer_list<value_type> __il); 989 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 990 991 _LIBCPP_INLINE_VISIBILITY 992 allocator_type get_allocator() const _NOEXCEPT 993 {return allocator_type(__table_.__node_alloc());} 994 995 _LIBCPP_INLINE_VISIBILITY 996 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 997 _LIBCPP_INLINE_VISIBILITY 998 size_type size() const _NOEXCEPT {return __table_.size();} 999 _LIBCPP_INLINE_VISIBILITY 1000 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1001 1002 _LIBCPP_INLINE_VISIBILITY 1003 iterator begin() _NOEXCEPT {return __table_.begin();} 1004 _LIBCPP_INLINE_VISIBILITY 1005 iterator end() _NOEXCEPT {return __table_.end();} 1006 _LIBCPP_INLINE_VISIBILITY 1007 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1008 _LIBCPP_INLINE_VISIBILITY 1009 const_iterator end() const _NOEXCEPT {return __table_.end();} 1010 _LIBCPP_INLINE_VISIBILITY 1011 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1012 _LIBCPP_INLINE_VISIBILITY 1013 const_iterator cend() const _NOEXCEPT {return __table_.end();} 1014 1015 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1016 template <class... _Args> 1017 _LIBCPP_INLINE_VISIBILITY 1018 iterator emplace(_Args&&... __args) 1019 {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 1020 template <class... _Args> 1021 _LIBCPP_INLINE_VISIBILITY 1022 iterator emplace_hint(const_iterator __p, _Args&&... __args) 1023 {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1024 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1025 _LIBCPP_INLINE_VISIBILITY 1026 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1027 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1028 _LIBCPP_INLINE_VISIBILITY 1029 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} 1030 #endif 1031 _LIBCPP_INLINE_VISIBILITY 1032 iterator insert(const_iterator __p, const value_type& __x) 1033 {return __table_.__insert_multi(__p, __x);} 1034 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1035 _LIBCPP_INLINE_VISIBILITY 1036 iterator insert(const_iterator __p, value_type&& __x) 1037 {return __table_.__insert_multi(__p, _VSTD::move(__x));} 1038 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1039 template <class _InputIterator> 1040 _LIBCPP_INLINE_VISIBILITY 1041 void insert(_InputIterator __first, _InputIterator __last); 1042 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1043 _LIBCPP_INLINE_VISIBILITY 1044 void insert(initializer_list<value_type> __il) 1045 {insert(__il.begin(), __il.end());} 1046 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1047 1048 _LIBCPP_INLINE_VISIBILITY 1049 iterator erase(const_iterator __p) {return __table_.erase(__p);} 1050 _LIBCPP_INLINE_VISIBILITY 1051 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1052 _LIBCPP_INLINE_VISIBILITY 1053 iterator erase(const_iterator __first, const_iterator __last) 1054 {return __table_.erase(__first, __last);} 1055 _LIBCPP_INLINE_VISIBILITY 1056 void clear() _NOEXCEPT {__table_.clear();} 1057 1058 _LIBCPP_INLINE_VISIBILITY 1059 void swap(unordered_multiset& __u) 1060 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1061 {__table_.swap(__u.__table_);} 1062 1063 _LIBCPP_INLINE_VISIBILITY 1064 hasher hash_function() const {return __table_.hash_function();} 1065 _LIBCPP_INLINE_VISIBILITY 1066 key_equal key_eq() const {return __table_.key_eq();} 1067 1068 _LIBCPP_INLINE_VISIBILITY 1069 iterator find(const key_type& __k) {return __table_.find(__k);} 1070 _LIBCPP_INLINE_VISIBILITY 1071 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1072 _LIBCPP_INLINE_VISIBILITY 1073 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1074 _LIBCPP_INLINE_VISIBILITY 1075 pair<iterator, iterator> equal_range(const key_type& __k) 1076 {return __table_.__equal_range_multi(__k);} 1077 _LIBCPP_INLINE_VISIBILITY 1078 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1079 {return __table_.__equal_range_multi(__k);} 1080 1081 _LIBCPP_INLINE_VISIBILITY 1082 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1083 _LIBCPP_INLINE_VISIBILITY 1084 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 1085 1086 _LIBCPP_INLINE_VISIBILITY 1087 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 1088 _LIBCPP_INLINE_VISIBILITY 1089 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1090 1091 _LIBCPP_INLINE_VISIBILITY 1092 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1093 _LIBCPP_INLINE_VISIBILITY 1094 local_iterator end(size_type __n) {return __table_.end(__n);} 1095 _LIBCPP_INLINE_VISIBILITY 1096 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1097 _LIBCPP_INLINE_VISIBILITY 1098 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1099 _LIBCPP_INLINE_VISIBILITY 1100 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1101 _LIBCPP_INLINE_VISIBILITY 1102 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1103 1104 _LIBCPP_INLINE_VISIBILITY 1105 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1106 _LIBCPP_INLINE_VISIBILITY 1107 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1108 _LIBCPP_INLINE_VISIBILITY 1109 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1110 _LIBCPP_INLINE_VISIBILITY 1111 void rehash(size_type __n) {__table_.rehash(__n);} 1112 _LIBCPP_INLINE_VISIBILITY 1113 void reserve(size_type __n) {__table_.reserve(__n);} 1114 1115 #if _LIBCPP_DEBUG_LEVEL >= 2 1116 1117 bool __dereferenceable(const const_iterator* __i) const 1118 {return __table_.__dereferenceable(__i);} 1119 bool __decrementable(const const_iterator* __i) const 1120 {return __table_.__decrementable(__i);} 1121 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1122 {return __table_.__addable(__i, __n);} 1123 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1124 {return __table_.__addable(__i, __n);} 1125 1126 #endif // _LIBCPP_DEBUG_LEVEL >= 2 1127 1128 }; 1129 1130 template <class _Value, class _Hash, class _Pred, class _Alloc> 1131 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1132 size_type __n, const hasher& __hf, const key_equal& __eql) 1133 : __table_(__hf, __eql) 1134 { 1135 #if _LIBCPP_DEBUG_LEVEL >= 2 1136 __get_db()->__insert_c(this); 1137 #endif 1138 __table_.rehash(__n); 1139 } 1140 1141 template <class _Value, class _Hash, class _Pred, class _Alloc> 1142 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1143 size_type __n, const hasher& __hf, const key_equal& __eql, 1144 const allocator_type& __a) 1145 : __table_(__hf, __eql, __a) 1146 { 1147 #if _LIBCPP_DEBUG_LEVEL >= 2 1148 __get_db()->__insert_c(this); 1149 #endif 1150 __table_.rehash(__n); 1151 } 1152 1153 template <class _Value, class _Hash, class _Pred, class _Alloc> 1154 template <class _InputIterator> 1155 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1156 _InputIterator __first, _InputIterator __last) 1157 { 1158 #if _LIBCPP_DEBUG_LEVEL >= 2 1159 __get_db()->__insert_c(this); 1160 #endif 1161 insert(__first, __last); 1162 } 1163 1164 template <class _Value, class _Hash, class _Pred, class _Alloc> 1165 template <class _InputIterator> 1166 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1167 _InputIterator __first, _InputIterator __last, size_type __n, 1168 const hasher& __hf, const key_equal& __eql) 1169 : __table_(__hf, __eql) 1170 { 1171 #if _LIBCPP_DEBUG_LEVEL >= 2 1172 __get_db()->__insert_c(this); 1173 #endif 1174 __table_.rehash(__n); 1175 insert(__first, __last); 1176 } 1177 1178 template <class _Value, class _Hash, class _Pred, class _Alloc> 1179 template <class _InputIterator> 1180 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1181 _InputIterator __first, _InputIterator __last, size_type __n, 1182 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1183 : __table_(__hf, __eql, __a) 1184 { 1185 #if _LIBCPP_DEBUG_LEVEL >= 2 1186 __get_db()->__insert_c(this); 1187 #endif 1188 __table_.rehash(__n); 1189 insert(__first, __last); 1190 } 1191 1192 template <class _Value, class _Hash, class _Pred, class _Alloc> 1193 inline 1194 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1195 const allocator_type& __a) 1196 : __table_(__a) 1197 { 1198 #if _LIBCPP_DEBUG_LEVEL >= 2 1199 __get_db()->__insert_c(this); 1200 #endif 1201 } 1202 1203 template <class _Value, class _Hash, class _Pred, class _Alloc> 1204 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1205 const unordered_multiset& __u) 1206 : __table_(__u.__table_) 1207 { 1208 #if _LIBCPP_DEBUG_LEVEL >= 2 1209 __get_db()->__insert_c(this); 1210 #endif 1211 __table_.rehash(__u.bucket_count()); 1212 insert(__u.begin(), __u.end()); 1213 } 1214 1215 template <class _Value, class _Hash, class _Pred, class _Alloc> 1216 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1217 const unordered_multiset& __u, const allocator_type& __a) 1218 : __table_(__u.__table_, __a) 1219 { 1220 #if _LIBCPP_DEBUG_LEVEL >= 2 1221 __get_db()->__insert_c(this); 1222 #endif 1223 __table_.rehash(__u.bucket_count()); 1224 insert(__u.begin(), __u.end()); 1225 } 1226 1227 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1228 1229 template <class _Value, class _Hash, class _Pred, class _Alloc> 1230 inline 1231 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1232 unordered_multiset&& __u) 1233 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1234 : __table_(_VSTD::move(__u.__table_)) 1235 { 1236 #if _LIBCPP_DEBUG_LEVEL >= 2 1237 __get_db()->__insert_c(this); 1238 __get_db()->swap(this, &__u); 1239 #endif 1240 } 1241 1242 template <class _Value, class _Hash, class _Pred, class _Alloc> 1243 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1244 unordered_multiset&& __u, const allocator_type& __a) 1245 : __table_(_VSTD::move(__u.__table_), __a) 1246 { 1247 #if _LIBCPP_DEBUG_LEVEL >= 2 1248 __get_db()->__insert_c(this); 1249 #endif 1250 if (__a != __u.get_allocator()) 1251 { 1252 iterator __i = __u.begin(); 1253 while (__u.size() != 0) 1254 __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 1255 } 1256 #if _LIBCPP_DEBUG_LEVEL >= 2 1257 else 1258 __get_db()->swap(this, &__u); 1259 #endif 1260 } 1261 1262 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1263 1264 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1265 1266 template <class _Value, class _Hash, class _Pred, class _Alloc> 1267 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1268 initializer_list<value_type> __il) 1269 { 1270 #if _LIBCPP_DEBUG_LEVEL >= 2 1271 __get_db()->__insert_c(this); 1272 #endif 1273 insert(__il.begin(), __il.end()); 1274 } 1275 1276 template <class _Value, class _Hash, class _Pred, class _Alloc> 1277 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1278 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1279 const key_equal& __eql) 1280 : __table_(__hf, __eql) 1281 { 1282 #if _LIBCPP_DEBUG_LEVEL >= 2 1283 __get_db()->__insert_c(this); 1284 #endif 1285 __table_.rehash(__n); 1286 insert(__il.begin(), __il.end()); 1287 } 1288 1289 template <class _Value, class _Hash, class _Pred, class _Alloc> 1290 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1291 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1292 const key_equal& __eql, const allocator_type& __a) 1293 : __table_(__hf, __eql, __a) 1294 { 1295 #if _LIBCPP_DEBUG_LEVEL >= 2 1296 __get_db()->__insert_c(this); 1297 #endif 1298 __table_.rehash(__n); 1299 insert(__il.begin(), __il.end()); 1300 } 1301 1302 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1303 1304 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1305 1306 template <class _Value, class _Hash, class _Pred, class _Alloc> 1307 inline 1308 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1309 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1310 unordered_multiset&& __u) 1311 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1312 { 1313 __table_ = _VSTD::move(__u.__table_); 1314 return *this; 1315 } 1316 1317 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1318 1319 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1320 1321 template <class _Value, class _Hash, class _Pred, class _Alloc> 1322 inline 1323 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1324 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1325 initializer_list<value_type> __il) 1326 { 1327 __table_.__assign_multi(__il.begin(), __il.end()); 1328 return *this; 1329 } 1330 1331 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1332 1333 template <class _Value, class _Hash, class _Pred, class _Alloc> 1334 template <class _InputIterator> 1335 inline 1336 void 1337 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1338 _InputIterator __last) 1339 { 1340 for (; __first != __last; ++__first) 1341 __table_.__insert_multi(*__first); 1342 } 1343 1344 template <class _Value, class _Hash, class _Pred, class _Alloc> 1345 inline _LIBCPP_INLINE_VISIBILITY 1346 void 1347 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1348 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1349 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1350 { 1351 __x.swap(__y); 1352 } 1353 1354 template <class _Value, class _Hash, class _Pred, class _Alloc> 1355 bool 1356 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1357 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1358 { 1359 if (__x.size() != __y.size()) 1360 return false; 1361 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 1362 const_iterator; 1363 typedef pair<const_iterator, const_iterator> _EqRng; 1364 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 1365 { 1366 _EqRng __xeq = __x.equal_range(*__i); 1367 _EqRng __yeq = __y.equal_range(*__i); 1368 if (_VSTD::distance(__xeq.first, __xeq.second) != 1369 _VSTD::distance(__yeq.first, __yeq.second) || 1370 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1371 return false; 1372 __i = __xeq.second; 1373 } 1374 return true; 1375 } 1376 1377 template <class _Value, class _Hash, class _Pred, class _Alloc> 1378 inline _LIBCPP_INLINE_VISIBILITY 1379 bool 1380 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1381 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1382 { 1383 return !(__x == __y); 1384 } 1385 1386 _LIBCPP_END_NAMESPACE_STD 1387 1388 #endif // _LIBCPP_UNORDERED_SET 1389
