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