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 202227825Stheraven#warning Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set> 203227825Stheraven#endif 204227825Stheraven 205227825Stheravennamespace __gnu_cxx { 206227825Stheraven 207227825Stheravenusing namespace std; 208227825Stheraven 209227825Stheraventemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 210227825Stheraven class _Alloc = allocator<_Value> > 211249998Sdimclass _LIBCPP_TYPE_VIS hash_set 212227825Stheraven{ 213227825Stheravenpublic: 214227825Stheraven // types 215227825Stheraven typedef _Value key_type; 216227825Stheraven typedef key_type value_type; 217227825Stheraven typedef _Hash hasher; 218227825Stheraven typedef _Pred key_equal; 219227825Stheraven typedef _Alloc allocator_type; 220227825Stheraven typedef value_type& reference; 221227825Stheraven typedef const value_type& const_reference; 222227825Stheraven 223227825Stheravenprivate: 224227825Stheraven typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 225227825Stheraven 226227825Stheraven __table __table_; 227227825Stheraven 228227825Stheravenpublic: 229227825Stheraven typedef typename __table::pointer pointer; 230227825Stheraven typedef typename __table::const_pointer const_pointer; 231227825Stheraven typedef typename __table::size_type size_type; 232227825Stheraven typedef typename __table::difference_type difference_type; 233227825Stheraven 234227825Stheraven typedef typename __table::const_iterator iterator; 235227825Stheraven typedef typename __table::const_iterator const_iterator; 236227825Stheraven 237227825Stheraven _LIBCPP_INLINE_VISIBILITY 238227825Stheraven hash_set() {__table_.rehash(193);} 239227825Stheraven explicit hash_set(size_type __n, const hasher& __hf = hasher(), 240227825Stheraven const key_equal& __eql = key_equal()); 241227825Stheraven hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, 242227825Stheraven const allocator_type& __a); 243227825Stheraven template <class _InputIterator> 244227825Stheraven hash_set(_InputIterator __first, _InputIterator __last); 245227825Stheraven template <class _InputIterator> 246227825Stheraven hash_set(_InputIterator __first, _InputIterator __last, 247227825Stheraven size_type __n, const hasher& __hf = hasher(), 248227825Stheraven const key_equal& __eql = key_equal()); 249227825Stheraven template <class _InputIterator> 250227825Stheraven hash_set(_InputIterator __first, _InputIterator __last, 251227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 252227825Stheraven const allocator_type& __a); 253227825Stheraven hash_set(const hash_set& __u); 254227825Stheraven 255227825Stheraven _LIBCPP_INLINE_VISIBILITY 256227825Stheraven allocator_type get_allocator() const 257227825Stheraven {return allocator_type(__table_.__node_alloc());} 258227825Stheraven 259227825Stheraven _LIBCPP_INLINE_VISIBILITY 260227825Stheraven bool empty() const {return __table_.size() == 0;} 261227825Stheraven _LIBCPP_INLINE_VISIBILITY 262227825Stheraven size_type size() const {return __table_.size();} 263227825Stheraven _LIBCPP_INLINE_VISIBILITY 264227825Stheraven size_type max_size() const {return __table_.max_size();} 265227825Stheraven 266227825Stheraven _LIBCPP_INLINE_VISIBILITY 267227825Stheraven iterator begin() {return __table_.begin();} 268227825Stheraven _LIBCPP_INLINE_VISIBILITY 269227825Stheraven iterator end() {return __table_.end();} 270227825Stheraven _LIBCPP_INLINE_VISIBILITY 271227825Stheraven const_iterator begin() const {return __table_.begin();} 272227825Stheraven _LIBCPP_INLINE_VISIBILITY 273227825Stheraven const_iterator end() const {return __table_.end();} 274227825Stheraven 275227825Stheraven _LIBCPP_INLINE_VISIBILITY 276227825Stheraven pair<iterator, bool> insert(const value_type& __x) 277227825Stheraven {return __table_.__insert_unique(__x);} 278227825Stheraven _LIBCPP_INLINE_VISIBILITY 279227825Stheraven iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;} 280227825Stheraven template <class _InputIterator> 281227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 282227825Stheraven 283227825Stheraven _LIBCPP_INLINE_VISIBILITY 284227825Stheraven void erase(const_iterator __p) {__table_.erase(__p);} 285227825Stheraven _LIBCPP_INLINE_VISIBILITY 286227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 287227825Stheraven _LIBCPP_INLINE_VISIBILITY 288227825Stheraven void erase(const_iterator __first, const_iterator __last) 289227825Stheraven {__table_.erase(__first, __last);} 290227825Stheraven _LIBCPP_INLINE_VISIBILITY 291227825Stheraven void clear() {__table_.clear();} 292227825Stheraven 293227825Stheraven _LIBCPP_INLINE_VISIBILITY 294227825Stheraven void swap(hash_set& __u) {__table_.swap(__u.__table_);} 295227825Stheraven 296227825Stheraven _LIBCPP_INLINE_VISIBILITY 297227825Stheraven hasher hash_funct() const {return __table_.hash_function();} 298227825Stheraven _LIBCPP_INLINE_VISIBILITY 299227825Stheraven key_equal key_eq() const {return __table_.key_eq();} 300227825Stheraven 301227825Stheraven _LIBCPP_INLINE_VISIBILITY 302227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 303227825Stheraven _LIBCPP_INLINE_VISIBILITY 304227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 305227825Stheraven _LIBCPP_INLINE_VISIBILITY 306227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 307227825Stheraven _LIBCPP_INLINE_VISIBILITY 308227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 309227825Stheraven {return __table_.__equal_range_unique(__k);} 310227825Stheraven _LIBCPP_INLINE_VISIBILITY 311227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 312227825Stheraven {return __table_.__equal_range_unique(__k);} 313227825Stheraven 314227825Stheraven _LIBCPP_INLINE_VISIBILITY 315227825Stheraven size_type bucket_count() const {return __table_.bucket_count();} 316227825Stheraven _LIBCPP_INLINE_VISIBILITY 317227825Stheraven size_type max_bucket_count() const {return __table_.max_bucket_count();} 318227825Stheraven 319227825Stheraven _LIBCPP_INLINE_VISIBILITY 320227825Stheraven size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);} 321227825Stheraven 322227825Stheraven _LIBCPP_INLINE_VISIBILITY 323227825Stheraven void resize(size_type __n) {__table_.rehash(__n);} 324227825Stheraven}; 325227825Stheraven 326227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 327227825Stheravenhash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, 328227825Stheraven const hasher& __hf, const key_equal& __eql) 329227825Stheraven : __table_(__hf, __eql) 330227825Stheraven{ 331227825Stheraven __table_.rehash(__n); 332227825Stheraven} 333227825Stheraven 334227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 335227825Stheravenhash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, 336227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 337227825Stheraven : __table_(__hf, __eql, __a) 338227825Stheraven{ 339227825Stheraven __table_.rehash(__n); 340227825Stheraven} 341227825Stheraven 342227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 343227825Stheraventemplate <class _InputIterator> 344227825Stheravenhash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 345227825Stheraven _InputIterator __first, _InputIterator __last) 346227825Stheraven{ 347227825Stheraven __table_.rehash(193); 348227825Stheraven insert(__first, __last); 349227825Stheraven} 350227825Stheraven 351227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 352227825Stheraventemplate <class _InputIterator> 353227825Stheravenhash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 354227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 355227825Stheraven const hasher& __hf, const key_equal& __eql) 356227825Stheraven : __table_(__hf, __eql) 357227825Stheraven{ 358227825Stheraven __table_.rehash(__n); 359227825Stheraven insert(__first, __last); 360227825Stheraven} 361227825Stheraven 362227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 363227825Stheraventemplate <class _InputIterator> 364227825Stheravenhash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 365227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 366227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 367227825Stheraven : __table_(__hf, __eql, __a) 368227825Stheraven{ 369227825Stheraven __table_.rehash(__n); 370227825Stheraven insert(__first, __last); 371227825Stheraven} 372227825Stheraven 373227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 374227825Stheravenhash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 375227825Stheraven const hash_set& __u) 376227825Stheraven : __table_(__u.__table_) 377227825Stheraven{ 378227825Stheraven __table_.rehash(__u.bucket_count()); 379227825Stheraven insert(__u.begin(), __u.end()); 380227825Stheraven} 381227825Stheraven 382227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 383227825Stheraventemplate <class _InputIterator> 384227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 385227825Stheravenvoid 386227825Stheravenhash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 387227825Stheraven _InputIterator __last) 388227825Stheraven{ 389227825Stheraven for (; __first != __last; ++__first) 390227825Stheraven __table_.__insert_unique(*__first); 391227825Stheraven} 392227825Stheraven 393227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 394227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 395227825Stheravenvoid 396227825Stheravenswap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 397227825Stheraven hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 398227825Stheraven{ 399227825Stheraven __x.swap(__y); 400227825Stheraven} 401227825Stheraven 402227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 403227825Stheravenbool 404227825Stheravenoperator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 405227825Stheraven const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 406227825Stheraven{ 407227825Stheraven if (__x.size() != __y.size()) 408227825Stheraven return false; 409227825Stheraven typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 410227825Stheraven const_iterator; 411227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 412227825Stheraven __i != __ex; ++__i) 413227825Stheraven { 414227825Stheraven const_iterator __j = __y.find(*__i); 415227825Stheraven if (__j == __ey || !(*__i == *__j)) 416227825Stheraven return false; 417227825Stheraven } 418227825Stheraven return true; 419227825Stheraven} 420227825Stheraven 421227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 422227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 423227825Stheravenbool 424227825Stheravenoperator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 425227825Stheraven const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 426227825Stheraven{ 427227825Stheraven return !(__x == __y); 428227825Stheraven} 429227825Stheraven 430227825Stheraventemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 431227825Stheraven class _Alloc = allocator<_Value> > 432249998Sdimclass _LIBCPP_TYPE_VIS hash_multiset 433227825Stheraven{ 434227825Stheravenpublic: 435227825Stheraven // types 436227825Stheraven typedef _Value key_type; 437227825Stheraven typedef key_type value_type; 438227825Stheraven typedef _Hash hasher; 439227825Stheraven typedef _Pred key_equal; 440227825Stheraven typedef _Alloc allocator_type; 441227825Stheraven typedef value_type& reference; 442227825Stheraven typedef const value_type& const_reference; 443227825Stheraven 444227825Stheravenprivate: 445227825Stheraven typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 446227825Stheraven 447227825Stheraven __table __table_; 448227825Stheraven 449227825Stheravenpublic: 450227825Stheraven typedef typename __table::pointer pointer; 451227825Stheraven typedef typename __table::const_pointer const_pointer; 452227825Stheraven typedef typename __table::size_type size_type; 453227825Stheraven typedef typename __table::difference_type difference_type; 454227825Stheraven 455227825Stheraven typedef typename __table::const_iterator iterator; 456227825Stheraven typedef typename __table::const_iterator const_iterator; 457227825Stheraven 458227825Stheraven _LIBCPP_INLINE_VISIBILITY 459227825Stheraven hash_multiset() {__table_.rehash(193);} 460227825Stheraven explicit hash_multiset(size_type __n, const hasher& __hf = hasher(), 461227825Stheraven const key_equal& __eql = key_equal()); 462227825Stheraven hash_multiset(size_type __n, const hasher& __hf, 463227825Stheraven const key_equal& __eql, const allocator_type& __a); 464227825Stheraven template <class _InputIterator> 465227825Stheraven hash_multiset(_InputIterator __first, _InputIterator __last); 466227825Stheraven template <class _InputIterator> 467227825Stheraven hash_multiset(_InputIterator __first, _InputIterator __last, 468227825Stheraven size_type __n, const hasher& __hf = hasher(), 469227825Stheraven const key_equal& __eql = key_equal()); 470227825Stheraven template <class _InputIterator> 471227825Stheraven hash_multiset(_InputIterator __first, _InputIterator __last, 472227825Stheraven size_type __n , const hasher& __hf, 473227825Stheraven const key_equal& __eql, const allocator_type& __a); 474227825Stheraven hash_multiset(const hash_multiset& __u); 475227825Stheraven 476227825Stheraven _LIBCPP_INLINE_VISIBILITY 477227825Stheraven allocator_type get_allocator() const 478227825Stheraven {return allocator_type(__table_.__node_alloc());} 479227825Stheraven 480227825Stheraven _LIBCPP_INLINE_VISIBILITY 481227825Stheraven bool empty() const {return __table_.size() == 0;} 482227825Stheraven _LIBCPP_INLINE_VISIBILITY 483227825Stheraven size_type size() const {return __table_.size();} 484227825Stheraven _LIBCPP_INLINE_VISIBILITY 485227825Stheraven size_type max_size() const {return __table_.max_size();} 486227825Stheraven 487227825Stheraven _LIBCPP_INLINE_VISIBILITY 488227825Stheraven iterator begin() {return __table_.begin();} 489227825Stheraven _LIBCPP_INLINE_VISIBILITY 490227825Stheraven iterator end() {return __table_.end();} 491227825Stheraven _LIBCPP_INLINE_VISIBILITY 492227825Stheraven const_iterator begin() const {return __table_.begin();} 493227825Stheraven _LIBCPP_INLINE_VISIBILITY 494227825Stheraven const_iterator end() const {return __table_.end();} 495227825Stheraven 496227825Stheraven _LIBCPP_INLINE_VISIBILITY 497227825Stheraven iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 498227825Stheraven _LIBCPP_INLINE_VISIBILITY 499227825Stheraven iterator insert(const_iterator, const value_type& __x) {return insert(__x);} 500227825Stheraven template <class _InputIterator> 501227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 502227825Stheraven 503227825Stheraven _LIBCPP_INLINE_VISIBILITY 504227825Stheraven void erase(const_iterator __p) {__table_.erase(__p);} 505227825Stheraven _LIBCPP_INLINE_VISIBILITY 506227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 507227825Stheraven _LIBCPP_INLINE_VISIBILITY 508227825Stheraven void erase(const_iterator __first, const_iterator __last) 509227825Stheraven {__table_.erase(__first, __last);} 510227825Stheraven _LIBCPP_INLINE_VISIBILITY 511227825Stheraven void clear() {__table_.clear();} 512227825Stheraven 513227825Stheraven _LIBCPP_INLINE_VISIBILITY 514227825Stheraven void swap(hash_multiset& __u) {__table_.swap(__u.__table_);} 515227825Stheraven 516227825Stheraven _LIBCPP_INLINE_VISIBILITY 517227825Stheraven hasher hash_funct() const {return __table_.hash_function();} 518227825Stheraven _LIBCPP_INLINE_VISIBILITY 519227825Stheraven key_equal key_eq() const {return __table_.key_eq();} 520227825Stheraven 521227825Stheraven _LIBCPP_INLINE_VISIBILITY 522227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 523227825Stheraven _LIBCPP_INLINE_VISIBILITY 524227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 525227825Stheraven _LIBCPP_INLINE_VISIBILITY 526227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 527227825Stheraven _LIBCPP_INLINE_VISIBILITY 528227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 529227825Stheraven {return __table_.__equal_range_multi(__k);} 530227825Stheraven _LIBCPP_INLINE_VISIBILITY 531227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 532227825Stheraven {return __table_.__equal_range_multi(__k);} 533227825Stheraven 534227825Stheraven _LIBCPP_INLINE_VISIBILITY 535227825Stheraven size_type bucket_count() const {return __table_.bucket_count();} 536227825Stheraven _LIBCPP_INLINE_VISIBILITY 537227825Stheraven size_type max_bucket_count() const {return __table_.max_bucket_count();} 538227825Stheraven 539227825Stheraven _LIBCPP_INLINE_VISIBILITY 540227825Stheraven size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);} 541227825Stheraven 542227825Stheraven _LIBCPP_INLINE_VISIBILITY 543227825Stheraven void resize(size_type __n) {__table_.rehash(__n);} 544227825Stheraven}; 545227825Stheraven 546227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 547227825Stheravenhash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 548227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 549227825Stheraven : __table_(__hf, __eql) 550227825Stheraven{ 551227825Stheraven __table_.rehash(__n); 552227825Stheraven} 553227825Stheraven 554227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 555227825Stheravenhash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 556227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 557227825Stheraven const allocator_type& __a) 558227825Stheraven : __table_(__hf, __eql, __a) 559227825Stheraven{ 560227825Stheraven __table_.rehash(__n); 561227825Stheraven} 562227825Stheraven 563227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 564227825Stheraventemplate <class _InputIterator> 565227825Stheravenhash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 566227825Stheraven _InputIterator __first, _InputIterator __last) 567227825Stheraven{ 568227825Stheraven __table_.rehash(193); 569227825Stheraven insert(__first, __last); 570227825Stheraven} 571227825Stheraven 572227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 573227825Stheraventemplate <class _InputIterator> 574227825Stheravenhash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 575227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 576227825Stheraven const hasher& __hf, const key_equal& __eql) 577227825Stheraven : __table_(__hf, __eql) 578227825Stheraven{ 579227825Stheraven __table_.rehash(__n); 580227825Stheraven insert(__first, __last); 581227825Stheraven} 582227825Stheraven 583227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 584227825Stheraventemplate <class _InputIterator> 585227825Stheravenhash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 586227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 587227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 588227825Stheraven : __table_(__hf, __eql, __a) 589227825Stheraven{ 590227825Stheraven __table_.rehash(__n); 591227825Stheraven insert(__first, __last); 592227825Stheraven} 593227825Stheraven 594227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 595227825Stheravenhash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 596227825Stheraven const hash_multiset& __u) 597227825Stheraven : __table_(__u.__table_) 598227825Stheraven{ 599227825Stheraven __table_.rehash(__u.bucket_count()); 600227825Stheraven insert(__u.begin(), __u.end()); 601227825Stheraven} 602227825Stheraven 603227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 604227825Stheraventemplate <class _InputIterator> 605227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 606227825Stheravenvoid 607227825Stheravenhash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 608227825Stheraven _InputIterator __last) 609227825Stheraven{ 610227825Stheraven for (; __first != __last; ++__first) 611227825Stheraven __table_.__insert_multi(*__first); 612227825Stheraven} 613227825Stheraven 614227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 615227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 616227825Stheravenvoid 617227825Stheravenswap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 618227825Stheraven hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 619227825Stheraven{ 620227825Stheraven __x.swap(__y); 621227825Stheraven} 622227825Stheraven 623227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 624227825Stheravenbool 625227825Stheravenoperator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 626227825Stheraven const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 627227825Stheraven{ 628227825Stheraven if (__x.size() != __y.size()) 629227825Stheraven return false; 630227825Stheraven typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 631227825Stheraven const_iterator; 632227825Stheraven typedef pair<const_iterator, const_iterator> _EqRng; 633227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 634227825Stheraven { 635227825Stheraven _EqRng __xeq = __x.equal_range(*__i); 636227825Stheraven _EqRng __yeq = __y.equal_range(*__i); 637227825Stheraven if (_VSTD::distance(__xeq.first, __xeq.second) != 638227825Stheraven _VSTD::distance(__yeq.first, __yeq.second) || 639227825Stheraven !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 640227825Stheraven return false; 641227825Stheraven __i = __xeq.second; 642227825Stheraven } 643227825Stheraven return true; 644227825Stheraven} 645227825Stheraven 646227825Stheraventemplate <class _Value, class _Hash, class _Pred, class _Alloc> 647227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 648227825Stheravenbool 649227825Stheravenoperator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 650227825Stheraven const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 651227825Stheraven{ 652227825Stheraven return !(__x == __y); 653227825Stheraven} 654227825Stheraven 655227825Stheraven} // __gnu_cxx 656227825Stheraven 657227825Stheraven#endif // _LIBCPP_HASH_SET 658