unordered_set revision 278724
1227825Stheraven// -*- C++ -*- 2227825Stheraven//===-------------------------- unordered_set -----------------------------===// 3227825Stheraven// 4227825Stheraven// The LLVM Compiler Infrastructure 5227825Stheraven// 6227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 7227825Stheraven// Source Licenses. See LICENSE.TXT for details. 8227825Stheraven// 9227825Stheraven//===----------------------------------------------------------------------===// 10227825Stheraven 11227825Stheraven#ifndef _LIBCPP_UNORDERED_SET 12227825Stheraven#define _LIBCPP_UNORDERED_SET 13227825Stheraven 14227825Stheraven/* 15227825Stheraven 16227825Stheraven unordered_set synopsis 17227825Stheraven 18227825Stheraven#include <initializer_list> 19227825Stheraven 20227825Stheravennamespace std 21227825Stheraven{ 22227825Stheraven 23227825Stheraventemplate <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 24227825Stheraven class Alloc = allocator<Value>> 25227825Stheravenclass unordered_set 26227825Stheraven{ 27227825Stheravenpublic: 28227825Stheraven // types 29227825Stheraven typedef Value key_type; 30227825Stheraven typedef key_type value_type; 31227825Stheraven typedef Hash hasher; 32227825Stheraven typedef Pred key_equal; 33227825Stheraven typedef Alloc allocator_type; 34227825Stheraven typedef value_type& reference; 35227825Stheraven typedef const value_type& const_reference; 36227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 37227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 38227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 39227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 40227825Stheraven 41227825Stheraven typedef /unspecified/ iterator; 42227825Stheraven typedef /unspecified/ const_iterator; 43227825Stheraven typedef /unspecified/ local_iterator; 44227825Stheraven typedef /unspecified/ const_local_iterator; 45227825Stheraven 46227825Stheraven unordered_set() 47227825Stheraven noexcept( 48227825Stheraven is_nothrow_default_constructible<hasher>::value && 49227825Stheraven is_nothrow_default_constructible<key_equal>::value && 50227825Stheraven is_nothrow_default_constructible<allocator_type>::value); 51227825Stheraven explicit unordered_set(size_type n, const hasher& hf = hasher(), 52227825Stheraven const key_equal& eql = key_equal(), 53227825Stheraven const allocator_type& a = allocator_type()); 54227825Stheraven template <class InputIterator> 55227825Stheraven unordered_set(InputIterator f, InputIterator l, 56227825Stheraven size_type n = 0, const hasher& hf = hasher(), 57227825Stheraven const key_equal& eql = key_equal(), 58227825Stheraven const allocator_type& a = allocator_type()); 59227825Stheraven explicit unordered_set(const allocator_type&); 60227825Stheraven unordered_set(const unordered_set&); 61227825Stheraven unordered_set(const unordered_set&, const Allocator&); 62227825Stheraven unordered_set(unordered_set&&) 63227825Stheraven noexcept( 64227825Stheraven is_nothrow_move_constructible<hasher>::value && 65227825Stheraven is_nothrow_move_constructible<key_equal>::value && 66227825Stheraven is_nothrow_move_constructible<allocator_type>::value); 67227825Stheraven unordered_set(unordered_set&&, const Allocator&); 68227825Stheraven unordered_set(initializer_list<value_type>, size_type n = 0, 69227825Stheraven const hasher& hf = hasher(), const key_equal& eql = key_equal(), 70227825Stheraven const allocator_type& a = allocator_type()); 71262801Sdim unordered_set(size_type n, const allocator_type& a); // C++14 72262801Sdim unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14 73262801Sdim template <class InputIterator> 74262801Sdim unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 75262801Sdim template <class InputIterator> 76262801Sdim unordered_set(InputIterator f, InputIterator l, size_type n, 77262801Sdim const hasher& hf, const allocator_type& a); // C++14 78262801Sdim unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 79262801Sdim unordered_set(initializer_list<value_type> il, size_type n, 80262801Sdim const hasher& hf, const allocator_type& a); // C++14 81227825Stheraven ~unordered_set(); 82227825Stheraven unordered_set& operator=(const unordered_set&); 83227825Stheraven unordered_set& operator=(unordered_set&&) 84227825Stheraven noexcept( 85227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 86227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 87227825Stheraven is_nothrow_move_assignable<hasher>::value && 88227825Stheraven is_nothrow_move_assignable<key_equal>::value); 89227825Stheraven unordered_set& operator=(initializer_list<value_type>); 90227825Stheraven 91227825Stheraven allocator_type get_allocator() const noexcept; 92227825Stheraven 93227825Stheraven bool empty() const noexcept; 94227825Stheraven size_type size() const noexcept; 95227825Stheraven size_type max_size() const noexcept; 96227825Stheraven 97227825Stheraven iterator begin() noexcept; 98227825Stheraven iterator end() noexcept; 99227825Stheraven const_iterator begin() const noexcept; 100227825Stheraven const_iterator end() const noexcept; 101227825Stheraven const_iterator cbegin() const noexcept; 102227825Stheraven const_iterator cend() const noexcept; 103227825Stheraven 104227825Stheraven template <class... Args> 105227825Stheraven pair<iterator, bool> emplace(Args&&... args); 106227825Stheraven template <class... Args> 107227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 108227825Stheraven pair<iterator, bool> insert(const value_type& obj); 109227825Stheraven pair<iterator, bool> insert(value_type&& obj); 110227825Stheraven iterator insert(const_iterator hint, const value_type& obj); 111227825Stheraven iterator insert(const_iterator hint, value_type&& obj); 112227825Stheraven template <class InputIterator> 113227825Stheraven void insert(InputIterator first, InputIterator last); 114227825Stheraven void insert(initializer_list<value_type>); 115227825Stheraven 116227825Stheraven iterator erase(const_iterator position); 117227825Stheraven size_type erase(const key_type& k); 118227825Stheraven iterator erase(const_iterator first, const_iterator last); 119227825Stheraven void clear() noexcept; 120227825Stheraven 121227825Stheraven void swap(unordered_set&) 122227825Stheraven noexcept( 123227825Stheraven (!allocator_type::propagate_on_container_swap::value || 124227825Stheraven __is_nothrow_swappable<allocator_type>::value) && 125227825Stheraven __is_nothrow_swappable<hasher>::value && 126227825Stheraven __is_nothrow_swappable<key_equal>::value); 127227825Stheraven 128227825Stheraven hasher hash_function() const; 129227825Stheraven key_equal key_eq() const; 130227825Stheraven 131227825Stheraven iterator find(const key_type& k); 132227825Stheraven const_iterator find(const key_type& k) const; 133227825Stheraven size_type count(const key_type& k) const; 134227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 135227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 136227825Stheraven 137227825Stheraven size_type bucket_count() const noexcept; 138227825Stheraven size_type max_bucket_count() const noexcept; 139227825Stheraven 140227825Stheraven size_type bucket_size(size_type n) const; 141227825Stheraven size_type bucket(const key_type& k) const; 142227825Stheraven 143227825Stheraven local_iterator begin(size_type n); 144227825Stheraven local_iterator end(size_type n); 145227825Stheraven const_local_iterator begin(size_type n) const; 146227825Stheraven const_local_iterator end(size_type n) const; 147227825Stheraven const_local_iterator cbegin(size_type n) const; 148227825Stheraven const_local_iterator cend(size_type n) const; 149227825Stheraven 150227825Stheraven float load_factor() const noexcept; 151227825Stheraven float max_load_factor() const noexcept; 152227825Stheraven void max_load_factor(float z); 153227825Stheraven void rehash(size_type n); 154227825Stheraven void reserve(size_type n); 155227825Stheraven}; 156227825Stheraven 157227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 158227825Stheraven void swap(unordered_set<Value, Hash, Pred, Alloc>& x, 159227825Stheraven unordered_set<Value, Hash, Pred, Alloc>& y) 160227825Stheraven noexcept(noexcept(x.swap(y))); 161227825Stheraven 162227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 163227825Stheraven bool 164227825Stheraven operator==(const unordered_set<Value, Hash, Pred, Alloc>& x, 165227825Stheraven const unordered_set<Value, Hash, Pred, Alloc>& y); 166227825Stheraven 167227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 168227825Stheraven bool 169227825Stheraven operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x, 170227825Stheraven const unordered_set<Value, Hash, Pred, Alloc>& y); 171227825Stheraven 172227825Stheraventemplate <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 173227825Stheraven class Alloc = allocator<Value>> 174227825Stheravenclass unordered_multiset 175227825Stheraven{ 176227825Stheravenpublic: 177227825Stheraven // types 178227825Stheraven typedef Value key_type; 179227825Stheraven typedef key_type value_type; 180227825Stheraven typedef Hash hasher; 181227825Stheraven typedef Pred key_equal; 182227825Stheraven typedef Alloc allocator_type; 183227825Stheraven typedef value_type& reference; 184227825Stheraven typedef const value_type& const_reference; 185227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 186227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 187227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 188227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 189227825Stheraven 190227825Stheraven typedef /unspecified/ iterator; 191227825Stheraven typedef /unspecified/ const_iterator; 192227825Stheraven typedef /unspecified/ local_iterator; 193227825Stheraven typedef /unspecified/ const_local_iterator; 194227825Stheraven 195227825Stheraven unordered_multiset() 196227825Stheraven noexcept( 197227825Stheraven is_nothrow_default_constructible<hasher>::value && 198227825Stheraven is_nothrow_default_constructible<key_equal>::value && 199227825Stheraven is_nothrow_default_constructible<allocator_type>::value); 200227825Stheraven explicit unordered_multiset(size_type n, const hasher& hf = hasher(), 201227825Stheraven const key_equal& eql = key_equal(), 202227825Stheraven const allocator_type& a = allocator_type()); 203227825Stheraven template <class InputIterator> 204227825Stheraven unordered_multiset(InputIterator f, InputIterator l, 205227825Stheraven size_type n = 0, const hasher& hf = hasher(), 206227825Stheraven const key_equal& eql = key_equal(), 207227825Stheraven const allocator_type& a = allocator_type()); 208227825Stheraven explicit unordered_multiset(const allocator_type&); 209227825Stheraven unordered_multiset(const unordered_multiset&); 210227825Stheraven unordered_multiset(const unordered_multiset&, const Allocator&); 211227825Stheraven unordered_multiset(unordered_multiset&&) 212227825Stheraven noexcept( 213227825Stheraven is_nothrow_move_constructible<hasher>::value && 214227825Stheraven is_nothrow_move_constructible<key_equal>::value && 215227825Stheraven is_nothrow_move_constructible<allocator_type>::value); 216227825Stheraven unordered_multiset(unordered_multiset&&, const Allocator&); 217227825Stheraven unordered_multiset(initializer_list<value_type>, size_type n = /see below/, 218227825Stheraven const hasher& hf = hasher(), const key_equal& eql = key_equal(), 219227825Stheraven const allocator_type& a = allocator_type()); 220262801Sdim unordered_multiset(size_type n, const allocator_type& a); // C++14 221262801Sdim unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14 222262801Sdim template <class InputIterator> 223262801Sdim unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 224262801Sdim template <class InputIterator> 225262801Sdim unordered_multiset(InputIterator f, InputIterator l, size_type n, 226262801Sdim const hasher& hf, const allocator_type& a); // C++14 227262801Sdim unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 228262801Sdim unordered_multiset(initializer_list<value_type> il, size_type n, 229262801Sdim const hasher& hf, const allocator_type& a); // C++14 230227825Stheraven ~unordered_multiset(); 231227825Stheraven unordered_multiset& operator=(const unordered_multiset&); 232227825Stheraven unordered_multiset& operator=(unordered_multiset&&) 233227825Stheraven noexcept( 234227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 235227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 236227825Stheraven is_nothrow_move_assignable<hasher>::value && 237227825Stheraven is_nothrow_move_assignable<key_equal>::value); 238227825Stheraven unordered_multiset& operator=(initializer_list<value_type>); 239227825Stheraven 240227825Stheraven allocator_type get_allocator() const noexcept; 241227825Stheraven 242227825Stheraven bool empty() const noexcept; 243227825Stheraven size_type size() const noexcept; 244227825Stheraven size_type max_size() const noexcept; 245227825Stheraven 246227825Stheraven iterator begin() noexcept; 247227825Stheraven iterator end() noexcept; 248227825Stheraven const_iterator begin() const noexcept; 249227825Stheraven const_iterator end() const noexcept; 250227825Stheraven const_iterator cbegin() const noexcept; 251227825Stheraven const_iterator cend() const noexcept; 252227825Stheraven 253227825Stheraven template <class... Args> 254227825Stheraven iterator emplace(Args&&... args); 255227825Stheraven template <class... Args> 256227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 257227825Stheraven iterator insert(const value_type& obj); 258227825Stheraven iterator insert(value_type&& obj); 259227825Stheraven iterator insert(const_iterator hint, const value_type& obj); 260227825Stheraven iterator insert(const_iterator hint, value_type&& obj); 261227825Stheraven template <class InputIterator> 262227825Stheraven void insert(InputIterator first, InputIterator last); 263227825Stheraven void insert(initializer_list<value_type>); 264227825Stheraven 265227825Stheraven iterator erase(const_iterator position); 266227825Stheraven size_type erase(const key_type& k); 267227825Stheraven iterator erase(const_iterator first, const_iterator last); 268227825Stheraven void clear() noexcept; 269227825Stheraven 270227825Stheraven void swap(unordered_multiset&) 271227825Stheraven noexcept( 272227825Stheraven (!allocator_type::propagate_on_container_swap::value || 273227825Stheraven __is_nothrow_swappable<allocator_type>::value) && 274227825Stheraven __is_nothrow_swappable<hasher>::value && 275227825Stheraven __is_nothrow_swappable<key_equal>::value); 276227825Stheraven 277227825Stheraven hasher hash_function() const; 278227825Stheraven key_equal key_eq() const; 279227825Stheraven 280227825Stheraven iterator find(const key_type& k); 281227825Stheraven const_iterator find(const key_type& k) const; 282227825Stheraven size_type count(const key_type& k) const; 283227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 284227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 285227825Stheraven 286227825Stheraven size_type bucket_count() const noexcept; 287227825Stheraven size_type max_bucket_count() const noexcept; 288227825Stheraven 289227825Stheraven size_type bucket_size(size_type n) const; 290227825Stheraven size_type bucket(const key_type& k) const; 291227825Stheraven 292227825Stheraven local_iterator begin(size_type n); 293227825Stheraven local_iterator end(size_type n); 294227825Stheraven const_local_iterator begin(size_type n) const; 295227825Stheraven const_local_iterator end(size_type n) const; 296227825Stheraven const_local_iterator cbegin(size_type n) const; 297227825Stheraven const_local_iterator cend(size_type n) const; 298227825Stheraven 299227825Stheraven float load_factor() const noexcept; 300227825Stheraven float max_load_factor() const noexcept; 301227825Stheraven void max_load_factor(float z); 302227825Stheraven void rehash(size_type n); 303227825Stheraven void reserve(size_type n); 304227825Stheraven}; 305227825Stheraven 306227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 307227825Stheraven void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x, 308227825Stheraven unordered_multiset<Value, Hash, Pred, Alloc>& y) 309227825Stheraven noexcept(noexcept(x.swap(y))); 310227825Stheraven 311227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 312227825Stheraven bool 313227825Stheraven operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 314227825Stheraven const unordered_multiset<Value, Hash, Pred, Alloc>& y); 315227825Stheraven 316227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 317227825Stheraven bool 318227825Stheraven operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 319227825Stheraven const unordered_multiset<Value, Hash, Pred, Alloc>& y); 320227825Stheraven} // std 321227825Stheraven 322227825Stheraven*/ 323227825Stheraven 324227825Stheraven#include <__config> 325227825Stheraven#include <__hash_table> 326227825Stheraven#include <functional> 327227825Stheraven 328278724Sdim#include <__debug> 329278724Sdim 330227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 331227825Stheraven#pragma GCC system_header 332227825Stheraven#endif 333227825Stheraven 334227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 335227825Stheraven 336227825Stheraventemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 337227825Stheraven class _Alloc = allocator<_Value> > 338262801Sdimclass _LIBCPP_TYPE_VIS_ONLY unordered_set 339227825Stheraven{ 340227825Stheravenpublic: 341227825Stheraven // types 342227825Stheraven typedef _Value key_type; 343227825Stheraven typedef key_type value_type; 344227825Stheraven typedef _Hash hasher; 345227825Stheraven typedef _Pred key_equal; 346227825Stheraven typedef _Alloc allocator_type; 347227825Stheraven typedef value_type& reference; 348227825Stheraven typedef const value_type& const_reference; 349262801Sdim static_assert((is_same<value_type, typename allocator_type::value_type>::value), 350262801Sdim "Invalid allocator::value_type"); 351227825Stheraven 352227825Stheravenprivate: 353227825Stheraven typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 354227825Stheraven 355227825Stheraven __table __table_; 356227825Stheraven 357227825Stheravenpublic: 358227825Stheraven typedef typename __table::pointer pointer; 359227825Stheraven typedef typename __table::const_pointer const_pointer; 360227825Stheraven typedef typename __table::size_type size_type; 361227825Stheraven typedef typename __table::difference_type difference_type; 362227825Stheraven 363227825Stheraven typedef typename __table::const_iterator iterator; 364227825Stheraven typedef typename __table::const_iterator const_iterator; 365227825Stheraven typedef typename __table::const_local_iterator local_iterator; 366227825Stheraven typedef typename __table::const_local_iterator const_local_iterator; 367227825Stheraven 368227825Stheraven _LIBCPP_INLINE_VISIBILITY 369227825Stheraven unordered_set() 370227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 371262801Sdim { 372262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 373262801Sdim __get_db()->__insert_c(this); 374262801Sdim#endif 375262801Sdim } 376227825Stheraven explicit unordered_set(size_type __n, const hasher& __hf = hasher(), 377227825Stheraven const key_equal& __eql = key_equal()); 378262801Sdim#if _LIBCPP_STD_VER > 11 379262801Sdim inline _LIBCPP_INLINE_VISIBILITY 380262801Sdim unordered_set(size_type __n, const allocator_type& __a) 381262801Sdim : unordered_set(__n, hasher(), key_equal(), __a) {} 382262801Sdim inline _LIBCPP_INLINE_VISIBILITY 383262801Sdim unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a) 384262801Sdim : unordered_set(__n, __hf, key_equal(), __a) {} 385262801Sdim#endif 386227825Stheraven unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, 387227825Stheraven const allocator_type& __a); 388227825Stheraven template <class _InputIterator> 389227825Stheraven unordered_set(_InputIterator __first, _InputIterator __last); 390227825Stheraven template <class _InputIterator> 391227825Stheraven unordered_set(_InputIterator __first, _InputIterator __last, 392227825Stheraven size_type __n, const hasher& __hf = hasher(), 393227825Stheraven const key_equal& __eql = key_equal()); 394227825Stheraven template <class _InputIterator> 395227825Stheraven unordered_set(_InputIterator __first, _InputIterator __last, 396227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 397227825Stheraven const allocator_type& __a); 398262801Sdim#if _LIBCPP_STD_VER > 11 399262801Sdim template <class _InputIterator> 400262801Sdim inline _LIBCPP_INLINE_VISIBILITY 401262801Sdim unordered_set(_InputIterator __first, _InputIterator __last, 402262801Sdim size_type __n, const allocator_type& __a) 403262801Sdim : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} 404262801Sdim template <class _InputIterator> 405262801Sdim unordered_set(_InputIterator __first, _InputIterator __last, 406262801Sdim size_type __n, const hasher& __hf, const allocator_type& __a) 407262801Sdim : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} 408262801Sdim#endif 409227825Stheraven explicit unordered_set(const allocator_type& __a); 410227825Stheraven unordered_set(const unordered_set& __u); 411227825Stheraven unordered_set(const unordered_set& __u, const allocator_type& __a); 412227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 413227825Stheraven unordered_set(unordered_set&& __u) 414227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 415227825Stheraven unordered_set(unordered_set&& __u, const allocator_type& __a); 416227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 417227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 418227825Stheraven unordered_set(initializer_list<value_type> __il); 419227825Stheraven unordered_set(initializer_list<value_type> __il, size_type __n, 420227825Stheraven const hasher& __hf = hasher(), 421227825Stheraven const key_equal& __eql = key_equal()); 422227825Stheraven unordered_set(initializer_list<value_type> __il, size_type __n, 423227825Stheraven const hasher& __hf, const key_equal& __eql, 424227825Stheraven const allocator_type& __a); 425262801Sdim#if _LIBCPP_STD_VER > 11 426262801Sdim inline _LIBCPP_INLINE_VISIBILITY 427262801Sdim unordered_set(initializer_list<value_type> __il, size_type __n, 428262801Sdim const allocator_type& __a) 429262801Sdim : unordered_set(__il, __n, hasher(), key_equal(), __a) {} 430262801Sdim inline _LIBCPP_INLINE_VISIBILITY 431262801Sdim unordered_set(initializer_list<value_type> __il, size_type __n, 432262801Sdim const hasher& __hf, const allocator_type& __a) 433262801Sdim : unordered_set(__il, __n, __hf, key_equal(), __a) {} 434262801Sdim#endif 435227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 436227825Stheraven // ~unordered_set() = default; 437227825Stheraven _LIBCPP_INLINE_VISIBILITY 438227825Stheraven unordered_set& operator=(const unordered_set& __u) 439227825Stheraven { 440227825Stheraven __table_ = __u.__table_; 441227825Stheraven return *this; 442227825Stheraven } 443227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 444227825Stheraven unordered_set& operator=(unordered_set&& __u) 445227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 446227825Stheraven#endif 447227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 448227825Stheraven unordered_set& operator=(initializer_list<value_type> __il); 449227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 450227825Stheraven 451227825Stheraven _LIBCPP_INLINE_VISIBILITY 452227825Stheraven allocator_type get_allocator() const _NOEXCEPT 453227825Stheraven {return allocator_type(__table_.__node_alloc());} 454227825Stheraven 455227825Stheraven _LIBCPP_INLINE_VISIBILITY 456227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 457227825Stheraven _LIBCPP_INLINE_VISIBILITY 458227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 459227825Stheraven _LIBCPP_INLINE_VISIBILITY 460227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 461227825Stheraven 462227825Stheraven _LIBCPP_INLINE_VISIBILITY 463227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 464227825Stheraven _LIBCPP_INLINE_VISIBILITY 465227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 466227825Stheraven _LIBCPP_INLINE_VISIBILITY 467227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 468227825Stheraven _LIBCPP_INLINE_VISIBILITY 469227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 470227825Stheraven _LIBCPP_INLINE_VISIBILITY 471227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 472227825Stheraven _LIBCPP_INLINE_VISIBILITY 473227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 474227825Stheraven 475227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 476227825Stheraven template <class... _Args> 477227825Stheraven _LIBCPP_INLINE_VISIBILITY 478227825Stheraven pair<iterator, bool> emplace(_Args&&... __args) 479227825Stheraven {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 480227825Stheraven template <class... _Args> 481227825Stheraven _LIBCPP_INLINE_VISIBILITY 482262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 483262801Sdim iterator emplace_hint(const_iterator __p, _Args&&... __args) 484262801Sdim { 485262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 486262801Sdim "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not" 487262801Sdim " referring to this unordered_set"); 488262801Sdim return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 489262801Sdim } 490262801Sdim#else 491227825Stheraven iterator emplace_hint(const_iterator, _Args&&... __args) 492227825Stheraven {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;} 493262801Sdim#endif 494227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 495227825Stheraven _LIBCPP_INLINE_VISIBILITY 496227825Stheraven pair<iterator, bool> insert(const value_type& __x) 497227825Stheraven {return __table_.__insert_unique(__x);} 498227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 499227825Stheraven _LIBCPP_INLINE_VISIBILITY 500227825Stheraven pair<iterator, bool> insert(value_type&& __x) 501227825Stheraven {return __table_.__insert_unique(_VSTD::move(__x));} 502227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 503227825Stheraven _LIBCPP_INLINE_VISIBILITY 504262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 505262801Sdim iterator insert(const_iterator __p, const value_type& __x) 506262801Sdim { 507262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 508262801Sdim "unordered_set::insert(const_iterator, const value_type&) called with an iterator not" 509262801Sdim " referring to this unordered_set"); 510262801Sdim return insert(__x).first; 511262801Sdim } 512262801Sdim#else 513227825Stheraven iterator insert(const_iterator, const value_type& __x) 514227825Stheraven {return insert(__x).first;} 515262801Sdim#endif 516227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 517227825Stheraven _LIBCPP_INLINE_VISIBILITY 518262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 519262801Sdim iterator insert(const_iterator __p, value_type&& __x) 520262801Sdim { 521262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 522262801Sdim "unordered_set::insert(const_iterator, value_type&&) called with an iterator not" 523262801Sdim " referring to this unordered_set"); 524262801Sdim return insert(_VSTD::move(__x)).first; 525262801Sdim } 526262801Sdim#else 527227825Stheraven iterator insert(const_iterator, value_type&& __x) 528227825Stheraven {return insert(_VSTD::move(__x)).first;} 529262801Sdim#endif 530227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 531227825Stheraven template <class _InputIterator> 532227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 533227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 534227825Stheraven _LIBCPP_INLINE_VISIBILITY 535227825Stheraven void insert(initializer_list<value_type> __il) 536227825Stheraven {insert(__il.begin(), __il.end());} 537227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 538227825Stheraven 539227825Stheraven _LIBCPP_INLINE_VISIBILITY 540227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p);} 541227825Stheraven _LIBCPP_INLINE_VISIBILITY 542227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 543227825Stheraven _LIBCPP_INLINE_VISIBILITY 544227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 545227825Stheraven {return __table_.erase(__first, __last);} 546227825Stheraven _LIBCPP_INLINE_VISIBILITY 547227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 548227825Stheraven 549227825Stheraven _LIBCPP_INLINE_VISIBILITY 550227825Stheraven void swap(unordered_set& __u) 551227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 552227825Stheraven {__table_.swap(__u.__table_);} 553227825Stheraven 554227825Stheraven _LIBCPP_INLINE_VISIBILITY 555227825Stheraven hasher hash_function() const {return __table_.hash_function();} 556227825Stheraven _LIBCPP_INLINE_VISIBILITY 557227825Stheraven key_equal key_eq() const {return __table_.key_eq();} 558227825Stheraven 559227825Stheraven _LIBCPP_INLINE_VISIBILITY 560227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 561227825Stheraven _LIBCPP_INLINE_VISIBILITY 562227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 563227825Stheraven _LIBCPP_INLINE_VISIBILITY 564227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 565227825Stheraven _LIBCPP_INLINE_VISIBILITY 566227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 567227825Stheraven {return __table_.__equal_range_unique(__k);} 568227825Stheraven _LIBCPP_INLINE_VISIBILITY 569227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 570227825Stheraven {return __table_.__equal_range_unique(__k);} 571227825Stheraven 572227825Stheraven _LIBCPP_INLINE_VISIBILITY 573227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 574227825Stheraven _LIBCPP_INLINE_VISIBILITY 575227825Stheraven size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 576227825Stheraven 577227825Stheraven _LIBCPP_INLINE_VISIBILITY 578227825Stheraven size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 579227825Stheraven _LIBCPP_INLINE_VISIBILITY 580227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 581227825Stheraven 582227825Stheraven _LIBCPP_INLINE_VISIBILITY 583227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 584227825Stheraven _LIBCPP_INLINE_VISIBILITY 585227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 586227825Stheraven _LIBCPP_INLINE_VISIBILITY 587227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 588227825Stheraven _LIBCPP_INLINE_VISIBILITY 589227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 590227825Stheraven _LIBCPP_INLINE_VISIBILITY 591227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 592227825Stheraven _LIBCPP_INLINE_VISIBILITY 593227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 594227825Stheraven 595227825Stheraven _LIBCPP_INLINE_VISIBILITY 596227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 597227825Stheraven _LIBCPP_INLINE_VISIBILITY 598227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 599227825Stheraven _LIBCPP_INLINE_VISIBILITY 600227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 601227825Stheraven _LIBCPP_INLINE_VISIBILITY 602227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 603227825Stheraven _LIBCPP_INLINE_VISIBILITY 604227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 605262801Sdim 606262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 607262801Sdim 608262801Sdim bool __dereferenceable(const const_iterator* __i) const 609262801Sdim {return __table_.__dereferenceable(__i);} 610262801Sdim bool __decrementable(const const_iterator* __i) const 611262801Sdim {return __table_.__decrementable(__i);} 612262801Sdim bool __addable(const const_iterator* __i, ptrdiff_t __n) const 613262801Sdim {return __table_.__addable(__i, __n);} 614262801Sdim bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 615262801Sdim {return __table_.__addable(__i, __n);} 616262801Sdim 617262801Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 618262801Sdim 619227825Stheraven}; 620227825Stheraven 621227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 622227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 623227825Stheraven const hasher& __hf, const key_equal& __eql) 624227825Stheraven : __table_(__hf, __eql) 625227825Stheraven{ 626262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 627262801Sdim __get_db()->__insert_c(this); 628262801Sdim#endif 629227825Stheraven __table_.rehash(__n); 630227825Stheraven} 631227825Stheraven 632227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 633227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 634227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 635227825Stheraven : __table_(__hf, __eql, __a) 636227825Stheraven{ 637262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 638262801Sdim __get_db()->__insert_c(this); 639262801Sdim#endif 640227825Stheraven __table_.rehash(__n); 641227825Stheraven} 642227825Stheraven 643227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 644227825Stheraventemplate <class _InputIterator> 645227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 646227825Stheraven _InputIterator __first, _InputIterator __last) 647227825Stheraven{ 648262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 649262801Sdim __get_db()->__insert_c(this); 650262801Sdim#endif 651227825Stheraven insert(__first, __last); 652227825Stheraven} 653227825Stheraven 654227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 655227825Stheraventemplate <class _InputIterator> 656227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 657227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 658227825Stheraven const hasher& __hf, const key_equal& __eql) 659227825Stheraven : __table_(__hf, __eql) 660227825Stheraven{ 661262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 662262801Sdim __get_db()->__insert_c(this); 663262801Sdim#endif 664227825Stheraven __table_.rehash(__n); 665227825Stheraven insert(__first, __last); 666227825Stheraven} 667227825Stheraven 668227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 669227825Stheraventemplate <class _InputIterator> 670227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 671227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 672227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 673227825Stheraven : __table_(__hf, __eql, __a) 674227825Stheraven{ 675262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 676262801Sdim __get_db()->__insert_c(this); 677262801Sdim#endif 678227825Stheraven __table_.rehash(__n); 679227825Stheraven insert(__first, __last); 680227825Stheraven} 681227825Stheraven 682227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 683227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 684227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 685227825Stheraven const allocator_type& __a) 686227825Stheraven : __table_(__a) 687227825Stheraven{ 688262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 689262801Sdim __get_db()->__insert_c(this); 690262801Sdim#endif 691227825Stheraven} 692227825Stheraven 693227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 694227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 695227825Stheraven const unordered_set& __u) 696227825Stheraven : __table_(__u.__table_) 697227825Stheraven{ 698262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 699262801Sdim __get_db()->__insert_c(this); 700262801Sdim#endif 701227825Stheraven __table_.rehash(__u.bucket_count()); 702227825Stheraven insert(__u.begin(), __u.end()); 703227825Stheraven} 704227825Stheraven 705227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 706227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 707227825Stheraven const unordered_set& __u, const allocator_type& __a) 708227825Stheraven : __table_(__u.__table_, __a) 709227825Stheraven{ 710262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 711262801Sdim __get_db()->__insert_c(this); 712262801Sdim#endif 713227825Stheraven __table_.rehash(__u.bucket_count()); 714227825Stheraven insert(__u.begin(), __u.end()); 715227825Stheraven} 716227825Stheraven 717227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 718227825Stheraven 719227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 720227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 721227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 722227825Stheraven unordered_set&& __u) 723227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 724227825Stheraven : __table_(_VSTD::move(__u.__table_)) 725227825Stheraven{ 726262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 727262801Sdim __get_db()->__insert_c(this); 728262801Sdim __get_db()->swap(this, &__u); 729262801Sdim#endif 730227825Stheraven} 731227825Stheraven 732227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 733227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 734227825Stheraven unordered_set&& __u, const allocator_type& __a) 735227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 736227825Stheraven{ 737262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 738262801Sdim __get_db()->__insert_c(this); 739262801Sdim#endif 740227825Stheraven if (__a != __u.get_allocator()) 741227825Stheraven { 742227825Stheraven iterator __i = __u.begin(); 743227825Stheraven while (__u.size() != 0) 744227825Stheraven __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 745227825Stheraven } 746262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 747262801Sdim else 748262801Sdim __get_db()->swap(this, &__u); 749262801Sdim#endif 750227825Stheraven} 751227825Stheraven 752227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 753227825Stheraven 754227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 755227825Stheraven 756227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 757227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 758227825Stheraven initializer_list<value_type> __il) 759227825Stheraven{ 760262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 761262801Sdim __get_db()->__insert_c(this); 762262801Sdim#endif 763227825Stheraven insert(__il.begin(), __il.end()); 764227825Stheraven} 765227825Stheraven 766227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 767227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 768227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 769227825Stheraven const key_equal& __eql) 770227825Stheraven : __table_(__hf, __eql) 771227825Stheraven{ 772262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 773262801Sdim __get_db()->__insert_c(this); 774262801Sdim#endif 775227825Stheraven __table_.rehash(__n); 776227825Stheraven insert(__il.begin(), __il.end()); 777227825Stheraven} 778227825Stheraven 779227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 780227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 781227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 782227825Stheraven const key_equal& __eql, const allocator_type& __a) 783227825Stheraven : __table_(__hf, __eql, __a) 784227825Stheraven{ 785262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 786262801Sdim __get_db()->__insert_c(this); 787262801Sdim#endif 788227825Stheraven __table_.rehash(__n); 789227825Stheraven insert(__il.begin(), __il.end()); 790227825Stheraven} 791227825Stheraven 792227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 793227825Stheraven 794227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 795227825Stheraven 796227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 797227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 798227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>& 799227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 800227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 801227825Stheraven{ 802227825Stheraven __table_ = _VSTD::move(__u.__table_); 803227825Stheraven return *this; 804227825Stheraven} 805227825Stheraven 806227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 807227825Stheraven 808227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 809227825Stheraven 810227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 811227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 812227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>& 813227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::operator=( 814227825Stheraven initializer_list<value_type> __il) 815227825Stheraven{ 816227825Stheraven __table_.__assign_unique(__il.begin(), __il.end()); 817227825Stheraven return *this; 818227825Stheraven} 819227825Stheraven 820227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 821227825Stheraven 822227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 823227825Stheraventemplate <class _InputIterator> 824227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 825227825Stheravenvoid 826227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 827227825Stheraven _InputIterator __last) 828227825Stheraven{ 829227825Stheraven for (; __first != __last; ++__first) 830227825Stheraven __table_.__insert_unique(*__first); 831227825Stheraven} 832227825Stheraven 833227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 834227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 835227825Stheravenvoid 836227825Stheravenswap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 837227825Stheraven unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 838227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 839227825Stheraven{ 840227825Stheraven __x.swap(__y); 841227825Stheraven} 842227825Stheraven 843227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 844227825Stheravenbool 845227825Stheravenoperator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 846227825Stheraven const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 847227825Stheraven{ 848227825Stheraven if (__x.size() != __y.size()) 849227825Stheraven return false; 850227825Stheraven typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 851227825Stheraven const_iterator; 852227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 853227825Stheraven __i != __ex; ++__i) 854227825Stheraven { 855227825Stheraven const_iterator __j = __y.find(*__i); 856227825Stheraven if (__j == __ey || !(*__i == *__j)) 857227825Stheraven return false; 858227825Stheraven } 859227825Stheraven return true; 860227825Stheraven} 861227825Stheraven 862227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 863227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 864227825Stheravenbool 865227825Stheravenoperator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 866227825Stheraven const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 867227825Stheraven{ 868227825Stheraven return !(__x == __y); 869227825Stheraven} 870227825Stheraven 871227825Stheraventemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 872227825Stheraven class _Alloc = allocator<_Value> > 873262801Sdimclass _LIBCPP_TYPE_VIS_ONLY unordered_multiset 874227825Stheraven{ 875227825Stheravenpublic: 876227825Stheraven // types 877227825Stheraven typedef _Value key_type; 878227825Stheraven typedef key_type value_type; 879227825Stheraven typedef _Hash hasher; 880227825Stheraven typedef _Pred key_equal; 881227825Stheraven typedef _Alloc allocator_type; 882227825Stheraven typedef value_type& reference; 883227825Stheraven typedef const value_type& const_reference; 884262801Sdim static_assert((is_same<value_type, typename allocator_type::value_type>::value), 885262801Sdim "Invalid allocator::value_type"); 886227825Stheraven 887227825Stheravenprivate: 888227825Stheraven typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 889227825Stheraven 890227825Stheraven __table __table_; 891227825Stheraven 892227825Stheravenpublic: 893227825Stheraven typedef typename __table::pointer pointer; 894227825Stheraven typedef typename __table::const_pointer const_pointer; 895227825Stheraven typedef typename __table::size_type size_type; 896227825Stheraven typedef typename __table::difference_type difference_type; 897227825Stheraven 898227825Stheraven typedef typename __table::const_iterator iterator; 899227825Stheraven typedef typename __table::const_iterator const_iterator; 900227825Stheraven typedef typename __table::const_local_iterator local_iterator; 901227825Stheraven typedef typename __table::const_local_iterator const_local_iterator; 902227825Stheraven 903227825Stheraven _LIBCPP_INLINE_VISIBILITY 904227825Stheraven unordered_multiset() 905227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 906262801Sdim { 907262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 908262801Sdim __get_db()->__insert_c(this); 909262801Sdim#endif 910262801Sdim } 911227825Stheraven explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(), 912227825Stheraven const key_equal& __eql = key_equal()); 913227825Stheraven unordered_multiset(size_type __n, const hasher& __hf, 914227825Stheraven const key_equal& __eql, const allocator_type& __a); 915262801Sdim#if _LIBCPP_STD_VER > 11 916262801Sdim inline _LIBCPP_INLINE_VISIBILITY 917262801Sdim unordered_multiset(size_type __n, const allocator_type& __a) 918262801Sdim : unordered_multiset(__n, hasher(), key_equal(), __a) {} 919262801Sdim inline _LIBCPP_INLINE_VISIBILITY 920262801Sdim unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) 921262801Sdim : unordered_multiset(__n, __hf, key_equal(), __a) {} 922262801Sdim#endif 923227825Stheraven template <class _InputIterator> 924227825Stheraven unordered_multiset(_InputIterator __first, _InputIterator __last); 925227825Stheraven template <class _InputIterator> 926227825Stheraven unordered_multiset(_InputIterator __first, _InputIterator __last, 927227825Stheraven size_type __n, const hasher& __hf = hasher(), 928227825Stheraven const key_equal& __eql = key_equal()); 929227825Stheraven template <class _InputIterator> 930227825Stheraven unordered_multiset(_InputIterator __first, _InputIterator __last, 931227825Stheraven size_type __n , const hasher& __hf, 932227825Stheraven const key_equal& __eql, const allocator_type& __a); 933262801Sdim#if _LIBCPP_STD_VER > 11 934262801Sdim template <class _InputIterator> 935262801Sdim inline _LIBCPP_INLINE_VISIBILITY 936262801Sdim unordered_multiset(_InputIterator __first, _InputIterator __last, 937262801Sdim size_type __n, const allocator_type& __a) 938262801Sdim : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} 939262801Sdim template <class _InputIterator> 940262801Sdim inline _LIBCPP_INLINE_VISIBILITY 941262801Sdim unordered_multiset(_InputIterator __first, _InputIterator __last, 942262801Sdim size_type __n, const hasher& __hf, const allocator_type& __a) 943262801Sdim : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} 944262801Sdim#endif 945227825Stheraven explicit unordered_multiset(const allocator_type& __a); 946227825Stheraven unordered_multiset(const unordered_multiset& __u); 947227825Stheraven unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 948227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 949227825Stheraven unordered_multiset(unordered_multiset&& __u) 950227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 951227825Stheraven unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 952227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 953227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 954227825Stheraven unordered_multiset(initializer_list<value_type> __il); 955227825Stheraven unordered_multiset(initializer_list<value_type> __il, size_type __n, 956227825Stheraven const hasher& __hf = hasher(), 957227825Stheraven const key_equal& __eql = key_equal()); 958227825Stheraven unordered_multiset(initializer_list<value_type> __il, size_type __n, 959227825Stheraven const hasher& __hf, const key_equal& __eql, 960227825Stheraven const allocator_type& __a); 961262801Sdim#if _LIBCPP_STD_VER > 11 962262801Sdim inline _LIBCPP_INLINE_VISIBILITY 963262801Sdim unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 964262801Sdim : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} 965262801Sdim inline _LIBCPP_INLINE_VISIBILITY 966262801Sdim unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 967262801Sdim : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} 968262801Sdim#endif 969227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 970227825Stheraven // ~unordered_multiset() = default; 971227825Stheraven _LIBCPP_INLINE_VISIBILITY 972227825Stheraven unordered_multiset& operator=(const unordered_multiset& __u) 973227825Stheraven { 974227825Stheraven __table_ = __u.__table_; 975227825Stheraven return *this; 976227825Stheraven } 977227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 978227825Stheraven unordered_multiset& operator=(unordered_multiset&& __u) 979227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 980227825Stheraven#endif 981227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 982227825Stheraven unordered_multiset& operator=(initializer_list<value_type> __il); 983227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 984227825Stheraven 985227825Stheraven _LIBCPP_INLINE_VISIBILITY 986227825Stheraven allocator_type get_allocator() const _NOEXCEPT 987227825Stheraven {return allocator_type(__table_.__node_alloc());} 988227825Stheraven 989227825Stheraven _LIBCPP_INLINE_VISIBILITY 990227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 991227825Stheraven _LIBCPP_INLINE_VISIBILITY 992227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 993227825Stheraven _LIBCPP_INLINE_VISIBILITY 994227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 995227825Stheraven 996227825Stheraven _LIBCPP_INLINE_VISIBILITY 997227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 998227825Stheraven _LIBCPP_INLINE_VISIBILITY 999227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 1000227825Stheraven _LIBCPP_INLINE_VISIBILITY 1001227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1002227825Stheraven _LIBCPP_INLINE_VISIBILITY 1003227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 1004227825Stheraven _LIBCPP_INLINE_VISIBILITY 1005227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1006227825Stheraven _LIBCPP_INLINE_VISIBILITY 1007227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 1008227825Stheraven 1009227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1010227825Stheraven template <class... _Args> 1011227825Stheraven _LIBCPP_INLINE_VISIBILITY 1012227825Stheraven iterator emplace(_Args&&... __args) 1013227825Stheraven {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 1014227825Stheraven template <class... _Args> 1015227825Stheraven _LIBCPP_INLINE_VISIBILITY 1016227825Stheraven iterator emplace_hint(const_iterator __p, _Args&&... __args) 1017227825Stheraven {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1018227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1019227825Stheraven _LIBCPP_INLINE_VISIBILITY 1020227825Stheraven iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1021227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1022227825Stheraven _LIBCPP_INLINE_VISIBILITY 1023227825Stheraven iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} 1024227825Stheraven#endif 1025227825Stheraven _LIBCPP_INLINE_VISIBILITY 1026227825Stheraven iterator insert(const_iterator __p, const value_type& __x) 1027227825Stheraven {return __table_.__insert_multi(__p, __x);} 1028227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1029227825Stheraven _LIBCPP_INLINE_VISIBILITY 1030227825Stheraven iterator insert(const_iterator __p, value_type&& __x) 1031227825Stheraven {return __table_.__insert_multi(__p, _VSTD::move(__x));} 1032227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1033227825Stheraven template <class _InputIterator> 1034227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 1035227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1036227825Stheraven _LIBCPP_INLINE_VISIBILITY 1037227825Stheraven void insert(initializer_list<value_type> __il) 1038227825Stheraven {insert(__il.begin(), __il.end());} 1039227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1040227825Stheraven 1041227825Stheraven _LIBCPP_INLINE_VISIBILITY 1042227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p);} 1043227825Stheraven _LIBCPP_INLINE_VISIBILITY 1044227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1045227825Stheraven _LIBCPP_INLINE_VISIBILITY 1046227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 1047227825Stheraven {return __table_.erase(__first, __last);} 1048227825Stheraven _LIBCPP_INLINE_VISIBILITY 1049227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 1050227825Stheraven 1051227825Stheraven _LIBCPP_INLINE_VISIBILITY 1052227825Stheraven void swap(unordered_multiset& __u) 1053227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1054227825Stheraven {__table_.swap(__u.__table_);} 1055227825Stheraven 1056227825Stheraven _LIBCPP_INLINE_VISIBILITY 1057227825Stheraven hasher hash_function() const {return __table_.hash_function();} 1058227825Stheraven _LIBCPP_INLINE_VISIBILITY 1059227825Stheraven key_equal key_eq() const {return __table_.key_eq();} 1060227825Stheraven 1061227825Stheraven _LIBCPP_INLINE_VISIBILITY 1062227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 1063227825Stheraven _LIBCPP_INLINE_VISIBILITY 1064227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1065227825Stheraven _LIBCPP_INLINE_VISIBILITY 1066227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1067227825Stheraven _LIBCPP_INLINE_VISIBILITY 1068227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 1069227825Stheraven {return __table_.__equal_range_multi(__k);} 1070227825Stheraven _LIBCPP_INLINE_VISIBILITY 1071227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1072227825Stheraven {return __table_.__equal_range_multi(__k);} 1073227825Stheraven 1074227825Stheraven _LIBCPP_INLINE_VISIBILITY 1075227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1076227825Stheraven _LIBCPP_INLINE_VISIBILITY 1077227825Stheraven size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 1078227825Stheraven 1079227825Stheraven _LIBCPP_INLINE_VISIBILITY 1080227825Stheraven size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 1081227825Stheraven _LIBCPP_INLINE_VISIBILITY 1082227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1083227825Stheraven 1084227825Stheraven _LIBCPP_INLINE_VISIBILITY 1085227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 1086227825Stheraven _LIBCPP_INLINE_VISIBILITY 1087227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 1088227825Stheraven _LIBCPP_INLINE_VISIBILITY 1089227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1090227825Stheraven _LIBCPP_INLINE_VISIBILITY 1091227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1092227825Stheraven _LIBCPP_INLINE_VISIBILITY 1093227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1094227825Stheraven _LIBCPP_INLINE_VISIBILITY 1095227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1096227825Stheraven 1097227825Stheraven _LIBCPP_INLINE_VISIBILITY 1098227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1099227825Stheraven _LIBCPP_INLINE_VISIBILITY 1100227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1101227825Stheraven _LIBCPP_INLINE_VISIBILITY 1102227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1103227825Stheraven _LIBCPP_INLINE_VISIBILITY 1104227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 1105227825Stheraven _LIBCPP_INLINE_VISIBILITY 1106227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 1107262801Sdim 1108262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1109262801Sdim 1110262801Sdim bool __dereferenceable(const const_iterator* __i) const 1111262801Sdim {return __table_.__dereferenceable(__i);} 1112262801Sdim bool __decrementable(const const_iterator* __i) const 1113262801Sdim {return __table_.__decrementable(__i);} 1114262801Sdim bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1115262801Sdim {return __table_.__addable(__i, __n);} 1116262801Sdim bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1117262801Sdim {return __table_.__addable(__i, __n);} 1118262801Sdim 1119262801Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1120262801Sdim 1121227825Stheraven}; 1122227825Stheraven 1123227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1124227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1125227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 1126227825Stheraven : __table_(__hf, __eql) 1127227825Stheraven{ 1128262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1129262801Sdim __get_db()->__insert_c(this); 1130262801Sdim#endif 1131227825Stheraven __table_.rehash(__n); 1132227825Stheraven} 1133227825Stheraven 1134227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1135227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1136227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 1137227825Stheraven const allocator_type& __a) 1138227825Stheraven : __table_(__hf, __eql, __a) 1139227825Stheraven{ 1140262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1141262801Sdim __get_db()->__insert_c(this); 1142262801Sdim#endif 1143227825Stheraven __table_.rehash(__n); 1144227825Stheraven} 1145227825Stheraven 1146227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1147227825Stheraventemplate <class _InputIterator> 1148227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1149227825Stheraven _InputIterator __first, _InputIterator __last) 1150227825Stheraven{ 1151262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1152262801Sdim __get_db()->__insert_c(this); 1153262801Sdim#endif 1154227825Stheraven insert(__first, __last); 1155227825Stheraven} 1156227825Stheraven 1157227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1158227825Stheraventemplate <class _InputIterator> 1159227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1160227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1161227825Stheraven const hasher& __hf, const key_equal& __eql) 1162227825Stheraven : __table_(__hf, __eql) 1163227825Stheraven{ 1164262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1165262801Sdim __get_db()->__insert_c(this); 1166262801Sdim#endif 1167227825Stheraven __table_.rehash(__n); 1168227825Stheraven insert(__first, __last); 1169227825Stheraven} 1170227825Stheraven 1171227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1172227825Stheraventemplate <class _InputIterator> 1173227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1174227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1175227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1176227825Stheraven : __table_(__hf, __eql, __a) 1177227825Stheraven{ 1178262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1179262801Sdim __get_db()->__insert_c(this); 1180262801Sdim#endif 1181227825Stheraven __table_.rehash(__n); 1182227825Stheraven insert(__first, __last); 1183227825Stheraven} 1184227825Stheraven 1185227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1186227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1187227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1188227825Stheraven const allocator_type& __a) 1189227825Stheraven : __table_(__a) 1190227825Stheraven{ 1191262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1192262801Sdim __get_db()->__insert_c(this); 1193262801Sdim#endif 1194227825Stheraven} 1195227825Stheraven 1196227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1197227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1198227825Stheraven const unordered_multiset& __u) 1199227825Stheraven : __table_(__u.__table_) 1200227825Stheraven{ 1201262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1202262801Sdim __get_db()->__insert_c(this); 1203262801Sdim#endif 1204227825Stheraven __table_.rehash(__u.bucket_count()); 1205227825Stheraven insert(__u.begin(), __u.end()); 1206227825Stheraven} 1207227825Stheraven 1208227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1209227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1210227825Stheraven const unordered_multiset& __u, const allocator_type& __a) 1211227825Stheraven : __table_(__u.__table_, __a) 1212227825Stheraven{ 1213262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1214262801Sdim __get_db()->__insert_c(this); 1215262801Sdim#endif 1216227825Stheraven __table_.rehash(__u.bucket_count()); 1217227825Stheraven insert(__u.begin(), __u.end()); 1218227825Stheraven} 1219227825Stheraven 1220227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1221227825Stheraven 1222227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1223227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1224227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1225227825Stheraven unordered_multiset&& __u) 1226227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1227227825Stheraven : __table_(_VSTD::move(__u.__table_)) 1228227825Stheraven{ 1229262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1230262801Sdim __get_db()->__insert_c(this); 1231262801Sdim __get_db()->swap(this, &__u); 1232262801Sdim#endif 1233227825Stheraven} 1234227825Stheraven 1235227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1236227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1237227825Stheraven unordered_multiset&& __u, const allocator_type& __a) 1238227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 1239227825Stheraven{ 1240262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1241262801Sdim __get_db()->__insert_c(this); 1242262801Sdim#endif 1243227825Stheraven if (__a != __u.get_allocator()) 1244227825Stheraven { 1245227825Stheraven iterator __i = __u.begin(); 1246227825Stheraven while (__u.size() != 0) 1247227825Stheraven __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 1248227825Stheraven } 1249262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1250262801Sdim else 1251262801Sdim __get_db()->swap(this, &__u); 1252262801Sdim#endif 1253227825Stheraven} 1254227825Stheraven 1255227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1256227825Stheraven 1257227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1258227825Stheraven 1259227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1260227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1261227825Stheraven initializer_list<value_type> __il) 1262227825Stheraven{ 1263262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1264262801Sdim __get_db()->__insert_c(this); 1265262801Sdim#endif 1266227825Stheraven insert(__il.begin(), __il.end()); 1267227825Stheraven} 1268227825Stheraven 1269227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1270227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1271227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1272227825Stheraven const key_equal& __eql) 1273227825Stheraven : __table_(__hf, __eql) 1274227825Stheraven{ 1275262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1276262801Sdim __get_db()->__insert_c(this); 1277262801Sdim#endif 1278227825Stheraven __table_.rehash(__n); 1279227825Stheraven insert(__il.begin(), __il.end()); 1280227825Stheraven} 1281227825Stheraven 1282227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1283227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1284227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1285227825Stheraven const key_equal& __eql, const allocator_type& __a) 1286227825Stheraven : __table_(__hf, __eql, __a) 1287227825Stheraven{ 1288262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1289262801Sdim __get_db()->__insert_c(this); 1290262801Sdim#endif 1291227825Stheraven __table_.rehash(__n); 1292227825Stheraven insert(__il.begin(), __il.end()); 1293227825Stheraven} 1294227825Stheraven 1295227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1296227825Stheraven 1297227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1298227825Stheraven 1299227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1300227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1301227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1302227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1303227825Stheraven unordered_multiset&& __u) 1304227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1305227825Stheraven{ 1306227825Stheraven __table_ = _VSTD::move(__u.__table_); 1307227825Stheraven return *this; 1308227825Stheraven} 1309227825Stheraven 1310227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1311227825Stheraven 1312227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1313227825Stheraven 1314227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1315227825Stheraveninline 1316227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1317227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1318227825Stheraven initializer_list<value_type> __il) 1319227825Stheraven{ 1320227825Stheraven __table_.__assign_multi(__il.begin(), __il.end()); 1321227825Stheraven return *this; 1322227825Stheraven} 1323227825Stheraven 1324227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1325227825Stheraven 1326227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1327227825Stheraventemplate <class _InputIterator> 1328227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1329227825Stheravenvoid 1330227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1331227825Stheraven _InputIterator __last) 1332227825Stheraven{ 1333227825Stheraven for (; __first != __last; ++__first) 1334227825Stheraven __table_.__insert_multi(*__first); 1335227825Stheraven} 1336227825Stheraven 1337227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1338227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1339227825Stheravenvoid 1340227825Stheravenswap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1341227825Stheraven unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1342227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1343227825Stheraven{ 1344227825Stheraven __x.swap(__y); 1345227825Stheraven} 1346227825Stheraven 1347227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1348227825Stheravenbool 1349227825Stheravenoperator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1350227825Stheraven const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1351227825Stheraven{ 1352227825Stheraven if (__x.size() != __y.size()) 1353227825Stheraven return false; 1354227825Stheraven typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 1355227825Stheraven const_iterator; 1356227825Stheraven typedef pair<const_iterator, const_iterator> _EqRng; 1357227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 1358227825Stheraven { 1359227825Stheraven _EqRng __xeq = __x.equal_range(*__i); 1360227825Stheraven _EqRng __yeq = __y.equal_range(*__i); 1361227825Stheraven if (_VSTD::distance(__xeq.first, __xeq.second) != 1362227825Stheraven _VSTD::distance(__yeq.first, __yeq.second) || 1363227825Stheraven !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1364227825Stheraven return false; 1365227825Stheraven __i = __xeq.second; 1366227825Stheraven } 1367227825Stheraven return true; 1368227825Stheraven} 1369227825Stheraven 1370227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1371227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1372227825Stheravenbool 1373227825Stheravenoperator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1374227825Stheraven const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1375227825Stheraven{ 1376227825Stheraven return !(__x == __y); 1377227825Stheraven} 1378227825Stheraven 1379227825Stheraven_LIBCPP_END_NAMESPACE_STD 1380227825Stheraven 1381227825Stheraven#endif // _LIBCPP_UNORDERED_SET 1382