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