hash_set revision 262801
1227825Stheraven// -*- C++ -*- 2227825Stheraven//===------------------------- hash_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_HASH_SET 12227825Stheraven#define _LIBCPP_HASH_SET 13227825Stheraven 14227825Stheraven/* 15227825Stheraven 16227825Stheraven hash_set synopsis 17227825Stheraven 18227825Stheravennamespace __gnu_cxx 19227825Stheraven{ 20227825Stheraven 21227825Stheraventemplate <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 22227825Stheraven class Alloc = allocator<Value>> 23227825Stheravenclass hash_set 24227825Stheraven{ 25227825Stheravenpublic: 26227825Stheraven // types 27227825Stheraven typedef Value key_type; 28227825Stheraven typedef key_type value_type; 29227825Stheraven typedef Hash hasher; 30227825Stheraven typedef Pred key_equal; 31227825Stheraven typedef Alloc allocator_type; 32227825Stheraven typedef value_type& reference; 33227825Stheraven typedef const value_type& const_reference; 34227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 35227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 36227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 37227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 38227825Stheraven 39227825Stheraven typedef /unspecified/ iterator; 40227825Stheraven typedef /unspecified/ const_iterator; 41227825Stheraven 42227825Stheraven explicit hash_set(size_type n = 193, const hasher& hf = hasher(), 43227825Stheraven const key_equal& eql = key_equal(), 44227825Stheraven const allocator_type& a = allocator_type()); 45227825Stheraven template <class InputIterator> 46227825Stheraven hash_set(InputIterator f, InputIterator l, 47227825Stheraven size_type n = 193, const hasher& hf = hasher(), 48227825Stheraven const key_equal& eql = key_equal(), 49227825Stheraven const allocator_type& a = allocator_type()); 50227825Stheraven hash_set(const hash_set&); 51227825Stheraven ~hash_set(); 52227825Stheraven hash_set& operator=(const hash_set&); 53227825Stheraven 54227825Stheraven allocator_type get_allocator() const; 55227825Stheraven 56227825Stheraven bool empty() const; 57227825Stheraven size_type size() const; 58227825Stheraven size_type max_size() const; 59227825Stheraven 60227825Stheraven iterator begin(); 61227825Stheraven iterator end(); 62227825Stheraven const_iterator begin() const; 63227825Stheraven const_iterator end() const; 64227825Stheraven 65227825Stheraven pair<iterator, bool> insert(const value_type& obj); 66227825Stheraven template <class InputIterator> 67227825Stheraven void insert(InputIterator first, InputIterator last); 68227825Stheraven 69227825Stheraven void erase(const_iterator position); 70227825Stheraven size_type erase(const key_type& k); 71227825Stheraven void erase(const_iterator first, const_iterator last); 72227825Stheraven void clear(); 73227825Stheraven 74227825Stheraven void swap(hash_set&); 75227825Stheraven 76227825Stheraven hasher hash_funct() const; 77227825Stheraven key_equal key_eq() const; 78227825Stheraven 79227825Stheraven iterator find(const key_type& k); 80227825Stheraven const_iterator find(const key_type& k) const; 81227825Stheraven size_type count(const key_type& k) const; 82227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 83227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 84227825Stheraven 85227825Stheraven size_type bucket_count() const; 86227825Stheraven size_type max_bucket_count() const; 87227825Stheraven 88227825Stheraven size_type elems_in_bucket(size_type n) const; 89227825Stheraven 90227825Stheraven void resize(size_type n); 91227825Stheraven}; 92227825Stheraven 93227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 94227825Stheraven void swap(hash_set<Value, Hash, Pred, Alloc>& x, 95227825Stheraven hash_set<Value, Hash, Pred, Alloc>& y); 96227825Stheraven 97227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 98227825Stheraven bool 99227825Stheraven operator==(const hash_set<Value, Hash, Pred, Alloc>& x, 100227825Stheraven const hash_set<Value, Hash, Pred, Alloc>& y); 101227825Stheraven 102227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 103227825Stheraven bool 104227825Stheraven operator!=(const hash_set<Value, Hash, Pred, Alloc>& x, 105227825Stheraven const hash_set<Value, Hash, Pred, Alloc>& y); 106227825Stheraven 107227825Stheraventemplate <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 108227825Stheraven class Alloc = allocator<Value>> 109227825Stheravenclass hash_multiset 110227825Stheraven{ 111227825Stheravenpublic: 112227825Stheraven // types 113227825Stheraven typedef Value key_type; 114227825Stheraven typedef key_type value_type; 115227825Stheraven typedef Hash hasher; 116227825Stheraven typedef Pred key_equal; 117227825Stheraven typedef Alloc allocator_type; 118227825Stheraven typedef value_type& reference; 119227825Stheraven typedef const value_type& const_reference; 120227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 121227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 122227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 123227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 124227825Stheraven 125227825Stheraven typedef /unspecified/ iterator; 126227825Stheraven typedef /unspecified/ const_iterator; 127227825Stheraven 128227825Stheraven explicit hash_multiset(size_type n = 193, const hasher& hf = hasher(), 129227825Stheraven const key_equal& eql = key_equal(), 130227825Stheraven const allocator_type& a = allocator_type()); 131227825Stheraven template <class InputIterator> 132227825Stheraven hash_multiset(InputIterator f, InputIterator l, 133227825Stheraven size_type n = 193, const hasher& hf = hasher(), 134227825Stheraven const key_equal& eql = key_equal(), 135227825Stheraven const allocator_type& a = allocator_type()); 136227825Stheraven hash_multiset(const hash_multiset&); 137227825Stheraven ~hash_multiset(); 138227825Stheraven hash_multiset& operator=(const hash_multiset&); 139227825Stheraven 140227825Stheraven allocator_type get_allocator() const; 141227825Stheraven 142227825Stheraven bool empty() const; 143227825Stheraven size_type size() const; 144227825Stheraven size_type max_size() const; 145227825Stheraven 146227825Stheraven iterator begin(); 147227825Stheraven iterator end(); 148227825Stheraven const_iterator begin() const; 149227825Stheraven const_iterator end() const; 150227825Stheraven 151227825Stheraven iterator insert(const value_type& obj); 152227825Stheraven template <class InputIterator> 153227825Stheraven void insert(InputIterator first, InputIterator last); 154227825Stheraven 155227825Stheraven void erase(const_iterator position); 156227825Stheraven size_type erase(const key_type& k); 157227825Stheraven void erase(const_iterator first, const_iterator last); 158227825Stheraven void clear(); 159227825Stheraven 160227825Stheraven void swap(hash_multiset&); 161227825Stheraven 162227825Stheraven hasher hash_funct() const; 163227825Stheraven key_equal key_eq() const; 164227825Stheraven 165227825Stheraven iterator find(const key_type& k); 166227825Stheraven const_iterator find(const key_type& k) const; 167227825Stheraven size_type count(const key_type& k) const; 168227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 169227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 170227825Stheraven 171227825Stheraven size_type bucket_count() const; 172227825Stheraven size_type max_bucket_count() const; 173227825Stheraven 174227825Stheraven size_type elems_in_bucket(size_type n) const; 175227825Stheraven 176227825Stheraven void resize(size_type n); 177227825Stheraven}; 178227825Stheraven 179227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 180227825Stheraven void swap(hash_multiset<Value, Hash, Pred, Alloc>& x, 181227825Stheraven hash_multiset<Value, Hash, Pred, Alloc>& y); 182227825Stheraven 183227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 184227825Stheraven bool 185227825Stheraven operator==(const hash_multiset<Value, Hash, Pred, Alloc>& x, 186227825Stheraven const hash_multiset<Value, Hash, Pred, Alloc>& y); 187227825Stheraven 188227825Stheraventemplate <class Value, class Hash, class Pred, class Alloc> 189227825Stheraven bool 190227825Stheraven operator!=(const hash_multiset<Value, Hash, Pred, Alloc>& x, 191227825Stheraven const hash_multiset<Value, Hash, Pred, Alloc>& y); 192227825Stheraven} // __gnu_cxx 193227825Stheraven 194227825Stheraven*/ 195227825Stheraven 196227825Stheraven#include <__config> 197227825Stheraven#include <__hash_table> 198227825Stheraven#include <functional> 199227825Stheraven#include <ext/__hash> 200227825Stheraven 201227825Stheraven#if __DEPRECATED 202262801Sdim#if defined(_MSC_VER) && ! defined(__clang__) 203262801Sdim _LIBCPP_WARNING("Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>") 204262801Sdim#else 205262801Sdim# warning Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set> 206227825Stheraven#endif 207262801Sdim#endif 208227825Stheraven 209227825Stheravennamespace __gnu_cxx { 210227825Stheraven 211227825Stheravenusing namespace std; 212227825Stheraven 213227825Stheraventemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 214227825Stheraven class _Alloc = allocator<_Value> > 215262801Sdimclass _LIBCPP_TYPE_VIS_ONLY hash_set 216227825Stheraven{ 217227825Stheravenpublic: 218227825Stheraven // types 219227825Stheraven typedef _Value key_type; 220227825Stheraven typedef key_type value_type; 221227825Stheraven typedef _Hash hasher; 222227825Stheraven typedef _Pred key_equal; 223227825Stheraven typedef _Alloc allocator_type; 224227825Stheraven typedef value_type& reference; 225227825Stheraven typedef const value_type& const_reference; 226227825Stheraven 227227825Stheravenprivate: 228227825Stheraven typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 229227825Stheraven 230227825Stheraven __table __table_; 231227825Stheraven 232227825Stheravenpublic: 233227825Stheraven typedef typename __table::pointer pointer; 234227825Stheraven typedef typename __table::const_pointer const_pointer; 235227825Stheraven typedef typename __table::size_type size_type; 236227825Stheraven typedef typename __table::difference_type difference_type; 237227825Stheraven 238227825Stheraven typedef typename __table::const_iterator iterator; 239227825Stheraven typedef typename __table::const_iterator const_iterator; 240227825Stheraven 241227825Stheraven _LIBCPP_INLINE_VISIBILITY 242227825Stheraven hash_set() {__table_.rehash(193);} 243227825Stheraven explicit hash_set(size_type __n, const hasher& __hf = hasher(), 244227825Stheraven const key_equal& __eql = key_equal()); 245227825Stheraven hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, 246227825Stheraven const allocator_type& __a); 247227825Stheraven template <class _InputIterator> 248227825Stheraven hash_set(_InputIterator __first, _InputIterator __last); 249227825Stheraven template <class _InputIterator> 250227825Stheraven hash_set(_InputIterator __first, _InputIterator __last, 251227825Stheraven size_type __n, const hasher& __hf = hasher(), 252227825Stheraven const key_equal& __eql = key_equal()); 253227825Stheraven template <class _InputIterator> 254227825Stheraven hash_set(_InputIterator __first, _InputIterator __last, 255227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 256227825Stheraven const allocator_type& __a); 257227825Stheraven hash_set(const hash_set& __u); 258227825Stheraven 259227825Stheraven _LIBCPP_INLINE_VISIBILITY 260227825Stheraven allocator_type get_allocator() const 261227825Stheraven {return allocator_type(__table_.__node_alloc());} 262227825Stheraven 263227825Stheraven _LIBCPP_INLINE_VISIBILITY 264227825Stheraven bool empty() const {return __table_.size() == 0;} 265227825Stheraven _LIBCPP_INLINE_VISIBILITY 266227825Stheraven size_type size() const {return __table_.size();} 267227825Stheraven _LIBCPP_INLINE_VISIBILITY 268227825Stheraven size_type max_size() const {return __table_.max_size();} 269227825Stheraven 270227825Stheraven _LIBCPP_INLINE_VISIBILITY 271227825Stheraven iterator begin() {return __table_.begin();} 272227825Stheraven _LIBCPP_INLINE_VISIBILITY 273227825Stheraven iterator end() {return __table_.end();} 274227825Stheraven _LIBCPP_INLINE_VISIBILITY 275227825Stheraven const_iterator begin() const {return __table_.begin();} 276227825Stheraven _LIBCPP_INLINE_VISIBILITY 277227825Stheraven const_iterator end() const {return __table_.end();} 278227825Stheraven 279227825Stheraven _LIBCPP_INLINE_VISIBILITY 280227825Stheraven pair<iterator, bool> insert(const value_type& __x) 281227825Stheraven {return __table_.__insert_unique(__x);} 282227825Stheraven _LIBCPP_INLINE_VISIBILITY 283227825Stheraven iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;} 284227825Stheraven template <class _InputIterator> 285227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 286227825Stheraven 287227825Stheraven _LIBCPP_INLINE_VISIBILITY 288227825Stheraven void erase(const_iterator __p) {__table_.erase(__p);} 289227825Stheraven _LIBCPP_INLINE_VISIBILITY 290227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 291227825Stheraven _LIBCPP_INLINE_VISIBILITY 292227825Stheraven void erase(const_iterator __first, const_iterator __last) 293227825Stheraven {__table_.erase(__first, __last);} 294227825Stheraven _LIBCPP_INLINE_VISIBILITY 295227825Stheraven void clear() {__table_.clear();} 296227825Stheraven 297227825Stheraven _LIBCPP_INLINE_VISIBILITY 298227825Stheraven void swap(hash_set& __u) {__table_.swap(__u.__table_);} 299227825Stheraven 300227825Stheraven _LIBCPP_INLINE_VISIBILITY 301227825Stheraven hasher hash_funct() const {return __table_.hash_function();} 302227825Stheraven _LIBCPP_INLINE_VISIBILITY 303227825Stheraven key_equal key_eq() const {return __table_.key_eq();} 304227825Stheraven 305227825Stheraven _LIBCPP_INLINE_VISIBILITY 306227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 307227825Stheraven _LIBCPP_INLINE_VISIBILITY 308227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 309227825Stheraven _LIBCPP_INLINE_VISIBILITY 310227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 311227825Stheraven _LIBCPP_INLINE_VISIBILITY 312227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 313227825Stheraven {return __table_.__equal_range_unique(__k);} 314227825Stheraven _LIBCPP_INLINE_VISIBILITY 315227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 316227825Stheraven {return __table_.__equal_range_unique(__k);} 317227825Stheraven 318227825Stheraven _LIBCPP_INLINE_VISIBILITY 319227825Stheraven size_type bucket_count() const {return __table_.bucket_count();} 320227825Stheraven _LIBCPP_INLINE_VISIBILITY 321227825Stheraven size_type max_bucket_count() const {return __table_.max_bucket_count();} 322227825Stheraven 323227825Stheraven _LIBCPP_INLINE_VISIBILITY 324227825Stheraven size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);} 325227825Stheraven 326227825Stheraven _LIBCPP_INLINE_VISIBILITY 327227825Stheraven void resize(size_type __n) {__table_.rehash(__n);} 328227825Stheraven}; 329227825Stheraven 330227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 331227825Stheravenhash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, 332227825Stheraven const hasher& __hf, const key_equal& __eql) 333227825Stheraven : __table_(__hf, __eql) 334227825Stheraven{ 335227825Stheraven __table_.rehash(__n); 336227825Stheraven} 337227825Stheraven 338227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 339227825Stheravenhash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, 340227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 341227825Stheraven : __table_(__hf, __eql, __a) 342227825Stheraven{ 343227825Stheraven __table_.rehash(__n); 344227825Stheraven} 345227825Stheraven 346227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 347227825Stheraventemplate <class _InputIterator> 348227825Stheravenhash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 349227825Stheraven _InputIterator __first, _InputIterator __last) 350227825Stheraven{ 351227825Stheraven __table_.rehash(193); 352227825Stheraven insert(__first, __last); 353227825Stheraven} 354227825Stheraven 355227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 356227825Stheraventemplate <class _InputIterator> 357227825Stheravenhash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 358227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 359227825Stheraven const hasher& __hf, const key_equal& __eql) 360227825Stheraven : __table_(__hf, __eql) 361227825Stheraven{ 362227825Stheraven __table_.rehash(__n); 363227825Stheraven insert(__first, __last); 364227825Stheraven} 365227825Stheraven 366227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 367227825Stheraventemplate <class _InputIterator> 368227825Stheravenhash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 369227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 370227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 371227825Stheraven : __table_(__hf, __eql, __a) 372227825Stheraven{ 373227825Stheraven __table_.rehash(__n); 374227825Stheraven insert(__first, __last); 375227825Stheraven} 376227825Stheraven 377227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 378227825Stheravenhash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 379227825Stheraven const hash_set& __u) 380227825Stheraven : __table_(__u.__table_) 381227825Stheraven{ 382227825Stheraven __table_.rehash(__u.bucket_count()); 383227825Stheraven insert(__u.begin(), __u.end()); 384227825Stheraven} 385227825Stheraven 386227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 387227825Stheraventemplate <class _InputIterator> 388227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 389227825Stheravenvoid 390227825Stheravenhash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 391227825Stheraven _InputIterator __last) 392227825Stheraven{ 393227825Stheraven for (; __first != __last; ++__first) 394227825Stheraven __table_.__insert_unique(*__first); 395227825Stheraven} 396227825Stheraven 397227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 398227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 399227825Stheravenvoid 400227825Stheravenswap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 401227825Stheraven hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 402227825Stheraven{ 403227825Stheraven __x.swap(__y); 404227825Stheraven} 405227825Stheraven 406227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 407227825Stheravenbool 408227825Stheravenoperator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 409227825Stheraven const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 410227825Stheraven{ 411227825Stheraven if (__x.size() != __y.size()) 412227825Stheraven return false; 413227825Stheraven typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 414227825Stheraven const_iterator; 415227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 416227825Stheraven __i != __ex; ++__i) 417227825Stheraven { 418227825Stheraven const_iterator __j = __y.find(*__i); 419227825Stheraven if (__j == __ey || !(*__i == *__j)) 420227825Stheraven return false; 421227825Stheraven } 422227825Stheraven return true; 423227825Stheraven} 424227825Stheraven 425227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 426227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 427227825Stheravenbool 428227825Stheravenoperator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 429227825Stheraven const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 430227825Stheraven{ 431227825Stheraven return !(__x == __y); 432227825Stheraven} 433227825Stheraven 434227825Stheraventemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 435227825Stheraven class _Alloc = allocator<_Value> > 436262801Sdimclass _LIBCPP_TYPE_VIS_ONLY hash_multiset 437227825Stheraven{ 438227825Stheravenpublic: 439227825Stheraven // types 440227825Stheraven typedef _Value key_type; 441227825Stheraven typedef key_type value_type; 442227825Stheraven typedef _Hash hasher; 443227825Stheraven typedef _Pred key_equal; 444227825Stheraven typedef _Alloc allocator_type; 445227825Stheraven typedef value_type& reference; 446227825Stheraven typedef const value_type& const_reference; 447227825Stheraven 448227825Stheravenprivate: 449227825Stheraven typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 450227825Stheraven 451227825Stheraven __table __table_; 452227825Stheraven 453227825Stheravenpublic: 454227825Stheraven typedef typename __table::pointer pointer; 455227825Stheraven typedef typename __table::const_pointer const_pointer; 456227825Stheraven typedef typename __table::size_type size_type; 457227825Stheraven typedef typename __table::difference_type difference_type; 458227825Stheraven 459227825Stheraven typedef typename __table::const_iterator iterator; 460227825Stheraven typedef typename __table::const_iterator const_iterator; 461227825Stheraven 462227825Stheraven _LIBCPP_INLINE_VISIBILITY 463227825Stheraven hash_multiset() {__table_.rehash(193);} 464227825Stheraven explicit hash_multiset(size_type __n, const hasher& __hf = hasher(), 465227825Stheraven const key_equal& __eql = key_equal()); 466227825Stheraven hash_multiset(size_type __n, const hasher& __hf, 467227825Stheraven const key_equal& __eql, const allocator_type& __a); 468227825Stheraven template <class _InputIterator> 469227825Stheraven hash_multiset(_InputIterator __first, _InputIterator __last); 470227825Stheraven template <class _InputIterator> 471227825Stheraven hash_multiset(_InputIterator __first, _InputIterator __last, 472227825Stheraven size_type __n, const hasher& __hf = hasher(), 473227825Stheraven const key_equal& __eql = key_equal()); 474227825Stheraven template <class _InputIterator> 475227825Stheraven hash_multiset(_InputIterator __first, _InputIterator __last, 476227825Stheraven size_type __n , const hasher& __hf, 477227825Stheraven const key_equal& __eql, const allocator_type& __a); 478227825Stheraven hash_multiset(const hash_multiset& __u); 479227825Stheraven 480227825Stheraven _LIBCPP_INLINE_VISIBILITY 481227825Stheraven allocator_type get_allocator() const 482227825Stheraven {return allocator_type(__table_.__node_alloc());} 483227825Stheraven 484227825Stheraven _LIBCPP_INLINE_VISIBILITY 485227825Stheraven bool empty() const {return __table_.size() == 0;} 486227825Stheraven _LIBCPP_INLINE_VISIBILITY 487227825Stheraven size_type size() const {return __table_.size();} 488227825Stheraven _LIBCPP_INLINE_VISIBILITY 489227825Stheraven size_type max_size() const {return __table_.max_size();} 490227825Stheraven 491227825Stheraven _LIBCPP_INLINE_VISIBILITY 492227825Stheraven iterator begin() {return __table_.begin();} 493227825Stheraven _LIBCPP_INLINE_VISIBILITY 494227825Stheraven iterator end() {return __table_.end();} 495227825Stheraven _LIBCPP_INLINE_VISIBILITY 496227825Stheraven const_iterator begin() const {return __table_.begin();} 497227825Stheraven _LIBCPP_INLINE_VISIBILITY 498227825Stheraven const_iterator end() const {return __table_.end();} 499227825Stheraven 500227825Stheraven _LIBCPP_INLINE_VISIBILITY 501227825Stheraven iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 502227825Stheraven _LIBCPP_INLINE_VISIBILITY 503227825Stheraven iterator insert(const_iterator, const value_type& __x) {return insert(__x);} 504227825Stheraven template <class _InputIterator> 505227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 506227825Stheraven 507227825Stheraven _LIBCPP_INLINE_VISIBILITY 508227825Stheraven void erase(const_iterator __p) {__table_.erase(__p);} 509227825Stheraven _LIBCPP_INLINE_VISIBILITY 510227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 511227825Stheraven _LIBCPP_INLINE_VISIBILITY 512227825Stheraven void erase(const_iterator __first, const_iterator __last) 513227825Stheraven {__table_.erase(__first, __last);} 514227825Stheraven _LIBCPP_INLINE_VISIBILITY 515227825Stheraven void clear() {__table_.clear();} 516227825Stheraven 517227825Stheraven _LIBCPP_INLINE_VISIBILITY 518227825Stheraven void swap(hash_multiset& __u) {__table_.swap(__u.__table_);} 519227825Stheraven 520227825Stheraven _LIBCPP_INLINE_VISIBILITY 521227825Stheraven hasher hash_funct() const {return __table_.hash_function();} 522227825Stheraven _LIBCPP_INLINE_VISIBILITY 523227825Stheraven key_equal key_eq() const {return __table_.key_eq();} 524227825Stheraven 525227825Stheraven _LIBCPP_INLINE_VISIBILITY 526227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 527227825Stheraven _LIBCPP_INLINE_VISIBILITY 528227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 529227825Stheraven _LIBCPP_INLINE_VISIBILITY 530227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 531227825Stheraven _LIBCPP_INLINE_VISIBILITY 532227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 533227825Stheraven {return __table_.__equal_range_multi(__k);} 534227825Stheraven _LIBCPP_INLINE_VISIBILITY 535227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 536227825Stheraven {return __table_.__equal_range_multi(__k);} 537227825Stheraven 538227825Stheraven _LIBCPP_INLINE_VISIBILITY 539227825Stheraven size_type bucket_count() const {return __table_.bucket_count();} 540227825Stheraven _LIBCPP_INLINE_VISIBILITY 541227825Stheraven size_type max_bucket_count() const {return __table_.max_bucket_count();} 542227825Stheraven 543227825Stheraven _LIBCPP_INLINE_VISIBILITY 544227825Stheraven size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);} 545227825Stheraven 546227825Stheraven _LIBCPP_INLINE_VISIBILITY 547227825Stheraven void resize(size_type __n) {__table_.rehash(__n);} 548227825Stheraven}; 549227825Stheraven 550227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 551227825Stheravenhash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 552227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 553227825Stheraven : __table_(__hf, __eql) 554227825Stheraven{ 555227825Stheraven __table_.rehash(__n); 556227825Stheraven} 557227825Stheraven 558227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 559227825Stheravenhash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 560227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 561227825Stheraven const allocator_type& __a) 562227825Stheraven : __table_(__hf, __eql, __a) 563227825Stheraven{ 564227825Stheraven __table_.rehash(__n); 565227825Stheraven} 566227825Stheraven 567227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 568227825Stheraventemplate <class _InputIterator> 569227825Stheravenhash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 570227825Stheraven _InputIterator __first, _InputIterator __last) 571227825Stheraven{ 572227825Stheraven __table_.rehash(193); 573227825Stheraven insert(__first, __last); 574227825Stheraven} 575227825Stheraven 576227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 577227825Stheraventemplate <class _InputIterator> 578227825Stheravenhash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 579227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 580227825Stheraven const hasher& __hf, const key_equal& __eql) 581227825Stheraven : __table_(__hf, __eql) 582227825Stheraven{ 583227825Stheraven __table_.rehash(__n); 584227825Stheraven insert(__first, __last); 585227825Stheraven} 586227825Stheraven 587227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 588227825Stheraventemplate <class _InputIterator> 589227825Stheravenhash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 590227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 591227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 592227825Stheraven : __table_(__hf, __eql, __a) 593227825Stheraven{ 594227825Stheraven __table_.rehash(__n); 595227825Stheraven insert(__first, __last); 596227825Stheraven} 597227825Stheraven 598227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 599227825Stheravenhash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 600227825Stheraven const hash_multiset& __u) 601227825Stheraven : __table_(__u.__table_) 602227825Stheraven{ 603227825Stheraven __table_.rehash(__u.bucket_count()); 604227825Stheraven insert(__u.begin(), __u.end()); 605227825Stheraven} 606227825Stheraven 607227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 608227825Stheraventemplate <class _InputIterator> 609227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 610227825Stheravenvoid 611227825Stheravenhash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 612227825Stheraven _InputIterator __last) 613227825Stheraven{ 614227825Stheraven for (; __first != __last; ++__first) 615227825Stheraven __table_.__insert_multi(*__first); 616227825Stheraven} 617227825Stheraven 618227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 619227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 620227825Stheravenvoid 621227825Stheravenswap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 622227825Stheraven hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 623227825Stheraven{ 624227825Stheraven __x.swap(__y); 625227825Stheraven} 626227825Stheraven 627227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 628227825Stheravenbool 629227825Stheravenoperator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 630227825Stheraven const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 631227825Stheraven{ 632227825Stheraven if (__x.size() != __y.size()) 633227825Stheraven return false; 634227825Stheraven typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 635227825Stheraven const_iterator; 636227825Stheraven typedef pair<const_iterator, const_iterator> _EqRng; 637227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 638227825Stheraven { 639227825Stheraven _EqRng __xeq = __x.equal_range(*__i); 640227825Stheraven _EqRng __yeq = __y.equal_range(*__i); 641227825Stheraven if (_VSTD::distance(__xeq.first, __xeq.second) != 642227825Stheraven _VSTD::distance(__yeq.first, __yeq.second) || 643227825Stheraven !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 644227825Stheraven return false; 645227825Stheraven __i = __xeq.second; 646227825Stheraven } 647227825Stheraven return true; 648227825Stheraven} 649227825Stheraven 650227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 651227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 652227825Stheravenbool 653227825Stheravenoperator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 654227825Stheraven const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 655227825Stheraven{ 656227825Stheraven return !(__x == __y); 657227825Stheraven} 658227825Stheraven 659227825Stheraven} // __gnu_cxx 660227825Stheraven 661227825Stheraven#endif // _LIBCPP_HASH_SET 662