Line data Source code
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 0 : unordered_map(BOOST_RV_REF(unordered_map) other)
103 : BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
104 0 : : table_(other.table_, boost::unordered::detail::move_tag())
105 : {
106 : // The move is done in table_
107 0 : }
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)
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 :
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
164 0 : unordered_map& operator=(unordered_map const& x)
165 : {
166 0 : table_.assign(x.table_, boost::unordered::detail::true_type());
167 : return *this;
168 : }
169 :
170 : #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
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 :
186 0 : allocator_type get_allocator() const BOOST_NOEXCEPT
187 : {
188 0 : return table_.node_alloc();
189 : }
190 :
191 : // iterators
192 :
193 0 : iterator begin() BOOST_NOEXCEPT { return iterator(table_.begin()); }
194 :
195 0 : const_iterator begin() const BOOST_NOEXCEPT
196 : {
197 0 : return const_iterator(table_.begin());
198 : }
199 :
200 479 : iterator end() BOOST_NOEXCEPT { return iterator(); }
201 :
202 0 : const_iterator end() const BOOST_NOEXCEPT { return const_iterator(); }
203 :
204 : const_iterator cbegin() const BOOST_NOEXCEPT
205 : {
206 : return const_iterator(table_.begin());
207 : }
208 :
209 : const_iterator cend() const BOOST_NOEXCEPT { return const_iterator(); }
210 :
211 : // size and capacity
212 :
213 : bool empty() const BOOST_NOEXCEPT { return table_.size_ == 0; }
214 :
215 0 : 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>
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 :
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>
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>
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>
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>
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 :
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>
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>
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>
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, _)
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 :
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>
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 :
396 : iterator insert(const_iterator hint, value_type const& x)
397 : {
398 : return this->emplace_hint(hint, x);
399 : }
400 :
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>
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 :
423 : node_type extract(const_iterator position)
424 : {
425 : return node_type(
426 : table_.extract_by_iterator_unique(position), table_.node_alloc());
427 : }
428 :
429 : node_type extract(const key_type& k)
430 : {
431 : return node_type(table_.extract_by_key(k), table_.node_alloc());
432 : }
433 :
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 :
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>
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>
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>
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>
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>
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>
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>
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>
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")
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); }
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);
722 1 : 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 :
773 : size_type bucket_count() const BOOST_NOEXCEPT
774 : {
775 : return table_.bucket_count_;
776 : }
777 :
778 : 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 :
785 : size_type bucket(const key_type& k) const
786 : {
787 : return table_.hash_to_bucket(table_.hash(k));
788 : }
789 :
790 : local_iterator begin(size_type n)
791 : {
792 : return local_iterator(table_.begin(n), n, table_.bucket_count_);
793 : }
794 :
795 : const_local_iterator begin(size_type n) const
796 : {
797 : return const_local_iterator(table_.begin(n), n, table_.bucket_count_);
798 : }
799 :
800 : local_iterator end(size_type) { return local_iterator(); }
801 :
802 : const_local_iterator end(size_type) const
803 : {
804 : return const_local_iterator();
805 : }
806 :
807 : const_local_iterator cbegin(size_type n) const
808 : {
809 : return const_local_iterator(table_.begin(n), n, table_.bucket_count_);
810 : }
811 :
812 : 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;
820 : 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(__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)
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)
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 :
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
1034 0 : unordered_multimap& operator=(unordered_multimap const& x)
1035 : {
1036 0 : table_.assign(x.table_, boost::unordered::detail::false_type());
1037 : return *this;
1038 : }
1039 :
1040 : #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
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 :
1056 0 : allocator_type get_allocator() const BOOST_NOEXCEPT
1057 : {
1058 0 : return table_.node_alloc();
1059 : }
1060 :
1061 : // iterators
1062 :
1063 695285 : iterator begin() BOOST_NOEXCEPT { return iterator(table_.begin()); }
1064 :
1065 0 : const_iterator begin() const BOOST_NOEXCEPT
1066 : {
1067 0 : return const_iterator(table_.begin());
1068 : }
1069 :
1070 43456296 : iterator end() BOOST_NOEXCEPT { return iterator(); }
1071 :
1072 0 : const_iterator end() const BOOST_NOEXCEPT { return const_iterator(); }
1073 :
1074 : const_iterator cbegin() const BOOST_NOEXCEPT
1075 : {
1076 : return const_iterator(table_.begin());
1077 : }
1078 :
1079 : const_iterator cend() const BOOST_NOEXCEPT { return const_iterator(); }
1080 :
1081 : // size and capacity
1082 :
1083 192 : bool empty() const BOOST_NOEXCEPT { return table_.size_ == 0; }
1084 :
1085 2482929 : 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 :
1093 2448950 : template <class... Args> iterator emplace(BOOST_FWD_REF(Args)... args)
1094 : {
1095 2448950 : return iterator(table_.emplace_equiv(
1096 2448950 : 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 :
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 :
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>
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>
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>
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 :
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>
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>
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>
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, _)
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 :
1246 2448950 : iterator insert(BOOST_RV_REF(value_type) x)
1247 : {
1248 2448950 : return this->emplace(boost::move(x));
1249 : }
1250 :
1251 : template <class P2>
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 :
1260 : iterator insert(const_iterator hint, value_type const& x)
1261 : {
1262 : return this->emplace_hint(hint, x);
1263 : }
1264 :
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>
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 :
1287 : node_type extract(const_iterator position)
1288 : {
1289 : return node_type(
1290 : table_.extract_by_iterator_equiv(position), table_.node_alloc());
1291 : }
1292 :
1293 : node_type extract(const key_type& k)
1294 : {
1295 : return node_type(table_.extract_by_key(k), table_.node_alloc());
1296 : }
1297 :
1298 : iterator insert(BOOST_RV_REF(node_type) np)
1299 : {
1300 : return table_.move_insert_node_type_equiv(np);
1301 : }
1302 :
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")
1323 : void quick_erase(const_iterator it) { erase(it); }
1324 : BOOST_UNORDERED_DEPRECATED("Use erase instead")
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);
1331 54458 : 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 :
1377 0 : size_type bucket_count() const BOOST_NOEXCEPT
1378 : {
1379 : return table_.bucket_count_;
1380 : }
1381 :
1382 : 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 :
1389 : size_type bucket(const key_type& k) const
1390 : {
1391 : return table_.hash_to_bucket(table_.hash(k));
1392 : }
1393 :
1394 : local_iterator begin(size_type n)
1395 : {
1396 : return local_iterator(table_.begin(n), n, table_.bucket_count_);
1397 : }
1398 :
1399 : const_local_iterator begin(size_type n) const
1400 : {
1401 : return const_local_iterator(table_.begin(n), n, table_.bucket_count_);
1402 : }
1403 :
1404 : local_iterator end(size_type) { return local_iterator(); }
1405 :
1406 : const_local_iterator end(size_type) const
1407 : {
1408 : return const_local_iterator();
1409 : }
1410 :
1411 : const_local_iterator cbegin(size_type n) const
1412 : {
1413 : return const_local_iterator(table_.begin(n), n, table_.bucket_count_);
1414 : }
1415 :
1416 : 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;
1424 0 : 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(__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>
1507 1 : unordered_map<K, T, H, P, A>::unordered_map()
1508 : : table_(boost::unordered::detail::default_bucket_count, hasher(),
1509 1 : key_equal(), allocator_type())
1510 : {
1511 0 : }
1512 :
1513 : template <class K, class T, class H, class P, class 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>
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>
1531 0 : unordered_map<K, T, H, P, A>::unordered_map(unordered_map const& other)
1532 0 : : table_(other.table_,
1533 : unordered_map::value_allocator_traits::
1534 0 : select_on_container_copy_construction(other.get_allocator()))
1535 : {
1536 0 : if (other.table_.size_) {
1537 0 : table_.copy_buckets(
1538 : other.table_, boost::unordered::detail::true_type());
1539 : }
1540 0 : }
1541 :
1542 : template <class K, class T, class H, class P, class 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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
1644 356 : unordered_map<K, T, H, P, A>::~unordered_map() BOOST_NOEXCEPT
1645 : {
1646 356 : }
1647 :
1648 : #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1649 :
1650 : template <class K, class T, class H, class P, class A>
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>
1664 : 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>
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>
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
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
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
1720 0 : unordered_map<K, T, H, P, A>::erase(const key_type& k)
1721 : {
1722 0 : 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
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>
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>
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>
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>
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>
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
1786 : 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
1793 : 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
1802 479 : unordered_map<K, T, H, P, A>::find(const key_type& k)
1803 : {
1804 479 : 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
1809 0 : unordered_map<K, T, H, P, A>::find(const key_type& k) const
1810 : {
1811 0 : 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
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
1829 : 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
1838 0 : unordered_map<K, T, H, P, A>::count(const key_type& k) const
1839 : {
1840 0 : 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>
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>
1855 : 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&
1864 80 : unordered_map<K, T, H, P, A>::operator[](const key_type& k)
1865 : {
1866 80 : 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&
1871 0 : unordered_map<K, T, H, P, A>::operator[](BOOST_RV_REF(key_type) k)
1872 : {
1873 0 : 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&
1878 0 : unordered_map<K, T, H, P, A>::at(const key_type& k)
1879 : {
1880 0 : if (table_.size_) {
1881 0 : node_pointer n = table_.find_node(k);
1882 0 : if (n)
1883 0 : return n->value().second;
1884 : }
1885 :
1886 0 : 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&
1892 : 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
1906 : 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>
1914 : 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>
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>
1928 0 : void unordered_map<K, T, H, P, A>::rehash(size_type n)
1929 : {
1930 0 : table_.rehash(n);
1931 : }
1932 :
1933 : template <class K, class T, class H, class P, class A>
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>
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(__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>
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(__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>
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(__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>
1983 0 : unordered_multimap<K, T, H, P, A>::unordered_multimap()
1984 : : table_(boost::unordered::detail::default_bucket_count, hasher(),
1985 0 : key_equal(), allocator_type())
1986 : {
1987 0 : }
1988 :
1989 : template <class K, class T, class H, class P, class A>
1990 304102 : 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 304102 : : table_(n, hf, eql, a)
1993 : {
1994 : }
1995 :
1996 : template <class K, class T, class H, class P, class A>
1997 : template <class InputIt>
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>
2007 0 : unordered_multimap<K, T, H, P, A>::unordered_multimap(
2008 : unordered_multimap const& other)
2009 0 : : table_(other.table_,
2010 : unordered_multimap::value_allocator_traits::
2011 0 : select_on_container_copy_construction(other.get_allocator()))
2012 : {
2013 0 : if (other.table_.size_) {
2014 0 : table_.copy_buckets(
2015 : other.table_, boost::unordered::detail::false_type());
2016 : }
2017 0 : }
2018 :
2019 : template <class K, class T, class H, class P, class 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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
2122 54458 : unordered_multimap<K, T, H, P, A>::~unordered_multimap() BOOST_NOEXCEPT
2123 : {
2124 54458 : }
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>::
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
2143 : 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>
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>
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
2174 26493 : unordered_multimap<K, T, H, P, A>::erase(iterator position)
2175 : {
2176 26493 : node_pointer node = table::get_node(position);
2177 26493 : BOOST_ASSERT(node);
2178 26493 : node_pointer next = table::next_node(node);
2179 26493 : table_.erase_nodes_equiv(node, next);
2180 26493 : 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
2185 0 : unordered_multimap<K, T, H, P, A>::erase(const_iterator position)
2186 : {
2187 0 : node_pointer node = table::get_node(position);
2188 0 : BOOST_ASSERT(node);
2189 0 : node_pointer next = table::next_node(node);
2190 0 : table_.erase_nodes_equiv(node, next);
2191 0 : 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
2196 0 : unordered_multimap<K, T, H, P, A>::erase(const key_type& k)
2197 : {
2198 0 : 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
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>
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
2226 : 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
2233 18682100 : unordered_multimap<K, T, H, P, A>::key_eq() const
2234 : {
2235 18682100 : return table_.key_eq();
2236 : }
2237 :
2238 : template <class K, class T, class H, class P, class A>
2239 : template <typename H2, typename P2>
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>
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>
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>
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
2286 24556122 : unordered_multimap<K, T, H, P, A>::find(const key_type& k)
2287 : {
2288 24639744 : 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
2293 0 : unordered_multimap<K, T, H, P, A>::find(const key_type& k) const
2294 : {
2295 0 : 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
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
2313 : 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
2322 91948 : unordered_multimap<K, T, H, P, A>::count(const key_type& k) const
2323 : {
2324 91948 : node_pointer n = table_.find_node(k);
2325 133300 : 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>
2331 10615300 : unordered_multimap<K, T, H, P, A>::equal_range(const key_type& k)
2332 : {
2333 10615300 : node_pointer n = table_.find_node(k);
2334 10615300 : return std::make_pair(
2335 8226120 : 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>
2341 0 : unordered_multimap<K, T, H, P, A>::equal_range(const key_type& k) const
2342 : {
2343 0 : node_pointer n = table_.find_node(k);
2344 0 : return std::make_pair(
2345 0 : 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
2350 0 : unordered_multimap<K, T, H, P, A>::bucket_size(size_type n) const
2351 : {
2352 0 : return table_.bucket_size(n);
2353 : }
2354 :
2355 : // hash policy
2356 :
2357 : template <class K, class T, class H, class P, class A>
2358 0 : float unordered_multimap<K, T, H, P, A>::load_factor() const BOOST_NOEXCEPT
2359 : {
2360 0 : BOOST_ASSERT(table_.bucket_count_ != 0);
2361 0 : return static_cast<float>(table_.size_) /
2362 0 : static_cast<float>(table_.bucket_count_);
2363 : }
2364 :
2365 : template <class K, class T, class H, class P, class A>
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>
2373 0 : void unordered_multimap<K, T, H, P, A>::rehash(size_type n)
2374 : {
2375 0 : table_.rehash(n);
2376 : }
2377 :
2378 : template <class K, class T, class H, class P, class A>
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>
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(__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>
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(__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>
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(__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 :
2455 : node_handle_map(node_pointer ptr, allocator_type const& a)
2456 : : ptr_(ptr), alloc_(a)
2457 : {
2458 : }
2459 :
2460 : public:
2461 : BOOST_CONSTEXPR node_handle_map() BOOST_NOEXCEPT : ptr_(), alloc_() {}
2462 :
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 :
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 :
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 :
2504 : key_type& key() const
2505 : {
2506 : return const_cast<key_type&>(ptr_->value().first);
2507 : }
2508 :
2509 : mapped_type& mapped() const { return ptr_->value().second; }
2510 :
2511 : 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 :
2517 : bool empty() const BOOST_NOEXCEPT { return ptr_ ? 0 : 1; }
2518 :
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>
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 :
2556 : insert_return_type_map() : inserted(false), position(), node() {}
2557 :
2558 : 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 :
2565 : 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>
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
|
