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 20namespace std 21{ 22 23template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 24 class Alloc = allocator<Value>> 25class unordered_set 26{ 27public: 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 173template <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 178template <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 183template <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 188template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 189 class Alloc = allocator<Value>> 190class unordered_multiset 191{ 192public: 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 337template <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 342template <class Value, class Hash, class Pred, class Alloc> 343 bool 344 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 345 const unordered_multiset<Value, Hash, Pred, Alloc>& y); 346 347template <class Value, class Hash, class Pred, class Alloc> 348 bool 349 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 350 const unordered_multiset<Value, Hash, Pred, Alloc>& y); 351} // std 352 353*/ 354 355#include <__config> 356#include <__hash_table> 357#include <__node_handle> 358#include <functional> 359#include <version> 360 361#include <__debug> 362 363#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 364#pragma GCC system_header 365#endif 366 367_LIBCPP_BEGIN_NAMESPACE_STD 368 369template <class _Value, class _Hash, class _Pred, class _Alloc> 370class unordered_multiset; 371 372template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 373 class _Alloc = allocator<_Value> > 374class _LIBCPP_TEMPLATE_VIS unordered_set 375{ 376public: 377 // types 378 typedef _Value key_type; 379 typedef key_type value_type; 380 typedef _Hash hasher; 381 typedef _Pred key_equal; 382 typedef _Alloc allocator_type; 383 typedef value_type& reference; 384 typedef const value_type& const_reference; 385 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 386 "Invalid allocator::value_type"); 387 388private: 389 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 390 391 __table __table_; 392 393public: 394 typedef typename __table::pointer pointer; 395 typedef typename __table::const_pointer const_pointer; 396 typedef typename __table::size_type size_type; 397 typedef typename __table::difference_type difference_type; 398 399 typedef typename __table::const_iterator iterator; 400 typedef typename __table::const_iterator const_iterator; 401 typedef typename __table::const_local_iterator local_iterator; 402 typedef typename __table::const_local_iterator const_local_iterator; 403 404#if _LIBCPP_STD_VER > 14 405 typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 406 typedef __insert_return_type<iterator, node_type> insert_return_type; 407#endif 408 409 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 410 friend class _LIBCPP_TEMPLATE_VIS unordered_set; 411 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 412 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 413 414 _LIBCPP_INLINE_VISIBILITY 415 unordered_set() 416 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 417 { 418#if _LIBCPP_DEBUG_LEVEL >= 2 419 __get_db()->__insert_c(this); 420#endif 421 } 422 explicit unordered_set(size_type __n, const hasher& __hf = hasher(), 423 const key_equal& __eql = key_equal()); 424#if _LIBCPP_STD_VER > 11 425 inline _LIBCPP_INLINE_VISIBILITY 426 unordered_set(size_type __n, const allocator_type& __a) 427 : unordered_set(__n, hasher(), key_equal(), __a) {} 428 inline _LIBCPP_INLINE_VISIBILITY 429 unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a) 430 : unordered_set(__n, __hf, key_equal(), __a) {} 431#endif 432 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, 433 const allocator_type& __a); 434 template <class _InputIterator> 435 unordered_set(_InputIterator __first, _InputIterator __last); 436 template <class _InputIterator> 437 unordered_set(_InputIterator __first, _InputIterator __last, 438 size_type __n, const hasher& __hf = hasher(), 439 const key_equal& __eql = key_equal()); 440 template <class _InputIterator> 441 unordered_set(_InputIterator __first, _InputIterator __last, 442 size_type __n, const hasher& __hf, const key_equal& __eql, 443 const allocator_type& __a); 444#if _LIBCPP_STD_VER > 11 445 template <class _InputIterator> 446 inline _LIBCPP_INLINE_VISIBILITY 447 unordered_set(_InputIterator __first, _InputIterator __last, 448 size_type __n, const allocator_type& __a) 449 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} 450 template <class _InputIterator> 451 unordered_set(_InputIterator __first, _InputIterator __last, 452 size_type __n, const hasher& __hf, const allocator_type& __a) 453 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} 454#endif 455 _LIBCPP_INLINE_VISIBILITY 456 explicit unordered_set(const allocator_type& __a); 457 unordered_set(const unordered_set& __u); 458 unordered_set(const unordered_set& __u, const allocator_type& __a); 459#ifndef _LIBCPP_CXX03_LANG 460 _LIBCPP_INLINE_VISIBILITY 461 unordered_set(unordered_set&& __u) 462 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 463 unordered_set(unordered_set&& __u, const allocator_type& __a); 464 unordered_set(initializer_list<value_type> __il); 465 unordered_set(initializer_list<value_type> __il, size_type __n, 466 const hasher& __hf = hasher(), 467 const key_equal& __eql = key_equal()); 468 unordered_set(initializer_list<value_type> __il, size_type __n, 469 const hasher& __hf, const key_equal& __eql, 470 const allocator_type& __a); 471#if _LIBCPP_STD_VER > 11 472 inline _LIBCPP_INLINE_VISIBILITY 473 unordered_set(initializer_list<value_type> __il, size_type __n, 474 const allocator_type& __a) 475 : unordered_set(__il, __n, hasher(), key_equal(), __a) {} 476 inline _LIBCPP_INLINE_VISIBILITY 477 unordered_set(initializer_list<value_type> __il, size_type __n, 478 const hasher& __hf, const allocator_type& __a) 479 : unordered_set(__il, __n, __hf, key_equal(), __a) {} 480#endif 481#endif // _LIBCPP_CXX03_LANG 482 // ~unordered_set() = default; 483 _LIBCPP_INLINE_VISIBILITY 484 unordered_set& operator=(const unordered_set& __u) 485 { 486 __table_ = __u.__table_; 487 return *this; 488 } 489#ifndef _LIBCPP_CXX03_LANG 490 _LIBCPP_INLINE_VISIBILITY 491 unordered_set& operator=(unordered_set&& __u) 492 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 493 _LIBCPP_INLINE_VISIBILITY 494 unordered_set& operator=(initializer_list<value_type> __il); 495#endif // _LIBCPP_CXX03_LANG 496 497 _LIBCPP_INLINE_VISIBILITY 498 allocator_type get_allocator() const _NOEXCEPT 499 {return allocator_type(__table_.__node_alloc());} 500 501 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 502 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 503 _LIBCPP_INLINE_VISIBILITY 504 size_type size() const _NOEXCEPT {return __table_.size();} 505 _LIBCPP_INLINE_VISIBILITY 506 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 507 508 _LIBCPP_INLINE_VISIBILITY 509 iterator begin() _NOEXCEPT {return __table_.begin();} 510 _LIBCPP_INLINE_VISIBILITY 511 iterator end() _NOEXCEPT {return __table_.end();} 512 _LIBCPP_INLINE_VISIBILITY 513 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 514 _LIBCPP_INLINE_VISIBILITY 515 const_iterator end() const _NOEXCEPT {return __table_.end();} 516 _LIBCPP_INLINE_VISIBILITY 517 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 518 _LIBCPP_INLINE_VISIBILITY 519 const_iterator cend() const _NOEXCEPT {return __table_.end();} 520 521#ifndef _LIBCPP_CXX03_LANG 522 template <class... _Args> 523 _LIBCPP_INLINE_VISIBILITY 524 pair<iterator, bool> emplace(_Args&&... __args) 525 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 526 template <class... _Args> 527 _LIBCPP_INLINE_VISIBILITY 528#if _LIBCPP_DEBUG_LEVEL >= 2 529 iterator emplace_hint(const_iterator __p, _Args&&... __args) 530 { 531 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 532 "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not" 533 " referring to this unordered_set"); 534 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 535 } 536#else 537 iterator emplace_hint(const_iterator, _Args&&... __args) 538 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;} 539#endif 540 541 _LIBCPP_INLINE_VISIBILITY 542 pair<iterator, bool> insert(value_type&& __x) 543 {return __table_.__insert_unique(_VSTD::move(__x));} 544 _LIBCPP_INLINE_VISIBILITY 545#if _LIBCPP_DEBUG_LEVEL >= 2 546 iterator insert(const_iterator __p, value_type&& __x) 547 { 548 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 549 "unordered_set::insert(const_iterator, value_type&&) called with an iterator not" 550 " referring to this unordered_set"); 551 return insert(_VSTD::move(__x)).first; 552 } 553#else 554 iterator insert(const_iterator, value_type&& __x) 555 {return insert(_VSTD::move(__x)).first;} 556#endif 557 _LIBCPP_INLINE_VISIBILITY 558 void insert(initializer_list<value_type> __il) 559 {insert(__il.begin(), __il.end());} 560#endif // _LIBCPP_CXX03_LANG 561 _LIBCPP_INLINE_VISIBILITY 562 pair<iterator, bool> insert(const value_type& __x) 563 {return __table_.__insert_unique(__x);} 564 565 _LIBCPP_INLINE_VISIBILITY 566#if _LIBCPP_DEBUG_LEVEL >= 2 567 iterator insert(const_iterator __p, const value_type& __x) 568 { 569 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 570 "unordered_set::insert(const_iterator, const value_type&) called with an iterator not" 571 " referring to this unordered_set"); 572 return insert(__x).first; 573 } 574#else 575 iterator insert(const_iterator, const value_type& __x) 576 {return insert(__x).first;} 577#endif 578 template <class _InputIterator> 579 _LIBCPP_INLINE_VISIBILITY 580 void insert(_InputIterator __first, _InputIterator __last); 581 582 _LIBCPP_INLINE_VISIBILITY 583 iterator erase(const_iterator __p) {return __table_.erase(__p);} 584 _LIBCPP_INLINE_VISIBILITY 585 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 586 _LIBCPP_INLINE_VISIBILITY 587 iterator erase(const_iterator __first, const_iterator __last) 588 {return __table_.erase(__first, __last);} 589 _LIBCPP_INLINE_VISIBILITY 590 void clear() _NOEXCEPT {__table_.clear();} 591 592#if _LIBCPP_STD_VER > 14 593 _LIBCPP_INLINE_VISIBILITY 594 insert_return_type insert(node_type&& __nh) 595 { 596 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 597 "node_type with incompatible allocator passed to unordered_set::insert()"); 598 return __table_.template __node_handle_insert_unique< 599 node_type, insert_return_type>(_VSTD::move(__nh)); 600 } 601 _LIBCPP_INLINE_VISIBILITY 602 iterator insert(const_iterator __h, 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<node_type>( 607 __h, _VSTD::move(__nh)); 608 } 609 _LIBCPP_INLINE_VISIBILITY 610 node_type extract(key_type const& __key) 611 { 612 return __table_.template __node_handle_extract<node_type>(__key); 613 } 614 _LIBCPP_INLINE_VISIBILITY 615 node_type extract(const_iterator __it) 616 { 617 return __table_.template __node_handle_extract<node_type>(__it); 618 } 619 620 template<class _H2, class _P2> 621 _LIBCPP_INLINE_VISIBILITY 622 void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) 623 { 624 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 625 "merging container with incompatible allocator"); 626 __table_.__node_handle_merge_unique(__source.__table_); 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_multiset<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#endif 653 654 _LIBCPP_INLINE_VISIBILITY 655 void swap(unordered_set& __u) 656 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 657 {__table_.swap(__u.__table_);} 658 659 _LIBCPP_INLINE_VISIBILITY 660 hasher hash_function() const {return __table_.hash_function();} 661 _LIBCPP_INLINE_VISIBILITY 662 key_equal key_eq() const {return __table_.key_eq();} 663 664 _LIBCPP_INLINE_VISIBILITY 665 iterator find(const key_type& __k) {return __table_.find(__k);} 666 _LIBCPP_INLINE_VISIBILITY 667 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 668 _LIBCPP_INLINE_VISIBILITY 669 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 670 _LIBCPP_INLINE_VISIBILITY 671 pair<iterator, iterator> equal_range(const key_type& __k) 672 {return __table_.__equal_range_unique(__k);} 673 _LIBCPP_INLINE_VISIBILITY 674 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 675 {return __table_.__equal_range_unique(__k);} 676 677 _LIBCPP_INLINE_VISIBILITY 678 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 679 _LIBCPP_INLINE_VISIBILITY 680 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 681 682 _LIBCPP_INLINE_VISIBILITY 683 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 684 _LIBCPP_INLINE_VISIBILITY 685 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 686 687 _LIBCPP_INLINE_VISIBILITY 688 local_iterator begin(size_type __n) {return __table_.begin(__n);} 689 _LIBCPP_INLINE_VISIBILITY 690 local_iterator end(size_type __n) {return __table_.end(__n);} 691 _LIBCPP_INLINE_VISIBILITY 692 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 693 _LIBCPP_INLINE_VISIBILITY 694 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 695 _LIBCPP_INLINE_VISIBILITY 696 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 697 _LIBCPP_INLINE_VISIBILITY 698 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 699 700 _LIBCPP_INLINE_VISIBILITY 701 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 702 _LIBCPP_INLINE_VISIBILITY 703 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 704 _LIBCPP_INLINE_VISIBILITY 705 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 706 _LIBCPP_INLINE_VISIBILITY 707 void rehash(size_type __n) {__table_.rehash(__n);} 708 _LIBCPP_INLINE_VISIBILITY 709 void reserve(size_type __n) {__table_.reserve(__n);} 710 711#if _LIBCPP_DEBUG_LEVEL >= 2 712 713 bool __dereferenceable(const const_iterator* __i) const 714 {return __table_.__dereferenceable(__i);} 715 bool __decrementable(const const_iterator* __i) const 716 {return __table_.__decrementable(__i);} 717 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 718 {return __table_.__addable(__i, __n);} 719 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 720 {return __table_.__addable(__i, __n);} 721 722#endif // _LIBCPP_DEBUG_LEVEL >= 2 723 724}; 725 726template <class _Value, class _Hash, class _Pred, class _Alloc> 727unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 728 const hasher& __hf, const key_equal& __eql) 729 : __table_(__hf, __eql) 730{ 731#if _LIBCPP_DEBUG_LEVEL >= 2 732 __get_db()->__insert_c(this); 733#endif 734 __table_.rehash(__n); 735} 736 737template <class _Value, class _Hash, class _Pred, class _Alloc> 738unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 739 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 740 : __table_(__hf, __eql, __a) 741{ 742#if _LIBCPP_DEBUG_LEVEL >= 2 743 __get_db()->__insert_c(this); 744#endif 745 __table_.rehash(__n); 746} 747 748template <class _Value, class _Hash, class _Pred, class _Alloc> 749template <class _InputIterator> 750unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 751 _InputIterator __first, _InputIterator __last) 752{ 753#if _LIBCPP_DEBUG_LEVEL >= 2 754 __get_db()->__insert_c(this); 755#endif 756 insert(__first, __last); 757} 758 759template <class _Value, class _Hash, class _Pred, class _Alloc> 760template <class _InputIterator> 761unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 762 _InputIterator __first, _InputIterator __last, size_type __n, 763 const hasher& __hf, const key_equal& __eql) 764 : __table_(__hf, __eql) 765{ 766#if _LIBCPP_DEBUG_LEVEL >= 2 767 __get_db()->__insert_c(this); 768#endif 769 __table_.rehash(__n); 770 insert(__first, __last); 771} 772 773template <class _Value, class _Hash, class _Pred, class _Alloc> 774template <class _InputIterator> 775unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 776 _InputIterator __first, _InputIterator __last, size_type __n, 777 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 778 : __table_(__hf, __eql, __a) 779{ 780#if _LIBCPP_DEBUG_LEVEL >= 2 781 __get_db()->__insert_c(this); 782#endif 783 __table_.rehash(__n); 784 insert(__first, __last); 785} 786 787template <class _Value, class _Hash, class _Pred, class _Alloc> 788inline 789unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 790 const allocator_type& __a) 791 : __table_(__a) 792{ 793#if _LIBCPP_DEBUG_LEVEL >= 2 794 __get_db()->__insert_c(this); 795#endif 796} 797 798template <class _Value, class _Hash, class _Pred, class _Alloc> 799unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 800 const unordered_set& __u) 801 : __table_(__u.__table_) 802{ 803#if _LIBCPP_DEBUG_LEVEL >= 2 804 __get_db()->__insert_c(this); 805#endif 806 __table_.rehash(__u.bucket_count()); 807 insert(__u.begin(), __u.end()); 808} 809 810template <class _Value, class _Hash, class _Pred, class _Alloc> 811unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 812 const unordered_set& __u, const allocator_type& __a) 813 : __table_(__u.__table_, __a) 814{ 815#if _LIBCPP_DEBUG_LEVEL >= 2 816 __get_db()->__insert_c(this); 817#endif 818 __table_.rehash(__u.bucket_count()); 819 insert(__u.begin(), __u.end()); 820} 821 822#ifndef _LIBCPP_CXX03_LANG 823 824template <class _Value, class _Hash, class _Pred, class _Alloc> 825inline 826unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 827 unordered_set&& __u) 828 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 829 : __table_(_VSTD::move(__u.__table_)) 830{ 831#if _LIBCPP_DEBUG_LEVEL >= 2 832 __get_db()->__insert_c(this); 833 __get_db()->swap(this, &__u); 834#endif 835} 836 837template <class _Value, class _Hash, class _Pred, class _Alloc> 838unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 839 unordered_set&& __u, const allocator_type& __a) 840 : __table_(_VSTD::move(__u.__table_), __a) 841{ 842#if _LIBCPP_DEBUG_LEVEL >= 2 843 __get_db()->__insert_c(this); 844#endif 845 if (__a != __u.get_allocator()) 846 { 847 iterator __i = __u.begin(); 848 while (__u.size() != 0) 849 __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 850 } 851#if _LIBCPP_DEBUG_LEVEL >= 2 852 else 853 __get_db()->swap(this, &__u); 854#endif 855} 856 857template <class _Value, class _Hash, class _Pred, class _Alloc> 858unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 859 initializer_list<value_type> __il) 860{ 861#if _LIBCPP_DEBUG_LEVEL >= 2 862 __get_db()->__insert_c(this); 863#endif 864 insert(__il.begin(), __il.end()); 865} 866 867template <class _Value, class _Hash, class _Pred, class _Alloc> 868unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 869 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 870 const key_equal& __eql) 871 : __table_(__hf, __eql) 872{ 873#if _LIBCPP_DEBUG_LEVEL >= 2 874 __get_db()->__insert_c(this); 875#endif 876 __table_.rehash(__n); 877 insert(__il.begin(), __il.end()); 878} 879 880template <class _Value, class _Hash, class _Pred, class _Alloc> 881unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 882 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 883 const key_equal& __eql, const allocator_type& __a) 884 : __table_(__hf, __eql, __a) 885{ 886#if _LIBCPP_DEBUG_LEVEL >= 2 887 __get_db()->__insert_c(this); 888#endif 889 __table_.rehash(__n); 890 insert(__il.begin(), __il.end()); 891} 892 893template <class _Value, class _Hash, class _Pred, class _Alloc> 894inline 895unordered_set<_Value, _Hash, _Pred, _Alloc>& 896unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 897 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 898{ 899 __table_ = _VSTD::move(__u.__table_); 900 return *this; 901} 902 903template <class _Value, class _Hash, class _Pred, class _Alloc> 904inline 905unordered_set<_Value, _Hash, _Pred, _Alloc>& 906unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=( 907 initializer_list<value_type> __il) 908{ 909 __table_.__assign_unique(__il.begin(), __il.end()); 910 return *this; 911} 912 913#endif // _LIBCPP_CXX03_LANG 914 915template <class _Value, class _Hash, class _Pred, class _Alloc> 916template <class _InputIterator> 917inline 918void 919unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 920 _InputIterator __last) 921{ 922 for (; __first != __last; ++__first) 923 __table_.__insert_unique(*__first); 924} 925 926template <class _Value, class _Hash, class _Pred, class _Alloc> 927inline _LIBCPP_INLINE_VISIBILITY 928void 929swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 930 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 931 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 932{ 933 __x.swap(__y); 934} 935 936template <class _Value, class _Hash, class _Pred, class _Alloc> 937bool 938operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 939 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 940{ 941 if (__x.size() != __y.size()) 942 return false; 943 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 944 const_iterator; 945 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 946 __i != __ex; ++__i) 947 { 948 const_iterator __j = __y.find(*__i); 949 if (__j == __ey || !(*__i == *__j)) 950 return false; 951 } 952 return true; 953} 954 955template <class _Value, class _Hash, class _Pred, class _Alloc> 956inline _LIBCPP_INLINE_VISIBILITY 957bool 958operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 959 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 960{ 961 return !(__x == __y); 962} 963 964template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 965 class _Alloc = allocator<_Value> > 966class _LIBCPP_TEMPLATE_VIS unordered_multiset 967{ 968public: 969 // types 970 typedef _Value key_type; 971 typedef key_type value_type; 972 typedef _Hash hasher; 973 typedef _Pred key_equal; 974 typedef _Alloc allocator_type; 975 typedef value_type& reference; 976 typedef const value_type& const_reference; 977 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 978 "Invalid allocator::value_type"); 979 980private: 981 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 982 983 __table __table_; 984 985public: 986 typedef typename __table::pointer pointer; 987 typedef typename __table::const_pointer const_pointer; 988 typedef typename __table::size_type size_type; 989 typedef typename __table::difference_type difference_type; 990 991 typedef typename __table::const_iterator iterator; 992 typedef typename __table::const_iterator const_iterator; 993 typedef typename __table::const_local_iterator local_iterator; 994 typedef typename __table::const_local_iterator const_local_iterator; 995 996#if _LIBCPP_STD_VER > 14 997 typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 998#endif 999 1000 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 1001 friend class _LIBCPP_TEMPLATE_VIS unordered_set; 1002 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 1003 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 1004 1005 _LIBCPP_INLINE_VISIBILITY 1006 unordered_multiset() 1007 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1008 { 1009#if _LIBCPP_DEBUG_LEVEL >= 2 1010 __get_db()->__insert_c(this); 1011#endif 1012 } 1013 explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(), 1014 const key_equal& __eql = key_equal()); 1015 unordered_multiset(size_type __n, const hasher& __hf, 1016 const key_equal& __eql, const allocator_type& __a); 1017#if _LIBCPP_STD_VER > 11 1018 inline _LIBCPP_INLINE_VISIBILITY 1019 unordered_multiset(size_type __n, const allocator_type& __a) 1020 : unordered_multiset(__n, hasher(), key_equal(), __a) {} 1021 inline _LIBCPP_INLINE_VISIBILITY 1022 unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) 1023 : unordered_multiset(__n, __hf, key_equal(), __a) {} 1024#endif 1025 template <class _InputIterator> 1026 unordered_multiset(_InputIterator __first, _InputIterator __last); 1027 template <class _InputIterator> 1028 unordered_multiset(_InputIterator __first, _InputIterator __last, 1029 size_type __n, const hasher& __hf = hasher(), 1030 const key_equal& __eql = key_equal()); 1031 template <class _InputIterator> 1032 unordered_multiset(_InputIterator __first, _InputIterator __last, 1033 size_type __n , const hasher& __hf, 1034 const key_equal& __eql, const allocator_type& __a); 1035#if _LIBCPP_STD_VER > 11 1036 template <class _InputIterator> 1037 inline _LIBCPP_INLINE_VISIBILITY 1038 unordered_multiset(_InputIterator __first, _InputIterator __last, 1039 size_type __n, const allocator_type& __a) 1040 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} 1041 template <class _InputIterator> 1042 inline _LIBCPP_INLINE_VISIBILITY 1043 unordered_multiset(_InputIterator __first, _InputIterator __last, 1044 size_type __n, const hasher& __hf, const allocator_type& __a) 1045 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} 1046#endif 1047 _LIBCPP_INLINE_VISIBILITY 1048 explicit unordered_multiset(const allocator_type& __a); 1049 unordered_multiset(const unordered_multiset& __u); 1050 unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 1051#ifndef _LIBCPP_CXX03_LANG 1052 _LIBCPP_INLINE_VISIBILITY 1053 unordered_multiset(unordered_multiset&& __u) 1054 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1055 unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 1056 unordered_multiset(initializer_list<value_type> __il); 1057 unordered_multiset(initializer_list<value_type> __il, size_type __n, 1058 const hasher& __hf = hasher(), 1059 const key_equal& __eql = key_equal()); 1060 unordered_multiset(initializer_list<value_type> __il, size_type __n, 1061 const hasher& __hf, const key_equal& __eql, 1062 const allocator_type& __a); 1063#if _LIBCPP_STD_VER > 11 1064 inline _LIBCPP_INLINE_VISIBILITY 1065 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1066 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} 1067 inline _LIBCPP_INLINE_VISIBILITY 1068 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 1069 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} 1070#endif 1071#endif // _LIBCPP_CXX03_LANG 1072 // ~unordered_multiset() = default; 1073 _LIBCPP_INLINE_VISIBILITY 1074 unordered_multiset& operator=(const unordered_multiset& __u) 1075 { 1076 __table_ = __u.__table_; 1077 return *this; 1078 } 1079#ifndef _LIBCPP_CXX03_LANG 1080 _LIBCPP_INLINE_VISIBILITY 1081 unordered_multiset& operator=(unordered_multiset&& __u) 1082 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1083 unordered_multiset& operator=(initializer_list<value_type> __il); 1084#endif // _LIBCPP_CXX03_LANG 1085 1086 _LIBCPP_INLINE_VISIBILITY 1087 allocator_type get_allocator() const _NOEXCEPT 1088 {return allocator_type(__table_.__node_alloc());} 1089 1090 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1091 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1092 _LIBCPP_INLINE_VISIBILITY 1093 size_type size() const _NOEXCEPT {return __table_.size();} 1094 _LIBCPP_INLINE_VISIBILITY 1095 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1096 1097 _LIBCPP_INLINE_VISIBILITY 1098 iterator begin() _NOEXCEPT {return __table_.begin();} 1099 _LIBCPP_INLINE_VISIBILITY 1100 iterator end() _NOEXCEPT {return __table_.end();} 1101 _LIBCPP_INLINE_VISIBILITY 1102 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1103 _LIBCPP_INLINE_VISIBILITY 1104 const_iterator end() const _NOEXCEPT {return __table_.end();} 1105 _LIBCPP_INLINE_VISIBILITY 1106 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1107 _LIBCPP_INLINE_VISIBILITY 1108 const_iterator cend() const _NOEXCEPT {return __table_.end();} 1109 1110#ifndef _LIBCPP_CXX03_LANG 1111 template <class... _Args> 1112 _LIBCPP_INLINE_VISIBILITY 1113 iterator emplace(_Args&&... __args) 1114 {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 1115 template <class... _Args> 1116 _LIBCPP_INLINE_VISIBILITY 1117 iterator emplace_hint(const_iterator __p, _Args&&... __args) 1118 {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1119 1120 _LIBCPP_INLINE_VISIBILITY 1121 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} 1122 _LIBCPP_INLINE_VISIBILITY 1123 iterator insert(const_iterator __p, value_type&& __x) 1124 {return __table_.__insert_multi(__p, _VSTD::move(__x));} 1125 _LIBCPP_INLINE_VISIBILITY 1126 void insert(initializer_list<value_type> __il) 1127 {insert(__il.begin(), __il.end());} 1128#endif // _LIBCPP_CXX03_LANG 1129 1130 _LIBCPP_INLINE_VISIBILITY 1131 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1132 1133 _LIBCPP_INLINE_VISIBILITY 1134 iterator insert(const_iterator __p, const value_type& __x) 1135 {return __table_.__insert_multi(__p, __x);} 1136 1137 template <class _InputIterator> 1138 _LIBCPP_INLINE_VISIBILITY 1139 void insert(_InputIterator __first, _InputIterator __last); 1140 1141#if _LIBCPP_STD_VER > 14 1142 _LIBCPP_INLINE_VISIBILITY 1143 iterator insert(node_type&& __nh) 1144 { 1145 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1146 "node_type with incompatible allocator passed to unordered_multiset::insert()"); 1147 return __table_.template __node_handle_insert_multi<node_type>( 1148 _VSTD::move(__nh)); 1149 } 1150 _LIBCPP_INLINE_VISIBILITY 1151 iterator insert(const_iterator __hint, node_type&& __nh) 1152 { 1153 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1154 "node_type with incompatible allocator passed to unordered_multiset::insert()"); 1155 return __table_.template __node_handle_insert_multi<node_type>( 1156 __hint, _VSTD::move(__nh)); 1157 } 1158 _LIBCPP_INLINE_VISIBILITY 1159 node_type extract(const_iterator __position) 1160 { 1161 return __table_.template __node_handle_extract<node_type>( 1162 __position); 1163 } 1164 _LIBCPP_INLINE_VISIBILITY 1165 node_type extract(key_type const& __key) 1166 { 1167 return __table_.template __node_handle_extract<node_type>(__key); 1168 } 1169 1170 template <class _H2, class _P2> 1171 _LIBCPP_INLINE_VISIBILITY 1172 void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) 1173 { 1174 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1175 "merging container with incompatible allocator"); 1176 return __table_.__node_handle_merge_multi(__source.__table_); 1177 } 1178 template <class _H2, class _P2> 1179 _LIBCPP_INLINE_VISIBILITY 1180 void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) 1181 { 1182 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1183 "merging container with incompatible allocator"); 1184 return __table_.__node_handle_merge_multi(__source.__table_); 1185 } 1186 template <class _H2, class _P2> 1187 _LIBCPP_INLINE_VISIBILITY 1188 void merge(unordered_set<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_set<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#endif 1203 1204 _LIBCPP_INLINE_VISIBILITY 1205 iterator erase(const_iterator __p) {return __table_.erase(__p);} 1206 _LIBCPP_INLINE_VISIBILITY 1207 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1208 _LIBCPP_INLINE_VISIBILITY 1209 iterator erase(const_iterator __first, const_iterator __last) 1210 {return __table_.erase(__first, __last);} 1211 _LIBCPP_INLINE_VISIBILITY 1212 void clear() _NOEXCEPT {__table_.clear();} 1213 1214 _LIBCPP_INLINE_VISIBILITY 1215 void swap(unordered_multiset& __u) 1216 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1217 {__table_.swap(__u.__table_);} 1218 1219 _LIBCPP_INLINE_VISIBILITY 1220 hasher hash_function() const {return __table_.hash_function();} 1221 _LIBCPP_INLINE_VISIBILITY 1222 key_equal key_eq() const {return __table_.key_eq();} 1223 1224 _LIBCPP_INLINE_VISIBILITY 1225 iterator find(const key_type& __k) {return __table_.find(__k);} 1226 _LIBCPP_INLINE_VISIBILITY 1227 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1228 _LIBCPP_INLINE_VISIBILITY 1229 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1230 _LIBCPP_INLINE_VISIBILITY 1231 pair<iterator, iterator> equal_range(const key_type& __k) 1232 {return __table_.__equal_range_multi(__k);} 1233 _LIBCPP_INLINE_VISIBILITY 1234 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1235 {return __table_.__equal_range_multi(__k);} 1236 1237 _LIBCPP_INLINE_VISIBILITY 1238 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1239 _LIBCPP_INLINE_VISIBILITY 1240 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 1241 1242 _LIBCPP_INLINE_VISIBILITY 1243 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 1244 _LIBCPP_INLINE_VISIBILITY 1245 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1246 1247 _LIBCPP_INLINE_VISIBILITY 1248 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1249 _LIBCPP_INLINE_VISIBILITY 1250 local_iterator end(size_type __n) {return __table_.end(__n);} 1251 _LIBCPP_INLINE_VISIBILITY 1252 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1253 _LIBCPP_INLINE_VISIBILITY 1254 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1255 _LIBCPP_INLINE_VISIBILITY 1256 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1257 _LIBCPP_INLINE_VISIBILITY 1258 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1259 1260 _LIBCPP_INLINE_VISIBILITY 1261 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1262 _LIBCPP_INLINE_VISIBILITY 1263 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1264 _LIBCPP_INLINE_VISIBILITY 1265 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1266 _LIBCPP_INLINE_VISIBILITY 1267 void rehash(size_type __n) {__table_.rehash(__n);} 1268 _LIBCPP_INLINE_VISIBILITY 1269 void reserve(size_type __n) {__table_.reserve(__n);} 1270 1271#if _LIBCPP_DEBUG_LEVEL >= 2 1272 1273 bool __dereferenceable(const const_iterator* __i) const 1274 {return __table_.__dereferenceable(__i);} 1275 bool __decrementable(const const_iterator* __i) const 1276 {return __table_.__decrementable(__i);} 1277 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1278 {return __table_.__addable(__i, __n);} 1279 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1280 {return __table_.__addable(__i, __n);} 1281 1282#endif // _LIBCPP_DEBUG_LEVEL >= 2 1283 1284}; 1285 1286template <class _Value, class _Hash, class _Pred, class _Alloc> 1287unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1288 size_type __n, const hasher& __hf, const key_equal& __eql) 1289 : __table_(__hf, __eql) 1290{ 1291#if _LIBCPP_DEBUG_LEVEL >= 2 1292 __get_db()->__insert_c(this); 1293#endif 1294 __table_.rehash(__n); 1295} 1296 1297template <class _Value, class _Hash, class _Pred, class _Alloc> 1298unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1299 size_type __n, const hasher& __hf, const key_equal& __eql, 1300 const allocator_type& __a) 1301 : __table_(__hf, __eql, __a) 1302{ 1303#if _LIBCPP_DEBUG_LEVEL >= 2 1304 __get_db()->__insert_c(this); 1305#endif 1306 __table_.rehash(__n); 1307} 1308 1309template <class _Value, class _Hash, class _Pred, class _Alloc> 1310template <class _InputIterator> 1311unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1312 _InputIterator __first, _InputIterator __last) 1313{ 1314#if _LIBCPP_DEBUG_LEVEL >= 2 1315 __get_db()->__insert_c(this); 1316#endif 1317 insert(__first, __last); 1318} 1319 1320template <class _Value, class _Hash, class _Pred, class _Alloc> 1321template <class _InputIterator> 1322unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1323 _InputIterator __first, _InputIterator __last, size_type __n, 1324 const hasher& __hf, const key_equal& __eql) 1325 : __table_(__hf, __eql) 1326{ 1327#if _LIBCPP_DEBUG_LEVEL >= 2 1328 __get_db()->__insert_c(this); 1329#endif 1330 __table_.rehash(__n); 1331 insert(__first, __last); 1332} 1333 1334template <class _Value, class _Hash, class _Pred, class _Alloc> 1335template <class _InputIterator> 1336unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1337 _InputIterator __first, _InputIterator __last, size_type __n, 1338 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1339 : __table_(__hf, __eql, __a) 1340{ 1341#if _LIBCPP_DEBUG_LEVEL >= 2 1342 __get_db()->__insert_c(this); 1343#endif 1344 __table_.rehash(__n); 1345 insert(__first, __last); 1346} 1347 1348template <class _Value, class _Hash, class _Pred, class _Alloc> 1349inline 1350unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1351 const allocator_type& __a) 1352 : __table_(__a) 1353{ 1354#if _LIBCPP_DEBUG_LEVEL >= 2 1355 __get_db()->__insert_c(this); 1356#endif 1357} 1358 1359template <class _Value, class _Hash, class _Pred, class _Alloc> 1360unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1361 const unordered_multiset& __u) 1362 : __table_(__u.__table_) 1363{ 1364#if _LIBCPP_DEBUG_LEVEL >= 2 1365 __get_db()->__insert_c(this); 1366#endif 1367 __table_.rehash(__u.bucket_count()); 1368 insert(__u.begin(), __u.end()); 1369} 1370 1371template <class _Value, class _Hash, class _Pred, class _Alloc> 1372unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1373 const unordered_multiset& __u, const allocator_type& __a) 1374 : __table_(__u.__table_, __a) 1375{ 1376#if _LIBCPP_DEBUG_LEVEL >= 2 1377 __get_db()->__insert_c(this); 1378#endif 1379 __table_.rehash(__u.bucket_count()); 1380 insert(__u.begin(), __u.end()); 1381} 1382 1383#ifndef _LIBCPP_CXX03_LANG 1384 1385template <class _Value, class _Hash, class _Pred, class _Alloc> 1386inline 1387unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1388 unordered_multiset&& __u) 1389 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1390 : __table_(_VSTD::move(__u.__table_)) 1391{ 1392#if _LIBCPP_DEBUG_LEVEL >= 2 1393 __get_db()->__insert_c(this); 1394 __get_db()->swap(this, &__u); 1395#endif 1396} 1397 1398template <class _Value, class _Hash, class _Pred, class _Alloc> 1399unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1400 unordered_multiset&& __u, const allocator_type& __a) 1401 : __table_(_VSTD::move(__u.__table_), __a) 1402{ 1403#if _LIBCPP_DEBUG_LEVEL >= 2 1404 __get_db()->__insert_c(this); 1405#endif 1406 if (__a != __u.get_allocator()) 1407 { 1408 iterator __i = __u.begin(); 1409 while (__u.size() != 0) 1410 __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 1411 } 1412#if _LIBCPP_DEBUG_LEVEL >= 2 1413 else 1414 __get_db()->swap(this, &__u); 1415#endif 1416} 1417 1418template <class _Value, class _Hash, class _Pred, class _Alloc> 1419unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1420 initializer_list<value_type> __il) 1421{ 1422#if _LIBCPP_DEBUG_LEVEL >= 2 1423 __get_db()->__insert_c(this); 1424#endif 1425 insert(__il.begin(), __il.end()); 1426} 1427 1428template <class _Value, class _Hash, class _Pred, class _Alloc> 1429unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1430 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1431 const key_equal& __eql) 1432 : __table_(__hf, __eql) 1433{ 1434#if _LIBCPP_DEBUG_LEVEL >= 2 1435 __get_db()->__insert_c(this); 1436#endif 1437 __table_.rehash(__n); 1438 insert(__il.begin(), __il.end()); 1439} 1440 1441template <class _Value, class _Hash, class _Pred, class _Alloc> 1442unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1443 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1444 const key_equal& __eql, const allocator_type& __a) 1445 : __table_(__hf, __eql, __a) 1446{ 1447#if _LIBCPP_DEBUG_LEVEL >= 2 1448 __get_db()->__insert_c(this); 1449#endif 1450 __table_.rehash(__n); 1451 insert(__il.begin(), __il.end()); 1452} 1453 1454template <class _Value, class _Hash, class _Pred, class _Alloc> 1455inline 1456unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1457unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1458 unordered_multiset&& __u) 1459 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1460{ 1461 __table_ = _VSTD::move(__u.__table_); 1462 return *this; 1463} 1464 1465template <class _Value, class _Hash, class _Pred, class _Alloc> 1466inline 1467unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1468unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1469 initializer_list<value_type> __il) 1470{ 1471 __table_.__assign_multi(__il.begin(), __il.end()); 1472 return *this; 1473} 1474 1475#endif // _LIBCPP_CXX03_LANG 1476 1477template <class _Value, class _Hash, class _Pred, class _Alloc> 1478template <class _InputIterator> 1479inline 1480void 1481unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1482 _InputIterator __last) 1483{ 1484 for (; __first != __last; ++__first) 1485 __table_.__insert_multi(*__first); 1486} 1487 1488template <class _Value, class _Hash, class _Pred, class _Alloc> 1489inline _LIBCPP_INLINE_VISIBILITY 1490void 1491swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1492 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1493 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1494{ 1495 __x.swap(__y); 1496} 1497 1498template <class _Value, class _Hash, class _Pred, class _Alloc> 1499bool 1500operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1501 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1502{ 1503 if (__x.size() != __y.size()) 1504 return false; 1505 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 1506 const_iterator; 1507 typedef pair<const_iterator, const_iterator> _EqRng; 1508 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 1509 { 1510 _EqRng __xeq = __x.equal_range(*__i); 1511 _EqRng __yeq = __y.equal_range(*__i); 1512 if (_VSTD::distance(__xeq.first, __xeq.second) != 1513 _VSTD::distance(__yeq.first, __yeq.second) || 1514 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1515 return false; 1516 __i = __xeq.second; 1517 } 1518 return true; 1519} 1520 1521template <class _Value, class _Hash, class _Pred, class _Alloc> 1522inline _LIBCPP_INLINE_VISIBILITY 1523bool 1524operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1525 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1526{ 1527 return !(__x == __y); 1528} 1529 1530_LIBCPP_END_NAMESPACE_STD 1531 1532#endif // _LIBCPP_UNORDERED_SET 1533