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