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