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/core/explicit_operator_bool.hpp> 18 #include <boost/functional/hash.hpp> 19 #include <boost/move/move.hpp> 20 #include <boost/type_traits/is_constructible.hpp> 21 #include <boost/unordered/detail/map.hpp> 22 23 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 24 #include <initializer_list> 25 #endif 26 27 #if defined(BOOST_MSVC) 28 #pragma warning(push) 29 // conditional expression is constant 30 #pragma warning(disable : 4127) 31 #if BOOST_MSVC >= 1400 32 // the inline specifier cannot be used when a friend declaration refers to a 33 // specialization of a function template 34 #pragma warning(disable : 4396) 35 #endif 36 #endif 37 38 namespace boost { 39 namespace unordered { 40 template <class K, class T, class H, class P, class A> class unordered_map 41 { 42 #if defined(BOOST_UNORDERED_USE_MOVE) 43 BOOST_COPYABLE_AND_MOVABLE(unordered_map) 44 #endif 45 template <typename, typename, typename, typename, typename> 46 friend class unordered_multimap; 47 48 public: 49 typedef K key_type; 50 typedef T mapped_type; 51 typedef std::pair<const K, T> value_type; 52 typedef H hasher; 53 typedef P key_equal; 54 typedef A allocator_type; 55 56 private: 57 typedef boost::unordered::detail::map<A, K, T, H, P> types; 58 typedef typename types::value_allocator_traits value_allocator_traits; 59 typedef typename types::table table; 60 typedef typename table::node_pointer node_pointer; 61 typedef typename table::link_pointer link_pointer; 62 63 public: 64 typedef typename value_allocator_traits::pointer pointer; 65 typedef typename value_allocator_traits::const_pointer const_pointer; 66 67 typedef value_type& reference; 68 typedef value_type const& const_reference; 69 70 typedef std::size_t size_type; 71 typedef std::ptrdiff_t difference_type; 72 73 typedef typename table::iterator iterator; 74 typedef typename table::c_iterator const_iterator; 75 typedef typename table::l_iterator local_iterator; 76 typedef typename table::cl_iterator const_local_iterator; 77 typedef typename types::node_type node_type; 78 typedef typename types::insert_return_type insert_return_type; 79 80 private: 81 table table_; 82 83 public: 84 // constructors 85 86 unordered_map(); 87 88 explicit unordered_map(size_type, const hasher& = hasher(), 89 const key_equal& = key_equal(), 90 const allocator_type& = allocator_type()); 91 92 template <class InputIt> 93 unordered_map(InputIt, InputIt, 94 size_type = boost::unordered::detail::default_bucket_count, 95 const hasher& = hasher(), const key_equal& = key_equal(), 96 const allocator_type& = allocator_type()); 97 98 unordered_map(unordered_map const&); 99 100 #if defined(BOOST_UNORDERED_USE_MOVE) || \ 101 !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 102 unordered_map(BOOST_RV_REF(unordered_map) other) BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)103 BOOST_NOEXCEPT_IF(table::nothrow_move_constructible) 104 : table_(other.table_, boost::unordered::detail::move_tag()) 105 { 106 // The move is done in table_ 107 } 108 #endif 109 110 explicit unordered_map(allocator_type const&); 111 112 unordered_map(unordered_map const&, allocator_type const&); 113 114 unordered_map(BOOST_RV_REF(unordered_map), allocator_type const&); 115 116 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 117 unordered_map(std::initializer_list<value_type>, 118 size_type = boost::unordered::detail::default_bucket_count, 119 const hasher& = hasher(), const key_equal& l = key_equal(), 120 const allocator_type& = allocator_type()); 121 #endif 122 123 explicit unordered_map(size_type, const allocator_type&); 124 125 explicit unordered_map(size_type, const hasher&, const allocator_type&); 126 127 template <class InputIt> 128 unordered_map(InputIt, InputIt, size_type, const allocator_type&); 129 130 template <class InputIt> 131 unordered_map( 132 InputIt, InputIt, size_type, const hasher&, const allocator_type&); 133 134 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 135 unordered_map( 136 std::initializer_list<value_type>, size_type, const allocator_type&); 137 138 unordered_map(std::initializer_list<value_type>, size_type, const hasher&, 139 const allocator_type&); 140 #endif 141 142 // Destructor 143 144 ~unordered_map() BOOST_NOEXCEPT; 145 146 // Assign 147 148 #if defined(BOOST_UNORDERED_USE_MOVE) operator =(BOOST_COPY_ASSIGN_REF (unordered_map)x)149 unordered_map& operator=(BOOST_COPY_ASSIGN_REF(unordered_map) x) 150 { 151 table_.assign(x.table_, boost::unordered::detail::true_type()); 152 return *this; 153 } 154 operator =(BOOST_RV_REF (unordered_map)x)155 unordered_map& operator=(BOOST_RV_REF(unordered_map) x) 156 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 157 boost::is_nothrow_move_assignable<H>::value&& 158 boost::is_nothrow_move_assignable<P>::value) 159 { 160 table_.move_assign(x.table_, boost::unordered::detail::true_type()); 161 return *this; 162 } 163 #else operator =(unordered_map const & x)164 unordered_map& operator=(unordered_map const& x) 165 { 166 table_.assign(x.table_, boost::unordered::detail::true_type()); 167 return *this; 168 } 169 170 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) operator =(unordered_map && x)171 unordered_map& operator=(unordered_map&& x) 172 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 173 boost::is_nothrow_move_assignable<H>::value&& 174 boost::is_nothrow_move_assignable<P>::value) 175 { 176 table_.move_assign(x.table_, boost::unordered::detail::true_type()); 177 return *this; 178 } 179 #endif 180 #endif 181 182 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 183 unordered_map& operator=(std::initializer_list<value_type>); 184 #endif 185 get_allocator() const186 allocator_type get_allocator() const BOOST_NOEXCEPT 187 { 188 return table_.node_alloc(); 189 } 190 191 // iterators 192 begin()193 iterator begin() BOOST_NOEXCEPT { return iterator(table_.begin()); } 194 begin() const195 const_iterator begin() const BOOST_NOEXCEPT 196 { 197 return const_iterator(table_.begin()); 198 } 199 end()200 iterator end() BOOST_NOEXCEPT { return iterator(); } 201 end() const202 const_iterator end() const BOOST_NOEXCEPT { return const_iterator(); } 203 cbegin() const204 const_iterator cbegin() const BOOST_NOEXCEPT 205 { 206 return const_iterator(table_.begin()); 207 } 208 cend() const209 const_iterator cend() const BOOST_NOEXCEPT { return const_iterator(); } 210 211 // size and capacity 212 empty() const213 bool empty() const BOOST_NOEXCEPT { return table_.size_ == 0; } 214 size() const215 size_type size() const BOOST_NOEXCEPT { return table_.size_; } 216 217 size_type max_size() const BOOST_NOEXCEPT; 218 219 // emplace 220 221 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 222 223 template <class... Args> emplace(BOOST_FWD_REF (Args)...args)224 std::pair<iterator, bool> emplace(BOOST_FWD_REF(Args)... args) 225 { 226 return table_.emplace_unique( 227 table::extractor::extract(boost::forward<Args>(args)...), 228 boost::forward<Args>(args)...); 229 } 230 231 #else 232 233 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1 234 235 // 0 argument emplace requires special treatment in case 236 // the container is instantiated with a value type that 237 // doesn't have a default constructor. 238 emplace(boost::unordered::detail::empty_emplace=boost::unordered::detail::empty_emplace (),value_type v=value_type ())239 std::pair<iterator, bool> emplace( 240 boost::unordered::detail::empty_emplace = 241 boost::unordered::detail::empty_emplace(), 242 value_type v = value_type()) 243 { 244 return this->emplace(boost::move(v)); 245 } 246 247 #endif 248 249 template <typename A0> emplace(BOOST_FWD_REF (A0)a0)250 std::pair<iterator, bool> emplace(BOOST_FWD_REF(A0) a0) 251 { 252 return table_.emplace_unique( 253 table::extractor::extract(boost::forward<A0>(a0)), 254 boost::unordered::detail::create_emplace_args( 255 boost::forward<A0>(a0))); 256 } 257 258 template <typename A0, typename A1> emplace(BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1)259 std::pair<iterator, bool> emplace( 260 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1) 261 { 262 return table_.emplace_unique( 263 table::extractor::extract( 264 boost::forward<A0>(a0), boost::forward<A1>(a1)), 265 boost::unordered::detail::create_emplace_args( 266 boost::forward<A0>(a0), boost::forward<A1>(a1))); 267 } 268 269 template <typename A0, typename A1, typename A2> emplace(BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1,BOOST_FWD_REF (A2)a2)270 std::pair<iterator, bool> emplace( 271 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 272 { 273 return table_.emplace_unique( 274 table::extractor::extract( 275 boost::forward<A0>(a0), boost::forward<A1>(a1)), 276 boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0), 277 boost::forward<A1>(a1), boost::forward<A2>(a2))); 278 } 279 280 #endif 281 282 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 283 284 template <class... Args> emplace_hint(const_iterator hint,BOOST_FWD_REF (Args)...args)285 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args) 286 { 287 return table_.emplace_hint_unique(hint, 288 table::extractor::extract(boost::forward<Args>(args)...), 289 boost::forward<Args>(args)...); 290 } 291 292 #else 293 294 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1 295 emplace_hint(const_iterator hint,boost::unordered::detail::empty_emplace=boost::unordered::detail::empty_emplace (),value_type v=value_type ())296 iterator emplace_hint(const_iterator hint, 297 boost::unordered::detail::empty_emplace = 298 boost::unordered::detail::empty_emplace(), 299 value_type v = value_type()) 300 { 301 return this->emplace_hint(hint, boost::move(v)); 302 } 303 304 #endif 305 306 template <typename A0> emplace_hint(const_iterator hint,BOOST_FWD_REF (A0)a0)307 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0) 308 { 309 return table_.emplace_hint_unique(hint, 310 table::extractor::extract(boost::forward<A0>(a0)), 311 boost::unordered::detail::create_emplace_args( 312 boost::forward<A0>(a0))); 313 } 314 315 template <typename A0, typename A1> emplace_hint(const_iterator hint,BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1)316 iterator emplace_hint( 317 const_iterator hint, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1) 318 { 319 return table_.emplace_hint_unique(hint, 320 table::extractor::extract( 321 boost::forward<A0>(a0), boost::forward<A1>(a1)), 322 boost::unordered::detail::create_emplace_args( 323 boost::forward<A0>(a0), boost::forward<A1>(a1))); 324 } 325 326 template <typename A0, typename A1, typename A2> emplace_hint(const_iterator hint,BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1,BOOST_FWD_REF (A2)a2)327 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0, 328 BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 329 { 330 return table_.emplace_hint_unique(hint, 331 table::extractor::extract( 332 boost::forward<A0>(a0), boost::forward<A1>(a1)), 333 boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0), 334 boost::forward<A1>(a1), boost::forward<A2>(a2))); 335 } 336 337 #endif 338 339 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 340 341 #define BOOST_UNORDERED_EMPLACE(z, n, _) \ 342 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 343 std::pair<iterator, bool> emplace( \ 344 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \ 345 { \ 346 return table_.emplace_unique( \ 347 table::extractor::extract( \ 348 boost::forward<A0>(a0), boost::forward<A1>(a1)), \ 349 boost::unordered::detail::create_emplace_args( \ 350 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \ 351 } \ 352 \ 353 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 354 iterator emplace_hint( \ 355 const_iterator hint, BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \ 356 { \ 357 return table_.emplace_hint_unique(hint, \ 358 table::extractor::extract( \ 359 boost::forward<A0>(a0), boost::forward<A1>(a1)), \ 360 boost::unordered::detail::create_emplace_args( \ 361 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \ 362 } 363 364 BOOST_UNORDERED_EMPLACE(1, 4, _) 365 BOOST_UNORDERED_EMPLACE(1, 5, _) 366 BOOST_UNORDERED_EMPLACE(1, 6, _) 367 BOOST_UNORDERED_EMPLACE(1, 7, _) 368 BOOST_UNORDERED_EMPLACE(1, 8, _) 369 BOOST_UNORDERED_EMPLACE(1, 9, _) BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT)370 BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT), 371 BOOST_UNORDERED_EMPLACE, _) 372 373 #undef BOOST_UNORDERED_EMPLACE 374 375 #endif 376 377 std::pair<iterator, bool> insert(value_type const& x) 378 { 379 return this->emplace(x); 380 } 381 insert(BOOST_RV_REF (value_type)x)382 std::pair<iterator, bool> insert(BOOST_RV_REF(value_type) x) 383 { 384 return this->emplace(boost::move(x)); 385 } 386 387 template <class P2> insert(BOOST_RV_REF (P2)obj,typename boost::enable_if_c<boost::is_constructible<value_type,BOOST_RV_REF (P2)>::value,void * >::type=0)388 std::pair<iterator, bool> insert(BOOST_RV_REF(P2) obj, 389 typename boost::enable_if_c< 390 boost::is_constructible<value_type, BOOST_RV_REF(P2)>::value, 391 void*>::type = 0) 392 { 393 return this->emplace(boost::forward<P2>(obj)); 394 } 395 insert(const_iterator hint,value_type const & x)396 iterator insert(const_iterator hint, value_type const& x) 397 { 398 return this->emplace_hint(hint, x); 399 } 400 insert(const_iterator hint,BOOST_RV_REF (value_type)x)401 iterator insert(const_iterator hint, BOOST_RV_REF(value_type) x) 402 { 403 return this->emplace_hint(hint, boost::move(x)); 404 } 405 406 template <class P2> insert(const_iterator hint,BOOST_RV_REF (P2)obj,typename boost::enable_if_c<boost::is_constructible<value_type,BOOST_RV_REF (P2)>::value,void * >::type=0)407 iterator insert(const_iterator hint, BOOST_RV_REF(P2) obj, 408 typename boost::enable_if_c< 409 boost::is_constructible<value_type, BOOST_RV_REF(P2)>::value, 410 void*>::type = 0) 411 { 412 return this->emplace_hint(hint, boost::forward<P2>(obj)); 413 } 414 415 template <class InputIt> void insert(InputIt, InputIt); 416 417 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 418 void insert(std::initializer_list<value_type>); 419 #endif 420 421 // extract 422 extract(const_iterator position)423 node_type extract(const_iterator position) 424 { 425 return node_type( 426 table_.extract_by_iterator_unique(position), table_.node_alloc()); 427 } 428 extract(const key_type & k)429 node_type extract(const key_type& k) 430 { 431 return node_type(table_.extract_by_key(k), table_.node_alloc()); 432 } 433 insert(BOOST_RV_REF (node_type)np)434 insert_return_type insert(BOOST_RV_REF(node_type) np) 435 { 436 insert_return_type result; 437 table_.move_insert_node_type_unique(np, result); 438 return boost::move(result); 439 } 440 insert(const_iterator hint,BOOST_RV_REF (node_type)np)441 iterator insert(const_iterator hint, BOOST_RV_REF(node_type) np) 442 { 443 return table_.move_insert_node_type_with_hint_unique(hint, np); 444 } 445 446 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || \ 447 (BOOST_COMP_GNUC && BOOST_COMP_GNUC < BOOST_VERSION_NUMBER(4, 6, 0)) 448 private: 449 // Note: Use r-value node_type to insert. 450 insert_return_type insert(node_type&); 451 iterator insert(const_iterator, node_type& np); 452 453 public: 454 #endif 455 456 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 457 458 template <class... Args> try_emplace(key_type const & k,BOOST_FWD_REF (Args)...args)459 std::pair<iterator, bool> try_emplace( 460 key_type const& k, BOOST_FWD_REF(Args)... args) 461 { 462 return table_.try_emplace_unique(k, boost::forward<Args>(args)...); 463 } 464 465 template <class... Args> try_emplace(BOOST_RV_REF (key_type)k,BOOST_FWD_REF (Args)...args)466 std::pair<iterator, bool> try_emplace( 467 BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args) 468 { 469 return table_.try_emplace_unique( 470 boost::move(k), boost::forward<Args>(args)...); 471 } 472 473 template <class... Args> try_emplace(const_iterator hint,key_type const & k,BOOST_FWD_REF (Args)...args)474 iterator try_emplace( 475 const_iterator hint, key_type const& k, BOOST_FWD_REF(Args)... args) 476 { 477 return table_.try_emplace_hint_unique( 478 hint, k, boost::forward<Args>(args)...); 479 } 480 481 template <class... Args> try_emplace(const_iterator hint,BOOST_RV_REF (key_type)k,BOOST_FWD_REF (Args)...args)482 iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, 483 BOOST_FWD_REF(Args)... args) 484 { 485 return table_.try_emplace_hint_unique( 486 hint, boost::move(k), boost::forward<Args>(args)...); 487 } 488 489 #else 490 491 // In order to make this a template, this handles both: 492 // try_emplace(key const&) 493 // try_emplace(key&&) 494 495 template <typename Key> 496 std::pair<iterator, bool> try_emplace(BOOST_FWD_REF(Key) k) 497 { 498 return table_.try_emplace_unique(boost::forward<Key>(k)); 499 } 500 501 // In order to make this a template, this handles both: 502 // try_emplace(const_iterator hint, key const&) 503 // try_emplace(const_iterator hint, key&&) 504 505 template <typename Key> 506 iterator try_emplace(const_iterator hint, BOOST_FWD_REF(Key) k) 507 { 508 return table_.try_emplace_hint_unique(hint, boost::forward<Key>(k)); 509 } 510 511 // try_emplace(key const&, Args&&...) 512 513 template <typename A0> 514 std::pair<iterator, bool> try_emplace( 515 key_type const& k, BOOST_FWD_REF(A0) a0) 516 { 517 return table_.try_emplace_unique( 518 k, boost::unordered::detail::create_emplace_args( 519 boost::forward<A0>(a0))); 520 } 521 522 template <typename A0, typename A1> 523 std::pair<iterator, bool> try_emplace( 524 key_type const& k, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1) 525 { 526 return table_.try_emplace_unique( 527 k, boost::unordered::detail::create_emplace_args( 528 boost::forward<A0>(a0), boost::forward<A1>(a1))); 529 } 530 531 template <typename A0, typename A1, typename A2> 532 std::pair<iterator, bool> try_emplace(key_type const& k, 533 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 534 { 535 return table_.try_emplace_unique(k, 536 boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0), 537 boost::forward<A1>(a1), boost::forward<A2>(a2))); 538 } 539 540 // try_emplace(key&&, Args&&...) 541 542 template <typename A0> 543 std::pair<iterator, bool> try_emplace( 544 BOOST_RV_REF(key_type) k, BOOST_FWD_REF(A0) a0) 545 { 546 return table_.try_emplace_unique( 547 boost::move(k), boost::unordered::detail::create_emplace_args( 548 boost::forward<A0>(a0))); 549 } 550 551 template <typename A0, typename A1> 552 std::pair<iterator, bool> try_emplace( 553 BOOST_RV_REF(key_type) k, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1) 554 { 555 return table_.try_emplace_unique( 556 boost::move(k), boost::unordered::detail::create_emplace_args( 557 boost::forward<A0>(a0), boost::forward<A1>(a1))); 558 } 559 560 template <typename A0, typename A1, typename A2> 561 std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, 562 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 563 { 564 return table_.try_emplace_unique(boost::move(k), 565 boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0), 566 boost::forward<A1>(a1), boost::forward<A2>(a2))); 567 } 568 569 // try_emplace(const_iterator hint, key const&, Args&&...) 570 571 template <typename A0> 572 iterator try_emplace( 573 const_iterator hint, key_type const& k, BOOST_FWD_REF(A0) a0) 574 { 575 return table_.try_emplace_hint_unique( 576 hint, k, boost::unordered::detail::create_emplace_args( 577 boost::forward<A0>(a0))); 578 } 579 580 template <typename A0, typename A1> 581 iterator try_emplace(const_iterator hint, key_type const& k, 582 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1) 583 { 584 return table_.try_emplace_hint_unique( 585 hint, k, boost::unordered::detail::create_emplace_args( 586 boost::forward<A0>(a0), boost::forward<A1>(a1))); 587 } 588 589 template <typename A0, typename A1, typename A2> 590 iterator try_emplace(const_iterator hint, key_type const& k, 591 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 592 { 593 return table_.try_emplace_hint_unique(hint, k, 594 boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0), 595 boost::forward<A1>(a1), boost::forward<A2>(a2))); 596 } 597 598 // try_emplace(const_iterator hint, key&&, Args&&...) 599 600 template <typename A0> 601 iterator try_emplace( 602 const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(A0) a0) 603 { 604 return table_.try_emplace_hint_unique( 605 hint, boost::move(k), boost::unordered::detail::create_emplace_args( 606 boost::forward<A0>(a0))); 607 } 608 609 template <typename A0, typename A1> 610 iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, 611 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1) 612 { 613 return table_.try_emplace_hint_unique(hint, boost::move(k), 614 boost::unordered::detail::create_emplace_args( 615 boost::forward<A0>(a0), boost::forward<A1>(a1))); 616 } 617 618 template <typename A0, typename A1, typename A2> 619 iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, 620 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 621 { 622 return table_.try_emplace_hint_unique(hint, boost::move(k), 623 boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0), 624 boost::forward<A1>(a1), boost::forward<A2>(a2))); 625 } 626 627 #define BOOST_UNORDERED_TRY_EMPLACE(z, n, _) \ 628 \ 629 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 630 std::pair<iterator, bool> try_emplace( \ 631 key_type const& k, BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \ 632 { \ 633 return table_.try_emplace_unique( \ 634 k, boost::unordered::detail::create_emplace_args( \ 635 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \ 636 } \ 637 \ 638 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 639 std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, \ 640 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \ 641 { \ 642 return table_.try_emplace_unique(boost::move(k), \ 643 boost::unordered::detail::create_emplace_args( \ 644 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \ 645 } \ 646 \ 647 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 648 iterator try_emplace(const_iterator hint, key_type const& k, \ 649 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \ 650 { \ 651 return table_.try_emplace_hint_unique( \ 652 hint, k, boost::unordered::detail::create_emplace_args( \ 653 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \ 654 } \ 655 \ 656 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 657 iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, \ 658 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \ 659 { \ 660 return table_.try_emplace_hint_unique(hint, boost::move(k), \ 661 boost::unordered::detail::create_emplace_args( \ 662 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \ 663 } 664 665 BOOST_UNORDERED_TRY_EMPLACE(1, 4, _) 666 BOOST_UNORDERED_TRY_EMPLACE(1, 5, _) 667 BOOST_UNORDERED_TRY_EMPLACE(1, 6, _) 668 BOOST_UNORDERED_TRY_EMPLACE(1, 7, _) 669 BOOST_UNORDERED_TRY_EMPLACE(1, 8, _) 670 BOOST_UNORDERED_TRY_EMPLACE(1, 9, _) 671 BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT), 672 BOOST_UNORDERED_TRY_EMPLACE, _) 673 674 #undef BOOST_UNORDERED_TRY_EMPLACE 675 676 #endif 677 678 template <class M> insert_or_assign(key_type const & k,BOOST_FWD_REF (M)obj)679 std::pair<iterator, bool> insert_or_assign( 680 key_type const& k, BOOST_FWD_REF(M) obj) 681 { 682 return table_.insert_or_assign_unique(k, boost::forward<M>(obj)); 683 } 684 685 template <class M> insert_or_assign(BOOST_RV_REF (key_type)k,BOOST_FWD_REF (M)obj)686 std::pair<iterator, bool> insert_or_assign( 687 BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj) 688 { 689 return table_.insert_or_assign_unique( 690 boost::move(k), boost::forward<M>(obj)); 691 } 692 693 template <class M> insert_or_assign(const_iterator,key_type const & k,BOOST_FWD_REF (M)obj)694 iterator insert_or_assign( 695 const_iterator, key_type const& k, BOOST_FWD_REF(M) obj) 696 { 697 return table_.insert_or_assign_unique(k, boost::forward<M>(obj)).first; 698 } 699 700 template <class M> insert_or_assign(const_iterator,BOOST_RV_REF (key_type)k,BOOST_FWD_REF (M)obj)701 iterator insert_or_assign( 702 const_iterator, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj) 703 { 704 return table_ 705 .insert_or_assign_unique(boost::move(k), boost::forward<M>(obj)) 706 .first; 707 } 708 709 iterator erase(iterator); 710 iterator erase(const_iterator); 711 size_type erase(const key_type&); 712 iterator erase(const_iterator, const_iterator); 713 BOOST_UNORDERED_DEPRECATED("Use erase instead") quick_erase(const_iterator it)714 void quick_erase(const_iterator it) { erase(it); } 715 BOOST_UNORDERED_DEPRECATED("Use erase instead") erase_return_void(const_iterator it)716 void erase_return_void(const_iterator it) { erase(it); } 717 718 void swap(unordered_map&) 719 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 720 boost::is_nothrow_swappable<H>::value&& 721 boost::is_nothrow_swappable<P>::value); clear()722 void clear() BOOST_NOEXCEPT { table_.clear_impl(); } 723 724 template <typename H2, typename P2> 725 void merge(boost::unordered_map<K, T, H2, P2, A>& source); 726 727 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 728 template <typename H2, typename P2> 729 void merge(boost::unordered_map<K, T, H2, P2, A>&& source); 730 #endif 731 732 template <typename H2, typename P2> 733 void merge(boost::unordered_multimap<K, T, H2, P2, A>& source); 734 735 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 736 template <typename H2, typename P2> 737 void merge(boost::unordered_multimap<K, T, H2, P2, A>&& source); 738 #endif 739 740 // observers 741 742 hasher hash_function() const; 743 key_equal key_eq() const; 744 745 // lookup 746 747 iterator find(const key_type&); 748 const_iterator find(const key_type&) const; 749 750 template <class CompatibleKey, class CompatibleHash, 751 class CompatiblePredicate> 752 iterator find(CompatibleKey const&, CompatibleHash const&, 753 CompatiblePredicate const&); 754 755 template <class CompatibleKey, class CompatibleHash, 756 class CompatiblePredicate> 757 const_iterator find(CompatibleKey const&, CompatibleHash const&, 758 CompatiblePredicate const&) const; 759 760 size_type count(const key_type&) const; 761 762 std::pair<iterator, iterator> equal_range(const key_type&); 763 std::pair<const_iterator, const_iterator> equal_range( 764 const key_type&) const; 765 766 mapped_type& operator[](const key_type&); 767 mapped_type& operator[](BOOST_RV_REF(key_type)); 768 mapped_type& at(const key_type&); 769 mapped_type const& at(const key_type&) const; 770 771 // bucket interface 772 bucket_count() const773 size_type bucket_count() const BOOST_NOEXCEPT 774 { 775 return table_.bucket_count_; 776 } 777 max_bucket_count() const778 size_type max_bucket_count() const BOOST_NOEXCEPT 779 { 780 return table_.max_bucket_count(); 781 } 782 783 size_type bucket_size(size_type) const; 784 bucket(const key_type & k) const785 size_type bucket(const key_type& k) const 786 { 787 return table_.hash_to_bucket(table_.hash(k)); 788 } 789 begin(size_type n)790 local_iterator begin(size_type n) 791 { 792 return local_iterator(table_.begin(n), n, table_.bucket_count_); 793 } 794 begin(size_type n) const795 const_local_iterator begin(size_type n) const 796 { 797 return const_local_iterator(table_.begin(n), n, table_.bucket_count_); 798 } 799 end(size_type)800 local_iterator end(size_type) { return local_iterator(); } 801 end(size_type) const802 const_local_iterator end(size_type) const 803 { 804 return const_local_iterator(); 805 } 806 cbegin(size_type n) const807 const_local_iterator cbegin(size_type n) const 808 { 809 return const_local_iterator(table_.begin(n), n, table_.bucket_count_); 810 } 811 cend(size_type) const812 const_local_iterator cend(size_type) const 813 { 814 return const_local_iterator(); 815 } 816 817 // hash policy 818 819 float load_factor() const BOOST_NOEXCEPT; max_load_factor() const820 float max_load_factor() const BOOST_NOEXCEPT { return table_.mlf_; } 821 void max_load_factor(float) BOOST_NOEXCEPT; 822 void rehash(size_type); 823 void reserve(size_type); 824 825 #if !BOOST_WORKAROUND(BOOST_BORLANDC, < 0x0582) 826 friend bool operator== 827 <K, T, H, P, A>(unordered_map const&, unordered_map const&); 828 friend bool operator!= 829 <K, T, H, P, A>(unordered_map const&, unordered_map const&); 830 #endif 831 }; // class template unordered_map 832 833 #if BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES 834 835 namespace detail { 836 template <typename T> 837 using iter_key_t = 838 typename std::iterator_traits<T>::value_type::first_type; 839 template <typename T> 840 using iter_val_t = 841 typename std::iterator_traits<T>::value_type::second_type; 842 template <typename T> 843 using iter_to_alloc_t = 844 typename std::pair<iter_key_t<T> const, iter_val_t<T> >; 845 } 846 847 template <class InputIterator, 848 class Hash = 849 boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >, 850 class Pred = 851 std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >, 852 class Allocator = std::allocator< 853 boost::unordered::detail::iter_to_alloc_t<InputIterator> > > 854 unordered_map(InputIterator, InputIterator, 855 std::size_t = boost::unordered::detail::default_bucket_count, 856 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 857 ->unordered_map<boost::unordered::detail::iter_key_t<InputIterator>, 858 boost::unordered::detail::iter_val_t<InputIterator>, Hash, Pred, 859 Allocator>; 860 861 template <class Key, class T, class Hash = boost::hash<Key>, 862 class Pred = std::equal_to<Key>, 863 class Allocator = std::allocator<std::pair<const Key, T> > > 864 unordered_map(std::initializer_list<std::pair<const Key, T> >, 865 std::size_t = boost::unordered::detail::default_bucket_count, 866 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 867 ->unordered_map<Key, T, Hash, Pred, Allocator>; 868 869 template <class InputIterator, class Allocator> 870 unordered_map(InputIterator, InputIterator, std::size_t, Allocator) 871 ->unordered_map<boost::unordered::detail::iter_key_t<InputIterator>, 872 boost::unordered::detail::iter_val_t<InputIterator>, 873 boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >, 874 std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >, 875 Allocator>; 876 877 template <class InputIterator, class Allocator> 878 unordered_map(InputIterator, InputIterator, Allocator) 879 ->unordered_map<boost::unordered::detail::iter_key_t<InputIterator>, 880 boost::unordered::detail::iter_val_t<InputIterator>, 881 boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >, 882 std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >, 883 Allocator>; 884 885 template <class InputIterator, class Hash, class Allocator> 886 unordered_map(InputIterator, InputIterator, std::size_t, Hash, Allocator) 887 ->unordered_map<boost::unordered::detail::iter_key_t<InputIterator>, 888 boost::unordered::detail::iter_val_t<InputIterator>, Hash, 889 std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >, 890 Allocator>; 891 892 template <class Key, class T, typename Allocator> 893 unordered_map( 894 std::initializer_list<std::pair<const Key, T> >, std::size_t, Allocator) 895 ->unordered_map<Key, T, boost::hash<Key>, std::equal_to<Key>, Allocator>; 896 897 template <class Key, class T, typename Allocator> 898 unordered_map(std::initializer_list<std::pair<const Key, T> >, Allocator) 899 ->unordered_map<Key, T, boost::hash<Key>, std::equal_to<Key>, Allocator>; 900 901 template <class Key, class T, class Hash, class Allocator> 902 unordered_map(std::initializer_list<std::pair<const Key, T> >, std::size_t, 903 Hash, Allocator) 904 ->unordered_map<Key, T, Hash, std::equal_to<Key>, Allocator>; 905 906 #endif 907 908 template <class K, class T, class H, class P, class A> 909 class unordered_multimap 910 { 911 #if defined(BOOST_UNORDERED_USE_MOVE) 912 BOOST_COPYABLE_AND_MOVABLE(unordered_multimap) 913 #endif 914 template <typename, typename, typename, typename, typename> 915 friend class unordered_map; 916 917 public: 918 typedef K key_type; 919 typedef T mapped_type; 920 typedef std::pair<const K, T> value_type; 921 typedef H hasher; 922 typedef P key_equal; 923 typedef A allocator_type; 924 925 private: 926 typedef boost::unordered::detail::map<A, K, T, H, P> types; 927 typedef typename types::value_allocator_traits value_allocator_traits; 928 typedef typename types::table table; 929 typedef typename table::node_pointer node_pointer; 930 typedef typename table::link_pointer link_pointer; 931 932 public: 933 typedef typename value_allocator_traits::pointer pointer; 934 typedef typename value_allocator_traits::const_pointer const_pointer; 935 936 typedef value_type& reference; 937 typedef value_type const& const_reference; 938 939 typedef std::size_t size_type; 940 typedef std::ptrdiff_t difference_type; 941 942 typedef typename table::iterator iterator; 943 typedef typename table::c_iterator const_iterator; 944 typedef typename table::l_iterator local_iterator; 945 typedef typename table::cl_iterator const_local_iterator; 946 typedef typename types::node_type node_type; 947 948 private: 949 table table_; 950 951 public: 952 // constructors 953 954 unordered_multimap(); 955 956 explicit unordered_multimap(size_type, const hasher& = hasher(), 957 const key_equal& = key_equal(), 958 const allocator_type& = allocator_type()); 959 960 template <class InputIt> 961 unordered_multimap(InputIt, InputIt, 962 size_type = boost::unordered::detail::default_bucket_count, 963 const hasher& = hasher(), const key_equal& = key_equal(), 964 const allocator_type& = allocator_type()); 965 966 unordered_multimap(unordered_multimap const&); 967 968 #if defined(BOOST_UNORDERED_USE_MOVE) || \ 969 !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 970 unordered_multimap(BOOST_RV_REF(unordered_multimap) other) BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)971 BOOST_NOEXCEPT_IF(table::nothrow_move_constructible) 972 : table_(other.table_, boost::unordered::detail::move_tag()) 973 { 974 // The move is done in table_ 975 } 976 #endif 977 978 explicit unordered_multimap(allocator_type const&); 979 980 unordered_multimap(unordered_multimap const&, allocator_type const&); 981 982 unordered_multimap( 983 BOOST_RV_REF(unordered_multimap), allocator_type const&); 984 985 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 986 unordered_multimap(std::initializer_list<value_type>, 987 size_type = boost::unordered::detail::default_bucket_count, 988 const hasher& = hasher(), const key_equal& l = key_equal(), 989 const allocator_type& = allocator_type()); 990 #endif 991 992 explicit unordered_multimap(size_type, const allocator_type&); 993 994 explicit unordered_multimap( 995 size_type, const hasher&, const allocator_type&); 996 997 template <class InputIt> 998 unordered_multimap(InputIt, InputIt, size_type, const allocator_type&); 999 1000 template <class InputIt> 1001 unordered_multimap( 1002 InputIt, InputIt, size_type, const hasher&, const allocator_type&); 1003 1004 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1005 unordered_multimap( 1006 std::initializer_list<value_type>, size_type, const allocator_type&); 1007 1008 unordered_multimap(std::initializer_list<value_type>, size_type, 1009 const hasher&, const allocator_type&); 1010 #endif 1011 1012 // Destructor 1013 1014 ~unordered_multimap() BOOST_NOEXCEPT; 1015 1016 // Assign 1017 1018 #if defined(BOOST_UNORDERED_USE_MOVE) operator =(BOOST_COPY_ASSIGN_REF (unordered_multimap)x)1019 unordered_multimap& operator=(BOOST_COPY_ASSIGN_REF(unordered_multimap) x) 1020 { 1021 table_.assign(x.table_, boost::unordered::detail::false_type()); 1022 return *this; 1023 } 1024 operator =(BOOST_RV_REF (unordered_multimap)x)1025 unordered_multimap& operator=(BOOST_RV_REF(unordered_multimap) x) 1026 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 1027 boost::is_nothrow_move_assignable<H>::value&& 1028 boost::is_nothrow_move_assignable<P>::value) 1029 { 1030 table_.move_assign(x.table_, boost::unordered::detail::false_type()); 1031 return *this; 1032 } 1033 #else operator =(unordered_multimap const & x)1034 unordered_multimap& operator=(unordered_multimap const& x) 1035 { 1036 table_.assign(x.table_, boost::unordered::detail::false_type()); 1037 return *this; 1038 } 1039 1040 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) operator =(unordered_multimap && x)1041 unordered_multimap& operator=(unordered_multimap&& x) 1042 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 1043 boost::is_nothrow_move_assignable<H>::value&& 1044 boost::is_nothrow_move_assignable<P>::value) 1045 { 1046 table_.move_assign(x.table_, boost::unordered::detail::false_type()); 1047 return *this; 1048 } 1049 #endif 1050 #endif 1051 1052 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1053 unordered_multimap& operator=(std::initializer_list<value_type>); 1054 #endif 1055 get_allocator() const1056 allocator_type get_allocator() const BOOST_NOEXCEPT 1057 { 1058 return table_.node_alloc(); 1059 } 1060 1061 // iterators 1062 begin()1063 iterator begin() BOOST_NOEXCEPT { return iterator(table_.begin()); } 1064 begin() const1065 const_iterator begin() const BOOST_NOEXCEPT 1066 { 1067 return const_iterator(table_.begin()); 1068 } 1069 end()1070 iterator end() BOOST_NOEXCEPT { return iterator(); } 1071 end() const1072 const_iterator end() const BOOST_NOEXCEPT { return const_iterator(); } 1073 cbegin() const1074 const_iterator cbegin() const BOOST_NOEXCEPT 1075 { 1076 return const_iterator(table_.begin()); 1077 } 1078 cend() const1079 const_iterator cend() const BOOST_NOEXCEPT { return const_iterator(); } 1080 1081 // size and capacity 1082 empty() const1083 bool empty() const BOOST_NOEXCEPT { return table_.size_ == 0; } 1084 size() const1085 size_type size() const BOOST_NOEXCEPT { return table_.size_; } 1086 1087 size_type max_size() const BOOST_NOEXCEPT; 1088 1089 // emplace 1090 1091 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1092 emplace(BOOST_FWD_REF (Args)...args)1093 template <class... Args> iterator emplace(BOOST_FWD_REF(Args)... args) 1094 { 1095 return iterator(table_.emplace_equiv( 1096 boost::unordered::detail::func::construct_node_from_args( 1097 table_.node_alloc(), boost::forward<Args>(args)...))); 1098 } 1099 1100 #else 1101 1102 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1 1103 1104 // 0 argument emplace requires special treatment in case 1105 // the container is instantiated with a value type that 1106 // doesn't have a default constructor. 1107 emplace(boost::unordered::detail::empty_emplace=boost::unordered::detail::empty_emplace (),value_type v=value_type ())1108 iterator emplace(boost::unordered::detail::empty_emplace = 1109 boost::unordered::detail::empty_emplace(), 1110 value_type v = value_type()) 1111 { 1112 return this->emplace(boost::move(v)); 1113 } 1114 1115 #endif 1116 emplace(BOOST_FWD_REF (A0)a0)1117 template <typename A0> iterator emplace(BOOST_FWD_REF(A0) a0) 1118 { 1119 return iterator(table_.emplace_equiv( 1120 boost::unordered::detail::func::construct_node_from_args( 1121 table_.node_alloc(), boost::unordered::detail::create_emplace_args( 1122 boost::forward<A0>(a0))))); 1123 } 1124 1125 template <typename A0, typename A1> emplace(BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1)1126 iterator emplace(BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1) 1127 { 1128 return iterator(table_.emplace_equiv( 1129 boost::unordered::detail::func::construct_node_from_args( 1130 table_.node_alloc(), 1131 boost::unordered::detail::create_emplace_args( 1132 boost::forward<A0>(a0), boost::forward<A1>(a1))))); 1133 } 1134 1135 template <typename A0, typename A1, typename A2> emplace(BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1,BOOST_FWD_REF (A2)a2)1136 iterator emplace( 1137 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 1138 { 1139 return iterator(table_.emplace_equiv( 1140 boost::unordered::detail::func::construct_node_from_args( 1141 table_.node_alloc(), 1142 boost::unordered::detail::create_emplace_args( 1143 boost::forward<A0>(a0), boost::forward<A1>(a1), 1144 boost::forward<A2>(a2))))); 1145 } 1146 1147 #endif 1148 1149 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1150 1151 template <class... Args> emplace_hint(const_iterator hint,BOOST_FWD_REF (Args)...args)1152 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args) 1153 { 1154 return iterator(table_.emplace_hint_equiv( 1155 hint, boost::unordered::detail::func::construct_node_from_args( 1156 table_.node_alloc(), boost::forward<Args>(args)...))); 1157 } 1158 1159 #else 1160 1161 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1 1162 emplace_hint(const_iterator hint,boost::unordered::detail::empty_emplace=boost::unordered::detail::empty_emplace (),value_type v=value_type ())1163 iterator emplace_hint(const_iterator hint, 1164 boost::unordered::detail::empty_emplace = 1165 boost::unordered::detail::empty_emplace(), 1166 value_type v = value_type()) 1167 { 1168 return this->emplace_hint(hint, boost::move(v)); 1169 } 1170 1171 #endif 1172 1173 template <typename A0> emplace_hint(const_iterator hint,BOOST_FWD_REF (A0)a0)1174 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0) 1175 { 1176 return iterator(table_.emplace_hint_equiv(hint, 1177 boost::unordered::detail::func::construct_node_from_args( 1178 table_.node_alloc(), boost::unordered::detail::create_emplace_args( 1179 boost::forward<A0>(a0))))); 1180 } 1181 1182 template <typename A0, typename A1> emplace_hint(const_iterator hint,BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1)1183 iterator emplace_hint( 1184 const_iterator hint, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1) 1185 { 1186 return iterator(table_.emplace_hint_equiv( 1187 hint, boost::unordered::detail::func::construct_node_from_args( 1188 table_.node_alloc(), 1189 boost::unordered::detail::create_emplace_args( 1190 boost::forward<A0>(a0), boost::forward<A1>(a1))))); 1191 } 1192 1193 template <typename A0, typename A1, typename A2> emplace_hint(const_iterator hint,BOOST_FWD_REF (A0)a0,BOOST_FWD_REF (A1)a1,BOOST_FWD_REF (A2)a2)1194 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0, 1195 BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 1196 { 1197 return iterator(table_.emplace_hint_equiv( 1198 hint, boost::unordered::detail::func::construct_node_from_args( 1199 table_.node_alloc(), 1200 boost::unordered::detail::create_emplace_args( 1201 boost::forward<A0>(a0), boost::forward<A1>(a1), 1202 boost::forward<A2>(a2))))); 1203 } 1204 1205 #endif 1206 1207 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1208 1209 #define BOOST_UNORDERED_EMPLACE(z, n, _) \ 1210 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 1211 iterator emplace(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \ 1212 { \ 1213 return iterator(table_.emplace_equiv( \ 1214 boost::unordered::detail::func::construct_node_from_args( \ 1215 table_.node_alloc(), \ 1216 boost::unordered::detail::create_emplace_args( \ 1217 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))))); \ 1218 } \ 1219 \ 1220 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 1221 iterator emplace_hint( \ 1222 const_iterator hint, BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \ 1223 { \ 1224 return iterator(table_.emplace_hint_equiv( \ 1225 hint, boost::unordered::detail::func::construct_node_from_args( \ 1226 table_.node_alloc(), \ 1227 boost::unordered::detail::create_emplace_args( \ 1228 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))))); \ 1229 } 1230 1231 BOOST_UNORDERED_EMPLACE(1, 4, _) 1232 BOOST_UNORDERED_EMPLACE(1, 5, _) 1233 BOOST_UNORDERED_EMPLACE(1, 6, _) 1234 BOOST_UNORDERED_EMPLACE(1, 7, _) 1235 BOOST_UNORDERED_EMPLACE(1, 8, _) 1236 BOOST_UNORDERED_EMPLACE(1, 9, _) BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT)1237 BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT), 1238 BOOST_UNORDERED_EMPLACE, _) 1239 1240 #undef BOOST_UNORDERED_EMPLACE 1241 1242 #endif 1243 1244 iterator insert(value_type const& x) { return this->emplace(x); } 1245 insert(BOOST_RV_REF (value_type)x)1246 iterator insert(BOOST_RV_REF(value_type) x) 1247 { 1248 return this->emplace(boost::move(x)); 1249 } 1250 1251 template <class P2> insert(BOOST_RV_REF (P2)obj,typename boost::enable_if_c<boost::is_constructible<value_type,BOOST_RV_REF (P2)>::value,void * >::type=0)1252 iterator insert(BOOST_RV_REF(P2) obj, 1253 typename boost::enable_if_c< 1254 boost::is_constructible<value_type, BOOST_RV_REF(P2)>::value, 1255 void*>::type = 0) 1256 { 1257 return this->emplace(boost::forward<P2>(obj)); 1258 } 1259 insert(const_iterator hint,value_type const & x)1260 iterator insert(const_iterator hint, value_type const& x) 1261 { 1262 return this->emplace_hint(hint, x); 1263 } 1264 insert(const_iterator hint,BOOST_RV_REF (value_type)x)1265 iterator insert(const_iterator hint, BOOST_RV_REF(value_type) x) 1266 { 1267 return this->emplace_hint(hint, boost::move(x)); 1268 } 1269 1270 template <class P2> insert(const_iterator hint,BOOST_RV_REF (P2)obj,typename boost::enable_if_c<boost::is_constructible<value_type,BOOST_RV_REF (P2)>::value,void * >::type=0)1271 iterator insert(const_iterator hint, BOOST_RV_REF(P2) obj, 1272 typename boost::enable_if_c< 1273 boost::is_constructible<value_type, BOOST_RV_REF(P2)>::value, 1274 void*>::type = 0) 1275 { 1276 return this->emplace_hint(hint, boost::forward<P2>(obj)); 1277 } 1278 1279 template <class InputIt> void insert(InputIt, InputIt); 1280 1281 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1282 void insert(std::initializer_list<value_type>); 1283 #endif 1284 1285 // extract 1286 extract(const_iterator position)1287 node_type extract(const_iterator position) 1288 { 1289 return node_type( 1290 table_.extract_by_iterator_equiv(position), table_.node_alloc()); 1291 } 1292 extract(const key_type & k)1293 node_type extract(const key_type& k) 1294 { 1295 return node_type(table_.extract_by_key(k), table_.node_alloc()); 1296 } 1297 insert(BOOST_RV_REF (node_type)np)1298 iterator insert(BOOST_RV_REF(node_type) np) 1299 { 1300 return table_.move_insert_node_type_equiv(np); 1301 } 1302 insert(const_iterator hint,BOOST_RV_REF (node_type)np)1303 iterator insert(const_iterator hint, BOOST_RV_REF(node_type) np) 1304 { 1305 return table_.move_insert_node_type_with_hint_equiv(hint, np); 1306 } 1307 1308 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || \ 1309 (BOOST_COMP_GNUC && BOOST_COMP_GNUC < BOOST_VERSION_NUMBER(4, 6, 0)) 1310 private: 1311 // Note: Use r-value node_type to insert. 1312 iterator insert(node_type&); 1313 iterator insert(const_iterator, node_type& np); 1314 1315 public: 1316 #endif 1317 1318 iterator erase(iterator); 1319 iterator erase(const_iterator); 1320 size_type erase(const key_type&); 1321 iterator erase(const_iterator, const_iterator); 1322 BOOST_UNORDERED_DEPRECATED("Use erase instead") quick_erase(const_iterator it)1323 void quick_erase(const_iterator it) { erase(it); } 1324 BOOST_UNORDERED_DEPRECATED("Use erase instead") erase_return_void(const_iterator it)1325 void erase_return_void(const_iterator it) { erase(it); } 1326 1327 void swap(unordered_multimap&) 1328 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 1329 boost::is_nothrow_swappable<H>::value&& 1330 boost::is_nothrow_swappable<P>::value); clear()1331 void clear() BOOST_NOEXCEPT { table_.clear_impl(); } 1332 1333 template <typename H2, typename P2> 1334 void merge(boost::unordered_multimap<K, T, H2, P2, A>& source); 1335 1336 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 1337 template <typename H2, typename P2> 1338 void merge(boost::unordered_multimap<K, T, H2, P2, A>&& source); 1339 #endif 1340 1341 template <typename H2, typename P2> 1342 void merge(boost::unordered_map<K, T, H2, P2, A>& source); 1343 1344 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 1345 template <typename H2, typename P2> 1346 void merge(boost::unordered_map<K, T, H2, P2, A>&& source); 1347 #endif 1348 1349 // observers 1350 1351 hasher hash_function() const; 1352 key_equal key_eq() const; 1353 1354 // lookup 1355 1356 iterator find(const key_type&); 1357 const_iterator find(const key_type&) const; 1358 1359 template <class CompatibleKey, class CompatibleHash, 1360 class CompatiblePredicate> 1361 iterator find(CompatibleKey const&, CompatibleHash const&, 1362 CompatiblePredicate const&); 1363 1364 template <class CompatibleKey, class CompatibleHash, 1365 class CompatiblePredicate> 1366 const_iterator find(CompatibleKey const&, CompatibleHash const&, 1367 CompatiblePredicate const&) const; 1368 1369 size_type count(const key_type&) const; 1370 1371 std::pair<iterator, iterator> equal_range(const key_type&); 1372 std::pair<const_iterator, const_iterator> equal_range( 1373 const key_type&) const; 1374 1375 // bucket interface 1376 bucket_count() const1377 size_type bucket_count() const BOOST_NOEXCEPT 1378 { 1379 return table_.bucket_count_; 1380 } 1381 max_bucket_count() const1382 size_type max_bucket_count() const BOOST_NOEXCEPT 1383 { 1384 return table_.max_bucket_count(); 1385 } 1386 1387 size_type bucket_size(size_type) const; 1388 bucket(const key_type & k) const1389 size_type bucket(const key_type& k) const 1390 { 1391 return table_.hash_to_bucket(table_.hash(k)); 1392 } 1393 begin(size_type n)1394 local_iterator begin(size_type n) 1395 { 1396 return local_iterator(table_.begin(n), n, table_.bucket_count_); 1397 } 1398 begin(size_type n) const1399 const_local_iterator begin(size_type n) const 1400 { 1401 return const_local_iterator(table_.begin(n), n, table_.bucket_count_); 1402 } 1403 end(size_type)1404 local_iterator end(size_type) { return local_iterator(); } 1405 end(size_type) const1406 const_local_iterator end(size_type) const 1407 { 1408 return const_local_iterator(); 1409 } 1410 cbegin(size_type n) const1411 const_local_iterator cbegin(size_type n) const 1412 { 1413 return const_local_iterator(table_.begin(n), n, table_.bucket_count_); 1414 } 1415 cend(size_type) const1416 const_local_iterator cend(size_type) const 1417 { 1418 return const_local_iterator(); 1419 } 1420 1421 // hash policy 1422 1423 float load_factor() const BOOST_NOEXCEPT; max_load_factor() const1424 float max_load_factor() const BOOST_NOEXCEPT { return table_.mlf_; } 1425 void max_load_factor(float) BOOST_NOEXCEPT; 1426 void rehash(size_type); 1427 void reserve(size_type); 1428 1429 #if !BOOST_WORKAROUND(BOOST_BORLANDC, < 0x0582) 1430 friend bool operator== 1431 <K, T, H, P, A>(unordered_multimap const&, unordered_multimap const&); 1432 friend bool operator!= 1433 <K, T, H, P, A>(unordered_multimap const&, unordered_multimap const&); 1434 #endif 1435 }; // class template unordered_multimap 1436 1437 #if BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES 1438 1439 template <class InputIterator, 1440 class Hash = 1441 boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >, 1442 class Pred = 1443 std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >, 1444 class Allocator = std::allocator< 1445 boost::unordered::detail::iter_to_alloc_t<InputIterator> > > 1446 unordered_multimap(InputIterator, InputIterator, 1447 std::size_t = boost::unordered::detail::default_bucket_count, 1448 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 1449 ->unordered_multimap<boost::unordered::detail::iter_key_t<InputIterator>, 1450 boost::unordered::detail::iter_val_t<InputIterator>, Hash, Pred, 1451 Allocator>; 1452 1453 template <class Key, class T, class Hash = boost::hash<Key>, 1454 class Pred = std::equal_to<Key>, 1455 class Allocator = std::allocator<std::pair<const Key, T> > > 1456 unordered_multimap(std::initializer_list<std::pair<const Key, T> >, 1457 std::size_t = boost::unordered::detail::default_bucket_count, 1458 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 1459 ->unordered_multimap<Key, T, Hash, Pred, Allocator>; 1460 1461 template <class InputIterator, class Allocator> 1462 unordered_multimap(InputIterator, InputIterator, std::size_t, Allocator) 1463 ->unordered_multimap<boost::unordered::detail::iter_key_t<InputIterator>, 1464 boost::unordered::detail::iter_val_t<InputIterator>, 1465 boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >, 1466 std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >, 1467 Allocator>; 1468 1469 template <class InputIterator, class Allocator> 1470 unordered_multimap(InputIterator, InputIterator, Allocator) 1471 ->unordered_multimap<boost::unordered::detail::iter_key_t<InputIterator>, 1472 boost::unordered::detail::iter_val_t<InputIterator>, 1473 boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >, 1474 std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >, 1475 Allocator>; 1476 1477 template <class InputIterator, class Hash, class Allocator> 1478 unordered_multimap( 1479 InputIterator, InputIterator, std::size_t, Hash, Allocator) 1480 ->unordered_multimap<boost::unordered::detail::iter_key_t<InputIterator>, 1481 boost::unordered::detail::iter_val_t<InputIterator>, Hash, 1482 std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >, 1483 Allocator>; 1484 1485 template <class Key, class T, typename Allocator> 1486 unordered_multimap( 1487 std::initializer_list<std::pair<const Key, T> >, std::size_t, Allocator) 1488 ->unordered_multimap<Key, T, boost::hash<Key>, std::equal_to<Key>, 1489 Allocator>; 1490 1491 template <class Key, class T, typename Allocator> 1492 unordered_multimap( 1493 std::initializer_list<std::pair<const Key, T> >, Allocator) 1494 ->unordered_multimap<Key, T, boost::hash<Key>, std::equal_to<Key>, 1495 Allocator>; 1496 1497 template <class Key, class T, class Hash, class Allocator> 1498 unordered_multimap(std::initializer_list<std::pair<const Key, T> >, 1499 std::size_t, Hash, Allocator) 1500 ->unordered_multimap<Key, T, Hash, std::equal_to<Key>, Allocator>; 1501 1502 #endif 1503 1504 //////////////////////////////////////////////////////////////////////////// 1505 1506 template <class K, class T, class H, class P, class A> unordered_map()1507 unordered_map<K, T, H, P, A>::unordered_map() 1508 : table_(boost::unordered::detail::default_bucket_count, hasher(), 1509 key_equal(), allocator_type()) 1510 { 1511 } 1512 1513 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)1514 unordered_map<K, T, H, P, A>::unordered_map(size_type n, const hasher& hf, 1515 const key_equal& eql, const allocator_type& a) 1516 : table_(n, hf, eql, a) 1517 { 1518 } 1519 1520 template <class K, class T, class H, class P, class A> 1521 template <class InputIt> unordered_map(InputIt f,InputIt l,size_type n,const hasher & hf,const key_equal & eql,const allocator_type & a)1522 unordered_map<K, T, H, P, A>::unordered_map(InputIt f, InputIt l, 1523 size_type n, const hasher& hf, const key_equal& eql, 1524 const allocator_type& a) 1525 : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a) 1526 { 1527 this->insert(f, l); 1528 } 1529 1530 template <class K, class T, class H, class P, class A> unordered_map(unordered_map const & other)1531 unordered_map<K, T, H, P, A>::unordered_map(unordered_map const& other) 1532 : table_(other.table_, 1533 unordered_map::value_allocator_traits:: 1534 select_on_container_copy_construction(other.get_allocator())) 1535 { 1536 if (other.table_.size_) { 1537 table_.copy_buckets( 1538 other.table_, boost::unordered::detail::true_type()); 1539 } 1540 } 1541 1542 template <class K, class T, class H, class P, class A> unordered_map(allocator_type const & a)1543 unordered_map<K, T, H, P, A>::unordered_map(allocator_type const& a) 1544 : table_(boost::unordered::detail::default_bucket_count, hasher(), 1545 key_equal(), a) 1546 { 1547 } 1548 1549 template <class K, class T, class H, class P, class A> unordered_map(unordered_map const & other,allocator_type const & a)1550 unordered_map<K, T, H, P, A>::unordered_map( 1551 unordered_map const& other, allocator_type const& a) 1552 : table_(other.table_, a) 1553 { 1554 if (other.table_.size_) { 1555 table_.copy_buckets( 1556 other.table_, boost::unordered::detail::true_type()); 1557 } 1558 } 1559 1560 template <class K, class T, class H, class P, class A> unordered_map(BOOST_RV_REF (unordered_map)other,allocator_type const & a)1561 unordered_map<K, T, H, P, A>::unordered_map( 1562 BOOST_RV_REF(unordered_map) other, allocator_type const& a) 1563 : table_(other.table_, a, boost::unordered::detail::move_tag()) 1564 { 1565 table_.move_construct_buckets(other.table_); 1566 } 1567 1568 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1569 1570 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)1571 unordered_map<K, T, H, P, A>::unordered_map( 1572 std::initializer_list<value_type> list, size_type n, const hasher& hf, 1573 const key_equal& eql, const allocator_type& a) 1574 : table_( 1575 boost::unordered::detail::initial_size(list.begin(), list.end(), n), 1576 hf, eql, a) 1577 { 1578 this->insert(list.begin(), list.end()); 1579 } 1580 1581 #endif 1582 1583 template <class K, class T, class H, class P, class A> unordered_map(size_type n,const allocator_type & a)1584 unordered_map<K, T, H, P, A>::unordered_map( 1585 size_type n, const allocator_type& a) 1586 : table_(n, hasher(), key_equal(), a) 1587 { 1588 } 1589 1590 template <class K, class T, class H, class P, class A> unordered_map(size_type n,const hasher & hf,const allocator_type & a)1591 unordered_map<K, T, H, P, A>::unordered_map( 1592 size_type n, const hasher& hf, const allocator_type& a) 1593 : table_(n, hf, key_equal(), a) 1594 { 1595 } 1596 1597 template <class K, class T, class H, class P, class A> 1598 template <class InputIt> unordered_map(InputIt f,InputIt l,size_type n,const allocator_type & a)1599 unordered_map<K, T, H, P, A>::unordered_map( 1600 InputIt f, InputIt l, size_type n, const allocator_type& a) 1601 : table_(boost::unordered::detail::initial_size(f, l, n), hasher(), 1602 key_equal(), a) 1603 { 1604 this->insert(f, l); 1605 } 1606 1607 template <class K, class T, class H, class P, class A> 1608 template <class InputIt> unordered_map(InputIt f,InputIt l,size_type n,const hasher & hf,const allocator_type & a)1609 unordered_map<K, T, H, P, A>::unordered_map(InputIt f, InputIt l, 1610 size_type n, const hasher& hf, const allocator_type& a) 1611 : table_( 1612 boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a) 1613 { 1614 this->insert(f, l); 1615 } 1616 1617 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1618 1619 template <class K, class T, class H, class P, class A> unordered_map(std::initializer_list<value_type> list,size_type n,const allocator_type & a)1620 unordered_map<K, T, H, P, A>::unordered_map( 1621 std::initializer_list<value_type> list, size_type n, 1622 const allocator_type& a) 1623 : table_( 1624 boost::unordered::detail::initial_size(list.begin(), list.end(), n), 1625 hasher(), key_equal(), a) 1626 { 1627 this->insert(list.begin(), list.end()); 1628 } 1629 1630 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 allocator_type & a)1631 unordered_map<K, T, H, P, A>::unordered_map( 1632 std::initializer_list<value_type> list, size_type n, const hasher& hf, 1633 const allocator_type& a) 1634 : table_( 1635 boost::unordered::detail::initial_size(list.begin(), list.end(), n), 1636 hf, key_equal(), a) 1637 { 1638 this->insert(list.begin(), list.end()); 1639 } 1640 1641 #endif 1642 1643 template <class K, class T, class H, class P, class A> ~unordered_map()1644 unordered_map<K, T, H, P, A>::~unordered_map() BOOST_NOEXCEPT 1645 { 1646 } 1647 1648 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1649 1650 template <class K, class T, class H, class P, class A> operator =(std::initializer_list<value_type> list)1651 unordered_map<K, T, H, P, A>& unordered_map<K, T, H, P, A>::operator=( 1652 std::initializer_list<value_type> list) 1653 { 1654 this->clear(); 1655 this->insert(list.begin(), list.end()); 1656 return *this; 1657 } 1658 1659 #endif 1660 1661 // size and capacity 1662 1663 template <class K, class T, class H, class P, class A> max_size() const1664 std::size_t unordered_map<K, T, H, P, A>::max_size() const BOOST_NOEXCEPT 1665 { 1666 using namespace std; 1667 1668 // size <= mlf_ * count 1669 return boost::unordered::detail::double_to_size( 1670 ceil(static_cast<double>(table_.mlf_) * 1671 static_cast<double>(table_.max_bucket_count()))) - 1672 1; 1673 } 1674 1675 // modifiers 1676 1677 template <class K, class T, class H, class P, class A> 1678 template <class InputIt> insert(InputIt first,InputIt last)1679 void unordered_map<K, T, H, P, A>::insert(InputIt first, InputIt last) 1680 { 1681 if (first != last) { 1682 table_.insert_range_unique( 1683 table::extractor::extract(*first), first, last); 1684 } 1685 } 1686 1687 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 1688 template <class K, class T, class H, class P, class A> insert(std::initializer_list<value_type> list)1689 void unordered_map<K, T, H, P, A>::insert( 1690 std::initializer_list<value_type> list) 1691 { 1692 this->insert(list.begin(), list.end()); 1693 } 1694 #endif 1695 1696 template <class K, class T, class H, class P, class A> 1697 typename unordered_map<K, T, H, P, A>::iterator erase(iterator position)1698 unordered_map<K, T, H, P, A>::erase(iterator position) 1699 { 1700 node_pointer node = table::get_node(position); 1701 BOOST_ASSERT(node); 1702 node_pointer next = table::next_node(node); 1703 table_.erase_nodes_unique(node, next); 1704 return iterator(next); 1705 } 1706 1707 template <class K, class T, class H, class P, class A> 1708 typename unordered_map<K, T, H, P, A>::iterator erase(const_iterator position)1709 unordered_map<K, T, H, P, A>::erase(const_iterator position) 1710 { 1711 node_pointer node = table::get_node(position); 1712 BOOST_ASSERT(node); 1713 node_pointer next = table::next_node(node); 1714 table_.erase_nodes_unique(node, next); 1715 return iterator(next); 1716 } 1717 1718 template <class K, class T, class H, class P, class A> 1719 typename unordered_map<K, T, H, P, A>::size_type erase(const key_type & k)1720 unordered_map<K, T, H, P, A>::erase(const key_type& k) 1721 { 1722 return table_.erase_key_unique(k); 1723 } 1724 1725 template <class K, class T, class H, class P, class A> 1726 typename unordered_map<K, T, H, P, A>::iterator erase(const_iterator first,const_iterator last)1727 unordered_map<K, T, H, P, A>::erase( 1728 const_iterator first, const_iterator last) 1729 { 1730 node_pointer last_node = table::get_node(last); 1731 if (first == last) 1732 return iterator(last_node); 1733 table_.erase_nodes_unique(table::get_node(first), last_node); 1734 return iterator(last_node); 1735 } 1736 1737 template <class K, class T, class H, class P, class A> swap(unordered_map & other)1738 void unordered_map<K, T, H, P, A>::swap(unordered_map& other) 1739 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 1740 boost::is_nothrow_swappable<H>::value&& 1741 boost::is_nothrow_swappable<P>::value) 1742 { 1743 table_.swap(other.table_); 1744 } 1745 1746 template <class K, class T, class H, class P, class A> 1747 template <typename H2, typename P2> merge(boost::unordered_map<K,T,H2,P2,A> & source)1748 void unordered_map<K, T, H, P, A>::merge( 1749 boost::unordered_map<K, T, H2, P2, A>& source) 1750 { 1751 table_.merge_unique(source.table_); 1752 } 1753 1754 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 1755 template <class K, class T, class H, class P, class A> 1756 template <typename H2, typename P2> merge(boost::unordered_map<K,T,H2,P2,A> && source)1757 void unordered_map<K, T, H, P, A>::merge( 1758 boost::unordered_map<K, T, H2, P2, A>&& source) 1759 { 1760 table_.merge_unique(source.table_); 1761 } 1762 #endif 1763 1764 template <class K, class T, class H, class P, class A> 1765 template <typename H2, typename P2> merge(boost::unordered_multimap<K,T,H2,P2,A> & source)1766 void unordered_map<K, T, H, P, A>::merge( 1767 boost::unordered_multimap<K, T, H2, P2, A>& source) 1768 { 1769 table_.merge_unique(source.table_); 1770 } 1771 1772 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 1773 template <class K, class T, class H, class P, class A> 1774 template <typename H2, typename P2> merge(boost::unordered_multimap<K,T,H2,P2,A> && source)1775 void unordered_map<K, T, H, P, A>::merge( 1776 boost::unordered_multimap<K, T, H2, P2, A>&& source) 1777 { 1778 table_.merge_unique(source.table_); 1779 } 1780 #endif 1781 1782 // observers 1783 1784 template <class K, class T, class H, class P, class A> 1785 typename unordered_map<K, T, H, P, A>::hasher hash_function() const1786 unordered_map<K, T, H, P, A>::hash_function() const 1787 { 1788 return table_.hash_function(); 1789 } 1790 1791 template <class K, class T, class H, class P, class A> 1792 typename unordered_map<K, T, H, P, A>::key_equal key_eq() const1793 unordered_map<K, T, H, P, A>::key_eq() const 1794 { 1795 return table_.key_eq(); 1796 } 1797 1798 // lookup 1799 1800 template <class K, class T, class H, class P, class A> 1801 typename unordered_map<K, T, H, P, A>::iterator find(const key_type & k)1802 unordered_map<K, T, H, P, A>::find(const key_type& k) 1803 { 1804 return iterator(table_.find_node(k)); 1805 } 1806 1807 template <class K, class T, class H, class P, class A> 1808 typename unordered_map<K, T, H, P, A>::const_iterator find(const key_type & k) const1809 unordered_map<K, T, H, P, A>::find(const key_type& k) const 1810 { 1811 return const_iterator(table_.find_node(k)); 1812 } 1813 1814 template <class K, class T, class H, class P, class A> 1815 template <class CompatibleKey, class CompatibleHash, 1816 class CompatiblePredicate> 1817 typename unordered_map<K, T, H, P, A>::iterator find(CompatibleKey const & k,CompatibleHash const & hash,CompatiblePredicate const & eq)1818 unordered_map<K, T, H, P, A>::find(CompatibleKey const& k, 1819 CompatibleHash const& hash, CompatiblePredicate const& eq) 1820 { 1821 return iterator( 1822 table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq)); 1823 } 1824 1825 template <class K, class T, class H, class P, class A> 1826 template <class CompatibleKey, class CompatibleHash, 1827 class CompatiblePredicate> 1828 typename unordered_map<K, T, H, P, A>::const_iterator find(CompatibleKey const & k,CompatibleHash const & hash,CompatiblePredicate const & eq) const1829 unordered_map<K, T, H, P, A>::find(CompatibleKey const& k, 1830 CompatibleHash const& hash, CompatiblePredicate const& eq) const 1831 { 1832 return const_iterator( 1833 table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq)); 1834 } 1835 1836 template <class K, class T, class H, class P, class A> 1837 typename unordered_map<K, T, H, P, A>::size_type count(const key_type & k) const1838 unordered_map<K, T, H, P, A>::count(const key_type& k) const 1839 { 1840 return table_.find_node(k) ? 1 : 0; 1841 } 1842 1843 template <class K, class T, class H, class P, class A> 1844 std::pair<typename unordered_map<K, T, H, P, A>::iterator, 1845 typename unordered_map<K, T, H, P, A>::iterator> equal_range(const key_type & k)1846 unordered_map<K, T, H, P, A>::equal_range(const key_type& k) 1847 { 1848 node_pointer n = table_.find_node(k); 1849 return std::make_pair(iterator(n), iterator(n ? table::next_node(n) : n)); 1850 } 1851 1852 template <class K, class T, class H, class P, class A> 1853 std::pair<typename unordered_map<K, T, H, P, A>::const_iterator, 1854 typename unordered_map<K, T, H, P, A>::const_iterator> equal_range(const key_type & k) const1855 unordered_map<K, T, H, P, A>::equal_range(const key_type& k) const 1856 { 1857 node_pointer n = table_.find_node(k); 1858 return std::make_pair( 1859 const_iterator(n), const_iterator(n ? table::next_node(n) : n)); 1860 } 1861 1862 template <class K, class T, class H, class P, class A> 1863 typename unordered_map<K, T, H, P, A>::mapped_type& operator [](const key_type & k)1864 unordered_map<K, T, H, P, A>::operator[](const key_type& k) 1865 { 1866 return table_.try_emplace_unique(k).first->second; 1867 } 1868 1869 template <class K, class T, class H, class P, class A> 1870 typename unordered_map<K, T, H, P, A>::mapped_type& operator [](BOOST_RV_REF (key_type)k)1871 unordered_map<K, T, H, P, A>::operator[](BOOST_RV_REF(key_type) k) 1872 { 1873 return table_.try_emplace_unique(boost::move(k)).first->second; 1874 } 1875 1876 template <class K, class T, class H, class P, class A> 1877 typename unordered_map<K, T, H, P, A>::mapped_type& at(const key_type & k)1878 unordered_map<K, T, H, P, A>::at(const key_type& k) 1879 { 1880 if (table_.size_) { 1881 node_pointer n = table_.find_node(k); 1882 if (n) 1883 return n->value().second; 1884 } 1885 1886 boost::throw_exception( 1887 std::out_of_range("Unable to find key in unordered_map.")); 1888 } 1889 1890 template <class K, class T, class H, class P, class A> 1891 typename unordered_map<K, T, H, P, A>::mapped_type const& at(const key_type & k) const1892 unordered_map<K, T, H, P, A>::at(const key_type& k) const 1893 { 1894 if (table_.size_) { 1895 node_pointer n = table_.find_node(k); 1896 if (n) 1897 return n->value().second; 1898 } 1899 1900 boost::throw_exception( 1901 std::out_of_range("Unable to find key in unordered_map.")); 1902 } 1903 1904 template <class K, class T, class H, class P, class A> 1905 typename unordered_map<K, T, H, P, A>::size_type bucket_size(size_type n) const1906 unordered_map<K, T, H, P, A>::bucket_size(size_type n) const 1907 { 1908 return table_.bucket_size(n); 1909 } 1910 1911 // hash policy 1912 1913 template <class K, class T, class H, class P, class A> load_factor() const1914 float unordered_map<K, T, H, P, A>::load_factor() const BOOST_NOEXCEPT 1915 { 1916 BOOST_ASSERT(table_.bucket_count_ != 0); 1917 return static_cast<float>(table_.size_) / 1918 static_cast<float>(table_.bucket_count_); 1919 } 1920 1921 template <class K, class T, class H, class P, class A> max_load_factor(float m)1922 void unordered_map<K, T, H, P, A>::max_load_factor(float m) BOOST_NOEXCEPT 1923 { 1924 table_.max_load_factor(m); 1925 } 1926 1927 template <class K, class T, class H, class P, class A> rehash(size_type n)1928 void unordered_map<K, T, H, P, A>::rehash(size_type n) 1929 { 1930 table_.rehash(n); 1931 } 1932 1933 template <class K, class T, class H, class P, class A> reserve(size_type n)1934 void unordered_map<K, T, H, P, A>::reserve(size_type n) 1935 { 1936 table_.rehash(static_cast<std::size_t>( 1937 std::ceil(static_cast<double>(n) / table_.mlf_))); 1938 } 1939 1940 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)1941 inline bool operator==(unordered_map<K, T, H, P, A> const& m1, 1942 unordered_map<K, T, H, P, A> const& m2) 1943 { 1944 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613)) 1945 struct dummy 1946 { 1947 unordered_map<K, T, H, P, A> x; 1948 }; 1949 #endif 1950 return m1.table_.equals_unique(m2.table_); 1951 } 1952 1953 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)1954 inline bool operator!=(unordered_map<K, T, H, P, A> const& m1, 1955 unordered_map<K, T, H, P, A> const& m2) 1956 { 1957 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613)) 1958 struct dummy 1959 { 1960 unordered_map<K, T, H, P, A> x; 1961 }; 1962 #endif 1963 return !m1.table_.equals_unique(m2.table_); 1964 } 1965 1966 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)1967 inline void swap( 1968 unordered_map<K, T, H, P, A>& m1, unordered_map<K, T, H, P, A>& m2) 1969 BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT_EXPR(m1.swap(m2))) 1970 { 1971 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613)) 1972 struct dummy 1973 { 1974 unordered_map<K, T, H, P, A> x; 1975 }; 1976 #endif 1977 m1.swap(m2); 1978 } 1979 1980 //////////////////////////////////////////////////////////////////////////// 1981 1982 template <class K, class T, class H, class P, class A> unordered_multimap()1983 unordered_multimap<K, T, H, P, A>::unordered_multimap() 1984 : table_(boost::unordered::detail::default_bucket_count, hasher(), 1985 key_equal(), allocator_type()) 1986 { 1987 } 1988 1989 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)1990 unordered_multimap<K, T, H, P, A>::unordered_multimap(size_type n, 1991 const hasher& hf, const key_equal& eql, const allocator_type& a) 1992 : table_(n, hf, eql, a) 1993 { 1994 } 1995 1996 template <class K, class T, class H, class P, class A> 1997 template <class InputIt> unordered_multimap(InputIt f,InputIt l,size_type n,const hasher & hf,const key_equal & eql,const allocator_type & a)1998 unordered_multimap<K, T, H, P, A>::unordered_multimap(InputIt f, InputIt l, 1999 size_type n, const hasher& hf, const key_equal& eql, 2000 const allocator_type& a) 2001 : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a) 2002 { 2003 this->insert(f, l); 2004 } 2005 2006 template <class K, class T, class H, class P, class A> unordered_multimap(unordered_multimap const & other)2007 unordered_multimap<K, T, H, P, A>::unordered_multimap( 2008 unordered_multimap const& other) 2009 : table_(other.table_, 2010 unordered_multimap::value_allocator_traits:: 2011 select_on_container_copy_construction(other.get_allocator())) 2012 { 2013 if (other.table_.size_) { 2014 table_.copy_buckets( 2015 other.table_, boost::unordered::detail::false_type()); 2016 } 2017 } 2018 2019 template <class K, class T, class H, class P, class A> unordered_multimap(allocator_type const & a)2020 unordered_multimap<K, T, H, P, A>::unordered_multimap( 2021 allocator_type const& a) 2022 : table_(boost::unordered::detail::default_bucket_count, hasher(), 2023 key_equal(), a) 2024 { 2025 } 2026 2027 template <class K, class T, class H, class P, class A> unordered_multimap(unordered_multimap const & other,allocator_type const & a)2028 unordered_multimap<K, T, H, P, A>::unordered_multimap( 2029 unordered_multimap const& other, allocator_type const& a) 2030 : table_(other.table_, a) 2031 { 2032 if (other.table_.size_) { 2033 table_.copy_buckets( 2034 other.table_, boost::unordered::detail::false_type()); 2035 } 2036 } 2037 2038 template <class K, class T, class H, class P, class A> unordered_multimap(BOOST_RV_REF (unordered_multimap)other,allocator_type const & a)2039 unordered_multimap<K, T, H, P, A>::unordered_multimap( 2040 BOOST_RV_REF(unordered_multimap) other, allocator_type const& a) 2041 : table_(other.table_, a, boost::unordered::detail::move_tag()) 2042 { 2043 table_.move_construct_buckets(other.table_); 2044 } 2045 2046 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 2047 2048 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)2049 unordered_multimap<K, T, H, P, A>::unordered_multimap( 2050 std::initializer_list<value_type> list, size_type n, const hasher& hf, 2051 const key_equal& eql, const allocator_type& a) 2052 : table_( 2053 boost::unordered::detail::initial_size(list.begin(), list.end(), n), 2054 hf, eql, a) 2055 { 2056 this->insert(list.begin(), list.end()); 2057 } 2058 2059 #endif 2060 2061 template <class K, class T, class H, class P, class A> unordered_multimap(size_type n,const allocator_type & a)2062 unordered_multimap<K, T, H, P, A>::unordered_multimap( 2063 size_type n, const allocator_type& a) 2064 : table_(n, hasher(), key_equal(), a) 2065 { 2066 } 2067 2068 template <class K, class T, class H, class P, class A> unordered_multimap(size_type n,const hasher & hf,const allocator_type & a)2069 unordered_multimap<K, T, H, P, A>::unordered_multimap( 2070 size_type n, const hasher& hf, const allocator_type& a) 2071 : table_(n, hf, key_equal(), a) 2072 { 2073 } 2074 2075 template <class K, class T, class H, class P, class A> 2076 template <class InputIt> unordered_multimap(InputIt f,InputIt l,size_type n,const allocator_type & a)2077 unordered_multimap<K, T, H, P, A>::unordered_multimap( 2078 InputIt f, InputIt l, size_type n, const allocator_type& a) 2079 : table_(boost::unordered::detail::initial_size(f, l, n), hasher(), 2080 key_equal(), a) 2081 { 2082 this->insert(f, l); 2083 } 2084 2085 template <class K, class T, class H, class P, class A> 2086 template <class InputIt> unordered_multimap(InputIt f,InputIt l,size_type n,const hasher & hf,const allocator_type & a)2087 unordered_multimap<K, T, H, P, A>::unordered_multimap(InputIt f, InputIt l, 2088 size_type n, const hasher& hf, const allocator_type& a) 2089 : table_( 2090 boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a) 2091 { 2092 this->insert(f, l); 2093 } 2094 2095 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 2096 2097 template <class K, class T, class H, class P, class A> unordered_multimap(std::initializer_list<value_type> list,size_type n,const allocator_type & a)2098 unordered_multimap<K, T, H, P, A>::unordered_multimap( 2099 std::initializer_list<value_type> list, size_type n, 2100 const allocator_type& a) 2101 : table_( 2102 boost::unordered::detail::initial_size(list.begin(), list.end(), n), 2103 hasher(), key_equal(), a) 2104 { 2105 this->insert(list.begin(), list.end()); 2106 } 2107 2108 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 allocator_type & a)2109 unordered_multimap<K, T, H, P, A>::unordered_multimap( 2110 std::initializer_list<value_type> list, size_type n, const hasher& hf, 2111 const allocator_type& a) 2112 : table_( 2113 boost::unordered::detail::initial_size(list.begin(), list.end(), n), 2114 hf, key_equal(), a) 2115 { 2116 this->insert(list.begin(), list.end()); 2117 } 2118 2119 #endif 2120 2121 template <class K, class T, class H, class P, class A> ~unordered_multimap()2122 unordered_multimap<K, T, H, P, A>::~unordered_multimap() BOOST_NOEXCEPT 2123 { 2124 } 2125 2126 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 2127 2128 template <class K, class T, class H, class P, class A> 2129 unordered_multimap<K, T, H, P, A>& unordered_multimap<K, T, H, P, A>:: operator =(std::initializer_list<value_type> list)2130 operator=(std::initializer_list<value_type> list) 2131 { 2132 this->clear(); 2133 this->insert(list.begin(), list.end()); 2134 return *this; 2135 } 2136 2137 #endif 2138 2139 // size and capacity 2140 2141 template <class K, class T, class H, class P, class A> 2142 std::size_t max_size() const2143 unordered_multimap<K, T, H, P, A>::max_size() const BOOST_NOEXCEPT 2144 { 2145 using namespace std; 2146 2147 // size <= mlf_ * count 2148 return boost::unordered::detail::double_to_size( 2149 ceil(static_cast<double>(table_.mlf_) * 2150 static_cast<double>(table_.max_bucket_count()))) - 2151 1; 2152 } 2153 2154 // modifiers 2155 2156 template <class K, class T, class H, class P, class A> 2157 template <class InputIt> insert(InputIt first,InputIt last)2158 void unordered_multimap<K, T, H, P, A>::insert(InputIt first, InputIt last) 2159 { 2160 table_.insert_range_equiv(first, last); 2161 } 2162 2163 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) 2164 template <class K, class T, class H, class P, class A> insert(std::initializer_list<value_type> list)2165 void unordered_multimap<K, T, H, P, A>::insert( 2166 std::initializer_list<value_type> list) 2167 { 2168 this->insert(list.begin(), list.end()); 2169 } 2170 #endif 2171 2172 template <class K, class T, class H, class P, class A> 2173 typename unordered_multimap<K, T, H, P, A>::iterator erase(iterator position)2174 unordered_multimap<K, T, H, P, A>::erase(iterator position) 2175 { 2176 node_pointer node = table::get_node(position); 2177 BOOST_ASSERT(node); 2178 node_pointer next = table::next_node(node); 2179 table_.erase_nodes_equiv(node, next); 2180 return iterator(next); 2181 } 2182 2183 template <class K, class T, class H, class P, class A> 2184 typename unordered_multimap<K, T, H, P, A>::iterator erase(const_iterator position)2185 unordered_multimap<K, T, H, P, A>::erase(const_iterator position) 2186 { 2187 node_pointer node = table::get_node(position); 2188 BOOST_ASSERT(node); 2189 node_pointer next = table::next_node(node); 2190 table_.erase_nodes_equiv(node, next); 2191 return iterator(next); 2192 } 2193 2194 template <class K, class T, class H, class P, class A> 2195 typename unordered_multimap<K, T, H, P, A>::size_type erase(const key_type & k)2196 unordered_multimap<K, T, H, P, A>::erase(const key_type& k) 2197 { 2198 return table_.erase_key_equiv(k); 2199 } 2200 2201 template <class K, class T, class H, class P, class A> 2202 typename unordered_multimap<K, T, H, P, A>::iterator erase(const_iterator first,const_iterator last)2203 unordered_multimap<K, T, H, P, A>::erase( 2204 const_iterator first, const_iterator last) 2205 { 2206 node_pointer last_node = table::get_node(last); 2207 if (first == last) 2208 return iterator(last_node); 2209 table_.erase_nodes_equiv(table::get_node(first), last_node); 2210 return iterator(last_node); 2211 } 2212 2213 template <class K, class T, class H, class P, class A> swap(unordered_multimap & other)2214 void unordered_multimap<K, T, H, P, A>::swap(unordered_multimap& other) 2215 BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&& 2216 boost::is_nothrow_swappable<H>::value&& 2217 boost::is_nothrow_swappable<P>::value) 2218 { 2219 table_.swap(other.table_); 2220 } 2221 2222 // observers 2223 2224 template <class K, class T, class H, class P, class A> 2225 typename unordered_multimap<K, T, H, P, A>::hasher hash_function() const2226 unordered_multimap<K, T, H, P, A>::hash_function() const 2227 { 2228 return table_.hash_function(); 2229 } 2230 2231 template <class K, class T, class H, class P, class A> 2232 typename unordered_multimap<K, T, H, P, A>::key_equal key_eq() const2233 unordered_multimap<K, T, H, P, A>::key_eq() const 2234 { 2235 return table_.key_eq(); 2236 } 2237 2238 template <class K, class T, class H, class P, class A> 2239 template <typename H2, typename P2> merge(boost::unordered_multimap<K,T,H2,P2,A> & source)2240 void unordered_multimap<K, T, H, P, A>::merge( 2241 boost::unordered_multimap<K, T, H2, P2, A>& source) 2242 { 2243 while (!source.empty()) { 2244 insert(source.extract(source.begin())); 2245 } 2246 } 2247 2248 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 2249 template <class K, class T, class H, class P, class A> 2250 template <typename H2, typename P2> merge(boost::unordered_multimap<K,T,H2,P2,A> && source)2251 void unordered_multimap<K, T, H, P, A>::merge( 2252 boost::unordered_multimap<K, T, H2, P2, A>&& source) 2253 { 2254 while (!source.empty()) { 2255 insert(source.extract(source.begin())); 2256 } 2257 } 2258 #endif 2259 2260 template <class K, class T, class H, class P, class A> 2261 template <typename H2, typename P2> merge(boost::unordered_map<K,T,H2,P2,A> & source)2262 void unordered_multimap<K, T, H, P, A>::merge( 2263 boost::unordered_map<K, T, H2, P2, A>& source) 2264 { 2265 while (!source.empty()) { 2266 insert(source.extract(source.begin())); 2267 } 2268 } 2269 2270 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 2271 template <class K, class T, class H, class P, class A> 2272 template <typename H2, typename P2> merge(boost::unordered_map<K,T,H2,P2,A> && source)2273 void unordered_multimap<K, T, H, P, A>::merge( 2274 boost::unordered_map<K, T, H2, P2, A>&& source) 2275 { 2276 while (!source.empty()) { 2277 insert(source.extract(source.begin())); 2278 } 2279 } 2280 #endif 2281 2282 // lookup 2283 2284 template <class K, class T, class H, class P, class A> 2285 typename unordered_multimap<K, T, H, P, A>::iterator find(const key_type & k)2286 unordered_multimap<K, T, H, P, A>::find(const key_type& k) 2287 { 2288 return iterator(table_.find_node(k)); 2289 } 2290 2291 template <class K, class T, class H, class P, class A> 2292 typename unordered_multimap<K, T, H, P, A>::const_iterator find(const key_type & k) const2293 unordered_multimap<K, T, H, P, A>::find(const key_type& k) const 2294 { 2295 return const_iterator(table_.find_node(k)); 2296 } 2297 2298 template <class K, class T, class H, class P, class A> 2299 template <class CompatibleKey, class CompatibleHash, 2300 class CompatiblePredicate> 2301 typename unordered_multimap<K, T, H, P, A>::iterator find(CompatibleKey const & k,CompatibleHash const & hash,CompatiblePredicate const & eq)2302 unordered_multimap<K, T, H, P, A>::find(CompatibleKey const& k, 2303 CompatibleHash const& hash, CompatiblePredicate const& eq) 2304 { 2305 return iterator( 2306 table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq)); 2307 } 2308 2309 template <class K, class T, class H, class P, class A> 2310 template <class CompatibleKey, class CompatibleHash, 2311 class CompatiblePredicate> 2312 typename unordered_multimap<K, T, H, P, A>::const_iterator find(CompatibleKey const & k,CompatibleHash const & hash,CompatiblePredicate const & eq) const2313 unordered_multimap<K, T, H, P, A>::find(CompatibleKey const& k, 2314 CompatibleHash const& hash, CompatiblePredicate const& eq) const 2315 { 2316 return const_iterator( 2317 table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq)); 2318 } 2319 2320 template <class K, class T, class H, class P, class A> 2321 typename unordered_multimap<K, T, H, P, A>::size_type count(const key_type & k) const2322 unordered_multimap<K, T, H, P, A>::count(const key_type& k) const 2323 { 2324 node_pointer n = table_.find_node(k); 2325 return n ? table_.group_count(n) : 0; 2326 } 2327 2328 template <class K, class T, class H, class P, class A> 2329 std::pair<typename unordered_multimap<K, T, H, P, A>::iterator, 2330 typename unordered_multimap<K, T, H, P, A>::iterator> equal_range(const key_type & k)2331 unordered_multimap<K, T, H, P, A>::equal_range(const key_type& k) 2332 { 2333 node_pointer n = table_.find_node(k); 2334 return std::make_pair( 2335 iterator(n), iterator(n ? table_.next_group(n) : n)); 2336 } 2337 2338 template <class K, class T, class H, class P, class A> 2339 std::pair<typename unordered_multimap<K, T, H, P, A>::const_iterator, 2340 typename unordered_multimap<K, T, H, P, A>::const_iterator> equal_range(const key_type & k) const2341 unordered_multimap<K, T, H, P, A>::equal_range(const key_type& k) const 2342 { 2343 node_pointer n = table_.find_node(k); 2344 return std::make_pair( 2345 const_iterator(n), const_iterator(n ? table_.next_group(n) : n)); 2346 } 2347 2348 template <class K, class T, class H, class P, class A> 2349 typename unordered_multimap<K, T, H, P, A>::size_type bucket_size(size_type n) const2350 unordered_multimap<K, T, H, P, A>::bucket_size(size_type n) const 2351 { 2352 return table_.bucket_size(n); 2353 } 2354 2355 // hash policy 2356 2357 template <class K, class T, class H, class P, class A> load_factor() const2358 float unordered_multimap<K, T, H, P, A>::load_factor() const BOOST_NOEXCEPT 2359 { 2360 BOOST_ASSERT(table_.bucket_count_ != 0); 2361 return static_cast<float>(table_.size_) / 2362 static_cast<float>(table_.bucket_count_); 2363 } 2364 2365 template <class K, class T, class H, class P, class A> max_load_factor(float m)2366 void unordered_multimap<K, T, H, P, A>::max_load_factor( 2367 float m) BOOST_NOEXCEPT 2368 { 2369 table_.max_load_factor(m); 2370 } 2371 2372 template <class K, class T, class H, class P, class A> rehash(size_type n)2373 void unordered_multimap<K, T, H, P, A>::rehash(size_type n) 2374 { 2375 table_.rehash(n); 2376 } 2377 2378 template <class K, class T, class H, class P, class A> reserve(size_type n)2379 void unordered_multimap<K, T, H, P, A>::reserve(size_type n) 2380 { 2381 table_.rehash(static_cast<std::size_t>( 2382 std::ceil(static_cast<double>(n) / table_.mlf_))); 2383 } 2384 2385 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)2386 inline bool operator==(unordered_multimap<K, T, H, P, A> const& m1, 2387 unordered_multimap<K, T, H, P, A> const& m2) 2388 { 2389 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613)) 2390 struct dummy 2391 { 2392 unordered_multimap<K, T, H, P, A> x; 2393 }; 2394 #endif 2395 return m1.table_.equals_equiv(m2.table_); 2396 } 2397 2398 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)2399 inline bool operator!=(unordered_multimap<K, T, H, P, A> const& m1, 2400 unordered_multimap<K, T, H, P, A> const& m2) 2401 { 2402 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613)) 2403 struct dummy 2404 { 2405 unordered_multimap<K, T, H, P, A> x; 2406 }; 2407 #endif 2408 return !m1.table_.equals_equiv(m2.table_); 2409 } 2410 2411 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)2412 inline void swap(unordered_multimap<K, T, H, P, A>& m1, 2413 unordered_multimap<K, T, H, P, A>& m2) 2414 BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT_EXPR(m1.swap(m2))) 2415 { 2416 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613)) 2417 struct dummy 2418 { 2419 unordered_multimap<K, T, H, P, A> x; 2420 }; 2421 #endif 2422 m1.swap(m2); 2423 } 2424 2425 template <typename N, class K, class T, class A> class node_handle_map 2426 { 2427 BOOST_MOVABLE_BUT_NOT_COPYABLE(node_handle_map) 2428 2429 template <typename Types> friend struct ::boost::unordered::detail::table; 2430 template <class K2, class T2, class H2, class P2, class A2> 2431 friend class boost::unordered::unordered_map; 2432 template <class K2, class T2, class H2, class P2, class A2> 2433 friend class boost::unordered::unordered_multimap; 2434 2435 typedef typename boost::unordered::detail::rebind_wrap<A, 2436 std::pair<K const, T> >::type value_allocator; 2437 typedef boost::unordered::detail::allocator_traits<value_allocator> 2438 value_allocator_traits; 2439 typedef N node; 2440 typedef typename boost::unordered::detail::rebind_wrap<A, node>::type 2441 node_allocator; 2442 typedef boost::unordered::detail::allocator_traits<node_allocator> 2443 node_allocator_traits; 2444 typedef typename node_allocator_traits::pointer node_pointer; 2445 2446 public: 2447 typedef K key_type; 2448 typedef T mapped_type; 2449 typedef A allocator_type; 2450 2451 private: 2452 node_pointer ptr_; 2453 boost::unordered::detail::optional<value_allocator> alloc_; 2454 node_handle_map(node_pointer ptr,allocator_type const & a)2455 node_handle_map(node_pointer ptr, allocator_type const& a) 2456 : ptr_(ptr), alloc_(a) 2457 { 2458 } 2459 2460 public: node_handle_map()2461 BOOST_CONSTEXPR node_handle_map() BOOST_NOEXCEPT : ptr_(), alloc_() {} 2462 ~node_handle_map()2463 ~node_handle_map() 2464 { 2465 if (ptr_) { 2466 node_allocator node_alloc(*alloc_); 2467 boost::unordered::detail::node_tmp<node_allocator> tmp( 2468 ptr_, node_alloc); 2469 } 2470 } 2471 node_handle_map(BOOST_RV_REF (node_handle_map)n)2472 node_handle_map(BOOST_RV_REF(node_handle_map) n) BOOST_NOEXCEPT 2473 : ptr_(n.ptr_), 2474 alloc_(boost::move(n.alloc_)) 2475 { 2476 n.ptr_ = node_pointer(); 2477 } 2478 operator =(BOOST_RV_REF (node_handle_map)n)2479 node_handle_map& operator=(BOOST_RV_REF(node_handle_map) n) 2480 { 2481 BOOST_ASSERT(!alloc_.has_value() || 2482 value_allocator_traits:: 2483 propagate_on_container_move_assignment::value || 2484 (n.alloc_.has_value() && alloc_ == n.alloc_)); 2485 2486 if (ptr_) { 2487 node_allocator node_alloc(*alloc_); 2488 boost::unordered::detail::node_tmp<node_allocator> tmp( 2489 ptr_, node_alloc); 2490 ptr_ = node_pointer(); 2491 } 2492 2493 if (!alloc_.has_value() || 2494 value_allocator_traits::propagate_on_container_move_assignment:: 2495 value) { 2496 alloc_ = boost::move(n.alloc_); 2497 } 2498 ptr_ = n.ptr_; 2499 n.ptr_ = node_pointer(); 2500 2501 return *this; 2502 } 2503 key() const2504 key_type& key() const 2505 { 2506 return const_cast<key_type&>(ptr_->value().first); 2507 } 2508 mapped() const2509 mapped_type& mapped() const { return ptr_->value().second; } 2510 get_allocator() const2511 allocator_type get_allocator() const { return *alloc_; } 2512 2513 BOOST_EXPLICIT_OPERATOR_BOOL_NOEXCEPT() 2514 2515 bool operator!() const BOOST_NOEXCEPT { return ptr_ ? 0 : 1; } 2516 empty() const2517 bool empty() const BOOST_NOEXCEPT { return ptr_ ? 0 : 1; } 2518 swap(node_handle_map & n)2519 void swap(node_handle_map& n) BOOST_NOEXCEPT_IF( 2520 value_allocator_traits::propagate_on_container_swap::value || 2521 value_allocator_traits::is_always_equal::value) 2522 { 2523 BOOST_ASSERT( 2524 !alloc_.has_value() || !n.alloc_.has_value() || 2525 value_allocator_traits::propagate_on_container_swap::value || 2526 alloc_ == n.alloc_); 2527 if (value_allocator_traits::propagate_on_container_swap::value || 2528 !alloc_.has_value() || !n.alloc_.has_value()) { 2529 boost::swap(alloc_, n.alloc_); 2530 } 2531 boost::swap(ptr_, n.ptr_); 2532 } 2533 }; 2534 2535 template <class N, class K, class T, class A> swap(node_handle_map<N,K,T,A> & x,node_handle_map<N,K,T,A> & y)2536 void swap(node_handle_map<N, K, T, A>& x, node_handle_map<N, K, T, A>& y) 2537 BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT_EXPR(x.swap(y))) 2538 { 2539 x.swap(y); 2540 } 2541 2542 template <class N, class K, class T, class A> struct insert_return_type_map 2543 { 2544 private: 2545 BOOST_MOVABLE_BUT_NOT_COPYABLE(insert_return_type_map) 2546 2547 typedef typename boost::unordered::detail::rebind_wrap<A, 2548 std::pair<K const, T> >::type value_allocator; 2549 typedef N node_; 2550 2551 public: 2552 bool inserted; 2553 boost::unordered::iterator_detail::iterator<node_> position; 2554 boost::unordered::node_handle_map<N, K, T, A> node; 2555 insert_return_type_mapboost::unordered::insert_return_type_map2556 insert_return_type_map() : inserted(false), position(), node() {} 2557 insert_return_type_mapboost::unordered::insert_return_type_map2558 insert_return_type_map(BOOST_RV_REF(insert_return_type_map) 2559 x) BOOST_NOEXCEPT : inserted(x.inserted), 2560 position(x.position), 2561 node(boost::move(x.node)) 2562 { 2563 } 2564 operator =boost::unordered::insert_return_type_map2565 insert_return_type_map& operator=(BOOST_RV_REF(insert_return_type_map) x) 2566 { 2567 inserted = x.inserted; 2568 position = x.position; 2569 node = boost::move(x.node); 2570 return *this; 2571 } 2572 }; 2573 2574 template <class N, class K, class T, class A> swap(insert_return_type_map<N,K,T,A> & x,insert_return_type_map<N,K,T,A> & y)2575 void swap(insert_return_type_map<N, K, T, A>& x, 2576 insert_return_type_map<N, K, T, A>& y) 2577 { 2578 boost::swap(x.node, y.node); 2579 boost::swap(x.inserted, y.inserted); 2580 boost::swap(x.position, y.position); 2581 } 2582 } // namespace unordered 2583 } // namespace boost 2584 2585 #if defined(BOOST_MSVC) 2586 #pragma warning(pop) 2587 #endif 2588 2589 #endif // BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED 2590