Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-07-12 08:31:46 

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