1 2 // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. 3 // Copyright (C) 2005-2011 Daniel James. 4 // Distributed under the Boost Software License, Version 1.0. (See accompanying 5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6 7 // See http://www.boost.org/libs/unordered for documentation 8 9 #ifndef BOOST_UNORDERED_UNORDERED_SET_HPP_INCLUDED 10 #define BOOST_UNORDERED_UNORDERED_SET_HPP_INCLUDED 11 12 #include <boost/config.hpp> 13 #if defined(BOOST_HAS_PRAGMA_ONCE) 14 #pragma once 15 #endif 16 17 #include <boost/core/explicit_operator_bool.hpp> 18 #include <boost/functional/hash.hpp> 19 #include <boost/move/move.hpp> 20 #include <boost/unordered/detail/set.hpp> 21 22 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 23 #include <initializer_list> 24 #endif 25 26 #if defined(BOOST_MSVC) 27 #pragma warning(push) 28 // conditional expression is constant 29 #pragma warning(disable : 4127) 30 #if BOOST_MSVC >= 1400 31 // the inline specifier cannot be used when a friend declaration refers to a 32 // specialization of a function template 33 #pragma warning(disable : 4396) 34 #endif 35 #endif 36 37 namespace boost { 38 namespace unordered { 39 template <class T, class H, class P, class A> class unordered_set 40 { 41 #if defined(BOOST_UNORDERED_USE_MOVE) 42 BOOST_COPYABLE_AND_MOVABLE(unordered_set) 43 #endif 44 template <typename, typename, typename, typename> 45 friend class unordered_multiset; 46 47 public: 48 typedef T key_type; 49 typedef T value_type; 50 typedef H hasher; 51 typedef P key_equal; 52 typedef A allocator_type; 53 54 private: 55 typedef boost::unordered::detail::set<A, T, H, P> types; 56 typedef typename types::value_allocator_traits value_allocator_traits; 57 typedef typename types::table table; 58 typedef typename table::node_pointer node_pointer; 59 typedef typename table::link_pointer link_pointer; 60 61 public: 62 typedef typename value_allocator_traits::pointer pointer; 63 typedef typename value_allocator_traits::const_pointer const_pointer; 64 65 typedef value_type& reference; 66 typedef value_type const& const_reference; 67 68 typedef std::size_t size_type; 69 typedef std::ptrdiff_t difference_type; 70 71 typedef typename table::iterator iterator; 72 typedef typename table::c_iterator const_iterator; 73 typedef typename table::l_iterator local_iterator; 74 typedef typename table::cl_iterator const_local_iterator; 75 typedef typename types::node_type node_type; 76 typedef typename types::insert_return_type insert_return_type; 77 78 private: 79 table table_; 80 81 public: 82 // constructors 83 84 unordered_set(); 85 86 explicit unordered_set(size_type, const hasher& = hasher(), 87 const key_equal& = key_equal(), 88 const allocator_type& = allocator_type()); 89 90 template <class InputIt> 91 unordered_set(InputIt, InputIt, 92 size_type = boost::unordered::detail::default_bucket_count, 93 const hasher& = hasher(), const key_equal& = key_equal(), 94 const allocator_type& = allocator_type()); 95 96 unordered_set(unordered_set const&); 97 98 #if defined(BOOST_UNORDERED_USE_MOVE) || \ 99 !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 100 unordered_set(BOOST_RV_REF(unordered_set) other) BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)101 BOOST_NOEXCEPT_IF(table::nothrow_move_constructible) 102 : table_(other.table_, boost::unordered::detail::move_tag()) 103 { 104 // The move is done in table_ 105 } 106 #endif 107 108 explicit unordered_set(allocator_type const&); 109 110 unordered_set(unordered_set const&, allocator_type const&); 111 112 unordered_set(BOOST_RV_REF(unordered_set), allocator_type const&); 113 114 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 115 unordered_set(std::initializer_list<value_type>, 116 size_type = boost::unordered::detail::default_bucket_count, 117 const hasher& = hasher(), const key_equal& l = key_equal(), 118 const allocator_type& = allocator_type()); 119 #endif 120 121 explicit unordered_set(size_type, const allocator_type&); 122 123 explicit unordered_set(size_type, const hasher&, const allocator_type&); 124 125 template <class InputIt> 126 unordered_set(InputIt, InputIt, size_type, const allocator_type&); 127 128 template <class InputIt> 129 unordered_set( 130 InputIt, InputIt, size_type, const hasher&, const allocator_type&); 131 132 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 133 unordered_set( 134 std::initializer_list<value_type>, size_type, const allocator_type&); 135 136 unordered_set(std::initializer_list<value_type>, size_type, const hasher&, 137 const allocator_type&); 138 #endif 139 140 // Destructor 141 142 ~unordered_set() BOOST_NOEXCEPT; 143 144 // Assign 145 146 #if defined(BOOST_UNORDERED_USE_MOVE) operator =(BOOST_COPY_ASSIGN_REF (unordered_set)x)147 unordered_set& operator=(BOOST_COPY_ASSIGN_REF(unordered_set) x) 148 { 149 table_.assign(x.table_, boost::unordered::detail::true_type()); 150 return *this; 151 } 152 operator =(BOOST_RV_REF (unordered_set)x)153 unordered_set& operator=(BOOST_RV_REF(unordered_set) x) 154 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 155 boost::is_nothrow_move_assignable<H>::value&& 156 boost::is_nothrow_move_assignable<P>::value) 157 { 158 table_.move_assign(x.table_, boost::unordered::detail::true_type()); 159 return *this; 160 } 161 #else operator =(unordered_set const & x)162 unordered_set& operator=(unordered_set const& x) 163 { 164 table_.assign(x.table_, boost::unordered::detail::true_type()); 165 return *this; 166 } 167 168 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) operator =(unordered_set && x)169 unordered_set& operator=(unordered_set&& x) 170 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 171 boost::is_nothrow_move_assignable<H>::value&& 172 boost::is_nothrow_move_assignable<P>::value) 173 { 174 table_.move_assign(x.table_, boost::unordered::detail::true_type()); 175 return *this; 176 } 177 #endif 178 #endif 179 180 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 181 unordered_set& operator=(std::initializer_list<value_type>); 182 #endif 183 get_allocator() const184 allocator_type get_allocator() const BOOST_NOEXCEPT 185 { 186 return table_.node_alloc(); 187 } 188 189 // iterators 190 begin()191 iterator begin() BOOST_NOEXCEPT { return iterator(table_.begin()); } 192 begin() const193 const_iterator begin() const BOOST_NOEXCEPT 194 { 195 return const_iterator(table_.begin()); 196 } 197 end()198 iterator end() BOOST_NOEXCEPT { return iterator(); } 199 end() const200 const_iterator end() const BOOST_NOEXCEPT { return const_iterator(); } 201 cbegin() const202 const_iterator cbegin() const BOOST_NOEXCEPT 203 { 204 return const_iterator(table_.begin()); 205 } 206 cend() const207 const_iterator cend() const BOOST_NOEXCEPT { return const_iterator(); } 208 209 // size and capacity 210 empty() const211 bool empty() const BOOST_NOEXCEPT { return table_.size_ == 0; } 212 size() const213 size_type size() const BOOST_NOEXCEPT { return table_.size_; } 214 215 size_type max_size() const BOOST_NOEXCEPT; 216 217 // emplace 218 219 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 220 221 template <class... Args> emplace(BOOST_FWD_REF (Args)...args)222 std::pair<iterator, bool> emplace(BOOST_FWD_REF(Args)... args) 223 { 224 return table_.emplace_unique( 225 table::extractor::extract(boost::forward<Args>(args)...), 226 boost::forward<Args>(args)...); 227 } 228 229 #else 230 231 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1 232 233 // 0 argument emplace requires special treatment in case 234 // the container is instantiated with a value type that 235 // doesn't have a default constructor. 236 emplace(boost::unordered::detail::empty_emplace=boost::unordered::detail::empty_emplace (),value_type v=value_type ())237 std::pair<iterator, bool> emplace( 238 boost::unordered::detail::empty_emplace = 239 boost::unordered::detail::empty_emplace(), 240 value_type v = value_type()) 241 { 242 return this->emplace(boost::move(v)); 243 } 244 245 #endif 246 247 template <typename A0> emplace(BOOST_FWD_REF (A0)a0)248 std::pair<iterator, bool> emplace(BOOST_FWD_REF(A0) a0) 249 { 250 return table_.emplace_unique( 251 table::extractor::extract(boost::forward<A0>(a0)), 252 boost::unordered::detail::create_emplace_args( 253 boost::forward<A0>(a0))); 254 } 255 256 template <typename A0, typename A1> emplace(BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1)257 std::pair<iterator, bool> emplace( 258 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1) 259 { 260 return table_.emplace_unique( 261 table::extractor::extract( 262 boost::forward<A0>(a0), boost::forward<A1>(a1)), 263 boost::unordered::detail::create_emplace_args( 264 boost::forward<A0>(a0), boost::forward<A1>(a1))); 265 } 266 267 template <typename A0, typename A1, typename A2> emplace(BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1,BOOST_FWD_REF (A2)a2)268 std::pair<iterator, bool> emplace( 269 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 270 { 271 return table_.emplace_unique( 272 table::extractor::extract( 273 boost::forward<A0>(a0), boost::forward<A1>(a1)), 274 boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0), 275 boost::forward<A1>(a1), boost::forward<A2>(a2))); 276 } 277 278 #endif 279 280 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 281 282 template <class... Args> emplace_hint(const_iterator hint,BOOST_FWD_REF (Args)...args)283 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args) 284 { 285 return table_.emplace_hint_unique(hint, 286 table::extractor::extract(boost::forward<Args>(args)...), 287 boost::forward<Args>(args)...); 288 } 289 290 #else 291 292 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1 293 emplace_hint(const_iterator hint,boost::unordered::detail::empty_emplace=boost::unordered::detail::empty_emplace (),value_type v=value_type ())294 iterator emplace_hint(const_iterator hint, 295 boost::unordered::detail::empty_emplace = 296 boost::unordered::detail::empty_emplace(), 297 value_type v = value_type()) 298 { 299 return this->emplace_hint(hint, boost::move(v)); 300 } 301 302 #endif 303 304 template <typename A0> emplace_hint(const_iterator hint,BOOST_FWD_REF (A0)a0)305 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0) 306 { 307 return table_.emplace_hint_unique(hint, 308 table::extractor::extract(boost::forward<A0>(a0)), 309 boost::unordered::detail::create_emplace_args( 310 boost::forward<A0>(a0))); 311 } 312 313 template <typename A0, typename A1> emplace_hint(const_iterator hint,BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1)314 iterator emplace_hint( 315 const_iterator hint, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1) 316 { 317 return table_.emplace_hint_unique(hint, 318 table::extractor::extract( 319 boost::forward<A0>(a0), boost::forward<A1>(a1)), 320 boost::unordered::detail::create_emplace_args( 321 boost::forward<A0>(a0), boost::forward<A1>(a1))); 322 } 323 324 template <typename A0, typename A1, typename A2> emplace_hint(const_iterator hint,BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1,BOOST_FWD_REF (A2)a2)325 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0, 326 BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 327 { 328 return table_.emplace_hint_unique(hint, 329 table::extractor::extract( 330 boost::forward<A0>(a0), boost::forward<A1>(a1)), 331 boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0), 332 boost::forward<A1>(a1), boost::forward<A2>(a2))); 333 } 334 335 #endif 336 337 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 338 339 #define BOOST_UNORDERED_EMPLACE(z, n, _) \ 340 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 341 std::pair<iterator, bool> emplace( \ 342 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \ 343 { \ 344 return table_.emplace_unique( \ 345 table::extractor::extract( \ 346 boost::forward<A0>(a0), boost::forward<A1>(a1)), \ 347 boost::unordered::detail::create_emplace_args( \ 348 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \ 349 } \ 350 \ 351 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 352 iterator emplace_hint( \ 353 const_iterator hint, BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \ 354 { \ 355 return table_.emplace_hint_unique(hint, \ 356 table::extractor::extract( \ 357 boost::forward<A0>(a0), boost::forward<A1>(a1)), \ 358 boost::unordered::detail::create_emplace_args( \ 359 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \ 360 } 361 362 BOOST_UNORDERED_EMPLACE(1, 4, _) 363 BOOST_UNORDERED_EMPLACE(1, 5, _) 364 BOOST_UNORDERED_EMPLACE(1, 6, _) 365 BOOST_UNORDERED_EMPLACE(1, 7, _) 366 BOOST_UNORDERED_EMPLACE(1, 8, _) 367 BOOST_UNORDERED_EMPLACE(1, 9, _) BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT)368 BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT), 369 BOOST_UNORDERED_EMPLACE, _) 370 371 #undef BOOST_UNORDERED_EMPLACE 372 373 #endif 374 375 std::pair<iterator, bool> insert(value_type const& x) 376 { 377 return this->emplace(x); 378 } 379 insert(BOOST_UNORDERED_RV_REF (value_type)x)380 std::pair<iterator, bool> insert(BOOST_UNORDERED_RV_REF(value_type) x) 381 { 382 return this->emplace(boost::move(x)); 383 } 384 insert(const_iterator hint,value_type const & x)385 iterator insert(const_iterator hint, value_type const& x) 386 { 387 return this->emplace_hint(hint, x); 388 } 389 insert(const_iterator hint,BOOST_UNORDERED_RV_REF (value_type)x)390 iterator insert(const_iterator hint, BOOST_UNORDERED_RV_REF(value_type) x) 391 { 392 return this->emplace_hint(hint, boost::move(x)); 393 } 394 395 template <class InputIt> void insert(InputIt, InputIt); 396 397 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 398 void insert(std::initializer_list<value_type>); 399 #endif 400 401 // extract 402 extract(const_iterator position)403 node_type extract(const_iterator position) 404 { 405 return node_type( 406 table_.extract_by_iterator_unique(position), table_.node_alloc()); 407 } 408 extract(const key_type & k)409 node_type extract(const key_type& k) 410 { 411 return node_type(table_.extract_by_key(k), table_.node_alloc()); 412 } 413 insert(BOOST_RV_REF (node_type)np)414 insert_return_type insert(BOOST_RV_REF(node_type) np) 415 { 416 insert_return_type result; 417 table_.move_insert_node_type_unique(np, result); 418 return boost::move(result); 419 } 420 insert(const_iterator hint,BOOST_RV_REF (node_type)np)421 iterator insert(const_iterator hint, BOOST_RV_REF(node_type) np) 422 { 423 return table_.move_insert_node_type_with_hint_unique(hint, np); 424 } 425 426 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || \ 427 (BOOST_COMP_GNUC && BOOST_COMP_GNUC < BOOST_VERSION_NUMBER(4, 6, 0)) 428 private: 429 // Note: Use r-value node_type to insert. 430 insert_return_type insert(node_type&); 431 iterator insert(const_iterator, node_type& np); 432 433 public: 434 #endif 435 436 iterator erase(const_iterator); 437 size_type erase(const key_type&); 438 iterator erase(const_iterator, const_iterator); 439 BOOST_UNORDERED_DEPRECATED("Use erase instead") quick_erase(const_iterator it)440 void quick_erase(const_iterator it) { erase(it); } 441 BOOST_UNORDERED_DEPRECATED("Use erase instead") erase_return_void(const_iterator it)442 void erase_return_void(const_iterator it) { erase(it); } 443 444 void swap(unordered_set&) 445 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 446 boost::is_nothrow_swappable<H>::value&& 447 boost::is_nothrow_swappable<P>::value); clear()448 void clear() BOOST_NOEXCEPT { table_.clear_impl(); } 449 450 template <typename H2, typename P2> 451 void merge(boost::unordered_set<T, H2, P2, A>& source); 452 453 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 454 template <typename H2, typename P2> 455 void merge(boost::unordered_set<T, H2, P2, A>&& source); 456 #endif 457 458 template <typename H2, typename P2> 459 void merge(boost::unordered_multiset<T, H2, P2, A>& source); 460 461 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 462 template <typename H2, typename P2> 463 void merge(boost::unordered_multiset<T, H2, P2, A>&& source); 464 #endif 465 466 // observers 467 468 hasher hash_function() const; 469 key_equal key_eq() const; 470 471 // lookup 472 473 const_iterator find(const key_type&) const; 474 475 template <class CompatibleKey, class CompatibleHash, 476 class CompatiblePredicate> 477 const_iterator find(CompatibleKey const&, CompatibleHash const&, 478 CompatiblePredicate const&) const; 479 480 size_type count(const key_type&) const; 481 482 std::pair<const_iterator, const_iterator> equal_range( 483 const key_type&) const; 484 485 // bucket interface 486 bucket_count() const487 size_type bucket_count() const BOOST_NOEXCEPT 488 { 489 return table_.bucket_count_; 490 } 491 max_bucket_count() const492 size_type max_bucket_count() const BOOST_NOEXCEPT 493 { 494 return table_.max_bucket_count(); 495 } 496 497 size_type bucket_size(size_type) const; 498 bucket(const key_type & k) const499 size_type bucket(const key_type& k) const 500 { 501 return table_.hash_to_bucket(table_.hash(k)); 502 } 503 begin(size_type n)504 local_iterator begin(size_type n) 505 { 506 return local_iterator(table_.begin(n), n, table_.bucket_count_); 507 } 508 begin(size_type n) const509 const_local_iterator begin(size_type n) const 510 { 511 return const_local_iterator(table_.begin(n), n, table_.bucket_count_); 512 } 513 end(size_type)514 local_iterator end(size_type) { return local_iterator(); } 515 end(size_type) const516 const_local_iterator end(size_type) const 517 { 518 return const_local_iterator(); 519 } 520 cbegin(size_type n) const521 const_local_iterator cbegin(size_type n) const 522 { 523 return const_local_iterator(table_.begin(n), n, table_.bucket_count_); 524 } 525 cend(size_type) const526 const_local_iterator cend(size_type) const 527 { 528 return const_local_iterator(); 529 } 530 531 // hash policy 532 533 float load_factor() const BOOST_NOEXCEPT; max_load_factor() const534 float max_load_factor() const BOOST_NOEXCEPT { return table_.mlf_; } 535 void max_load_factor(float) BOOST_NOEXCEPT; 536 void rehash(size_type); 537 void reserve(size_type); 538 539 #if !BOOST_WORKAROUND(BOOST_BORLANDC, < 0x0582) 540 friend bool operator== 541 <T, H, P, A>(unordered_set const&, unordered_set const&); 542 friend bool operator!= 543 <T, H, P, A>(unordered_set const&, unordered_set const&); 544 #endif 545 }; // class template unordered_set 546 547 #if BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES 548 549 template <class InputIterator, 550 class Hash = 551 boost::hash<typename std::iterator_traits<InputIterator>::value_type>, 552 class Pred = 553 std::equal_to<typename std::iterator_traits<InputIterator>::value_type>, 554 class Allocator = std::allocator< 555 typename std::iterator_traits<InputIterator>::value_type> > 556 unordered_set(InputIterator, InputIterator, 557 std::size_t = boost::unordered::detail::default_bucket_count, 558 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 559 ->unordered_set<typename std::iterator_traits<InputIterator>::value_type, 560 Hash, Pred, Allocator>; 561 562 template <class T, class Hash = boost::hash<T>, 563 class Pred = std::equal_to<T>, class Allocator = std::allocator<T> > 564 unordered_set(std::initializer_list<T>, 565 std::size_t = boost::unordered::detail::default_bucket_count, 566 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 567 ->unordered_set<T, Hash, Pred, Allocator>; 568 569 template <class InputIterator, class Allocator> 570 unordered_set(InputIterator, InputIterator, std::size_t, Allocator) 571 ->unordered_set<typename std::iterator_traits<InputIterator>::value_type, 572 boost::hash<typename std::iterator_traits<InputIterator>::value_type>, 573 std::equal_to<typename std::iterator_traits<InputIterator>::value_type>, 574 Allocator>; 575 576 template <class InputIterator, class Hash, class Allocator> 577 unordered_set(InputIterator, InputIterator, std::size_t, Hash, Allocator) 578 ->unordered_set<typename std::iterator_traits<InputIterator>::value_type, 579 Hash, 580 std::equal_to<typename std::iterator_traits<InputIterator>::value_type>, 581 Allocator>; 582 583 template <class T, class Allocator> 584 unordered_set(std::initializer_list<T>, std::size_t, Allocator) 585 ->unordered_set<T, boost::hash<T>, std::equal_to<T>, Allocator>; 586 587 template <class T, class Hash, class Allocator> 588 unordered_set(std::initializer_list<T>, std::size_t, Hash, Allocator) 589 ->unordered_set<T, Hash, std::equal_to<T>, Allocator>; 590 591 #endif 592 593 template <class T, class H, class P, class A> class unordered_multiset 594 { 595 #if defined(BOOST_UNORDERED_USE_MOVE) 596 BOOST_COPYABLE_AND_MOVABLE(unordered_multiset) 597 #endif 598 template <typename, typename, typename, typename> 599 friend class unordered_set; 600 601 public: 602 typedef T key_type; 603 typedef T value_type; 604 typedef H hasher; 605 typedef P key_equal; 606 typedef A allocator_type; 607 608 private: 609 typedef boost::unordered::detail::set<A, T, H, P> types; 610 typedef typename types::value_allocator_traits value_allocator_traits; 611 typedef typename types::table table; 612 typedef typename table::node_pointer node_pointer; 613 typedef typename table::link_pointer link_pointer; 614 615 public: 616 typedef typename value_allocator_traits::pointer pointer; 617 typedef typename value_allocator_traits::const_pointer const_pointer; 618 619 typedef value_type& reference; 620 typedef value_type const& const_reference; 621 622 typedef std::size_t size_type; 623 typedef std::ptrdiff_t difference_type; 624 625 typedef typename table::iterator iterator; 626 typedef typename table::c_iterator const_iterator; 627 typedef typename table::l_iterator local_iterator; 628 typedef typename table::cl_iterator const_local_iterator; 629 typedef typename types::node_type node_type; 630 631 private: 632 table table_; 633 634 public: 635 // constructors 636 637 unordered_multiset(); 638 639 explicit unordered_multiset(size_type, const hasher& = hasher(), 640 const key_equal& = key_equal(), 641 const allocator_type& = allocator_type()); 642 643 template <class InputIt> 644 unordered_multiset(InputIt, InputIt, 645 size_type = boost::unordered::detail::default_bucket_count, 646 const hasher& = hasher(), const key_equal& = key_equal(), 647 const allocator_type& = allocator_type()); 648 649 unordered_multiset(unordered_multiset const&); 650 651 #if defined(BOOST_UNORDERED_USE_MOVE) || \ 652 !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 653 unordered_multiset(BOOST_RV_REF(unordered_multiset) other) BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)654 BOOST_NOEXCEPT_IF(table::nothrow_move_constructible) 655 : table_(other.table_, boost::unordered::detail::move_tag()) 656 { 657 // The move is done in table_ 658 } 659 #endif 660 661 explicit unordered_multiset(allocator_type const&); 662 663 unordered_multiset(unordered_multiset const&, allocator_type const&); 664 665 unordered_multiset( 666 BOOST_RV_REF(unordered_multiset), allocator_type const&); 667 668 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 669 unordered_multiset(std::initializer_list<value_type>, 670 size_type = boost::unordered::detail::default_bucket_count, 671 const hasher& = hasher(), const key_equal& l = key_equal(), 672 const allocator_type& = allocator_type()); 673 #endif 674 675 explicit unordered_multiset(size_type, const allocator_type&); 676 677 explicit unordered_multiset( 678 size_type, const hasher&, const allocator_type&); 679 680 template <class InputIt> 681 unordered_multiset(InputIt, InputIt, size_type, const allocator_type&); 682 683 template <class InputIt> 684 unordered_multiset( 685 InputIt, InputIt, size_type, const hasher&, const allocator_type&); 686 687 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 688 unordered_multiset( 689 std::initializer_list<value_type>, size_type, const allocator_type&); 690 691 unordered_multiset(std::initializer_list<value_type>, size_type, 692 const hasher&, const allocator_type&); 693 #endif 694 695 // Destructor 696 697 ~unordered_multiset() BOOST_NOEXCEPT; 698 699 // Assign 700 701 #if defined(BOOST_UNORDERED_USE_MOVE) operator =(BOOST_COPY_ASSIGN_REF (unordered_multiset)x)702 unordered_multiset& operator=(BOOST_COPY_ASSIGN_REF(unordered_multiset) x) 703 { 704 table_.assign(x.table_, boost::unordered::detail::false_type()); 705 return *this; 706 } 707 operator =(BOOST_RV_REF (unordered_multiset)x)708 unordered_multiset& operator=(BOOST_RV_REF(unordered_multiset) x) 709 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 710 boost::is_nothrow_move_assignable<H>::value&& 711 boost::is_nothrow_move_assignable<P>::value) 712 { 713 table_.move_assign(x.table_, boost::unordered::detail::false_type()); 714 return *this; 715 } 716 #else operator =(unordered_multiset const & x)717 unordered_multiset& operator=(unordered_multiset const& x) 718 { 719 table_.assign(x.table_, boost::unordered::detail::false_type()); 720 return *this; 721 } 722 723 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) operator =(unordered_multiset && x)724 unordered_multiset& operator=(unordered_multiset&& x) 725 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 726 boost::is_nothrow_move_assignable<H>::value&& 727 boost::is_nothrow_move_assignable<P>::value) 728 { 729 table_.move_assign(x.table_, boost::unordered::detail::false_type()); 730 return *this; 731 } 732 #endif 733 #endif 734 735 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 736 unordered_multiset& operator=(std::initializer_list<value_type>); 737 #endif 738 get_allocator() const739 allocator_type get_allocator() const BOOST_NOEXCEPT 740 { 741 return table_.node_alloc(); 742 } 743 744 // iterators 745 begin()746 iterator begin() BOOST_NOEXCEPT { return iterator(table_.begin()); } 747 begin() const748 const_iterator begin() const BOOST_NOEXCEPT 749 { 750 return const_iterator(table_.begin()); 751 } 752 end()753 iterator end() BOOST_NOEXCEPT { return iterator(); } 754 end() const755 const_iterator end() const BOOST_NOEXCEPT { return const_iterator(); } 756 cbegin() const757 const_iterator cbegin() const BOOST_NOEXCEPT 758 { 759 return const_iterator(table_.begin()); 760 } 761 cend() const762 const_iterator cend() const BOOST_NOEXCEPT { return const_iterator(); } 763 764 // size and capacity 765 empty() const766 bool empty() const BOOST_NOEXCEPT { return table_.size_ == 0; } 767 size() const768 size_type size() const BOOST_NOEXCEPT { return table_.size_; } 769 770 size_type max_size() const BOOST_NOEXCEPT; 771 772 // emplace 773 774 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 775 emplace(BOOST_FWD_REF (Args)...args)776 template <class... Args> iterator emplace(BOOST_FWD_REF(Args)... args) 777 { 778 return iterator(table_.emplace_equiv( 779 boost::unordered::detail::func::construct_node_from_args( 780 table_.node_alloc(), boost::forward<Args>(args)...))); 781 } 782 783 #else 784 785 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1 786 787 // 0 argument emplace requires special treatment in case 788 // the container is instantiated with a value type that 789 // doesn't have a default constructor. 790 emplace(boost::unordered::detail::empty_emplace=boost::unordered::detail::empty_emplace (),value_type v=value_type ())791 iterator emplace(boost::unordered::detail::empty_emplace = 792 boost::unordered::detail::empty_emplace(), 793 value_type v = value_type()) 794 { 795 return this->emplace(boost::move(v)); 796 } 797 798 #endif 799 emplace(BOOST_FWD_REF (A0)a0)800 template <typename A0> iterator emplace(BOOST_FWD_REF(A0) a0) 801 { 802 return iterator(table_.emplace_equiv( 803 boost::unordered::detail::func::construct_node_from_args( 804 table_.node_alloc(), boost::unordered::detail::create_emplace_args( 805 boost::forward<A0>(a0))))); 806 } 807 808 template <typename A0, typename A1> emplace(BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1)809 iterator emplace(BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1) 810 { 811 return iterator(table_.emplace_equiv( 812 boost::unordered::detail::func::construct_node_from_args( 813 table_.node_alloc(), 814 boost::unordered::detail::create_emplace_args( 815 boost::forward<A0>(a0), boost::forward<A1>(a1))))); 816 } 817 818 template <typename A0, typename A1, typename A2> emplace(BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1,BOOST_FWD_REF (A2)a2)819 iterator emplace( 820 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 821 { 822 return iterator(table_.emplace_equiv( 823 boost::unordered::detail::func::construct_node_from_args( 824 table_.node_alloc(), 825 boost::unordered::detail::create_emplace_args( 826 boost::forward<A0>(a0), boost::forward<A1>(a1), 827 boost::forward<A2>(a2))))); 828 } 829 830 #endif 831 832 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 833 834 template <class... Args> emplace_hint(const_iterator hint,BOOST_FWD_REF (Args)...args)835 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args) 836 { 837 return iterator(table_.emplace_hint_equiv( 838 hint, boost::unordered::detail::func::construct_node_from_args( 839 table_.node_alloc(), boost::forward<Args>(args)...))); 840 } 841 842 #else 843 844 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1 845 emplace_hint(const_iterator hint,boost::unordered::detail::empty_emplace=boost::unordered::detail::empty_emplace (),value_type v=value_type ())846 iterator emplace_hint(const_iterator hint, 847 boost::unordered::detail::empty_emplace = 848 boost::unordered::detail::empty_emplace(), 849 value_type v = value_type()) 850 { 851 return this->emplace_hint(hint, boost::move(v)); 852 } 853 854 #endif 855 856 template <typename A0> emplace_hint(const_iterator hint,BOOST_FWD_REF (A0)a0)857 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0) 858 { 859 return iterator(table_.emplace_hint_equiv(hint, 860 boost::unordered::detail::func::construct_node_from_args( 861 table_.node_alloc(), boost::unordered::detail::create_emplace_args( 862 boost::forward<A0>(a0))))); 863 } 864 865 template <typename A0, typename A1> emplace_hint(const_iterator hint,BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1)866 iterator emplace_hint( 867 const_iterator hint, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1) 868 { 869 return iterator(table_.emplace_hint_equiv( 870 hint, boost::unordered::detail::func::construct_node_from_args( 871 table_.node_alloc(), 872 boost::unordered::detail::create_emplace_args( 873 boost::forward<A0>(a0), boost::forward<A1>(a1))))); 874 } 875 876 template <typename A0, typename A1, typename A2> emplace_hint(const_iterator hint,BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1,BOOST_FWD_REF (A2)a2)877 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0, 878 BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 879 { 880 return iterator(table_.emplace_hint_equiv( 881 hint, boost::unordered::detail::func::construct_node_from_args( 882 table_.node_alloc(), 883 boost::unordered::detail::create_emplace_args( 884 boost::forward<A0>(a0), boost::forward<A1>(a1), 885 boost::forward<A2>(a2))))); 886 } 887 888 #endif 889 890 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 891 892 #define BOOST_UNORDERED_EMPLACE(z, n, _) \ 893 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 894 iterator emplace(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \ 895 { \ 896 return iterator(table_.emplace_equiv( \ 897 boost::unordered::detail::func::construct_node_from_args( \ 898 table_.node_alloc(), \ 899 boost::unordered::detail::create_emplace_args( \ 900 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))))); \ 901 } \ 902 \ 903 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 904 iterator emplace_hint( \ 905 const_iterator hint, BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \ 906 { \ 907 return iterator(table_.emplace_hint_equiv( \ 908 hint, boost::unordered::detail::func::construct_node_from_args( \ 909 table_.node_alloc(), \ 910 boost::unordered::detail::create_emplace_args( \ 911 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))))); \ 912 } 913 914 BOOST_UNORDERED_EMPLACE(1, 4, _) 915 BOOST_UNORDERED_EMPLACE(1, 5, _) 916 BOOST_UNORDERED_EMPLACE(1, 6, _) 917 BOOST_UNORDERED_EMPLACE(1, 7, _) 918 BOOST_UNORDERED_EMPLACE(1, 8, _) 919 BOOST_UNORDERED_EMPLACE(1, 9, _) BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT)920 BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT), 921 BOOST_UNORDERED_EMPLACE, _) 922 923 #undef BOOST_UNORDERED_EMPLACE 924 925 #endif 926 927 iterator insert(value_type const& x) { return this->emplace(x); } 928 insert(BOOST_UNORDERED_RV_REF (value_type)x)929 iterator insert(BOOST_UNORDERED_RV_REF(value_type) x) 930 { 931 return this->emplace(boost::move(x)); 932 } 933 insert(const_iterator hint,value_type const & x)934 iterator insert(const_iterator hint, value_type const& x) 935 { 936 return this->emplace_hint(hint, x); 937 } 938 insert(const_iterator hint,BOOST_UNORDERED_RV_REF (value_type)x)939 iterator insert(const_iterator hint, BOOST_UNORDERED_RV_REF(value_type) x) 940 { 941 return this->emplace_hint(hint, boost::move(x)); 942 } 943 944 template <class InputIt> void insert(InputIt, InputIt); 945 946 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 947 void insert(std::initializer_list<value_type>); 948 #endif 949 950 // extract 951 extract(const_iterator position)952 node_type extract(const_iterator position) 953 { 954 return node_type( 955 table_.extract_by_iterator_equiv(position), table_.node_alloc()); 956 } 957 extract(const key_type & k)958 node_type extract(const key_type& k) 959 { 960 return node_type(table_.extract_by_key(k), table_.node_alloc()); 961 } 962 insert(BOOST_RV_REF (node_type)np)963 iterator insert(BOOST_RV_REF(node_type) np) 964 { 965 return table_.move_insert_node_type_equiv(np); 966 } 967 insert(const_iterator hint,BOOST_RV_REF (node_type)np)968 iterator insert(const_iterator hint, BOOST_RV_REF(node_type) np) 969 { 970 return table_.move_insert_node_type_with_hint_equiv(hint, np); 971 } 972 973 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || \ 974 (BOOST_COMP_GNUC && BOOST_COMP_GNUC < BOOST_VERSION_NUMBER(4, 6, 0)) 975 private: 976 // Note: Use r-value node_type to insert. 977 iterator insert(node_type&); 978 iterator insert(const_iterator, node_type& np); 979 980 public: 981 #endif 982 983 iterator erase(const_iterator); 984 size_type erase(const key_type&); 985 iterator erase(const_iterator, const_iterator); 986 BOOST_UNORDERED_DEPRECATED("Use erase instead") quick_erase(const_iterator it)987 void quick_erase(const_iterator it) { erase(it); } 988 BOOST_UNORDERED_DEPRECATED("Use erase instead") erase_return_void(const_iterator it)989 void erase_return_void(const_iterator it) { erase(it); } 990 991 void swap(unordered_multiset&) 992 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 993 boost::is_nothrow_swappable<H>::value&& 994 boost::is_nothrow_swappable<P>::value); clear()995 void clear() BOOST_NOEXCEPT { table_.clear_impl(); } 996 997 template <typename H2, typename P2> 998 void merge(boost::unordered_multiset<T, H2, P2, A>& source); 999 1000 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 1001 template <typename H2, typename P2> 1002 void merge(boost::unordered_multiset<T, H2, P2, A>&& source); 1003 #endif 1004 1005 template <typename H2, typename P2> 1006 void merge(boost::unordered_set<T, H2, P2, A>& source); 1007 1008 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 1009 template <typename H2, typename P2> 1010 void merge(boost::unordered_set<T, H2, P2, A>&& source); 1011 #endif 1012 1013 // observers 1014 1015 hasher hash_function() const; 1016 key_equal key_eq() const; 1017 1018 // lookup 1019 1020 const_iterator find(const key_type&) const; 1021 1022 template <class CompatibleKey, class CompatibleHash, 1023 class CompatiblePredicate> 1024 const_iterator find(CompatibleKey const&, CompatibleHash const&, 1025 CompatiblePredicate const&) const; 1026 1027 size_type count(const key_type&) const; 1028 1029 std::pair<const_iterator, const_iterator> equal_range( 1030 const key_type&) const; 1031 1032 // bucket interface 1033 bucket_count() const1034 size_type bucket_count() const BOOST_NOEXCEPT 1035 { 1036 return table_.bucket_count_; 1037 } 1038 max_bucket_count() const1039 size_type max_bucket_count() const BOOST_NOEXCEPT 1040 { 1041 return table_.max_bucket_count(); 1042 } 1043 1044 size_type bucket_size(size_type) const; 1045 bucket(const key_type & k) const1046 size_type bucket(const key_type& k) const 1047 { 1048 return table_.hash_to_bucket(table_.hash(k)); 1049 } 1050 begin(size_type n)1051 local_iterator begin(size_type n) 1052 { 1053 return local_iterator(table_.begin(n), n, table_.bucket_count_); 1054 } 1055 begin(size_type n) const1056 const_local_iterator begin(size_type n) const 1057 { 1058 return const_local_iterator(table_.begin(n), n, table_.bucket_count_); 1059 } 1060 end(size_type)1061 local_iterator end(size_type) { return local_iterator(); } 1062 end(size_type) const1063 const_local_iterator end(size_type) const 1064 { 1065 return const_local_iterator(); 1066 } 1067 cbegin(size_type n) const1068 const_local_iterator cbegin(size_type n) const 1069 { 1070 return const_local_iterator(table_.begin(n), n, table_.bucket_count_); 1071 } 1072 cend(size_type) const1073 const_local_iterator cend(size_type) const 1074 { 1075 return const_local_iterator(); 1076 } 1077 1078 // hash policy 1079 1080 float load_factor() const BOOST_NOEXCEPT; max_load_factor() const1081 float max_load_factor() const BOOST_NOEXCEPT { return table_.mlf_; } 1082 void max_load_factor(float) BOOST_NOEXCEPT; 1083 void rehash(size_type); 1084 void reserve(size_type); 1085 1086 #if !BOOST_WORKAROUND(BOOST_BORLANDC, < 0x0582) 1087 friend bool operator== 1088 <T, H, P, A>(unordered_multiset const&, unordered_multiset const&); 1089 friend bool operator!= 1090 <T, H, P, A>(unordered_multiset const&, unordered_multiset const&); 1091 #endif 1092 }; // class template unordered_multiset 1093 1094 #if BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES 1095 1096 template <class InputIterator, 1097 class Hash = 1098 boost::hash<typename std::iterator_traits<InputIterator>::value_type>, 1099 class Pred = 1100 std::equal_to<typename std::iterator_traits<InputIterator>::value_type>, 1101 class Allocator = std::allocator< 1102 typename std::iterator_traits<InputIterator>::value_type> > 1103 unordered_multiset(InputIterator, InputIterator, 1104 std::size_t = boost::unordered::detail::default_bucket_count, 1105 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 1106 ->unordered_multiset< 1107 typename std::iterator_traits<InputIterator>::value_type, Hash, Pred, 1108 Allocator>; 1109 1110 template <class T, class Hash = boost::hash<T>, 1111 class Pred = std::equal_to<T>, class Allocator = std::allocator<T> > 1112 unordered_multiset(std::initializer_list<T>, 1113 std::size_t = boost::unordered::detail::default_bucket_count, 1114 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 1115 ->unordered_multiset<T, Hash, Pred, Allocator>; 1116 1117 template <class InputIterator, class Allocator> 1118 unordered_multiset(InputIterator, InputIterator, std::size_t, Allocator) 1119 ->unordered_multiset< 1120 typename std::iterator_traits<InputIterator>::value_type, 1121 boost::hash<typename std::iterator_traits<InputIterator>::value_type>, 1122 std::equal_to<typename std::iterator_traits<InputIterator>::value_type>, 1123 Allocator>; 1124 1125 template <class InputIterator, class Hash, class Allocator> 1126 unordered_multiset( 1127 InputIterator, InputIterator, std::size_t, Hash, Allocator) 1128 ->unordered_multiset< 1129 typename std::iterator_traits<InputIterator>::value_type, Hash, 1130 std::equal_to<typename std::iterator_traits<InputIterator>::value_type>, 1131 Allocator>; 1132 1133 template <class T, class Allocator> 1134 unordered_multiset(std::initializer_list<T>, std::size_t, Allocator) 1135 ->unordered_multiset<T, boost::hash<T>, std::equal_to<T>, Allocator>; 1136 1137 template <class T, class Hash, class Allocator> 1138 unordered_multiset(std::initializer_list<T>, std::size_t, Hash, Allocator) 1139 ->unordered_multiset<T, Hash, std::equal_to<T>, Allocator>; 1140 1141 #endif 1142 1143 //////////////////////////////////////////////////////////////////////////// 1144 template <class T, class H, class P, class A> unordered_set()1145 unordered_set<T, H, P, A>::unordered_set() 1146 : table_(boost::unordered::detail::default_bucket_count, hasher(), 1147 key_equal(), allocator_type()) 1148 { 1149 } 1150 1151 template <class T, class H, class P, class A> unordered_set(size_type n,const hasher & hf,const key_equal & eql,const allocator_type & a)1152 unordered_set<T, H, P, A>::unordered_set(size_type n, const hasher& hf, 1153 const key_equal& eql, const allocator_type& a) 1154 : table_(n, hf, eql, a) 1155 { 1156 } 1157 1158 template <class T, class H, class P, class A> 1159 template <class InputIt> unordered_set(InputIt f,InputIt l,size_type n,const hasher & hf,const key_equal & eql,const allocator_type & a)1160 unordered_set<T, H, P, A>::unordered_set(InputIt f, InputIt l, size_type n, 1161 const hasher& hf, const key_equal& eql, const allocator_type& a) 1162 : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a) 1163 { 1164 this->insert(f, l); 1165 } 1166 1167 template <class T, class H, class P, class A> unordered_set(unordered_set const & other)1168 unordered_set<T, H, P, A>::unordered_set(unordered_set const& other) 1169 : table_(other.table_, 1170 unordered_set::value_allocator_traits:: 1171 select_on_container_copy_construction(other.get_allocator())) 1172 { 1173 if (other.table_.size_) { 1174 table_.copy_buckets( 1175 other.table_, boost::unordered::detail::true_type()); 1176 } 1177 } 1178 1179 template <class T, class H, class P, class A> unordered_set(allocator_type const & a)1180 unordered_set<T, H, P, A>::unordered_set(allocator_type const& a) 1181 : table_(boost::unordered::detail::default_bucket_count, hasher(), 1182 key_equal(), a) 1183 { 1184 } 1185 1186 template <class T, class H, class P, class A> unordered_set(unordered_set const & other,allocator_type const & a)1187 unordered_set<T, H, P, A>::unordered_set( 1188 unordered_set const& other, allocator_type const& a) 1189 : table_(other.table_, a) 1190 { 1191 if (other.table_.size_) { 1192 table_.copy_buckets( 1193 other.table_, boost::unordered::detail::true_type()); 1194 } 1195 } 1196 1197 template <class T, class H, class P, class A> unordered_set(BOOST_RV_REF (unordered_set)other,allocator_type const & a)1198 unordered_set<T, H, P, A>::unordered_set( 1199 BOOST_RV_REF(unordered_set) other, allocator_type const& a) 1200 : table_(other.table_, a, boost::unordered::detail::move_tag()) 1201 { 1202 table_.move_construct_buckets(other.table_); 1203 } 1204 1205 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1206 1207 template <class T, class H, class P, class A> unordered_set(std::initializer_list<value_type> list,size_type n,const hasher & hf,const key_equal & eql,const allocator_type & a)1208 unordered_set<T, H, P, A>::unordered_set( 1209 std::initializer_list<value_type> list, size_type n, const hasher& hf, 1210 const key_equal& eql, const allocator_type& a) 1211 : table_( 1212 boost::unordered::detail::initial_size(list.begin(), list.end(), n), 1213 hf, eql, a) 1214 { 1215 this->insert(list.begin(), list.end()); 1216 } 1217 1218 #endif 1219 1220 template <class T, class H, class P, class A> unordered_set(size_type n,const allocator_type & a)1221 unordered_set<T, H, P, A>::unordered_set( 1222 size_type n, const allocator_type& a) 1223 : table_(n, hasher(), key_equal(), a) 1224 { 1225 } 1226 1227 template <class T, class H, class P, class A> unordered_set(size_type n,const hasher & hf,const allocator_type & a)1228 unordered_set<T, H, P, A>::unordered_set( 1229 size_type n, const hasher& hf, const allocator_type& a) 1230 : table_(n, hf, key_equal(), a) 1231 { 1232 } 1233 1234 template <class T, class H, class P, class A> 1235 template <class InputIt> unordered_set(InputIt f,InputIt l,size_type n,const allocator_type & a)1236 unordered_set<T, H, P, A>::unordered_set( 1237 InputIt f, InputIt l, size_type n, const allocator_type& a) 1238 : table_(boost::unordered::detail::initial_size(f, l, n), hasher(), 1239 key_equal(), a) 1240 { 1241 this->insert(f, l); 1242 } 1243 1244 template <class T, class H, class P, class A> 1245 template <class InputIt> unordered_set(InputIt f,InputIt l,size_type n,const hasher & hf,const allocator_type & a)1246 unordered_set<T, H, P, A>::unordered_set(InputIt f, InputIt l, size_type n, 1247 const hasher& hf, const allocator_type& a) 1248 : table_( 1249 boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a) 1250 { 1251 this->insert(f, l); 1252 } 1253 1254 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1255 1256 template <class T, class H, class P, class A> unordered_set(std::initializer_list<value_type> list,size_type n,const allocator_type & a)1257 unordered_set<T, H, P, A>::unordered_set( 1258 std::initializer_list<value_type> list, size_type n, 1259 const allocator_type& a) 1260 : table_( 1261 boost::unordered::detail::initial_size(list.begin(), list.end(), n), 1262 hasher(), key_equal(), a) 1263 { 1264 this->insert(list.begin(), list.end()); 1265 } 1266 1267 template <class T, class H, class P, class A> unordered_set(std::initializer_list<value_type> list,size_type n,const hasher & hf,const allocator_type & a)1268 unordered_set<T, H, P, A>::unordered_set( 1269 std::initializer_list<value_type> list, size_type n, const hasher& hf, 1270 const allocator_type& a) 1271 : table_( 1272 boost::unordered::detail::initial_size(list.begin(), list.end(), n), 1273 hf, key_equal(), a) 1274 { 1275 this->insert(list.begin(), list.end()); 1276 } 1277 1278 #endif 1279 1280 template <class T, class H, class P, class A> ~unordered_set()1281 unordered_set<T, H, P, A>::~unordered_set() BOOST_NOEXCEPT 1282 { 1283 } 1284 1285 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1286 1287 template <class T, class H, class P, class A> operator =(std::initializer_list<value_type> list)1288 unordered_set<T, H, P, A>& unordered_set<T, H, P, A>::operator=( 1289 std::initializer_list<value_type> list) 1290 { 1291 this->clear(); 1292 this->insert(list.begin(), list.end()); 1293 return *this; 1294 } 1295 1296 #endif 1297 1298 // size and capacity 1299 1300 template <class T, class H, class P, class A> max_size() const1301 std::size_t unordered_set<T, H, P, A>::max_size() const BOOST_NOEXCEPT 1302 { 1303 using namespace std; 1304 1305 // size < mlf_ * count 1306 return boost::unordered::detail::double_to_size( 1307 ceil(static_cast<double>(table_.mlf_) * 1308 static_cast<double>(table_.max_bucket_count()))) - 1309 1; 1310 } 1311 1312 // modifiers 1313 1314 template <class T, class H, class P, class A> 1315 template <class InputIt> insert(InputIt first,InputIt last)1316 void unordered_set<T, H, P, A>::insert(InputIt first, InputIt last) 1317 { 1318 if (first != last) { 1319 table_.insert_range_unique( 1320 table::extractor::extract(*first), first, last); 1321 } 1322 } 1323 1324 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1325 template <class T, class H, class P, class A> insert(std::initializer_list<value_type> list)1326 void unordered_set<T, H, P, A>::insert( 1327 std::initializer_list<value_type> list) 1328 { 1329 this->insert(list.begin(), list.end()); 1330 } 1331 #endif 1332 1333 template <class T, class H, class P, class A> 1334 typename unordered_set<T, H, P, A>::iterator erase(const_iterator position)1335 unordered_set<T, H, P, A>::erase(const_iterator position) 1336 { 1337 node_pointer node = table::get_node(position); 1338 BOOST_ASSERT(node); 1339 node_pointer next = table::next_node(node); 1340 table_.erase_nodes_unique(node, next); 1341 return iterator(next); 1342 } 1343 1344 template <class T, class H, class P, class A> 1345 typename unordered_set<T, H, P, A>::size_type erase(const key_type & k)1346 unordered_set<T, H, P, A>::erase(const key_type& k) 1347 { 1348 return table_.erase_key_unique(k); 1349 } 1350 1351 template <class T, class H, class P, class A> 1352 typename unordered_set<T, H, P, A>::iterator erase(const_iterator first,const_iterator last)1353 unordered_set<T, H, P, A>::erase(const_iterator first, const_iterator last) 1354 { 1355 node_pointer last_node = table::get_node(last); 1356 if (first == last) 1357 return iterator(last_node); 1358 table_.erase_nodes_unique(table::get_node(first), last_node); 1359 return iterator(last_node); 1360 } 1361 1362 template <class T, class H, class P, class A> swap(unordered_set & other)1363 void unordered_set<T, H, P, A>::swap(unordered_set& other) 1364 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 1365 boost::is_nothrow_swappable<H>::value&& 1366 boost::is_nothrow_swappable<P>::value) 1367 { 1368 table_.swap(other.table_); 1369 } 1370 1371 // observers 1372 1373 template <class T, class H, class P, class A> 1374 typename unordered_set<T, H, P, A>::hasher hash_function() const1375 unordered_set<T, H, P, A>::hash_function() const 1376 { 1377 return table_.hash_function(); 1378 } 1379 1380 template <class T, class H, class P, class A> 1381 typename unordered_set<T, H, P, A>::key_equal key_eq() const1382 unordered_set<T, H, P, A>::key_eq() const 1383 { 1384 return table_.key_eq(); 1385 } 1386 1387 template <class T, class H, class P, class A> 1388 template <typename H2, typename P2> merge(boost::unordered_set<T,H2,P2,A> & source)1389 void unordered_set<T, H, P, A>::merge( 1390 boost::unordered_set<T, H2, P2, A>& source) 1391 { 1392 table_.merge_unique(source.table_); 1393 } 1394 1395 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 1396 template <class T, class H, class P, class A> 1397 template <typename H2, typename P2> merge(boost::unordered_set<T,H2,P2,A> && source)1398 void unordered_set<T, H, P, A>::merge( 1399 boost::unordered_set<T, H2, P2, A>&& source) 1400 { 1401 table_.merge_unique(source.table_); 1402 } 1403 #endif 1404 1405 template <class T, class H, class P, class A> 1406 template <typename H2, typename P2> merge(boost::unordered_multiset<T,H2,P2,A> & source)1407 void unordered_set<T, H, P, A>::merge( 1408 boost::unordered_multiset<T, H2, P2, A>& source) 1409 { 1410 table_.merge_unique(source.table_); 1411 } 1412 1413 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 1414 template <class T, class H, class P, class A> 1415 template <typename H2, typename P2> merge(boost::unordered_multiset<T,H2,P2,A> && source)1416 void unordered_set<T, H, P, A>::merge( 1417 boost::unordered_multiset<T, H2, P2, A>&& source) 1418 { 1419 table_.merge_unique(source.table_); 1420 } 1421 #endif 1422 1423 // lookup 1424 1425 template <class T, class H, class P, class A> 1426 typename unordered_set<T, H, P, A>::const_iterator find(const key_type & k) const1427 unordered_set<T, H, P, A>::find(const key_type& k) const 1428 { 1429 return const_iterator(table_.find_node(k)); 1430 } 1431 1432 template <class T, class H, class P, class A> 1433 template <class CompatibleKey, class CompatibleHash, 1434 class CompatiblePredicate> 1435 typename unordered_set<T, H, P, A>::const_iterator find(CompatibleKey const & k,CompatibleHash const & hash,CompatiblePredicate const & eq) const1436 unordered_set<T, H, P, A>::find(CompatibleKey const& k, 1437 CompatibleHash const& hash, CompatiblePredicate const& eq) const 1438 { 1439 return const_iterator( 1440 table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq)); 1441 } 1442 1443 template <class T, class H, class P, class A> 1444 typename unordered_set<T, H, P, A>::size_type count(const key_type & k) const1445 unordered_set<T, H, P, A>::count(const key_type& k) const 1446 { 1447 return table_.find_node(k) ? 1 : 0; 1448 } 1449 1450 template <class T, class H, class P, class A> 1451 std::pair<typename unordered_set<T, H, P, A>::const_iterator, 1452 typename unordered_set<T, H, P, A>::const_iterator> equal_range(const key_type & k) const1453 unordered_set<T, H, P, A>::equal_range(const key_type& k) const 1454 { 1455 node_pointer n = table_.find_node(k); 1456 return std::make_pair( 1457 const_iterator(n), const_iterator(n ? table::next_node(n) : n)); 1458 } 1459 1460 template <class T, class H, class P, class A> 1461 typename unordered_set<T, H, P, A>::size_type bucket_size(size_type n) const1462 unordered_set<T, H, P, A>::bucket_size(size_type n) const 1463 { 1464 return table_.bucket_size(n); 1465 } 1466 1467 // hash policy 1468 1469 template <class T, class H, class P, class A> load_factor() const1470 float unordered_set<T, H, P, A>::load_factor() const BOOST_NOEXCEPT 1471 { 1472 BOOST_ASSERT(table_.bucket_count_ != 0); 1473 return static_cast<float>(table_.size_) / 1474 static_cast<float>(table_.bucket_count_); 1475 } 1476 1477 template <class T, class H, class P, class A> max_load_factor(float m)1478 void unordered_set<T, H, P, A>::max_load_factor(float m) BOOST_NOEXCEPT 1479 { 1480 table_.max_load_factor(m); 1481 } 1482 1483 template <class T, class H, class P, class A> rehash(size_type n)1484 void unordered_set<T, H, P, A>::rehash(size_type n) 1485 { 1486 table_.rehash(n); 1487 } 1488 1489 template <class T, class H, class P, class A> reserve(size_type n)1490 void unordered_set<T, H, P, A>::reserve(size_type n) 1491 { 1492 table_.rehash(static_cast<std::size_t>( 1493 std::ceil(static_cast<double>(n) / table_.mlf_))); 1494 } 1495 1496 template <class T, class H, class P, class A> operator ==(unordered_set<T,H,P,A> const & m1,unordered_set<T,H,P,A> const & m2)1497 inline bool operator==( 1498 unordered_set<T, H, P, A> const& m1, unordered_set<T, H, P, A> const& m2) 1499 { 1500 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613)) 1501 struct dummy 1502 { 1503 unordered_set<T, H, P, A> x; 1504 }; 1505 #endif 1506 return m1.table_.equals_unique(m2.table_); 1507 } 1508 1509 template <class T, class H, class P, class A> operator !=(unordered_set<T,H,P,A> const & m1,unordered_set<T,H,P,A> const & m2)1510 inline bool operator!=( 1511 unordered_set<T, H, P, A> const& m1, unordered_set<T, H, P, A> const& m2) 1512 { 1513 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613)) 1514 struct dummy 1515 { 1516 unordered_set<T, H, P, A> x; 1517 }; 1518 #endif 1519 return !m1.table_.equals_unique(m2.table_); 1520 } 1521 1522 template <class T, class H, class P, class A> swap(unordered_set<T,H,P,A> & m1,unordered_set<T,H,P,A> & m2)1523 inline void swap( 1524 unordered_set<T, H, P, A>& m1, unordered_set<T, H, P, A>& m2) 1525 BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT_EXPR(m1.swap(m2))) 1526 { 1527 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613)) 1528 struct dummy 1529 { 1530 unordered_set<T, H, P, A> x; 1531 }; 1532 #endif 1533 m1.swap(m2); 1534 } 1535 1536 //////////////////////////////////////////////////////////////////////////// 1537 1538 template <class T, class H, class P, class A> unordered_multiset()1539 unordered_multiset<T, H, P, A>::unordered_multiset() 1540 : table_(boost::unordered::detail::default_bucket_count, hasher(), 1541 key_equal(), allocator_type()) 1542 { 1543 } 1544 1545 template <class T, class H, class P, class A> unordered_multiset(size_type n,const hasher & hf,const key_equal & eql,const allocator_type & a)1546 unordered_multiset<T, H, P, A>::unordered_multiset(size_type n, 1547 const hasher& hf, const key_equal& eql, const allocator_type& a) 1548 : table_(n, hf, eql, a) 1549 { 1550 } 1551 1552 template <class T, class H, class P, class A> 1553 template <class InputIt> unordered_multiset(InputIt f,InputIt l,size_type n,const hasher & hf,const key_equal & eql,const allocator_type & a)1554 unordered_multiset<T, H, P, A>::unordered_multiset(InputIt f, InputIt l, 1555 size_type n, const hasher& hf, const key_equal& eql, 1556 const allocator_type& a) 1557 : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a) 1558 { 1559 this->insert(f, l); 1560 } 1561 1562 template <class T, class H, class P, class A> unordered_multiset(unordered_multiset const & other)1563 unordered_multiset<T, H, P, A>::unordered_multiset( 1564 unordered_multiset const& other) 1565 : table_(other.table_, 1566 unordered_multiset::value_allocator_traits:: 1567 select_on_container_copy_construction(other.get_allocator())) 1568 { 1569 if (other.table_.size_) { 1570 table_.copy_buckets( 1571 other.table_, boost::unordered::detail::false_type()); 1572 } 1573 } 1574 1575 template <class T, class H, class P, class A> unordered_multiset(allocator_type const & a)1576 unordered_multiset<T, H, P, A>::unordered_multiset(allocator_type const& a) 1577 : table_(boost::unordered::detail::default_bucket_count, hasher(), 1578 key_equal(), a) 1579 { 1580 } 1581 1582 template <class T, class H, class P, class A> unordered_multiset(unordered_multiset const & other,allocator_type const & a)1583 unordered_multiset<T, H, P, A>::unordered_multiset( 1584 unordered_multiset const& other, allocator_type const& a) 1585 : table_(other.table_, a) 1586 { 1587 if (other.table_.size_) { 1588 table_.copy_buckets( 1589 other.table_, boost::unordered::detail::false_type()); 1590 } 1591 } 1592 1593 template <class T, class H, class P, class A> unordered_multiset(BOOST_RV_REF (unordered_multiset)other,allocator_type const & a)1594 unordered_multiset<T, H, P, A>::unordered_multiset( 1595 BOOST_RV_REF(unordered_multiset) other, allocator_type const& a) 1596 : table_(other.table_, a, boost::unordered::detail::move_tag()) 1597 { 1598 table_.move_construct_buckets(other.table_); 1599 } 1600 1601 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1602 1603 template <class T, class H, class P, class A> unordered_multiset(std::initializer_list<value_type> list,size_type n,const hasher & hf,const key_equal & eql,const allocator_type & a)1604 unordered_multiset<T, H, P, A>::unordered_multiset( 1605 std::initializer_list<value_type> list, size_type n, const hasher& hf, 1606 const key_equal& eql, const allocator_type& a) 1607 : table_( 1608 boost::unordered::detail::initial_size(list.begin(), list.end(), n), 1609 hf, eql, a) 1610 { 1611 this->insert(list.begin(), list.end()); 1612 } 1613 1614 #endif 1615 1616 template <class T, class H, class P, class A> unordered_multiset(size_type n,const allocator_type & a)1617 unordered_multiset<T, H, P, A>::unordered_multiset( 1618 size_type n, const allocator_type& a) 1619 : table_(n, hasher(), key_equal(), a) 1620 { 1621 } 1622 1623 template <class T, class H, class P, class A> unordered_multiset(size_type n,const hasher & hf,const allocator_type & a)1624 unordered_multiset<T, H, P, A>::unordered_multiset( 1625 size_type n, const hasher& hf, const allocator_type& a) 1626 : table_(n, hf, key_equal(), a) 1627 { 1628 } 1629 1630 template <class T, class H, class P, class A> 1631 template <class InputIt> unordered_multiset(InputIt f,InputIt l,size_type n,const allocator_type & a)1632 unordered_multiset<T, H, P, A>::unordered_multiset( 1633 InputIt f, InputIt l, size_type n, const allocator_type& a) 1634 : table_(boost::unordered::detail::initial_size(f, l, n), hasher(), 1635 key_equal(), a) 1636 { 1637 this->insert(f, l); 1638 } 1639 1640 template <class T, class H, class P, class A> 1641 template <class InputIt> unordered_multiset(InputIt f,InputIt l,size_type n,const hasher & hf,const allocator_type & a)1642 unordered_multiset<T, H, P, A>::unordered_multiset(InputIt f, InputIt l, 1643 size_type n, const hasher& hf, const allocator_type& a) 1644 : table_( 1645 boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a) 1646 { 1647 this->insert(f, l); 1648 } 1649 1650 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1651 1652 template <class T, class H, class P, class A> unordered_multiset(std::initializer_list<value_type> list,size_type n,const allocator_type & a)1653 unordered_multiset<T, H, P, A>::unordered_multiset( 1654 std::initializer_list<value_type> list, size_type n, 1655 const allocator_type& a) 1656 : table_( 1657 boost::unordered::detail::initial_size(list.begin(), list.end(), n), 1658 hasher(), key_equal(), a) 1659 { 1660 this->insert(list.begin(), list.end()); 1661 } 1662 1663 template <class T, class H, class P, class A> unordered_multiset(std::initializer_list<value_type> list,size_type n,const hasher & hf,const allocator_type & a)1664 unordered_multiset<T, H, P, A>::unordered_multiset( 1665 std::initializer_list<value_type> list, size_type n, const hasher& hf, 1666 const allocator_type& a) 1667 : table_( 1668 boost::unordered::detail::initial_size(list.begin(), list.end(), n), 1669 hf, key_equal(), a) 1670 { 1671 this->insert(list.begin(), list.end()); 1672 } 1673 1674 #endif 1675 1676 template <class T, class H, class P, class A> ~unordered_multiset()1677 unordered_multiset<T, H, P, A>::~unordered_multiset() BOOST_NOEXCEPT 1678 { 1679 } 1680 1681 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1682 1683 template <class T, class H, class P, class A> operator =(std::initializer_list<value_type> list)1684 unordered_multiset<T, H, P, A>& unordered_multiset<T, H, P, A>::operator=( 1685 std::initializer_list<value_type> list) 1686 { 1687 this->clear(); 1688 this->insert(list.begin(), list.end()); 1689 return *this; 1690 } 1691 1692 #endif 1693 1694 // size and capacity 1695 1696 template <class T, class H, class P, class A> max_size() const1697 std::size_t unordered_multiset<T, H, P, A>::max_size() const BOOST_NOEXCEPT 1698 { 1699 using namespace std; 1700 1701 // size < mlf_ * count 1702 return boost::unordered::detail::double_to_size( 1703 ceil(static_cast<double>(table_.mlf_) * 1704 static_cast<double>(table_.max_bucket_count()))) - 1705 1; 1706 } 1707 1708 // modifiers 1709 1710 template <class T, class H, class P, class A> 1711 template <class InputIt> insert(InputIt first,InputIt last)1712 void unordered_multiset<T, H, P, A>::insert(InputIt first, InputIt last) 1713 { 1714 table_.insert_range_equiv(first, last); 1715 } 1716 1717 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1718 template <class T, class H, class P, class A> insert(std::initializer_list<value_type> list)1719 void unordered_multiset<T, H, P, A>::insert( 1720 std::initializer_list<value_type> list) 1721 { 1722 this->insert(list.begin(), list.end()); 1723 } 1724 #endif 1725 1726 template <class T, class H, class P, class A> 1727 typename unordered_multiset<T, H, P, A>::iterator erase(const_iterator position)1728 unordered_multiset<T, H, P, A>::erase(const_iterator position) 1729 { 1730 node_pointer node = table::get_node(position); 1731 BOOST_ASSERT(node); 1732 node_pointer next = table::next_node(node); 1733 table_.erase_nodes_equiv(node, next); 1734 return iterator(next); 1735 } 1736 1737 template <class T, class H, class P, class A> 1738 typename unordered_multiset<T, H, P, A>::size_type erase(const key_type & k)1739 unordered_multiset<T, H, P, A>::erase(const key_type& k) 1740 { 1741 return table_.erase_key_equiv(k); 1742 } 1743 1744 template <class T, class H, class P, class A> 1745 typename unordered_multiset<T, H, P, A>::iterator erase(const_iterator first,const_iterator last)1746 unordered_multiset<T, H, P, A>::erase( 1747 const_iterator first, const_iterator last) 1748 { 1749 node_pointer last_node = table::get_node(last); 1750 if (first == last) 1751 return iterator(last_node); 1752 table_.erase_nodes_equiv(table::get_node(first), last_node); 1753 return iterator(last_node); 1754 } 1755 1756 template <class T, class H, class P, class A> swap(unordered_multiset & other)1757 void unordered_multiset<T, H, P, A>::swap(unordered_multiset& other) 1758 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 1759 boost::is_nothrow_swappable<H>::value&& 1760 boost::is_nothrow_swappable<P>::value) 1761 { 1762 table_.swap(other.table_); 1763 } 1764 1765 // observers 1766 1767 template <class T, class H, class P, class A> 1768 typename unordered_multiset<T, H, P, A>::hasher hash_function() const1769 unordered_multiset<T, H, P, A>::hash_function() const 1770 { 1771 return table_.hash_function(); 1772 } 1773 1774 template <class T, class H, class P, class A> 1775 typename unordered_multiset<T, H, P, A>::key_equal key_eq() const1776 unordered_multiset<T, H, P, A>::key_eq() const 1777 { 1778 return table_.key_eq(); 1779 } 1780 1781 template <class T, class H, class P, class A> 1782 template <typename H2, typename P2> merge(boost::unordered_multiset<T,H2,P2,A> & source)1783 void unordered_multiset<T, H, P, A>::merge( 1784 boost::unordered_multiset<T, H2, P2, A>& source) 1785 { 1786 while (!source.empty()) { 1787 insert(source.extract(source.begin())); 1788 } 1789 } 1790 1791 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 1792 template <class T, class H, class P, class A> 1793 template <typename H2, typename P2> merge(boost::unordered_multiset<T,H2,P2,A> && source)1794 void unordered_multiset<T, H, P, A>::merge( 1795 boost::unordered_multiset<T, H2, P2, A>&& source) 1796 { 1797 while (!source.empty()) { 1798 insert(source.extract(source.begin())); 1799 } 1800 } 1801 #endif 1802 1803 template <class T, class H, class P, class A> 1804 template <typename H2, typename P2> merge(boost::unordered_set<T,H2,P2,A> & source)1805 void unordered_multiset<T, H, P, A>::merge( 1806 boost::unordered_set<T, H2, P2, A>& source) 1807 { 1808 while (!source.empty()) { 1809 insert(source.extract(source.begin())); 1810 } 1811 } 1812 1813 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 1814 template <class T, class H, class P, class A> 1815 template <typename H2, typename P2> merge(boost::unordered_set<T,H2,P2,A> && source)1816 void unordered_multiset<T, H, P, A>::merge( 1817 boost::unordered_set<T, H2, P2, A>&& source) 1818 { 1819 while (!source.empty()) { 1820 insert(source.extract(source.begin())); 1821 } 1822 } 1823 #endif 1824 1825 // lookup 1826 1827 template <class T, class H, class P, class A> 1828 typename unordered_multiset<T, H, P, A>::const_iterator find(const key_type & k) const1829 unordered_multiset<T, H, P, A>::find(const key_type& k) const 1830 { 1831 return const_iterator(table_.find_node(k)); 1832 } 1833 1834 template <class T, class H, class P, class A> 1835 template <class CompatibleKey, class CompatibleHash, 1836 class CompatiblePredicate> 1837 typename unordered_multiset<T, H, P, A>::const_iterator find(CompatibleKey const & k,CompatibleHash const & hash,CompatiblePredicate const & eq) const1838 unordered_multiset<T, H, P, A>::find(CompatibleKey const& k, 1839 CompatibleHash const& hash, CompatiblePredicate const& eq) const 1840 { 1841 return const_iterator( 1842 table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq)); 1843 } 1844 1845 template <class T, class H, class P, class A> 1846 typename unordered_multiset<T, H, P, A>::size_type count(const key_type & k) const1847 unordered_multiset<T, H, P, A>::count(const key_type& k) const 1848 { 1849 node_pointer n = table_.find_node(k); 1850 return n ? table_.group_count(n) : 0; 1851 } 1852 1853 template <class T, class H, class P, class A> 1854 std::pair<typename unordered_multiset<T, H, P, A>::const_iterator, 1855 typename unordered_multiset<T, H, P, A>::const_iterator> equal_range(const key_type & k) const1856 unordered_multiset<T, H, P, A>::equal_range(const key_type& k) const 1857 { 1858 node_pointer n = table_.find_node(k); 1859 return std::make_pair( 1860 const_iterator(n), const_iterator(n ? table_.next_group(n) : n)); 1861 } 1862 1863 template <class T, class H, class P, class A> 1864 typename unordered_multiset<T, H, P, A>::size_type bucket_size(size_type n) const1865 unordered_multiset<T, H, P, A>::bucket_size(size_type n) const 1866 { 1867 return table_.bucket_size(n); 1868 } 1869 1870 // hash policy 1871 1872 template <class T, class H, class P, class A> load_factor() const1873 float unordered_multiset<T, H, P, A>::load_factor() const BOOST_NOEXCEPT 1874 { 1875 BOOST_ASSERT(table_.bucket_count_ != 0); 1876 return static_cast<float>(table_.size_) / 1877 static_cast<float>(table_.bucket_count_); 1878 } 1879 1880 template <class T, class H, class P, class A> max_load_factor(float m)1881 void unordered_multiset<T, H, P, A>::max_load_factor(float m) BOOST_NOEXCEPT 1882 { 1883 table_.max_load_factor(m); 1884 } 1885 1886 template <class T, class H, class P, class A> rehash(size_type n)1887 void unordered_multiset<T, H, P, A>::rehash(size_type n) 1888 { 1889 table_.rehash(n); 1890 } 1891 1892 template <class T, class H, class P, class A> reserve(size_type n)1893 void unordered_multiset<T, H, P, A>::reserve(size_type n) 1894 { 1895 table_.rehash(static_cast<std::size_t>( 1896 std::ceil(static_cast<double>(n) / table_.mlf_))); 1897 } 1898 1899 template <class T, class H, class P, class A> operator ==(unordered_multiset<T,H,P,A> const & m1,unordered_multiset<T,H,P,A> const & m2)1900 inline bool operator==(unordered_multiset<T, H, P, A> const& m1, 1901 unordered_multiset<T, H, P, A> const& m2) 1902 { 1903 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613)) 1904 struct dummy 1905 { 1906 unordered_multiset<T, H, P, A> x; 1907 }; 1908 #endif 1909 return m1.table_.equals_equiv(m2.table_); 1910 } 1911 1912 template <class T, class H, class P, class A> operator !=(unordered_multiset<T,H,P,A> const & m1,unordered_multiset<T,H,P,A> const & m2)1913 inline bool operator!=(unordered_multiset<T, H, P, A> const& m1, 1914 unordered_multiset<T, H, P, A> const& m2) 1915 { 1916 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613)) 1917 struct dummy 1918 { 1919 unordered_multiset<T, H, P, A> x; 1920 }; 1921 #endif 1922 return !m1.table_.equals_equiv(m2.table_); 1923 } 1924 1925 template <class T, class H, class P, class A> swap(unordered_multiset<T,H,P,A> & m1,unordered_multiset<T,H,P,A> & m2)1926 inline void swap( 1927 unordered_multiset<T, H, P, A>& m1, unordered_multiset<T, H, P, A>& m2) 1928 BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT_EXPR(m1.swap(m2))) 1929 { 1930 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613)) 1931 struct dummy 1932 { 1933 unordered_multiset<T, H, P, A> x; 1934 }; 1935 #endif 1936 m1.swap(m2); 1937 } 1938 1939 template <typename N, typename T, typename A> class node_handle_set 1940 { 1941 BOOST_MOVABLE_BUT_NOT_COPYABLE(node_handle_set) 1942 1943 template <typename Types> friend struct ::boost::unordered::detail::table; 1944 template <class T2, class H2, class P2, class A2> 1945 friend class unordered_set; 1946 template <class T2, class H2, class P2, class A2> 1947 friend class unordered_multiset; 1948 1949 typedef typename boost::unordered::detail::rebind_wrap<A, T>::type 1950 value_allocator; 1951 typedef boost::unordered::detail::allocator_traits<value_allocator> 1952 value_allocator_traits; 1953 typedef N node; 1954 typedef typename boost::unordered::detail::rebind_wrap<A, node>::type 1955 node_allocator; 1956 typedef boost::unordered::detail::allocator_traits<node_allocator> 1957 node_allocator_traits; 1958 typedef typename node_allocator_traits::pointer node_pointer; 1959 1960 public: 1961 typedef T value_type; 1962 typedef A allocator_type; 1963 1964 private: 1965 node_pointer ptr_; 1966 bool has_alloc_; 1967 boost::unordered::detail::optional<value_allocator> alloc_; 1968 node_handle_set(node_pointer ptr,allocator_type const & a)1969 node_handle_set(node_pointer ptr, allocator_type const& a) 1970 : ptr_(ptr), alloc_(a) 1971 { 1972 } 1973 1974 public: node_handle_set()1975 BOOST_CONSTEXPR node_handle_set() BOOST_NOEXCEPT : ptr_(), 1976 has_alloc_(false) 1977 { 1978 } 1979 ~node_handle_set()1980 ~node_handle_set() 1981 { 1982 if (ptr_) { 1983 node_allocator node_alloc(*alloc_); 1984 boost::unordered::detail::node_tmp<node_allocator> tmp( 1985 ptr_, node_alloc); 1986 } 1987 } 1988 node_handle_set(BOOST_RV_REF (node_handle_set)n)1989 node_handle_set(BOOST_RV_REF(node_handle_set) n) BOOST_NOEXCEPT 1990 : ptr_(n.ptr_), 1991 alloc_(boost::move(n.alloc_)) 1992 { 1993 n.ptr_ = node_pointer(); 1994 } 1995 operator =(BOOST_RV_REF (node_handle_set)n)1996 node_handle_set& operator=(BOOST_RV_REF(node_handle_set) n) 1997 { 1998 BOOST_ASSERT(!alloc_.has_value() || 1999 value_allocator_traits:: 2000 propagate_on_container_move_assignment::value || 2001 (n.alloc_.has_value() && alloc_ == n.alloc_)); 2002 2003 if (ptr_) { 2004 node_allocator node_alloc(*alloc_); 2005 boost::unordered::detail::node_tmp<node_allocator> tmp( 2006 ptr_, node_alloc); 2007 ptr_ = node_pointer(); 2008 } 2009 2010 if (!alloc_.has_value() || 2011 value_allocator_traits::propagate_on_container_move_assignment:: 2012 value) { 2013 alloc_ = boost::move(n.alloc_); 2014 } 2015 ptr_ = n.ptr_; 2016 n.ptr_ = node_pointer(); 2017 2018 return *this; 2019 } 2020 value() const2021 value_type& value() const { return ptr_->value(); } 2022 get_allocator() const2023 allocator_type get_allocator() const { return *alloc_; } 2024 2025 BOOST_EXPLICIT_OPERATOR_BOOL_NOEXCEPT() 2026 2027 bool operator!() const BOOST_NOEXCEPT { return ptr_ ? 0 : 1; } 2028 empty() const2029 bool empty() const BOOST_NOEXCEPT { return ptr_ ? 0 : 1; } 2030 swap(node_handle_set & n)2031 void swap(node_handle_set& n) BOOST_NOEXCEPT_IF( 2032 value_allocator_traits::propagate_on_container_swap::value || 2033 value_allocator_traits::is_always_equal::value) 2034 { 2035 BOOST_ASSERT( 2036 !alloc_.has_value() || !n.alloc_.has_value() || 2037 value_allocator_traits::propagate_on_container_swap::value || 2038 alloc_ == n.alloc_); 2039 if (value_allocator_traits::propagate_on_container_swap::value || 2040 !alloc_.has_value() || !n.alloc_.has_value()) { 2041 boost::swap(alloc_, n.alloc_); 2042 } 2043 boost::swap(ptr_, n.ptr_); 2044 } 2045 }; 2046 2047 template <typename N, typename T, typename A> swap(node_handle_set<N,T,A> & x,node_handle_set<N,T,A> & y)2048 void swap(node_handle_set<N, T, A>& x, node_handle_set<N, T, A>& y) 2049 BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT_EXPR(x.swap(y))) 2050 { 2051 x.swap(y); 2052 } 2053 2054 template <typename N, typename T, typename A> struct insert_return_type_set 2055 { 2056 private: 2057 BOOST_MOVABLE_BUT_NOT_COPYABLE(insert_return_type_set) 2058 2059 typedef typename boost::unordered::detail::rebind_wrap<A, T>::type 2060 value_allocator; 2061 typedef N node_; 2062 2063 public: 2064 bool inserted; 2065 boost::unordered::iterator_detail::c_iterator<node_> position; 2066 boost::unordered::node_handle_set<N, T, A> node; 2067 insert_return_type_setboost::unordered::insert_return_type_set2068 insert_return_type_set() : inserted(false), position(), node() {} 2069 insert_return_type_setboost::unordered::insert_return_type_set2070 insert_return_type_set(BOOST_RV_REF(insert_return_type_set) 2071 x) BOOST_NOEXCEPT : inserted(x.inserted), 2072 position(x.position), 2073 node(boost::move(x.node)) 2074 { 2075 } 2076 operator =boost::unordered::insert_return_type_set2077 insert_return_type_set& operator=(BOOST_RV_REF(insert_return_type_set) x) 2078 { 2079 inserted = x.inserted; 2080 position = x.position; 2081 node = boost::move(x.node); 2082 return *this; 2083 } 2084 }; 2085 2086 template <typename N, typename T, typename A> swap(insert_return_type_set<N,T,A> & x,insert_return_type_set<N,T,A> & y)2087 void swap( 2088 insert_return_type_set<N, T, A>& x, insert_return_type_set<N, T, A>& y) 2089 { 2090 boost::swap(x.node, y.node); 2091 boost::swap(x.inserted, y.inserted); 2092 boost::swap(x.position, y.position); 2093 } 2094 } // namespace unordered 2095 } // namespace boost 2096 2097 #if defined(BOOST_MSVC) 2098 #pragma warning(pop) 2099 #endif 2100 2101 #endif // BOOST_UNORDERED_UNORDERED_SET_HPP_INCLUDED 2102