2 // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
3 // Copyright (C) 2005-2011 Daniel James.
4 // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7 // See http://www.boost.org/libs/unordered for documentation
9 #ifndef BOOST_UNORDERED_UNORDERED_SET_HPP_INCLUDED
10 #define BOOST_UNORDERED_UNORDERED_SET_HPP_INCLUDED
12 #include <boost/config.hpp>
13 #if defined(BOOST_HAS_PRAGMA_ONCE)
17 #include <boost/unordered/detail/set.hpp>
18 #include <boost/functional/hash.hpp>
19 #include <boost/move/move.hpp>
21 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
22 #include <initializer_list>
25 #if defined(BOOST_MSVC)
27 #if BOOST_MSVC >= 1400
28 #pragma warning(disable:4396) //the inline specifier cannot be used when a
29 // friend declaration refers to a specialization
30 // of a function template
38 template <class T, class H, class P, class A>
41 #if defined(BOOST_UNORDERED_USE_MOVE)
42 BOOST_COPYABLE_AND_MOVABLE(unordered_set)
50 typedef A allocator_type;
54 typedef boost::unordered::detail::set<A, T, H, P> types;
55 typedef typename types::traits allocator_traits;
56 typedef typename types::table table;
60 typedef typename allocator_traits::pointer pointer;
61 typedef typename allocator_traits::const_pointer const_pointer;
63 typedef value_type& reference;
64 typedef value_type const& const_reference;
66 typedef std::size_t size_type;
67 typedef std::ptrdiff_t difference_type;
69 typedef typename table::cl_iterator const_local_iterator;
70 typedef typename table::l_iterator local_iterator;
71 typedef typename table::c_iterator const_iterator;
72 typedef typename table::iterator iterator;
84 explicit unordered_set(
86 const hasher& = hasher(),
87 const key_equal& = key_equal(),
88 const allocator_type& = allocator_type());
90 explicit unordered_set(
92 const allocator_type&);
94 explicit unordered_set(
97 const allocator_type&);
99 explicit unordered_set(allocator_type const&);
101 template <class InputIt>
102 unordered_set(InputIt, InputIt);
104 template <class InputIt>
108 const hasher& = hasher(),
109 const key_equal& = key_equal());
111 template <class InputIt>
117 const allocator_type&);
119 template <class InputIt>
124 const allocator_type&);
126 template <class InputIt>
130 const allocator_type&);
132 // copy/move constructors
134 unordered_set(unordered_set const&);
136 unordered_set(unordered_set const&, allocator_type const&);
137 unordered_set(BOOST_RV_REF(unordered_set), allocator_type const&);
139 #if defined(BOOST_UNORDERED_USE_MOVE)
140 unordered_set(BOOST_RV_REF(unordered_set) other)
141 BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
142 : table_(other.table_, boost::unordered::detail::move_tag())
145 #elif !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
146 unordered_set(unordered_set&& other)
147 BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
148 : table_(other.table_, boost::unordered::detail::move_tag())
153 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
155 std::initializer_list<value_type>,
156 size_type = boost::unordered::detail::default_bucket_count,
157 const hasher& = hasher(),
158 const key_equal&l = key_equal(),
159 const allocator_type& = allocator_type());
161 std::initializer_list<value_type>,
164 const allocator_type&);
166 std::initializer_list<value_type>,
168 const allocator_type&);
173 ~unordered_set() BOOST_NOEXCEPT;
177 #if defined(BOOST_UNORDERED_USE_MOVE)
178 unordered_set& operator=(BOOST_COPY_ASSIGN_REF(unordered_set) x)
180 table_.assign(x.table_);
184 unordered_set& operator=(BOOST_RV_REF(unordered_set) x)
186 table_.move_assign(x.table_);
190 unordered_set& operator=(unordered_set const& x)
192 table_.assign(x.table_);
196 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
197 unordered_set& operator=(unordered_set&& x)
199 table_.move_assign(x.table_);
205 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
206 unordered_set& operator=(std::initializer_list<value_type>);
209 allocator_type get_allocator() const BOOST_NOEXCEPT
211 return table_.node_alloc();
216 bool empty() const BOOST_NOEXCEPT
218 return table_.size_ == 0;
221 size_type size() const BOOST_NOEXCEPT
226 size_type max_size() const BOOST_NOEXCEPT;
230 iterator begin() BOOST_NOEXCEPT
232 return iterator(table_.begin());
235 const_iterator begin() const BOOST_NOEXCEPT
237 return const_iterator(table_.begin());
240 iterator end() BOOST_NOEXCEPT
245 const_iterator end() const BOOST_NOEXCEPT
247 return const_iterator();
250 const_iterator cbegin() const BOOST_NOEXCEPT
252 return const_iterator(table_.begin());
255 const_iterator cend() const BOOST_NOEXCEPT
257 return const_iterator();
262 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
263 template <class... Args>
264 std::pair<iterator, bool> emplace(BOOST_FWD_REF(Args)... args)
266 return table_.emplace(boost::forward<Args>(args)...);
269 template <class... Args>
270 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
272 return table_.emplace_hint(hint, boost::forward<Args>(args)...);
276 #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
278 // 0 argument emplace requires special treatment in case
279 // the container is instantiated with a value type that
280 // doesn't have a default constructor.
282 std::pair<iterator, bool> emplace(
283 boost::unordered::detail::empty_emplace
284 = boost::unordered::detail::empty_emplace(),
285 value_type v = value_type())
287 return this->emplace(boost::move(v));
290 iterator emplace_hint(const_iterator hint,
291 boost::unordered::detail::empty_emplace
292 = boost::unordered::detail::empty_emplace(),
293 value_type v = value_type()
296 return this->emplace_hint(hint, boost::move(v));
301 template <typename A0>
302 std::pair<iterator, bool> emplace(BOOST_FWD_REF(A0) a0)
304 return table_.emplace(
305 boost::unordered::detail::create_emplace_args(
306 boost::forward<A0>(a0))
310 template <typename A0>
311 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0)
313 return table_.emplace_hint(hint,
314 boost::unordered::detail::create_emplace_args(
315 boost::forward<A0>(a0))
319 template <typename A0, typename A1>
320 std::pair<iterator, bool> emplace(
321 BOOST_FWD_REF(A0) a0,
322 BOOST_FWD_REF(A1) a1)
324 return table_.emplace(
325 boost::unordered::detail::create_emplace_args(
326 boost::forward<A0>(a0),
327 boost::forward<A1>(a1))
331 template <typename A0, typename A1>
332 iterator emplace_hint(const_iterator hint,
333 BOOST_FWD_REF(A0) a0,
334 BOOST_FWD_REF(A1) a1)
336 return table_.emplace_hint(hint,
337 boost::unordered::detail::create_emplace_args(
338 boost::forward<A0>(a0),
339 boost::forward<A1>(a1))
343 template <typename A0, typename A1, typename A2>
344 std::pair<iterator, bool> emplace(
345 BOOST_FWD_REF(A0) a0,
346 BOOST_FWD_REF(A1) a1,
347 BOOST_FWD_REF(A2) a2)
349 return table_.emplace(
350 boost::unordered::detail::create_emplace_args(
351 boost::forward<A0>(a0),
352 boost::forward<A1>(a1),
353 boost::forward<A2>(a2))
357 template <typename A0, typename A1, typename A2>
358 iterator emplace_hint(const_iterator hint,
359 BOOST_FWD_REF(A0) a0,
360 BOOST_FWD_REF(A1) a1,
361 BOOST_FWD_REF(A2) a2)
363 return table_.emplace_hint(hint,
364 boost::unordered::detail::create_emplace_args(
365 boost::forward<A0>(a0),
366 boost::forward<A1>(a1),
367 boost::forward<A2>(a2))
371 #define BOOST_UNORDERED_EMPLACE(z, n, _) \
373 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A) \
375 std::pair<iterator, bool> emplace( \
376 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a) \
379 return table_.emplace( \
380 boost::unordered::detail::create_emplace_args( \
381 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, \
387 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A) \
389 iterator emplace_hint( \
390 const_iterator hint, \
391 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a) \
394 return table_.emplace_hint(hint, \
395 boost::unordered::detail::create_emplace_args( \
396 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, \
401 BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT,
402 BOOST_UNORDERED_EMPLACE, _)
404 #undef BOOST_UNORDERED_EMPLACE
408 std::pair<iterator, bool> insert(value_type const& x)
410 return this->emplace(x);
413 std::pair<iterator, bool> insert(BOOST_UNORDERED_RV_REF(value_type) x)
415 return this->emplace(boost::move(x));
418 iterator insert(const_iterator hint, value_type const& x)
420 return this->emplace_hint(hint, x);
423 iterator insert(const_iterator hint,
424 BOOST_UNORDERED_RV_REF(value_type) x)
426 return this->emplace_hint(hint, boost::move(x));
429 template <class InputIt> void insert(InputIt, InputIt);
431 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
432 void insert(std::initializer_list<value_type>);
435 iterator erase(const_iterator);
436 size_type erase(const key_type&);
437 iterator erase(const_iterator, const_iterator);
438 void quick_erase(const_iterator it) { erase(it); }
439 void erase_return_void(const_iterator it) { erase(it); }
442 void swap(unordered_set&);
446 hasher hash_function() const;
447 key_equal key_eq() const;
451 const_iterator find(const key_type&) const;
453 template <class CompatibleKey, class CompatibleHash,
454 class CompatiblePredicate>
456 CompatibleKey const&,
457 CompatibleHash const&,
458 CompatiblePredicate const&) const;
460 size_type count(const key_type&) const;
462 std::pair<const_iterator, const_iterator>
463 equal_range(const key_type&) const;
467 size_type bucket_count() const BOOST_NOEXCEPT
469 return table_.bucket_count_;
472 size_type max_bucket_count() const BOOST_NOEXCEPT
474 return table_.max_bucket_count();
477 size_type bucket_size(size_type) const;
479 size_type bucket(const key_type& k) const
481 return table_.hash_to_bucket(table_.hash(k));
484 local_iterator begin(size_type n)
486 return local_iterator(
487 table_.begin(n), n, table_.bucket_count_);
490 const_local_iterator begin(size_type n) const
492 return const_local_iterator(
493 table_.begin(n), n, table_.bucket_count_);
496 local_iterator end(size_type)
498 return local_iterator();
501 const_local_iterator end(size_type) const
503 return const_local_iterator();
506 const_local_iterator cbegin(size_type n) const
508 return const_local_iterator(
509 table_.begin(n), n, table_.bucket_count_);
512 const_local_iterator cend(size_type) const
514 return const_local_iterator();
519 float max_load_factor() const BOOST_NOEXCEPT
524 float load_factor() const BOOST_NOEXCEPT;
525 void max_load_factor(float) BOOST_NOEXCEPT;
526 void rehash(size_type);
527 void reserve(size_type);
529 #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
530 friend bool operator==<T,H,P,A>(
531 unordered_set const&, unordered_set const&);
532 friend bool operator!=<T,H,P,A>(
533 unordered_set const&, unordered_set const&);
535 }; // class template unordered_set
537 template <class T, class H, class P, class A>
538 class unordered_multiset
540 #if defined(BOOST_UNORDERED_USE_MOVE)
541 BOOST_COPYABLE_AND_MOVABLE(unordered_multiset)
546 typedef T value_type;
549 typedef A allocator_type;
553 typedef boost::unordered::detail::multiset<A, T, H, P> types;
554 typedef typename types::traits allocator_traits;
555 typedef typename types::table table;
559 typedef typename allocator_traits::pointer pointer;
560 typedef typename allocator_traits::const_pointer const_pointer;
562 typedef value_type& reference;
563 typedef value_type const& const_reference;
565 typedef std::size_t size_type;
566 typedef std::ptrdiff_t difference_type;
568 typedef typename table::cl_iterator const_local_iterator;
569 typedef typename table::l_iterator local_iterator;
570 typedef typename table::c_iterator const_iterator;
571 typedef typename table::iterator iterator;
581 unordered_multiset();
583 explicit unordered_multiset(
585 const hasher& = hasher(),
586 const key_equal& = key_equal(),
587 const allocator_type& = allocator_type());
589 explicit unordered_multiset(
591 const allocator_type&);
593 explicit unordered_multiset(
596 const allocator_type&);
598 explicit unordered_multiset(allocator_type const&);
600 template <class InputIt>
601 unordered_multiset(InputIt, InputIt);
603 template <class InputIt>
607 const hasher& = hasher(),
608 const key_equal& = key_equal());
610 template <class InputIt>
616 const allocator_type&);
618 template <class InputIt>
623 const allocator_type&);
625 template <class InputIt>
629 const allocator_type&);
631 // copy/move constructors
633 unordered_multiset(unordered_multiset const&);
635 unordered_multiset(unordered_multiset const&, allocator_type const&);
636 unordered_multiset(BOOST_RV_REF(unordered_multiset), allocator_type const&);
638 #if defined(BOOST_UNORDERED_USE_MOVE)
639 unordered_multiset(BOOST_RV_REF(unordered_multiset) other)
640 BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
641 : table_(other.table_, boost::unordered::detail::move_tag())
644 #elif !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
645 unordered_multiset(unordered_multiset&& other)
646 BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
647 : table_(other.table_, boost::unordered::detail::move_tag())
652 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
654 std::initializer_list<value_type>,
655 size_type = boost::unordered::detail::default_bucket_count,
656 const hasher& = hasher(),
657 const key_equal&l = key_equal(),
658 const allocator_type& = allocator_type());
660 std::initializer_list<value_type>,
663 const allocator_type&);
665 std::initializer_list<value_type>,
667 const allocator_type&);
672 ~unordered_multiset() BOOST_NOEXCEPT;
676 #if defined(BOOST_UNORDERED_USE_MOVE)
677 unordered_multiset& operator=(
678 BOOST_COPY_ASSIGN_REF(unordered_multiset) x)
680 table_.assign(x.table_);
684 unordered_multiset& operator=(BOOST_RV_REF(unordered_multiset) x)
686 table_.move_assign(x.table_);
690 unordered_multiset& operator=(unordered_multiset const& x)
692 table_.assign(x.table_);
696 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
697 unordered_multiset& operator=(unordered_multiset&& x)
699 table_.move_assign(x.table_);
705 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
706 unordered_multiset& operator=(std::initializer_list<value_type>);
709 allocator_type get_allocator() const BOOST_NOEXCEPT
711 return table_.node_alloc();
716 bool empty() const BOOST_NOEXCEPT
718 return table_.size_ == 0;
721 size_type size() const BOOST_NOEXCEPT
726 size_type max_size() const BOOST_NOEXCEPT;
730 iterator begin() BOOST_NOEXCEPT
732 return iterator(table_.begin());
735 const_iterator begin() const BOOST_NOEXCEPT
737 return const_iterator(table_.begin());
740 iterator end() BOOST_NOEXCEPT
745 const_iterator end() const BOOST_NOEXCEPT
747 return const_iterator();
750 const_iterator cbegin() const BOOST_NOEXCEPT
752 return const_iterator(table_.begin());
755 const_iterator cend() const BOOST_NOEXCEPT
757 return const_iterator();
762 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
763 template <class... Args>
764 iterator emplace(BOOST_FWD_REF(Args)... args)
766 return table_.emplace(boost::forward<Args>(args)...);
769 template <class... Args>
770 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
772 return table_.emplace_hint(hint, boost::forward<Args>(args)...);
776 #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
778 // 0 argument emplace requires special treatment in case
779 // the container is instantiated with a value type that
780 // doesn't have a default constructor.
783 boost::unordered::detail::empty_emplace
784 = boost::unordered::detail::empty_emplace(),
785 value_type v = value_type())
787 return this->emplace(boost::move(v));
790 iterator emplace_hint(const_iterator hint,
791 boost::unordered::detail::empty_emplace
792 = boost::unordered::detail::empty_emplace(),
793 value_type v = value_type()
796 return this->emplace_hint(hint, boost::move(v));
801 template <typename A0>
802 iterator emplace(BOOST_FWD_REF(A0) a0)
804 return table_.emplace(
805 boost::unordered::detail::create_emplace_args(
806 boost::forward<A0>(a0))
810 template <typename A0>
811 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0)
813 return table_.emplace_hint(hint,
814 boost::unordered::detail::create_emplace_args(
815 boost::forward<A0>(a0))
819 template <typename A0, typename A1>
821 BOOST_FWD_REF(A0) a0,
822 BOOST_FWD_REF(A1) a1)
824 return table_.emplace(
825 boost::unordered::detail::create_emplace_args(
826 boost::forward<A0>(a0),
827 boost::forward<A1>(a1))
831 template <typename A0, typename A1>
832 iterator emplace_hint(const_iterator hint,
833 BOOST_FWD_REF(A0) a0,
834 BOOST_FWD_REF(A1) a1)
836 return table_.emplace_hint(hint,
837 boost::unordered::detail::create_emplace_args(
838 boost::forward<A0>(a0),
839 boost::forward<A1>(a1))
843 template <typename A0, typename A1, typename A2>
845 BOOST_FWD_REF(A0) a0,
846 BOOST_FWD_REF(A1) a1,
847 BOOST_FWD_REF(A2) a2)
849 return table_.emplace(
850 boost::unordered::detail::create_emplace_args(
851 boost::forward<A0>(a0),
852 boost::forward<A1>(a1),
853 boost::forward<A2>(a2))
857 template <typename A0, typename A1, typename A2>
858 iterator emplace_hint(const_iterator hint,
859 BOOST_FWD_REF(A0) a0,
860 BOOST_FWD_REF(A1) a1,
861 BOOST_FWD_REF(A2) a2)
863 return table_.emplace_hint(hint,
864 boost::unordered::detail::create_emplace_args(
865 boost::forward<A0>(a0),
866 boost::forward<A1>(a1),
867 boost::forward<A2>(a2))
871 #define BOOST_UNORDERED_EMPLACE(z, n, _) \
873 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A) \
876 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a) \
879 return table_.emplace( \
880 boost::unordered::detail::create_emplace_args( \
881 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, \
887 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A) \
889 iterator emplace_hint( \
890 const_iterator hint, \
891 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a) \
894 return table_.emplace_hint(hint, \
895 boost::unordered::detail::create_emplace_args( \
896 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, \
901 BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT,
902 BOOST_UNORDERED_EMPLACE, _)
904 #undef BOOST_UNORDERED_EMPLACE
908 iterator insert(value_type const& x)
910 return this->emplace(x);
913 iterator insert(BOOST_UNORDERED_RV_REF(value_type) x)
915 return this->emplace(boost::move(x));
918 iterator insert(const_iterator hint, value_type const& x)
920 return this->emplace_hint(hint, x);
923 iterator insert(const_iterator hint,
924 BOOST_UNORDERED_RV_REF(value_type) x)
926 return this->emplace_hint(hint, boost::move(x));
929 template <class InputIt> void insert(InputIt, InputIt);
931 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
932 void insert(std::initializer_list<value_type>);
935 iterator erase(const_iterator);
936 size_type erase(const key_type&);
937 iterator erase(const_iterator, const_iterator);
938 void quick_erase(const_iterator it) { erase(it); }
939 void erase_return_void(const_iterator it) { erase(it); }
942 void swap(unordered_multiset&);
946 hasher hash_function() const;
947 key_equal key_eq() const;
951 const_iterator find(const key_type&) const;
953 template <class CompatibleKey, class CompatibleHash,
954 class CompatiblePredicate>
956 CompatibleKey const&,
957 CompatibleHash const&,
958 CompatiblePredicate const&) const;
960 size_type count(const key_type&) const;
962 std::pair<const_iterator, const_iterator>
963 equal_range(const key_type&) const;
967 size_type bucket_count() const BOOST_NOEXCEPT
969 return table_.bucket_count_;
972 size_type max_bucket_count() const BOOST_NOEXCEPT
974 return table_.max_bucket_count();
977 size_type bucket_size(size_type) const;
979 size_type bucket(const key_type& k) const
981 return table_.hash_to_bucket(table_.hash(k));
984 local_iterator begin(size_type n)
986 return local_iterator(
987 table_.begin(n), n, table_.bucket_count_);
990 const_local_iterator begin(size_type n) const
992 return const_local_iterator(
993 table_.begin(n), n, table_.bucket_count_);
996 local_iterator end(size_type)
998 return local_iterator();
1001 const_local_iterator end(size_type) const
1003 return const_local_iterator();
1006 const_local_iterator cbegin(size_type n) const
1008 return const_local_iterator(
1009 table_.begin(n), n, table_.bucket_count_);
1012 const_local_iterator cend(size_type) const
1014 return const_local_iterator();
1019 float max_load_factor() const BOOST_NOEXCEPT
1024 float load_factor() const BOOST_NOEXCEPT;
1025 void max_load_factor(float) BOOST_NOEXCEPT;
1026 void rehash(size_type);
1027 void reserve(size_type);
1029 #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
1030 friend bool operator==<T,H,P,A>(
1031 unordered_multiset const&, unordered_multiset const&);
1032 friend bool operator!=<T,H,P,A>(
1033 unordered_multiset const&, unordered_multiset const&);
1035 }; // class template unordered_multiset
1037 ////////////////////////////////////////////////////////////////////////////////
1039 template <class T, class H, class P, class A>
1040 unordered_set<T,H,P,A>::unordered_set()
1041 : table_(boost::unordered::detail::default_bucket_count, hasher(),
1042 key_equal(), allocator_type())
1046 template <class T, class H, class P, class A>
1047 unordered_set<T,H,P,A>::unordered_set(
1048 size_type n, const hasher &hf, const key_equal &eql,
1049 const allocator_type &a)
1050 : table_(n, hf, eql, a)
1054 template <class T, class H, class P, class A>
1055 unordered_set<T,H,P,A>::unordered_set(
1056 size_type n, const allocator_type &a)
1057 : table_(n, hasher(), key_equal(), a)
1061 template <class T, class H, class P, class A>
1062 unordered_set<T,H,P,A>::unordered_set(
1063 size_type n, const hasher &hf, const allocator_type &a)
1064 : table_(n, hf, key_equal(), a)
1068 template <class T, class H, class P, class A>
1069 unordered_set<T,H,P,A>::unordered_set(allocator_type const& a)
1070 : table_(boost::unordered::detail::default_bucket_count,
1071 hasher(), key_equal(), a)
1075 template <class T, class H, class P, class A>
1076 unordered_set<T,H,P,A>::unordered_set(
1077 unordered_set const& other, allocator_type const& a)
1078 : table_(other.table_, a)
1082 template <class T, class H, class P, class A>
1083 template <class InputIt>
1084 unordered_set<T,H,P,A>::unordered_set(InputIt f, InputIt l)
1085 : table_(boost::unordered::detail::initial_size(f, l),
1086 hasher(), key_equal(), allocator_type())
1088 table_.insert_range(f, l);
1091 template <class T, class H, class P, class A>
1092 template <class InputIt>
1093 unordered_set<T,H,P,A>::unordered_set(
1094 InputIt f, InputIt l,
1097 const key_equal &eql)
1098 : table_(boost::unordered::detail::initial_size(f, l, n),
1099 hf, eql, allocator_type())
1101 table_.insert_range(f, l);
1104 template <class T, class H, class P, class A>
1105 template <class InputIt>
1106 unordered_set<T,H,P,A>::unordered_set(
1107 InputIt f, InputIt l,
1110 const key_equal &eql,
1111 const allocator_type &a)
1112 : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
1114 table_.insert_range(f, l);
1117 template <class T, class H, class P, class A>
1118 template <class InputIt>
1119 unordered_set<T,H,P,A>::unordered_set(
1120 InputIt f, InputIt l,
1123 const allocator_type &a)
1124 : table_(boost::unordered::detail::initial_size(f, l, n),
1127 table_.insert_range(f, l);
1130 template <class T, class H, class P, class A>
1131 template <class InputIt>
1132 unordered_set<T,H,P,A>::unordered_set(
1133 InputIt f, InputIt l,
1135 const allocator_type &a)
1136 : table_(boost::unordered::detail::initial_size(f, l, n),
1137 hasher(), key_equal(), a)
1139 table_.insert_range(f, l);
1142 template <class T, class H, class P, class A>
1143 unordered_set<T,H,P,A>::~unordered_set() BOOST_NOEXCEPT {}
1145 template <class T, class H, class P, class A>
1146 unordered_set<T,H,P,A>::unordered_set(
1147 unordered_set const& other)
1148 : table_(other.table_)
1152 template <class T, class H, class P, class A>
1153 unordered_set<T,H,P,A>::unordered_set(
1154 BOOST_RV_REF(unordered_set) other, allocator_type const& a)
1155 : table_(other.table_, a, boost::unordered::detail::move_tag())
1159 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1161 template <class T, class H, class P, class A>
1162 unordered_set<T,H,P,A>::unordered_set(
1163 std::initializer_list<value_type> list, size_type n,
1164 const hasher &hf, const key_equal &eql, const allocator_type &a)
1166 boost::unordered::detail::initial_size(
1167 list.begin(), list.end(), n),
1170 table_.insert_range(list.begin(), list.end());
1173 template <class T, class H, class P, class A>
1174 unordered_set<T,H,P,A>::unordered_set(
1175 std::initializer_list<value_type> list, size_type n,
1176 const hasher &hf, const allocator_type &a)
1178 boost::unordered::detail::initial_size(
1179 list.begin(), list.end(), n),
1182 table_.insert_range(list.begin(), list.end());
1185 template <class T, class H, class P, class A>
1186 unordered_set<T,H,P,A>::unordered_set(
1187 std::initializer_list<value_type> list, size_type n,
1188 const allocator_type &a)
1190 boost::unordered::detail::initial_size(
1191 list.begin(), list.end(), n),
1192 hasher(), key_equal(), a)
1194 table_.insert_range(list.begin(), list.end());
1197 template <class T, class H, class P, class A>
1198 unordered_set<T,H,P,A>& unordered_set<T,H,P,A>::operator=(
1199 std::initializer_list<value_type> list)
1202 table_.insert_range(list.begin(), list.end());
1208 // size and capacity
1210 template <class T, class H, class P, class A>
1211 std::size_t unordered_set<T,H,P,A>::max_size() const BOOST_NOEXCEPT
1213 return table_.max_size();
1218 template <class T, class H, class P, class A>
1219 template <class InputIt>
1220 void unordered_set<T,H,P,A>::insert(InputIt first, InputIt last)
1222 table_.insert_range(first, last);
1225 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1226 template <class T, class H, class P, class A>
1227 void unordered_set<T,H,P,A>::insert(
1228 std::initializer_list<value_type> list)
1230 table_.insert_range(list.begin(), list.end());
1234 template <class T, class H, class P, class A>
1235 typename unordered_set<T,H,P,A>::iterator
1236 unordered_set<T,H,P,A>::erase(const_iterator position)
1238 return table_.erase(position);
1241 template <class T, class H, class P, class A>
1242 typename unordered_set<T,H,P,A>::size_type
1243 unordered_set<T,H,P,A>::erase(const key_type& k)
1245 return table_.erase_key(k);
1248 template <class T, class H, class P, class A>
1249 typename unordered_set<T,H,P,A>::iterator
1250 unordered_set<T,H,P,A>::erase(
1251 const_iterator first, const_iterator last)
1253 return table_.erase_range(first, last);
1256 template <class T, class H, class P, class A>
1257 void unordered_set<T,H,P,A>::clear()
1262 template <class T, class H, class P, class A>
1263 void unordered_set<T,H,P,A>::swap(unordered_set& other)
1265 table_.swap(other.table_);
1270 template <class T, class H, class P, class A>
1271 typename unordered_set<T,H,P,A>::hasher
1272 unordered_set<T,H,P,A>::hash_function() const
1274 return table_.hash_function();
1277 template <class T, class H, class P, class A>
1278 typename unordered_set<T,H,P,A>::key_equal
1279 unordered_set<T,H,P,A>::key_eq() const
1281 return table_.key_eq();
1286 template <class T, class H, class P, class A>
1287 typename unordered_set<T,H,P,A>::const_iterator
1288 unordered_set<T,H,P,A>::find(const key_type& k) const
1290 return const_iterator(table_.find_node(k));
1293 template <class T, class H, class P, class A>
1294 template <class CompatibleKey, class CompatibleHash,
1295 class CompatiblePredicate>
1296 typename unordered_set<T,H,P,A>::const_iterator
1297 unordered_set<T,H,P,A>::find(
1298 CompatibleKey const& k,
1299 CompatibleHash const& hash,
1300 CompatiblePredicate const& eq) const
1302 return const_iterator(table_.generic_find_node(k, hash, eq));
1305 template <class T, class H, class P, class A>
1306 typename unordered_set<T,H,P,A>::size_type
1307 unordered_set<T,H,P,A>::count(const key_type& k) const
1309 return table_.count(k);
1312 template <class T, class H, class P, class A>
1314 typename unordered_set<T,H,P,A>::const_iterator,
1315 typename unordered_set<T,H,P,A>::const_iterator>
1316 unordered_set<T,H,P,A>::equal_range(const key_type& k) const
1318 return table_.equal_range(k);
1321 template <class T, class H, class P, class A>
1322 typename unordered_set<T,H,P,A>::size_type
1323 unordered_set<T,H,P,A>::bucket_size(size_type n) const
1325 return table_.bucket_size(n);
1330 template <class T, class H, class P, class A>
1331 float unordered_set<T,H,P,A>::load_factor() const BOOST_NOEXCEPT
1333 return table_.load_factor();
1336 template <class T, class H, class P, class A>
1337 void unordered_set<T,H,P,A>::max_load_factor(float m) BOOST_NOEXCEPT
1339 table_.max_load_factor(m);
1342 template <class T, class H, class P, class A>
1343 void unordered_set<T,H,P,A>::rehash(size_type n)
1348 template <class T, class H, class P, class A>
1349 void unordered_set<T,H,P,A>::reserve(size_type n)
1354 template <class T, class H, class P, class A>
1355 inline bool operator==(
1356 unordered_set<T,H,P,A> const& m1,
1357 unordered_set<T,H,P,A> const& m2)
1359 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1360 struct dummy { unordered_set<T,H,P,A> x; };
1362 return m1.table_.equals(m2.table_);
1365 template <class T, class H, class P, class A>
1366 inline bool operator!=(
1367 unordered_set<T,H,P,A> const& m1,
1368 unordered_set<T,H,P,A> const& m2)
1370 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1371 struct dummy { unordered_set<T,H,P,A> x; };
1373 return !m1.table_.equals(m2.table_);
1376 template <class T, class H, class P, class A>
1378 unordered_set<T,H,P,A> &m1,
1379 unordered_set<T,H,P,A> &m2)
1381 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1382 struct dummy { unordered_set<T,H,P,A> x; };
1387 ////////////////////////////////////////////////////////////////////////////////
1389 template <class T, class H, class P, class A>
1390 unordered_multiset<T,H,P,A>::unordered_multiset()
1391 : table_(boost::unordered::detail::default_bucket_count, hasher(),
1392 key_equal(), allocator_type())
1396 template <class T, class H, class P, class A>
1397 unordered_multiset<T,H,P,A>::unordered_multiset(
1398 size_type n, const hasher &hf, const key_equal &eql,
1399 const allocator_type &a)
1400 : table_(n, hf, eql, a)
1404 template <class T, class H, class P, class A>
1405 unordered_multiset<T,H,P,A>::unordered_multiset(
1406 size_type n, const allocator_type &a)
1407 : table_(n, hasher(), key_equal(), a)
1411 template <class T, class H, class P, class A>
1412 unordered_multiset<T,H,P,A>::unordered_multiset(
1413 size_type n, const hasher &hf, const allocator_type &a)
1414 : table_(n, hf, key_equal(), a)
1418 template <class T, class H, class P, class A>
1419 unordered_multiset<T,H,P,A>::unordered_multiset(allocator_type const& a)
1420 : table_(boost::unordered::detail::default_bucket_count,
1421 hasher(), key_equal(), a)
1425 template <class T, class H, class P, class A>
1426 unordered_multiset<T,H,P,A>::unordered_multiset(
1427 unordered_multiset const& other, allocator_type const& a)
1428 : table_(other.table_, a)
1432 template <class T, class H, class P, class A>
1433 template <class InputIt>
1434 unordered_multiset<T,H,P,A>::unordered_multiset(InputIt f, InputIt l)
1435 : table_(boost::unordered::detail::initial_size(f, l),
1436 hasher(), key_equal(), allocator_type())
1438 table_.insert_range(f, l);
1441 template <class T, class H, class P, class A>
1442 template <class InputIt>
1443 unordered_multiset<T,H,P,A>::unordered_multiset(
1444 InputIt f, InputIt l,
1447 const key_equal &eql)
1448 : table_(boost::unordered::detail::initial_size(f, l, n),
1449 hf, eql, allocator_type())
1451 table_.insert_range(f, l);
1454 template <class T, class H, class P, class A>
1455 template <class InputIt>
1456 unordered_multiset<T,H,P,A>::unordered_multiset(
1457 InputIt f, InputIt l,
1460 const key_equal &eql,
1461 const allocator_type &a)
1462 : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
1464 table_.insert_range(f, l);
1467 template <class T, class H, class P, class A>
1468 template <class InputIt>
1469 unordered_multiset<T,H,P,A>::unordered_multiset(
1470 InputIt f, InputIt l,
1473 const allocator_type &a)
1474 : table_(boost::unordered::detail::initial_size(f, l, n),
1477 table_.insert_range(f, l);
1480 template <class T, class H, class P, class A>
1481 template <class InputIt>
1482 unordered_multiset<T,H,P,A>::unordered_multiset(
1483 InputIt f, InputIt l,
1485 const allocator_type &a)
1486 : table_(boost::unordered::detail::initial_size(f, l, n),
1487 hasher(), key_equal(), a)
1489 table_.insert_range(f, l);
1492 template <class T, class H, class P, class A>
1493 unordered_multiset<T,H,P,A>::~unordered_multiset() BOOST_NOEXCEPT {}
1495 template <class T, class H, class P, class A>
1496 unordered_multiset<T,H,P,A>::unordered_multiset(
1497 unordered_multiset const& other)
1498 : table_(other.table_)
1502 template <class T, class H, class P, class A>
1503 unordered_multiset<T,H,P,A>::unordered_multiset(
1504 BOOST_RV_REF(unordered_multiset) other, allocator_type const& a)
1505 : table_(other.table_, a, boost::unordered::detail::move_tag())
1509 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1511 template <class T, class H, class P, class A>
1512 unordered_multiset<T,H,P,A>::unordered_multiset(
1513 std::initializer_list<value_type> list, size_type n,
1514 const hasher &hf, const key_equal &eql, const allocator_type &a)
1516 boost::unordered::detail::initial_size(
1517 list.begin(), list.end(), n),
1520 table_.insert_range(list.begin(), list.end());
1523 template <class T, class H, class P, class A>
1524 unordered_multiset<T,H,P,A>::unordered_multiset(
1525 std::initializer_list<value_type> list, size_type n,
1526 const hasher &hf, const allocator_type &a)
1528 boost::unordered::detail::initial_size(
1529 list.begin(), list.end(), n),
1532 table_.insert_range(list.begin(), list.end());
1535 template <class T, class H, class P, class A>
1536 unordered_multiset<T,H,P,A>::unordered_multiset(
1537 std::initializer_list<value_type> list, size_type n,
1538 const allocator_type &a)
1540 boost::unordered::detail::initial_size(
1541 list.begin(), list.end(), n),
1542 hasher(), key_equal(), a)
1544 table_.insert_range(list.begin(), list.end());
1547 template <class T, class H, class P, class A>
1548 unordered_multiset<T,H,P,A>& unordered_multiset<T,H,P,A>::operator=(
1549 std::initializer_list<value_type> list)
1552 table_.insert_range(list.begin(), list.end());
1558 // size and capacity
1560 template <class T, class H, class P, class A>
1561 std::size_t unordered_multiset<T,H,P,A>::max_size() const BOOST_NOEXCEPT
1563 return table_.max_size();
1568 template <class T, class H, class P, class A>
1569 template <class InputIt>
1570 void unordered_multiset<T,H,P,A>::insert(InputIt first, InputIt last)
1572 table_.insert_range(first, last);
1575 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1576 template <class T, class H, class P, class A>
1577 void unordered_multiset<T,H,P,A>::insert(
1578 std::initializer_list<value_type> list)
1580 table_.insert_range(list.begin(), list.end());
1584 template <class T, class H, class P, class A>
1585 typename unordered_multiset<T,H,P,A>::iterator
1586 unordered_multiset<T,H,P,A>::erase(const_iterator position)
1588 return table_.erase(position);
1591 template <class T, class H, class P, class A>
1592 typename unordered_multiset<T,H,P,A>::size_type
1593 unordered_multiset<T,H,P,A>::erase(const key_type& k)
1595 return table_.erase_key(k);
1598 template <class T, class H, class P, class A>
1599 typename unordered_multiset<T,H,P,A>::iterator
1600 unordered_multiset<T,H,P,A>::erase(
1601 const_iterator first, const_iterator last)
1603 return table_.erase_range(first, last);
1606 template <class T, class H, class P, class A>
1607 void unordered_multiset<T,H,P,A>::clear()
1612 template <class T, class H, class P, class A>
1613 void unordered_multiset<T,H,P,A>::swap(unordered_multiset& other)
1615 table_.swap(other.table_);
1620 template <class T, class H, class P, class A>
1621 typename unordered_multiset<T,H,P,A>::hasher
1622 unordered_multiset<T,H,P,A>::hash_function() const
1624 return table_.hash_function();
1627 template <class T, class H, class P, class A>
1628 typename unordered_multiset<T,H,P,A>::key_equal
1629 unordered_multiset<T,H,P,A>::key_eq() const
1631 return table_.key_eq();
1636 template <class T, class H, class P, class A>
1637 typename unordered_multiset<T,H,P,A>::const_iterator
1638 unordered_multiset<T,H,P,A>::find(const key_type& k) const
1640 return const_iterator(table_.find_node(k));
1643 template <class T, class H, class P, class A>
1644 template <class CompatibleKey, class CompatibleHash,
1645 class CompatiblePredicate>
1646 typename unordered_multiset<T,H,P,A>::const_iterator
1647 unordered_multiset<T,H,P,A>::find(
1648 CompatibleKey const& k,
1649 CompatibleHash const& hash,
1650 CompatiblePredicate const& eq) const
1652 return const_iterator(table_.generic_find_node(k, hash, eq));
1655 template <class T, class H, class P, class A>
1656 typename unordered_multiset<T,H,P,A>::size_type
1657 unordered_multiset<T,H,P,A>::count(const key_type& k) const
1659 return table_.count(k);
1662 template <class T, class H, class P, class A>
1664 typename unordered_multiset<T,H,P,A>::const_iterator,
1665 typename unordered_multiset<T,H,P,A>::const_iterator>
1666 unordered_multiset<T,H,P,A>::equal_range(const key_type& k) const
1668 return table_.equal_range(k);
1671 template <class T, class H, class P, class A>
1672 typename unordered_multiset<T,H,P,A>::size_type
1673 unordered_multiset<T,H,P,A>::bucket_size(size_type n) const
1675 return table_.bucket_size(n);
1680 template <class T, class H, class P, class A>
1681 float unordered_multiset<T,H,P,A>::load_factor() const BOOST_NOEXCEPT
1683 return table_.load_factor();
1686 template <class T, class H, class P, class A>
1687 void unordered_multiset<T,H,P,A>::max_load_factor(float m) BOOST_NOEXCEPT
1689 table_.max_load_factor(m);
1692 template <class T, class H, class P, class A>
1693 void unordered_multiset<T,H,P,A>::rehash(size_type n)
1698 template <class T, class H, class P, class A>
1699 void unordered_multiset<T,H,P,A>::reserve(size_type n)
1704 template <class T, class H, class P, class A>
1705 inline bool operator==(
1706 unordered_multiset<T,H,P,A> const& m1,
1707 unordered_multiset<T,H,P,A> const& m2)
1709 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1710 struct dummy { unordered_multiset<T,H,P,A> x; };
1712 return m1.table_.equals(m2.table_);
1715 template <class T, class H, class P, class A>
1716 inline bool operator!=(
1717 unordered_multiset<T,H,P,A> const& m1,
1718 unordered_multiset<T,H,P,A> const& m2)
1720 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1721 struct dummy { unordered_multiset<T,H,P,A> x; };
1723 return !m1.table_.equals(m2.table_);
1726 template <class T, class H, class P, class A>
1728 unordered_multiset<T,H,P,A> &m1,
1729 unordered_multiset<T,H,P,A> &m2)
1731 #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
1732 struct dummy { unordered_multiset<T,H,P,A> x; };
1736 } // namespace unordered
1737 } // namespace boost
1739 #if defined(BOOST_MSVC)
1740 #pragma warning(pop)
1743 #endif // BOOST_UNORDERED_UNORDERED_SET_HPP_INCLUDED