1 // -*- C++ -*- 2 //===-------------------------- unordered_set -----------------------------===// 3 // 4 // The LLVM Compiler Infrastructure 5 // 6 // This file is dual licensed under the MIT and the University of Illinois Open 7 // Source Licenses. See LICENSE.TXT for details. 8 // 9 //===----------------------------------------------------------------------===// 10 11 #ifndef _LIBCPP_UNORDERED_SET 12 #define _LIBCPP_UNORDERED_SET 13 14 /* 15 16 unordered_set synopsis 17 18 #include <initializer_list> 19 20 namespace std 21 { 22 23 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 24 class Alloc = allocator<Value>> 25 class unordered_set 26 { 27 public: 28 // types 29 typedef Value key_type; 30 typedef key_type value_type; 31 typedef Hash hasher; 32 typedef Pred key_equal; 33 typedef Alloc allocator_type; 34 typedef value_type& reference; 35 typedef const value_type& const_reference; 36 typedef typename allocator_traits<allocator_type>::pointer pointer; 37 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 38 typedef typename allocator_traits<allocator_type>::size_type size_type; 39 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 40 41 typedef /unspecified/ iterator; 42 typedef /unspecified/ const_iterator; 43 typedef /unspecified/ local_iterator; 44 typedef /unspecified/ const_local_iterator; 45 46 unordered_set() 47 noexcept( 48 is_nothrow_default_constructible<hasher>::value && 49 is_nothrow_default_constructible<key_equal>::value && 50 is_nothrow_default_constructible<allocator_type>::value); 51 explicit unordered_set(size_type n, const hasher& hf = hasher(), 52 const key_equal& eql = key_equal(), 53 const allocator_type& a = allocator_type()); 54 template <class InputIterator> 55 unordered_set(InputIterator f, InputIterator l, 56 size_type n = 0, const hasher& hf = hasher(), 57 const key_equal& eql = key_equal(), 58 const allocator_type& a = allocator_type()); 59 explicit unordered_set(const allocator_type&); 60 unordered_set(const unordered_set&); 61 unordered_set(const unordered_set&, const Allocator&); 62 unordered_set(unordered_set&&) 63 noexcept( 64 is_nothrow_move_constructible<hasher>::value && 65 is_nothrow_move_constructible<key_equal>::value && 66 is_nothrow_move_constructible<allocator_type>::value); 67 unordered_set(unordered_set&&, const Allocator&); 68 unordered_set(initializer_list<value_type>, size_type n = 0, 69 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 70 const allocator_type& a = allocator_type()); 71 ~unordered_set(); 72 unordered_set& operator=(const unordered_set&); 73 unordered_set& operator=(unordered_set&&) 74 noexcept( 75 allocator_type::propagate_on_container_move_assignment::value && 76 is_nothrow_move_assignable<allocator_type>::value && 77 is_nothrow_move_assignable<hasher>::value && 78 is_nothrow_move_assignable<key_equal>::value); 79 unordered_set& operator=(initializer_list<value_type>); 80 81 allocator_type get_allocator() const noexcept; 82 83 bool empty() const noexcept; 84 size_type size() const noexcept; 85 size_type max_size() const noexcept; 86 87 iterator begin() noexcept; 88 iterator end() noexcept; 89 const_iterator begin() const noexcept; 90 const_iterator end() const noexcept; 91 const_iterator cbegin() const noexcept; 92 const_iterator cend() const noexcept; 93 94 template <class... Args> 95 pair<iterator, bool> emplace(Args&&... args); 96 template <class... Args> 97 iterator emplace_hint(const_iterator position, Args&&... args); 98 pair<iterator, bool> insert(const value_type& obj); 99 pair<iterator, bool> insert(value_type&& obj); 100 iterator insert(const_iterator hint, const value_type& obj); 101 iterator insert(const_iterator hint, value_type&& obj); 102 template <class InputIterator> 103 void insert(InputIterator first, InputIterator last); 104 void insert(initializer_list<value_type>); 105 106 iterator erase(const_iterator position); 107 size_type erase(const key_type& k); 108 iterator erase(const_iterator first, const_iterator last); 109 void clear() noexcept; 110 111 void swap(unordered_set&) 112 noexcept( 113 (!allocator_type::propagate_on_container_swap::value || 114 __is_nothrow_swappable<allocator_type>::value) && 115 __is_nothrow_swappable<hasher>::value && 116 __is_nothrow_swappable<key_equal>::value); 117 118 hasher hash_function() const; 119 key_equal key_eq() const; 120 121 iterator find(const key_type& k); 122 const_iterator find(const key_type& k) const; 123 size_type count(const key_type& k) const; 124 pair<iterator, iterator> equal_range(const key_type& k); 125 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 126 127 size_type bucket_count() const noexcept; 128 size_type max_bucket_count() const noexcept; 129 130 size_type bucket_size(size_type n) const; 131 size_type bucket(const key_type& k) const; 132 133 local_iterator begin(size_type n); 134 local_iterator end(size_type n); 135 const_local_iterator begin(size_type n) const; 136 const_local_iterator end(size_type n) const; 137 const_local_iterator cbegin(size_type n) const; 138 const_local_iterator cend(size_type n) const; 139 140 float load_factor() const noexcept; 141 float max_load_factor() const noexcept; 142 void max_load_factor(float z); 143 void rehash(size_type n); 144 void reserve(size_type n); 145 }; 146 147 template <class Value, class Hash, class Pred, class Alloc> 148 void swap(unordered_set<Value, Hash, Pred, Alloc>& x, 149 unordered_set<Value, Hash, Pred, Alloc>& y) 150 noexcept(noexcept(x.swap(y))); 151 152 template <class Value, class Hash, class Pred, class Alloc> 153 bool 154 operator==(const unordered_set<Value, Hash, Pred, Alloc>& x, 155 const unordered_set<Value, Hash, Pred, Alloc>& y); 156 157 template <class Value, class Hash, class Pred, class Alloc> 158 bool 159 operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x, 160 const unordered_set<Value, Hash, Pred, Alloc>& y); 161 162 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 163 class Alloc = allocator<Value>> 164 class unordered_multiset 165 { 166 public: 167 // types 168 typedef Value key_type; 169 typedef key_type value_type; 170 typedef Hash hasher; 171 typedef Pred key_equal; 172 typedef Alloc allocator_type; 173 typedef value_type& reference; 174 typedef const value_type& const_reference; 175 typedef typename allocator_traits<allocator_type>::pointer pointer; 176 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 177 typedef typename allocator_traits<allocator_type>::size_type size_type; 178 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 179 180 typedef /unspecified/ iterator; 181 typedef /unspecified/ const_iterator; 182 typedef /unspecified/ local_iterator; 183 typedef /unspecified/ const_local_iterator; 184 185 unordered_multiset() 186 noexcept( 187 is_nothrow_default_constructible<hasher>::value && 188 is_nothrow_default_constructible<key_equal>::value && 189 is_nothrow_default_constructible<allocator_type>::value); 190 explicit unordered_multiset(size_type n, const hasher& hf = hasher(), 191 const key_equal& eql = key_equal(), 192 const allocator_type& a = allocator_type()); 193 template <class InputIterator> 194 unordered_multiset(InputIterator f, InputIterator l, 195 size_type n = 0, const hasher& hf = hasher(), 196 const key_equal& eql = key_equal(), 197 const allocator_type& a = allocator_type()); 198 explicit unordered_multiset(const allocator_type&); 199 unordered_multiset(const unordered_multiset&); 200 unordered_multiset(const unordered_multiset&, const Allocator&); 201 unordered_multiset(unordered_multiset&&) 202 noexcept( 203 is_nothrow_move_constructible<hasher>::value && 204 is_nothrow_move_constructible<key_equal>::value && 205 is_nothrow_move_constructible<allocator_type>::value); 206 unordered_multiset(unordered_multiset&&, const Allocator&); 207 unordered_multiset(initializer_list<value_type>, size_type n = /see below/, 208 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 209 const allocator_type& a = allocator_type()); 210 ~unordered_multiset(); 211 unordered_multiset& operator=(const unordered_multiset&); 212 unordered_multiset& operator=(unordered_multiset&&) 213 noexcept( 214 allocator_type::propagate_on_container_move_assignment::value && 215 is_nothrow_move_assignable<allocator_type>::value && 216 is_nothrow_move_assignable<hasher>::value && 217 is_nothrow_move_assignable<key_equal>::value); 218 unordered_multiset& operator=(initializer_list<value_type>); 219 220 allocator_type get_allocator() const noexcept; 221 222 bool empty() const noexcept; 223 size_type size() const noexcept; 224 size_type max_size() const noexcept; 225 226 iterator begin() noexcept; 227 iterator end() noexcept; 228 const_iterator begin() const noexcept; 229 const_iterator end() const noexcept; 230 const_iterator cbegin() const noexcept; 231 const_iterator cend() const noexcept; 232 233 template <class... Args> 234 iterator emplace(Args&&... args); 235 template <class... Args> 236 iterator emplace_hint(const_iterator position, Args&&... args); 237 iterator insert(const value_type& obj); 238 iterator insert(value_type&& obj); 239 iterator insert(const_iterator hint, const value_type& obj); 240 iterator insert(const_iterator hint, value_type&& obj); 241 template <class InputIterator> 242 void insert(InputIterator first, InputIterator last); 243 void insert(initializer_list<value_type>); 244 245 iterator erase(const_iterator position); 246 size_type erase(const key_type& k); 247 iterator erase(const_iterator first, const_iterator last); 248 void clear() noexcept; 249 250 void swap(unordered_multiset&) 251 noexcept( 252 (!allocator_type::propagate_on_container_swap::value || 253 __is_nothrow_swappable<allocator_type>::value) && 254 __is_nothrow_swappable<hasher>::value && 255 __is_nothrow_swappable<key_equal>::value); 256 257 hasher hash_function() const; 258 key_equal key_eq() const; 259 260 iterator find(const key_type& k); 261 const_iterator find(const key_type& k) const; 262 size_type count(const key_type& k) const; 263 pair<iterator, iterator> equal_range(const key_type& k); 264 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 265 266 size_type bucket_count() const noexcept; 267 size_type max_bucket_count() const noexcept; 268 269 size_type bucket_size(size_type n) const; 270 size_type bucket(const key_type& k) const; 271 272 local_iterator begin(size_type n); 273 local_iterator end(size_type n); 274 const_local_iterator begin(size_type n) const; 275 const_local_iterator end(size_type n) const; 276 const_local_iterator cbegin(size_type n) const; 277 const_local_iterator cend(size_type n) const; 278 279 float load_factor() const noexcept; 280 float max_load_factor() const noexcept; 281 void max_load_factor(float z); 282 void rehash(size_type n); 283 void reserve(size_type n); 284 }; 285 286 template <class Value, class Hash, class Pred, class Alloc> 287 void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x, 288 unordered_multiset<Value, Hash, Pred, Alloc>& y) 289 noexcept(noexcept(x.swap(y))); 290 291 template <class Value, class Hash, class Pred, class Alloc> 292 bool 293 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 294 const unordered_multiset<Value, Hash, Pred, Alloc>& y); 295 296 template <class Value, class Hash, class Pred, class Alloc> 297 bool 298 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 299 const unordered_multiset<Value, Hash, Pred, Alloc>& y); 300 } // std 301 302 */ 303 304 #include <__config> 305 #include <__hash_table> 306 #include <functional> 307 308 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 309 #pragma GCC system_header 310 #endif 311 312 _LIBCPP_BEGIN_NAMESPACE_STD 313 314 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 315 class _Alloc = allocator<_Value> > 316 class _LIBCPP_TYPE_VIS unordered_set 317 { 318 public: 319 // types 320 typedef _Value key_type; 321 typedef key_type value_type; 322 typedef _Hash hasher; 323 typedef _Pred key_equal; 324 typedef _Alloc allocator_type; 325 typedef value_type& reference; 326 typedef const value_type& const_reference; 327 328 private: 329 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 330 331 __table __table_; 332 333 public: 334 typedef typename __table::pointer pointer; 335 typedef typename __table::const_pointer const_pointer; 336 typedef typename __table::size_type size_type; 337 typedef typename __table::difference_type difference_type; 338 339 typedef typename __table::const_iterator iterator; 340 typedef typename __table::const_iterator const_iterator; 341 typedef typename __table::const_local_iterator local_iterator; 342 typedef typename __table::const_local_iterator const_local_iterator; 343 344 _LIBCPP_INLINE_VISIBILITY 345 unordered_set() 346 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 347 {} // = default; 348 explicit unordered_set(size_type __n, const hasher& __hf = hasher(), 349 const key_equal& __eql = key_equal()); 350 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, 351 const allocator_type& __a); 352 template <class _InputIterator> 353 unordered_set(_InputIterator __first, _InputIterator __last); 354 template <class _InputIterator> 355 unordered_set(_InputIterator __first, _InputIterator __last, 356 size_type __n, const hasher& __hf = hasher(), 357 const key_equal& __eql = key_equal()); 358 template <class _InputIterator> 359 unordered_set(_InputIterator __first, _InputIterator __last, 360 size_type __n, const hasher& __hf, const key_equal& __eql, 361 const allocator_type& __a); 362 explicit unordered_set(const allocator_type& __a); 363 unordered_set(const unordered_set& __u); 364 unordered_set(const unordered_set& __u, const allocator_type& __a); 365 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 366 unordered_set(unordered_set&& __u) 367 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 368 unordered_set(unordered_set&& __u, const allocator_type& __a); 369 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 370 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 371 unordered_set(initializer_list<value_type> __il); 372 unordered_set(initializer_list<value_type> __il, size_type __n, 373 const hasher& __hf = hasher(), 374 const key_equal& __eql = key_equal()); 375 unordered_set(initializer_list<value_type> __il, size_type __n, 376 const hasher& __hf, const key_equal& __eql, 377 const allocator_type& __a); 378 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 379 // ~unordered_set() = default; 380 _LIBCPP_INLINE_VISIBILITY 381 unordered_set& operator=(const unordered_set& __u) 382 { 383 __table_ = __u.__table_; 384 return *this; 385 } 386 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 387 unordered_set& operator=(unordered_set&& __u) 388 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 389 #endif 390 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 391 unordered_set& operator=(initializer_list<value_type> __il); 392 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 393 394 _LIBCPP_INLINE_VISIBILITY 395 allocator_type get_allocator() const _NOEXCEPT 396 {return allocator_type(__table_.__node_alloc());} 397 398 _LIBCPP_INLINE_VISIBILITY 399 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 400 _LIBCPP_INLINE_VISIBILITY 401 size_type size() const _NOEXCEPT {return __table_.size();} 402 _LIBCPP_INLINE_VISIBILITY 403 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 404 405 _LIBCPP_INLINE_VISIBILITY 406 iterator begin() _NOEXCEPT {return __table_.begin();} 407 _LIBCPP_INLINE_VISIBILITY 408 iterator end() _NOEXCEPT {return __table_.end();} 409 _LIBCPP_INLINE_VISIBILITY 410 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 411 _LIBCPP_INLINE_VISIBILITY 412 const_iterator end() const _NOEXCEPT {return __table_.end();} 413 _LIBCPP_INLINE_VISIBILITY 414 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 415 _LIBCPP_INLINE_VISIBILITY 416 const_iterator cend() const _NOEXCEPT {return __table_.end();} 417 418 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 419 template <class... _Args> 420 _LIBCPP_INLINE_VISIBILITY 421 pair<iterator, bool> emplace(_Args&&... __args) 422 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 423 template <class... _Args> 424 _LIBCPP_INLINE_VISIBILITY 425 iterator emplace_hint(const_iterator, _Args&&... __args) 426 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;} 427 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 428 _LIBCPP_INLINE_VISIBILITY 429 pair<iterator, bool> insert(const value_type& __x) 430 {return __table_.__insert_unique(__x);} 431 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 432 _LIBCPP_INLINE_VISIBILITY 433 pair<iterator, bool> insert(value_type&& __x) 434 {return __table_.__insert_unique(_VSTD::move(__x));} 435 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 436 _LIBCPP_INLINE_VISIBILITY 437 iterator insert(const_iterator, const value_type& __x) 438 {return insert(__x).first;} 439 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 440 _LIBCPP_INLINE_VISIBILITY 441 iterator insert(const_iterator, value_type&& __x) 442 {return insert(_VSTD::move(__x)).first;} 443 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 444 template <class _InputIterator> 445 void insert(_InputIterator __first, _InputIterator __last); 446 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 447 _LIBCPP_INLINE_VISIBILITY 448 void insert(initializer_list<value_type> __il) 449 {insert(__il.begin(), __il.end());} 450 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 451 452 _LIBCPP_INLINE_VISIBILITY 453 iterator erase(const_iterator __p) {return __table_.erase(__p);} 454 _LIBCPP_INLINE_VISIBILITY 455 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 456 _LIBCPP_INLINE_VISIBILITY 457 iterator erase(const_iterator __first, const_iterator __last) 458 {return __table_.erase(__first, __last);} 459 _LIBCPP_INLINE_VISIBILITY 460 void clear() _NOEXCEPT {__table_.clear();} 461 462 _LIBCPP_INLINE_VISIBILITY 463 void swap(unordered_set& __u) 464 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 465 {__table_.swap(__u.__table_);} 466 467 _LIBCPP_INLINE_VISIBILITY 468 hasher hash_function() const {return __table_.hash_function();} 469 _LIBCPP_INLINE_VISIBILITY 470 key_equal key_eq() const {return __table_.key_eq();} 471 472 _LIBCPP_INLINE_VISIBILITY 473 iterator find(const key_type& __k) {return __table_.find(__k);} 474 _LIBCPP_INLINE_VISIBILITY 475 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 476 _LIBCPP_INLINE_VISIBILITY 477 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 478 _LIBCPP_INLINE_VISIBILITY 479 pair<iterator, iterator> equal_range(const key_type& __k) 480 {return __table_.__equal_range_unique(__k);} 481 _LIBCPP_INLINE_VISIBILITY 482 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 483 {return __table_.__equal_range_unique(__k);} 484 485 _LIBCPP_INLINE_VISIBILITY 486 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 487 _LIBCPP_INLINE_VISIBILITY 488 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 489 490 _LIBCPP_INLINE_VISIBILITY 491 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 492 _LIBCPP_INLINE_VISIBILITY 493 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 494 495 _LIBCPP_INLINE_VISIBILITY 496 local_iterator begin(size_type __n) {return __table_.begin(__n);} 497 _LIBCPP_INLINE_VISIBILITY 498 local_iterator end(size_type __n) {return __table_.end(__n);} 499 _LIBCPP_INLINE_VISIBILITY 500 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 501 _LIBCPP_INLINE_VISIBILITY 502 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 503 _LIBCPP_INLINE_VISIBILITY 504 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 505 _LIBCPP_INLINE_VISIBILITY 506 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 507 508 _LIBCPP_INLINE_VISIBILITY 509 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 510 _LIBCPP_INLINE_VISIBILITY 511 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 512 _LIBCPP_INLINE_VISIBILITY 513 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 514 _LIBCPP_INLINE_VISIBILITY 515 void rehash(size_type __n) {__table_.rehash(__n);} 516 _LIBCPP_INLINE_VISIBILITY 517 void reserve(size_type __n) {__table_.reserve(__n);} 518 }; 519 520 template <class _Value, class _Hash, class _Pred, class _Alloc> 521 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 522 const hasher& __hf, const key_equal& __eql) 523 : __table_(__hf, __eql) 524 { 525 __table_.rehash(__n); 526 } 527 528 template <class _Value, class _Hash, class _Pred, class _Alloc> 529 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 530 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 531 : __table_(__hf, __eql, __a) 532 { 533 __table_.rehash(__n); 534 } 535 536 template <class _Value, class _Hash, class _Pred, class _Alloc> 537 template <class _InputIterator> 538 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 539 _InputIterator __first, _InputIterator __last) 540 { 541 insert(__first, __last); 542 } 543 544 template <class _Value, class _Hash, class _Pred, class _Alloc> 545 template <class _InputIterator> 546 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 547 _InputIterator __first, _InputIterator __last, size_type __n, 548 const hasher& __hf, const key_equal& __eql) 549 : __table_(__hf, __eql) 550 { 551 __table_.rehash(__n); 552 insert(__first, __last); 553 } 554 555 template <class _Value, class _Hash, class _Pred, class _Alloc> 556 template <class _InputIterator> 557 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 558 _InputIterator __first, _InputIterator __last, size_type __n, 559 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 560 : __table_(__hf, __eql, __a) 561 { 562 __table_.rehash(__n); 563 insert(__first, __last); 564 } 565 566 template <class _Value, class _Hash, class _Pred, class _Alloc> 567 inline _LIBCPP_INLINE_VISIBILITY 568 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 569 const allocator_type& __a) 570 : __table_(__a) 571 { 572 } 573 574 template <class _Value, class _Hash, class _Pred, class _Alloc> 575 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 576 const unordered_set& __u) 577 : __table_(__u.__table_) 578 { 579 __table_.rehash(__u.bucket_count()); 580 insert(__u.begin(), __u.end()); 581 } 582 583 template <class _Value, class _Hash, class _Pred, class _Alloc> 584 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 585 const unordered_set& __u, const allocator_type& __a) 586 : __table_(__u.__table_, __a) 587 { 588 __table_.rehash(__u.bucket_count()); 589 insert(__u.begin(), __u.end()); 590 } 591 592 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 593 594 template <class _Value, class _Hash, class _Pred, class _Alloc> 595 inline _LIBCPP_INLINE_VISIBILITY 596 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 597 unordered_set&& __u) 598 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 599 : __table_(_VSTD::move(__u.__table_)) 600 { 601 } 602 603 template <class _Value, class _Hash, class _Pred, class _Alloc> 604 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 605 unordered_set&& __u, const allocator_type& __a) 606 : __table_(_VSTD::move(__u.__table_), __a) 607 { 608 if (__a != __u.get_allocator()) 609 { 610 iterator __i = __u.begin(); 611 while (__u.size() != 0) 612 __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 613 } 614 } 615 616 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 617 618 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 619 620 template <class _Value, class _Hash, class _Pred, class _Alloc> 621 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 622 initializer_list<value_type> __il) 623 { 624 insert(__il.begin(), __il.end()); 625 } 626 627 template <class _Value, class _Hash, class _Pred, class _Alloc> 628 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 629 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 630 const key_equal& __eql) 631 : __table_(__hf, __eql) 632 { 633 __table_.rehash(__n); 634 insert(__il.begin(), __il.end()); 635 } 636 637 template <class _Value, class _Hash, class _Pred, class _Alloc> 638 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 639 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 640 const key_equal& __eql, const allocator_type& __a) 641 : __table_(__hf, __eql, __a) 642 { 643 __table_.rehash(__n); 644 insert(__il.begin(), __il.end()); 645 } 646 647 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 648 649 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 650 651 template <class _Value, class _Hash, class _Pred, class _Alloc> 652 inline _LIBCPP_INLINE_VISIBILITY 653 unordered_set<_Value, _Hash, _Pred, _Alloc>& 654 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 655 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 656 { 657 __table_ = _VSTD::move(__u.__table_); 658 return *this; 659 } 660 661 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 662 663 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 664 665 template <class _Value, class _Hash, class _Pred, class _Alloc> 666 inline _LIBCPP_INLINE_VISIBILITY 667 unordered_set<_Value, _Hash, _Pred, _Alloc>& 668 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=( 669 initializer_list<value_type> __il) 670 { 671 __table_.__assign_unique(__il.begin(), __il.end()); 672 return *this; 673 } 674 675 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 676 677 template <class _Value, class _Hash, class _Pred, class _Alloc> 678 template <class _InputIterator> 679 inline _LIBCPP_INLINE_VISIBILITY 680 void 681 unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 682 _InputIterator __last) 683 { 684 for (; __first != __last; ++__first) 685 __table_.__insert_unique(*__first); 686 } 687 688 template <class _Value, class _Hash, class _Pred, class _Alloc> 689 inline _LIBCPP_INLINE_VISIBILITY 690 void 691 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 692 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 693 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 694 { 695 __x.swap(__y); 696 } 697 698 template <class _Value, class _Hash, class _Pred, class _Alloc> 699 bool 700 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 701 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 702 { 703 if (__x.size() != __y.size()) 704 return false; 705 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 706 const_iterator; 707 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 708 __i != __ex; ++__i) 709 { 710 const_iterator __j = __y.find(*__i); 711 if (__j == __ey || !(*__i == *__j)) 712 return false; 713 } 714 return true; 715 } 716 717 template <class _Value, class _Hash, class _Pred, class _Alloc> 718 inline _LIBCPP_INLINE_VISIBILITY 719 bool 720 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 721 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 722 { 723 return !(__x == __y); 724 } 725 726 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 727 class _Alloc = allocator<_Value> > 728 class _LIBCPP_TYPE_VIS unordered_multiset 729 { 730 public: 731 // types 732 typedef _Value key_type; 733 typedef key_type value_type; 734 typedef _Hash hasher; 735 typedef _Pred key_equal; 736 typedef _Alloc allocator_type; 737 typedef value_type& reference; 738 typedef const value_type& const_reference; 739 740 private: 741 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 742 743 __table __table_; 744 745 public: 746 typedef typename __table::pointer pointer; 747 typedef typename __table::const_pointer const_pointer; 748 typedef typename __table::size_type size_type; 749 typedef typename __table::difference_type difference_type; 750 751 typedef typename __table::const_iterator iterator; 752 typedef typename __table::const_iterator const_iterator; 753 typedef typename __table::const_local_iterator local_iterator; 754 typedef typename __table::const_local_iterator const_local_iterator; 755 756 _LIBCPP_INLINE_VISIBILITY 757 unordered_multiset() 758 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 759 {} // = default 760 explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(), 761 const key_equal& __eql = key_equal()); 762 unordered_multiset(size_type __n, const hasher& __hf, 763 const key_equal& __eql, const allocator_type& __a); 764 template <class _InputIterator> 765 unordered_multiset(_InputIterator __first, _InputIterator __last); 766 template <class _InputIterator> 767 unordered_multiset(_InputIterator __first, _InputIterator __last, 768 size_type __n, const hasher& __hf = hasher(), 769 const key_equal& __eql = key_equal()); 770 template <class _InputIterator> 771 unordered_multiset(_InputIterator __first, _InputIterator __last, 772 size_type __n , const hasher& __hf, 773 const key_equal& __eql, const allocator_type& __a); 774 explicit unordered_multiset(const allocator_type& __a); 775 unordered_multiset(const unordered_multiset& __u); 776 unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 777 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 778 unordered_multiset(unordered_multiset&& __u) 779 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 780 unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 781 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 782 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 783 unordered_multiset(initializer_list<value_type> __il); 784 unordered_multiset(initializer_list<value_type> __il, size_type __n, 785 const hasher& __hf = hasher(), 786 const key_equal& __eql = key_equal()); 787 unordered_multiset(initializer_list<value_type> __il, size_type __n, 788 const hasher& __hf, const key_equal& __eql, 789 const allocator_type& __a); 790 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 791 // ~unordered_multiset() = default; 792 _LIBCPP_INLINE_VISIBILITY 793 unordered_multiset& operator=(const unordered_multiset& __u) 794 { 795 __table_ = __u.__table_; 796 return *this; 797 } 798 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 799 unordered_multiset& operator=(unordered_multiset&& __u) 800 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 801 #endif 802 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 803 unordered_multiset& operator=(initializer_list<value_type> __il); 804 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 805 806 _LIBCPP_INLINE_VISIBILITY 807 allocator_type get_allocator() const _NOEXCEPT 808 {return allocator_type(__table_.__node_alloc());} 809 810 _LIBCPP_INLINE_VISIBILITY 811 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 812 _LIBCPP_INLINE_VISIBILITY 813 size_type size() const _NOEXCEPT {return __table_.size();} 814 _LIBCPP_INLINE_VISIBILITY 815 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 816 817 _LIBCPP_INLINE_VISIBILITY 818 iterator begin() _NOEXCEPT {return __table_.begin();} 819 _LIBCPP_INLINE_VISIBILITY 820 iterator end() _NOEXCEPT {return __table_.end();} 821 _LIBCPP_INLINE_VISIBILITY 822 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 823 _LIBCPP_INLINE_VISIBILITY 824 const_iterator end() const _NOEXCEPT {return __table_.end();} 825 _LIBCPP_INLINE_VISIBILITY 826 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 827 _LIBCPP_INLINE_VISIBILITY 828 const_iterator cend() const _NOEXCEPT {return __table_.end();} 829 830 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 831 template <class... _Args> 832 _LIBCPP_INLINE_VISIBILITY 833 iterator emplace(_Args&&... __args) 834 {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 835 template <class... _Args> 836 _LIBCPP_INLINE_VISIBILITY 837 iterator emplace_hint(const_iterator __p, _Args&&... __args) 838 {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 839 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 840 _LIBCPP_INLINE_VISIBILITY 841 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 842 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 843 _LIBCPP_INLINE_VISIBILITY 844 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} 845 #endif 846 _LIBCPP_INLINE_VISIBILITY 847 iterator insert(const_iterator __p, const value_type& __x) 848 {return __table_.__insert_multi(__p, __x);} 849 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 850 _LIBCPP_INLINE_VISIBILITY 851 iterator insert(const_iterator __p, value_type&& __x) 852 {return __table_.__insert_multi(__p, _VSTD::move(__x));} 853 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 854 template <class _InputIterator> 855 void insert(_InputIterator __first, _InputIterator __last); 856 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 857 _LIBCPP_INLINE_VISIBILITY 858 void insert(initializer_list<value_type> __il) 859 {insert(__il.begin(), __il.end());} 860 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 861 862 _LIBCPP_INLINE_VISIBILITY 863 iterator erase(const_iterator __p) {return __table_.erase(__p);} 864 _LIBCPP_INLINE_VISIBILITY 865 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 866 _LIBCPP_INLINE_VISIBILITY 867 iterator erase(const_iterator __first, const_iterator __last) 868 {return __table_.erase(__first, __last);} 869 _LIBCPP_INLINE_VISIBILITY 870 void clear() _NOEXCEPT {__table_.clear();} 871 872 _LIBCPP_INLINE_VISIBILITY 873 void swap(unordered_multiset& __u) 874 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 875 {__table_.swap(__u.__table_);} 876 877 _LIBCPP_INLINE_VISIBILITY 878 hasher hash_function() const {return __table_.hash_function();} 879 _LIBCPP_INLINE_VISIBILITY 880 key_equal key_eq() const {return __table_.key_eq();} 881 882 _LIBCPP_INLINE_VISIBILITY 883 iterator find(const key_type& __k) {return __table_.find(__k);} 884 _LIBCPP_INLINE_VISIBILITY 885 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 886 _LIBCPP_INLINE_VISIBILITY 887 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 888 _LIBCPP_INLINE_VISIBILITY 889 pair<iterator, iterator> equal_range(const key_type& __k) 890 {return __table_.__equal_range_multi(__k);} 891 _LIBCPP_INLINE_VISIBILITY 892 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 893 {return __table_.__equal_range_multi(__k);} 894 895 _LIBCPP_INLINE_VISIBILITY 896 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 897 _LIBCPP_INLINE_VISIBILITY 898 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 899 900 _LIBCPP_INLINE_VISIBILITY 901 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 902 _LIBCPP_INLINE_VISIBILITY 903 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 904 905 _LIBCPP_INLINE_VISIBILITY 906 local_iterator begin(size_type __n) {return __table_.begin(__n);} 907 _LIBCPP_INLINE_VISIBILITY 908 local_iterator end(size_type __n) {return __table_.end(__n);} 909 _LIBCPP_INLINE_VISIBILITY 910 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 911 _LIBCPP_INLINE_VISIBILITY 912 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 913 _LIBCPP_INLINE_VISIBILITY 914 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 915 _LIBCPP_INLINE_VISIBILITY 916 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 917 918 _LIBCPP_INLINE_VISIBILITY 919 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 920 _LIBCPP_INLINE_VISIBILITY 921 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 922 _LIBCPP_INLINE_VISIBILITY 923 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 924 _LIBCPP_INLINE_VISIBILITY 925 void rehash(size_type __n) {__table_.rehash(__n);} 926 _LIBCPP_INLINE_VISIBILITY 927 void reserve(size_type __n) {__table_.reserve(__n);} 928 }; 929 930 template <class _Value, class _Hash, class _Pred, class _Alloc> 931 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 932 size_type __n, const hasher& __hf, const key_equal& __eql) 933 : __table_(__hf, __eql) 934 { 935 __table_.rehash(__n); 936 } 937 938 template <class _Value, class _Hash, class _Pred, class _Alloc> 939 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 940 size_type __n, const hasher& __hf, const key_equal& __eql, 941 const allocator_type& __a) 942 : __table_(__hf, __eql, __a) 943 { 944 __table_.rehash(__n); 945 } 946 947 template <class _Value, class _Hash, class _Pred, class _Alloc> 948 template <class _InputIterator> 949 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 950 _InputIterator __first, _InputIterator __last) 951 { 952 insert(__first, __last); 953 } 954 955 template <class _Value, class _Hash, class _Pred, class _Alloc> 956 template <class _InputIterator> 957 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 958 _InputIterator __first, _InputIterator __last, size_type __n, 959 const hasher& __hf, const key_equal& __eql) 960 : __table_(__hf, __eql) 961 { 962 __table_.rehash(__n); 963 insert(__first, __last); 964 } 965 966 template <class _Value, class _Hash, class _Pred, class _Alloc> 967 template <class _InputIterator> 968 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 969 _InputIterator __first, _InputIterator __last, size_type __n, 970 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 971 : __table_(__hf, __eql, __a) 972 { 973 __table_.rehash(__n); 974 insert(__first, __last); 975 } 976 977 template <class _Value, class _Hash, class _Pred, class _Alloc> 978 inline _LIBCPP_INLINE_VISIBILITY 979 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 980 const allocator_type& __a) 981 : __table_(__a) 982 { 983 } 984 985 template <class _Value, class _Hash, class _Pred, class _Alloc> 986 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 987 const unordered_multiset& __u) 988 : __table_(__u.__table_) 989 { 990 __table_.rehash(__u.bucket_count()); 991 insert(__u.begin(), __u.end()); 992 } 993 994 template <class _Value, class _Hash, class _Pred, class _Alloc> 995 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 996 const unordered_multiset& __u, const allocator_type& __a) 997 : __table_(__u.__table_, __a) 998 { 999 __table_.rehash(__u.bucket_count()); 1000 insert(__u.begin(), __u.end()); 1001 } 1002 1003 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1004 1005 template <class _Value, class _Hash, class _Pred, class _Alloc> 1006 inline _LIBCPP_INLINE_VISIBILITY 1007 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1008 unordered_multiset&& __u) 1009 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1010 : __table_(_VSTD::move(__u.__table_)) 1011 { 1012 } 1013 1014 template <class _Value, class _Hash, class _Pred, class _Alloc> 1015 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1016 unordered_multiset&& __u, const allocator_type& __a) 1017 : __table_(_VSTD::move(__u.__table_), __a) 1018 { 1019 if (__a != __u.get_allocator()) 1020 { 1021 iterator __i = __u.begin(); 1022 while (__u.size() != 0) 1023 __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 1024 } 1025 } 1026 1027 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1028 1029 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1030 1031 template <class _Value, class _Hash, class _Pred, class _Alloc> 1032 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1033 initializer_list<value_type> __il) 1034 { 1035 insert(__il.begin(), __il.end()); 1036 } 1037 1038 template <class _Value, class _Hash, class _Pred, class _Alloc> 1039 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1040 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1041 const key_equal& __eql) 1042 : __table_(__hf, __eql) 1043 { 1044 __table_.rehash(__n); 1045 insert(__il.begin(), __il.end()); 1046 } 1047 1048 template <class _Value, class _Hash, class _Pred, class _Alloc> 1049 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1050 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1051 const key_equal& __eql, const allocator_type& __a) 1052 : __table_(__hf, __eql, __a) 1053 { 1054 __table_.rehash(__n); 1055 insert(__il.begin(), __il.end()); 1056 } 1057 1058 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1059 1060 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1061 1062 template <class _Value, class _Hash, class _Pred, class _Alloc> 1063 inline _LIBCPP_INLINE_VISIBILITY 1064 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1065 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1066 unordered_multiset&& __u) 1067 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1068 { 1069 __table_ = _VSTD::move(__u.__table_); 1070 return *this; 1071 } 1072 1073 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1074 1075 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1076 1077 template <class _Value, class _Hash, class _Pred, class _Alloc> 1078 inline 1079 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1080 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1081 initializer_list<value_type> __il) 1082 { 1083 __table_.__assign_multi(__il.begin(), __il.end()); 1084 return *this; 1085 } 1086 1087 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1088 1089 template <class _Value, class _Hash, class _Pred, class _Alloc> 1090 template <class _InputIterator> 1091 inline _LIBCPP_INLINE_VISIBILITY 1092 void 1093 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1094 _InputIterator __last) 1095 { 1096 for (; __first != __last; ++__first) 1097 __table_.__insert_multi(*__first); 1098 } 1099 1100 template <class _Value, class _Hash, class _Pred, class _Alloc> 1101 inline _LIBCPP_INLINE_VISIBILITY 1102 void 1103 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1104 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1105 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1106 { 1107 __x.swap(__y); 1108 } 1109 1110 template <class _Value, class _Hash, class _Pred, class _Alloc> 1111 bool 1112 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1113 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1114 { 1115 if (__x.size() != __y.size()) 1116 return false; 1117 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 1118 const_iterator; 1119 typedef pair<const_iterator, const_iterator> _EqRng; 1120 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 1121 { 1122 _EqRng __xeq = __x.equal_range(*__i); 1123 _EqRng __yeq = __y.equal_range(*__i); 1124 if (_VSTD::distance(__xeq.first, __xeq.second) != 1125 _VSTD::distance(__yeq.first, __yeq.second) || 1126 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1127 return false; 1128 __i = __xeq.second; 1129 } 1130 return true; 1131 } 1132 1133 template <class _Value, class _Hash, class _Pred, class _Alloc> 1134 inline _LIBCPP_INLINE_VISIBILITY 1135 bool 1136 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1137 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1138 { 1139 return !(__x == __y); 1140 } 1141 1142 _LIBCPP_END_NAMESPACE_STD 1143 1144 #endif // _LIBCPP_UNORDERED_SET 1145
