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