ceph/src/boost/libs/unordered/include/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/unordered/detail/set.hpp>
  18 #include <boost/functional/hash.hpp>
  19 #include <boost/move/move.hpp>
  20
  21 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
  22 #include <initializer_list>
  23 #endif
  24
  25 #if defined(BOOST_MSVC)
  26 #pragma warning(push)
  27 #if BOOST_MSVC >= 1400
  28 #pragma warning(disable:4396) //the inline specifier cannot be used when a
  29                               // friend declaration refers to a specialization
  30                               // of a function template
  31 #endif
  32 #endif
  33
  34 namespace boost
  35 {
  36 namespace unordered
  37 {
  38     template <class T, class H, class P, class A>
  39     class unordered_set
  40     {
  41 #if defined(BOOST_UNORDERED_USE_MOVE)
  42         BOOST_COPYABLE_AND_MOVABLE(unordered_set)
  43 #endif
  44     public:
  45
  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
  54         typedef boost::unordered::detail::set<A, T, H, P> types;
  55         typedef typename types::traits allocator_traits;
  56         typedef typename types::table table;
  57
  58     public:
  59
  60         typedef typename allocator_traits::pointer pointer;
  61         typedef typename 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::cl_iterator const_local_iterator;
  70         typedef typename table::l_iterator local_iterator;
  71         typedef typename table::c_iterator const_iterator;
  72         typedef typename table::iterator iterator;
  73
  74     private:
  75
  76         table table_;
  77
  78     public:
  79
  80         // constructors
  81
  82         unordered_set();
  83
  84         explicit unordered_set(
  85                 size_type,
  86                 const hasher& = hasher(),
  87                 const key_equal& = key_equal(),
  88                 const allocator_type& = allocator_type());
  89
  90         explicit unordered_set(
  91                 size_type,
  92                 const allocator_type&);
  93
  94         explicit unordered_set(
  95                 size_type,
  96                 const hasher&,
  97                 const allocator_type&);
  98
  99         explicit unordered_set(allocator_type const&);
 100
 101         template <class InputIt>
 102         unordered_set(InputIt, InputIt);
 103
 104         template <class InputIt>
 105         unordered_set(
 106                 InputIt, InputIt,
 107                 size_type,
 108                 const hasher& = hasher(),
 109                 const key_equal& = key_equal());
 110
 111         template <class InputIt>
 112         unordered_set(
 113                 InputIt, InputIt,
 114                 size_type,
 115                 const hasher&,
 116                 const key_equal&,
 117                 const allocator_type&);
 118
 119         template <class InputIt>
 120         unordered_set(
 121                 InputIt, InputIt,
 122                 size_type,
 123                 const hasher&,
 124                 const allocator_type&);
 125
 126         template <class InputIt>
 127         unordered_set(
 128                 InputIt, InputIt,
 129                 size_type,
 130                 const allocator_type&);
 131
 132         // copy/move constructors
 133
 134         unordered_set(unordered_set const&);
 135
 136         unordered_set(unordered_set const&, allocator_type const&);
 137         unordered_set(BOOST_RV_REF(unordered_set), allocator_type const&);
 138
 139 #if defined(BOOST_UNORDERED_USE_MOVE)
 140         unordered_set(BOOST_RV_REF(unordered_set) other)
 141                 BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
 142             : table_(other.table_, boost::unordered::detail::move_tag())
 143         {
 144         }
 145 #elif !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 146         unordered_set(unordered_set&& other)
 147                 BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
 148             : table_(other.table_, boost::unordered::detail::move_tag())
 149         {
 150         }
 151 #endif
 152
 153 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 154         unordered_set(
 155                 std::initializer_list<value_type>,
 156                 size_type = boost::unordered::detail::default_bucket_count,
 157                 const hasher& = hasher(),
 158                 const key_equal&l = key_equal(),
 159                 const allocator_type& = allocator_type());
 160         unordered_set(
 161                 std::initializer_list<value_type>,
 162                 size_type,
 163                 const hasher&,
 164                 const allocator_type&);
 165         unordered_set(
 166                 std::initializer_list<value_type>,
 167                 size_type,
 168                 const allocator_type&);
 169 #endif
 170
 171         // Destructor
 172
 173         ~unordered_set() BOOST_NOEXCEPT;
 174
 175         // Assign
 176
 177 #if defined(BOOST_UNORDERED_USE_MOVE)
 178         unordered_set& operator=(BOOST_COPY_ASSIGN_REF(unordered_set) x)
 179         {
 180             table_.assign(x.table_);
 181             return *this;
 182         }
 183
 184         unordered_set& operator=(BOOST_RV_REF(unordered_set) x)
 185         {
 186             table_.move_assign(x.table_);
 187             return *this;
 188         }
 189 #else
 190         unordered_set& operator=(unordered_set const& x)
 191         {
 192             table_.assign(x.table_);
 193             return *this;
 194         }
 195
 196 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 197         unordered_set& operator=(unordered_set&& x)
 198         {
 199             table_.move_assign(x.table_);
 200             return *this;
 201         }
 202 #endif
 203 #endif
 204
 205 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 206         unordered_set& operator=(std::initializer_list<value_type>);
 207 #endif
 208
 209         allocator_type get_allocator() const BOOST_NOEXCEPT
 210         {
 211             return table_.node_alloc();
 212         }
 213
 214         // size and capacity
 215
 216         bool empty() const BOOST_NOEXCEPT
 217         {
 218             return table_.size_ == 0;
 219         }
 220
 221         size_type size() const BOOST_NOEXCEPT
 222         {
 223             return table_.size_;
 224         }
 225
 226         size_type max_size() const BOOST_NOEXCEPT;
 227
 228         // iterators
 229
 230         iterator begin() BOOST_NOEXCEPT
 231         {
 232             return iterator(table_.begin());
 233         }
 234
 235         const_iterator begin() const BOOST_NOEXCEPT
 236         {
 237             return const_iterator(table_.begin());
 238         }
 239
 240         iterator end() BOOST_NOEXCEPT
 241         {
 242             return iterator();
 243         }
 244
 245         const_iterator end() const BOOST_NOEXCEPT
 246         {
 247             return const_iterator();
 248         }
 249
 250         const_iterator cbegin() const BOOST_NOEXCEPT
 251         {
 252             return const_iterator(table_.begin());
 253         }
 254
 255         const_iterator cend() const BOOST_NOEXCEPT
 256         {
 257             return const_iterator();
 258         }
 259
 260         // emplace
 261
 262 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 263         template <class... Args>
 264         std::pair<iterator, bool> emplace(BOOST_FWD_REF(Args)... args)
 265         {
 266             return table_.emplace(boost::forward<Args>(args)...);
 267         }
 268
 269         template <class... Args>
 270         iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
 271         {
 272             return table_.emplace_hint(hint, boost::forward<Args>(args)...);
 273         }
 274 #else
 275
 276 #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
 277
 278         // 0 argument emplace requires special treatment in case
 279         // the container is instantiated with a value type that
 280         // doesn't have a default constructor.
 281
 282         std::pair<iterator, bool> emplace(
 283                 boost::unordered::detail::empty_emplace
 284                     = boost::unordered::detail::empty_emplace(),
 285                 value_type v = value_type())
 286         {
 287             return this->emplace(boost::move(v));
 288         }
 289
 290         iterator emplace_hint(const_iterator hint,
 291                 boost::unordered::detail::empty_emplace
 292                     = boost::unordered::detail::empty_emplace(),
 293                 value_type v = value_type()
 294             )
 295         {
 296             return this->emplace_hint(hint, boost::move(v));
 297         }
 298
 299 #endif
 300
 301         template <typename A0>
 302         std::pair<iterator, bool> emplace(BOOST_FWD_REF(A0) a0)
 303         {
 304             return table_.emplace(
 305                 boost::unordered::detail::create_emplace_args(
 306                     boost::forward<A0>(a0))
 307             );
 308         }
 309
 310         template <typename A0>
 311         iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0)
 312         {
 313             return table_.emplace_hint(hint,
 314                 boost::unordered::detail::create_emplace_args(
 315                     boost::forward<A0>(a0))
 316             );
 317         }
 318
 319         template <typename A0, typename A1>
 320         std::pair<iterator, bool> emplace(
 321             BOOST_FWD_REF(A0) a0,
 322             BOOST_FWD_REF(A1) a1)
 323         {
 324             return table_.emplace(
 325                 boost::unordered::detail::create_emplace_args(
 326                     boost::forward<A0>(a0),
 327                     boost::forward<A1>(a1))
 328             );
 329         }
 330
 331         template <typename A0, typename A1>
 332         iterator emplace_hint(const_iterator hint,
 333             BOOST_FWD_REF(A0) a0,
 334             BOOST_FWD_REF(A1) a1)
 335         {
 336             return table_.emplace_hint(hint,
 337                 boost::unordered::detail::create_emplace_args(
 338                     boost::forward<A0>(a0),
 339                     boost::forward<A1>(a1))
 340             );
 341         }
 342
 343         template <typename A0, typename A1, typename A2>
 344         std::pair<iterator, bool> emplace(
 345             BOOST_FWD_REF(A0) a0,
 346             BOOST_FWD_REF(A1) a1,
 347             BOOST_FWD_REF(A2) a2)
 348         {
 349             return table_.emplace(
 350                 boost::unordered::detail::create_emplace_args(
 351                     boost::forward<A0>(a0),
 352                     boost::forward<A1>(a1),
 353                     boost::forward<A2>(a2))
 354             );
 355         }
 356
 357         template <typename A0, typename A1, typename A2>
 358         iterator emplace_hint(const_iterator hint,
 359             BOOST_FWD_REF(A0) a0,
 360             BOOST_FWD_REF(A1) a1,
 361             BOOST_FWD_REF(A2) a2)
 362         {
 363             return table_.emplace_hint(hint,
 364                 boost::unordered::detail::create_emplace_args(
 365                     boost::forward<A0>(a0),
 366                     boost::forward<A1>(a1),
 367                     boost::forward<A2>(a2))
 368             );
 369         }
 370
 371 #define BOOST_UNORDERED_EMPLACE(z, n, _)                                    \
 372             template <                                                      \
 373                 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)                    \
 374             >                                                               \
 375             std::pair<iterator, bool> emplace(                              \
 376                     BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)      \
 377             )                                                               \
 378             {                                                               \
 379                 return table_.emplace(                                      \
 380                     boost::unordered::detail::create_emplace_args(          \
 381                         BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD,  \
 382                             a)                                              \
 383                 ));                                                         \
 384             }                                                               \
 385                                                                             \
 386             template <                                                      \
 387                 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)                    \
 388             >                                                               \
 389             iterator emplace_hint(                                          \
 390                     const_iterator hint,                                    \
 391                     BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)      \
 392             )                                                               \
 393             {                                                               \
 394                 return table_.emplace_hint(hint,                            \
 395                     boost::unordered::detail::create_emplace_args(          \
 396                         BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD,  \
 397                             a)                                              \
 398                 ));                                                         \
 399             }
 400
 401         BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT,
 402             BOOST_UNORDERED_EMPLACE, _)
 403
 404 #undef BOOST_UNORDERED_EMPLACE
 405
 406 #endif
 407
 408         std::pair<iterator, bool> insert(value_type const& x)
 409         {
 410             return this->emplace(x);
 411         }
 412
 413         std::pair<iterator, bool> insert(BOOST_UNORDERED_RV_REF(value_type) x)
 414         {
 415             return this->emplace(boost::move(x));
 416         }
 417
 418         iterator insert(const_iterator hint, value_type const& x)
 419         {
 420             return this->emplace_hint(hint, x);
 421         }
 422
 423         iterator insert(const_iterator hint,
 424                 BOOST_UNORDERED_RV_REF(value_type) x)
 425         {
 426             return this->emplace_hint(hint, boost::move(x));
 427         }
 428
 429         template <class InputIt> void insert(InputIt, InputIt);
 430
 431 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 432         void insert(std::initializer_list<value_type>);
 433 #endif
 434
 435         iterator erase(const_iterator);
 436         size_type erase(const key_type&);
 437         iterator erase(const_iterator, const_iterator);
 438         void quick_erase(const_iterator it) { erase(it); }
 439         void erase_return_void(const_iterator it) { erase(it); }
 440
 441         void clear();
 442         void swap(unordered_set&);
 443
 444         // observers
 445
 446         hasher hash_function() const;
 447         key_equal key_eq() const;
 448
 449         // lookup
 450
 451         const_iterator find(const key_type&) const;
 452
 453         template <class CompatibleKey, class CompatibleHash,
 454             class CompatiblePredicate>
 455         const_iterator find(
 456                 CompatibleKey const&,
 457                 CompatibleHash const&,
 458                 CompatiblePredicate const&) const;
 459
 460         size_type count(const key_type&) const;
 461
 462         std::pair<const_iterator, const_iterator>
 463         equal_range(const key_type&) const;
 464
 465         // bucket interface
 466
 467         size_type bucket_count() const BOOST_NOEXCEPT
 468         {
 469             return table_.bucket_count_;
 470         }
 471
 472         size_type max_bucket_count() const BOOST_NOEXCEPT
 473         {
 474             return table_.max_bucket_count();
 475         }
 476
 477         size_type bucket_size(size_type) const;
 478
 479         size_type bucket(const key_type& k) const
 480         {
 481             return table_.hash_to_bucket(table_.hash(k));
 482         }
 483
 484         local_iterator begin(size_type n)
 485         {
 486             return local_iterator(
 487                 table_.begin(n), n, table_.bucket_count_);
 488         }
 489
 490         const_local_iterator begin(size_type n) const
 491         {
 492             return const_local_iterator(
 493                 table_.begin(n), n, table_.bucket_count_);
 494         }
 495
 496         local_iterator end(size_type)
 497         {
 498             return local_iterator();
 499         }
 500
 501         const_local_iterator end(size_type) const
 502         {
 503             return const_local_iterator();
 504         }
 505
 506         const_local_iterator cbegin(size_type n) const
 507         {
 508             return const_local_iterator(
 509                 table_.begin(n), n, table_.bucket_count_);
 510         }
 511
 512         const_local_iterator cend(size_type) const
 513         {
 514             return const_local_iterator();
 515         }
 516
 517         // hash policy
 518
 519         float max_load_factor() const BOOST_NOEXCEPT
 520         {
 521             return table_.mlf_;
 522         }
 523
 524         float load_factor() const BOOST_NOEXCEPT;
 525         void max_load_factor(float) BOOST_NOEXCEPT;
 526         void rehash(size_type);
 527         void reserve(size_type);
 528
 529 #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
 530         friend bool operator==<T,H,P,A>(
 531                 unordered_set const&, unordered_set const&);
 532         friend bool operator!=<T,H,P,A>(
 533                 unordered_set const&, unordered_set const&);
 534 #endif
 535     }; // class template unordered_set
 536
 537     template <class T, class H, class P, class A>
 538     class unordered_multiset
 539     {
 540 #if defined(BOOST_UNORDERED_USE_MOVE)
 541         BOOST_COPYABLE_AND_MOVABLE(unordered_multiset)
 542 #endif
 543     public:
 544
 545         typedef T key_type;
 546         typedef T value_type;
 547         typedef H hasher;
 548         typedef P key_equal;
 549         typedef A allocator_type;
 550
 551     private:
 552
 553         typedef boost::unordered::detail::multiset<A, T, H, P> types;
 554         typedef typename types::traits allocator_traits;
 555         typedef typename types::table table;
 556
 557     public:
 558
 559         typedef typename allocator_traits::pointer pointer;
 560         typedef typename allocator_traits::const_pointer const_pointer;
 561
 562         typedef value_type& reference;
 563         typedef value_type const& const_reference;
 564
 565         typedef std::size_t size_type;
 566         typedef std::ptrdiff_t difference_type;
 567
 568         typedef typename table::cl_iterator const_local_iterator;
 569         typedef typename table::l_iterator local_iterator;
 570         typedef typename table::c_iterator const_iterator;
 571         typedef typename table::iterator iterator;
 572
 573     private:
 574
 575         table table_;
 576
 577     public:
 578
 579         // constructors
 580
 581         unordered_multiset();
 582
 583         explicit unordered_multiset(
 584                 size_type,
 585                 const hasher& = hasher(),
 586                 const key_equal& = key_equal(),
 587                 const allocator_type& = allocator_type());
 588
 589         explicit unordered_multiset(
 590                 size_type,
 591                 const allocator_type&);
 592
 593         explicit unordered_multiset(
 594                 size_type,
 595                 const hasher&,
 596                 const allocator_type&);
 597
 598         explicit unordered_multiset(allocator_type const&);
 599
 600         template <class InputIt>
 601         unordered_multiset(InputIt, InputIt);
 602
 603         template <class InputIt>
 604         unordered_multiset(
 605                 InputIt, InputIt,
 606                 size_type,
 607                 const hasher& = hasher(),
 608                 const key_equal& = key_equal());
 609
 610         template <class InputIt>
 611         unordered_multiset(
 612                 InputIt, InputIt,
 613                 size_type,
 614                 const hasher&,
 615                 const key_equal&,
 616                 const allocator_type&);
 617
 618         template <class InputIt>
 619         unordered_multiset(
 620                 InputIt, InputIt,
 621                 size_type,
 622                 const hasher&,
 623                 const allocator_type&);
 624
 625         template <class InputIt>
 626         unordered_multiset(
 627                 InputIt, InputIt,
 628                 size_type,
 629                 const allocator_type&);
 630
 631         // copy/move constructors
 632
 633         unordered_multiset(unordered_multiset const&);
 634
 635         unordered_multiset(unordered_multiset const&, allocator_type const&);
 636         unordered_multiset(BOOST_RV_REF(unordered_multiset), allocator_type const&);
 637
 638 #if defined(BOOST_UNORDERED_USE_MOVE)
 639         unordered_multiset(BOOST_RV_REF(unordered_multiset) other)
 640                 BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
 641             : table_(other.table_, boost::unordered::detail::move_tag())
 642         {
 643         }
 644 #elif !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 645         unordered_multiset(unordered_multiset&& other)
 646                 BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
 647             : table_(other.table_, boost::unordered::detail::move_tag())
 648         {
 649         }
 650 #endif
 651
 652 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 653         unordered_multiset(
 654                 std::initializer_list<value_type>,
 655                 size_type = boost::unordered::detail::default_bucket_count,
 656                 const hasher& = hasher(),
 657                 const key_equal&l = key_equal(),
 658                 const allocator_type& = allocator_type());
 659         unordered_multiset(
 660                 std::initializer_list<value_type>,
 661                 size_type,
 662                 const hasher&,
 663                 const allocator_type&);
 664         unordered_multiset(
 665                 std::initializer_list<value_type>,
 666                 size_type,
 667                 const allocator_type&);
 668 #endif
 669
 670         // Destructor
 671
 672         ~unordered_multiset() BOOST_NOEXCEPT;
 673
 674         // Assign
 675
 676 #if defined(BOOST_UNORDERED_USE_MOVE)
 677         unordered_multiset& operator=(
 678                 BOOST_COPY_ASSIGN_REF(unordered_multiset) x)
 679         {
 680             table_.assign(x.table_);
 681             return *this;
 682         }
 683
 684         unordered_multiset& operator=(BOOST_RV_REF(unordered_multiset) x)
 685         {
 686             table_.move_assign(x.table_);
 687             return *this;
 688         }
 689 #else
 690         unordered_multiset& operator=(unordered_multiset const& x)
 691         {
 692             table_.assign(x.table_);
 693             return *this;
 694         }
 695
 696 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 697         unordered_multiset& operator=(unordered_multiset&& x)
 698         {
 699             table_.move_assign(x.table_);
 700             return *this;
 701         }
 702 #endif
 703 #endif
 704
 705 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 706         unordered_multiset& operator=(std::initializer_list<value_type>);
 707 #endif
 708
 709         allocator_type get_allocator() const BOOST_NOEXCEPT
 710         {
 711             return table_.node_alloc();
 712         }
 713
 714         // size and capacity
 715
 716         bool empty() const BOOST_NOEXCEPT
 717         {
 718             return table_.size_ == 0;
 719         }
 720
 721         size_type size() const BOOST_NOEXCEPT
 722         {
 723             return table_.size_;
 724         }
 725
 726         size_type max_size() const BOOST_NOEXCEPT;
 727
 728         // iterators
 729
 730         iterator begin() BOOST_NOEXCEPT
 731         {
 732             return iterator(table_.begin());
 733         }
 734
 735         const_iterator begin() const BOOST_NOEXCEPT
 736         {
 737             return const_iterator(table_.begin());
 738         }
 739
 740         iterator end() BOOST_NOEXCEPT
 741         {
 742             return iterator();
 743         }
 744
 745         const_iterator end() const BOOST_NOEXCEPT
 746         {
 747             return const_iterator();
 748         }
 749
 750         const_iterator cbegin() const BOOST_NOEXCEPT
 751         {
 752             return const_iterator(table_.begin());
 753         }
 754
 755         const_iterator cend() const BOOST_NOEXCEPT
 756         {
 757             return const_iterator();
 758         }
 759
 760         // emplace
 761
 762 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 763         template <class... Args>
 764         iterator emplace(BOOST_FWD_REF(Args)... args)
 765         {
 766             return table_.emplace(boost::forward<Args>(args)...);
 767         }
 768
 769         template <class... Args>
 770         iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
 771         {
 772             return table_.emplace_hint(hint, boost::forward<Args>(args)...);
 773         }
 774 #else
 775
 776 #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
 777
 778         // 0 argument emplace requires special treatment in case
 779         // the container is instantiated with a value type that
 780         // doesn't have a default constructor.
 781
 782         iterator emplace(
 783                 boost::unordered::detail::empty_emplace
 784                     = boost::unordered::detail::empty_emplace(),
 785                 value_type v = value_type())
 786         {
 787             return this->emplace(boost::move(v));
 788         }
 789
 790         iterator emplace_hint(const_iterator hint,
 791                 boost::unordered::detail::empty_emplace
 792                     = boost::unordered::detail::empty_emplace(),
 793                 value_type v = value_type()
 794             )
 795         {
 796             return this->emplace_hint(hint, boost::move(v));
 797         }
 798
 799 #endif
 800
 801         template <typename A0>
 802         iterator emplace(BOOST_FWD_REF(A0) a0)
 803         {
 804             return table_.emplace(
 805                 boost::unordered::detail::create_emplace_args(
 806                     boost::forward<A0>(a0))
 807             );
 808         }
 809
 810         template <typename A0>
 811         iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0)
 812         {
 813             return table_.emplace_hint(hint,
 814                 boost::unordered::detail::create_emplace_args(
 815                     boost::forward<A0>(a0))
 816             );
 817         }
 818
 819         template <typename A0, typename A1>
 820         iterator emplace(
 821             BOOST_FWD_REF(A0) a0,
 822             BOOST_FWD_REF(A1) a1)
 823         {
 824             return table_.emplace(
 825                 boost::unordered::detail::create_emplace_args(
 826                     boost::forward<A0>(a0),
 827                     boost::forward<A1>(a1))
 828             );
 829         }
 830
 831         template <typename A0, typename A1>
 832         iterator emplace_hint(const_iterator hint,
 833             BOOST_FWD_REF(A0) a0,
 834             BOOST_FWD_REF(A1) a1)
 835         {
 836             return table_.emplace_hint(hint,
 837                 boost::unordered::detail::create_emplace_args(
 838                     boost::forward<A0>(a0),
 839                     boost::forward<A1>(a1))
 840             );
 841         }
 842
 843         template <typename A0, typename A1, typename A2>
 844         iterator emplace(
 845             BOOST_FWD_REF(A0) a0,
 846             BOOST_FWD_REF(A1) a1,
 847             BOOST_FWD_REF(A2) a2)
 848         {
 849             return table_.emplace(
 850                 boost::unordered::detail::create_emplace_args(
 851                     boost::forward<A0>(a0),
 852                     boost::forward<A1>(a1),
 853                     boost::forward<A2>(a2))
 854             );
 855         }
 856
 857         template <typename A0, typename A1, typename A2>
 858         iterator emplace_hint(const_iterator hint,
 859             BOOST_FWD_REF(A0) a0,
 860             BOOST_FWD_REF(A1) a1,
 861             BOOST_FWD_REF(A2) a2)
 862         {
 863             return table_.emplace_hint(hint,
 864                 boost::unordered::detail::create_emplace_args(
 865                     boost::forward<A0>(a0),
 866                     boost::forward<A1>(a1),
 867                     boost::forward<A2>(a2))
 868             );
 869         }
 870
 871 #define BOOST_UNORDERED_EMPLACE(z, n, _)                                    \
 872             template <                                                      \
 873                 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)                    \
 874             >                                                               \
 875             iterator emplace(                                               \
 876                     BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)      \
 877             )                                                               \
 878             {                                                               \
 879                 return table_.emplace(                                      \
 880                     boost::unordered::detail::create_emplace_args(          \
 881                         BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD,  \
 882                             a)                                              \
 883                 ));                                                         \
 884             }                                                               \
 885                                                                             \
 886             template <                                                      \
 887                 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)                    \
 888             >                                                               \
 889             iterator emplace_hint(                                          \
 890                     const_iterator hint,                                    \
 891                     BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)      \
 892             )                                                               \
 893             {                                                               \
 894                 return table_.emplace_hint(hint,                            \
 895                     boost::unordered::detail::create_emplace_args(          \
 896                         BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD,  \
 897                             a)                                              \
 898                 ));                                                         \
 899             }
 900
 901         BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT,
 902             BOOST_UNORDERED_EMPLACE, _)
 903
 904 #undef BOOST_UNORDERED_EMPLACE
 905
 906 #endif
 907
 908         iterator insert(value_type const& x)
 909         {
 910             return this->emplace(x);
 911         }
 912
 913         iterator insert(BOOST_UNORDERED_RV_REF(value_type) x)
 914         {
 915             return this->emplace(boost::move(x));
 916         }
 917
 918         iterator insert(const_iterator hint, value_type const& x)
 919         {
 920             return this->emplace_hint(hint, x);
 921         }
 922
 923         iterator insert(const_iterator hint,
 924                 BOOST_UNORDERED_RV_REF(value_type) x)
 925         {
 926             return this->emplace_hint(hint, boost::move(x));
 927         }
 928
 929         template <class InputIt> void insert(InputIt, InputIt);
 930
 931 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 932         void insert(std::initializer_list<value_type>);
 933 #endif
 934
 935         iterator erase(const_iterator);
 936         size_type erase(const key_type&);
 937         iterator erase(const_iterator, const_iterator);
 938         void quick_erase(const_iterator it) { erase(it); }
 939         void erase_return_void(const_iterator it) { erase(it); }
 940
 941         void clear();
 942         void swap(unordered_multiset&);
 943
 944         // observers
 945
 946         hasher hash_function() const;
 947         key_equal key_eq() const;
 948
 949         // lookup
 950
 951         const_iterator find(const key_type&) const;
 952
 953         template <class CompatibleKey, class CompatibleHash,
 954             class CompatiblePredicate>
 955         const_iterator find(
 956                 CompatibleKey const&,
 957                 CompatibleHash const&,
 958                 CompatiblePredicate const&) const;
 959
 960         size_type count(const key_type&) const;
 961
 962         std::pair<const_iterator, const_iterator>
 963         equal_range(const key_type&) const;
 964
 965         // bucket interface
 966
 967         size_type bucket_count() const BOOST_NOEXCEPT
 968         {
 969             return table_.bucket_count_;
 970         }
 971
 972         size_type max_bucket_count() const BOOST_NOEXCEPT
 973         {
 974             return table_.max_bucket_count();
 975         }
 976
 977         size_type bucket_size(size_type) const;
 978
 979         size_type bucket(const key_type& k) const
 980         {
 981             return table_.hash_to_bucket(table_.hash(k));
 982         }
 983
 984         local_iterator begin(size_type n)
 985         {
 986             return local_iterator(
 987                 table_.begin(n), n, table_.bucket_count_);
 988         }
 989
 990         const_local_iterator begin(size_type n) const
 991         {
 992             return const_local_iterator(
 993                 table_.begin(n), n, table_.bucket_count_);
 994         }
 995
 996         local_iterator end(size_type)
 997         {
 998             return local_iterator();
 999         }
1000
1001         const_local_iterator end(size_type) const
1002         {
1003             return const_local_iterator();
1004         }
1005
1006         const_local_iterator cbegin(size_type n) const
1007         {
1008             return const_local_iterator(
1009                 table_.begin(n), n, table_.bucket_count_);
1010         }
1011
1012         const_local_iterator cend(size_type) const
1013         {
1014             return const_local_iterator();
1015         }
1016
1017         // hash policy
1018
1019         float max_load_factor() const BOOST_NOEXCEPT
1020         {
1021             return table_.mlf_;
1022         }
1023
1024         float load_factor() const BOOST_NOEXCEPT;
1025         void max_load_factor(float) BOOST_NOEXCEPT;
1026         void rehash(size_type);
1027         void reserve(size_type);
1028
1029 #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
1030         friend bool operator==<T,H,P,A>(
1031                 unordered_multiset const&, unordered_multiset const&);
1032         friend bool operator!=<T,H,P,A>(
1033                 unordered_multiset const&, unordered_multiset const&);
1034 #endif
1035     }; // class template unordered_multiset
1036
1037 ////////////////////////////////////////////////////////////////////////////////
1038
1039     template <class T, class H, class P, class A>
1040     unordered_set<T,H,P,A>::unordered_set()
1041       : table_(boost::unordered::detail::default_bucket_count, hasher(),
1042             key_equal(), allocator_type())
1043     {
1044     }
1045
1046     template <class T, class H, class P, class A>
1047     unordered_set<T,H,P,A>::unordered_set(
1048             size_type n, const hasher &hf, const key_equal &eql,
1049             const allocator_type &a)
1050       : table_(n, hf, eql, a)
1051     {
1052     }
1053
1054     template <class T, class H, class P, class A>
1055     unordered_set<T,H,P,A>::unordered_set(
1056             size_type n, const allocator_type &a)
1057       : table_(n, hasher(), key_equal(), a)
1058     {
1059     }
1060
1061     template <class T, class H, class P, class A>
1062     unordered_set<T,H,P,A>::unordered_set(
1063             size_type n, const hasher &hf, const allocator_type &a)
1064       : table_(n, hf, key_equal(), a)
1065     {
1066     }
1067
1068     template <class T, class H, class P, class A>
1069     unordered_set<T,H,P,A>::unordered_set(allocator_type const& a)
1070       : table_(boost::unordered::detail::default_bucket_count,
1071             hasher(), key_equal(), a)
1072     {
1073     }
1074
1075     template <class T, class H, class P, class A>
1076     unordered_set<T,H,P,A>::unordered_set(
1077             unordered_set const& other, allocator_type const& a)
1078       : table_(other.table_, a)
1079     {
1080     }
1081
1082     template <class T, class H, class P, class A>
1083     template <class InputIt>
1084     unordered_set<T,H,P,A>::unordered_set(InputIt f, InputIt l)
1085       : table_(boost::unordered::detail::initial_size(f, l),
1086         hasher(), key_equal(), allocator_type())
1087     {
1088         table_.insert_range(f, l);
1089     }
1090
1091     template <class T, class H, class P, class A>
1092     template <class InputIt>
1093     unordered_set<T,H,P,A>::unordered_set(
1094             InputIt f, InputIt l,
1095             size_type n,
1096             const hasher &hf,
1097             const key_equal &eql)
1098       : table_(boost::unordered::detail::initial_size(f, l, n),
1099             hf, eql, allocator_type())
1100     {
1101         table_.insert_range(f, l);
1102     }
1103
1104     template <class T, class H, class P, class A>
1105     template <class InputIt>
1106     unordered_set<T,H,P,A>::unordered_set(
1107             InputIt f, InputIt l,
1108             size_type n,
1109             const hasher &hf,
1110             const key_equal &eql,
1111             const allocator_type &a)
1112       : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
1113     {
1114         table_.insert_range(f, l);
1115     }
1116
1117     template <class T, class H, class P, class A>
1118     template <class InputIt>
1119     unordered_set<T,H,P,A>::unordered_set(
1120             InputIt f, InputIt l,
1121             size_type n,
1122             const hasher &hf,
1123             const allocator_type &a)
1124       : table_(boost::unordered::detail::initial_size(f, l, n),
1125             hf, key_equal(), a)
1126     {
1127         table_.insert_range(f, l);
1128     }
1129
1130     template <class T, class H, class P, class A>
1131     template <class InputIt>
1132     unordered_set<T,H,P,A>::unordered_set(
1133             InputIt f, InputIt l,
1134             size_type n,
1135             const allocator_type &a)
1136       : table_(boost::unordered::detail::initial_size(f, l, n),
1137             hasher(), key_equal(), a)
1138     {
1139         table_.insert_range(f, l);
1140     }
1141
1142     template <class T, class H, class P, class A>
1143     unordered_set<T,H,P,A>::~unordered_set() BOOST_NOEXCEPT {}
1144
1145     template <class T, class H, class P, class A>
1146     unordered_set<T,H,P,A>::unordered_set(
1147             unordered_set const& other)
1148       : table_(other.table_)
1149     {
1150     }
1151
1152     template <class T, class H, class P, class A>
1153     unordered_set<T,H,P,A>::unordered_set(
1154             BOOST_RV_REF(unordered_set) other, allocator_type const& a)
1155       : table_(other.table_, a, boost::unordered::detail::move_tag())
1156     {
1157     }
1158
1159 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1160
1161     template <class T, class H, class P, class A>
1162     unordered_set<T,H,P,A>::unordered_set(
1163             std::initializer_list<value_type> list, size_type n,
1164             const hasher &hf, const key_equal &eql, const allocator_type &a)
1165       : table_(
1166             boost::unordered::detail::initial_size(
1167                 list.begin(), list.end(), n),
1168             hf, eql, a)
1169     {
1170         table_.insert_range(list.begin(), list.end());
1171     }
1172
1173     template <class T, class H, class P, class A>
1174     unordered_set<T,H,P,A>::unordered_set(
1175             std::initializer_list<value_type> list, size_type n,
1176             const hasher &hf, const allocator_type &a)
1177       : table_(
1178             boost::unordered::detail::initial_size(
1179                 list.begin(), list.end(), n),
1180             hf, key_equal(), a)
1181     {
1182         table_.insert_range(list.begin(), list.end());
1183     }
1184
1185     template <class T, class H, class P, class A>
1186     unordered_set<T,H,P,A>::unordered_set(
1187             std::initializer_list<value_type> list, size_type n,
1188             const allocator_type &a)
1189       : table_(
1190             boost::unordered::detail::initial_size(
1191                 list.begin(), list.end(), n),
1192             hasher(), key_equal(), a)
1193     {
1194         table_.insert_range(list.begin(), list.end());
1195     }
1196
1197     template <class T, class H, class P, class A>
1198     unordered_set<T,H,P,A>& unordered_set<T,H,P,A>::operator=(
1199             std::initializer_list<value_type> list)
1200     {
1201         table_.clear();
1202         table_.insert_range(list.begin(), list.end());
1203         return *this;
1204     }
1205
1206 #endif
1207
1208     // size and capacity
1209
1210     template <class T, class H, class P, class A>
1211     std::size_t unordered_set<T,H,P,A>::max_size() const BOOST_NOEXCEPT
1212     {
1213         return table_.max_size();
1214     }
1215
1216     // modifiers
1217
1218     template <class T, class H, class P, class A>
1219     template <class InputIt>
1220     void unordered_set<T,H,P,A>::insert(InputIt first, InputIt last)
1221     {
1222         table_.insert_range(first, last);
1223     }
1224
1225 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1226     template <class T, class H, class P, class A>
1227     void unordered_set<T,H,P,A>::insert(
1228             std::initializer_list<value_type> list)
1229     {
1230         table_.insert_range(list.begin(), list.end());
1231     }
1232 #endif
1233
1234     template <class T, class H, class P, class A>
1235     typename unordered_set<T,H,P,A>::iterator
1236         unordered_set<T,H,P,A>::erase(const_iterator position)
1237     {
1238         return table_.erase(position);
1239     }
1240
1241     template <class T, class H, class P, class A>
1242     typename unordered_set<T,H,P,A>::size_type
1243         unordered_set<T,H,P,A>::erase(const key_type& k)
1244     {
1245         return table_.erase_key(k);
1246     }
1247
1248     template <class T, class H, class P, class A>
1249     typename unordered_set<T,H,P,A>::iterator
1250         unordered_set<T,H,P,A>::erase(
1251             const_iterator first, const_iterator last)
1252     {
1253         return table_.erase_range(first, last);
1254     }
1255
1256     template <class T, class H, class P, class A>
1257     void unordered_set<T,H,P,A>::clear()
1258     {
1259         table_.clear();
1260     }
1261
1262     template <class T, class H, class P, class A>
1263     void unordered_set<T,H,P,A>::swap(unordered_set& other)
1264     {
1265         table_.swap(other.table_);
1266     }
1267
1268     // observers
1269
1270     template <class T, class H, class P, class A>
1271     typename unordered_set<T,H,P,A>::hasher
1272         unordered_set<T,H,P,A>::hash_function() const
1273     {
1274         return table_.hash_function();
1275     }
1276
1277     template <class T, class H, class P, class A>
1278     typename unordered_set<T,H,P,A>::key_equal
1279         unordered_set<T,H,P,A>::key_eq() const
1280     {
1281         return table_.key_eq();
1282     }
1283
1284     // lookup
1285
1286     template <class T, class H, class P, class A>
1287     typename unordered_set<T,H,P,A>::const_iterator
1288         unordered_set<T,H,P,A>::find(const key_type& k) const
1289     {
1290         return const_iterator(table_.find_node(k));
1291     }
1292
1293     template <class T, class H, class P, class A>
1294     template <class CompatibleKey, class CompatibleHash,
1295         class CompatiblePredicate>
1296     typename unordered_set<T,H,P,A>::const_iterator
1297         unordered_set<T,H,P,A>::find(
1298             CompatibleKey const& k,
1299             CompatibleHash const& hash,
1300             CompatiblePredicate const& eq) const
1301     {
1302         return const_iterator(table_.generic_find_node(k, hash, eq));
1303     }
1304
1305     template <class T, class H, class P, class A>
1306     typename unordered_set<T,H,P,A>::size_type
1307         unordered_set<T,H,P,A>::count(const key_type& k) const
1308     {
1309         return table_.count(k);
1310     }
1311
1312     template <class T, class H, class P, class A>
1313     std::pair<
1314             typename unordered_set<T,H,P,A>::const_iterator,
1315             typename unordered_set<T,H,P,A>::const_iterator>
1316         unordered_set<T,H,P,A>::equal_range(const key_type& k) const
1317     {
1318         return table_.equal_range(k);
1319     }
1320
1321     template <class T, class H, class P, class A>
1322     typename unordered_set<T,H,P,A>::size_type
1323         unordered_set<T,H,P,A>::bucket_size(size_type n) const
1324     {
1325         return table_.bucket_size(n);
1326     }
1327
1328     // hash policy
1329
1330     template <class T, class H, class P, class A>
1331     float unordered_set<T,H,P,A>::load_factor() const BOOST_NOEXCEPT
1332     {
1333         return table_.load_factor();
1334     }
1335
1336     template <class T, class H, class P, class A>
1337     void unordered_set<T,H,P,A>::max_load_factor(float m) BOOST_NOEXCEPT
1338     {
1339         table_.max_load_factor(m);
1340     }
1341
1342     template <class T, class H, class P, class A>
1343     void unordered_set<T,H,P,A>::rehash(size_type n)
1344     {
1345         table_.rehash(n);
1346     }
1347
1348     template <class T, class H, class P, class A>
1349     void unordered_set<T,H,P,A>::reserve(size_type n)
1350     {
1351         table_.reserve(n);
1352     }
1353
1354     template <class T, class H, class P, class A>
1355     inline bool operator==(
1356             unordered_set<T,H,P,A> const& m1,
1357             unordered_set<T,H,P,A> const& m2)
1358     {
1359 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1360         struct dummy { unordered_set<T,H,P,A> x; };
1361 #endif
1362         return m1.table_.equals(m2.table_);
1363     }
1364
1365     template <class T, class H, class P, class A>
1366     inline bool operator!=(
1367             unordered_set<T,H,P,A> const& m1,
1368             unordered_set<T,H,P,A> const& m2)
1369     {
1370 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1371         struct dummy { unordered_set<T,H,P,A> x; };
1372 #endif
1373         return !m1.table_.equals(m2.table_);
1374     }
1375
1376     template <class T, class H, class P, class A>
1377     inline void swap(
1378             unordered_set<T,H,P,A> &m1,
1379             unordered_set<T,H,P,A> &m2)
1380     {
1381 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1382         struct dummy { unordered_set<T,H,P,A> x; };
1383 #endif
1384         m1.swap(m2);
1385     }
1386
1387 ////////////////////////////////////////////////////////////////////////////////
1388
1389     template <class T, class H, class P, class A>
1390     unordered_multiset<T,H,P,A>::unordered_multiset()
1391       : table_(boost::unordered::detail::default_bucket_count, hasher(),
1392             key_equal(), allocator_type())
1393     {
1394     }
1395
1396     template <class T, class H, class P, class A>
1397     unordered_multiset<T,H,P,A>::unordered_multiset(
1398             size_type n, const hasher &hf, const key_equal &eql,
1399             const allocator_type &a)
1400       : table_(n, hf, eql, a)
1401     {
1402     }
1403
1404     template <class T, class H, class P, class A>
1405     unordered_multiset<T,H,P,A>::unordered_multiset(
1406             size_type n, const allocator_type &a)
1407       : table_(n, hasher(), key_equal(), a)
1408     {
1409     }
1410
1411     template <class T, class H, class P, class A>
1412     unordered_multiset<T,H,P,A>::unordered_multiset(
1413             size_type n, const hasher &hf, const allocator_type &a)
1414       : table_(n, hf, key_equal(), a)
1415     {
1416     }
1417
1418     template <class T, class H, class P, class A>
1419     unordered_multiset<T,H,P,A>::unordered_multiset(allocator_type const& a)
1420       : table_(boost::unordered::detail::default_bucket_count,
1421             hasher(), key_equal(), a)
1422     {
1423     }
1424
1425     template <class T, class H, class P, class A>
1426     unordered_multiset<T,H,P,A>::unordered_multiset(
1427             unordered_multiset const& other, allocator_type const& a)
1428       : table_(other.table_, a)
1429     {
1430     }
1431
1432     template <class T, class H, class P, class A>
1433     template <class InputIt>
1434     unordered_multiset<T,H,P,A>::unordered_multiset(InputIt f, InputIt l)
1435       : table_(boost::unordered::detail::initial_size(f, l),
1436         hasher(), key_equal(), allocator_type())
1437     {
1438         table_.insert_range(f, l);
1439     }
1440
1441     template <class T, class H, class P, class A>
1442     template <class InputIt>
1443     unordered_multiset<T,H,P,A>::unordered_multiset(
1444             InputIt f, InputIt l,
1445             size_type n,
1446             const hasher &hf,
1447             const key_equal &eql)
1448       : table_(boost::unordered::detail::initial_size(f, l, n),
1449             hf, eql, allocator_type())
1450     {
1451         table_.insert_range(f, l);
1452     }
1453
1454     template <class T, class H, class P, class A>
1455     template <class InputIt>
1456     unordered_multiset<T,H,P,A>::unordered_multiset(
1457             InputIt f, InputIt l,
1458             size_type n,
1459             const hasher &hf,
1460             const key_equal &eql,
1461             const allocator_type &a)
1462       : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
1463     {
1464         table_.insert_range(f, l);
1465     }
1466
1467     template <class T, class H, class P, class A>
1468     template <class InputIt>
1469     unordered_multiset<T,H,P,A>::unordered_multiset(
1470             InputIt f, InputIt l,
1471             size_type n,
1472             const hasher &hf,
1473             const allocator_type &a)
1474       : table_(boost::unordered::detail::initial_size(f, l, n),
1475             hf, key_equal(), a)
1476     {
1477         table_.insert_range(f, l);
1478     }
1479
1480     template <class T, class H, class P, class A>
1481     template <class InputIt>
1482     unordered_multiset<T,H,P,A>::unordered_multiset(
1483             InputIt f, InputIt l,
1484             size_type n,
1485             const allocator_type &a)
1486       : table_(boost::unordered::detail::initial_size(f, l, n),
1487             hasher(), key_equal(), a)
1488     {
1489         table_.insert_range(f, l);
1490     }
1491
1492     template <class T, class H, class P, class A>
1493     unordered_multiset<T,H,P,A>::~unordered_multiset() BOOST_NOEXCEPT {}
1494
1495     template <class T, class H, class P, class A>
1496     unordered_multiset<T,H,P,A>::unordered_multiset(
1497             unordered_multiset const& other)
1498       : table_(other.table_)
1499     {
1500     }
1501
1502     template <class T, class H, class P, class A>
1503     unordered_multiset<T,H,P,A>::unordered_multiset(
1504             BOOST_RV_REF(unordered_multiset) other, allocator_type const& a)
1505       : table_(other.table_, a, boost::unordered::detail::move_tag())
1506     {
1507     }
1508
1509 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1510
1511     template <class T, class H, class P, class A>
1512     unordered_multiset<T,H,P,A>::unordered_multiset(
1513             std::initializer_list<value_type> list, size_type n,
1514             const hasher &hf, const key_equal &eql, const allocator_type &a)
1515       : table_(
1516             boost::unordered::detail::initial_size(
1517                 list.begin(), list.end(), n),
1518             hf, eql, a)
1519     {
1520         table_.insert_range(list.begin(), list.end());
1521     }
1522
1523     template <class T, class H, class P, class A>
1524     unordered_multiset<T,H,P,A>::unordered_multiset(
1525             std::initializer_list<value_type> list, size_type n,
1526             const hasher &hf, const allocator_type &a)
1527       : table_(
1528             boost::unordered::detail::initial_size(
1529                 list.begin(), list.end(), n),
1530             hf, key_equal(), a)
1531     {
1532         table_.insert_range(list.begin(), list.end());
1533     }
1534
1535     template <class T, class H, class P, class A>
1536     unordered_multiset<T,H,P,A>::unordered_multiset(
1537             std::initializer_list<value_type> list, size_type n,
1538             const allocator_type &a)
1539       : table_(
1540             boost::unordered::detail::initial_size(
1541                 list.begin(), list.end(), n),
1542             hasher(), key_equal(), a)
1543     {
1544         table_.insert_range(list.begin(), list.end());
1545     }
1546
1547     template <class T, class H, class P, class A>
1548     unordered_multiset<T,H,P,A>& unordered_multiset<T,H,P,A>::operator=(
1549             std::initializer_list<value_type> list)
1550     {
1551         table_.clear();
1552         table_.insert_range(list.begin(), list.end());
1553         return *this;
1554     }
1555
1556 #endif
1557
1558     // size and capacity
1559
1560     template <class T, class H, class P, class A>
1561     std::size_t unordered_multiset<T,H,P,A>::max_size() const BOOST_NOEXCEPT
1562     {
1563         return table_.max_size();
1564     }
1565
1566     // modifiers
1567
1568     template <class T, class H, class P, class A>
1569     template <class InputIt>
1570     void unordered_multiset<T,H,P,A>::insert(InputIt first, InputIt last)
1571     {
1572         table_.insert_range(first, last);
1573     }
1574
1575 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1576     template <class T, class H, class P, class A>
1577     void unordered_multiset<T,H,P,A>::insert(
1578             std::initializer_list<value_type> list)
1579     {
1580         table_.insert_range(list.begin(), list.end());
1581     }
1582 #endif
1583
1584     template <class T, class H, class P, class A>
1585     typename unordered_multiset<T,H,P,A>::iterator
1586         unordered_multiset<T,H,P,A>::erase(const_iterator position)
1587     {
1588         return table_.erase(position);
1589     }
1590
1591     template <class T, class H, class P, class A>
1592     typename unordered_multiset<T,H,P,A>::size_type
1593         unordered_multiset<T,H,P,A>::erase(const key_type& k)
1594     {
1595         return table_.erase_key(k);
1596     }
1597
1598     template <class T, class H, class P, class A>
1599     typename unordered_multiset<T,H,P,A>::iterator
1600         unordered_multiset<T,H,P,A>::erase(
1601                 const_iterator first, const_iterator last)
1602     {
1603         return table_.erase_range(first, last);
1604     }
1605
1606     template <class T, class H, class P, class A>
1607     void unordered_multiset<T,H,P,A>::clear()
1608     {
1609         table_.clear();
1610     }
1611
1612     template <class T, class H, class P, class A>
1613     void unordered_multiset<T,H,P,A>::swap(unordered_multiset& other)
1614     {
1615         table_.swap(other.table_);
1616     }
1617
1618     // observers
1619
1620     template <class T, class H, class P, class A>
1621     typename unordered_multiset<T,H,P,A>::hasher
1622         unordered_multiset<T,H,P,A>::hash_function() const
1623     {
1624         return table_.hash_function();
1625     }
1626
1627     template <class T, class H, class P, class A>
1628     typename unordered_multiset<T,H,P,A>::key_equal
1629         unordered_multiset<T,H,P,A>::key_eq() const
1630     {
1631         return table_.key_eq();
1632     }
1633
1634     // lookup
1635
1636     template <class T, class H, class P, class A>
1637     typename unordered_multiset<T,H,P,A>::const_iterator
1638         unordered_multiset<T,H,P,A>::find(const key_type& k) const
1639     {
1640         return const_iterator(table_.find_node(k));
1641     }
1642
1643     template <class T, class H, class P, class A>
1644     template <class CompatibleKey, class CompatibleHash,
1645         class CompatiblePredicate>
1646     typename unordered_multiset<T,H,P,A>::const_iterator
1647         unordered_multiset<T,H,P,A>::find(
1648             CompatibleKey const& k,
1649             CompatibleHash const& hash,
1650             CompatiblePredicate const& eq) const
1651     {
1652         return const_iterator(table_.generic_find_node(k, hash, eq));
1653     }
1654
1655     template <class T, class H, class P, class A>
1656     typename unordered_multiset<T,H,P,A>::size_type
1657         unordered_multiset<T,H,P,A>::count(const key_type& k) const
1658     {
1659         return table_.count(k);
1660     }
1661
1662     template <class T, class H, class P, class A>
1663     std::pair<
1664             typename unordered_multiset<T,H,P,A>::const_iterator,
1665             typename unordered_multiset<T,H,P,A>::const_iterator>
1666         unordered_multiset<T,H,P,A>::equal_range(const key_type& k) const
1667     {
1668         return table_.equal_range(k);
1669     }
1670
1671     template <class T, class H, class P, class A>
1672     typename unordered_multiset<T,H,P,A>::size_type
1673         unordered_multiset<T,H,P,A>::bucket_size(size_type n) const
1674     {
1675         return table_.bucket_size(n);
1676     }
1677
1678     // hash policy
1679
1680     template <class T, class H, class P, class A>
1681     float unordered_multiset<T,H,P,A>::load_factor() const BOOST_NOEXCEPT
1682     {
1683         return table_.load_factor();
1684     }
1685
1686     template <class T, class H, class P, class A>
1687     void unordered_multiset<T,H,P,A>::max_load_factor(float m) BOOST_NOEXCEPT
1688     {
1689         table_.max_load_factor(m);
1690     }
1691
1692     template <class T, class H, class P, class A>
1693     void unordered_multiset<T,H,P,A>::rehash(size_type n)
1694     {
1695         table_.rehash(n);
1696     }
1697
1698     template <class T, class H, class P, class A>
1699     void unordered_multiset<T,H,P,A>::reserve(size_type n)
1700     {
1701         table_.reserve(n);
1702     }
1703
1704     template <class T, class H, class P, class A>
1705     inline bool operator==(
1706             unordered_multiset<T,H,P,A> const& m1,
1707             unordered_multiset<T,H,P,A> const& m2)
1708     {
1709 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1710         struct dummy { unordered_multiset<T,H,P,A> x; };
1711 #endif
1712         return m1.table_.equals(m2.table_);
1713     }
1714
1715     template <class T, class H, class P, class A>
1716     inline bool operator!=(
1717             unordered_multiset<T,H,P,A> const& m1,
1718             unordered_multiset<T,H,P,A> const& m2)
1719     {
1720 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1721         struct dummy { unordered_multiset<T,H,P,A> x; };
1722 #endif
1723         return !m1.table_.equals(m2.table_);
1724     }
1725
1726     template <class T, class H, class P, class A>
1727     inline void swap(
1728             unordered_multiset<T,H,P,A> &m1,
1729             unordered_multiset<T,H,P,A> &m2)
1730     {
1731 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1732         struct dummy { unordered_multiset<T,H,P,A> x; };
1733 #endif
1734         m1.swap(m2);
1735     }
1736 } // namespace unordered
1737 } // namespace boost
1738
1739 #if defined(BOOST_MSVC)
1740 #pragma warning(pop)
1741 #endif
1742
1743 #endif // BOOST_UNORDERED_UNORDERED_SET_HPP_INCLUDED