ceph/src/boost/boost/unordered/unordered_set.hpp

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