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