Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-30 10:02:00 

0001 // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
0002 // Copyright (C) 2005-2011 Daniel James.
0003 // Copyright (C) 2022-2023 Christian Mazakas
0004 // Distributed under the Boost Software License, Version 1.0. (See accompanying
0005 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 
0007 //  See http://www.boost.org/libs/unordered for documentation
0008 
0009 #ifndef BOOST_UNORDERED_UNORDERED_SET_HPP_INCLUDED
0010 #define BOOST_UNORDERED_UNORDERED_SET_HPP_INCLUDED
0011 
0012 #include <boost/config.hpp>
0013 #if defined(BOOST_HAS_PRAGMA_ONCE)
0014 #pragma once
0015 #endif
0016 
0017 #include <boost/unordered/detail/serialize_fca_container.hpp>
0018 #include <boost/unordered/detail/set.hpp>
0019 #include <boost/unordered/detail/type_traits.hpp>
0020 
0021 #include <boost/container_hash/hash.hpp>
0022 
0023 #include <initializer_list>
0024 
0025 #if defined(BOOST_MSVC)
0026 #pragma warning(push)
0027 // conditional expression is constant
0028 #pragma warning(disable : 4127)
0029 #if BOOST_MSVC >= 1400
0030 // the inline specifier cannot be used when a friend declaration refers to a
0031 // specialization of a function template
0032 #pragma warning(disable : 4396)
0033 #endif
0034 #endif
0035 
0036 namespace boost {
0037   namespace unordered {
0038     template <class T, class H, class P, class A> class unordered_set
0039     {
0040       template <typename, typename, typename, typename>
0041       friend class unordered_multiset;
0042 
0043     public:
0044       typedef T key_type;
0045       typedef T value_type;
0046       typedef H hasher;
0047       typedef P key_equal;
0048       typedef A allocator_type;
0049 
0050     private:
0051       typedef boost::unordered::detail::set<A, T, H, P> types;
0052       typedef typename types::value_allocator_traits value_allocator_traits;
0053       typedef typename types::table table;
0054 
0055     public:
0056       typedef typename value_allocator_traits::pointer pointer;
0057       typedef typename value_allocator_traits::const_pointer const_pointer;
0058 
0059       typedef value_type& reference;
0060       typedef value_type const& const_reference;
0061 
0062       typedef std::size_t size_type;
0063       typedef std::ptrdiff_t difference_type;
0064 
0065       typedef typename table::c_iterator iterator;
0066       typedef typename table::c_iterator const_iterator;
0067       typedef typename table::cl_iterator local_iterator;
0068       typedef typename table::cl_iterator const_local_iterator;
0069       typedef typename types::node_type node_type;
0070       typedef typename types::insert_return_type insert_return_type;
0071 
0072     private:
0073       table table_;
0074 
0075     public:
0076       // constructors
0077 
0078       unordered_set();
0079 
0080       explicit unordered_set(size_type, const hasher& = hasher(),
0081         const key_equal& = key_equal(),
0082         const allocator_type& = allocator_type());
0083 
0084       template <class InputIt>
0085       unordered_set(InputIt, InputIt,
0086         size_type = boost::unordered::detail::default_bucket_count,
0087         const hasher& = hasher(), const key_equal& = key_equal(),
0088         const allocator_type& = allocator_type());
0089 
0090       unordered_set(unordered_set const&);
0091 
0092       unordered_set(unordered_set&& other)
0093         noexcept(table::nothrow_move_constructible)
0094           : table_(other.table_, boost::unordered::detail::move_tag())
0095       {
0096         // The move is done in table_
0097       }
0098 
0099       explicit unordered_set(allocator_type const&);
0100 
0101       unordered_set(unordered_set const&, allocator_type const&);
0102 
0103       unordered_set(unordered_set&&, allocator_type const&);
0104 
0105       unordered_set(std::initializer_list<value_type>,
0106         size_type = boost::unordered::detail::default_bucket_count,
0107         const hasher& = hasher(), const key_equal& l = key_equal(),
0108         const allocator_type& = allocator_type());
0109 
0110       explicit unordered_set(size_type, const allocator_type&);
0111 
0112       explicit unordered_set(size_type, const hasher&, const allocator_type&);
0113 
0114       template <class InputIterator>
0115       unordered_set(InputIterator, InputIterator, const allocator_type&);
0116 
0117       template <class InputIt>
0118       unordered_set(InputIt, InputIt, size_type, const allocator_type&);
0119 
0120       template <class InputIt>
0121       unordered_set(
0122         InputIt, InputIt, size_type, const hasher&, const allocator_type&);
0123 
0124       unordered_set(std::initializer_list<value_type>, const allocator_type&);
0125 
0126       unordered_set(
0127         std::initializer_list<value_type>, size_type, const allocator_type&);
0128 
0129       unordered_set(std::initializer_list<value_type>, size_type, const hasher&,
0130         const allocator_type&);
0131 
0132       // Destructor
0133 
0134       ~unordered_set() noexcept;
0135 
0136       // Assign
0137 
0138       unordered_set& operator=(unordered_set const& x)
0139       {
0140         table_.assign(x.table_, std::true_type());
0141         return *this;
0142       }
0143 
0144       unordered_set& operator=(unordered_set&& x)
0145         noexcept(value_allocator_traits::is_always_equal::value&&
0146             std::is_nothrow_move_assignable<H>::value&&
0147               std::is_nothrow_move_assignable<P>::value)
0148       {
0149         table_.move_assign(x.table_, std::true_type());
0150         return *this;
0151       }
0152 
0153       unordered_set& operator=(std::initializer_list<value_type>);
0154 
0155       allocator_type get_allocator() const noexcept
0156       {
0157         return table_.node_alloc();
0158       }
0159 
0160       // iterators
0161 
0162       iterator begin() noexcept { return iterator(table_.begin()); }
0163 
0164       const_iterator begin() const noexcept
0165       {
0166         return const_iterator(table_.begin());
0167       }
0168 
0169       iterator end() noexcept { return iterator(); }
0170 
0171       const_iterator end() const noexcept { return const_iterator(); }
0172 
0173       const_iterator cbegin() const noexcept
0174       {
0175         return const_iterator(table_.begin());
0176       }
0177 
0178       const_iterator cend() const noexcept { return const_iterator(); }
0179 
0180       // size and capacity
0181 
0182       BOOST_ATTRIBUTE_NODISCARD bool empty() const noexcept
0183       {
0184         return table_.size_ == 0;
0185       }
0186 
0187       size_type size() const noexcept { return table_.size_; }
0188 
0189       size_type max_size() const noexcept;
0190 
0191       // emplace
0192 
0193       template <class... Args> std::pair<iterator, bool> emplace(Args&&... args)
0194       {
0195         return table_.emplace_unique(
0196           table::extractor::extract(std::forward<Args>(args)...),
0197           std::forward<Args>(args)...);
0198       }
0199 
0200       template <class... Args>
0201       iterator emplace_hint(const_iterator hint, Args&&... args)
0202       {
0203         return table_.emplace_hint_unique(hint,
0204           table::extractor::extract(std::forward<Args>(args)...),
0205           std::forward<Args>(args)...);
0206       }
0207 
0208       std::pair<iterator, bool> insert(value_type const& x)
0209       {
0210         return this->emplace(x);
0211       }
0212 
0213       std::pair<iterator, bool> insert(value_type&& x)
0214       {
0215         return this->emplace(std::move(x));
0216       }
0217 
0218       template <class Key>
0219       typename boost::enable_if_c<
0220         detail::transparent_non_iterable<Key, unordered_set>::value,
0221         std::pair<iterator, bool> >::type
0222       insert(Key&& k)
0223       {
0224         return table_.try_emplace_unique(std::forward<Key>(k));
0225       }
0226 
0227       iterator insert(const_iterator hint, value_type const& x)
0228       {
0229         return this->emplace_hint(hint, x);
0230       }
0231 
0232       iterator insert(const_iterator hint, value_type&& x)
0233       {
0234         return this->emplace_hint(hint, std::move(x));
0235       }
0236 
0237       template <class Key>
0238       typename boost::enable_if_c<
0239         detail::transparent_non_iterable<Key, unordered_set>::value,
0240         iterator>::type
0241       insert(const_iterator hint, Key&& k)
0242       {
0243         return table_.try_emplace_hint_unique(hint, std::forward<Key>(k));
0244       }
0245 
0246       template <class InputIt> void insert(InputIt, InputIt);
0247 
0248       void insert(std::initializer_list<value_type>);
0249 
0250       // extract
0251 
0252       node_type extract(const_iterator position)
0253       {
0254         return node_type(
0255           table_.extract_by_iterator_unique(position), table_.node_alloc());
0256       }
0257 
0258       node_type extract(const key_type& k)
0259       {
0260         return node_type(table_.extract_by_key_impl(k), table_.node_alloc());
0261       }
0262 
0263       template <class Key>
0264       typename boost::enable_if_c<
0265         detail::transparent_non_iterable<Key, unordered_set>::value,
0266         node_type>::type
0267       extract(const Key& k)
0268       {
0269         return node_type(table_.extract_by_key_impl(k), table_.node_alloc());
0270       }
0271 
0272       insert_return_type insert(node_type&& np)
0273       {
0274         insert_return_type result;
0275         table_.move_insert_node_type_unique(np, result);
0276         return result;
0277       }
0278 
0279       iterator insert(const_iterator hint, node_type&& np)
0280       {
0281         return table_.move_insert_node_type_with_hint_unique(hint, np);
0282       }
0283 
0284       iterator erase(const_iterator);
0285       size_type erase(const key_type&);
0286       iterator erase(const_iterator, const_iterator);
0287 
0288       template <class Key>
0289       typename boost::enable_if_c<
0290         detail::transparent_non_iterable<Key, unordered_set>::value,
0291         size_type>::type
0292       erase(Key&& k)
0293       {
0294         return table_.erase_key_unique_impl(std::forward<Key>(k));
0295       }
0296 
0297       BOOST_UNORDERED_DEPRECATED("Use erase instead")
0298       void quick_erase(const_iterator it) { erase(it); }
0299       BOOST_UNORDERED_DEPRECATED("Use erase instead")
0300       void erase_return_void(const_iterator it) { erase(it); }
0301 
0302       void swap(unordered_set&)
0303         noexcept(value_allocator_traits::is_always_equal::value&&
0304             boost::unordered::detail::is_nothrow_swappable<H>::value&&
0305               boost::unordered::detail::is_nothrow_swappable<P>::value);
0306       void clear() noexcept { table_.clear_impl(); }
0307 
0308       template <typename H2, typename P2>
0309       void merge(boost::unordered_set<T, H2, P2, A>& source);
0310 
0311       template <typename H2, typename P2>
0312       void merge(boost::unordered_set<T, H2, P2, A>&& source);
0313 
0314       template <typename H2, typename P2>
0315       void merge(boost::unordered_multiset<T, H2, P2, A>& source);
0316 
0317       template <typename H2, typename P2>
0318       void merge(boost::unordered_multiset<T, H2, P2, A>&& source);
0319 
0320       // observers
0321 
0322       hasher hash_function() const;
0323       key_equal key_eq() const;
0324 
0325       // lookup
0326 
0327       const_iterator find(const key_type&) const;
0328 
0329       template <class Key>
0330       typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
0331         const_iterator>::type
0332       find(const Key& k) const
0333       {
0334         return const_iterator(table_.find(k));
0335       }
0336 
0337       template <class CompatibleKey, class CompatibleHash,
0338         class CompatiblePredicate>
0339       const_iterator find(CompatibleKey const&, CompatibleHash const&,
0340         CompatiblePredicate const&) const;
0341 
0342       bool contains(key_type const& k) const
0343       {
0344         return table_.find(k) != this->end();
0345       }
0346 
0347       template <class Key>
0348       typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
0349         bool>::type
0350       contains(const Key& k) const
0351       {
0352         return table_.find(k) != this->end();
0353       }
0354 
0355       size_type count(const key_type&) const;
0356 
0357       template <class Key>
0358       typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
0359         size_type>::type
0360       count(const Key& k) const
0361       {
0362         return table_.find(k) != this->end() ? 1 : 0;
0363       }
0364 
0365       std::pair<const_iterator, const_iterator> equal_range(
0366         const key_type&) const;
0367 
0368       template <class Key>
0369       typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
0370         std::pair<const_iterator, const_iterator> >::type
0371       equal_range(Key const& k) const
0372       {
0373         iterator n = table_.find(k);
0374         iterator m = n;
0375         if (m != this->end()) {
0376           ++m;
0377         }
0378 
0379         return std::make_pair(const_iterator(n), const_iterator(m));
0380       }
0381 
0382       // bucket interface
0383 
0384       size_type bucket_count() const noexcept { return table_.bucket_count(); }
0385 
0386       size_type max_bucket_count() const noexcept
0387       {
0388         return table_.max_bucket_count();
0389       }
0390 
0391       size_type bucket_size(size_type) const;
0392 
0393       size_type bucket(const key_type& k) const
0394       {
0395         return table_.hash_to_bucket(table_.hash(k));
0396       }
0397 
0398       template <class Key>
0399       typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
0400         size_type>::type
0401       bucket(Key&& k) const
0402       {
0403         return table_.hash_to_bucket(table_.hash(std::forward<Key>(k)));
0404       }
0405 
0406       local_iterator begin(size_type n)
0407       {
0408         return local_iterator(table_.begin(n));
0409       }
0410 
0411       const_local_iterator begin(size_type n) const
0412       {
0413         return const_local_iterator(table_.begin(n));
0414       }
0415 
0416       local_iterator end(size_type) { return local_iterator(); }
0417 
0418       const_local_iterator end(size_type) const
0419       {
0420         return const_local_iterator();
0421       }
0422 
0423       const_local_iterator cbegin(size_type n) const
0424       {
0425         return const_local_iterator(table_.begin(n));
0426       }
0427 
0428       const_local_iterator cend(size_type) const
0429       {
0430         return const_local_iterator();
0431       }
0432 
0433       // hash policy
0434 
0435       float load_factor() const noexcept;
0436       float max_load_factor() const noexcept { return table_.mlf_; }
0437       void max_load_factor(float) noexcept;
0438       void rehash(size_type);
0439       void reserve(size_type);
0440 
0441 #if !BOOST_WORKAROUND(BOOST_BORLANDC, < 0x0582)
0442       friend bool operator==
0443         <T, H, P, A>(unordered_set const&, unordered_set const&);
0444       friend bool operator!=
0445         <T, H, P, A>(unordered_set const&, unordered_set const&);
0446 #endif
0447     }; // class template unordered_set
0448 
0449     template <class Archive, class K, class H, class P, class A>
0450     void serialize(
0451       Archive& ar, unordered_set<K, H, P, A>& c, unsigned int version)
0452     {
0453       detail::serialize_fca_container(ar, c, version);
0454     }
0455 
0456 #if BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES
0457 
0458     template <class InputIterator,
0459       class Hash =
0460         boost::hash<typename std::iterator_traits<InputIterator>::value_type>,
0461       class Pred =
0462         std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
0463       class Allocator = std::allocator<
0464         typename std::iterator_traits<InputIterator>::value_type>,
0465       class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
0466       class = std::enable_if_t<detail::is_hash_v<Hash> >,
0467       class = std::enable_if_t<detail::is_pred_v<Pred> >,
0468       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0469     unordered_set(InputIterator, InputIterator,
0470       std::size_t = boost::unordered::detail::default_bucket_count,
0471       Hash = Hash(), Pred = Pred(), Allocator = Allocator())
0472       -> unordered_set<typename std::iterator_traits<InputIterator>::value_type,
0473         Hash, Pred, Allocator>;
0474 
0475     template <class T, class Hash = boost::hash<T>,
0476       class Pred = std::equal_to<T>, class Allocator = std::allocator<T>,
0477       class = std::enable_if_t<detail::is_hash_v<Hash> >,
0478       class = std::enable_if_t<detail::is_pred_v<Pred> >,
0479       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0480     unordered_set(std::initializer_list<T>,
0481       std::size_t = boost::unordered::detail::default_bucket_count,
0482       Hash = Hash(), Pred = Pred(), Allocator = Allocator())
0483       -> unordered_set<T, Hash, Pred, Allocator>;
0484 
0485     template <class InputIterator, class Allocator,
0486       class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
0487       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0488     unordered_set(InputIterator, InputIterator, std::size_t, Allocator)
0489       -> unordered_set<typename std::iterator_traits<InputIterator>::value_type,
0490         boost::hash<typename std::iterator_traits<InputIterator>::value_type>,
0491         std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
0492         Allocator>;
0493 
0494     template <class InputIterator, class Hash, class Allocator,
0495       class = std::enable_if_t<detail::is_hash_v<Hash> >,
0496       class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
0497       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0498     unordered_set(InputIterator, InputIterator, std::size_t, Hash, Allocator)
0499       -> unordered_set<typename std::iterator_traits<InputIterator>::value_type,
0500         Hash,
0501         std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
0502         Allocator>;
0503 
0504     template <class T, class Allocator,
0505       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0506     unordered_set(std::initializer_list<T>, std::size_t, Allocator)
0507       -> unordered_set<T, boost::hash<T>, std::equal_to<T>, Allocator>;
0508 
0509     template <class T, class Hash, class Allocator,
0510       class = std::enable_if_t<detail::is_hash_v<Hash> >,
0511       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0512     unordered_set(std::initializer_list<T>, std::size_t, Hash, Allocator)
0513       -> unordered_set<T, Hash, std::equal_to<T>, Allocator>;
0514 
0515     template <class InputIterator, class Allocator,
0516       class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
0517       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0518     unordered_set(InputIterator, InputIterator, Allocator)
0519       -> unordered_set<typename std::iterator_traits<InputIterator>::value_type,
0520         boost::hash<typename std::iterator_traits<InputIterator>::value_type>,
0521         std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
0522         Allocator>;
0523 
0524     template <class T, class Allocator,
0525       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0526     unordered_set(std::initializer_list<T>, Allocator)
0527       -> unordered_set<T, boost::hash<T>, std::equal_to<T>, Allocator>;
0528 
0529 #endif
0530 
0531     template <class T, class H, class P, class A> class unordered_multiset
0532     {
0533       template <typename, typename, typename, typename>
0534       friend class unordered_set;
0535 
0536     public:
0537       typedef T key_type;
0538       typedef T value_type;
0539       typedef H hasher;
0540       typedef P key_equal;
0541       typedef A allocator_type;
0542 
0543     private:
0544       typedef boost::unordered::detail::set<A, T, H, P> types;
0545       typedef typename types::value_allocator_traits value_allocator_traits;
0546       typedef typename types::table table;
0547 
0548     public:
0549       typedef typename value_allocator_traits::pointer pointer;
0550       typedef typename value_allocator_traits::const_pointer const_pointer;
0551 
0552       typedef value_type& reference;
0553       typedef value_type const& const_reference;
0554 
0555       typedef std::size_t size_type;
0556       typedef std::ptrdiff_t difference_type;
0557 
0558       typedef typename table::c_iterator iterator;
0559       typedef typename table::c_iterator const_iterator;
0560       typedef typename table::cl_iterator local_iterator;
0561       typedef typename table::cl_iterator const_local_iterator;
0562       typedef typename types::node_type node_type;
0563 
0564     private:
0565       table table_;
0566 
0567     public:
0568       // constructors
0569 
0570       unordered_multiset();
0571 
0572       explicit unordered_multiset(size_type, const hasher& = hasher(),
0573         const key_equal& = key_equal(),
0574         const allocator_type& = allocator_type());
0575 
0576       template <class InputIt>
0577       unordered_multiset(InputIt, InputIt,
0578         size_type = boost::unordered::detail::default_bucket_count,
0579         const hasher& = hasher(), const key_equal& = key_equal(),
0580         const allocator_type& = allocator_type());
0581 
0582       unordered_multiset(unordered_multiset const&);
0583 
0584       unordered_multiset(unordered_multiset&& other)
0585         noexcept(table::nothrow_move_constructible)
0586           : table_(other.table_, boost::unordered::detail::move_tag())
0587       {
0588         // The move is done in table_
0589       }
0590 
0591       explicit unordered_multiset(allocator_type const&);
0592 
0593       unordered_multiset(unordered_multiset const&, allocator_type const&);
0594 
0595       unordered_multiset(unordered_multiset&&, allocator_type const&);
0596 
0597       unordered_multiset(std::initializer_list<value_type>,
0598         size_type = boost::unordered::detail::default_bucket_count,
0599         const hasher& = hasher(), const key_equal& l = key_equal(),
0600         const allocator_type& = allocator_type());
0601 
0602       explicit unordered_multiset(size_type, const allocator_type&);
0603 
0604       explicit unordered_multiset(
0605         size_type, const hasher&, const allocator_type&);
0606 
0607       template <class InputIterator>
0608       unordered_multiset(InputIterator, InputIterator, const allocator_type&);
0609 
0610       template <class InputIt>
0611       unordered_multiset(InputIt, InputIt, size_type, const allocator_type&);
0612 
0613       template <class InputIt>
0614       unordered_multiset(
0615         InputIt, InputIt, size_type, const hasher&, const allocator_type&);
0616 
0617       unordered_multiset(
0618         std::initializer_list<value_type>, const allocator_type&);
0619 
0620       unordered_multiset(
0621         std::initializer_list<value_type>, size_type, const allocator_type&);
0622 
0623       unordered_multiset(std::initializer_list<value_type>, size_type,
0624         const hasher&, const allocator_type&);
0625 
0626       // Destructor
0627 
0628       ~unordered_multiset() noexcept;
0629 
0630       // Assign
0631       unordered_multiset& operator=(unordered_multiset const& x)
0632       {
0633         table_.assign(x.table_, std::false_type());
0634         return *this;
0635       }
0636 
0637       unordered_multiset& operator=(unordered_multiset&& x)
0638         noexcept(value_allocator_traits::is_always_equal::value&&
0639             std::is_nothrow_move_assignable<H>::value&&
0640               std::is_nothrow_move_assignable<P>::value)
0641       {
0642         table_.move_assign(x.table_, std::false_type());
0643         return *this;
0644       }
0645 
0646       unordered_multiset& operator=(std::initializer_list<value_type>);
0647 
0648       allocator_type get_allocator() const noexcept
0649       {
0650         return table_.node_alloc();
0651       }
0652 
0653       // iterators
0654 
0655       iterator begin() noexcept { return iterator(table_.begin()); }
0656 
0657       const_iterator begin() const noexcept
0658       {
0659         return const_iterator(table_.begin());
0660       }
0661 
0662       iterator end() noexcept { return iterator(); }
0663 
0664       const_iterator end() const noexcept { return const_iterator(); }
0665 
0666       const_iterator cbegin() const noexcept
0667       {
0668         return const_iterator(table_.begin());
0669       }
0670 
0671       const_iterator cend() const noexcept { return const_iterator(); }
0672 
0673       // size and capacity
0674 
0675       BOOST_ATTRIBUTE_NODISCARD bool empty() const noexcept
0676       {
0677         return table_.size_ == 0;
0678       }
0679 
0680       size_type size() const noexcept { return table_.size_; }
0681 
0682       size_type max_size() const noexcept;
0683 
0684       // emplace
0685 
0686       template <class... Args> iterator emplace(Args&&... args)
0687       {
0688         return iterator(table_.emplace_equiv(
0689           boost::unordered::detail::func::construct_node_from_args(
0690             table_.node_alloc(), std::forward<Args>(args)...)));
0691       }
0692 
0693       template <class... Args>
0694       iterator emplace_hint(const_iterator hint, Args&&... args)
0695       {
0696         return iterator(table_.emplace_hint_equiv(
0697           hint, boost::unordered::detail::func::construct_node_from_args(
0698                   table_.node_alloc(), std::forward<Args>(args)...)));
0699       }
0700 
0701       iterator insert(value_type const& x) { return this->emplace(x); }
0702 
0703       iterator insert(value_type&& x) { return this->emplace(std::move(x)); }
0704 
0705       iterator insert(const_iterator hint, value_type const& x)
0706       {
0707         return this->emplace_hint(hint, x);
0708       }
0709 
0710       iterator insert(const_iterator hint, value_type&& x)
0711       {
0712         return this->emplace_hint(hint, std::move(x));
0713       }
0714 
0715       template <class InputIt> void insert(InputIt, InputIt);
0716 
0717       void insert(std::initializer_list<value_type>);
0718 
0719       // extract
0720 
0721       node_type extract(const_iterator position)
0722       {
0723         return node_type(
0724           table_.extract_by_iterator_equiv(position), table_.node_alloc());
0725       }
0726 
0727       node_type extract(const key_type& k)
0728       {
0729         return node_type(table_.extract_by_key_impl(k), table_.node_alloc());
0730       }
0731 
0732       template <class Key>
0733       typename boost::enable_if_c<
0734         detail::transparent_non_iterable<Key, unordered_multiset>::value,
0735         node_type>::type
0736       extract(const Key& k)
0737       {
0738         return node_type(table_.extract_by_key_impl(k), table_.node_alloc());
0739       }
0740 
0741       iterator insert(node_type&& np)
0742       {
0743         return table_.move_insert_node_type_equiv(np);
0744       }
0745 
0746       iterator insert(const_iterator hint, node_type&& np)
0747       {
0748         return table_.move_insert_node_type_with_hint_equiv(hint, np);
0749       }
0750 
0751       iterator erase(const_iterator);
0752       size_type erase(const key_type&);
0753 
0754       template <class Key>
0755       typename boost::enable_if_c<
0756         detail::transparent_non_iterable<Key, unordered_multiset>::value,
0757         size_type>::type
0758       erase(const Key& k)
0759       {
0760         return table_.erase_key_equiv_impl(k);
0761       }
0762 
0763       iterator erase(const_iterator, const_iterator);
0764       BOOST_UNORDERED_DEPRECATED("Use erase instead")
0765       void quick_erase(const_iterator it) { erase(it); }
0766       BOOST_UNORDERED_DEPRECATED("Use erase instead")
0767       void erase_return_void(const_iterator it) { erase(it); }
0768 
0769       void swap(unordered_multiset&)
0770         noexcept(value_allocator_traits::is_always_equal::value&&
0771             boost::unordered::detail::is_nothrow_swappable<H>::value&&
0772               boost::unordered::detail::is_nothrow_swappable<P>::value);
0773       void clear() noexcept { table_.clear_impl(); }
0774 
0775       template <typename H2, typename P2>
0776       void merge(boost::unordered_multiset<T, H2, P2, A>& source);
0777 
0778       template <typename H2, typename P2>
0779       void merge(boost::unordered_multiset<T, H2, P2, A>&& source);
0780 
0781       template <typename H2, typename P2>
0782       void merge(boost::unordered_set<T, H2, P2, A>& source);
0783 
0784       template <typename H2, typename P2>
0785       void merge(boost::unordered_set<T, H2, P2, A>&& source);
0786 
0787       // observers
0788 
0789       hasher hash_function() const;
0790       key_equal key_eq() const;
0791 
0792       // lookup
0793 
0794       const_iterator find(const key_type&) const;
0795 
0796       template <class Key>
0797       typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
0798         const_iterator>::type
0799       find(const Key& k) const
0800       {
0801         return table_.find(k);
0802       }
0803 
0804       template <class CompatibleKey, class CompatibleHash,
0805         class CompatiblePredicate>
0806       const_iterator find(CompatibleKey const&, CompatibleHash const&,
0807         CompatiblePredicate const&) const;
0808 
0809       bool contains(const key_type& k) const
0810       {
0811         return table_.find(k) != this->end();
0812       }
0813 
0814       template <class Key>
0815       typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
0816         bool>::type
0817       contains(const Key& k) const
0818       {
0819         return table_.find(k) != this->end();
0820       }
0821 
0822       size_type count(const key_type&) const;
0823 
0824       template <class Key>
0825       typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
0826         size_type>::type
0827       count(const Key& k) const
0828       {
0829         return table_.group_count(k);
0830       }
0831 
0832       std::pair<const_iterator, const_iterator> equal_range(
0833         const key_type&) const;
0834 
0835       template <class Key>
0836       typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
0837         std::pair<const_iterator, const_iterator> >::type
0838       equal_range(const Key& k) const
0839       {
0840         iterator first = table_.find(k);
0841         iterator last = table_.next_group(k, first);
0842         return std::make_pair(const_iterator(first), const_iterator(last));
0843       }
0844 
0845       // bucket interface
0846 
0847       size_type bucket_count() const noexcept { return table_.bucket_count(); }
0848 
0849       size_type max_bucket_count() const noexcept
0850       {
0851         return table_.max_bucket_count();
0852       }
0853 
0854       size_type bucket_size(size_type) const;
0855 
0856       size_type bucket(const key_type& k) const
0857       {
0858         return table_.hash_to_bucket(table_.hash(k));
0859       }
0860 
0861       template <class Key>
0862       typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
0863         size_type>::type
0864       bucket(Key&& k) const
0865       {
0866         return table_.hash_to_bucket(table_.hash(std::forward<Key>(k)));
0867       }
0868 
0869       local_iterator begin(size_type n)
0870       {
0871         return local_iterator(table_.begin(n));
0872       }
0873 
0874       const_local_iterator begin(size_type n) const
0875       {
0876         return const_local_iterator(table_.begin(n));
0877       }
0878 
0879       local_iterator end(size_type) { return local_iterator(); }
0880 
0881       const_local_iterator end(size_type) const
0882       {
0883         return const_local_iterator();
0884       }
0885 
0886       const_local_iterator cbegin(size_type n) const
0887       {
0888         return const_local_iterator(table_.begin(n));
0889       }
0890 
0891       const_local_iterator cend(size_type) const
0892       {
0893         return const_local_iterator();
0894       }
0895 
0896       // hash policy
0897 
0898       float load_factor() const noexcept;
0899       float max_load_factor() const noexcept { return table_.mlf_; }
0900       void max_load_factor(float) noexcept;
0901       void rehash(size_type);
0902       void reserve(size_type);
0903 
0904 #if !BOOST_WORKAROUND(BOOST_BORLANDC, < 0x0582)
0905       friend bool operator==
0906         <T, H, P, A>(unordered_multiset const&, unordered_multiset const&);
0907       friend bool operator!=
0908         <T, H, P, A>(unordered_multiset const&, unordered_multiset const&);
0909 #endif
0910     }; // class template unordered_multiset
0911 
0912     template <class Archive, class K, class H, class P, class A>
0913     void serialize(
0914       Archive& ar, unordered_multiset<K, H, P, A>& c, unsigned int version)
0915     {
0916       detail::serialize_fca_container(ar, c, version);
0917     }
0918 
0919 #if BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES
0920 
0921     template <class InputIterator,
0922       class Hash =
0923         boost::hash<typename std::iterator_traits<InputIterator>::value_type>,
0924       class Pred =
0925         std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
0926       class Allocator = std::allocator<
0927         typename std::iterator_traits<InputIterator>::value_type>,
0928       class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
0929       class = std::enable_if_t<detail::is_hash_v<Hash> >,
0930       class = std::enable_if_t<detail::is_pred_v<Pred> >,
0931       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0932     unordered_multiset(InputIterator, InputIterator,
0933       std::size_t = boost::unordered::detail::default_bucket_count,
0934       Hash = Hash(), Pred = Pred(), Allocator = Allocator())
0935       -> unordered_multiset<
0936         typename std::iterator_traits<InputIterator>::value_type, Hash, Pred,
0937         Allocator>;
0938 
0939     template <class T, class Hash = boost::hash<T>,
0940       class Pred = std::equal_to<T>, class Allocator = std::allocator<T>,
0941       class = std::enable_if_t<detail::is_hash_v<Hash> >,
0942       class = std::enable_if_t<detail::is_pred_v<Pred> >,
0943       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0944     unordered_multiset(std::initializer_list<T>,
0945       std::size_t = boost::unordered::detail::default_bucket_count,
0946       Hash = Hash(), Pred = Pred(), Allocator = Allocator())
0947       -> unordered_multiset<T, Hash, Pred, Allocator>;
0948 
0949     template <class InputIterator, class Allocator,
0950       class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
0951       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0952     unordered_multiset(InputIterator, InputIterator, std::size_t, Allocator)
0953       -> unordered_multiset<
0954         typename std::iterator_traits<InputIterator>::value_type,
0955         boost::hash<typename std::iterator_traits<InputIterator>::value_type>,
0956         std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
0957         Allocator>;
0958 
0959     template <class InputIterator, class Hash, class Allocator,
0960       class = std::enable_if_t<detail::is_hash_v<Hash> >,
0961       class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
0962       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0963     unordered_multiset(
0964       InputIterator, InputIterator, std::size_t, Hash, Allocator)
0965       -> unordered_multiset<
0966         typename std::iterator_traits<InputIterator>::value_type, Hash,
0967         std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
0968         Allocator>;
0969 
0970     template <class T, class Allocator,
0971       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0972     unordered_multiset(std::initializer_list<T>, std::size_t, Allocator)
0973       -> unordered_multiset<T, boost::hash<T>, std::equal_to<T>, Allocator>;
0974 
0975     template <class T, class Hash, class Allocator,
0976       class = std::enable_if_t<detail::is_hash_v<Hash> >,
0977       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0978     unordered_multiset(std::initializer_list<T>, std::size_t, Hash, Allocator)
0979       -> unordered_multiset<T, Hash, std::equal_to<T>, Allocator>;
0980 
0981     template <class InputIterator, class Allocator,
0982       class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
0983       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0984     unordered_multiset(InputIterator, InputIterator, Allocator)
0985       -> unordered_multiset<
0986         typename std::iterator_traits<InputIterator>::value_type,
0987         boost::hash<typename std::iterator_traits<InputIterator>::value_type>,
0988         std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
0989         Allocator>;
0990 
0991     template <class T, class Allocator,
0992       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0993     unordered_multiset(std::initializer_list<T>, Allocator)
0994       -> unordered_multiset<T, boost::hash<T>, std::equal_to<T>, Allocator>;
0995 
0996 #endif
0997 
0998     ////////////////////////////////////////////////////////////////////////////
0999     template <class T, class H, class P, class A>
1000     unordered_set<T, H, P, A>::unordered_set()
1001     {
1002     }
1003 
1004     template <class T, class H, class P, class A>
1005     unordered_set<T, H, P, A>::unordered_set(size_type n, const hasher& hf,
1006       const key_equal& eql, const allocator_type& a)
1007         : table_(n, hf, eql, a)
1008     {
1009     }
1010 
1011     template <class T, class H, class P, class A>
1012     template <class InputIt>
1013     unordered_set<T, H, P, A>::unordered_set(InputIt f, InputIt l, size_type n,
1014       const hasher& hf, const key_equal& eql, const allocator_type& a)
1015         : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
1016     {
1017       this->insert(f, l);
1018     }
1019 
1020     template <class T, class H, class P, class A>
1021     unordered_set<T, H, P, A>::unordered_set(unordered_set const& other)
1022         : table_(other.table_,
1023             unordered_set::value_allocator_traits::
1024               select_on_container_copy_construction(other.get_allocator()))
1025     {
1026       if (other.size()) {
1027         table_.copy_buckets(other.table_, std::true_type());
1028       }
1029     }
1030 
1031     template <class T, class H, class P, class A>
1032     unordered_set<T, H, P, A>::unordered_set(allocator_type const& a)
1033         : table_(boost::unordered::detail::default_bucket_count, hasher(),
1034             key_equal(), a)
1035     {
1036     }
1037 
1038     template <class T, class H, class P, class A>
1039     unordered_set<T, H, P, A>::unordered_set(
1040       unordered_set const& other, allocator_type const& a)
1041         : table_(other.table_, a)
1042     {
1043       if (other.table_.size_) {
1044         table_.copy_buckets(other.table_, std::true_type());
1045       }
1046     }
1047 
1048     template <class T, class H, class P, class A>
1049     unordered_set<T, H, P, A>::unordered_set(
1050       unordered_set&& other, allocator_type const& a)
1051         : table_(other.table_, a, boost::unordered::detail::move_tag())
1052     {
1053       table_.move_construct_buckets(other.table_);
1054     }
1055 
1056     template <class T, class H, class P, class A>
1057     unordered_set<T, H, P, A>::unordered_set(
1058       std::initializer_list<value_type> list, size_type n, const hasher& hf,
1059       const key_equal& eql, const allocator_type& a)
1060         : table_(
1061             boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1062             hf, eql, a)
1063     {
1064       this->insert(list.begin(), list.end());
1065     }
1066 
1067     template <class T, class H, class P, class A>
1068     unordered_set<T, H, P, A>::unordered_set(
1069       size_type n, const allocator_type& a)
1070         : table_(n, hasher(), key_equal(), a)
1071     {
1072     }
1073 
1074     template <class T, class H, class P, class A>
1075     unordered_set<T, H, P, A>::unordered_set(
1076       size_type n, const hasher& hf, const allocator_type& a)
1077         : table_(n, hf, key_equal(), a)
1078     {
1079     }
1080 
1081     template <class T, class H, class P, class A>
1082     template <class InputIterator>
1083     unordered_set<T, H, P, A>::unordered_set(
1084       InputIterator f, InputIterator l, const allocator_type& a)
1085         : table_(boost::unordered::detail::initial_size(
1086                    f, l, detail::default_bucket_count),
1087             hasher(), key_equal(), a)
1088     {
1089       this->insert(f, l);
1090     }
1091 
1092     template <class T, class H, class P, class A>
1093     template <class InputIt>
1094     unordered_set<T, H, P, A>::unordered_set(
1095       InputIt f, InputIt l, size_type n, const allocator_type& a)
1096         : table_(boost::unordered::detail::initial_size(f, l, n), hasher(),
1097             key_equal(), a)
1098     {
1099       this->insert(f, l);
1100     }
1101 
1102     template <class T, class H, class P, class A>
1103     template <class InputIt>
1104     unordered_set<T, H, P, A>::unordered_set(InputIt f, InputIt l, size_type n,
1105       const hasher& hf, const allocator_type& a)
1106         : table_(
1107             boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a)
1108     {
1109       this->insert(f, l);
1110     }
1111 
1112     template <class T, class H, class P, class A>
1113     unordered_set<T, H, P, A>::unordered_set(
1114       std::initializer_list<value_type> list, const allocator_type& a)
1115         : table_(boost::unordered::detail::initial_size(
1116                    list.begin(), list.end(), detail::default_bucket_count),
1117             hasher(), key_equal(), a)
1118     {
1119       this->insert(list.begin(), list.end());
1120     }
1121 
1122     template <class T, class H, class P, class A>
1123     unordered_set<T, H, P, A>::unordered_set(
1124       std::initializer_list<value_type> list, size_type n,
1125       const allocator_type& a)
1126         : table_(
1127             boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1128             hasher(), key_equal(), a)
1129     {
1130       this->insert(list.begin(), list.end());
1131     }
1132 
1133     template <class T, class H, class P, class A>
1134     unordered_set<T, H, P, A>::unordered_set(
1135       std::initializer_list<value_type> list, size_type n, const hasher& hf,
1136       const allocator_type& a)
1137         : table_(
1138             boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1139             hf, key_equal(), a)
1140     {
1141       this->insert(list.begin(), list.end());
1142     }
1143 
1144     template <class T, class H, class P, class A>
1145     unordered_set<T, H, P, A>::~unordered_set() noexcept
1146     {
1147     }
1148 
1149     template <class T, class H, class P, class A>
1150     unordered_set<T, H, P, A>& unordered_set<T, H, P, A>::operator=(
1151       std::initializer_list<value_type> list)
1152     {
1153       this->clear();
1154       this->insert(list.begin(), list.end());
1155       return *this;
1156     }
1157 
1158     // size and capacity
1159 
1160     template <class T, class H, class P, class A>
1161     std::size_t unordered_set<T, H, P, A>::max_size() const noexcept
1162     {
1163       using namespace std;
1164 
1165       // size < mlf_ * count
1166       return boost::unordered::detail::double_to_size(
1167                ceil(static_cast<double>(table_.mlf_) *
1168                     static_cast<double>(table_.max_bucket_count()))) -
1169              1;
1170     }
1171 
1172     // modifiers
1173 
1174     template <class T, class H, class P, class A>
1175     template <class InputIt>
1176     void unordered_set<T, H, P, A>::insert(InputIt first, InputIt last)
1177     {
1178       if (first != last) {
1179         table_.insert_range_unique(
1180           table::extractor::extract(*first), first, last);
1181       }
1182     }
1183 
1184     template <class T, class H, class P, class A>
1185     void unordered_set<T, H, P, A>::insert(
1186       std::initializer_list<value_type> list)
1187     {
1188       this->insert(list.begin(), list.end());
1189     }
1190 
1191     template <class T, class H, class P, class A>
1192     typename unordered_set<T, H, P, A>::iterator
1193     unordered_set<T, H, P, A>::erase(const_iterator position)
1194     {
1195       return table_.erase_node(position);
1196     }
1197 
1198     template <class T, class H, class P, class A>
1199     typename unordered_set<T, H, P, A>::size_type
1200     unordered_set<T, H, P, A>::erase(const key_type& k)
1201     {
1202       return table_.erase_key_unique_impl(k);
1203     }
1204 
1205     template <class T, class H, class P, class A>
1206     typename unordered_set<T, H, P, A>::iterator
1207     unordered_set<T, H, P, A>::erase(const_iterator first, const_iterator last)
1208     {
1209       return table_.erase_nodes_range(first, last);
1210     }
1211 
1212     template <class T, class H, class P, class A>
1213     void unordered_set<T, H, P, A>::swap(unordered_set& other)
1214       noexcept(value_allocator_traits::is_always_equal::value&&
1215           boost::unordered::detail::is_nothrow_swappable<H>::value&&
1216             boost::unordered::detail::is_nothrow_swappable<P>::value)
1217     {
1218       table_.swap(other.table_);
1219     }
1220 
1221     // observers
1222 
1223     template <class T, class H, class P, class A>
1224     typename unordered_set<T, H, P, A>::hasher
1225     unordered_set<T, H, P, A>::hash_function() const
1226     {
1227       return table_.hash_function();
1228     }
1229 
1230     template <class T, class H, class P, class A>
1231     typename unordered_set<T, H, P, A>::key_equal
1232     unordered_set<T, H, P, A>::key_eq() const
1233     {
1234       return table_.key_eq();
1235     }
1236 
1237     template <class T, class H, class P, class A>
1238     template <typename H2, typename P2>
1239     void unordered_set<T, H, P, A>::merge(
1240       boost::unordered_set<T, H2, P2, A>& source)
1241     {
1242       table_.merge_unique(source.table_);
1243     }
1244 
1245     template <class T, class H, class P, class A>
1246     template <typename H2, typename P2>
1247     void unordered_set<T, H, P, A>::merge(
1248       boost::unordered_set<T, H2, P2, A>&& source)
1249     {
1250       table_.merge_unique(source.table_);
1251     }
1252 
1253     template <class T, class H, class P, class A>
1254     template <typename H2, typename P2>
1255     void unordered_set<T, H, P, A>::merge(
1256       boost::unordered_multiset<T, H2, P2, A>& source)
1257     {
1258       table_.merge_unique(source.table_);
1259     }
1260 
1261     template <class T, class H, class P, class A>
1262     template <typename H2, typename P2>
1263     void unordered_set<T, H, P, A>::merge(
1264       boost::unordered_multiset<T, H2, P2, A>&& source)
1265     {
1266       table_.merge_unique(source.table_);
1267     }
1268 
1269     // lookup
1270 
1271     template <class T, class H, class P, class A>
1272     typename unordered_set<T, H, P, A>::const_iterator
1273     unordered_set<T, H, P, A>::find(const key_type& k) const
1274     {
1275       return const_iterator(table_.find(k));
1276     }
1277 
1278     template <class T, class H, class P, class A>
1279     template <class CompatibleKey, class CompatibleHash,
1280       class CompatiblePredicate>
1281     typename unordered_set<T, H, P, A>::const_iterator
1282     unordered_set<T, H, P, A>::find(CompatibleKey const& k,
1283       CompatibleHash const& hash, CompatiblePredicate const& eq) const
1284     {
1285       return table_.transparent_find(k, hash, eq);
1286     }
1287 
1288     template <class T, class H, class P, class A>
1289     typename unordered_set<T, H, P, A>::size_type
1290     unordered_set<T, H, P, A>::count(const key_type& k) const
1291     {
1292       return table_.find_node(k) ? 1 : 0;
1293     }
1294 
1295     template <class T, class H, class P, class A>
1296     std::pair<typename unordered_set<T, H, P, A>::const_iterator,
1297       typename unordered_set<T, H, P, A>::const_iterator>
1298     unordered_set<T, H, P, A>::equal_range(const key_type& k) const
1299     {
1300       iterator first = table_.find(k);
1301       iterator second = first;
1302       if (second != this->end()) {
1303         ++second;
1304       }
1305       return std::make_pair(first, second);
1306     }
1307 
1308     template <class T, class H, class P, class A>
1309     typename unordered_set<T, H, P, A>::size_type
1310     unordered_set<T, H, P, A>::bucket_size(size_type n) const
1311     {
1312       return table_.bucket_size(n);
1313     }
1314 
1315     // hash policy
1316 
1317     template <class T, class H, class P, class A>
1318     float unordered_set<T, H, P, A>::load_factor() const noexcept
1319     {
1320       if (table_.size_ == 0) {
1321         return 0.0f;
1322       }
1323 
1324       BOOST_ASSERT(table_.bucket_count() != 0);
1325       return static_cast<float>(table_.size_) /
1326              static_cast<float>(table_.bucket_count());
1327     }
1328 
1329     template <class T, class H, class P, class A>
1330     void unordered_set<T, H, P, A>::max_load_factor(float m) noexcept
1331     {
1332       table_.max_load_factor(m);
1333     }
1334 
1335     template <class T, class H, class P, class A>
1336     void unordered_set<T, H, P, A>::rehash(size_type n)
1337     {
1338       table_.rehash(n);
1339     }
1340 
1341     template <class T, class H, class P, class A>
1342     void unordered_set<T, H, P, A>::reserve(size_type n)
1343     {
1344       table_.reserve(n);
1345     }
1346 
1347     template <class T, class H, class P, class A>
1348     inline bool operator==(
1349       unordered_set<T, H, P, A> const& m1, unordered_set<T, H, P, A> const& m2)
1350     {
1351 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
1352       struct dummy
1353       {
1354         unordered_set<T, H, P, A> x;
1355       };
1356 #endif
1357       return m1.table_.equals_unique(m2.table_);
1358     }
1359 
1360     template <class T, class H, class P, class A>
1361     inline bool operator!=(
1362       unordered_set<T, H, P, A> const& m1, unordered_set<T, H, P, A> const& m2)
1363     {
1364 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
1365       struct dummy
1366       {
1367         unordered_set<T, H, P, A> x;
1368       };
1369 #endif
1370       return !m1.table_.equals_unique(m2.table_);
1371     }
1372 
1373     template <class T, class H, class P, class A>
1374     inline void swap(unordered_set<T, H, P, A>& m1,
1375       unordered_set<T, H, P, A>& m2) noexcept(noexcept(m1.swap(m2)))
1376     {
1377 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
1378       struct dummy
1379       {
1380         unordered_set<T, H, P, A> x;
1381       };
1382 #endif
1383       m1.swap(m2);
1384     }
1385 
1386     template <class K, class H, class P, class A, class Predicate>
1387     typename unordered_set<K, H, P, A>::size_type erase_if(
1388       unordered_set<K, H, P, A>& c, Predicate pred)
1389     {
1390       return detail::erase_if(c, pred);
1391     }
1392 
1393     ////////////////////////////////////////////////////////////////////////////
1394 
1395     template <class T, class H, class P, class A>
1396     unordered_multiset<T, H, P, A>::unordered_multiset()
1397     {
1398     }
1399 
1400     template <class T, class H, class P, class A>
1401     unordered_multiset<T, H, P, A>::unordered_multiset(size_type n,
1402       const hasher& hf, const key_equal& eql, const allocator_type& a)
1403         : table_(n, hf, eql, a)
1404     {
1405     }
1406 
1407     template <class T, class H, class P, class A>
1408     template <class InputIt>
1409     unordered_multiset<T, H, P, A>::unordered_multiset(InputIt f, InputIt l,
1410       size_type n, const hasher& hf, const key_equal& eql,
1411       const allocator_type& a)
1412         : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
1413     {
1414       this->insert(f, l);
1415     }
1416 
1417     template <class T, class H, class P, class A>
1418     unordered_multiset<T, H, P, A>::unordered_multiset(
1419       unordered_multiset const& other)
1420         : table_(other.table_,
1421             unordered_multiset::value_allocator_traits::
1422               select_on_container_copy_construction(other.get_allocator()))
1423     {
1424       if (other.table_.size_) {
1425         table_.copy_buckets(other.table_, std::false_type());
1426       }
1427     }
1428 
1429     template <class T, class H, class P, class A>
1430     unordered_multiset<T, H, P, A>::unordered_multiset(allocator_type const& a)
1431         : table_(boost::unordered::detail::default_bucket_count, hasher(),
1432             key_equal(), a)
1433     {
1434     }
1435 
1436     template <class T, class H, class P, class A>
1437     unordered_multiset<T, H, P, A>::unordered_multiset(
1438       unordered_multiset const& other, allocator_type const& a)
1439         : table_(other.table_, a)
1440     {
1441       if (other.table_.size_) {
1442         table_.copy_buckets(other.table_, std::false_type());
1443       }
1444     }
1445 
1446     template <class T, class H, class P, class A>
1447     unordered_multiset<T, H, P, A>::unordered_multiset(
1448       unordered_multiset&& other, allocator_type const& a)
1449         : table_(other.table_, a, boost::unordered::detail::move_tag())
1450     {
1451       table_.move_construct_buckets(other.table_);
1452     }
1453 
1454     template <class T, class H, class P, class A>
1455     unordered_multiset<T, H, P, A>::unordered_multiset(
1456       std::initializer_list<value_type> list, size_type n, const hasher& hf,
1457       const key_equal& eql, const allocator_type& a)
1458         : table_(
1459             boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1460             hf, eql, a)
1461     {
1462       this->insert(list.begin(), list.end());
1463     }
1464 
1465     template <class T, class H, class P, class A>
1466     unordered_multiset<T, H, P, A>::unordered_multiset(
1467       size_type n, const allocator_type& a)
1468         : table_(n, hasher(), key_equal(), a)
1469     {
1470     }
1471 
1472     template <class T, class H, class P, class A>
1473     unordered_multiset<T, H, P, A>::unordered_multiset(
1474       size_type n, const hasher& hf, const allocator_type& a)
1475         : table_(n, hf, key_equal(), a)
1476     {
1477     }
1478 
1479     template <class T, class H, class P, class A>
1480     template <class InputIterator>
1481     unordered_multiset<T, H, P, A>::unordered_multiset(
1482       InputIterator f, InputIterator l, const allocator_type& a)
1483         : table_(boost::unordered::detail::initial_size(
1484                    f, l, detail::default_bucket_count),
1485             hasher(), key_equal(), a)
1486     {
1487       this->insert(f, l);
1488     }
1489 
1490     template <class T, class H, class P, class A>
1491     template <class InputIt>
1492     unordered_multiset<T, H, P, A>::unordered_multiset(
1493       InputIt f, InputIt l, size_type n, const allocator_type& a)
1494         : table_(boost::unordered::detail::initial_size(f, l, n), hasher(),
1495             key_equal(), a)
1496     {
1497       this->insert(f, l);
1498     }
1499 
1500     template <class T, class H, class P, class A>
1501     template <class InputIt>
1502     unordered_multiset<T, H, P, A>::unordered_multiset(InputIt f, InputIt l,
1503       size_type n, const hasher& hf, const allocator_type& a)
1504         : table_(
1505             boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a)
1506     {
1507       this->insert(f, l);
1508     }
1509 
1510     template <class T, class H, class P, class A>
1511     unordered_multiset<T, H, P, A>::unordered_multiset(
1512       std::initializer_list<value_type> list, const allocator_type& a)
1513         : table_(boost::unordered::detail::initial_size(
1514                    list.begin(), list.end(), detail::default_bucket_count),
1515             hasher(), key_equal(), a)
1516     {
1517       this->insert(list.begin(), list.end());
1518     }
1519 
1520     template <class T, class H, class P, class A>
1521     unordered_multiset<T, H, P, A>::unordered_multiset(
1522       std::initializer_list<value_type> list, size_type n,
1523       const allocator_type& a)
1524         : table_(
1525             boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1526             hasher(), key_equal(), a)
1527     {
1528       this->insert(list.begin(), list.end());
1529     }
1530 
1531     template <class T, class H, class P, class A>
1532     unordered_multiset<T, H, P, A>::unordered_multiset(
1533       std::initializer_list<value_type> list, size_type n, const hasher& hf,
1534       const allocator_type& a)
1535         : table_(
1536             boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1537             hf, key_equal(), a)
1538     {
1539       this->insert(list.begin(), list.end());
1540     }
1541 
1542     template <class T, class H, class P, class A>
1543     unordered_multiset<T, H, P, A>::~unordered_multiset() noexcept
1544     {
1545     }
1546 
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)
1550     {
1551       this->clear();
1552       this->insert(list.begin(), list.end());
1553       return *this;
1554     }
1555 
1556     // size and capacity
1557 
1558     template <class T, class H, class P, class A>
1559     std::size_t unordered_multiset<T, H, P, A>::max_size() const noexcept
1560     {
1561       using namespace std;
1562 
1563       // size < mlf_ * count
1564       return boost::unordered::detail::double_to_size(
1565                ceil(static_cast<double>(table_.mlf_) *
1566                     static_cast<double>(table_.max_bucket_count()))) -
1567              1;
1568     }
1569 
1570     // modifiers
1571 
1572     template <class T, class H, class P, class A>
1573     template <class InputIt>
1574     void unordered_multiset<T, H, P, A>::insert(InputIt first, InputIt last)
1575     {
1576       table_.insert_range_equiv(first, last);
1577     }
1578 
1579     template <class T, class H, class P, class A>
1580     void unordered_multiset<T, H, P, A>::insert(
1581       std::initializer_list<value_type> list)
1582     {
1583       this->insert(list.begin(), list.end());
1584     }
1585 
1586     template <class T, class H, class P, class A>
1587     typename unordered_multiset<T, H, P, A>::iterator
1588     unordered_multiset<T, H, P, A>::erase(const_iterator position)
1589     {
1590       BOOST_ASSERT(position != this->end());
1591       return table_.erase_node(position);
1592     }
1593 
1594     template <class T, class H, class P, class A>
1595     typename unordered_multiset<T, H, P, A>::size_type
1596     unordered_multiset<T, H, P, A>::erase(const key_type& k)
1597     {
1598       return table_.erase_key_equiv(k);
1599     }
1600 
1601     template <class T, class H, class P, class A>
1602     typename unordered_multiset<T, H, P, A>::iterator
1603     unordered_multiset<T, H, P, A>::erase(
1604       const_iterator first, const_iterator last)
1605     {
1606       return table_.erase_nodes_range(first, last);
1607     }
1608 
1609     template <class T, class H, class P, class A>
1610     void unordered_multiset<T, H, P, A>::swap(unordered_multiset& other)
1611       noexcept(value_allocator_traits::is_always_equal::value&&
1612           boost::unordered::detail::is_nothrow_swappable<H>::value&&
1613             boost::unordered::detail::is_nothrow_swappable<P>::value)
1614     {
1615       table_.swap(other.table_);
1616     }
1617 
1618     // observers
1619 
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
1623     {
1624       return table_.hash_function();
1625     }
1626 
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
1630     {
1631       return table_.key_eq();
1632     }
1633 
1634     template <class T, class H, class P, class A>
1635     template <typename H2, typename P2>
1636     void unordered_multiset<T, H, P, A>::merge(
1637       boost::unordered_multiset<T, H2, P2, A>& source)
1638     {
1639       while (!source.empty()) {
1640         insert(source.extract(source.begin()));
1641       }
1642     }
1643 
1644     template <class T, class H, class P, class A>
1645     template <typename H2, typename P2>
1646     void unordered_multiset<T, H, P, A>::merge(
1647       boost::unordered_multiset<T, H2, P2, A>&& source)
1648     {
1649       while (!source.empty()) {
1650         insert(source.extract(source.begin()));
1651       }
1652     }
1653 
1654     template <class T, class H, class P, class A>
1655     template <typename H2, typename P2>
1656     void unordered_multiset<T, H, P, A>::merge(
1657       boost::unordered_set<T, H2, P2, A>& source)
1658     {
1659       while (!source.empty()) {
1660         insert(source.extract(source.begin()));
1661       }
1662     }
1663 
1664     template <class T, class H, class P, class A>
1665     template <typename H2, typename P2>
1666     void unordered_multiset<T, H, P, A>::merge(
1667       boost::unordered_set<T, H2, P2, A>&& source)
1668     {
1669       while (!source.empty()) {
1670         insert(source.extract(source.begin()));
1671       }
1672     }
1673 
1674     // lookup
1675 
1676     template <class T, class H, class P, class A>
1677     typename unordered_multiset<T, H, P, A>::const_iterator
1678     unordered_multiset<T, H, P, A>::find(const key_type& k) const
1679     {
1680       return const_iterator(table_.find(k));
1681     }
1682 
1683     template <class T, class H, class P, class A>
1684     template <class CompatibleKey, class CompatibleHash,
1685       class CompatiblePredicate>
1686     typename unordered_multiset<T, H, P, A>::const_iterator
1687     unordered_multiset<T, H, P, A>::find(CompatibleKey const& k,
1688       CompatibleHash const& hash, CompatiblePredicate const& eq) const
1689     {
1690       return table_.transparent_find(k, hash, eq);
1691     }
1692 
1693     template <class T, class H, class P, class A>
1694     typename unordered_multiset<T, H, P, A>::size_type
1695     unordered_multiset<T, H, P, A>::count(const key_type& k) const
1696     {
1697       return table_.group_count(k);
1698     }
1699 
1700     template <class T, class H, class P, class A>
1701     std::pair<typename unordered_multiset<T, H, P, A>::const_iterator,
1702       typename unordered_multiset<T, H, P, A>::const_iterator>
1703     unordered_multiset<T, H, P, A>::equal_range(const key_type& k) const
1704     {
1705       iterator n = table_.find(k);
1706       return std::make_pair(const_iterator(n),
1707         const_iterator(n == end() ? n : table_.next_group(k, n)));
1708     }
1709 
1710     template <class T, class H, class P, class A>
1711     typename unordered_multiset<T, H, P, A>::size_type
1712     unordered_multiset<T, H, P, A>::bucket_size(size_type n) const
1713     {
1714       return table_.bucket_size(n);
1715     }
1716 
1717     // hash policy
1718 
1719     template <class T, class H, class P, class A>
1720     float unordered_multiset<T, H, P, A>::load_factor() const noexcept
1721     {
1722       if (table_.size_ == 0) {
1723         return 0.0f;
1724       }
1725 
1726       BOOST_ASSERT(table_.bucket_count() != 0);
1727       return static_cast<float>(table_.size_) /
1728              static_cast<float>(table_.bucket_count());
1729     }
1730 
1731     template <class T, class H, class P, class A>
1732     void unordered_multiset<T, H, P, A>::max_load_factor(float m) noexcept
1733     {
1734       table_.max_load_factor(m);
1735     }
1736 
1737     template <class T, class H, class P, class A>
1738     void unordered_multiset<T, H, P, A>::rehash(size_type n)
1739     {
1740       table_.rehash(n);
1741     }
1742 
1743     template <class T, class H, class P, class A>
1744     void unordered_multiset<T, H, P, A>::reserve(size_type n)
1745     {
1746       table_.reserve(n);
1747     }
1748 
1749     template <class T, class H, class P, class A>
1750     inline bool operator==(unordered_multiset<T, H, P, A> const& m1,
1751       unordered_multiset<T, H, P, A> const& m2)
1752     {
1753 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
1754       struct dummy
1755       {
1756         unordered_multiset<T, H, P, A> x;
1757       };
1758 #endif
1759       return m1.table_.equals_equiv(m2.table_);
1760     }
1761 
1762     template <class T, class H, class P, class A>
1763     inline bool operator!=(unordered_multiset<T, H, P, A> const& m1,
1764       unordered_multiset<T, H, P, A> const& m2)
1765     {
1766 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
1767       struct dummy
1768       {
1769         unordered_multiset<T, H, P, A> x;
1770       };
1771 #endif
1772       return !m1.table_.equals_equiv(m2.table_);
1773     }
1774 
1775     template <class T, class H, class P, class A>
1776     inline void swap(unordered_multiset<T, H, P, A>& m1,
1777       unordered_multiset<T, H, P, A>& m2) noexcept(noexcept(m1.swap(m2)))
1778     {
1779 #if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
1780       struct dummy
1781       {
1782         unordered_multiset<T, H, P, A> x;
1783       };
1784 #endif
1785       m1.swap(m2);
1786     }
1787 
1788     template <class K, class H, class P, class A, class Predicate>
1789     typename unordered_multiset<K, H, P, A>::size_type erase_if(
1790       unordered_multiset<K, H, P, A>& c, Predicate pred)
1791     {
1792       return detail::erase_if(c, pred);
1793     }
1794 
1795     template <typename N, typename T, typename A> class node_handle_set
1796     {
1797       template <typename Types> friend struct ::boost::unordered::detail::table;
1798       template <class T2, class H2, class P2, class A2>
1799       friend class unordered_set;
1800       template <class T2, class H2, class P2, class A2>
1801       friend class unordered_multiset;
1802 
1803       typedef typename boost::unordered::detail::rebind_wrap<A, T>::type
1804         value_allocator;
1805       typedef boost::unordered::detail::allocator_traits<value_allocator>
1806         value_allocator_traits;
1807       typedef N node;
1808       typedef typename boost::unordered::detail::rebind_wrap<A, node>::type
1809         node_allocator;
1810       typedef boost::unordered::detail::allocator_traits<node_allocator>
1811         node_allocator_traits;
1812       typedef typename node_allocator_traits::pointer node_pointer;
1813 
1814     public:
1815       typedef T value_type;
1816       typedef A allocator_type;
1817 
1818     private:
1819       node_pointer ptr_;
1820       bool has_alloc_;
1821       boost::unordered::detail::optional<value_allocator> alloc_;
1822 
1823       node_handle_set(node_pointer ptr, allocator_type const& a)
1824           : ptr_(ptr), alloc_(a)
1825       {
1826       }
1827 
1828     public:
1829       constexpr node_handle_set() noexcept : ptr_(), has_alloc_(false) {}
1830       node_handle_set(node_handle_set const&) = delete;
1831       node_handle_set& operator=(node_handle_set const&) = delete;
1832 
1833       ~node_handle_set()
1834       {
1835         if (ptr_) {
1836           node_allocator node_alloc(*alloc_);
1837           boost::unordered::detail::node_tmp<node_allocator> tmp(
1838             ptr_, node_alloc);
1839         }
1840       }
1841 
1842       node_handle_set(node_handle_set&& n) noexcept
1843           : ptr_(n.ptr_),
1844             alloc_(std::move(n.alloc_))
1845       {
1846         n.ptr_ = node_pointer();
1847       }
1848 
1849       node_handle_set& operator=(node_handle_set&& n)
1850       {
1851         BOOST_ASSERT(!alloc_.has_value() ||
1852                      value_allocator_traits::
1853                        propagate_on_container_move_assignment::value ||
1854                      (n.alloc_.has_value() && alloc_ == n.alloc_));
1855 
1856         if (ptr_) {
1857           node_allocator node_alloc(*alloc_);
1858           boost::unordered::detail::node_tmp<node_allocator> tmp(
1859             ptr_, node_alloc);
1860           ptr_ = node_pointer();
1861         }
1862 
1863         if (!alloc_.has_value() ||
1864             value_allocator_traits::propagate_on_container_move_assignment::
1865               value) {
1866           alloc_ = std::move(n.alloc_);
1867         }
1868         ptr_ = n.ptr_;
1869         n.ptr_ = node_pointer();
1870 
1871         return *this;
1872       }
1873 
1874       value_type& value() const { return ptr_->value(); }
1875 
1876       allocator_type get_allocator() const { return *alloc_; }
1877 
1878       explicit operator bool() const noexcept
1879       {
1880         return !this->operator!();
1881       }
1882 
1883       bool operator!() const noexcept { return ptr_ ? 0 : 1; }
1884 
1885       BOOST_ATTRIBUTE_NODISCARD bool empty() const noexcept
1886       {
1887         return ptr_ ? 0 : 1;
1888       }
1889 
1890       void swap(node_handle_set& n)
1891         noexcept(value_allocator_traits::propagate_on_container_swap::value ||
1892                  value_allocator_traits::is_always_equal::value)
1893       {
1894         BOOST_ASSERT(
1895           !alloc_.has_value() || !n.alloc_.has_value() ||
1896           value_allocator_traits::propagate_on_container_swap::value ||
1897           alloc_ == n.alloc_);
1898         if (value_allocator_traits::propagate_on_container_swap::value ||
1899             !alloc_.has_value() || !n.alloc_.has_value()) {
1900           boost::core::invoke_swap(alloc_, n.alloc_);
1901         }
1902         boost::core::invoke_swap(ptr_, n.ptr_);
1903       }
1904     };
1905 
1906     template <typename N, typename T, typename A>
1907     void swap(node_handle_set<N, T, A>& x, node_handle_set<N, T, A>& y)
1908       noexcept(noexcept(x.swap(y)))
1909     {
1910       x.swap(y);
1911     }
1912 
1913     template <class Iter, class NodeType> struct insert_return_type_set
1914     {
1915     public:
1916       Iter position;
1917       bool inserted;
1918       NodeType node;
1919 
1920       insert_return_type_set() : position(), inserted(false), node() {}
1921       insert_return_type_set(insert_return_type_set const&) = delete;
1922       insert_return_type_set& operator=(insert_return_type_set const&) = delete;
1923 
1924       insert_return_type_set(insert_return_type_set&& x) noexcept
1925           : position(x.position),
1926             inserted(x.inserted),
1927             node(std::move(x.node))
1928       {
1929       }
1930 
1931       insert_return_type_set& operator=(insert_return_type_set&& x)
1932       {
1933         inserted = x.inserted;
1934         position = x.position;
1935         node = std::move(x.node);
1936         return *this;
1937       }
1938     };
1939 
1940     template <class Iter, class NodeType>
1941     void swap(insert_return_type_set<Iter, NodeType>& x,
1942       insert_return_type_set<Iter, NodeType>& y)
1943     {
1944       boost::core::invoke_swap(x.node, y.node);
1945       boost::core::invoke_swap(x.inserted, y.inserted);
1946       boost::core::invoke_swap(x.position, y.position);
1947     }
1948   } // namespace unordered
1949 
1950   namespace serialization {
1951     template <class K, class H, class P, class A>
1952     struct version<boost::unordered_set<K, H, P, A> >
1953     {
1954       BOOST_STATIC_CONSTANT(int, value = 1);
1955     };
1956 
1957     template <class K, class H, class P, class A>
1958     struct version<boost::unordered_multiset<K, H, P, A> >
1959     {
1960       BOOST_STATIC_CONSTANT(int, value = 1);
1961     };
1962   } // namespace serialization
1963 
1964 } // namespace boost
1965 
1966 #if defined(BOOST_MSVC)
1967 #pragma warning(pop)
1968 #endif
1969 
1970 #endif // BOOST_UNORDERED_UNORDERED_SET_HPP_INCLUDED
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!