unordered_set revision 227825
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()); 71227825Stheraven ~unordered_set(); 72227825Stheraven unordered_set& operator=(const unordered_set&); 73227825Stheraven unordered_set& operator=(unordered_set&&) 74227825Stheraven noexcept( 75227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 76227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 77227825Stheraven is_nothrow_move_assignable<hasher>::value && 78227825Stheraven is_nothrow_move_assignable<key_equal>::value); 79227825Stheraven unordered_set& operator=(initializer_list<value_type>); 80227825Stheraven 81227825Stheraven allocator_type get_allocator() const noexcept; 82227825Stheraven 83227825Stheraven bool empty() const noexcept; 84227825Stheraven size_type size() const noexcept; 85227825Stheraven size_type max_size() const noexcept; 86227825Stheraven 87227825Stheraven iterator begin() noexcept; 88227825Stheraven iterator end() noexcept; 89227825Stheraven const_iterator begin() const noexcept; 90227825Stheraven const_iterator end() const noexcept; 91227825Stheraven const_iterator cbegin() const noexcept; 92227825Stheraven const_iterator cend() const noexcept; 93227825Stheraven 94227825Stheraven template <class... Args> 95227825Stheraven pair<iterator, bool> emplace(Args&&... args); 96227825Stheraven template <class... Args> 97227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 98227825Stheraven pair<iterator, bool> insert(const value_type& obj); 99227825Stheraven pair<iterator, bool> insert(value_type&& obj); 100227825Stheraven iterator insert(const_iterator hint, const value_type& obj); 101227825Stheraven iterator insert(const_iterator hint, value_type&& obj); 102227825Stheraven template <class InputIterator> 103227825Stheraven void insert(InputIterator first, InputIterator last); 104227825Stheraven void insert(initializer_list<value_type>); 105227825Stheraven 106227825Stheraven iterator erase(const_iterator position); 107227825Stheraven size_type erase(const key_type& k); 108227825Stheraven iterator erase(const_iterator first, const_iterator last); 109227825Stheraven void clear() noexcept; 110227825Stheraven 111227825Stheraven void swap(unordered_set&) 112227825Stheraven noexcept( 113227825Stheraven (!allocator_type::propagate_on_container_swap::value || 114227825Stheraven __is_nothrow_swappable<allocator_type>::value) && 115227825Stheraven __is_nothrow_swappable<hasher>::value && 116227825Stheraven __is_nothrow_swappable<key_equal>::value); 117227825Stheraven 118227825Stheraven hasher hash_function() const; 119227825Stheraven key_equal key_eq() const; 120227825Stheraven 121227825Stheraven iterator find(const key_type& k); 122227825Stheraven const_iterator find(const key_type& k) const; 123227825Stheraven size_type count(const key_type& k) const; 124227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 125227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 126227825Stheraven 127227825Stheraven size_type bucket_count() const noexcept; 128227825Stheraven size_type max_bucket_count() const noexcept; 129227825Stheraven 130227825Stheraven size_type bucket_size(size_type n) const; 131227825Stheraven size_type bucket(const key_type& k) const; 132227825Stheraven 133227825Stheraven local_iterator begin(size_type n); 134227825Stheraven local_iterator end(size_type n); 135227825Stheraven const_local_iterator begin(size_type n) const; 136227825Stheraven const_local_iterator end(size_type n) const; 137227825Stheraven const_local_iterator cbegin(size_type n) const; 138227825Stheraven const_local_iterator cend(size_type n) const; 139227825Stheraven 140227825Stheraven float load_factor() const noexcept; 141227825Stheraven float max_load_factor() const noexcept; 142227825Stheraven void max_load_factor(float z); 143227825Stheraven void rehash(size_type n); 144227825Stheraven void reserve(size_type n); 145227825Stheraven}; 146227825Stheraven 147227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 148227825Stheraven void swap(unordered_set<Value, Hash, Pred, Alloc>& x, 149227825Stheraven unordered_set<Value, Hash, Pred, Alloc>& y) 150227825Stheraven noexcept(noexcept(x.swap(y))); 151227825Stheraven 152227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 153227825Stheraven bool 154227825Stheraven operator==(const unordered_set<Value, Hash, Pred, Alloc>& x, 155227825Stheraven const unordered_set<Value, Hash, Pred, Alloc>& y); 156227825Stheraven 157227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 158227825Stheraven bool 159227825Stheraven operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x, 160227825Stheraven const unordered_set<Value, Hash, Pred, Alloc>& y); 161227825Stheraven 162227825Stheraventemplate <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 163227825Stheraven class Alloc = allocator<Value>> 164227825Stheravenclass unordered_multiset 165227825Stheraven{ 166227825Stheravenpublic: 167227825Stheraven // types 168227825Stheraven typedef Value key_type; 169227825Stheraven typedef key_type value_type; 170227825Stheraven typedef Hash hasher; 171227825Stheraven typedef Pred key_equal; 172227825Stheraven typedef Alloc allocator_type; 173227825Stheraven typedef value_type& reference; 174227825Stheraven typedef const value_type& const_reference; 175227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 176227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 177227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 178227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 179227825Stheraven 180227825Stheraven typedef /unspecified/ iterator; 181227825Stheraven typedef /unspecified/ const_iterator; 182227825Stheraven typedef /unspecified/ local_iterator; 183227825Stheraven typedef /unspecified/ const_local_iterator; 184227825Stheraven 185227825Stheraven unordered_multiset() 186227825Stheraven noexcept( 187227825Stheraven is_nothrow_default_constructible<hasher>::value && 188227825Stheraven is_nothrow_default_constructible<key_equal>::value && 189227825Stheraven is_nothrow_default_constructible<allocator_type>::value); 190227825Stheraven explicit unordered_multiset(size_type n, const hasher& hf = hasher(), 191227825Stheraven const key_equal& eql = key_equal(), 192227825Stheraven const allocator_type& a = allocator_type()); 193227825Stheraven template <class InputIterator> 194227825Stheraven unordered_multiset(InputIterator f, InputIterator l, 195227825Stheraven size_type n = 0, const hasher& hf = hasher(), 196227825Stheraven const key_equal& eql = key_equal(), 197227825Stheraven const allocator_type& a = allocator_type()); 198227825Stheraven explicit unordered_multiset(const allocator_type&); 199227825Stheraven unordered_multiset(const unordered_multiset&); 200227825Stheraven unordered_multiset(const unordered_multiset&, const Allocator&); 201227825Stheraven unordered_multiset(unordered_multiset&&) 202227825Stheraven noexcept( 203227825Stheraven is_nothrow_move_constructible<hasher>::value && 204227825Stheraven is_nothrow_move_constructible<key_equal>::value && 205227825Stheraven is_nothrow_move_constructible<allocator_type>::value); 206227825Stheraven unordered_multiset(unordered_multiset&&, const Allocator&); 207227825Stheraven unordered_multiset(initializer_list<value_type>, size_type n = /see below/, 208227825Stheraven const hasher& hf = hasher(), const key_equal& eql = key_equal(), 209227825Stheraven const allocator_type& a = allocator_type()); 210227825Stheraven ~unordered_multiset(); 211227825Stheraven unordered_multiset& operator=(const unordered_multiset&); 212227825Stheraven unordered_multiset& operator=(unordered_multiset&&) 213227825Stheraven noexcept( 214227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 215227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 216227825Stheraven is_nothrow_move_assignable<hasher>::value && 217227825Stheraven is_nothrow_move_assignable<key_equal>::value); 218227825Stheraven unordered_multiset& operator=(initializer_list<value_type>); 219227825Stheraven 220227825Stheraven allocator_type get_allocator() const noexcept; 221227825Stheraven 222227825Stheraven bool empty() const noexcept; 223227825Stheraven size_type size() const noexcept; 224227825Stheraven size_type max_size() const noexcept; 225227825Stheraven 226227825Stheraven iterator begin() noexcept; 227227825Stheraven iterator end() noexcept; 228227825Stheraven const_iterator begin() const noexcept; 229227825Stheraven const_iterator end() const noexcept; 230227825Stheraven const_iterator cbegin() const noexcept; 231227825Stheraven const_iterator cend() const noexcept; 232227825Stheraven 233227825Stheraven template <class... Args> 234227825Stheraven iterator emplace(Args&&... args); 235227825Stheraven template <class... Args> 236227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 237227825Stheraven iterator insert(const value_type& obj); 238227825Stheraven iterator insert(value_type&& obj); 239227825Stheraven iterator insert(const_iterator hint, const value_type& obj); 240227825Stheraven iterator insert(const_iterator hint, value_type&& obj); 241227825Stheraven template <class InputIterator> 242227825Stheraven void insert(InputIterator first, InputIterator last); 243227825Stheraven void insert(initializer_list<value_type>); 244227825Stheraven 245227825Stheraven iterator erase(const_iterator position); 246227825Stheraven size_type erase(const key_type& k); 247227825Stheraven iterator erase(const_iterator first, const_iterator last); 248227825Stheraven void clear() noexcept; 249227825Stheraven 250227825Stheraven void swap(unordered_multiset&) 251227825Stheraven noexcept( 252227825Stheraven (!allocator_type::propagate_on_container_swap::value || 253227825Stheraven __is_nothrow_swappable<allocator_type>::value) && 254227825Stheraven __is_nothrow_swappable<hasher>::value && 255227825Stheraven __is_nothrow_swappable<key_equal>::value); 256227825Stheraven 257227825Stheraven hasher hash_function() const; 258227825Stheraven key_equal key_eq() const; 259227825Stheraven 260227825Stheraven iterator find(const key_type& k); 261227825Stheraven const_iterator find(const key_type& k) const; 262227825Stheraven size_type count(const key_type& k) const; 263227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 264227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 265227825Stheraven 266227825Stheraven size_type bucket_count() const noexcept; 267227825Stheraven size_type max_bucket_count() const noexcept; 268227825Stheraven 269227825Stheraven size_type bucket_size(size_type n) const; 270227825Stheraven size_type bucket(const key_type& k) const; 271227825Stheraven 272227825Stheraven local_iterator begin(size_type n); 273227825Stheraven local_iterator end(size_type n); 274227825Stheraven const_local_iterator begin(size_type n) const; 275227825Stheraven const_local_iterator end(size_type n) const; 276227825Stheraven const_local_iterator cbegin(size_type n) const; 277227825Stheraven const_local_iterator cend(size_type n) const; 278227825Stheraven 279227825Stheraven float load_factor() const noexcept; 280227825Stheraven float max_load_factor() const noexcept; 281227825Stheraven void max_load_factor(float z); 282227825Stheraven void rehash(size_type n); 283227825Stheraven void reserve(size_type n); 284227825Stheraven}; 285227825Stheraven 286227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 287227825Stheraven void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x, 288227825Stheraven unordered_multiset<Value, Hash, Pred, Alloc>& y) 289227825Stheraven noexcept(noexcept(x.swap(y))); 290227825Stheraven 291227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 292227825Stheraven bool 293227825Stheraven operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 294227825Stheraven const unordered_multiset<Value, Hash, Pred, Alloc>& y); 295227825Stheraven 296227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 297227825Stheraven bool 298227825Stheraven operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 299227825Stheraven const unordered_multiset<Value, Hash, Pred, Alloc>& y); 300227825Stheraven} // std 301227825Stheraven 302227825Stheraven*/ 303227825Stheraven 304227825Stheraven#include <__config> 305227825Stheraven#include <__hash_table> 306227825Stheraven#include <functional> 307227825Stheraven 308227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 309227825Stheraven#pragma GCC system_header 310227825Stheraven#endif 311227825Stheraven 312227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 313227825Stheraven 314227825Stheraventemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 315227825Stheraven class _Alloc = allocator<_Value> > 316227825Stheravenclass _LIBCPP_VISIBLE unordered_set 317227825Stheraven{ 318227825Stheravenpublic: 319227825Stheraven // types 320227825Stheraven typedef _Value key_type; 321227825Stheraven typedef key_type value_type; 322227825Stheraven typedef _Hash hasher; 323227825Stheraven typedef _Pred key_equal; 324227825Stheraven typedef _Alloc allocator_type; 325227825Stheraven typedef value_type& reference; 326227825Stheraven typedef const value_type& const_reference; 327227825Stheraven 328227825Stheravenprivate: 329227825Stheraven typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 330227825Stheraven 331227825Stheraven __table __table_; 332227825Stheraven 333227825Stheravenpublic: 334227825Stheraven typedef typename __table::pointer pointer; 335227825Stheraven typedef typename __table::const_pointer const_pointer; 336227825Stheraven typedef typename __table::size_type size_type; 337227825Stheraven typedef typename __table::difference_type difference_type; 338227825Stheraven 339227825Stheraven typedef typename __table::const_iterator iterator; 340227825Stheraven typedef typename __table::const_iterator const_iterator; 341227825Stheraven typedef typename __table::const_local_iterator local_iterator; 342227825Stheraven typedef typename __table::const_local_iterator const_local_iterator; 343227825Stheraven 344227825Stheraven _LIBCPP_INLINE_VISIBILITY 345227825Stheraven unordered_set() 346227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 347227825Stheraven {} // = default; 348227825Stheraven explicit unordered_set(size_type __n, const hasher& __hf = hasher(), 349227825Stheraven const key_equal& __eql = key_equal()); 350227825Stheraven unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, 351227825Stheraven const allocator_type& __a); 352227825Stheraven template <class _InputIterator> 353227825Stheraven unordered_set(_InputIterator __first, _InputIterator __last); 354227825Stheraven template <class _InputIterator> 355227825Stheraven unordered_set(_InputIterator __first, _InputIterator __last, 356227825Stheraven size_type __n, const hasher& __hf = hasher(), 357227825Stheraven const key_equal& __eql = key_equal()); 358227825Stheraven template <class _InputIterator> 359227825Stheraven unordered_set(_InputIterator __first, _InputIterator __last, 360227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 361227825Stheraven const allocator_type& __a); 362227825Stheraven explicit unordered_set(const allocator_type& __a); 363227825Stheraven unordered_set(const unordered_set& __u); 364227825Stheraven unordered_set(const unordered_set& __u, const allocator_type& __a); 365227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 366227825Stheraven unordered_set(unordered_set&& __u) 367227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 368227825Stheraven unordered_set(unordered_set&& __u, const allocator_type& __a); 369227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 370227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 371227825Stheraven unordered_set(initializer_list<value_type> __il); 372227825Stheraven unordered_set(initializer_list<value_type> __il, size_type __n, 373227825Stheraven const hasher& __hf = hasher(), 374227825Stheraven const key_equal& __eql = key_equal()); 375227825Stheraven unordered_set(initializer_list<value_type> __il, size_type __n, 376227825Stheraven const hasher& __hf, const key_equal& __eql, 377227825Stheraven const allocator_type& __a); 378227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 379227825Stheraven // ~unordered_set() = default; 380227825Stheraven _LIBCPP_INLINE_VISIBILITY 381227825Stheraven unordered_set& operator=(const unordered_set& __u) 382227825Stheraven { 383227825Stheraven __table_ = __u.__table_; 384227825Stheraven return *this; 385227825Stheraven } 386227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 387227825Stheraven unordered_set& operator=(unordered_set&& __u) 388227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 389227825Stheraven#endif 390227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 391227825Stheraven unordered_set& operator=(initializer_list<value_type> __il); 392227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 393227825Stheraven 394227825Stheraven _LIBCPP_INLINE_VISIBILITY 395227825Stheraven allocator_type get_allocator() const _NOEXCEPT 396227825Stheraven {return allocator_type(__table_.__node_alloc());} 397227825Stheraven 398227825Stheraven _LIBCPP_INLINE_VISIBILITY 399227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 400227825Stheraven _LIBCPP_INLINE_VISIBILITY 401227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 402227825Stheraven _LIBCPP_INLINE_VISIBILITY 403227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 404227825Stheraven 405227825Stheraven _LIBCPP_INLINE_VISIBILITY 406227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 407227825Stheraven _LIBCPP_INLINE_VISIBILITY 408227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 409227825Stheraven _LIBCPP_INLINE_VISIBILITY 410227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 411227825Stheraven _LIBCPP_INLINE_VISIBILITY 412227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 413227825Stheraven _LIBCPP_INLINE_VISIBILITY 414227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 415227825Stheraven _LIBCPP_INLINE_VISIBILITY 416227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 417227825Stheraven 418227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 419227825Stheraven template <class... _Args> 420227825Stheraven _LIBCPP_INLINE_VISIBILITY 421227825Stheraven pair<iterator, bool> emplace(_Args&&... __args) 422227825Stheraven {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 423227825Stheraven template <class... _Args> 424227825Stheraven _LIBCPP_INLINE_VISIBILITY 425227825Stheraven iterator emplace_hint(const_iterator, _Args&&... __args) 426227825Stheraven {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;} 427227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 428227825Stheraven _LIBCPP_INLINE_VISIBILITY 429227825Stheraven pair<iterator, bool> insert(const value_type& __x) 430227825Stheraven {return __table_.__insert_unique(__x);} 431227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 432227825Stheraven _LIBCPP_INLINE_VISIBILITY 433227825Stheraven pair<iterator, bool> insert(value_type&& __x) 434227825Stheraven {return __table_.__insert_unique(_VSTD::move(__x));} 435227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 436227825Stheraven _LIBCPP_INLINE_VISIBILITY 437227825Stheraven iterator insert(const_iterator, const value_type& __x) 438227825Stheraven {return insert(__x).first;} 439227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 440227825Stheraven _LIBCPP_INLINE_VISIBILITY 441227825Stheraven iterator insert(const_iterator, value_type&& __x) 442227825Stheraven {return insert(_VSTD::move(__x)).first;} 443227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 444227825Stheraven template <class _InputIterator> 445227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 446227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 447227825Stheraven _LIBCPP_INLINE_VISIBILITY 448227825Stheraven void insert(initializer_list<value_type> __il) 449227825Stheraven {insert(__il.begin(), __il.end());} 450227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 451227825Stheraven 452227825Stheraven _LIBCPP_INLINE_VISIBILITY 453227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p);} 454227825Stheraven _LIBCPP_INLINE_VISIBILITY 455227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 456227825Stheraven _LIBCPP_INLINE_VISIBILITY 457227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 458227825Stheraven {return __table_.erase(__first, __last);} 459227825Stheraven _LIBCPP_INLINE_VISIBILITY 460227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 461227825Stheraven 462227825Stheraven _LIBCPP_INLINE_VISIBILITY 463227825Stheraven void swap(unordered_set& __u) 464227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 465227825Stheraven {__table_.swap(__u.__table_);} 466227825Stheraven 467227825Stheraven _LIBCPP_INLINE_VISIBILITY 468227825Stheraven hasher hash_function() const {return __table_.hash_function();} 469227825Stheraven _LIBCPP_INLINE_VISIBILITY 470227825Stheraven key_equal key_eq() const {return __table_.key_eq();} 471227825Stheraven 472227825Stheraven _LIBCPP_INLINE_VISIBILITY 473227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 474227825Stheraven _LIBCPP_INLINE_VISIBILITY 475227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 476227825Stheraven _LIBCPP_INLINE_VISIBILITY 477227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 478227825Stheraven _LIBCPP_INLINE_VISIBILITY 479227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 480227825Stheraven {return __table_.__equal_range_unique(__k);} 481227825Stheraven _LIBCPP_INLINE_VISIBILITY 482227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 483227825Stheraven {return __table_.__equal_range_unique(__k);} 484227825Stheraven 485227825Stheraven _LIBCPP_INLINE_VISIBILITY 486227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 487227825Stheraven _LIBCPP_INLINE_VISIBILITY 488227825Stheraven size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 489227825Stheraven 490227825Stheraven _LIBCPP_INLINE_VISIBILITY 491227825Stheraven size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 492227825Stheraven _LIBCPP_INLINE_VISIBILITY 493227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 494227825Stheraven 495227825Stheraven _LIBCPP_INLINE_VISIBILITY 496227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 497227825Stheraven _LIBCPP_INLINE_VISIBILITY 498227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 499227825Stheraven _LIBCPP_INLINE_VISIBILITY 500227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 501227825Stheraven _LIBCPP_INLINE_VISIBILITY 502227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 503227825Stheraven _LIBCPP_INLINE_VISIBILITY 504227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 505227825Stheraven _LIBCPP_INLINE_VISIBILITY 506227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 507227825Stheraven 508227825Stheraven _LIBCPP_INLINE_VISIBILITY 509227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 510227825Stheraven _LIBCPP_INLINE_VISIBILITY 511227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 512227825Stheraven _LIBCPP_INLINE_VISIBILITY 513227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 514227825Stheraven _LIBCPP_INLINE_VISIBILITY 515227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 516227825Stheraven _LIBCPP_INLINE_VISIBILITY 517227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 518227825Stheraven}; 519227825Stheraven 520227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 521227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 522227825Stheraven const hasher& __hf, const key_equal& __eql) 523227825Stheraven : __table_(__hf, __eql) 524227825Stheraven{ 525227825Stheraven __table_.rehash(__n); 526227825Stheraven} 527227825Stheraven 528227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 529227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 530227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 531227825Stheraven : __table_(__hf, __eql, __a) 532227825Stheraven{ 533227825Stheraven __table_.rehash(__n); 534227825Stheraven} 535227825Stheraven 536227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 537227825Stheraventemplate <class _InputIterator> 538227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 539227825Stheraven _InputIterator __first, _InputIterator __last) 540227825Stheraven{ 541227825Stheraven insert(__first, __last); 542227825Stheraven} 543227825Stheraven 544227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 545227825Stheraventemplate <class _InputIterator> 546227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 547227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 548227825Stheraven const hasher& __hf, const key_equal& __eql) 549227825Stheraven : __table_(__hf, __eql) 550227825Stheraven{ 551227825Stheraven __table_.rehash(__n); 552227825Stheraven insert(__first, __last); 553227825Stheraven} 554227825Stheraven 555227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 556227825Stheraventemplate <class _InputIterator> 557227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 558227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 559227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 560227825Stheraven : __table_(__hf, __eql, __a) 561227825Stheraven{ 562227825Stheraven __table_.rehash(__n); 563227825Stheraven insert(__first, __last); 564227825Stheraven} 565227825Stheraven 566227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 567227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 568227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 569227825Stheraven const allocator_type& __a) 570227825Stheraven : __table_(__a) 571227825Stheraven{ 572227825Stheraven} 573227825Stheraven 574227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 575227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 576227825Stheraven const unordered_set& __u) 577227825Stheraven : __table_(__u.__table_) 578227825Stheraven{ 579227825Stheraven __table_.rehash(__u.bucket_count()); 580227825Stheraven insert(__u.begin(), __u.end()); 581227825Stheraven} 582227825Stheraven 583227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 584227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 585227825Stheraven const unordered_set& __u, const allocator_type& __a) 586227825Stheraven : __table_(__u.__table_, __a) 587227825Stheraven{ 588227825Stheraven __table_.rehash(__u.bucket_count()); 589227825Stheraven insert(__u.begin(), __u.end()); 590227825Stheraven} 591227825Stheraven 592227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 593227825Stheraven 594227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 595227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 596227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 597227825Stheraven unordered_set&& __u) 598227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 599227825Stheraven : __table_(_VSTD::move(__u.__table_)) 600227825Stheraven{ 601227825Stheraven} 602227825Stheraven 603227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 604227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 605227825Stheraven unordered_set&& __u, const allocator_type& __a) 606227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 607227825Stheraven{ 608227825Stheraven if (__a != __u.get_allocator()) 609227825Stheraven { 610227825Stheraven iterator __i = __u.begin(); 611227825Stheraven while (__u.size() != 0) 612227825Stheraven __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 613227825Stheraven } 614227825Stheraven} 615227825Stheraven 616227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 617227825Stheraven 618227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 619227825Stheraven 620227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 621227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 622227825Stheraven initializer_list<value_type> __il) 623227825Stheraven{ 624227825Stheraven insert(__il.begin(), __il.end()); 625227825Stheraven} 626227825Stheraven 627227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 628227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 629227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 630227825Stheraven const key_equal& __eql) 631227825Stheraven : __table_(__hf, __eql) 632227825Stheraven{ 633227825Stheraven __table_.rehash(__n); 634227825Stheraven insert(__il.begin(), __il.end()); 635227825Stheraven} 636227825Stheraven 637227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 638227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 639227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 640227825Stheraven const key_equal& __eql, const allocator_type& __a) 641227825Stheraven : __table_(__hf, __eql, __a) 642227825Stheraven{ 643227825Stheraven __table_.rehash(__n); 644227825Stheraven insert(__il.begin(), __il.end()); 645227825Stheraven} 646227825Stheraven 647227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 648227825Stheraven 649227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 650227825Stheraven 651227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 652227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 653227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>& 654227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 655227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 656227825Stheraven{ 657227825Stheraven __table_ = _VSTD::move(__u.__table_); 658227825Stheraven return *this; 659227825Stheraven} 660227825Stheraven 661227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 662227825Stheraven 663227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 664227825Stheraven 665227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 666227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 667227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>& 668227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::operator=( 669227825Stheraven initializer_list<value_type> __il) 670227825Stheraven{ 671227825Stheraven __table_.__assign_unique(__il.begin(), __il.end()); 672227825Stheraven return *this; 673227825Stheraven} 674227825Stheraven 675227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 676227825Stheraven 677227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 678227825Stheraventemplate <class _InputIterator> 679227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 680227825Stheravenvoid 681227825Stheravenunordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 682227825Stheraven _InputIterator __last) 683227825Stheraven{ 684227825Stheraven for (; __first != __last; ++__first) 685227825Stheraven __table_.__insert_unique(*__first); 686227825Stheraven} 687227825Stheraven 688227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 689227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 690227825Stheravenvoid 691227825Stheravenswap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 692227825Stheraven unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 693227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 694227825Stheraven{ 695227825Stheraven __x.swap(__y); 696227825Stheraven} 697227825Stheraven 698227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 699227825Stheravenbool 700227825Stheravenoperator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 701227825Stheraven const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 702227825Stheraven{ 703227825Stheraven if (__x.size() != __y.size()) 704227825Stheraven return false; 705227825Stheraven typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 706227825Stheraven const_iterator; 707227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 708227825Stheraven __i != __ex; ++__i) 709227825Stheraven { 710227825Stheraven const_iterator __j = __y.find(*__i); 711227825Stheraven if (__j == __ey || !(*__i == *__j)) 712227825Stheraven return false; 713227825Stheraven } 714227825Stheraven return true; 715227825Stheraven} 716227825Stheraven 717227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 718227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 719227825Stheravenbool 720227825Stheravenoperator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 721227825Stheraven const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 722227825Stheraven{ 723227825Stheraven return !(__x == __y); 724227825Stheraven} 725227825Stheraven 726227825Stheraventemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 727227825Stheraven class _Alloc = allocator<_Value> > 728227825Stheravenclass _LIBCPP_VISIBLE unordered_multiset 729227825Stheraven{ 730227825Stheravenpublic: 731227825Stheraven // types 732227825Stheraven typedef _Value key_type; 733227825Stheraven typedef key_type value_type; 734227825Stheraven typedef _Hash hasher; 735227825Stheraven typedef _Pred key_equal; 736227825Stheraven typedef _Alloc allocator_type; 737227825Stheraven typedef value_type& reference; 738227825Stheraven typedef const value_type& const_reference; 739227825Stheraven 740227825Stheravenprivate: 741227825Stheraven typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 742227825Stheraven 743227825Stheraven __table __table_; 744227825Stheraven 745227825Stheravenpublic: 746227825Stheraven typedef typename __table::pointer pointer; 747227825Stheraven typedef typename __table::const_pointer const_pointer; 748227825Stheraven typedef typename __table::size_type size_type; 749227825Stheraven typedef typename __table::difference_type difference_type; 750227825Stheraven 751227825Stheraven typedef typename __table::const_iterator iterator; 752227825Stheraven typedef typename __table::const_iterator const_iterator; 753227825Stheraven typedef typename __table::const_local_iterator local_iterator; 754227825Stheraven typedef typename __table::const_local_iterator const_local_iterator; 755227825Stheraven 756227825Stheraven _LIBCPP_INLINE_VISIBILITY 757227825Stheraven unordered_multiset() 758227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 759227825Stheraven {} // = default 760227825Stheraven explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(), 761227825Stheraven const key_equal& __eql = key_equal()); 762227825Stheraven unordered_multiset(size_type __n, const hasher& __hf, 763227825Stheraven const key_equal& __eql, const allocator_type& __a); 764227825Stheraven template <class _InputIterator> 765227825Stheraven unordered_multiset(_InputIterator __first, _InputIterator __last); 766227825Stheraven template <class _InputIterator> 767227825Stheraven unordered_multiset(_InputIterator __first, _InputIterator __last, 768227825Stheraven size_type __n, const hasher& __hf = hasher(), 769227825Stheraven const key_equal& __eql = key_equal()); 770227825Stheraven template <class _InputIterator> 771227825Stheraven unordered_multiset(_InputIterator __first, _InputIterator __last, 772227825Stheraven size_type __n , const hasher& __hf, 773227825Stheraven const key_equal& __eql, const allocator_type& __a); 774227825Stheraven explicit unordered_multiset(const allocator_type& __a); 775227825Stheraven unordered_multiset(const unordered_multiset& __u); 776227825Stheraven unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 777227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 778227825Stheraven unordered_multiset(unordered_multiset&& __u) 779227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 780227825Stheraven unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 781227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 782227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 783227825Stheraven unordered_multiset(initializer_list<value_type> __il); 784227825Stheraven unordered_multiset(initializer_list<value_type> __il, size_type __n, 785227825Stheraven const hasher& __hf = hasher(), 786227825Stheraven const key_equal& __eql = key_equal()); 787227825Stheraven unordered_multiset(initializer_list<value_type> __il, size_type __n, 788227825Stheraven const hasher& __hf, const key_equal& __eql, 789227825Stheraven const allocator_type& __a); 790227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 791227825Stheraven // ~unordered_multiset() = default; 792227825Stheraven _LIBCPP_INLINE_VISIBILITY 793227825Stheraven unordered_multiset& operator=(const unordered_multiset& __u) 794227825Stheraven { 795227825Stheraven __table_ = __u.__table_; 796227825Stheraven return *this; 797227825Stheraven } 798227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 799227825Stheraven unordered_multiset& operator=(unordered_multiset&& __u) 800227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 801227825Stheraven#endif 802227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 803227825Stheraven unordered_multiset& operator=(initializer_list<value_type> __il); 804227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 805227825Stheraven 806227825Stheraven _LIBCPP_INLINE_VISIBILITY 807227825Stheraven allocator_type get_allocator() const _NOEXCEPT 808227825Stheraven {return allocator_type(__table_.__node_alloc());} 809227825Stheraven 810227825Stheraven _LIBCPP_INLINE_VISIBILITY 811227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 812227825Stheraven _LIBCPP_INLINE_VISIBILITY 813227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 814227825Stheraven _LIBCPP_INLINE_VISIBILITY 815227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 816227825Stheraven 817227825Stheraven _LIBCPP_INLINE_VISIBILITY 818227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 819227825Stheraven _LIBCPP_INLINE_VISIBILITY 820227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 821227825Stheraven _LIBCPP_INLINE_VISIBILITY 822227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 823227825Stheraven _LIBCPP_INLINE_VISIBILITY 824227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 825227825Stheraven _LIBCPP_INLINE_VISIBILITY 826227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 827227825Stheraven _LIBCPP_INLINE_VISIBILITY 828227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 829227825Stheraven 830227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 831227825Stheraven template <class... _Args> 832227825Stheraven _LIBCPP_INLINE_VISIBILITY 833227825Stheraven iterator emplace(_Args&&... __args) 834227825Stheraven {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 835227825Stheraven template <class... _Args> 836227825Stheraven _LIBCPP_INLINE_VISIBILITY 837227825Stheraven iterator emplace_hint(const_iterator __p, _Args&&... __args) 838227825Stheraven {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 839227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 840227825Stheraven _LIBCPP_INLINE_VISIBILITY 841227825Stheraven iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 842227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 843227825Stheraven _LIBCPP_INLINE_VISIBILITY 844227825Stheraven iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} 845227825Stheraven#endif 846227825Stheraven _LIBCPP_INLINE_VISIBILITY 847227825Stheraven iterator insert(const_iterator __p, const value_type& __x) 848227825Stheraven {return __table_.__insert_multi(__p, __x);} 849227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 850227825Stheraven _LIBCPP_INLINE_VISIBILITY 851227825Stheraven iterator insert(const_iterator __p, value_type&& __x) 852227825Stheraven {return __table_.__insert_multi(__p, _VSTD::move(__x));} 853227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 854227825Stheraven template <class _InputIterator> 855227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 856227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 857227825Stheraven _LIBCPP_INLINE_VISIBILITY 858227825Stheraven void insert(initializer_list<value_type> __il) 859227825Stheraven {insert(__il.begin(), __il.end());} 860227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 861227825Stheraven 862227825Stheraven _LIBCPP_INLINE_VISIBILITY 863227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p);} 864227825Stheraven _LIBCPP_INLINE_VISIBILITY 865227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 866227825Stheraven _LIBCPP_INLINE_VISIBILITY 867227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 868227825Stheraven {return __table_.erase(__first, __last);} 869227825Stheraven _LIBCPP_INLINE_VISIBILITY 870227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 871227825Stheraven 872227825Stheraven _LIBCPP_INLINE_VISIBILITY 873227825Stheraven void swap(unordered_multiset& __u) 874227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 875227825Stheraven {__table_.swap(__u.__table_);} 876227825Stheraven 877227825Stheraven _LIBCPP_INLINE_VISIBILITY 878227825Stheraven hasher hash_function() const {return __table_.hash_function();} 879227825Stheraven _LIBCPP_INLINE_VISIBILITY 880227825Stheraven key_equal key_eq() const {return __table_.key_eq();} 881227825Stheraven 882227825Stheraven _LIBCPP_INLINE_VISIBILITY 883227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 884227825Stheraven _LIBCPP_INLINE_VISIBILITY 885227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 886227825Stheraven _LIBCPP_INLINE_VISIBILITY 887227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 888227825Stheraven _LIBCPP_INLINE_VISIBILITY 889227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 890227825Stheraven {return __table_.__equal_range_multi(__k);} 891227825Stheraven _LIBCPP_INLINE_VISIBILITY 892227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 893227825Stheraven {return __table_.__equal_range_multi(__k);} 894227825Stheraven 895227825Stheraven _LIBCPP_INLINE_VISIBILITY 896227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 897227825Stheraven _LIBCPP_INLINE_VISIBILITY 898227825Stheraven size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 899227825Stheraven 900227825Stheraven _LIBCPP_INLINE_VISIBILITY 901227825Stheraven size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 902227825Stheraven _LIBCPP_INLINE_VISIBILITY 903227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 904227825Stheraven 905227825Stheraven _LIBCPP_INLINE_VISIBILITY 906227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 907227825Stheraven _LIBCPP_INLINE_VISIBILITY 908227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 909227825Stheraven _LIBCPP_INLINE_VISIBILITY 910227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 911227825Stheraven _LIBCPP_INLINE_VISIBILITY 912227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 913227825Stheraven _LIBCPP_INLINE_VISIBILITY 914227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 915227825Stheraven _LIBCPP_INLINE_VISIBILITY 916227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 917227825Stheraven 918227825Stheraven _LIBCPP_INLINE_VISIBILITY 919227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 920227825Stheraven _LIBCPP_INLINE_VISIBILITY 921227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 922227825Stheraven _LIBCPP_INLINE_VISIBILITY 923227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 924227825Stheraven _LIBCPP_INLINE_VISIBILITY 925227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 926227825Stheraven _LIBCPP_INLINE_VISIBILITY 927227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 928227825Stheraven}; 929227825Stheraven 930227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 931227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 932227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 933227825Stheraven : __table_(__hf, __eql) 934227825Stheraven{ 935227825Stheraven __table_.rehash(__n); 936227825Stheraven} 937227825Stheraven 938227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 939227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 940227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 941227825Stheraven const allocator_type& __a) 942227825Stheraven : __table_(__hf, __eql, __a) 943227825Stheraven{ 944227825Stheraven __table_.rehash(__n); 945227825Stheraven} 946227825Stheraven 947227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 948227825Stheraventemplate <class _InputIterator> 949227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 950227825Stheraven _InputIterator __first, _InputIterator __last) 951227825Stheraven{ 952227825Stheraven insert(__first, __last); 953227825Stheraven} 954227825Stheraven 955227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 956227825Stheraventemplate <class _InputIterator> 957227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 958227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 959227825Stheraven const hasher& __hf, const key_equal& __eql) 960227825Stheraven : __table_(__hf, __eql) 961227825Stheraven{ 962227825Stheraven __table_.rehash(__n); 963227825Stheraven insert(__first, __last); 964227825Stheraven} 965227825Stheraven 966227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 967227825Stheraventemplate <class _InputIterator> 968227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 969227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 970227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 971227825Stheraven : __table_(__hf, __eql, __a) 972227825Stheraven{ 973227825Stheraven __table_.rehash(__n); 974227825Stheraven insert(__first, __last); 975227825Stheraven} 976227825Stheraven 977227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 978227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 979227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 980227825Stheraven const allocator_type& __a) 981227825Stheraven : __table_(__a) 982227825Stheraven{ 983227825Stheraven} 984227825Stheraven 985227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 986227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 987227825Stheraven const unordered_multiset& __u) 988227825Stheraven : __table_(__u.__table_) 989227825Stheraven{ 990227825Stheraven __table_.rehash(__u.bucket_count()); 991227825Stheraven insert(__u.begin(), __u.end()); 992227825Stheraven} 993227825Stheraven 994227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 995227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 996227825Stheraven const unordered_multiset& __u, const allocator_type& __a) 997227825Stheraven : __table_(__u.__table_, __a) 998227825Stheraven{ 999227825Stheraven __table_.rehash(__u.bucket_count()); 1000227825Stheraven insert(__u.begin(), __u.end()); 1001227825Stheraven} 1002227825Stheraven 1003227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1004227825Stheraven 1005227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1006227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1007227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1008227825Stheraven unordered_multiset&& __u) 1009227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1010227825Stheraven : __table_(_VSTD::move(__u.__table_)) 1011227825Stheraven{ 1012227825Stheraven} 1013227825Stheraven 1014227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1015227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1016227825Stheraven unordered_multiset&& __u, const allocator_type& __a) 1017227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 1018227825Stheraven{ 1019227825Stheraven if (__a != __u.get_allocator()) 1020227825Stheraven { 1021227825Stheraven iterator __i = __u.begin(); 1022227825Stheraven while (__u.size() != 0) 1023227825Stheraven __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 1024227825Stheraven } 1025227825Stheraven} 1026227825Stheraven 1027227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1028227825Stheraven 1029227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1030227825Stheraven 1031227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1032227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1033227825Stheraven initializer_list<value_type> __il) 1034227825Stheraven{ 1035227825Stheraven insert(__il.begin(), __il.end()); 1036227825Stheraven} 1037227825Stheraven 1038227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1039227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1040227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1041227825Stheraven const key_equal& __eql) 1042227825Stheraven : __table_(__hf, __eql) 1043227825Stheraven{ 1044227825Stheraven __table_.rehash(__n); 1045227825Stheraven insert(__il.begin(), __il.end()); 1046227825Stheraven} 1047227825Stheraven 1048227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1049227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1050227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1051227825Stheraven const key_equal& __eql, const allocator_type& __a) 1052227825Stheraven : __table_(__hf, __eql, __a) 1053227825Stheraven{ 1054227825Stheraven __table_.rehash(__n); 1055227825Stheraven insert(__il.begin(), __il.end()); 1056227825Stheraven} 1057227825Stheraven 1058227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1059227825Stheraven 1060227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1061227825Stheraven 1062227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1063227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1064227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1065227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1066227825Stheraven unordered_multiset&& __u) 1067227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1068227825Stheraven{ 1069227825Stheraven __table_ = _VSTD::move(__u.__table_); 1070227825Stheraven return *this; 1071227825Stheraven} 1072227825Stheraven 1073227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1074227825Stheraven 1075227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1076227825Stheraven 1077227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1078227825Stheraveninline 1079227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1080227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1081227825Stheraven initializer_list<value_type> __il) 1082227825Stheraven{ 1083227825Stheraven __table_.__assign_multi(__il.begin(), __il.end()); 1084227825Stheraven return *this; 1085227825Stheraven} 1086227825Stheraven 1087227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1088227825Stheraven 1089227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1090227825Stheraventemplate <class _InputIterator> 1091227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1092227825Stheravenvoid 1093227825Stheravenunordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1094227825Stheraven _InputIterator __last) 1095227825Stheraven{ 1096227825Stheraven for (; __first != __last; ++__first) 1097227825Stheraven __table_.__insert_multi(*__first); 1098227825Stheraven} 1099227825Stheraven 1100227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1101227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1102227825Stheravenvoid 1103227825Stheravenswap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1104227825Stheraven unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1105227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1106227825Stheraven{ 1107227825Stheraven __x.swap(__y); 1108227825Stheraven} 1109227825Stheraven 1110227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1111227825Stheravenbool 1112227825Stheravenoperator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1113227825Stheraven const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1114227825Stheraven{ 1115227825Stheraven if (__x.size() != __y.size()) 1116227825Stheraven return false; 1117227825Stheraven typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 1118227825Stheraven const_iterator; 1119227825Stheraven typedef pair<const_iterator, const_iterator> _EqRng; 1120227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 1121227825Stheraven { 1122227825Stheraven _EqRng __xeq = __x.equal_range(*__i); 1123227825Stheraven _EqRng __yeq = __y.equal_range(*__i); 1124227825Stheraven if (_VSTD::distance(__xeq.first, __xeq.second) != 1125227825Stheraven _VSTD::distance(__yeq.first, __yeq.second) || 1126227825Stheraven !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1127227825Stheraven return false; 1128227825Stheraven __i = __xeq.second; 1129227825Stheraven } 1130227825Stheraven return true; 1131227825Stheraven} 1132227825Stheraven 1133227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1134227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1135227825Stheravenbool 1136227825Stheravenoperator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1137227825Stheraven const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1138227825Stheraven{ 1139227825Stheraven return !(__x == __y); 1140227825Stheraven} 1141227825Stheraven 1142227825Stheraven_LIBCPP_END_NAMESPACE_STD 1143227825Stheraven 1144227825Stheraven#endif // _LIBCPP_UNORDERED_SET 1145