unordered_set revision 262801
1160814Ssimon// -*- C++ -*- 2160814Ssimon//===-------------------------- unordered_set -----------------------------===// 3160814Ssimon// 4160814Ssimon// The LLVM Compiler Infrastructure 5160814Ssimon// 6160814Ssimon// This file is dual licensed under the MIT and the University of Illinois Open 7160814Ssimon// Source Licenses. See LICENSE.TXT for details. 8160814Ssimon// 9160814Ssimon//===----------------------------------------------------------------------===// 10160814Ssimon 11160814Ssimon#ifndef _LIBCPP_UNORDERED_SET 12160814Ssimon#define _LIBCPP_UNORDERED_SET 13160814Ssimon 14160814Ssimon/* 15194206Ssimon 16194206Ssimon unordered_set synopsis 17194206Ssimon 18194206Ssimon#include <initializer_list> 19160814Ssimon 20160814Ssimonnamespace std 21167612Ssimon{ 22160814Ssimon 23160814Ssimontemplate <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 24160814Ssimon class Alloc = allocator<Value>> 25194206Ssimonclass unordered_set 26194206Ssimon{ 27194206Ssimonpublic: 28160814Ssimon // types 29160814Ssimon typedef Value key_type; 30160814Ssimon typedef key_type value_type; 31160814Ssimon typedef Hash hasher; 32160814Ssimon typedef Pred key_equal; 33160814Ssimon typedef Alloc allocator_type; 34160814Ssimon typedef value_type& reference; 35160814Ssimon typedef const value_type& const_reference; 36160814Ssimon typedef typename allocator_traits<allocator_type>::pointer pointer; 37160814Ssimon typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 38160814Ssimon typedef typename allocator_traits<allocator_type>::size_type size_type; 39194206Ssimon typedef typename allocator_traits<allocator_type>::difference_type difference_type; 40194206Ssimon 41194206Ssimon typedef /unspecified/ iterator; 42160814Ssimon typedef /unspecified/ const_iterator; 43160814Ssimon typedef /unspecified/ local_iterator; 44160814Ssimon typedef /unspecified/ const_local_iterator; 45160814Ssimon 46160814Ssimon unordered_set() 47160814Ssimon noexcept( 48160814Ssimon is_nothrow_default_constructible<hasher>::value && 49160814Ssimon is_nothrow_default_constructible<key_equal>::value && 50160814Ssimon is_nothrow_default_constructible<allocator_type>::value); 51160814Ssimon explicit unordered_set(size_type n, const hasher& hf = hasher(), 52160814Ssimon const key_equal& eql = key_equal(), 53160814Ssimon const allocator_type& a = allocator_type()); 54160814Ssimon template <class InputIterator> 55160814Ssimon unordered_set(InputIterator f, InputIterator l, 56160814Ssimon size_type n = 0, const hasher& hf = hasher(), 57160814Ssimon const key_equal& eql = key_equal(), 58160814Ssimon const allocator_type& a = allocator_type()); 59160814Ssimon explicit unordered_set(const allocator_type&); 60160814Ssimon unordered_set(const unordered_set&); 61160814Ssimon unordered_set(const unordered_set&, const Allocator&); 62160814Ssimon unordered_set(unordered_set&&) 63160814Ssimon noexcept( 64160814Ssimon is_nothrow_move_constructible<hasher>::value && 65160814Ssimon is_nothrow_move_constructible<key_equal>::value && 66160814Ssimon is_nothrow_move_constructible<allocator_type>::value); 67160814Ssimon unordered_set(unordered_set&&, const Allocator&); 68160814Ssimon unordered_set(initializer_list<value_type>, size_type n = 0, 69160814Ssimon const hasher& hf = hasher(), const key_equal& eql = key_equal(), 70160814Ssimon const allocator_type& a = allocator_type()); 71160814Ssimon unordered_set(size_type n, const allocator_type& a); // C++14 72160814Ssimon unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14 73160814Ssimon template <class InputIterator> 74160814Ssimon unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 75160814Ssimon template <class InputIterator> 76160814Ssimon unordered_set(InputIterator f, InputIterator l, size_type n, 77160814Ssimon const hasher& hf, const allocator_type& a); // C++14 78160814Ssimon unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 79160814Ssimon unordered_set(initializer_list<value_type> il, size_type n, 80160814Ssimon const hasher& hf, const allocator_type& a); // C++14 81160814Ssimon ~unordered_set(); 82160814Ssimon unordered_set& operator=(const unordered_set&); 83160814Ssimon unordered_set& operator=(unordered_set&&) 84160814Ssimon noexcept( 85160814Ssimon allocator_type::propagate_on_container_move_assignment::value && 86160814Ssimon is_nothrow_move_assignable<allocator_type>::value && 87160814Ssimon is_nothrow_move_assignable<hasher>::value && 88160814Ssimon is_nothrow_move_assignable<key_equal>::value); 89160814Ssimon unordered_set& operator=(initializer_list<value_type>); 90160814Ssimon 91160814Ssimon allocator_type get_allocator() const noexcept; 92160814Ssimon 93160814Ssimon bool empty() const noexcept; 94160814Ssimon size_type size() const noexcept; 95160814Ssimon size_type max_size() const noexcept; 96160814Ssimon 97194206Ssimon iterator begin() noexcept; 98160814Ssimon iterator end() noexcept; 99160814Ssimon const_iterator begin() const noexcept; 100194206Ssimon const_iterator end() const noexcept; 101194206Ssimon const_iterator cbegin() const noexcept; 102160814Ssimon const_iterator cend() const noexcept; 103160814Ssimon 104194206Ssimon template <class... Args> 105194206Ssimon pair<iterator, bool> emplace(Args&&... args); 106160814Ssimon template <class... Args> 107160814Ssimon iterator emplace_hint(const_iterator position, Args&&... args); 108160814Ssimon pair<iterator, bool> insert(const value_type& obj); 109160814Ssimon pair<iterator, bool> insert(value_type&& obj); 110194206Ssimon iterator insert(const_iterator hint, const value_type& obj); 111194206Ssimon iterator insert(const_iterator hint, value_type&& obj); 112160814Ssimon template <class InputIterator> 113160814Ssimon void insert(InputIterator first, InputIterator last); 114160814Ssimon void insert(initializer_list<value_type>); 115160814Ssimon 116160814Ssimon iterator erase(const_iterator position); 117160814Ssimon size_type erase(const key_type& k); 118160814Ssimon iterator erase(const_iterator first, const_iterator last); 119160814Ssimon void clear() noexcept; 120194206Ssimon 121194206Ssimon void swap(unordered_set&) 122194206Ssimon noexcept( 123160814Ssimon (!allocator_type::propagate_on_container_swap::value || 124160814Ssimon __is_nothrow_swappable<allocator_type>::value) && 125160814Ssimon __is_nothrow_swappable<hasher>::value && 126160814Ssimon __is_nothrow_swappable<key_equal>::value); 127194206Ssimon 128160814Ssimon hasher hash_function() const; 129160814Ssimon key_equal key_eq() const; 130160814Ssimon 131160814Ssimon iterator find(const key_type& k); 132160814Ssimon const_iterator find(const key_type& k) const; 133160814Ssimon size_type count(const key_type& k) const; 134160814Ssimon pair<iterator, iterator> equal_range(const key_type& k); 135160814Ssimon pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 136160814Ssimon 137160814Ssimon size_type bucket_count() const noexcept; 138160814Ssimon size_type max_bucket_count() const noexcept; 139160814Ssimon 140160814Ssimon size_type bucket_size(size_type n) const; 141160814Ssimon size_type bucket(const key_type& k) const; 142160814Ssimon 143160814Ssimon local_iterator begin(size_type n); 144160814Ssimon local_iterator end(size_type n); 145160814Ssimon const_local_iterator begin(size_type n) const; 146160814Ssimon const_local_iterator end(size_type n) const; 147160814Ssimon const_local_iterator cbegin(size_type n) const; 148160814Ssimon const_local_iterator cend(size_type n) const; 149160814Ssimon 150160814Ssimon float load_factor() const noexcept; 151160814Ssimon float max_load_factor() const noexcept; 152160814Ssimon void max_load_factor(float z); 153160814Ssimon void rehash(size_type n); 154160814Ssimon void reserve(size_type n); 155160814Ssimon}; 156160814Ssimon 157160814Ssimontemplate <class Value, class Hash, class Pred, class Alloc> 158160814Ssimon void swap(unordered_set<Value, Hash, Pred, Alloc>& x, 159160814Ssimon unordered_set<Value, Hash, Pred, Alloc>& y) 160160814Ssimon noexcept(noexcept(x.swap(y))); 161194206Ssimon 162160814Ssimontemplate <class Value, class Hash, class Pred, class Alloc> 163160814Ssimon bool 164194206Ssimon operator==(const unordered_set<Value, Hash, Pred, Alloc>& x, 165160814Ssimon const unordered_set<Value, Hash, Pred, Alloc>& y); 166160814Ssimon 167160814Ssimontemplate <class Value, class Hash, class Pred, class Alloc> 168160814Ssimon bool 169160814Ssimon operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x, 170160814Ssimon const unordered_set<Value, Hash, Pred, Alloc>& y); 171160814Ssimon 172160814Ssimontemplate <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 173194206Ssimon class Alloc = allocator<Value>> 174160814Ssimonclass unordered_multiset 175194206Ssimon{ 176194206Ssimonpublic: 177194206Ssimon // types 178194206Ssimon typedef Value key_type; 179194206Ssimon typedef key_type value_type; 180160814Ssimon typedef Hash hasher; 181160814Ssimon typedef Pred key_equal; 182160814Ssimon typedef Alloc allocator_type; 183160814Ssimon typedef value_type& reference; 184160814Ssimon typedef const value_type& const_reference; 185160814Ssimon typedef typename allocator_traits<allocator_type>::pointer pointer; 186160814Ssimon typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 187160814Ssimon typedef typename allocator_traits<allocator_type>::size_type size_type; 188160814Ssimon typedef typename allocator_traits<allocator_type>::difference_type difference_type; 189160814Ssimon 190160814Ssimon typedef /unspecified/ iterator; 191160814Ssimon typedef /unspecified/ const_iterator; 192160814Ssimon typedef /unspecified/ local_iterator; 193160814Ssimon typedef /unspecified/ const_local_iterator; 194160814Ssimon 195160814Ssimon unordered_multiset() 196160814Ssimon noexcept( 197160814Ssimon is_nothrow_default_constructible<hasher>::value && 198160814Ssimon is_nothrow_default_constructible<key_equal>::value && 199160814Ssimon is_nothrow_default_constructible<allocator_type>::value); 200160814Ssimon explicit unordered_multiset(size_type n, const hasher& hf = hasher(), 201160814Ssimon const key_equal& eql = key_equal(), 202160814Ssimon const allocator_type& a = allocator_type()); 203160814Ssimon template <class InputIterator> 204160814Ssimon unordered_multiset(InputIterator f, InputIterator l, 205160814Ssimon size_type n = 0, const hasher& hf = hasher(), 206160814Ssimon const key_equal& eql = key_equal(), 207160814Ssimon const allocator_type& a = allocator_type()); 208160814Ssimon explicit unordered_multiset(const allocator_type&); 209160814Ssimon unordered_multiset(const unordered_multiset&); 210160814Ssimon unordered_multiset(const unordered_multiset&, const Allocator&); 211160814Ssimon unordered_multiset(unordered_multiset&&) 212160814Ssimon noexcept( 213194206Ssimon is_nothrow_move_constructible<hasher>::value && 214160814Ssimon is_nothrow_move_constructible<key_equal>::value && 215160814Ssimon is_nothrow_move_constructible<allocator_type>::value); 216160814Ssimon unordered_multiset(unordered_multiset&&, const Allocator&); 217160814Ssimon unordered_multiset(initializer_list<value_type>, size_type n = /see below/, 218160814Ssimon const hasher& hf = hasher(), const key_equal& eql = key_equal(), 219194206Ssimon const allocator_type& a = allocator_type()); 220160814Ssimon unordered_multiset(size_type n, const allocator_type& a); // C++14 221160814Ssimon unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14 222160814Ssimon template <class InputIterator> 223160814Ssimon unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 224160814Ssimon template <class InputIterator> 225160814Ssimon unordered_multiset(InputIterator f, InputIterator l, size_type n, 226194206Ssimon const hasher& hf, const allocator_type& a); // C++14 227160814Ssimon unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 228160814Ssimon unordered_multiset(initializer_list<value_type> il, size_type n, 229160814Ssimon const hasher& hf, const allocator_type& a); // C++14 230160814Ssimon ~unordered_multiset(); 231160814Ssimon unordered_multiset& operator=(const unordered_multiset&); 232160814Ssimon unordered_multiset& operator=(unordered_multiset&&) 233160814Ssimon noexcept( 234160814Ssimon allocator_type::propagate_on_container_move_assignment::value && 235160814Ssimon is_nothrow_move_assignable<allocator_type>::value && 236160814Ssimon is_nothrow_move_assignable<hasher>::value && 237160814Ssimon is_nothrow_move_assignable<key_equal>::value); 238160814Ssimon unordered_multiset& operator=(initializer_list<value_type>); 239160814Ssimon 240160814Ssimon allocator_type get_allocator() const noexcept; 241160814Ssimon 242160814Ssimon bool empty() const noexcept; 243160814Ssimon size_type size() const noexcept; 244160814Ssimon size_type max_size() const noexcept; 245160814Ssimon 246160814Ssimon iterator begin() noexcept; 247160814Ssimon iterator end() noexcept; 248160814Ssimon const_iterator begin() const noexcept; 249160814Ssimon const_iterator end() const noexcept; 250160814Ssimon const_iterator cbegin() const noexcept; 251160814Ssimon const_iterator cend() const noexcept; 252160814Ssimon 253160814Ssimon template <class... Args> 254160814Ssimon iterator emplace(Args&&... args); 255160814Ssimon template <class... Args> 256160814Ssimon iterator emplace_hint(const_iterator position, Args&&... args); 257160814Ssimon iterator insert(const value_type& obj); 258160814Ssimon iterator insert(value_type&& obj); 259160814Ssimon iterator insert(const_iterator hint, const value_type& obj); 260160814Ssimon iterator insert(const_iterator hint, value_type&& obj); 261160814Ssimon template <class InputIterator> 262160814Ssimon void insert(InputIterator first, InputIterator last); 263160814Ssimon void insert(initializer_list<value_type>); 264160814Ssimon 265160814Ssimon iterator erase(const_iterator position); 266160814Ssimon size_type erase(const key_type& k); 267160814Ssimon iterator erase(const_iterator first, const_iterator last); 268160814Ssimon void clear() noexcept; 269160814Ssimon 270160814Ssimon void swap(unordered_multiset&) 271160814Ssimon noexcept( 272160814Ssimon (!allocator_type::propagate_on_container_swap::value || 273160814Ssimon __is_nothrow_swappable<allocator_type>::value) && 274160814Ssimon __is_nothrow_swappable<hasher>::value && 275160814Ssimon __is_nothrow_swappable<key_equal>::value); 276160814Ssimon 277160814Ssimon hasher hash_function() const; 278160814Ssimon key_equal key_eq() const; 279160814Ssimon 280160814Ssimon iterator find(const key_type& k); 281160814Ssimon const_iterator find(const key_type& k) const; 282160814Ssimon size_type count(const key_type& k) const; 283160814Ssimon pair<iterator, iterator> equal_range(const key_type& k); 284160814Ssimon pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 285160814Ssimon 286160814Ssimon size_type bucket_count() const noexcept; 287160814Ssimon size_type max_bucket_count() const noexcept; 288160814Ssimon 289160814Ssimon size_type bucket_size(size_type n) const; 290160814Ssimon size_type bucket(const key_type& k) const; 291160814Ssimon 292160814Ssimon local_iterator begin(size_type n); 293 local_iterator end(size_type n); 294 const_local_iterator begin(size_type n) const; 295 const_local_iterator end(size_type n) const; 296 const_local_iterator cbegin(size_type n) const; 297 const_local_iterator cend(size_type n) const; 298 299 float load_factor() const noexcept; 300 float max_load_factor() const noexcept; 301 void max_load_factor(float z); 302 void rehash(size_type n); 303 void reserve(size_type n); 304}; 305 306template <class Value, class Hash, class Pred, class Alloc> 307 void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x, 308 unordered_multiset<Value, Hash, Pred, Alloc>& y) 309 noexcept(noexcept(x.swap(y))); 310 311template <class Value, class Hash, class Pred, class Alloc> 312 bool 313 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 314 const unordered_multiset<Value, Hash, Pred, Alloc>& y); 315 316template <class Value, class Hash, class Pred, class Alloc> 317 bool 318 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 319 const unordered_multiset<Value, Hash, Pred, Alloc>& y); 320} // std 321 322*/ 323 324#include <__config> 325#include <__hash_table> 326#include <functional> 327 328#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 329#pragma GCC system_header 330#endif 331 332_LIBCPP_BEGIN_NAMESPACE_STD 333 334template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 335 class _Alloc = allocator<_Value> > 336class _LIBCPP_TYPE_VIS_ONLY unordered_set 337{ 338public: 339 // types 340 typedef _Value key_type; 341 typedef key_type value_type; 342 typedef _Hash hasher; 343 typedef _Pred key_equal; 344 typedef _Alloc allocator_type; 345 typedef value_type& reference; 346 typedef const value_type& const_reference; 347 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 348 "Invalid allocator::value_type"); 349 350private: 351 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 352 353 __table __table_; 354 355public: 356 typedef typename __table::pointer pointer; 357 typedef typename __table::const_pointer const_pointer; 358 typedef typename __table::size_type size_type; 359 typedef typename __table::difference_type difference_type; 360 361 typedef typename __table::const_iterator iterator; 362 typedef typename __table::const_iterator const_iterator; 363 typedef typename __table::const_local_iterator local_iterator; 364 typedef typename __table::const_local_iterator const_local_iterator; 365 366 _LIBCPP_INLINE_VISIBILITY 367 unordered_set() 368 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 369 { 370#if _LIBCPP_DEBUG_LEVEL >= 2 371 __get_db()->__insert_c(this); 372#endif 373 } 374 explicit unordered_set(size_type __n, const hasher& __hf = hasher(), 375 const key_equal& __eql = key_equal()); 376#if _LIBCPP_STD_VER > 11 377 inline _LIBCPP_INLINE_VISIBILITY 378 unordered_set(size_type __n, const allocator_type& __a) 379 : unordered_set(__n, hasher(), key_equal(), __a) {} 380 inline _LIBCPP_INLINE_VISIBILITY 381 unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a) 382 : unordered_set(__n, __hf, key_equal(), __a) {} 383#endif 384 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, 385 const allocator_type& __a); 386 template <class _InputIterator> 387 unordered_set(_InputIterator __first, _InputIterator __last); 388 template <class _InputIterator> 389 unordered_set(_InputIterator __first, _InputIterator __last, 390 size_type __n, const hasher& __hf = hasher(), 391 const key_equal& __eql = key_equal()); 392 template <class _InputIterator> 393 unordered_set(_InputIterator __first, _InputIterator __last, 394 size_type __n, const hasher& __hf, const key_equal& __eql, 395 const allocator_type& __a); 396#if _LIBCPP_STD_VER > 11 397 template <class _InputIterator> 398 inline _LIBCPP_INLINE_VISIBILITY 399 unordered_set(_InputIterator __first, _InputIterator __last, 400 size_type __n, const allocator_type& __a) 401 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} 402 template <class _InputIterator> 403 unordered_set(_InputIterator __first, _InputIterator __last, 404 size_type __n, const hasher& __hf, const allocator_type& __a) 405 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} 406#endif 407 explicit unordered_set(const allocator_type& __a); 408 unordered_set(const unordered_set& __u); 409 unordered_set(const unordered_set& __u, const allocator_type& __a); 410#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 411 unordered_set(unordered_set&& __u) 412 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 413 unordered_set(unordered_set&& __u, const allocator_type& __a); 414#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 415#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 416 unordered_set(initializer_list<value_type> __il); 417 unordered_set(initializer_list<value_type> __il, size_type __n, 418 const hasher& __hf = hasher(), 419 const key_equal& __eql = key_equal()); 420 unordered_set(initializer_list<value_type> __il, size_type __n, 421 const hasher& __hf, const key_equal& __eql, 422 const allocator_type& __a); 423#if _LIBCPP_STD_VER > 11 424 inline _LIBCPP_INLINE_VISIBILITY 425 unordered_set(initializer_list<value_type> __il, size_type __n, 426 const allocator_type& __a) 427 : unordered_set(__il, __n, hasher(), key_equal(), __a) {} 428 inline _LIBCPP_INLINE_VISIBILITY 429 unordered_set(initializer_list<value_type> __il, size_type __n, 430 const hasher& __hf, const allocator_type& __a) 431 : unordered_set(__il, __n, __hf, key_equal(), __a) {} 432#endif 433#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 434 // ~unordered_set() = default; 435 _LIBCPP_INLINE_VISIBILITY 436 unordered_set& operator=(const unordered_set& __u) 437 { 438 __table_ = __u.__table_; 439 return *this; 440 } 441#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 442 unordered_set& operator=(unordered_set&& __u) 443 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 444#endif 445#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 446 unordered_set& operator=(initializer_list<value_type> __il); 447#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 448 449 _LIBCPP_INLINE_VISIBILITY 450 allocator_type get_allocator() const _NOEXCEPT 451 {return allocator_type(__table_.__node_alloc());} 452 453 _LIBCPP_INLINE_VISIBILITY 454 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 455 _LIBCPP_INLINE_VISIBILITY 456 size_type size() const _NOEXCEPT {return __table_.size();} 457 _LIBCPP_INLINE_VISIBILITY 458 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 459 460 _LIBCPP_INLINE_VISIBILITY 461 iterator begin() _NOEXCEPT {return __table_.begin();} 462 _LIBCPP_INLINE_VISIBILITY 463 iterator end() _NOEXCEPT {return __table_.end();} 464 _LIBCPP_INLINE_VISIBILITY 465 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 466 _LIBCPP_INLINE_VISIBILITY 467 const_iterator end() const _NOEXCEPT {return __table_.end();} 468 _LIBCPP_INLINE_VISIBILITY 469 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 470 _LIBCPP_INLINE_VISIBILITY 471 const_iterator cend() const _NOEXCEPT {return __table_.end();} 472 473#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 474 template <class... _Args> 475 _LIBCPP_INLINE_VISIBILITY 476 pair<iterator, bool> emplace(_Args&&... __args) 477 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 478 template <class... _Args> 479 _LIBCPP_INLINE_VISIBILITY 480#if _LIBCPP_DEBUG_LEVEL >= 2 481 iterator emplace_hint(const_iterator __p, _Args&&... __args) 482 { 483 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 484 "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not" 485 " referring to this unordered_set"); 486 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 487 } 488#else 489 iterator emplace_hint(const_iterator, _Args&&... __args) 490 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;} 491#endif 492#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 493 _LIBCPP_INLINE_VISIBILITY 494 pair<iterator, bool> insert(const value_type& __x) 495 {return __table_.__insert_unique(__x);} 496#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 497 _LIBCPP_INLINE_VISIBILITY 498 pair<iterator, bool> insert(value_type&& __x) 499 {return __table_.__insert_unique(_VSTD::move(__x));} 500#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 501 _LIBCPP_INLINE_VISIBILITY 502#if _LIBCPP_DEBUG_LEVEL >= 2 503 iterator insert(const_iterator __p, const value_type& __x) 504 { 505 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 506 "unordered_set::insert(const_iterator, const value_type&) called with an iterator not" 507 " referring to this unordered_set"); 508 return insert(__x).first; 509 } 510#else 511 iterator insert(const_iterator, const value_type& __x) 512 {return insert(__x).first;} 513#endif 514#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 515 _LIBCPP_INLINE_VISIBILITY 516#if _LIBCPP_DEBUG_LEVEL >= 2 517 iterator insert(const_iterator __p, value_type&& __x) 518 { 519 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 520 "unordered_set::insert(const_iterator, value_type&&) called with an iterator not" 521 " referring to this unordered_set"); 522 return insert(_VSTD::move(__x)).first; 523 } 524#else 525 iterator insert(const_iterator, value_type&& __x) 526 {return insert(_VSTD::move(__x)).first;} 527#endif 528#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 529 template <class _InputIterator> 530 void insert(_InputIterator __first, _InputIterator __last); 531#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 532 _LIBCPP_INLINE_VISIBILITY 533 void insert(initializer_list<value_type> __il) 534 {insert(__il.begin(), __il.end());} 535#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 536 537 _LIBCPP_INLINE_VISIBILITY 538 iterator erase(const_iterator __p) {return __table_.erase(__p);} 539 _LIBCPP_INLINE_VISIBILITY 540 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 541 _LIBCPP_INLINE_VISIBILITY 542 iterator erase(const_iterator __first, const_iterator __last) 543 {return __table_.erase(__first, __last);} 544 _LIBCPP_INLINE_VISIBILITY 545 void clear() _NOEXCEPT {__table_.clear();} 546 547 _LIBCPP_INLINE_VISIBILITY 548 void swap(unordered_set& __u) 549 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 550 {__table_.swap(__u.__table_);} 551 552 _LIBCPP_INLINE_VISIBILITY 553 hasher hash_function() const {return __table_.hash_function();} 554 _LIBCPP_INLINE_VISIBILITY 555 key_equal key_eq() const {return __table_.key_eq();} 556 557 _LIBCPP_INLINE_VISIBILITY 558 iterator find(const key_type& __k) {return __table_.find(__k);} 559 _LIBCPP_INLINE_VISIBILITY 560 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 561 _LIBCPP_INLINE_VISIBILITY 562 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 563 _LIBCPP_INLINE_VISIBILITY 564 pair<iterator, iterator> equal_range(const key_type& __k) 565 {return __table_.__equal_range_unique(__k);} 566 _LIBCPP_INLINE_VISIBILITY 567 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 568 {return __table_.__equal_range_unique(__k);} 569 570 _LIBCPP_INLINE_VISIBILITY 571 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 572 _LIBCPP_INLINE_VISIBILITY 573 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 574 575 _LIBCPP_INLINE_VISIBILITY 576 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 577 _LIBCPP_INLINE_VISIBILITY 578 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 579 580 _LIBCPP_INLINE_VISIBILITY 581 local_iterator begin(size_type __n) {return __table_.begin(__n);} 582 _LIBCPP_INLINE_VISIBILITY 583 local_iterator end(size_type __n) {return __table_.end(__n);} 584 _LIBCPP_INLINE_VISIBILITY 585 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 586 _LIBCPP_INLINE_VISIBILITY 587 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 588 _LIBCPP_INLINE_VISIBILITY 589 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 590 _LIBCPP_INLINE_VISIBILITY 591 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 592 593 _LIBCPP_INLINE_VISIBILITY 594 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 595 _LIBCPP_INLINE_VISIBILITY 596 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 597 _LIBCPP_INLINE_VISIBILITY 598 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 599 _LIBCPP_INLINE_VISIBILITY 600 void rehash(size_type __n) {__table_.rehash(__n);} 601 _LIBCPP_INLINE_VISIBILITY 602 void reserve(size_type __n) {__table_.reserve(__n);} 603 604#if _LIBCPP_DEBUG_LEVEL >= 2 605 606 bool __dereferenceable(const const_iterator* __i) const 607 {return __table_.__dereferenceable(__i);} 608 bool __decrementable(const const_iterator* __i) const 609 {return __table_.__decrementable(__i);} 610 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 611 {return __table_.__addable(__i, __n);} 612 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 613 {return __table_.__addable(__i, __n);} 614 615#endif // _LIBCPP_DEBUG_LEVEL >= 2 616 617}; 618 619template <class _Value, class _Hash, class _Pred, class _Alloc> 620unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 621 const hasher& __hf, const key_equal& __eql) 622 : __table_(__hf, __eql) 623{ 624#if _LIBCPP_DEBUG_LEVEL >= 2 625 __get_db()->__insert_c(this); 626#endif 627 __table_.rehash(__n); 628} 629 630template <class _Value, class _Hash, class _Pred, class _Alloc> 631unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 632 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 633 : __table_(__hf, __eql, __a) 634{ 635#if _LIBCPP_DEBUG_LEVEL >= 2 636 __get_db()->__insert_c(this); 637#endif 638 __table_.rehash(__n); 639} 640 641template <class _Value, class _Hash, class _Pred, class _Alloc> 642template <class _InputIterator> 643unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 644 _InputIterator __first, _InputIterator __last) 645{ 646#if _LIBCPP_DEBUG_LEVEL >= 2 647 __get_db()->__insert_c(this); 648#endif 649 insert(__first, __last); 650} 651 652template <class _Value, class _Hash, class _Pred, class _Alloc> 653template <class _InputIterator> 654unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 655 _InputIterator __first, _InputIterator __last, size_type __n, 656 const hasher& __hf, const key_equal& __eql) 657 : __table_(__hf, __eql) 658{ 659#if _LIBCPP_DEBUG_LEVEL >= 2 660 __get_db()->__insert_c(this); 661#endif 662 __table_.rehash(__n); 663 insert(__first, __last); 664} 665 666template <class _Value, class _Hash, class _Pred, class _Alloc> 667template <class _InputIterator> 668unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 669 _InputIterator __first, _InputIterator __last, size_type __n, 670 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 671 : __table_(__hf, __eql, __a) 672{ 673#if _LIBCPP_DEBUG_LEVEL >= 2 674 __get_db()->__insert_c(this); 675#endif 676 __table_.rehash(__n); 677 insert(__first, __last); 678} 679 680template <class _Value, class _Hash, class _Pred, class _Alloc> 681inline _LIBCPP_INLINE_VISIBILITY 682unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 683 const allocator_type& __a) 684 : __table_(__a) 685{ 686#if _LIBCPP_DEBUG_LEVEL >= 2 687 __get_db()->__insert_c(this); 688#endif 689} 690 691template <class _Value, class _Hash, class _Pred, class _Alloc> 692unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 693 const unordered_set& __u) 694 : __table_(__u.__table_) 695{ 696#if _LIBCPP_DEBUG_LEVEL >= 2 697 __get_db()->__insert_c(this); 698#endif 699 __table_.rehash(__u.bucket_count()); 700 insert(__u.begin(), __u.end()); 701} 702 703template <class _Value, class _Hash, class _Pred, class _Alloc> 704unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 705 const unordered_set& __u, const allocator_type& __a) 706 : __table_(__u.__table_, __a) 707{ 708#if _LIBCPP_DEBUG_LEVEL >= 2 709 __get_db()->__insert_c(this); 710#endif 711 __table_.rehash(__u.bucket_count()); 712 insert(__u.begin(), __u.end()); 713} 714 715#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 716 717template <class _Value, class _Hash, class _Pred, class _Alloc> 718inline _LIBCPP_INLINE_VISIBILITY 719unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 720 unordered_set&& __u) 721 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 722 : __table_(_VSTD::move(__u.__table_)) 723{ 724#if _LIBCPP_DEBUG_LEVEL >= 2 725 __get_db()->__insert_c(this); 726 __get_db()->swap(this, &__u); 727#endif 728} 729 730template <class _Value, class _Hash, class _Pred, class _Alloc> 731unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 732 unordered_set&& __u, const allocator_type& __a) 733 : __table_(_VSTD::move(__u.__table_), __a) 734{ 735#if _LIBCPP_DEBUG_LEVEL >= 2 736 __get_db()->__insert_c(this); 737#endif 738 if (__a != __u.get_allocator()) 739 { 740 iterator __i = __u.begin(); 741 while (__u.size() != 0) 742 __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 743 } 744#if _LIBCPP_DEBUG_LEVEL >= 2 745 else 746 __get_db()->swap(this, &__u); 747#endif 748} 749 750#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 751 752#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 753 754template <class _Value, class _Hash, class _Pred, class _Alloc> 755unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 756 initializer_list<value_type> __il) 757{ 758#if _LIBCPP_DEBUG_LEVEL >= 2 759 __get_db()->__insert_c(this); 760#endif 761 insert(__il.begin(), __il.end()); 762} 763 764template <class _Value, class _Hash, class _Pred, class _Alloc> 765unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 766 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 767 const key_equal& __eql) 768 : __table_(__hf, __eql) 769{ 770#if _LIBCPP_DEBUG_LEVEL >= 2 771 __get_db()->__insert_c(this); 772#endif 773 __table_.rehash(__n); 774 insert(__il.begin(), __il.end()); 775} 776 777template <class _Value, class _Hash, class _Pred, class _Alloc> 778unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 779 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 780 const key_equal& __eql, const allocator_type& __a) 781 : __table_(__hf, __eql, __a) 782{ 783#if _LIBCPP_DEBUG_LEVEL >= 2 784 __get_db()->__insert_c(this); 785#endif 786 __table_.rehash(__n); 787 insert(__il.begin(), __il.end()); 788} 789 790#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 791 792#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 793 794template <class _Value, class _Hash, class _Pred, class _Alloc> 795inline _LIBCPP_INLINE_VISIBILITY 796unordered_set<_Value, _Hash, _Pred, _Alloc>& 797unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 798 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 799{ 800 __table_ = _VSTD::move(__u.__table_); 801 return *this; 802} 803 804#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 805 806#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 807 808template <class _Value, class _Hash, class _Pred, class _Alloc> 809inline _LIBCPP_INLINE_VISIBILITY 810unordered_set<_Value, _Hash, _Pred, _Alloc>& 811unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=( 812 initializer_list<value_type> __il) 813{ 814 __table_.__assign_unique(__il.begin(), __il.end()); 815 return *this; 816} 817 818#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 819 820template <class _Value, class _Hash, class _Pred, class _Alloc> 821template <class _InputIterator> 822inline _LIBCPP_INLINE_VISIBILITY 823void 824unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 825 _InputIterator __last) 826{ 827 for (; __first != __last; ++__first) 828 __table_.__insert_unique(*__first); 829} 830 831template <class _Value, class _Hash, class _Pred, class _Alloc> 832inline _LIBCPP_INLINE_VISIBILITY 833void 834swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 835 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 836 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 837{ 838 __x.swap(__y); 839} 840 841template <class _Value, class _Hash, class _Pred, class _Alloc> 842bool 843operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 844 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 845{ 846 if (__x.size() != __y.size()) 847 return false; 848 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 849 const_iterator; 850 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 851 __i != __ex; ++__i) 852 { 853 const_iterator __j = __y.find(*__i); 854 if (__j == __ey || !(*__i == *__j)) 855 return false; 856 } 857 return true; 858} 859 860template <class _Value, class _Hash, class _Pred, class _Alloc> 861inline _LIBCPP_INLINE_VISIBILITY 862bool 863operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 864 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 865{ 866 return !(__x == __y); 867} 868 869template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 870 class _Alloc = allocator<_Value> > 871class _LIBCPP_TYPE_VIS_ONLY unordered_multiset 872{ 873public: 874 // types 875 typedef _Value key_type; 876 typedef key_type value_type; 877 typedef _Hash hasher; 878 typedef _Pred key_equal; 879 typedef _Alloc allocator_type; 880 typedef value_type& reference; 881 typedef const value_type& const_reference; 882 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 883 "Invalid allocator::value_type"); 884 885private: 886 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 887 888 __table __table_; 889 890public: 891 typedef typename __table::pointer pointer; 892 typedef typename __table::const_pointer const_pointer; 893 typedef typename __table::size_type size_type; 894 typedef typename __table::difference_type difference_type; 895 896 typedef typename __table::const_iterator iterator; 897 typedef typename __table::const_iterator const_iterator; 898 typedef typename __table::const_local_iterator local_iterator; 899 typedef typename __table::const_local_iterator const_local_iterator; 900 901 _LIBCPP_INLINE_VISIBILITY 902 unordered_multiset() 903 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 904 { 905#if _LIBCPP_DEBUG_LEVEL >= 2 906 __get_db()->__insert_c(this); 907#endif 908 } 909 explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(), 910 const key_equal& __eql = key_equal()); 911 unordered_multiset(size_type __n, const hasher& __hf, 912 const key_equal& __eql, const allocator_type& __a); 913#if _LIBCPP_STD_VER > 11 914 inline _LIBCPP_INLINE_VISIBILITY 915 unordered_multiset(size_type __n, const allocator_type& __a) 916 : unordered_multiset(__n, hasher(), key_equal(), __a) {} 917 inline _LIBCPP_INLINE_VISIBILITY 918 unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) 919 : unordered_multiset(__n, __hf, key_equal(), __a) {} 920#endif 921 template <class _InputIterator> 922 unordered_multiset(_InputIterator __first, _InputIterator __last); 923 template <class _InputIterator> 924 unordered_multiset(_InputIterator __first, _InputIterator __last, 925 size_type __n, const hasher& __hf = hasher(), 926 const key_equal& __eql = key_equal()); 927 template <class _InputIterator> 928 unordered_multiset(_InputIterator __first, _InputIterator __last, 929 size_type __n , const hasher& __hf, 930 const key_equal& __eql, const allocator_type& __a); 931#if _LIBCPP_STD_VER > 11 932 template <class _InputIterator> 933 inline _LIBCPP_INLINE_VISIBILITY 934 unordered_multiset(_InputIterator __first, _InputIterator __last, 935 size_type __n, const allocator_type& __a) 936 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} 937 template <class _InputIterator> 938 inline _LIBCPP_INLINE_VISIBILITY 939 unordered_multiset(_InputIterator __first, _InputIterator __last, 940 size_type __n, const hasher& __hf, const allocator_type& __a) 941 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} 942#endif 943 explicit unordered_multiset(const allocator_type& __a); 944 unordered_multiset(const unordered_multiset& __u); 945 unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 946#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 947 unordered_multiset(unordered_multiset&& __u) 948 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 949 unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 950#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 951#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 952 unordered_multiset(initializer_list<value_type> __il); 953 unordered_multiset(initializer_list<value_type> __il, size_type __n, 954 const hasher& __hf = hasher(), 955 const key_equal& __eql = key_equal()); 956 unordered_multiset(initializer_list<value_type> __il, size_type __n, 957 const hasher& __hf, const key_equal& __eql, 958 const allocator_type& __a); 959#if _LIBCPP_STD_VER > 11 960 inline _LIBCPP_INLINE_VISIBILITY 961 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 962 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} 963 inline _LIBCPP_INLINE_VISIBILITY 964 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 965 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} 966#endif 967#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 968 // ~unordered_multiset() = default; 969 _LIBCPP_INLINE_VISIBILITY 970 unordered_multiset& operator=(const unordered_multiset& __u) 971 { 972 __table_ = __u.__table_; 973 return *this; 974 } 975#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 976 unordered_multiset& operator=(unordered_multiset&& __u) 977 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 978#endif 979#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 980 unordered_multiset& operator=(initializer_list<value_type> __il); 981#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 982 983 _LIBCPP_INLINE_VISIBILITY 984 allocator_type get_allocator() const _NOEXCEPT 985 {return allocator_type(__table_.__node_alloc());} 986 987 _LIBCPP_INLINE_VISIBILITY 988 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 989 _LIBCPP_INLINE_VISIBILITY 990 size_type size() const _NOEXCEPT {return __table_.size();} 991 _LIBCPP_INLINE_VISIBILITY 992 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 993 994 _LIBCPP_INLINE_VISIBILITY 995 iterator begin() _NOEXCEPT {return __table_.begin();} 996 _LIBCPP_INLINE_VISIBILITY 997 iterator end() _NOEXCEPT {return __table_.end();} 998 _LIBCPP_INLINE_VISIBILITY 999 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1000 _LIBCPP_INLINE_VISIBILITY 1001 const_iterator end() const _NOEXCEPT {return __table_.end();} 1002 _LIBCPP_INLINE_VISIBILITY 1003 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1004 _LIBCPP_INLINE_VISIBILITY 1005 const_iterator cend() const _NOEXCEPT {return __table_.end();} 1006 1007#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1008 template <class... _Args> 1009 _LIBCPP_INLINE_VISIBILITY 1010 iterator emplace(_Args&&... __args) 1011 {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 1012 template <class... _Args> 1013 _LIBCPP_INLINE_VISIBILITY 1014 iterator emplace_hint(const_iterator __p, _Args&&... __args) 1015 {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1016#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1017 _LIBCPP_INLINE_VISIBILITY 1018 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1019#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1020 _LIBCPP_INLINE_VISIBILITY 1021 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} 1022#endif 1023 _LIBCPP_INLINE_VISIBILITY 1024 iterator insert(const_iterator __p, const value_type& __x) 1025 {return __table_.__insert_multi(__p, __x);} 1026#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1027 _LIBCPP_INLINE_VISIBILITY 1028 iterator insert(const_iterator __p, value_type&& __x) 1029 {return __table_.__insert_multi(__p, _VSTD::move(__x));} 1030#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1031 template <class _InputIterator> 1032 void insert(_InputIterator __first, _InputIterator __last); 1033#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1034 _LIBCPP_INLINE_VISIBILITY 1035 void insert(initializer_list<value_type> __il) 1036 {insert(__il.begin(), __il.end());} 1037#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1038 1039 _LIBCPP_INLINE_VISIBILITY 1040 iterator erase(const_iterator __p) {return __table_.erase(__p);} 1041 _LIBCPP_INLINE_VISIBILITY 1042 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1043 _LIBCPP_INLINE_VISIBILITY 1044 iterator erase(const_iterator __first, const_iterator __last) 1045 {return __table_.erase(__first, __last);} 1046 _LIBCPP_INLINE_VISIBILITY 1047 void clear() _NOEXCEPT {__table_.clear();} 1048 1049 _LIBCPP_INLINE_VISIBILITY 1050 void swap(unordered_multiset& __u) 1051 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1052 {__table_.swap(__u.__table_);} 1053 1054 _LIBCPP_INLINE_VISIBILITY 1055 hasher hash_function() const {return __table_.hash_function();} 1056 _LIBCPP_INLINE_VISIBILITY 1057 key_equal key_eq() const {return __table_.key_eq();} 1058 1059 _LIBCPP_INLINE_VISIBILITY 1060 iterator find(const key_type& __k) {return __table_.find(__k);} 1061 _LIBCPP_INLINE_VISIBILITY 1062 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1063 _LIBCPP_INLINE_VISIBILITY 1064 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1065 _LIBCPP_INLINE_VISIBILITY 1066 pair<iterator, iterator> equal_range(const key_type& __k) 1067 {return __table_.__equal_range_multi(__k);} 1068 _LIBCPP_INLINE_VISIBILITY 1069 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1070 {return __table_.__equal_range_multi(__k);} 1071 1072 _LIBCPP_INLINE_VISIBILITY 1073 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1074 _LIBCPP_INLINE_VISIBILITY 1075 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 1076 1077 _LIBCPP_INLINE_VISIBILITY 1078 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 1079 _LIBCPP_INLINE_VISIBILITY 1080 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1081 1082 _LIBCPP_INLINE_VISIBILITY 1083 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1084 _LIBCPP_INLINE_VISIBILITY 1085 local_iterator end(size_type __n) {return __table_.end(__n);} 1086 _LIBCPP_INLINE_VISIBILITY 1087 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1088 _LIBCPP_INLINE_VISIBILITY 1089 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1090 _LIBCPP_INLINE_VISIBILITY 1091 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1092 _LIBCPP_INLINE_VISIBILITY 1093 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1094 1095 _LIBCPP_INLINE_VISIBILITY 1096 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1097 _LIBCPP_INLINE_VISIBILITY 1098 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1099 _LIBCPP_INLINE_VISIBILITY 1100 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1101 _LIBCPP_INLINE_VISIBILITY 1102 void rehash(size_type __n) {__table_.rehash(__n);} 1103 _LIBCPP_INLINE_VISIBILITY 1104 void reserve(size_type __n) {__table_.reserve(__n);} 1105 1106#if _LIBCPP_DEBUG_LEVEL >= 2 1107 1108 bool __dereferenceable(const const_iterator* __i) const 1109 {return __table_.__dereferenceable(__i);} 1110 bool __decrementable(const const_iterator* __i) const 1111 {return __table_.__decrementable(__i);} 1112 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1113 {return __table_.__addable(__i, __n);} 1114 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1115 {return __table_.__addable(__i, __n);} 1116 1117#endif // _LIBCPP_DEBUG_LEVEL >= 2 1118 1119}; 1120 1121template <class _Value, class _Hash, class _Pred, class _Alloc> 1122unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1123 size_type __n, const hasher& __hf, const key_equal& __eql) 1124 : __table_(__hf, __eql) 1125{ 1126#if _LIBCPP_DEBUG_LEVEL >= 2 1127 __get_db()->__insert_c(this); 1128#endif 1129 __table_.rehash(__n); 1130} 1131 1132template <class _Value, class _Hash, class _Pred, class _Alloc> 1133unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1134 size_type __n, const hasher& __hf, const key_equal& __eql, 1135 const allocator_type& __a) 1136 : __table_(__hf, __eql, __a) 1137{ 1138#if _LIBCPP_DEBUG_LEVEL >= 2 1139 __get_db()->__insert_c(this); 1140#endif 1141 __table_.rehash(__n); 1142} 1143 1144template <class _Value, class _Hash, class _Pred, class _Alloc> 1145template <class _InputIterator> 1146unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1147 _InputIterator __first, _InputIterator __last) 1148{ 1149#if _LIBCPP_DEBUG_LEVEL >= 2 1150 __get_db()->__insert_c(this); 1151#endif 1152 insert(__first, __last); 1153} 1154 1155template <class _Value, class _Hash, class _Pred, class _Alloc> 1156template <class _InputIterator> 1157unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1158 _InputIterator __first, _InputIterator __last, size_type __n, 1159 const hasher& __hf, const key_equal& __eql) 1160 : __table_(__hf, __eql) 1161{ 1162#if _LIBCPP_DEBUG_LEVEL >= 2 1163 __get_db()->__insert_c(this); 1164#endif 1165 __table_.rehash(__n); 1166 insert(__first, __last); 1167} 1168 1169template <class _Value, class _Hash, class _Pred, class _Alloc> 1170template <class _InputIterator> 1171unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1172 _InputIterator __first, _InputIterator __last, size_type __n, 1173 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1174 : __table_(__hf, __eql, __a) 1175{ 1176#if _LIBCPP_DEBUG_LEVEL >= 2 1177 __get_db()->__insert_c(this); 1178#endif 1179 __table_.rehash(__n); 1180 insert(__first, __last); 1181} 1182 1183template <class _Value, class _Hash, class _Pred, class _Alloc> 1184inline _LIBCPP_INLINE_VISIBILITY 1185unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1186 const allocator_type& __a) 1187 : __table_(__a) 1188{ 1189#if _LIBCPP_DEBUG_LEVEL >= 2 1190 __get_db()->__insert_c(this); 1191#endif 1192} 1193 1194template <class _Value, class _Hash, class _Pred, class _Alloc> 1195unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1196 const unordered_multiset& __u) 1197 : __table_(__u.__table_) 1198{ 1199#if _LIBCPP_DEBUG_LEVEL >= 2 1200 __get_db()->__insert_c(this); 1201#endif 1202 __table_.rehash(__u.bucket_count()); 1203 insert(__u.begin(), __u.end()); 1204} 1205 1206template <class _Value, class _Hash, class _Pred, class _Alloc> 1207unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1208 const unordered_multiset& __u, const allocator_type& __a) 1209 : __table_(__u.__table_, __a) 1210{ 1211#if _LIBCPP_DEBUG_LEVEL >= 2 1212 __get_db()->__insert_c(this); 1213#endif 1214 __table_.rehash(__u.bucket_count()); 1215 insert(__u.begin(), __u.end()); 1216} 1217 1218#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1219 1220template <class _Value, class _Hash, class _Pred, class _Alloc> 1221inline _LIBCPP_INLINE_VISIBILITY 1222unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1223 unordered_multiset&& __u) 1224 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1225 : __table_(_VSTD::move(__u.__table_)) 1226{ 1227#if _LIBCPP_DEBUG_LEVEL >= 2 1228 __get_db()->__insert_c(this); 1229 __get_db()->swap(this, &__u); 1230#endif 1231} 1232 1233template <class _Value, class _Hash, class _Pred, class _Alloc> 1234unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1235 unordered_multiset&& __u, const allocator_type& __a) 1236 : __table_(_VSTD::move(__u.__table_), __a) 1237{ 1238#if _LIBCPP_DEBUG_LEVEL >= 2 1239 __get_db()->__insert_c(this); 1240#endif 1241 if (__a != __u.get_allocator()) 1242 { 1243 iterator __i = __u.begin(); 1244 while (__u.size() != 0) 1245 __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 1246 } 1247#if _LIBCPP_DEBUG_LEVEL >= 2 1248 else 1249 __get_db()->swap(this, &__u); 1250#endif 1251} 1252 1253#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1254 1255#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1256 1257template <class _Value, class _Hash, class _Pred, class _Alloc> 1258unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1259 initializer_list<value_type> __il) 1260{ 1261#if _LIBCPP_DEBUG_LEVEL >= 2 1262 __get_db()->__insert_c(this); 1263#endif 1264 insert(__il.begin(), __il.end()); 1265} 1266 1267template <class _Value, class _Hash, class _Pred, class _Alloc> 1268unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1269 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1270 const key_equal& __eql) 1271 : __table_(__hf, __eql) 1272{ 1273#if _LIBCPP_DEBUG_LEVEL >= 2 1274 __get_db()->__insert_c(this); 1275#endif 1276 __table_.rehash(__n); 1277 insert(__il.begin(), __il.end()); 1278} 1279 1280template <class _Value, class _Hash, class _Pred, class _Alloc> 1281unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1282 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1283 const key_equal& __eql, const allocator_type& __a) 1284 : __table_(__hf, __eql, __a) 1285{ 1286#if _LIBCPP_DEBUG_LEVEL >= 2 1287 __get_db()->__insert_c(this); 1288#endif 1289 __table_.rehash(__n); 1290 insert(__il.begin(), __il.end()); 1291} 1292 1293#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1294 1295#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1296 1297template <class _Value, class _Hash, class _Pred, class _Alloc> 1298inline _LIBCPP_INLINE_VISIBILITY 1299unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1300unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1301 unordered_multiset&& __u) 1302 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1303{ 1304 __table_ = _VSTD::move(__u.__table_); 1305 return *this; 1306} 1307 1308#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1309 1310#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1311 1312template <class _Value, class _Hash, class _Pred, class _Alloc> 1313inline 1314unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1315unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1316 initializer_list<value_type> __il) 1317{ 1318 __table_.__assign_multi(__il.begin(), __il.end()); 1319 return *this; 1320} 1321 1322#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1323 1324template <class _Value, class _Hash, class _Pred, class _Alloc> 1325template <class _InputIterator> 1326inline _LIBCPP_INLINE_VISIBILITY 1327void 1328unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1329 _InputIterator __last) 1330{ 1331 for (; __first != __last; ++__first) 1332 __table_.__insert_multi(*__first); 1333} 1334 1335template <class _Value, class _Hash, class _Pred, class _Alloc> 1336inline _LIBCPP_INLINE_VISIBILITY 1337void 1338swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1339 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1340 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1341{ 1342 __x.swap(__y); 1343} 1344 1345template <class _Value, class _Hash, class _Pred, class _Alloc> 1346bool 1347operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1348 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1349{ 1350 if (__x.size() != __y.size()) 1351 return false; 1352 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 1353 const_iterator; 1354 typedef pair<const_iterator, const_iterator> _EqRng; 1355 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 1356 { 1357 _EqRng __xeq = __x.equal_range(*__i); 1358 _EqRng __yeq = __y.equal_range(*__i); 1359 if (_VSTD::distance(__xeq.first, __xeq.second) != 1360 _VSTD::distance(__yeq.first, __yeq.second) || 1361 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1362 return false; 1363 __i = __xeq.second; 1364 } 1365 return true; 1366} 1367 1368template <class _Value, class _Hash, class _Pred, class _Alloc> 1369inline _LIBCPP_INLINE_VISIBILITY 1370bool 1371operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1372 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1373{ 1374 return !(__x == __y); 1375} 1376 1377_LIBCPP_END_NAMESPACE_STD 1378 1379#endif // _LIBCPP_UNORDERED_SET 1380