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)
7 // See http://www.boost.org/libs/unordered for documentation
9 #ifndef BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED
10 #define BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED
12 #include <boost/config.hpp>
13 #if defined(BOOST_HAS_PRAGMA_ONCE)
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>
23 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
24 #include <initializer_list>
27 #if defined(BOOST_MSVC)
29 #if BOOST_MSVC >= 1400
30 #pragma warning(disable : 4396) // the inline specifier cannot be used when a
31 // friend declaration refers to a specialization
32 // of a function template
38 template <class K, class T, class H, class P, class A> class unordered_map
40 #if defined(BOOST_UNORDERED_USE_MOVE)
41 BOOST_COPYABLE_AND_MOVABLE(unordered_map)
43 template <typename, typename, typename, typename, typename>
44 friend class unordered_multimap;
48 typedef T mapped_type;
49 typedef std::pair<const K, T> value_type;
52 typedef A allocator_type;
55 typedef boost::unordered::detail::map<A, K, T, H, P> types;
56 typedef typename types::value_allocator_traits value_allocator_traits;
57 typedef typename types::table table;
58 typedef typename table::node_pointer node_pointer;
59 typedef typename table::link_pointer link_pointer;
62 typedef typename value_allocator_traits::pointer pointer;
63 typedef typename value_allocator_traits::const_pointer const_pointer;
65 typedef value_type& reference;
66 typedef value_type const& const_reference;
68 typedef std::size_t size_type;
69 typedef std::ptrdiff_t difference_type;
71 typedef typename table::iterator iterator;
72 typedef typename table::c_iterator const_iterator;
73 typedef typename table::l_iterator local_iterator;
74 typedef typename table::cl_iterator const_local_iterator;
75 typedef typename types::node_type node_type;
76 typedef typename types::insert_return_type insert_return_type;
86 explicit unordered_map(size_type, const hasher& = hasher(),
87 const key_equal& = key_equal(),
88 const allocator_type& = allocator_type());
90 template <class InputIt>
91 unordered_map(InputIt, InputIt,
92 size_type = boost::unordered::detail::default_bucket_count,
93 const hasher& = hasher(), const key_equal& = key_equal(),
94 const allocator_type& = allocator_type());
96 unordered_map(unordered_map const&);
98 #if defined(BOOST_UNORDERED_USE_MOVE) || \
99 !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
100 unordered_map(BOOST_RV_REF(unordered_map) other)
101 BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
102 : table_(other.table_, boost::unordered::detail::move_tag())
104 // The move is done in table_
108 explicit unordered_map(allocator_type const&);
110 unordered_map(unordered_map const&, allocator_type const&);
112 unordered_map(BOOST_RV_REF(unordered_map), allocator_type const&);
114 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
115 unordered_map(std::initializer_list<value_type>,
116 size_type = boost::unordered::detail::default_bucket_count,
117 const hasher& = hasher(), const key_equal& l = key_equal(),
118 const allocator_type& = allocator_type());
121 explicit unordered_map(size_type, const allocator_type&);
123 explicit unordered_map(size_type, const hasher&, const allocator_type&);
125 template <class InputIt>
126 unordered_map(InputIt, InputIt, size_type, const allocator_type&);
128 template <class InputIt>
130 InputIt, InputIt, size_type, const hasher&, const allocator_type&);
132 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
134 std::initializer_list<value_type>, size_type, const allocator_type&);
136 unordered_map(std::initializer_list<value_type>, size_type, const hasher&,
137 const allocator_type&);
142 ~unordered_map() BOOST_NOEXCEPT;
146 #if defined(BOOST_UNORDERED_USE_MOVE)
147 unordered_map& operator=(BOOST_COPY_ASSIGN_REF(unordered_map) x)
149 table_.assign(x.table_, boost::unordered::detail::true_type());
153 unordered_map& operator=(BOOST_RV_REF(unordered_map) x)
154 // C++17 support: BOOST_NOEXCEPT_IF(
155 // value_allocator_traits::is_always_equal::value &&
156 // is_nothrow_move_assignable_v<H> &&
157 // is_nothrow_move_assignable_v<P>)
159 table_.move_assign(x.table_, boost::unordered::detail::true_type());
163 unordered_map& operator=(unordered_map const& x)
165 table_.assign(x.table_, boost::unordered::detail::true_type());
169 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
170 unordered_map& operator=(unordered_map&& x)
171 // C++17 support: BOOST_NOEXCEPT_IF(
172 // value_allocator_traits::is_always_equal::value &&
173 // is_nothrow_move_assignable_v<H> &&
174 // is_nothrow_move_assignable_v<P>)
176 table_.move_assign(x.table_, boost::unordered::detail::true_type());
182 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
183 unordered_map& operator=(std::initializer_list<value_type>);
186 allocator_type get_allocator() const BOOST_NOEXCEPT
188 return table_.node_alloc();
193 iterator begin() BOOST_NOEXCEPT { return iterator(table_.begin()); }
195 const_iterator begin() const BOOST_NOEXCEPT
197 return const_iterator(table_.begin());
200 iterator end() BOOST_NOEXCEPT { return iterator(); }
202 const_iterator end() const BOOST_NOEXCEPT { return const_iterator(); }
204 const_iterator cbegin() const BOOST_NOEXCEPT
206 return const_iterator(table_.begin());
209 const_iterator cend() const BOOST_NOEXCEPT { return const_iterator(); }
213 bool empty() const BOOST_NOEXCEPT { return table_.size_ == 0; }
215 size_type size() const BOOST_NOEXCEPT { return table_.size_; }
217 size_type max_size() const BOOST_NOEXCEPT;
221 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
223 template <class... Args>
224 std::pair<iterator, bool> emplace(BOOST_FWD_REF(Args)... args)
226 return table_.emplace_unique(
227 table::extractor::extract(boost::forward<Args>(args)...),
228 boost::forward<Args>(args)...);
233 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1
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.
239 std::pair<iterator, bool> emplace(
240 boost::unordered::detail::empty_emplace =
241 boost::unordered::detail::empty_emplace(),
242 value_type v = value_type())
244 return this->emplace(boost::move(v));
249 template <typename A0>
250 std::pair<iterator, bool> emplace(BOOST_FWD_REF(A0) a0)
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)));
258 template <typename A0, typename A1>
259 std::pair<iterator, bool> emplace(
260 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
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)));
269 template <typename A0, typename A1, typename A2>
270 std::pair<iterator, bool> emplace(
271 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
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)));
282 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
284 template <class... Args>
285 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
287 return table_.emplace_hint_unique(hint,
288 table::extractor::extract(boost::forward<Args>(args)...),
289 boost::forward<Args>(args)...);
294 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1
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())
301 return this->emplace_hint(hint, boost::move(v));
306 template <typename A0>
307 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0)
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)));
315 template <typename A0, typename A1>
316 iterator emplace_hint(
317 const_iterator hint, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
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)));
326 template <typename A0, typename A1, typename A2>
327 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0,
328 BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
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)));
339 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
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)) \
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))); \
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)) \
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))); \
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, _)
370 BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT),
371 BOOST_UNORDERED_EMPLACE, _)
373 #undef BOOST_UNORDERED_EMPLACE
377 std::pair<iterator, bool> insert(value_type const& x)
379 return this->emplace(x);
382 std::pair<iterator, bool> insert(BOOST_RV_REF(value_type) x)
384 return this->emplace(boost::move(x));
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,
393 return this->emplace(boost::forward<P2>(obj));
396 iterator insert(const_iterator hint, value_type const& x)
398 return this->emplace_hint(hint, x);
401 iterator insert(const_iterator hint, BOOST_RV_REF(value_type) x)
403 return this->emplace_hint(hint, boost::move(x));
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,
412 return this->emplace_hint(hint, boost::forward<P2>(obj));
415 template <class InputIt> void insert(InputIt, InputIt);
417 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
418 void insert(std::initializer_list<value_type>);
423 node_type extract(const_iterator position)
426 table_.extract_by_iterator_unique(position), table_.node_alloc());
429 node_type extract(const key_type& k)
431 return node_type(table_.extract_by_key(k), table_.node_alloc());
434 insert_return_type insert(BOOST_RV_REF(node_type) np)
436 insert_return_type result;
437 table_.move_insert_node_type_unique(np, result);
438 return boost::move(result);
441 iterator insert(const_iterator hint, BOOST_RV_REF(node_type) np)
443 return table_.move_insert_node_type_with_hint_unique(hint, np);
446 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || \
447 (BOOST_COMP_GNUC && BOOST_COMP_GNUC < BOOST_VERSION_NUMBER(4, 6, 0))
449 // Note: Use r-value node_type to insert.
450 insert_return_type insert(node_type&);
451 iterator insert(const_iterator, node_type& np);
456 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
458 template <class... Args>
459 std::pair<iterator, bool> try_emplace(
460 key_type const& k, BOOST_FWD_REF(Args)... args)
462 return table_.try_emplace_unique(k, boost::forward<Args>(args)...);
465 template <class... Args>
466 std::pair<iterator, bool> try_emplace(
467 BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
469 return table_.try_emplace_unique(
470 boost::move(k), boost::forward<Args>(args)...);
473 template <class... Args>
474 iterator try_emplace(
475 const_iterator hint, key_type const& k, BOOST_FWD_REF(Args)... args)
477 return table_.try_emplace_hint_unique(
478 hint, k, boost::forward<Args>(args)...);
481 template <class... Args>
482 iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k,
483 BOOST_FWD_REF(Args)... args)
485 return table_.try_emplace_hint_unique(
486 hint, boost::move(k), boost::forward<Args>(args)...);
491 // In order to make this a template, this handles both:
492 // try_emplace(key const&)
493 // try_emplace(key&&)
495 template <typename Key>
496 std::pair<iterator, bool> try_emplace(BOOST_FWD_REF(Key) k)
498 return table_.try_emplace_unique(boost::forward<Key>(k));
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&&)
505 template <typename Key>
506 iterator try_emplace(const_iterator hint, BOOST_FWD_REF(Key) k)
508 return table_.try_emplace_hint_unique(hint, boost::forward<Key>(k));
511 // try_emplace(key const&, Args&&...)
513 template <typename A0>
514 std::pair<iterator, bool> try_emplace(
515 key_type const& k, BOOST_FWD_REF(A0) a0)
517 return table_.try_emplace_unique(
518 k, boost::unordered::detail::create_emplace_args(
519 boost::forward<A0>(a0)));
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)
526 return table_.try_emplace_unique(
527 k, boost::unordered::detail::create_emplace_args(
528 boost::forward<A0>(a0), boost::forward<A1>(a1)));
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)
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)));
540 // try_emplace(key&&, Args&&...)
542 template <typename A0>
543 std::pair<iterator, bool> try_emplace(
544 BOOST_RV_REF(key_type) k, BOOST_FWD_REF(A0) a0)
546 return table_.try_emplace_unique(
547 boost::move(k), boost::unordered::detail::create_emplace_args(
548 boost::forward<A0>(a0)));
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)
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)));
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)
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)));
569 // try_emplace(const_iterator hint, key const&, Args&&...)
571 template <typename A0>
572 iterator try_emplace(
573 const_iterator hint, key_type const& k, BOOST_FWD_REF(A0) a0)
575 return table_.try_emplace_hint_unique(
576 hint, k, boost::unordered::detail::create_emplace_args(
577 boost::forward<A0>(a0)));
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)
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)));
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)
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)));
598 // try_emplace(const_iterator hint, key&&, Args&&...)
600 template <typename A0>
601 iterator try_emplace(
602 const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(A0) a0)
604 return table_.try_emplace_hint_unique(
605 hint, boost::move(k), boost::unordered::detail::create_emplace_args(
606 boost::forward<A0>(a0)));
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)
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)));
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)
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)));
627 #define BOOST_UNORDERED_TRY_EMPLACE(z, n, _) \
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)) \
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))); \
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)) \
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))); \
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)) \
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))); \
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)) \
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))); \
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, _)
674 #undef BOOST_UNORDERED_TRY_EMPLACE
679 std::pair<iterator, bool> insert_or_assign(
680 key_type const& k, BOOST_FWD_REF(M) obj)
682 return table_.insert_or_assign_unique(k, boost::forward<M>(obj));
686 std::pair<iterator, bool> insert_or_assign(
687 BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
689 return table_.insert_or_assign_unique(
690 boost::move(k), boost::forward<M>(obj));
694 iterator insert_or_assign(
695 const_iterator, key_type const& k, BOOST_FWD_REF(M) obj)
697 return table_.insert_or_assign_unique(k, boost::forward<M>(obj)).first;
701 iterator insert_or_assign(
702 const_iterator, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
705 .insert_or_assign_unique(boost::move(k), boost::forward<M>(obj))
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")
714 void quick_erase(const_iterator it) { erase(it); }
715 BOOST_UNORDERED_DEPRECATED("Use erase instead")
716 void erase_return_void(const_iterator it) { erase(it); }
718 void swap(unordered_map&);
719 // C++17 support: BOOST_NOEXCEPT_IF(
720 // value_allocator_traits::is_always_equal::value &&
721 // is_nothrow_move_assignable_v<H> &&
722 // is_nothrow_move_assignable_v<P>)
723 void clear() BOOST_NOEXCEPT { table_.clear_impl(); }
725 template <typename H2, typename P2>
726 void merge(boost::unordered_map<K, T, H2, P2, A>& source);
728 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
729 template <typename H2, typename P2>
730 void merge(boost::unordered_map<K, T, H2, P2, A>&& source);
733 template <typename H2, typename P2>
734 void merge(boost::unordered_multimap<K, T, H2, P2, A>& source);
736 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
737 template <typename H2, typename P2>
738 void merge(boost::unordered_multimap<K, T, H2, P2, A>&& source);
743 hasher hash_function() const;
744 key_equal key_eq() const;
748 iterator find(const key_type&);
749 const_iterator find(const key_type&) const;
751 template <class CompatibleKey, class CompatibleHash,
752 class CompatiblePredicate>
753 iterator find(CompatibleKey const&, CompatibleHash const&,
754 CompatiblePredicate const&);
756 template <class CompatibleKey, class CompatibleHash,
757 class CompatiblePredicate>
758 const_iterator find(CompatibleKey const&, CompatibleHash const&,
759 CompatiblePredicate const&) const;
761 size_type count(const key_type&) const;
763 std::pair<iterator, iterator> equal_range(const key_type&);
764 std::pair<const_iterator, const_iterator> equal_range(
765 const key_type&) const;
767 mapped_type& operator[](const key_type&);
768 mapped_type& operator[](BOOST_RV_REF(key_type));
769 mapped_type& at(const key_type&);
770 mapped_type const& at(const key_type&) const;
774 size_type bucket_count() const BOOST_NOEXCEPT
776 return table_.bucket_count_;
779 size_type max_bucket_count() const BOOST_NOEXCEPT
781 return table_.max_bucket_count();
784 size_type bucket_size(size_type) const;
786 size_type bucket(const key_type& k) const
788 return table_.hash_to_bucket(table_.hash(k));
791 local_iterator begin(size_type n)
793 return local_iterator(table_.begin(n), n, table_.bucket_count_);
796 const_local_iterator begin(size_type n) const
798 return const_local_iterator(table_.begin(n), n, table_.bucket_count_);
801 local_iterator end(size_type) { return local_iterator(); }
803 const_local_iterator end(size_type) const
805 return const_local_iterator();
808 const_local_iterator cbegin(size_type n) const
810 return const_local_iterator(table_.begin(n), n, table_.bucket_count_);
813 const_local_iterator cend(size_type) const
815 return const_local_iterator();
820 float load_factor() const BOOST_NOEXCEPT;
821 float max_load_factor() const BOOST_NOEXCEPT { return table_.mlf_; }
822 void max_load_factor(float) BOOST_NOEXCEPT;
823 void rehash(size_type);
824 void reserve(size_type);
826 #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
827 friend bool operator==
828 <K, T, H, P, A>(unordered_map const&, unordered_map const&);
829 friend bool operator!=
830 <K, T, H, P, A>(unordered_map const&, unordered_map const&);
832 }; // class template unordered_map
834 template <class K, class T, class H, class P, class A>
835 class unordered_multimap
837 #if defined(BOOST_UNORDERED_USE_MOVE)
838 BOOST_COPYABLE_AND_MOVABLE(unordered_multimap)
840 template <typename, typename, typename, typename, typename>
841 friend class unordered_map;
845 typedef T mapped_type;
846 typedef std::pair<const K, T> value_type;
849 typedef A allocator_type;
852 typedef boost::unordered::detail::map<A, K, T, H, P> types;
853 typedef typename types::value_allocator_traits value_allocator_traits;
854 typedef typename types::table table;
855 typedef typename table::node_pointer node_pointer;
856 typedef typename table::link_pointer link_pointer;
859 typedef typename value_allocator_traits::pointer pointer;
860 typedef typename value_allocator_traits::const_pointer const_pointer;
862 typedef value_type& reference;
863 typedef value_type const& const_reference;
865 typedef std::size_t size_type;
866 typedef std::ptrdiff_t difference_type;
868 typedef typename table::iterator iterator;
869 typedef typename table::c_iterator const_iterator;
870 typedef typename table::l_iterator local_iterator;
871 typedef typename table::cl_iterator const_local_iterator;
872 typedef typename types::node_type node_type;
880 unordered_multimap();
882 explicit unordered_multimap(size_type, const hasher& = hasher(),
883 const key_equal& = key_equal(),
884 const allocator_type& = allocator_type());
886 template <class InputIt>
887 unordered_multimap(InputIt, InputIt,
888 size_type = boost::unordered::detail::default_bucket_count,
889 const hasher& = hasher(), const key_equal& = key_equal(),
890 const allocator_type& = allocator_type());
892 unordered_multimap(unordered_multimap const&);
894 #if defined(BOOST_UNORDERED_USE_MOVE) || \
895 !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
896 unordered_multimap(BOOST_RV_REF(unordered_multimap) other)
897 BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
898 : table_(other.table_, boost::unordered::detail::move_tag())
900 // The move is done in table_
904 explicit unordered_multimap(allocator_type const&);
906 unordered_multimap(unordered_multimap const&, allocator_type const&);
909 BOOST_RV_REF(unordered_multimap), allocator_type const&);
911 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
912 unordered_multimap(std::initializer_list<value_type>,
913 size_type = boost::unordered::detail::default_bucket_count,
914 const hasher& = hasher(), const key_equal& l = key_equal(),
915 const allocator_type& = allocator_type());
918 explicit unordered_multimap(size_type, const allocator_type&);
920 explicit unordered_multimap(
921 size_type, const hasher&, const allocator_type&);
923 template <class InputIt>
924 unordered_multimap(InputIt, InputIt, size_type, const allocator_type&);
926 template <class InputIt>
928 InputIt, InputIt, size_type, const hasher&, const allocator_type&);
930 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
932 std::initializer_list<value_type>, size_type, const allocator_type&);
934 unordered_multimap(std::initializer_list<value_type>, size_type,
935 const hasher&, const allocator_type&);
940 ~unordered_multimap() BOOST_NOEXCEPT;
944 #if defined(BOOST_UNORDERED_USE_MOVE)
945 unordered_multimap& operator=(BOOST_COPY_ASSIGN_REF(unordered_multimap) x)
947 table_.assign(x.table_, boost::unordered::detail::false_type());
951 unordered_multimap& operator=(BOOST_RV_REF(unordered_multimap) x)
952 // C++17 support: BOOST_NOEXCEPT_IF(
953 // value_allocator_traits::is_always_equal::value &&
954 // is_nothrow_move_assignable_v<H> &&
955 // is_nothrow_move_assignable_v<P>)
957 table_.move_assign(x.table_, boost::unordered::detail::false_type());
961 unordered_multimap& operator=(unordered_multimap const& x)
963 table_.assign(x.table_, boost::unordered::detail::false_type());
967 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
968 unordered_multimap& operator=(unordered_multimap&& x)
969 // C++17 support: BOOST_NOEXCEPT_IF(
970 // value_allocator_traits::is_always_equal::value &&
971 // is_nothrow_move_assignable_v<H> &&
972 // is_nothrow_move_assignable_v<P>)
974 table_.move_assign(x.table_, boost::unordered::detail::false_type());
980 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
981 unordered_multimap& operator=(std::initializer_list<value_type>);
984 allocator_type get_allocator() const BOOST_NOEXCEPT
986 return table_.node_alloc();
991 iterator begin() BOOST_NOEXCEPT { return iterator(table_.begin()); }
993 const_iterator begin() const BOOST_NOEXCEPT
995 return const_iterator(table_.begin());
998 iterator end() BOOST_NOEXCEPT { return iterator(); }
1000 const_iterator end() const BOOST_NOEXCEPT { return const_iterator(); }
1002 const_iterator cbegin() const BOOST_NOEXCEPT
1004 return const_iterator(table_.begin());
1007 const_iterator cend() const BOOST_NOEXCEPT { return const_iterator(); }
1009 // size and capacity
1011 bool empty() const BOOST_NOEXCEPT { return table_.size_ == 0; }
1013 size_type size() const BOOST_NOEXCEPT { return table_.size_; }
1015 size_type max_size() const BOOST_NOEXCEPT;
1019 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1021 template <class... Args> iterator emplace(BOOST_FWD_REF(Args)... args)
1023 return iterator(table_.emplace_equiv(
1024 boost::unordered::detail::func::construct_node_from_args(
1025 table_.node_alloc(), boost::forward<Args>(args)...)));
1030 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1
1032 // 0 argument emplace requires special treatment in case
1033 // the container is instantiated with a value type that
1034 // doesn't have a default constructor.
1036 iterator emplace(boost::unordered::detail::empty_emplace =
1037 boost::unordered::detail::empty_emplace(),
1038 value_type v = value_type())
1040 return this->emplace(boost::move(v));
1045 template <typename A0> iterator emplace(BOOST_FWD_REF(A0) a0)
1047 return iterator(table_.emplace_equiv(
1048 boost::unordered::detail::func::construct_node_from_args(
1049 table_.node_alloc(), boost::unordered::detail::create_emplace_args(
1050 boost::forward<A0>(a0)))));
1053 template <typename A0, typename A1>
1054 iterator emplace(BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
1056 return iterator(table_.emplace_equiv(
1057 boost::unordered::detail::func::construct_node_from_args(
1058 table_.node_alloc(),
1059 boost::unordered::detail::create_emplace_args(
1060 boost::forward<A0>(a0), boost::forward<A1>(a1)))));
1063 template <typename A0, typename A1, typename A2>
1065 BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
1067 return iterator(table_.emplace_equiv(
1068 boost::unordered::detail::func::construct_node_from_args(
1069 table_.node_alloc(),
1070 boost::unordered::detail::create_emplace_args(
1071 boost::forward<A0>(a0), boost::forward<A1>(a1),
1072 boost::forward<A2>(a2)))));
1077 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1079 template <class... Args>
1080 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
1082 return iterator(table_.emplace_hint_equiv(
1083 hint, boost::unordered::detail::func::construct_node_from_args(
1084 table_.node_alloc(), boost::forward<Args>(args)...)));
1089 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1
1091 iterator emplace_hint(const_iterator hint,
1092 boost::unordered::detail::empty_emplace =
1093 boost::unordered::detail::empty_emplace(),
1094 value_type v = value_type())
1096 return this->emplace_hint(hint, boost::move(v));
1101 template <typename A0>
1102 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0)
1104 return iterator(table_.emplace_hint_equiv(hint,
1105 boost::unordered::detail::func::construct_node_from_args(
1106 table_.node_alloc(), boost::unordered::detail::create_emplace_args(
1107 boost::forward<A0>(a0)))));
1110 template <typename A0, typename A1>
1111 iterator emplace_hint(
1112 const_iterator hint, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
1114 return iterator(table_.emplace_hint_equiv(
1115 hint, boost::unordered::detail::func::construct_node_from_args(
1116 table_.node_alloc(),
1117 boost::unordered::detail::create_emplace_args(
1118 boost::forward<A0>(a0), boost::forward<A1>(a1)))));
1121 template <typename A0, typename A1, typename A2>
1122 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0,
1123 BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
1125 return iterator(table_.emplace_hint_equiv(
1126 hint, boost::unordered::detail::func::construct_node_from_args(
1127 table_.node_alloc(),
1128 boost::unordered::detail::create_emplace_args(
1129 boost::forward<A0>(a0), boost::forward<A1>(a1),
1130 boost::forward<A2>(a2)))));
1135 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1137 #define BOOST_UNORDERED_EMPLACE(z, n, _) \
1138 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
1139 iterator emplace(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
1141 return iterator(table_.emplace_equiv( \
1142 boost::unordered::detail::func::construct_node_from_args( \
1143 table_.node_alloc(), \
1144 boost::unordered::detail::create_emplace_args( \
1145 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))))); \
1148 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
1149 iterator emplace_hint( \
1150 const_iterator hint, BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
1152 return iterator(table_.emplace_hint_equiv( \
1153 hint, boost::unordered::detail::func::construct_node_from_args( \
1154 table_.node_alloc(), \
1155 boost::unordered::detail::create_emplace_args( \
1156 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))))); \
1159 BOOST_UNORDERED_EMPLACE(1, 4, _)
1160 BOOST_UNORDERED_EMPLACE(1, 5, _)
1161 BOOST_UNORDERED_EMPLACE(1, 6, _)
1162 BOOST_UNORDERED_EMPLACE(1, 7, _)
1163 BOOST_UNORDERED_EMPLACE(1, 8, _)
1164 BOOST_UNORDERED_EMPLACE(1, 9, _)
1165 BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT),
1166 BOOST_UNORDERED_EMPLACE, _)
1168 #undef BOOST_UNORDERED_EMPLACE
1172 iterator insert(value_type const& x) { return this->emplace(x); }
1174 iterator insert(BOOST_RV_REF(value_type) x)
1176 return this->emplace(boost::move(x));
1180 iterator insert(BOOST_RV_REF(P2) obj,
1181 typename boost::enable_if_c<
1182 boost::is_constructible<value_type, BOOST_RV_REF(P2)>::value,
1185 return this->emplace(boost::forward<P2>(obj));
1188 iterator insert(const_iterator hint, value_type const& x)
1190 return this->emplace_hint(hint, x);
1193 iterator insert(const_iterator hint, BOOST_RV_REF(value_type) x)
1195 return this->emplace_hint(hint, boost::move(x));
1199 iterator insert(const_iterator hint, BOOST_RV_REF(P2) obj,
1200 typename boost::enable_if_c<
1201 boost::is_constructible<value_type, BOOST_RV_REF(P2)>::value,
1204 return this->emplace_hint(hint, boost::forward<P2>(obj));
1207 template <class InputIt> void insert(InputIt, InputIt);
1209 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1210 void insert(std::initializer_list<value_type>);
1215 node_type extract(const_iterator position)
1218 table_.extract_by_iterator_equiv(position), table_.node_alloc());
1221 node_type extract(const key_type& k)
1223 return node_type(table_.extract_by_key(k), table_.node_alloc());
1226 iterator insert(BOOST_RV_REF(node_type) np)
1228 return table_.move_insert_node_type_equiv(np);
1231 iterator insert(const_iterator hint, BOOST_RV_REF(node_type) np)
1233 return table_.move_insert_node_type_with_hint_equiv(hint, np);
1236 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || \
1237 (BOOST_COMP_GNUC && BOOST_COMP_GNUC < BOOST_VERSION_NUMBER(4, 6, 0))
1239 // Note: Use r-value node_type to insert.
1240 iterator insert(node_type&);
1241 iterator insert(const_iterator, node_type& np);
1246 iterator erase(iterator);
1247 iterator erase(const_iterator);
1248 size_type erase(const key_type&);
1249 iterator erase(const_iterator, const_iterator);
1250 BOOST_UNORDERED_DEPRECATED("Use erase instead")
1251 void quick_erase(const_iterator it) { erase(it); }
1252 BOOST_UNORDERED_DEPRECATED("Use erase instead")
1253 void erase_return_void(const_iterator it) { erase(it); }
1255 void swap(unordered_multimap&);
1256 // C++17 support: BOOST_NOEXCEPT_IF(
1257 // value_allocator_traits::is_always_equal::value &&
1258 // is_nothrow_move_assignable_v<H> &&
1259 // is_nothrow_move_assignable_v<P>)
1260 void clear() BOOST_NOEXCEPT { table_.clear_impl(); }
1262 template <typename H2, typename P2>
1263 void merge(boost::unordered_multimap<K, T, H2, P2, A>& source);
1265 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
1266 template <typename H2, typename P2>
1267 void merge(boost::unordered_multimap<K, T, H2, P2, A>&& source);
1270 template <typename H2, typename P2>
1271 void merge(boost::unordered_map<K, T, H2, P2, A>& source);
1273 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
1274 template <typename H2, typename P2>
1275 void merge(boost::unordered_map<K, T, H2, P2, A>&& source);
1280 hasher hash_function() const;
1281 key_equal key_eq() const;
1285 iterator find(const key_type&);
1286 const_iterator find(const key_type&) const;
1288 template <class CompatibleKey, class CompatibleHash,
1289 class CompatiblePredicate>
1290 iterator find(CompatibleKey const&, CompatibleHash const&,
1291 CompatiblePredicate const&);
1293 template <class CompatibleKey, class CompatibleHash,
1294 class CompatiblePredicate>
1295 const_iterator find(CompatibleKey const&, CompatibleHash const&,
1296 CompatiblePredicate const&) const;
1298 size_type count(const key_type&) const;
1300 std::pair<iterator, iterator> equal_range(const key_type&);
1301 std::pair<const_iterator, const_iterator> equal_range(
1302 const key_type&) const;
1306 size_type bucket_count() const BOOST_NOEXCEPT
1308 return table_.bucket_count_;
1311 size_type max_bucket_count() const BOOST_NOEXCEPT
1313 return table_.max_bucket_count();
1316 size_type bucket_size(size_type) const;
1318 size_type bucket(const key_type& k) const
1320 return table_.hash_to_bucket(table_.hash(k));
1323 local_iterator begin(size_type n)
1325 return local_iterator(table_.begin(n), n, table_.bucket_count_);
1328 const_local_iterator begin(size_type n) const
1330 return const_local_iterator(table_.begin(n), n, table_.bucket_count_);
1333 local_iterator end(size_type) { return local_iterator(); }
1335 const_local_iterator end(size_type) const
1337 return const_local_iterator();
1340 const_local_iterator cbegin(size_type n) const
1342 return const_local_iterator(table_.begin(n), n, table_.bucket_count_);
1345 const_local_iterator cend(size_type) const
1347 return const_local_iterator();
1352 float load_factor() const BOOST_NOEXCEPT;
1353 float max_load_factor() const BOOST_NOEXCEPT { return table_.mlf_; }
1354 void max_load_factor(float) BOOST_NOEXCEPT;
1355 void rehash(size_type);
1356 void reserve(size_type);
1358 #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
1359 friend bool operator==
1360 <K, T, H, P, A>(unordered_multimap const&, unordered_multimap const&);
1361 friend bool operator!=
1362 <K, T, H, P, A>(unordered_multimap const&, unordered_multimap const&);
1364 }; // class template unordered_multimap
1366 ////////////////////////////////////////////////////////////////////////////
1368 template <class K, class T, class H, class P, class A>
1369 unordered_map<K, T, H, P, A>::unordered_map()
1370 : table_(boost::unordered::detail::default_bucket_count, hasher(),
1371 key_equal(), allocator_type())
1375 template <class K, class T, class H, class P, class A>
1376 unordered_map<K, T, H, P, A>::unordered_map(size_type n, const hasher& hf,
1377 const key_equal& eql, const allocator_type& a)
1378 : table_(n, hf, eql, a)
1382 template <class K, class T, class H, class P, class A>
1383 template <class InputIt>
1384 unordered_map<K, T, H, P, A>::unordered_map(InputIt f, InputIt l,
1385 size_type n, const hasher& hf, const key_equal& eql,
1386 const allocator_type& a)
1387 : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
1392 template <class K, class T, class H, class P, class A>
1393 unordered_map<K, T, H, P, A>::unordered_map(unordered_map const& other)
1394 : table_(other.table_,
1395 unordered_map::value_allocator_traits::
1396 select_on_container_copy_construction(other.get_allocator()))
1398 if (other.table_.size_) {
1399 table_.copy_buckets(
1400 other.table_, boost::unordered::detail::true_type());
1404 template <class K, class T, class H, class P, class A>
1405 unordered_map<K, T, H, P, A>::unordered_map(allocator_type const& a)
1406 : table_(boost::unordered::detail::default_bucket_count, hasher(),
1411 template <class K, class T, class H, class P, class A>
1412 unordered_map<K, T, H, P, A>::unordered_map(
1413 unordered_map const& other, allocator_type const& a)
1414 : table_(other.table_, a)
1416 if (other.table_.size_) {
1417 table_.copy_buckets(
1418 other.table_, boost::unordered::detail::true_type());
1422 template <class K, class T, class H, class P, class A>
1423 unordered_map<K, T, H, P, A>::unordered_map(
1424 BOOST_RV_REF(unordered_map) other, allocator_type const& a)
1425 : table_(other.table_, a, boost::unordered::detail::move_tag())
1427 table_.move_construct_buckets(other.table_);
1430 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1432 template <class K, class T, class H, class P, class A>
1433 unordered_map<K, T, H, P, A>::unordered_map(
1434 std::initializer_list<value_type> list, size_type n, const hasher& hf,
1435 const key_equal& eql, const allocator_type& a)
1437 boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1440 this->insert(list.begin(), list.end());
1445 template <class K, class T, class H, class P, class A>
1446 unordered_map<K, T, H, P, A>::unordered_map(
1447 size_type n, const allocator_type& a)
1448 : table_(n, hasher(), key_equal(), a)
1452 template <class K, class T, class H, class P, class A>
1453 unordered_map<K, T, H, P, A>::unordered_map(
1454 size_type n, const hasher& hf, const allocator_type& a)
1455 : table_(n, hf, key_equal(), a)
1459 template <class K, class T, class H, class P, class A>
1460 template <class InputIt>
1461 unordered_map<K, T, H, P, A>::unordered_map(
1462 InputIt f, InputIt l, size_type n, const allocator_type& a)
1463 : table_(boost::unordered::detail::initial_size(f, l, n), hasher(),
1469 template <class K, class T, class H, class P, class A>
1470 template <class InputIt>
1471 unordered_map<K, T, H, P, A>::unordered_map(InputIt f, InputIt l,
1472 size_type n, const hasher& hf, const allocator_type& a)
1474 boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a)
1479 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1481 template <class K, class T, class H, class P, class A>
1482 unordered_map<K, T, H, P, A>::unordered_map(
1483 std::initializer_list<value_type> list, size_type n,
1484 const allocator_type& a)
1486 boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1487 hasher(), key_equal(), a)
1489 this->insert(list.begin(), list.end());
1492 template <class K, class T, class H, class P, class A>
1493 unordered_map<K, T, H, P, A>::unordered_map(
1494 std::initializer_list<value_type> list, size_type n, const hasher& hf,
1495 const allocator_type& a)
1497 boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1500 this->insert(list.begin(), list.end());
1505 template <class K, class T, class H, class P, class A>
1506 unordered_map<K, T, H, P, A>::~unordered_map() BOOST_NOEXCEPT
1510 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1512 template <class K, class T, class H, class P, class A>
1513 unordered_map<K, T, H, P, A>& unordered_map<K, T, H, P, A>::operator=(
1514 std::initializer_list<value_type> list)
1517 this->insert(list.begin(), list.end());
1523 // size and capacity
1525 template <class K, class T, class H, class P, class A>
1526 std::size_t unordered_map<K, T, H, P, A>::max_size() const BOOST_NOEXCEPT
1528 using namespace std;
1530 // size <= mlf_ * count
1531 return boost::unordered::detail::double_to_size(
1532 ceil(static_cast<double>(table_.mlf_) *
1533 static_cast<double>(table_.max_bucket_count()))) -
1539 template <class K, class T, class H, class P, class A>
1540 template <class InputIt>
1541 void unordered_map<K, T, H, P, A>::insert(InputIt first, InputIt last)
1543 if (first != last) {
1544 table_.insert_range_unique(
1545 table::extractor::extract(*first), first, last);
1549 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1550 template <class K, class T, class H, class P, class A>
1551 void unordered_map<K, T, H, P, A>::insert(
1552 std::initializer_list<value_type> list)
1554 this->insert(list.begin(), list.end());
1558 template <class K, class T, class H, class P, class A>
1559 typename unordered_map<K, T, H, P, A>::iterator
1560 unordered_map<K, T, H, P, A>::erase(iterator position)
1562 node_pointer node = table::get_node(position);
1564 node_pointer next = table::next_node(node);
1565 table_.erase_nodes_unique(node, next);
1566 return iterator(next);
1569 template <class K, class T, class H, class P, class A>
1570 typename unordered_map<K, T, H, P, A>::iterator
1571 unordered_map<K, T, H, P, A>::erase(const_iterator position)
1573 node_pointer node = table::get_node(position);
1575 node_pointer next = table::next_node(node);
1576 table_.erase_nodes_unique(node, next);
1577 return iterator(next);
1580 template <class K, class T, class H, class P, class A>
1581 typename unordered_map<K, T, H, P, A>::size_type
1582 unordered_map<K, T, H, P, A>::erase(const key_type& k)
1584 return table_.erase_key_unique(k);
1587 template <class K, class T, class H, class P, class A>
1588 typename unordered_map<K, T, H, P, A>::iterator
1589 unordered_map<K, T, H, P, A>::erase(
1590 const_iterator first, const_iterator last)
1592 node_pointer last_node = table::get_node(last);
1594 return iterator(last_node);
1595 table_.erase_nodes_unique(table::get_node(first), last_node);
1596 return iterator(last_node);
1599 template <class K, class T, class H, class P, class A>
1600 void unordered_map<K, T, H, P, A>::swap(unordered_map& other)
1601 // C++17 support: BOOST_NOEXCEPT_IF(
1602 // value_allocator_traits::is_always_equal::value &&
1603 // is_nothrow_move_assignable_v<H> &&
1604 // is_nothrow_move_assignable_v<P>)
1606 table_.swap(other.table_);
1609 template <class K, class T, class H, class P, class A>
1610 template <typename H2, typename P2>
1611 void unordered_map<K, T, H, P, A>::merge(
1612 boost::unordered_map<K, T, H2, P2, A>& source)
1614 table_.merge_unique(source.table_);
1617 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
1618 template <class K, class T, class H, class P, class A>
1619 template <typename H2, typename P2>
1620 void unordered_map<K, T, H, P, A>::merge(
1621 boost::unordered_map<K, T, H2, P2, A>&& source)
1623 table_.merge_unique(source.table_);
1627 template <class K, class T, class H, class P, class A>
1628 template <typename H2, typename P2>
1629 void unordered_map<K, T, H, P, A>::merge(
1630 boost::unordered_multimap<K, T, H2, P2, A>& source)
1632 table_.merge_unique(source.table_);
1635 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
1636 template <class K, class T, class H, class P, class A>
1637 template <typename H2, typename P2>
1638 void unordered_map<K, T, H, P, A>::merge(
1639 boost::unordered_multimap<K, T, H2, P2, A>&& source)
1641 table_.merge_unique(source.table_);
1647 template <class K, class T, class H, class P, class A>
1648 typename unordered_map<K, T, H, P, A>::hasher
1649 unordered_map<K, T, H, P, A>::hash_function() const
1651 return table_.hash_function();
1654 template <class K, class T, class H, class P, class A>
1655 typename unordered_map<K, T, H, P, A>::key_equal
1656 unordered_map<K, T, H, P, A>::key_eq() const
1658 return table_.key_eq();
1663 template <class K, class T, class H, class P, class A>
1664 typename unordered_map<K, T, H, P, A>::iterator
1665 unordered_map<K, T, H, P, A>::find(const key_type& k)
1667 return iterator(table_.find_node(k));
1670 template <class K, class T, class H, class P, class A>
1671 typename unordered_map<K, T, H, P, A>::const_iterator
1672 unordered_map<K, T, H, P, A>::find(const key_type& k) const
1674 return const_iterator(table_.find_node(k));
1677 template <class K, class T, class H, class P, class A>
1678 template <class CompatibleKey, class CompatibleHash,
1679 class CompatiblePredicate>
1680 typename unordered_map<K, T, H, P, A>::iterator
1681 unordered_map<K, T, H, P, A>::find(CompatibleKey const& k,
1682 CompatibleHash const& hash, CompatiblePredicate const& eq)
1685 table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq));
1688 template <class K, class T, class H, class P, class A>
1689 template <class CompatibleKey, class CompatibleHash,
1690 class CompatiblePredicate>
1691 typename unordered_map<K, T, H, P, A>::const_iterator
1692 unordered_map<K, T, H, P, A>::find(CompatibleKey const& k,
1693 CompatibleHash const& hash, CompatiblePredicate const& eq) const
1695 return const_iterator(
1696 table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq));
1699 template <class K, class T, class H, class P, class A>
1700 typename unordered_map<K, T, H, P, A>::size_type
1701 unordered_map<K, T, H, P, A>::count(const key_type& k) const
1703 return table_.find_node(k) ? 1 : 0;
1706 template <class K, class T, class H, class P, class A>
1707 std::pair<typename unordered_map<K, T, H, P, A>::iterator,
1708 typename unordered_map<K, T, H, P, A>::iterator>
1709 unordered_map<K, T, H, P, A>::equal_range(const key_type& k)
1711 node_pointer n = table_.find_node(k);
1712 return std::make_pair(iterator(n), iterator(n ? table::next_node(n) : n));
1715 template <class K, class T, class H, class P, class A>
1716 std::pair<typename unordered_map<K, T, H, P, A>::const_iterator,
1717 typename unordered_map<K, T, H, P, A>::const_iterator>
1718 unordered_map<K, T, H, P, A>::equal_range(const key_type& k) const
1720 node_pointer n = table_.find_node(k);
1721 return std::make_pair(
1722 const_iterator(n), const_iterator(n ? table::next_node(n) : n));
1725 template <class K, class T, class H, class P, class A>
1726 typename unordered_map<K, T, H, P, A>::mapped_type&
1727 unordered_map<K, T, H, P, A>::operator[](const key_type& k)
1729 return table_.try_emplace_unique(k).first->second;
1732 template <class K, class T, class H, class P, class A>
1733 typename unordered_map<K, T, H, P, A>::mapped_type&
1734 unordered_map<K, T, H, P, A>::operator[](BOOST_RV_REF(key_type) k)
1736 return table_.try_emplace_unique(boost::move(k)).first->second;
1739 template <class K, class T, class H, class P, class A>
1740 typename unordered_map<K, T, H, P, A>::mapped_type&
1741 unordered_map<K, T, H, P, A>::at(const key_type& k)
1744 node_pointer n = table_.find_node(k);
1746 return n->value().second;
1749 boost::throw_exception(
1750 std::out_of_range("Unable to find key in unordered_map."));
1753 template <class K, class T, class H, class P, class A>
1754 typename unordered_map<K, T, H, P, A>::mapped_type const&
1755 unordered_map<K, T, H, P, A>::at(const key_type& k) const
1758 node_pointer n = table_.find_node(k);
1760 return n->value().second;
1763 boost::throw_exception(
1764 std::out_of_range("Unable to find key in unordered_map."));
1767 template <class K, class T, class H, class P, class A>
1768 typename unordered_map<K, T, H, P, A>::size_type
1769 unordered_map<K, T, H, P, A>::bucket_size(size_type n) const
1771 return table_.bucket_size(n);
1776 template <class K, class T, class H, class P, class A>
1777 float unordered_map<K, T, H, P, A>::load_factor() const BOOST_NOEXCEPT
1779 BOOST_ASSERT(table_.bucket_count_ != 0);
1780 return static_cast<float>(table_.size_) /
1781 static_cast<float>(table_.bucket_count_);
1784 template <class K, class T, class H, class P, class A>
1785 void unordered_map<K, T, H, P, A>::max_load_factor(float m) BOOST_NOEXCEPT
1787 table_.max_load_factor(m);
1790 template <class K, class T, class H, class P, class A>
1791 void unordered_map<K, T, H, P, A>::rehash(size_type n)
1796 template <class K, class T, class H, class P, class A>
1797 void unordered_map<K, T, H, P, A>::reserve(size_type n)
1799 table_.rehash(static_cast<std::size_t>(
1800 std::ceil(static_cast<double>(n) / table_.mlf_)));
1803 template <class K, class T, class H, class P, class A>
1804 inline bool operator==(unordered_map<K, T, H, P, A> const& m1,
1805 unordered_map<K, T, H, P, A> const& m2)
1807 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1810 unordered_map<K, T, H, P, A> x;
1813 return m1.table_.equals_unique(m2.table_);
1816 template <class K, class T, class H, class P, class A>
1817 inline bool operator!=(unordered_map<K, T, H, P, A> const& m1,
1818 unordered_map<K, T, H, P, A> const& m2)
1820 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1823 unordered_map<K, T, H, P, A> x;
1826 return !m1.table_.equals_unique(m2.table_);
1829 template <class K, class T, class H, class P, class A>
1831 unordered_map<K, T, H, P, A>& m1, unordered_map<K, T, H, P, A>& m2)
1832 BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT_EXPR(m1.swap(m2)))
1834 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1837 unordered_map<K, T, H, P, A> x;
1843 ////////////////////////////////////////////////////////////////////////////
1845 template <class K, class T, class H, class P, class A>
1846 unordered_multimap<K, T, H, P, A>::unordered_multimap()
1847 : table_(boost::unordered::detail::default_bucket_count, hasher(),
1848 key_equal(), allocator_type())
1852 template <class K, class T, class H, class P, class A>
1853 unordered_multimap<K, T, H, P, A>::unordered_multimap(size_type n,
1854 const hasher& hf, const key_equal& eql, const allocator_type& a)
1855 : table_(n, hf, eql, a)
1859 template <class K, class T, class H, class P, class A>
1860 template <class InputIt>
1861 unordered_multimap<K, T, H, P, A>::unordered_multimap(InputIt f, InputIt l,
1862 size_type n, const hasher& hf, const key_equal& eql,
1863 const allocator_type& a)
1864 : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
1869 template <class K, class T, class H, class P, class A>
1870 unordered_multimap<K, T, H, P, A>::unordered_multimap(
1871 unordered_multimap const& other)
1872 : table_(other.table_,
1873 unordered_multimap::value_allocator_traits::
1874 select_on_container_copy_construction(other.get_allocator()))
1876 if (other.table_.size_) {
1877 table_.copy_buckets(
1878 other.table_, boost::unordered::detail::false_type());
1882 template <class K, class T, class H, class P, class A>
1883 unordered_multimap<K, T, H, P, A>::unordered_multimap(
1884 allocator_type const& a)
1885 : table_(boost::unordered::detail::default_bucket_count, hasher(),
1890 template <class K, class T, class H, class P, class A>
1891 unordered_multimap<K, T, H, P, A>::unordered_multimap(
1892 unordered_multimap const& other, allocator_type const& a)
1893 : table_(other.table_, a)
1895 if (other.table_.size_) {
1896 table_.copy_buckets(
1897 other.table_, boost::unordered::detail::false_type());
1901 template <class K, class T, class H, class P, class A>
1902 unordered_multimap<K, T, H, P, A>::unordered_multimap(
1903 BOOST_RV_REF(unordered_multimap) other, allocator_type const& a)
1904 : table_(other.table_, a, boost::unordered::detail::move_tag())
1906 table_.move_construct_buckets(other.table_);
1909 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1911 template <class K, class T, class H, class P, class A>
1912 unordered_multimap<K, T, H, P, A>::unordered_multimap(
1913 std::initializer_list<value_type> list, size_type n, const hasher& hf,
1914 const key_equal& eql, const allocator_type& a)
1916 boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1919 this->insert(list.begin(), list.end());
1924 template <class K, class T, class H, class P, class A>
1925 unordered_multimap<K, T, H, P, A>::unordered_multimap(
1926 size_type n, const allocator_type& a)
1927 : table_(n, hasher(), key_equal(), a)
1931 template <class K, class T, class H, class P, class A>
1932 unordered_multimap<K, T, H, P, A>::unordered_multimap(
1933 size_type n, const hasher& hf, const allocator_type& a)
1934 : table_(n, hf, key_equal(), a)
1938 template <class K, class T, class H, class P, class A>
1939 template <class InputIt>
1940 unordered_multimap<K, T, H, P, A>::unordered_multimap(
1941 InputIt f, InputIt l, size_type n, const allocator_type& a)
1942 : table_(boost::unordered::detail::initial_size(f, l, n), hasher(),
1948 template <class K, class T, class H, class P, class A>
1949 template <class InputIt>
1950 unordered_multimap<K, T, H, P, A>::unordered_multimap(InputIt f, InputIt l,
1951 size_type n, const hasher& hf, const allocator_type& a)
1953 boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a)
1958 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1960 template <class K, class T, class H, class P, class A>
1961 unordered_multimap<K, T, H, P, A>::unordered_multimap(
1962 std::initializer_list<value_type> list, size_type n,
1963 const allocator_type& a)
1965 boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1966 hasher(), key_equal(), a)
1968 this->insert(list.begin(), list.end());
1971 template <class K, class T, class H, class P, class A>
1972 unordered_multimap<K, T, H, P, A>::unordered_multimap(
1973 std::initializer_list<value_type> list, size_type n, const hasher& hf,
1974 const allocator_type& a)
1976 boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1979 this->insert(list.begin(), list.end());
1984 template <class K, class T, class H, class P, class A>
1985 unordered_multimap<K, T, H, P, A>::~unordered_multimap() BOOST_NOEXCEPT
1989 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1991 template <class K, class T, class H, class P, class A>
1992 unordered_multimap<K, T, H, P, A>& unordered_multimap<K, T, H, P, A>::
1993 operator=(std::initializer_list<value_type> list)
1996 this->insert(list.begin(), list.end());
2002 // size and capacity
2004 template <class K, class T, class H, class P, class A>
2006 unordered_multimap<K, T, H, P, A>::max_size() const BOOST_NOEXCEPT
2008 using namespace std;
2010 // size <= mlf_ * count
2011 return boost::unordered::detail::double_to_size(
2012 ceil(static_cast<double>(table_.mlf_) *
2013 static_cast<double>(table_.max_bucket_count()))) -
2019 template <class K, class T, class H, class P, class A>
2020 template <class InputIt>
2021 void unordered_multimap<K, T, H, P, A>::insert(InputIt first, InputIt last)
2023 table_.insert_range_equiv(first, last);
2026 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
2027 template <class K, class T, class H, class P, class A>
2028 void unordered_multimap<K, T, H, P, A>::insert(
2029 std::initializer_list<value_type> list)
2031 this->insert(list.begin(), list.end());
2035 template <class K, class T, class H, class P, class A>
2036 typename unordered_multimap<K, T, H, P, A>::iterator
2037 unordered_multimap<K, T, H, P, A>::erase(iterator position)
2039 node_pointer node = table::get_node(position);
2041 node_pointer next = table::next_node(node);
2042 table_.erase_nodes_equiv(node, next);
2043 return iterator(next);
2046 template <class K, class T, class H, class P, class A>
2047 typename unordered_multimap<K, T, H, P, A>::iterator
2048 unordered_multimap<K, T, H, P, A>::erase(const_iterator position)
2050 node_pointer node = table::get_node(position);
2052 node_pointer next = table::next_node(node);
2053 table_.erase_nodes_equiv(node, next);
2054 return iterator(next);
2057 template <class K, class T, class H, class P, class A>
2058 typename unordered_multimap<K, T, H, P, A>::size_type
2059 unordered_multimap<K, T, H, P, A>::erase(const key_type& k)
2061 return table_.erase_key_equiv(k);
2064 template <class K, class T, class H, class P, class A>
2065 typename unordered_multimap<K, T, H, P, A>::iterator
2066 unordered_multimap<K, T, H, P, A>::erase(
2067 const_iterator first, const_iterator last)
2069 node_pointer last_node = table::get_node(last);
2071 return iterator(last_node);
2072 table_.erase_nodes_equiv(table::get_node(first), last_node);
2073 return iterator(last_node);
2076 template <class K, class T, class H, class P, class A>
2077 void unordered_multimap<K, T, H, P, A>::swap(unordered_multimap& other)
2078 // C++17 support: BOOST_NOEXCEPT_IF(
2079 // value_allocator_traits::is_always_equal::value &&
2080 // is_nothrow_move_assignable_v<H> &&
2081 // is_nothrow_move_assignable_v<P>)
2083 table_.swap(other.table_);
2088 template <class K, class T, class H, class P, class A>
2089 typename unordered_multimap<K, T, H, P, A>::hasher
2090 unordered_multimap<K, T, H, P, A>::hash_function() const
2092 return table_.hash_function();
2095 template <class K, class T, class H, class P, class A>
2096 typename unordered_multimap<K, T, H, P, A>::key_equal
2097 unordered_multimap<K, T, H, P, A>::key_eq() const
2099 return table_.key_eq();
2102 template <class K, class T, class H, class P, class A>
2103 template <typename H2, typename P2>
2104 void unordered_multimap<K, T, H, P, A>::merge(
2105 boost::unordered_multimap<K, T, H2, P2, A>& source)
2107 while (!source.empty()) {
2108 insert(source.extract(source.begin()));
2112 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
2113 template <class K, class T, class H, class P, class A>
2114 template <typename H2, typename P2>
2115 void unordered_multimap<K, T, H, P, A>::merge(
2116 boost::unordered_multimap<K, T, H2, P2, A>&& source)
2118 while (!source.empty()) {
2119 insert(source.extract(source.begin()));
2124 template <class K, class T, class H, class P, class A>
2125 template <typename H2, typename P2>
2126 void unordered_multimap<K, T, H, P, A>::merge(
2127 boost::unordered_map<K, T, H2, P2, A>& source)
2129 while (!source.empty()) {
2130 insert(source.extract(source.begin()));
2134 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
2135 template <class K, class T, class H, class P, class A>
2136 template <typename H2, typename P2>
2137 void unordered_multimap<K, T, H, P, A>::merge(
2138 boost::unordered_map<K, T, H2, P2, A>&& source)
2140 while (!source.empty()) {
2141 insert(source.extract(source.begin()));
2148 template <class K, class T, class H, class P, class A>
2149 typename unordered_multimap<K, T, H, P, A>::iterator
2150 unordered_multimap<K, T, H, P, A>::find(const key_type& k)
2152 return iterator(table_.find_node(k));
2155 template <class K, class T, class H, class P, class A>
2156 typename unordered_multimap<K, T, H, P, A>::const_iterator
2157 unordered_multimap<K, T, H, P, A>::find(const key_type& k) const
2159 return const_iterator(table_.find_node(k));
2162 template <class K, class T, class H, class P, class A>
2163 template <class CompatibleKey, class CompatibleHash,
2164 class CompatiblePredicate>
2165 typename unordered_multimap<K, T, H, P, A>::iterator
2166 unordered_multimap<K, T, H, P, A>::find(CompatibleKey const& k,
2167 CompatibleHash const& hash, CompatiblePredicate const& eq)
2170 table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq));
2173 template <class K, class T, class H, class P, class A>
2174 template <class CompatibleKey, class CompatibleHash,
2175 class CompatiblePredicate>
2176 typename unordered_multimap<K, T, H, P, A>::const_iterator
2177 unordered_multimap<K, T, H, P, A>::find(CompatibleKey const& k,
2178 CompatibleHash const& hash, CompatiblePredicate const& eq) const
2180 return const_iterator(
2181 table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq));
2184 template <class K, class T, class H, class P, class A>
2185 typename unordered_multimap<K, T, H, P, A>::size_type
2186 unordered_multimap<K, T, H, P, A>::count(const key_type& k) const
2188 node_pointer n = table_.find_node(k);
2189 return n ? table_.group_count(n) : 0;
2192 template <class K, class T, class H, class P, class A>
2193 std::pair<typename unordered_multimap<K, T, H, P, A>::iterator,
2194 typename unordered_multimap<K, T, H, P, A>::iterator>
2195 unordered_multimap<K, T, H, P, A>::equal_range(const key_type& k)
2197 node_pointer n = table_.find_node(k);
2198 return std::make_pair(
2199 iterator(n), iterator(n ? table_.next_group(n) : n));
2202 template <class K, class T, class H, class P, class A>
2203 std::pair<typename unordered_multimap<K, T, H, P, A>::const_iterator,
2204 typename unordered_multimap<K, T, H, P, A>::const_iterator>
2205 unordered_multimap<K, T, H, P, A>::equal_range(const key_type& k) const
2207 node_pointer n = table_.find_node(k);
2208 return std::make_pair(
2209 const_iterator(n), const_iterator(n ? table_.next_group(n) : n));
2212 template <class K, class T, class H, class P, class A>
2213 typename unordered_multimap<K, T, H, P, A>::size_type
2214 unordered_multimap<K, T, H, P, A>::bucket_size(size_type n) const
2216 return table_.bucket_size(n);
2221 template <class K, class T, class H, class P, class A>
2222 float unordered_multimap<K, T, H, P, A>::load_factor() const BOOST_NOEXCEPT
2224 BOOST_ASSERT(table_.bucket_count_ != 0);
2225 return static_cast<float>(table_.size_) /
2226 static_cast<float>(table_.bucket_count_);
2229 template <class K, class T, class H, class P, class A>
2230 void unordered_multimap<K, T, H, P, A>::max_load_factor(
2231 float m) BOOST_NOEXCEPT
2233 table_.max_load_factor(m);
2236 template <class K, class T, class H, class P, class A>
2237 void unordered_multimap<K, T, H, P, A>::rehash(size_type n)
2242 template <class K, class T, class H, class P, class A>
2243 void unordered_multimap<K, T, H, P, A>::reserve(size_type n)
2245 table_.rehash(static_cast<std::size_t>(
2246 std::ceil(static_cast<double>(n) / table_.mlf_)));
2249 template <class K, class T, class H, class P, class A>
2250 inline bool operator==(unordered_multimap<K, T, H, P, A> const& m1,
2251 unordered_multimap<K, T, H, P, A> const& m2)
2253 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
2256 unordered_multimap<K, T, H, P, A> x;
2259 return m1.table_.equals_equiv(m2.table_);
2262 template <class K, class T, class H, class P, class A>
2263 inline bool operator!=(unordered_multimap<K, T, H, P, A> const& m1,
2264 unordered_multimap<K, T, H, P, A> const& m2)
2266 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
2269 unordered_multimap<K, T, H, P, A> x;
2272 return !m1.table_.equals_equiv(m2.table_);
2275 template <class K, class T, class H, class P, class A>
2276 inline void swap(unordered_multimap<K, T, H, P, A>& m1,
2277 unordered_multimap<K, T, H, P, A>& m2)
2278 BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT_EXPR(m1.swap(m2)))
2280 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
2283 unordered_multimap<K, T, H, P, A> x;
2289 template <typename N, class K, class T, class A> class node_handle_map
2291 BOOST_MOVABLE_BUT_NOT_COPYABLE(node_handle_map)
2293 template <typename Types> friend struct ::boost::unordered::detail::table;
2294 template <class K2, class T2, class H2, class P2, class A2>
2295 friend class boost::unordered::unordered_map;
2296 template <class K2, class T2, class H2, class P2, class A2>
2297 friend class boost::unordered::unordered_multimap;
2299 typedef typename boost::unordered::detail::rebind_wrap<A,
2300 std::pair<K const, T> >::type value_allocator;
2301 typedef boost::unordered::detail::allocator_traits<value_allocator>
2302 value_allocator_traits;
2304 typedef typename boost::unordered::detail::rebind_wrap<A, node>::type
2306 typedef boost::unordered::detail::allocator_traits<node_allocator>
2307 node_allocator_traits;
2308 typedef typename node_allocator_traits::pointer node_pointer;
2312 typedef T mapped_type;
2313 typedef A allocator_type;
2318 boost::unordered::detail::value_base<value_allocator> alloc_;
2320 node_handle_map(node_pointer ptr, allocator_type const& a)
2321 : ptr_(ptr), has_alloc_(false)
2324 new ((void*)&alloc_) value_allocator(a);
2330 BOOST_CONSTEXPR node_handle_map() BOOST_NOEXCEPT : ptr_(),
2337 if (has_alloc_ && ptr_) {
2338 node_allocator node_alloc(alloc_.value());
2339 boost::unordered::detail::node_tmp<node_allocator> tmp(
2343 alloc_.value_ptr()->~value_allocator();
2347 node_handle_map(BOOST_RV_REF(node_handle_map) n) BOOST_NOEXCEPT
2352 new ((void*)&alloc_) value_allocator(boost::move(n.alloc_.value()));
2354 n.ptr_ = node_pointer();
2355 n.alloc_.value_ptr()->~value_allocator();
2356 n.has_alloc_ = false;
2360 node_handle_map& operator=(BOOST_RV_REF(node_handle_map) n)
2362 BOOST_ASSERT(!has_alloc_ ||
2363 value_allocator_traits::
2364 propagate_on_container_move_assignment::value ||
2365 (n.has_alloc_ && alloc_.value() == n.alloc_.value()));
2368 node_allocator node_alloc(alloc_.value());
2369 boost::unordered::detail::node_tmp<node_allocator> tmp(
2371 ptr_ = node_pointer();
2375 alloc_.value_ptr()->~value_allocator();
2379 if (!has_alloc_ && n.has_alloc_) {
2384 n.ptr_ = node_pointer();
2389 key_type& key() const
2391 return const_cast<key_type&>(ptr_->value().first);
2394 mapped_type& mapped() const { return ptr_->value().second; }
2396 allocator_type get_allocator() const { return alloc_.value(); }
2398 BOOST_EXPLICIT_OPERATOR_BOOL_NOEXCEPT()
2400 bool operator!() const BOOST_NOEXCEPT { return ptr_ ? 0 : 1; }
2402 bool empty() const BOOST_NOEXCEPT { return ptr_ ? 0 : 1; }
2404 void swap(node_handle_map& n) BOOST_NOEXCEPT_IF(
2405 value_allocator_traits::propagate_on_container_swap::value
2406 /* || value_allocator_traits::is_always_equal::value */)
2412 } else if (!n.has_alloc_) {
2413 n.move_allocator(*this);
2416 n, boost::unordered::detail::integral_constant<bool,
2417 value_allocator_traits::propagate_on_container_swap::value>());
2419 boost::swap(ptr_, n.ptr_);
2423 void move_allocator(node_handle_map& n)
2425 new ((void*)&alloc_) value_allocator(boost::move(n.alloc_.value()));
2426 n.alloc_.value_ptr()->~value_allocator();
2428 n.has_alloc_ = false;
2431 void swap_impl(node_handle_map&, boost::unordered::detail::false_type) {}
2433 void swap_impl(node_handle_map& n, boost::unordered::detail::true_type)
2435 boost::swap(alloc_, n.alloc_);
2439 template <class N, class K, class T, class A>
2440 void swap(node_handle_map<N, K, T, A>& x, node_handle_map<N, K, T, A>& y)
2441 BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT_EXPR(x.swap(y)))
2446 template <class N, class K, class T, class A> struct insert_return_type_map
2449 BOOST_MOVABLE_BUT_NOT_COPYABLE(insert_return_type_map)
2451 typedef typename boost::unordered::detail::rebind_wrap<A,
2452 std::pair<K const, T> >::type value_allocator;
2457 boost::unordered::iterator_detail::iterator<node_> position;
2458 boost::unordered::node_handle_map<N, K, T, A> node;
2460 insert_return_type_map() : inserted(false), position(), node() {}
2462 insert_return_type_map(BOOST_RV_REF(insert_return_type_map)
2463 x) BOOST_NOEXCEPT : inserted(x.inserted),
2464 position(x.position),
2465 node(boost::move(x.node))
2469 insert_return_type_map& operator=(BOOST_RV_REF(insert_return_type_map) x)
2471 inserted = x.inserted;
2472 position = x.position;
2473 node = boost::move(x.node);
2478 template <class N, class K, class T, class A>
2479 void swap(insert_return_type_map<N, K, T, A>& x,
2480 insert_return_type_map<N, K, T, A>& y)
2482 boost::swap(x.node, y.node);
2483 boost::swap(x.inserted, y.inserted);
2484 boost::swap(x.position, y.position);
2486 } // namespace unordered
2487 } // namespace boost
2489 #if defined(BOOST_MSVC)
2490 #pragma warning(pop)
2493 #endif // BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED