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