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