EIC code displayed by LXR master/​include/​boost/​unordered/​detail/​implementation.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-07-15 08:51:08

 // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
 // Copyright (C) 2005-2016 Daniel James
 // Copyright (C) 2022-2024 Joaquin M Lopez Munoz.
 // Copyright (C) 2022-2023 Christian Mazakas
 // Copyright (C) 2024 Braden Ganetsky
 //
 // Distributed under the Boost Software License, Version 1.0. (See accompanying
 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 
 #ifndef BOOST_UNORDERED_DETAIL_IMPLEMENTATION_HPP
 #define BOOST_UNORDERED_DETAIL_IMPLEMENTATION_HPP
 
 #include <boost/config.hpp>
 #if defined(BOOST_HAS_PRAGMA_ONCE)
 #pragma once
 #endif
 
 #include <boost/unordered/detail/allocator_constructed.hpp>
 #include <boost/unordered/detail/fca.hpp>
 #include <boost/unordered/detail/opt_storage.hpp>
 #include <boost/unordered/detail/serialize_tracked_address.hpp>
 #include <boost/unordered/detail/static_assert.hpp>
 #include <boost/unordered/detail/type_traits.hpp>
 
 #include <boost/assert.hpp>
 #include <boost/core/allocator_traits.hpp>
 #include <boost/core/bit.hpp>
 #include <boost/core/invoke_swap.hpp>
 #include <boost/core/no_exceptions_support.hpp>
 #include <boost/core/pointer_traits.hpp>
 #include <boost/core/serialization.hpp>
 #include <boost/mp11/algorithm.hpp>
 #include <boost/mp11/list.hpp>
 #include <boost/throw_exception.hpp>
 
 #include <algorithm>
 #include <cmath>
 #include <iterator>
 #include <limits>
 #include <stdexcept>
 #include <type_traits>
 #include <utility>
 #include <tuple> // std::forward_as_tuple
 
 namespace boost {
   namespace tuples {
     struct null_type;
   }
 } // namespace boost
 
 // BOOST_UNORDERED_SUPPRESS_DEPRECATED
 //
 // Define to stop deprecation attributes
 
 #if defined(BOOST_UNORDERED_SUPPRESS_DEPRECATED)
 #define BOOST_UNORDERED_DEPRECATED(msg)
 #endif
 
 // BOOST_UNORDERED_DEPRECATED
 //
 // Wrapper around various depreaction attributes.
 
 #if defined(__has_cpp_attribute) &&                                            \
   (!defined(__cplusplus) || __cplusplus >= 201402)
 #if __has_cpp_attribute(deprecated) && !defined(BOOST_UNORDERED_DEPRECATED)
 #define BOOST_UNORDERED_DEPRECATED(msg) [[deprecated(msg)]]
 #endif
 #endif
 
 #if !defined(BOOST_UNORDERED_DEPRECATED)
 #if defined(__GNUC__) && __GNUC__ >= 4
 #define BOOST_UNORDERED_DEPRECATED(msg) __attribute__((deprecated))
 #elif defined(_MSC_VER) && _MSC_VER >= 1400
 #define BOOST_UNORDERED_DEPRECATED(msg) __declspec(deprecated(msg))
 #elif defined(_MSC_VER) && _MSC_VER >= 1310
 #define BOOST_UNORDERED_DEPRECATED(msg) __declspec(deprecated)
 #else
 #define BOOST_UNORDERED_DEPRECATED(msg)
 #endif
 #endif
 
 namespace boost {
   namespace unordered {
 
     using std::piecewise_construct;
     using std::piecewise_construct_t;
 
     namespace detail {
 
       template <typename Types> struct table;
 
       static const float minimum_max_load_factor = 1e-3f;
       static const std::size_t default_bucket_count = 0;
 
       struct move_tag
       {
       };
 
       struct empty_emplace
       {
       };
 
       struct no_key
       {
         no_key() {}
         template <class T> no_key(T const&) {}
       };
 
       struct converting_key
       {
       };
 
       namespace func {
         template <class T> inline void ignore_unused_variable_warning(T const&)
         {
         }
       } // namespace func
 
       //////////////////////////////////////////////////////////////////////////
       // iterator SFINAE
 
       template <typename I>
       struct is_forward : std::is_base_of<std::forward_iterator_tag,
                             typename std::iterator_traits<I>::iterator_category>
       {
       };
 
       template <typename I, typename ReturnType>
       struct enable_if_forward
           : std::enable_if<boost::unordered::detail::is_forward<I>::value,
               ReturnType>
       {
       };
 
       template <typename I, typename ReturnType>
       struct disable_if_forward
           : std::enable_if<!boost::unordered::detail::is_forward<I>::value,
               ReturnType>
       {
       };
     } // namespace detail
   } // namespace unordered
 } // namespace boost
 
 namespace boost {
   namespace unordered {
     namespace detail {
       //////////////////////////////////////////////////////////////////////////
       // insert_size/initial_size
 
       template <class I>
       inline typename boost::unordered::detail::enable_if_forward<I,
         std::size_t>::type
       insert_size(I i, I j)
       {
         return static_cast<std::size_t>(std::distance(i, j));
       }
 
       template <class I>
       inline typename boost::unordered::detail::disable_if_forward<I,
         std::size_t>::type
       insert_size(I, I)
       {
         return 1;
       }
 
       template <class I>
       inline std::size_t initial_size(I i, I j,
         std::size_t num_buckets =
           boost::unordered::detail::default_bucket_count)
       {
         return (std::max)(
           boost::unordered::detail::insert_size(i, j), num_buckets);
       }
 
       //////////////////////////////////////////////////////////////////////////
       // compressed
 
       template <typename T, int Index>
       struct compressed_base : boost::empty_value<T>
       {
         compressed_base(T const& x) : empty_value<T>(boost::empty_init_t(), x)
         {
         }
         compressed_base(T& x, move_tag)
             : empty_value<T>(boost::empty_init_t(), std::move(x))
         {
         }
 
         T& get() { return empty_value<T>::get(); }
         T const& get() const { return empty_value<T>::get(); }
       };
 
       template <typename T, int Index>
       struct generate_base : boost::unordered::detail::compressed_base<T, Index>
       {
         typedef compressed_base<T, Index> type;
 
         generate_base() : type() {}
       };
 
       template <typename T1, typename T2>
       struct compressed
           : private boost::unordered::detail::generate_base<T1, 1>::type,
             private boost::unordered::detail::generate_base<T2, 2>::type
       {
         typedef typename generate_base<T1, 1>::type base1;
         typedef typename generate_base<T2, 2>::type base2;
 
         typedef T1 first_type;
         typedef T2 second_type;
 
         first_type& first() { return static_cast<base1*>(this)->get(); }
 
         first_type const& first() const
         {
           return static_cast<base1 const*>(this)->get();
         }
 
         second_type& second() { return static_cast<base2*>(this)->get(); }
 
         second_type const& second() const
         {
           return static_cast<base2 const*>(this)->get();
         }
 
         template <typename First, typename Second>
         compressed(First const& x1, Second const& x2) : base1(x1), base2(x2)
         {
         }
 
         compressed(compressed const& x) : base1(x.first()), base2(x.second()) {}
 
         compressed(compressed& x, move_tag m)
             : base1(x.first(), m), base2(x.second(), m)
         {
         }
 
         void assign(compressed const& x)
         {
           first() = x.first();
           second() = x.second();
         }
 
         void move_assign(compressed& x)
         {
           first() = std::move(x.first());
           second() = std::move(x.second());
         }
 
         void swap(compressed& x)
         {
           boost::core::invoke_swap(first(), x.first());
           boost::core::invoke_swap(second(), x.second());
         }
 
       private:
         // Prevent assignment just to make use of assign or
         // move_assign explicit.
         compressed& operator=(compressed const&);
       };
 
       //////////////////////////////////////////////////////////////////////////
       // pair_traits
       //
       // Used to get the types from a pair without instantiating it.
 
       template <typename Pair> struct pair_traits
       {
         typedef typename Pair::first_type first_type;
         typedef typename Pair::second_type second_type;
       };
 
       template <typename T1, typename T2> struct pair_traits<std::pair<T1, T2> >
       {
         typedef T1 first_type;
         typedef T2 second_type;
       };
 
 #if defined(BOOST_MSVC)
 #pragma warning(push)
 #pragma warning(disable : 4512) // assignment operator could not be generated.
 #pragma warning(disable : 4345) // behavior change: an object of POD type
 // constructed with an initializer of the form ()
 // will be default-initialized.
 #endif
 
       //////////////////////////////////////////////////////////////////////////
       // Bits and pieces for implementing traits
 
       template <typename T> typename std::add_lvalue_reference<T>::type make();
       struct choice2
       {
         typedef char (&type)[2];
       };
       struct choice1 : choice2
       {
         typedef char (&type)[1];
       };
       choice1 choose();
 
       typedef choice1::type yes_type;
       typedef choice2::type no_type;
 
       struct private_type
       {
         private_type const& operator,(int) const;
       };
 
       template <typename T> no_type is_private_type(T const&);
       yes_type is_private_type(private_type const&);
 
       struct convert_from_anything
       {
         template <typename T> convert_from_anything(T const&);
       };
     } // namespace detail
   } // namespace unordered
 } // namespace boost
 
 ////////////////////////////////////////////////////////////////////////////////
 //
 // Some utilities for implementing allocator_traits, but useful elsewhere so
 // they're always defined.
 
 namespace boost {
   namespace unordered {
     namespace detail {
 
       ////////////////////////////////////////////////////////////////////////////
       // Explicitly call a destructor
 
 #if defined(BOOST_MSVC)
 #pragma warning(push)
 #pragma warning(disable : 4100) // unreferenced formal parameter
 #endif
 
       namespace func {
         template <class T> inline void destroy(T* x) { x->~T(); }
       } // namespace func
 
 #if defined(BOOST_MSVC)
 #pragma warning(pop)
 #endif
 
       //////////////////////////////////////////////////////////////////////////
       // value_base
       //
       // Space used to store values.
 
       template <typename ValueType> struct value_base
       {
         typedef ValueType value_type;
 
         opt_storage<value_type> data_;
 
         value_base() : data_() {}
 
         void* address() { return this; }
 
         value_type& value() { return *(ValueType*)this; }
 
         value_type const& value() const { return *(ValueType const*)this; }
 
         value_type* value_ptr() { return (ValueType*)this; }
 
         value_type const* value_ptr() const { return (ValueType const*)this; }
 
       private:
         value_base& operator=(value_base const&);
       };
 
       //////////////////////////////////////////////////////////////////////////
       // optional
       // TODO: Use std::optional when available.
 
       template <typename T> class optional
       {
         boost::unordered::detail::value_base<T> value_;
         bool has_value_;
 
         void destroy()
         {
           if (has_value_) {
             boost::unordered::detail::func::destroy(value_.value_ptr());
             has_value_ = false;
           }
         }
 
         void move(optional<T>& x)
         {
           BOOST_ASSERT(!has_value_ && x.has_value_);
           new (value_.value_ptr()) T(std::move(x.value_.value()));
           boost::unordered::detail::func::destroy(x.value_.value_ptr());
           has_value_ = true;
           x.has_value_ = false;
         }
 
       public:
         optional() noexcept : has_value_(false) {}
 
         optional(optional const&) = delete;
         optional& operator=(optional const&) = delete;
 
         optional(optional<T>&& x) : has_value_(false)
         {
           if (x.has_value_) {
             move(x);
           }
         }
 
         explicit optional(T const& x) : has_value_(true)
         {
           new (value_.value_ptr()) T(x);
         }
 
         optional& operator=(optional<T>&& x)
         {
           destroy();
           if (x.has_value_) {
             move(x);
           }
           return *this;
         }
 
         ~optional() { destroy(); }
 
         bool has_value() const { return has_value_; }
         T& operator*() { return value_.value(); }
         T const& operator*() const { return value_.value(); }
         T* operator->() { return value_.value_ptr(); }
         T const* operator->() const { return value_.value_ptr(); }
 
         bool operator==(optional<T> const& x) const
         {
           return has_value_ ? x.has_value_ && value_.value() == x.value_.value()
                             : !x.has_value_;
         }
 
         bool operator!=(optional<T> const& x) const { return !((*this) == x); }
 
         void swap(optional<T>& x)
         {
           if (has_value_ != x.has_value_) {
             if (has_value_) {
               x.move(*this);
             } else {
               move(x);
             }
           } else if (has_value_) {
             boost::core::invoke_swap(value_.value(), x.value_.value());
           }
         }
 
         friend void swap(optional<T>& x, optional<T>& y) { x.swap(y); }
       };
     } // namespace detail
   } // namespace unordered
 } // namespace boost
 
 ////////////////////////////////////////////////////////////////////////////////
 //
 // Allocator traits
 //
 
 namespace boost {
   namespace unordered {
     namespace detail {
 
       template <typename Alloc>
       struct allocator_traits : boost::allocator_traits<Alloc>
       {
       };
 
       template <typename Alloc, typename T>
       struct rebind_wrap : boost::allocator_rebind<Alloc, T>
       {
       };
     } // namespace detail
   } // namespace unordered
 } // namespace boost
 
 namespace boost {
   namespace unordered {
     namespace detail {
       namespace func {
         ////////////////////////////////////////////////////////////////////////
         // Trait to check for piecewise construction.
 
         template <typename A0> struct use_piecewise
         {
           static choice1::type test(choice1, std::piecewise_construct_t);
 
           static choice2::type test(choice2, ...);
 
           enum
           {
             value = sizeof(choice1::type) ==
                     sizeof(test(choose(), boost::unordered::detail::make<A0>()))
           };
         };
 
         ////////////////////////////////////////////////////////////////////////
         // Construct from variadic parameters
 
         template <typename Alloc, typename T, typename... Args>
         inline void construct_from_args(
           Alloc& alloc, T* address, Args&&... args)
         {
           boost::allocator_construct(
             alloc, address, std::forward<Args>(args)...);
         }
 
         // For backwards compatibility, implement a special case for
         // piecewise_construct with boost::tuple
 
         template <typename A0> struct detect_std_tuple
         {
           template <class... Args>
           static choice1::type test(choice1, std::tuple<Args...> const&);
 
           static choice2::type test(choice2, ...);
 
           enum
           {
             value = sizeof(choice1::type) ==
                     sizeof(test(choose(), boost::unordered::detail::make<A0>()))
           };
         };
 
         // Special case for piecewise_construct
 
         template <template <class...> class Tuple, class... Args,
           std::size_t... Is, class... TupleArgs>
         std::tuple<typename std::add_lvalue_reference<Args>::type...>
         to_std_tuple_impl(boost::mp11::mp_list<Args...>,
           Tuple<TupleArgs...>& tuple, boost::mp11::index_sequence<Is...>)
         {
           (void)tuple;
           using std::get;
           return std::tuple<typename std::add_lvalue_reference<Args>::type...>(
             get<Is>(tuple)...);
         }
 
         template <class T>
         using add_lvalue_reference_t =
           typename std::add_lvalue_reference<T>::type;
 
         template <template <class...> class Tuple, class... Args>
         boost::mp11::mp_transform<add_lvalue_reference_t,
           boost::mp11::mp_remove<std::tuple<Args...>,
             boost::tuples::null_type> >
         to_std_tuple(Tuple<Args...>& tuple)
         {
           using list = boost::mp11::mp_remove<boost::mp11::mp_list<Args...>,
             boost::tuples::null_type>;
           using list_size = boost::mp11::mp_size<list>;
           using index_seq = boost::mp11::make_index_sequence<list_size::value>;
 
           return to_std_tuple_impl(list{}, tuple, index_seq{});
         }
 
         template <typename Alloc, typename A, typename B, typename A0,
           typename A1, typename A2>
         inline typename std::enable_if<use_piecewise<A0>::value &&
                                          !detect_std_tuple<A1>::value &&
                                          !detect_std_tuple<A2>::value,
           void>::type
         construct_from_args(
           Alloc& alloc, std::pair<A, B>* address, A0&&, A1&& a1, A2&& a2)
         {
           boost::allocator_construct(alloc, address, std::piecewise_construct,
             to_std_tuple(a1), to_std_tuple(a2));
         }
       } // namespace func
     } // namespace detail
   } // namespace unordered
 } // namespace boost
 
 namespace boost {
   namespace unordered {
     namespace detail {
 
       ///////////////////////////////////////////////////////////////////
       //
       // Node construction
 
       template <typename NodeAlloc> struct node_constructor
       {
         typedef NodeAlloc node_allocator;
         typedef boost::unordered::detail::allocator_traits<NodeAlloc>
           node_allocator_traits;
         typedef typename node_allocator_traits::value_type node;
         typedef typename node_allocator_traits::pointer node_pointer;
         typedef typename node::value_type value_type;
 
         node_allocator& alloc_;
         node_pointer node_;
 
         node_constructor(node_allocator& n) : alloc_(n), node_() {}
 
         ~node_constructor();
 
         void create_node();
 
         // no throw
         node_pointer release()
         {
           BOOST_ASSERT(node_);
           node_pointer p = node_;
           node_ = node_pointer();
           return p;
         }
 
       private:
         node_constructor(node_constructor const&);
         node_constructor& operator=(node_constructor const&);
       };
 
       template <typename Alloc> node_constructor<Alloc>::~node_constructor()
       {
         if (node_) {
           boost::unordered::detail::func::destroy(boost::to_address(node_));
           node_allocator_traits::deallocate(alloc_, node_, 1);
         }
       }
 
       template <typename Alloc> void node_constructor<Alloc>::create_node()
       {
         BOOST_ASSERT(!node_);
         node_ = node_allocator_traits::allocate(alloc_, 1);
         new ((void*)boost::to_address(node_)) node();
       }
 
       template <typename NodeAlloc> struct node_tmp
       {
         typedef typename boost::allocator_value_type<NodeAlloc>::type node;
         typedef typename boost::allocator_pointer<NodeAlloc>::type node_pointer;
         typedef typename node::value_type value_type;
         typedef typename boost::allocator_rebind<NodeAlloc, value_type>::type
           value_allocator;
 
         NodeAlloc& alloc_;
         node_pointer node_;
 
         explicit node_tmp(node_pointer n, NodeAlloc& a) : alloc_(a), node_(n) {}
 
         ~node_tmp();
 
         // no throw
         node_pointer release()
         {
           node_pointer p = node_;
           node_ = node_pointer();
           return p;
         }
       };
 
       template <typename Alloc> node_tmp<Alloc>::~node_tmp()
       {
         if (node_) {
           value_allocator val_alloc(alloc_);
           boost::allocator_destroy(val_alloc, node_->value_ptr());
           boost::allocator_deallocate(alloc_, node_, 1);
         }
       }
     } // namespace detail
   } // namespace unordered
 } // namespace boost
 
 namespace boost {
   namespace unordered {
     namespace detail {
       namespace func {
 
         // Some nicer construct_node functions, might try to
         // improve implementation later.
 
         template <typename Alloc, typename... Args>
         inline typename boost::allocator_pointer<Alloc>::type
         construct_node_from_args(Alloc& alloc, Args&&... args)
         {
           typedef typename boost::allocator_value_type<Alloc>::type node;
           typedef typename node::value_type value_type;
           typedef typename boost::allocator_rebind<Alloc, value_type>::type
             value_allocator;
 
           value_allocator val_alloc(alloc);
 
           node_constructor<Alloc> a(alloc);
           a.create_node();
           construct_from_args(
             val_alloc, a.node_->value_ptr(), std::forward<Args>(args)...);
           return a.release();
         }
 
         template <typename Alloc, typename U>
         inline typename boost::allocator_pointer<Alloc>::type construct_node(
           Alloc& alloc, U&& x)
         {
           node_constructor<Alloc> a(alloc);
           a.create_node();
 
           typedef typename boost::allocator_value_type<Alloc>::type node;
           typedef typename node::value_type value_type;
           typedef typename boost::allocator_rebind<Alloc, value_type>::type
             value_allocator;
 
           value_allocator val_alloc(alloc);
 
           boost::allocator_construct(
             val_alloc, a.node_->value_ptr(), std::forward<U>(x));
           return a.release();
         }
 
         template <typename Alloc, typename Key>
         inline typename boost::allocator_pointer<Alloc>::type
         construct_node_pair(Alloc& alloc, Key&& k)
         {
           node_constructor<Alloc> a(alloc);
           a.create_node();
 
           typedef typename boost::allocator_value_type<Alloc>::type node;
           typedef typename node::value_type value_type;
           typedef typename boost::allocator_rebind<Alloc, value_type>::type
             value_allocator;
 
           value_allocator val_alloc(alloc);
 
           boost::allocator_construct(val_alloc, a.node_->value_ptr(),
             std::piecewise_construct,
             std::forward_as_tuple(std::forward<Key>(k)),
             std::forward_as_tuple());
           return a.release();
         }
 
         template <typename Alloc, typename Key, typename Mapped>
         inline typename boost::allocator_pointer<Alloc>::type
         construct_node_pair(Alloc& alloc, Key&& k, Mapped&& m)
         {
           node_constructor<Alloc> a(alloc);
           a.create_node();
 
           typedef typename boost::allocator_value_type<Alloc>::type node;
           typedef typename node::value_type value_type;
           typedef typename boost::allocator_rebind<Alloc, value_type>::type
             value_allocator;
 
           value_allocator val_alloc(alloc);
 
           boost::allocator_construct(val_alloc, a.node_->value_ptr(),
             std::piecewise_construct,
             std::forward_as_tuple(std::forward<Key>(k)),
             std::forward_as_tuple(std::forward<Mapped>(m)));
           return a.release();
         }
 
         template <typename Alloc, typename Key, typename... Args>
         inline typename boost::allocator_pointer<Alloc>::type
         construct_node_pair_from_args(Alloc& alloc, Key&& k, Args&&... args)
         {
           node_constructor<Alloc> a(alloc);
           a.create_node();
 
           typedef typename boost::allocator_value_type<Alloc>::type node;
           typedef typename node::value_type value_type;
           typedef typename boost::allocator_rebind<Alloc, value_type>::type
             value_allocator;
 
           value_allocator val_alloc(alloc);
 
           boost::allocator_construct(val_alloc, a.node_->value_ptr(),
             std::piecewise_construct,
             std::forward_as_tuple(std::forward<Key>(k)),
             std::forward_as_tuple(std::forward<Args>(args)...));
 
           return a.release();
         }
 
         template <typename T, typename Alloc, typename Key>
         inline typename boost::allocator_pointer<Alloc>::type
         construct_node_from_key(T*, Alloc& alloc, Key&& k)
         {
           return construct_node(alloc, std::forward<Key>(k));
         }
 
         template <typename T, typename V, typename Alloc, typename Key>
         inline typename boost::allocator_pointer<Alloc>::type
         construct_node_from_key(std::pair<T const, V>*, Alloc& alloc, Key&& k)
         {
           return construct_node_pair(alloc, std::forward<Key>(k));
         }
       } // namespace func
     } // namespace detail
   } // namespace unordered
 } // namespace boost
 
 #if defined(BOOST_MSVC)
 #pragma warning(pop)
 #endif
 
 namespace boost {
   namespace unordered {
     namespace detail {
       //////////////////////////////////////////////////////////////////////////
       // Functions
       //
       // This double buffers the storage for the hash function and key equality
       // predicate in order to have exception safe copy/swap. To do so,
       // use 'construct_spare' to construct in the spare space, and then when
       // ready to use 'switch_functions' to switch to the new functions.
       // If an exception is thrown between these two calls, use
       // 'cleanup_spare_functions' to destroy the unused constructed functions.
 
 #if defined(_GLIBCXX_HAVE_BUILTIN_LAUNDER)
       // gcc-12 warns when accessing the `current_functions` of our `functions`
       // class below with `-Wmaybe-unitialized`. By laundering the pointer, we
       // silence the warning and assure the compiler that a valid object exists
       // in that region of storage. This warning is also generated in C++03
       // which does not have `std::launder`. The compiler builtin is always
       // available, regardless of the C++ standard used when compiling.
       template <class T> T* launder(T* p) noexcept
       {
         return __builtin_launder(p);
       }
 #else
       template <class T> T* launder(T* p) noexcept { return p; }
 #endif
 
       template <class H, class P> class functions
       {
       public:
         static const bool nothrow_move_assignable =
           std::is_nothrow_move_assignable<H>::value &&
           std::is_nothrow_move_assignable<P>::value;
         static const bool nothrow_move_constructible =
           std::is_nothrow_move_constructible<H>::value &&
           std::is_nothrow_move_constructible<P>::value;
         static const bool nothrow_swappable =
           boost::unordered::detail::is_nothrow_swappable<H>::value &&
           boost::unordered::detail::is_nothrow_swappable<P>::value;
 
       private:
         functions& operator=(functions const&);
 
         typedef compressed<H, P> function_pair;
 
         unsigned char current_; // 0/1 - Currently active functions
                                 // +2 - Both constructed
         opt_storage<function_pair> funcs_[2];
 
       public:
         functions(H const& hf, P const& eq) : current_(0)
         {
           construct_functions(current_, hf, eq);
         }
 
         functions(functions const& bf) : current_(0)
         {
           construct_functions(current_, bf.current_functions());
         }
 
         functions(functions& bf, boost::unordered::detail::move_tag)
             : current_(0)
         {
           construct_functions(current_, bf.current_functions(),
             std::integral_constant<bool, nothrow_move_constructible>());
         }
 
         ~functions()
         {
           BOOST_ASSERT(!(current_ & 2));
           destroy_functions(current_);
         }
 
         H const& hash_function() const { return current_functions().first(); }
 
         P const& key_eq() const { return current_functions().second(); }
 
         function_pair const& current_functions() const
         {
           return *::boost::unordered::detail::launder(
             static_cast<function_pair const*>(
               static_cast<void const*>(funcs_[current_ & 1].address())));
         }
 
         function_pair& current_functions()
         {
           return *::boost::unordered::detail::launder(
             static_cast<function_pair*>(
               static_cast<void*>(funcs_[current_ & 1].address())));
         }
 
         void construct_spare_functions(function_pair const& f)
         {
           BOOST_ASSERT(!(current_ & 2));
           construct_functions(current_ ^ 1, f);
           current_ |= 2;
         }
 
         void cleanup_spare_functions()
         {
           if (current_ & 2) {
             current_ = static_cast<unsigned char>(current_ & 1);
             destroy_functions(current_ ^ 1);
           }
         }
 
         void switch_functions()
         {
           BOOST_ASSERT(current_ & 2);
           destroy_functions(static_cast<unsigned char>(current_ & 1));
           current_ ^= 3;
         }
 
       private:
         void construct_functions(unsigned char which, H const& hf, P const& eq)
         {
           BOOST_ASSERT(!(which & 2));
           new ((void*)&funcs_[which]) function_pair(hf, eq);
         }
 
         void construct_functions(
           unsigned char which, function_pair const& f, std::false_type = {})
         {
           BOOST_ASSERT(!(which & 2));
           new ((void*)&funcs_[which]) function_pair(f);
         }
 
         void construct_functions(
           unsigned char which, function_pair& f, std::true_type)
         {
           BOOST_ASSERT(!(which & 2));
           new ((void*)&funcs_[which])
             function_pair(f, boost::unordered::detail::move_tag());
         }
 
         void destroy_functions(unsigned char which)
         {
           BOOST_ASSERT(!(which & 2));
           boost::unordered::detail::func::destroy(
             (function_pair*)(&funcs_[which]));
         }
       };
 
 #if defined(BOOST_MSVC)
 #pragma warning(push)
 #pragma warning(disable : 4127) // conditional expression is constant
 #endif
 
       //////////////////////////////////////////////////////////////////////////
       // convert double to std::size_t
 
       inline std::size_t double_to_size(double f)
       {
         return f >= static_cast<double>(
                       (std::numeric_limits<std::size_t>::max)())
                  ? (std::numeric_limits<std::size_t>::max)()
                  : static_cast<std::size_t>(f);
       }
 
       //////////////////////////////////////////////////////////////////////////
       // iterator definitions
 
       namespace iterator_detail {
         template <class Node, class Bucket> class c_iterator;
 
         template <class Node, class Bucket> class iterator
         {
         public:
           typedef typename Node::value_type value_type;
           typedef value_type element_type;
           typedef value_type* pointer;
           typedef value_type& reference;
           typedef std::ptrdiff_t difference_type;
           typedef std::forward_iterator_tag iterator_category;
 
           iterator() : p(), itb() {}
 
           reference operator*() const noexcept { return dereference(); }
           pointer operator->() const noexcept
           {
             pointer x = std::addressof(p->value());
             return x;
           }
 
           iterator& operator++() noexcept
           {
             increment();
             return *this;
           }
 
           iterator operator++(int) noexcept
           {
             iterator old = *this;
             increment();
             return old;
           }
 
           bool operator==(iterator const& other) const noexcept
           {
             return equal(other);
           }
 
           bool operator!=(iterator const& other) const noexcept
           {
             return !equal(other);
           }
 
           bool operator==(
             boost::unordered::detail::iterator_detail::c_iterator<Node,
               Bucket> const& other) const noexcept
           {
             return equal(other);
           }
 
           bool operator!=(
             boost::unordered::detail::iterator_detail::c_iterator<Node,
               Bucket> const& other) const noexcept
           {
             return !equal(other);
           }
 
         private:
           typedef typename Node::node_pointer node_pointer;
           typedef grouped_bucket_iterator<Bucket> bucket_iterator;
 
           node_pointer p;
           bucket_iterator itb;
 
           template <class Types> friend struct boost::unordered::detail::table;
           template <class N, class B> friend class c_iterator;
 
           iterator(node_pointer p_, bucket_iterator itb_) : p(p_), itb(itb_) {}
 
           value_type& dereference() const noexcept { return p->value(); }
 
           bool equal(const iterator& x) const noexcept { return (p == x.p); }
 
           bool equal(
             const boost::unordered::detail::iterator_detail::c_iterator<Node,
               Bucket>& x) const noexcept
           {
             return (p == x.p);
           }
 
           void increment() noexcept
           {
             p = p->next;
             if (!p) {
               p = (++itb)->next;
             }
           }
 
           template <typename Archive>
           friend void serialization_track(Archive& ar, const iterator& x)
           {
             if (x.p) {
               track_address(ar, x.p);
               serialization_track(ar, x.itb);
             }
           }
 
           friend class boost::serialization::access;
 
           template <typename Archive> void serialize(Archive& ar, unsigned int)
           {
             if (!p)
               itb = bucket_iterator();
             serialize_tracked_address(ar, p);
             ar& core::make_nvp("bucket_iterator", itb);
           }
         };
 
         template <class Node, class Bucket> class c_iterator
         {
         public:
           typedef typename Node::value_type value_type;
           typedef value_type const element_type;
           typedef value_type const* pointer;
           typedef value_type const& reference;
           typedef std::ptrdiff_t difference_type;
           typedef std::forward_iterator_tag iterator_category;
 
           c_iterator() : p(), itb() {}
           c_iterator(iterator<Node, Bucket> it) : p(it.p), itb(it.itb) {}
 
           reference operator*() const noexcept { return dereference(); }
           pointer operator->() const noexcept
           {
             pointer x = std::addressof(p->value());
             return x;
           }
 
           c_iterator& operator++() noexcept
           {
             increment();
             return *this;
           }
 
           c_iterator operator++(int) noexcept
           {
             c_iterator old = *this;
             increment();
             return old;
           }
 
           bool operator==(c_iterator const& other) const noexcept
           {
             return equal(other);
           }
 
           bool operator!=(c_iterator const& other) const noexcept
           {
             return !equal(other);
           }
 
           bool operator==(
             boost::unordered::detail::iterator_detail::iterator<Node,
               Bucket> const& other) const noexcept
           {
             return equal(other);
           }
 
           bool operator!=(
             boost::unordered::detail::iterator_detail::iterator<Node,
               Bucket> const& other) const noexcept
           {
             return !equal(other);
           }
 
         private:
           typedef typename Node::node_pointer node_pointer;
           typedef grouped_bucket_iterator<Bucket> bucket_iterator;
 
           node_pointer p;
           bucket_iterator itb;
 
           template <class Types> friend struct boost::unordered::detail::table;
           template <class, class> friend class iterator;
 
           c_iterator(node_pointer p_, bucket_iterator itb_) : p(p_), itb(itb_)
           {
           }
 
           value_type const& dereference() const noexcept { return p->value(); }
 
           bool equal(const c_iterator& x) const noexcept { return (p == x.p); }
 
           void increment() noexcept
           {
             p = p->next;
             if (!p) {
               p = (++itb)->next;
             }
           }
 
           template <typename Archive>
           friend void serialization_track(Archive& ar, const c_iterator& x)
           {
             if (x.p) {
               track_address(ar, x.p);
               serialization_track(ar, x.itb);
             }
           }
 
           friend class boost::serialization::access;
 
           template <typename Archive> void serialize(Archive& ar, unsigned int)
           {
             if (!p)
               itb = bucket_iterator();
             serialize_tracked_address(ar, p);
             ar& core::make_nvp("bucket_iterator", itb);
           }
         };
       } // namespace iterator_detail
 
       //////////////////////////////////////////////////////////////////////////
       // table structure used by the containers
       template <typename Types>
       struct table : boost::unordered::detail::functions<typename Types::hasher,
                        typename Types::key_equal>
       {
       private:
         table(table const&);
         table& operator=(table const&);
 
       public:
         typedef typename Types::hasher hasher;
         typedef typename Types::key_equal key_equal;
         typedef typename Types::const_key_type const_key_type;
         typedef typename Types::extractor extractor;
         typedef typename Types::value_type value_type;
         typedef typename Types::table table_impl;
 
         typedef boost::unordered::detail::functions<typename Types::hasher,
           typename Types::key_equal>
           functions;
 
         typedef typename Types::value_allocator value_allocator;
         typedef typename boost::allocator_void_pointer<value_allocator>::type
           void_pointer;
         typedef node<value_type, void_pointer> node_type;
 
         typedef boost::unordered::detail::grouped_bucket_array<
           bucket<node_type, void_pointer>, value_allocator, prime_fmod_size<> >
           bucket_array_type;
 
         typedef
           typename bucket_array_type::node_allocator_type node_allocator_type;
         typedef typename boost::allocator_pointer<node_allocator_type>::type
           node_pointer;
 
         typedef boost::unordered::detail::node_constructor<node_allocator_type>
           node_constructor;
         typedef boost::unordered::detail::node_tmp<node_allocator_type>
           node_tmp;
 
         typedef typename bucket_array_type::bucket_type bucket_type;
 
         typedef typename bucket_array_type::iterator bucket_iterator;
 
         typedef typename bucket_array_type::local_iterator l_iterator;
         typedef typename bucket_array_type::const_local_iterator cl_iterator;
 
         typedef std::size_t size_type;
 
         typedef iterator_detail::iterator<node_type, bucket_type> iterator;
         typedef iterator_detail::c_iterator<node_type, bucket_type> c_iterator;
 
         typedef std::pair<iterator, bool> emplace_return;
 
         ////////////////////////////////////////////////////////////////////////
         // Members
 
         std::size_t size_;
         float mlf_;
         std::size_t max_load_;
         bucket_array_type buckets_;
 
       public:
         ////////////////////////////////////////////////////////////////////////
         // Data access
 
         size_type bucket_count() const { return buckets_.bucket_count(); }
 
         template <class Key>
         iterator next_group(Key const& k, c_iterator n) const
         {
           c_iterator last = this->end();
           while (n != last && this->key_eq()(k, extractor::extract(*n))) {
             ++n;
           }
           return iterator(n.p, n.itb);
         }
 
         template <class Key> std::size_t group_count(Key const& k) const
         {
           if (size_ == 0) {
             return 0;
           }
           std::size_t c = 0;
           std::size_t const key_hash = this->hash(k);
           bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
 
           bool found = false;
 
           for (node_pointer pos = itb->next; pos; pos = pos->next) {
             if (this->key_eq()(k, this->get_key(pos))) {
               ++c;
               found = true;
             } else if (found) {
               break;
             }
           }
           return c;
         }
 
         node_allocator_type const& node_alloc() const
         {
           return buckets_.get_node_allocator();
         }
 
         node_allocator_type& node_alloc()
         {
           return buckets_.get_node_allocator();
         }
 
         std::size_t max_bucket_count() const
         {
           typedef typename bucket_array_type::size_policy size_policy;
           return size_policy::size(size_policy::size_index(
             boost::allocator_max_size(this->node_alloc())));
         }
 
         iterator begin() const
         {
           if (size_ == 0) {
             return end();
           }
 
           bucket_iterator itb = buckets_.begin();
           return iterator(itb->next, itb);
         }
 
         iterator end() const { return iterator(); }
 
         l_iterator begin(std::size_t bucket_index) const
         {
           return buckets_.begin(bucket_index);
         }
 
         std::size_t hash_to_bucket(std::size_t hash_value) const
         {
           return buckets_.position(hash_value);
         }
 
         std::size_t bucket_size(std::size_t index) const
         {
           std::size_t count = 0;
           if (size_ > 0) {
             bucket_iterator itb = buckets_.at(index);
             node_pointer n = itb->next;
             while (n) {
               ++count;
               n = n->next;
             }
           }
           return count;
         }
 
         ////////////////////////////////////////////////////////////////////////
         // Load methods
 
         void recalculate_max_load()
         {
           // From 6.3.1/13:
           // Only resize when size >= mlf_ * count
           std::size_t const bc = buckets_.bucket_count();
 
           // it's important we do the `bc == 0` check here because the `mlf_`
           // can be specified to be infinity. The operation `n * INF` is `INF`
           // for all `n > 0` but NaN for `n == 0`.
           //
           max_load_ =
             bc == 0 ? 0
                     : boost::unordered::detail::double_to_size(
                         static_cast<double>(mlf_) * static_cast<double>(bc));
         }
 
         void max_load_factor(float z)
         {
           BOOST_ASSERT(z > 0);
           mlf_ = (std::max)(z, minimum_max_load_factor);
           recalculate_max_load();
         }
 
         ////////////////////////////////////////////////////////////////////////
         // Constructors
 
         table()
             : functions(hasher(), key_equal()), size_(0), mlf_(1.0f),
               max_load_(0)
         {
         }
 
         table(std::size_t num_buckets, hasher const& hf, key_equal const& eq,
           value_allocator const& a)
             : functions(hf, eq), size_(0), mlf_(1.0f), max_load_(0),
               buckets_(num_buckets, a)
         {
           recalculate_max_load();
         }
 
         table(table const& x, value_allocator const& a)
             : functions(x), size_(0), mlf_(x.mlf_), max_load_(0),
               buckets_(x.size_, a)
         {
           recalculate_max_load();
         }
 
         table(table& x, boost::unordered::detail::move_tag m)
             : functions(x, m), size_(x.size_), mlf_(x.mlf_),
               max_load_(x.max_load_), buckets_(std::move(x.buckets_))
         {
           x.size_ = 0;
           x.max_load_ = 0;
         }
 
         table(table& x, value_allocator const& a,
           boost::unordered::detail::move_tag m)
             : functions(x, m), size_(0), mlf_(x.mlf_), max_load_(0),
               buckets_(x.bucket_count(), a)
         {
           recalculate_max_load();
         }
 
         ////////////////////////////////////////////////////////////////////////
         // Swap and Move
 
         void swap_allocators(table& other, std::false_type)
         {
           boost::unordered::detail::func::ignore_unused_variable_warning(other);
 
           // According to 23.2.1.8, if propagate_on_container_swap is
           // false the behaviour is undefined unless the allocators
           // are equal.
           BOOST_ASSERT(node_alloc() == other.node_alloc());
         }
 
         // Not nothrow swappable
         void swap(table& x, std::false_type)
         {
           if (this == &x) {
             return;
           }
 
           this->construct_spare_functions(x.current_functions());
           BOOST_TRY { x.construct_spare_functions(this->current_functions()); }
           BOOST_CATCH(...)
           {
             this->cleanup_spare_functions();
             BOOST_RETHROW
           }
           BOOST_CATCH_END
           this->switch_functions();
           x.switch_functions();
 
           buckets_.swap(x.buckets_);
           boost::core::invoke_swap(size_, x.size_);
           std::swap(mlf_, x.mlf_);
           std::swap(max_load_, x.max_load_);
         }
 
         // Nothrow swappable
         void swap(table& x, std::true_type)
         {
           buckets_.swap(x.buckets_);
           boost::core::invoke_swap(size_, x.size_);
           std::swap(mlf_, x.mlf_);
           std::swap(max_load_, x.max_load_);
           this->current_functions().swap(x.current_functions());
         }
 
         // Only swaps the allocators if propagate_on_container_swap.
         // If not propagate_on_container_swap and allocators aren't
         // equal, behaviour is undefined.
         void swap(table& x)
         {
           BOOST_ASSERT(boost::allocator_propagate_on_container_swap<
                          node_allocator_type>::type::value ||
                        node_alloc() == x.node_alloc());
           swap(x, std::integral_constant<bool, functions::nothrow_swappable>());
         }
 
         // Only call with nodes allocated with the currect allocator, or
         // one that is equal to it. (Can't assert because other's
         // allocators might have already been moved).
         void move_buckets_from(table& other)
         {
           buckets_ = std::move(other.buckets_);
 
           size_ = other.size_;
           max_load_ = other.max_load_;
 
           other.size_ = 0;
           other.max_load_ = 0;
         }
 
         // For use in the constructor when allocators might be different.
         void move_construct_buckets(table& src)
         {
           if (this->node_alloc() == src.node_alloc()) {
             move_buckets_from(src);
             return;
           }
 
           if (src.size_ == 0) {
             return;
           }
 
           BOOST_ASSERT(buckets_.bucket_count() == src.buckets_.bucket_count());
 
           this->reserve(src.size_);
           for (iterator pos = src.begin(); pos != src.end(); ++pos) {
             node_tmp b(detail::func::construct_node(
                          this->node_alloc(), std::move(pos.p->value())),
               this->node_alloc());
 
             const_key_type& k = this->get_key(b.node_);
             std::size_t key_hash = this->hash(k);
 
             bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
             buckets_.insert_node(itb, b.release());
             ++size_;
           }
         }
 
         ////////////////////////////////////////////////////////////////////////
         // Delete/destruct
 
         ~table() { delete_buckets(); }
 
         void delete_node(node_pointer p)
         {
           node_allocator_type alloc = this->node_alloc();
 
           value_allocator val_alloc(alloc);
           boost::allocator_destroy(val_alloc, p->value_ptr());
           boost::unordered::detail::func::destroy(boost::to_address(p));
           boost::allocator_deallocate(alloc, p, 1);
         }
 
         void delete_buckets()
         {
           iterator pos = begin(), last = this->end();
           for (; pos != last;) {
             node_pointer p = pos.p;
             bucket_iterator itb = pos.itb;
             ++pos;
             buckets_.extract_node(itb, p);
             delete_node(p);
             --size_;
           }
 
           buckets_.clear();
         }
 
         ////////////////////////////////////////////////////////////////////////
         // Clear
 
         void clear_impl();
 
         ////////////////////////////////////////////////////////////////////////
         // Assignment
 
         template <typename UniqueType>
         void assign(table const& x, UniqueType is_unique)
         {
           typedef
             typename boost::allocator_propagate_on_container_copy_assignment<
               node_allocator_type>::type pocca;
 
           if (this != &x) {
             assign(x, is_unique, std::integral_constant<bool, pocca::value>());
           }
         }
 
         template <typename UniqueType>
         void assign(table const& x, UniqueType is_unique, std::false_type)
         {
           // Strong exception safety.
           this->construct_spare_functions(x.current_functions());
           BOOST_TRY
           {
             mlf_ = x.mlf_;
             recalculate_max_load();
 
             this->reserve_for_insert(x.size_);
             this->clear_impl();
           }
           BOOST_CATCH(...)
           {
             this->cleanup_spare_functions();
             BOOST_RETHROW
           }
           BOOST_CATCH_END
           this->switch_functions();
           copy_buckets(x, is_unique);
         }
 
         template <typename UniqueType>
         void assign(table const& x, UniqueType is_unique, std::true_type)
         {
           if (node_alloc() == x.node_alloc()) {
             buckets_.reset_allocator(x.node_alloc());
             assign(x, is_unique, std::false_type());
           } else {
             bucket_array_type new_buckets(x.size_, x.node_alloc());
             this->construct_spare_functions(x.current_functions());
             this->switch_functions();
 
             // Delete everything with current allocators before assigning
             // the new ones.
             delete_buckets();
             buckets_.reset_allocator(x.node_alloc());
             buckets_ = std::move(new_buckets);
 
             // Copy over other data, all no throw.
             mlf_ = x.mlf_;
             reserve(x.size_);
 
             // Finally copy the elements.
             if (x.size_) {
               copy_buckets(x, is_unique);
             }
           }
         }
 
         template <typename UniqueType>
         void move_assign(table& x, UniqueType is_unique)
         {
           if (this != &x) {
             move_assign(x, is_unique,
               std::integral_constant<bool,
                 boost::allocator_propagate_on_container_move_assignment<
                   node_allocator_type>::type::value>());
           }
         }
 
         // Propagate allocator
         template <typename UniqueType>
         void move_assign(table& x, UniqueType, std::true_type)
         {
           if (!functions::nothrow_move_assignable) {
             this->construct_spare_functions(x.current_functions());
             this->switch_functions();
           } else {
             this->current_functions().move_assign(x.current_functions());
           }
           delete_buckets();
 
           buckets_.reset_allocator(x.buckets_.get_node_allocator());
           mlf_ = x.mlf_;
           move_buckets_from(x);
         }
 
         // Don't propagate allocator
         template <typename UniqueType>
         void move_assign(table& x, UniqueType is_unique, std::false_type)
         {
           if (node_alloc() == x.node_alloc()) {
             move_assign_equal_alloc(x);
           } else {
             move_assign_realloc(x, is_unique);
           }
         }
 
         void move_assign_equal_alloc(table& x)
         {
           if (!functions::nothrow_move_assignable) {
             this->construct_spare_functions(x.current_functions());
             this->switch_functions();
           } else {
             this->current_functions().move_assign(x.current_functions());
           }
           delete_buckets();
           mlf_ = x.mlf_;
           move_buckets_from(x);
         }
 
         template <typename UniqueType>
         void move_assign_realloc(table& x, UniqueType is_unique)
         {
           this->construct_spare_functions(x.current_functions());
           BOOST_TRY
           {
             mlf_ = x.mlf_;
             recalculate_max_load();
             if (x.size_ > 0) {
               this->reserve_for_insert(x.size_);
             }
             this->clear_impl();
           }
           BOOST_CATCH(...)
           {
             this->cleanup_spare_functions();
             BOOST_RETHROW
           }
           BOOST_CATCH_END
           this->switch_functions();
           move_assign_buckets(x, is_unique);
         }
 
         // Accessors
 
         const_key_type& get_key(node_pointer n) const
         {
           return extractor::extract(n->value());
         }
 
         template <class Key> std::size_t hash(Key const& k) const
         {
           return this->hash_function()(k);
         }
 
         // Find Node
 
         template <class Key>
         node_pointer find_node_impl(Key const& x, bucket_iterator itb) const
         {
           node_pointer p = node_pointer();
           if (itb != buckets_.end()) {
             key_equal const& pred = this->key_eq();
             p = itb->next;
             for (; p; p = p->next) {
               if (pred(x, extractor::extract(p->value()))) {
                 break;
               }
             }
           }
           return p;
         }
 
         template <class Key> node_pointer find_node(Key const& k) const
         {
           std::size_t const key_hash = this->hash(k);
           return find_node_impl(k, buckets_.at(buckets_.position(key_hash)));
         }
 
         node_pointer find_node(const_key_type& k, bucket_iterator itb) const
         {
           return find_node_impl(k, itb);
         }
 
         template <class Key> iterator find(Key const& k) const
         {
           return this->transparent_find(
             k, this->hash_function(), this->key_eq());
         }
 
         template <class Key, class Hash, class Pred>
         inline iterator transparent_find(
           Key const& k, Hash const& h, Pred const& pred) const
         {
           if (size_ > 0) {
             std::size_t const key_hash = h(k);
             bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
             for (node_pointer p = itb->next; p; p = p->next) {
               if (BOOST_LIKELY(pred(k, extractor::extract(p->value())))) {
                 return iterator(p, itb);
               }
             }
           }
 
           return this->end();
         }
 
         template <class Key>
         node_pointer* find_prev(Key const& key, bucket_iterator itb)
         {
           if (size_ > 0) {
             key_equal pred = this->key_eq();
             for (node_pointer* pp = std::addressof(itb->next); *pp;
                  pp = std::addressof((*pp)->next)) {
               if (pred(key, extractor::extract((*pp)->value()))) {
                 return pp;
               }
             }
           }
           typedef node_pointer* node_pointer_pointer;
           return node_pointer_pointer();
         }
 
         // Extract and erase
 
         template <class Key> node_pointer extract_by_key_impl(Key const& k)
         {
           iterator it = this->find(k);
           if (it == this->end()) {
             return node_pointer();
           }
 
           buckets_.extract_node(it.itb, it.p);
           --size_;
 
           return it.p;
         }
 
         // Reserve and rehash
         void transfer_node(
           node_pointer p, bucket_type&, bucket_array_type& new_buckets)
         {
           const_key_type& key = extractor::extract(p->value());
           std::size_t const h = this->hash(key);
           bucket_iterator itnewb = new_buckets.at(new_buckets.position(h));
           new_buckets.insert_node(itnewb, p);
         }
 
         static std::size_t min_buckets(std::size_t num_elements, float mlf)
         {
           std::size_t num_buckets = static_cast<std::size_t>(
             std::ceil(static_cast<float>(num_elements) / mlf));
 
           if (num_buckets == 0 && num_elements > 0) { // mlf == inf
             num_buckets = 1;
           }
           return num_buckets;
         }
 
         void rehash(std::size_t);
         void reserve(std::size_t);
         void reserve_for_insert(std::size_t);
         void rehash_impl(std::size_t);
 
         ////////////////////////////////////////////////////////////////////////
         // Unique keys
 
         // equals
 
         bool equals_unique(table const& other) const
         {
           if (this->size_ != other.size_)
             return false;
 
           c_iterator pos = this->begin();
           c_iterator last = this->end();
 
           while (pos != last) {
             node_pointer p = pos.p;
             node_pointer p2 = other.find_node(this->get_key(p));
             if (!p2 || !(p->value() == p2->value())) {
               return false;
             }
             ++pos;
           }
 
           return true;
         }
 
         // Emplace/Insert
 
         template <typename... Args>
         iterator emplace_hint_unique(
           c_iterator hint, const_key_type& k, Args&&... args)
         {
           if (hint.p && this->key_eq()(k, this->get_key(hint.p))) {
             return iterator(hint.p, hint.itb);
           } else {
             return emplace_unique(k, std::forward<Args>(args)...).first;
           }
         }
 
         template <typename... Args>
         emplace_return emplace_unique(const_key_type& k, Args&&... args)
         {
           std::size_t key_hash = this->hash(k);
           bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
           node_pointer pos = this->find_node_impl(k, itb);
 
           if (pos) {
             return emplace_return(iterator(pos, itb), false);
           } else {
             node_tmp b(boost::unordered::detail::func::construct_node_from_args(
                          this->node_alloc(), std::forward<Args>(args)...),
               this->node_alloc());
 
             if (size_ + 1 > max_load_) {
               reserve(size_ + 1);
               itb = buckets_.at(buckets_.position(key_hash));
             }
 
             node_pointer p = b.release();
             buckets_.insert_node(itb, p);
             ++size_;
 
             return emplace_return(iterator(p, itb), true);
           }
         }
 
         template <typename... Args>
         iterator emplace_hint_unique(c_iterator hint, no_key, Args&&... args)
         {
           node_tmp b(boost::unordered::detail::func::construct_node_from_args(
                        this->node_alloc(), std::forward<Args>(args)...),
             this->node_alloc());
 
           const_key_type& k = this->get_key(b.node_);
           if (hint.p && this->key_eq()(k, this->get_key(hint.p))) {
             return iterator(hint.p, hint.itb);
           }
 
           std::size_t const key_hash = this->hash(k);
           bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
 
           node_pointer p = this->find_node_impl(k, itb);
           if (p) {
             return iterator(p, itb);
           }
 
           if (size_ + 1 > max_load_) {
             this->reserve(size_ + 1);
             itb = buckets_.at(buckets_.position(key_hash));
           }
 
           p = b.release();
           buckets_.insert_node(itb, p);
           ++size_;
           return iterator(p, itb);
         }
 
         template <typename... Args>
         emplace_return emplace_unique(no_key, Args&&... args)
         {
           node_tmp b(boost::unordered::detail::func::construct_node_from_args(
                        this->node_alloc(), std::forward<Args>(args)...),
             this->node_alloc());
 
           const_key_type& k = this->get_key(b.node_);
           std::size_t key_hash = this->hash(k);
 
           bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
           node_pointer pos = this->find_node_impl(k, itb);
 
           if (pos) {
             return emplace_return(iterator(pos, itb), false);
           } else {
             if (size_ + 1 > max_load_) {
               reserve(size_ + 1);
               itb = buckets_.at(buckets_.position(key_hash));
             }
 
             node_pointer p = b.release();
             buckets_.insert_node(itb, p);
             ++size_;
 
             return emplace_return(iterator(p, itb), true);
           }
         }
 
         template <typename K, typename V>
         emplace_return emplace_unique(converting_key, K&& k, V&& v)
         {
           using alloc_cted = allocator_constructed<node_allocator_type,
             typename Types::key_type>;
           alloc_cted key(this->node_alloc(), std::forward<K>(k));
           return emplace_unique(
             key.value(), std::move(key.value()), std::forward<V>(v));
         }
 
         template <typename Key> emplace_return try_emplace_unique(Key&& k)
         {
           std::size_t key_hash = this->hash(k);
           bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
 
           node_pointer pos = this->find_node_impl(k, itb);
 
           if (pos) {
             return emplace_return(iterator(pos, itb), false);
           } else {
             node_allocator_type alloc = node_alloc();
 
             value_type* dispatch = BOOST_NULLPTR;
 
             node_tmp tmp(detail::func::construct_node_from_key(
                            dispatch, alloc, std::forward<Key>(k)),
               alloc);
 
             if (size_ + 1 > max_load_) {
               reserve(size_ + 1);
               itb = buckets_.at(buckets_.position(key_hash));
             }
 
             node_pointer p = tmp.release();
             buckets_.insert_node(itb, p);
 
             ++size_;
             return emplace_return(iterator(p, itb), true);
           }
         }
 
         template <typename Key>
         iterator try_emplace_hint_unique(c_iterator hint, Key&& k)
         {
           if (hint.p && this->key_eq()(extractor::extract(*hint), k)) {
             return iterator(hint.p, hint.itb);
           } else {
             return try_emplace_unique(k).first;
           }
         }
 
         template <typename Key, typename... Args>
         emplace_return try_emplace_unique(Key&& k, Args&&... args)
         {
           std::size_t key_hash = this->hash(k);
           bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
 
           node_pointer pos = this->find_node_impl(k, itb);
 
           if (pos) {
             return emplace_return(iterator(pos, itb), false);
           }
 
           node_tmp b(
             boost::unordered::detail::func::construct_node_pair_from_args(
               this->node_alloc(), k, std::forward<Args>(args)...),
             this->node_alloc());
 
           if (size_ + 1 > max_load_) {
             reserve(size_ + 1);
             itb = buckets_.at(buckets_.position(key_hash));
           }
 
           pos = b.release();
 
           buckets_.insert_node(itb, pos);
           ++size_;
           return emplace_return(iterator(pos, itb), true);
         }
 
         template <typename Key, typename... Args>
         iterator try_emplace_hint_unique(
           c_iterator hint, Key&& k, Args&&... args)
         {
           if (hint.p && this->key_eq()(hint->first, k)) {
             return iterator(hint.p, hint.itb);
           } else {
             return try_emplace_unique(k, std::forward<Args>(args)...).first;
           }
         }
 
         template <typename Key, typename M>
         emplace_return insert_or_assign_unique(Key&& k, M&& obj)
         {
           std::size_t key_hash = this->hash(k);
           bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
 
           node_pointer p = this->find_node_impl(k, itb);
           if (p) {
             p->value().second = std::forward<M>(obj);
             return emplace_return(iterator(p, itb), false);
           }
 
           node_tmp b(
             boost::unordered::detail::func::construct_node_pair(
               this->node_alloc(), std::forward<Key>(k), std::forward<M>(obj)),
             node_alloc());
 
           if (size_ + 1 > max_load_) {
             reserve(size_ + 1);
             itb = buckets_.at(buckets_.position(key_hash));
           }
 
           p = b.release();
 
           buckets_.insert_node(itb, p);
           ++size_;
           return emplace_return(iterator(p, itb), true);
         }
 
         template <typename NodeType, typename InsertReturnType>
         void move_insert_node_type_unique(
           NodeType& np, InsertReturnType& result)
         {
           if (!np) {
             result.position = this->end();
             result.inserted = false;
             return;
           }
 
           const_key_type& k = this->get_key(np.ptr_);
           std::size_t const key_hash = this->hash(k);
           bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
           node_pointer p = this->find_node_impl(k, itb);
 
           if (p) {
             iterator pos(p, itb);
             result.node = std::move(np);
             result.position = pos;
             result.inserted = false;
             return;
           }
 
           this->reserve_for_insert(size_ + 1);
 
           p = np.ptr_;
           itb = buckets_.at(buckets_.position(key_hash));
 
           buckets_.insert_node(itb, p);
           np.ptr_ = node_pointer();
           ++size_;
 
           result.position = iterator(p, itb);
           result.inserted = true;
         }
 
         template <typename NodeType>
         iterator move_insert_node_type_with_hint_unique(
           c_iterator hint, NodeType& np)
         {
           if (!np) {
             return this->end();
           }
 
           const_key_type& k = this->get_key(np.ptr_);
           if (hint.p && this->key_eq()(k, this->get_key(hint.p))) {
             return iterator(hint.p, hint.itb);
           }
 
           std::size_t const key_hash = this->hash(k);
           bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
           node_pointer p = this->find_node_impl(k, itb);
           if (p) {
             return iterator(p, itb);
           }
 
           p = np.ptr_;
 
           if (size_ + 1 > max_load_) {
             this->reserve(size_ + 1);
             itb = buckets_.at(buckets_.position(key_hash));
           }
 
           buckets_.insert_node(itb, p);
           ++size_;
           np.ptr_ = node_pointer();
           return iterator(p, itb);
         }
 
         template <typename Types2>
         void merge_unique(boost::unordered::detail::table<Types2>& other)
         {
           typedef boost::unordered::detail::table<Types2> other_table;
           BOOST_UNORDERED_STATIC_ASSERT(
             (std::is_same<node_type, typename other_table::node_type>::value));
           BOOST_ASSERT(this->node_alloc() == other.node_alloc());
 
           if (other.size_ == 0) {
             return;
           }
 
           this->reserve_for_insert(size_ + other.size_);
 
           iterator last = other.end();
           for (iterator pos = other.begin(); pos != last;) {
             const_key_type& key = other.get_key(pos.p);
             std::size_t const key_hash = this->hash(key);
 
             bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
 
             if (this->find_node_impl(key, itb)) {
               ++pos;
               continue;
             }
 
             iterator old = pos;
             ++pos;
 
             node_pointer p = other.extract_by_iterator_unique(old);
             buckets_.insert_node(itb, p);
             ++size_;
           }
         }
 
         ////////////////////////////////////////////////////////////////////////
         // Insert range methods
         //
         // if hash function throws, or inserting > 1 element, basic exception
         // safety strong otherwise
 
         template <class InputIt>
         void insert_range_unique(no_key, InputIt i, InputIt j)
         {
           hasher const& hf = this->hash_function();
           node_allocator_type alloc = this->node_alloc();
 
           for (; i != j; ++i) {
             node_tmp tmp(detail::func::construct_node(alloc, *i), alloc);
 
             value_type const& value = tmp.node_->value();
             const_key_type& key = extractor::extract(value);
             std::size_t const h = hf(key);
 
             bucket_iterator itb = buckets_.at(buckets_.position(h));
             node_pointer it = find_node_impl(key, itb);
             if (it) {
               continue;
             }
 
             if (size_ + 1 > max_load_) {
               reserve(size_ + 1);
               itb = buckets_.at(buckets_.position(h));
             }
 
             node_pointer nptr = tmp.release();
             buckets_.insert_node(itb, nptr);
             ++size_;
           }
         }
 
         ////////////////////////////////////////////////////////////////////////
         // Extract
 
         inline node_pointer extract_by_iterator_unique(c_iterator i)
         {
           node_pointer p = i.p;
           bucket_iterator itb = i.itb;
 
           buckets_.extract_node(itb, p);
           --size_;
 
           return p;
         }
 
         ////////////////////////////////////////////////////////////////////////
         // Erase
         //
 
         template <class Key> std::size_t erase_key_unique_impl(Key const& k)
         {
           bucket_iterator itb = buckets_.at(buckets_.position(this->hash(k)));
           node_pointer* pp = this->find_prev(k, itb);
           if (!pp) {
             return 0;
           }
 
           node_pointer p = *pp;
           buckets_.extract_node_after(itb, pp);
           this->delete_node(p);
           --size_;
           return 1;
         }
 
         iterator erase_node(c_iterator pos)
         {
           c_iterator next = pos;
           ++next;
 
           bucket_iterator itb = pos.itb;
           node_pointer* pp = std::addressof(itb->next);
           while (*pp != pos.p) {
             pp = std::addressof((*pp)->next);
           }
 
           buckets_.extract_node_after(itb, pp);
           this->delete_node(pos.p);
           --size_;
 
           return iterator(next.p, next.itb);
         }
 
         iterator erase_nodes_range(c_iterator first, c_iterator last)
         {
           if (first == last) {
             return iterator(last.p, last.itb);
           }
 
           // though `first` stores of a copy of a pointer to a node, we wish to
           // mutate the pointers stored internally by the singly-linked list in
           // each bucket group so we have to retrieve it manually by iterating
           //
           bucket_iterator itb = first.itb;
           node_pointer* pp = std::addressof(itb->next);
           while (*pp != first.p) {
             pp = std::addressof((*pp)->next);
           }
 
           while (*pp != last.p) {
             node_pointer p = *pp;
             *pp = (*pp)->next;
 
             this->delete_node(p);
             --size_;
 
             bool const at_end = !(*pp);
             bool const is_empty_bucket = !itb->next;
 
             if (at_end) {
               if (is_empty_bucket) {
                 buckets_.unlink_bucket(itb++);
               } else {
                 ++itb;
               }
               pp = std::addressof(itb->next);
             }
           }
 
           return iterator(last.p, last.itb);
         }
 
         ////////////////////////////////////////////////////////////////////////
         // fill_buckets_unique
 
         void copy_buckets(table const& src, std::true_type)
         {
           BOOST_ASSERT(size_ == 0);
 
           this->reserve_for_insert(src.size_);
 
           for (iterator pos = src.begin(); pos != src.end(); ++pos) {
             value_type const& value = *pos;
             const_key_type& key = extractor::extract(value);
             std::size_t const key_hash = this->hash(key);
 
             bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
 
             node_allocator_type alloc = this->node_alloc();
             node_tmp tmp(detail::func::construct_node(alloc, value), alloc);
 
             buckets_.insert_node(itb, tmp.release());
             ++size_;
           }
         }
 
         void move_assign_buckets(table& src, std::true_type)
         {
           BOOST_ASSERT(size_ == 0);
           BOOST_ASSERT(max_load_ >= src.size_);
 
           iterator last = src.end();
           node_allocator_type alloc = this->node_alloc();
 
           for (iterator pos = src.begin(); pos != last; ++pos) {
             value_type value = std::move(*pos);
             const_key_type& key = extractor::extract(value);
             std::size_t const key_hash = this->hash(key);
 
             bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
 
             node_tmp tmp(
               detail::func::construct_node(alloc, std::move(value)), alloc);
 
             buckets_.insert_node(itb, tmp.release());
             ++size_;
           }
         }
 
         ////////////////////////////////////////////////////////////////////////
         // Equivalent keys
 
         // Equality
 
         bool equals_equiv(table const& other) const
         {
           if (this->size_ != other.size_)
             return false;
 
           iterator last = this->end();
           for (iterator n1 = this->begin(); n1 != last;) {
             const_key_type& k = extractor::extract(*n1);
             iterator n2 = other.find(k);
             if (n2 == other.end()) {
               return false;
             }
 
             iterator end1 = this->next_group(k, n1);
             iterator end2 = other.next_group(k, n2);
 
             if (!group_equals_equiv(n1, end1, n2, end2)) {
               return false;
             }
 
             n1 = end1;
           }
 
           return true;
         }
 
         static bool group_equals_equiv(
           iterator n1, iterator end1, iterator n2, iterator end2)
         {
           for (;;) {
             if (*n1 != *n2)
               break;
 
             ++n1;
             ++n2;
 
             if (n1 == end1)
               return n2 == end2;
 
             if (n2 == end2)
               return false;
           }
 
           for (iterator n1a = n1, n2a = n2;;) {
             ++n1a;
             ++n2a;
 
             if (n1a == end1) {
               if (n2a == end2)
                 break;
               else
                 return false;
             }
 
             if (n2a == end2)
               return false;
           }
 
           iterator start = n1;
           for (; n1 != end1; ++n1) {
             value_type const& v = *n1;
             if (!find_equiv(start, n1, v)) {
               std::size_t matches = count_equal_equiv(n2, end2, v);
               if (!matches)
                 return false;
 
               iterator t = n1;
               if (matches != 1 + count_equal_equiv(++t, end1, v))
                 return false;
             }
           }
 
           return true;
         }
 
         static bool find_equiv(iterator n, iterator last, value_type const& v)
         {
           for (; n != last; ++n)
             if (*n == v)
               return true;
           return false;
         }
 
         static std::size_t count_equal_equiv(
           iterator n, iterator last, value_type const& v)
         {
           std::size_t count = 0;
           for (; n != last; ++n)
             if (*n == v)
               ++count;
           return count;
         }
 
         // Emplace/Insert
 
         iterator emplace_equiv(node_pointer n)
         {
           node_tmp a(n, this->node_alloc());
           const_key_type& k = this->get_key(a.node_);
           std::size_t key_hash = this->hash(k);
           bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
           node_pointer hint = this->find_node_impl(k, itb);
 
           if (size_ + 1 > max_load_) {
             this->reserve(size_ + 1);
             itb = buckets_.at(buckets_.position(key_hash));
           }
           node_pointer p = a.release();
           buckets_.insert_node_hint(itb, p, hint);
           ++size_;
           return iterator(p, itb);
         }
 
         iterator emplace_hint_equiv(c_iterator hint, node_pointer n)
         {
           node_tmp a(n, this->node_alloc());
           const_key_type& k = this->get_key(a.node_);
           bucket_iterator itb = hint.itb;
           node_pointer p = hint.p;
 
           std::size_t key_hash = 0u;
 
           bool const needs_rehash = (size_ + 1 > max_load_);
           bool const usable_hint = (p && this->key_eq()(k, this->get_key(p)));
 
           if (!usable_hint) {
             key_hash = this->hash(k);
             itb = buckets_.at(buckets_.position(key_hash));
             p = this->find_node_impl(k, itb);
           } else if (usable_hint && needs_rehash) {
             key_hash = this->hash(k);
           }
 
           if (needs_rehash) {
             this->reserve(size_ + 1);
             itb = buckets_.at(buckets_.position(key_hash));
           }
 
           a.release();
           buckets_.insert_node_hint(itb, n, p);
           ++size_;
           return iterator(n, itb);
         }
 
         void emplace_no_rehash_equiv(node_pointer n)
         {
           BOOST_ASSERT(size_ + 1 <= max_load_);
           node_tmp a(n, this->node_alloc());
           const_key_type& k = this->get_key(a.node_);
           std::size_t key_hash = this->hash(k);
           bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
           node_pointer hint = this->find_node_impl(k, itb);
           node_pointer p = a.release();
           buckets_.insert_node_hint(itb, p, hint);
           ++size_;
         }
 
         template <typename NodeType>
         iterator move_insert_node_type_equiv(NodeType& np)
         {
           iterator result;
 
           if (np) {
             this->reserve_for_insert(size_ + 1);
 
             const_key_type& k = this->get_key(np.ptr_);
             std::size_t key_hash = this->hash(k);
 
             bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
 
             node_pointer hint = this->find_node_impl(k, itb);
             buckets_.insert_node_hint(itb, np.ptr_, hint);
             ++size_;
 
             result = iterator(np.ptr_, itb);
             np.ptr_ = node_pointer();
           }
 
           return result;
         }
 
         template <typename NodeType>
         iterator move_insert_node_type_with_hint_equiv(
           c_iterator hint, NodeType& np)
         {
           iterator result;
           if (np) {
             bucket_iterator itb = hint.itb;
             node_pointer pos = hint.p;
             const_key_type& k = this->get_key(np.ptr_);
             std::size_t key_hash = this->hash(k);
             if (size_ + 1 > max_load_) {
               this->reserve(size_ + 1);
               itb = buckets_.at(buckets_.position(key_hash));
             }
 
             if (hint.p && this->key_eq()(k, this->get_key(hint.p))) {
             } else {
               itb = buckets_.at(buckets_.position(key_hash));
               pos = this->find_node_impl(k, itb);
             }
             buckets_.insert_node_hint(itb, np.ptr_, pos);
             ++size_;
             result = iterator(np.ptr_, itb);
 
             np.ptr_ = node_pointer();
           }
 
           return result;
         }
 
         ////////////////////////////////////////////////////////////////////////
         // Insert range methods
 
         // if hash function throws, or inserting > 1 element, basic exception
         // safety. Strong otherwise
         template <class I>
         typename boost::unordered::detail::enable_if_forward<I, void>::type
         insert_range_equiv(I i, I j)
         {
           if (i == j)
             return;
 
           std::size_t distance = static_cast<std::size_t>(std::distance(i, j));
           if (distance == 1) {
             emplace_equiv(boost::unordered::detail::func::construct_node(
               this->node_alloc(), *i));
           } else {
             // Only require basic exception safety here
             this->reserve_for_insert(size_ + distance);
 
             for (; i != j; ++i) {
               emplace_no_rehash_equiv(
                 boost::unordered::detail::func::construct_node(
                   this->node_alloc(), *i));
             }
           }
         }
 
         template <class I>
         typename boost::unordered::detail::disable_if_forward<I, void>::type
         insert_range_equiv(I i, I j)
         {
           for (; i != j; ++i) {
             emplace_equiv(boost::unordered::detail::func::construct_node(
               this->node_alloc(), *i));
           }
         }
 
         ////////////////////////////////////////////////////////////////////////
         // Extract
 
         inline node_pointer extract_by_iterator_equiv(c_iterator n)
         {
           node_pointer p = n.p;
           bucket_iterator itb = n.itb;
           buckets_.extract_node(itb, p);
           --size_;
           return p;
         }
 
         ////////////////////////////////////////////////////////////////////////
         // Erase
         //
         // no throw
 
         template <class Key> std::size_t erase_key_equiv_impl(Key const& k)
         {
           std::size_t deleted_count = 0;
 
           bucket_iterator itb = buckets_.at(buckets_.position(this->hash(k)));
           node_pointer* pp = this->find_prev(k, itb);
           if (pp) {
             while (*pp && this->key_eq()(this->get_key(*pp), k)) {
               node_pointer p = *pp;
               *pp = (*pp)->next;
 
               this->delete_node(p);
               --size_;
               ++deleted_count;
             }
 
             if (!itb->next) {
               buckets_.unlink_bucket(itb);
             }
           }
           return deleted_count;
         }
 
         std::size_t erase_key_equiv(const_key_type& k)
         {
           return this->erase_key_equiv_impl(k);
         }
 
         ////////////////////////////////////////////////////////////////////////
         // fill_buckets
 
         void copy_buckets(table const& src, std::false_type)
         {
           BOOST_ASSERT(size_ == 0);
 
           this->reserve_for_insert(src.size_);
 
           iterator last = src.end();
           for (iterator pos = src.begin(); pos != last; ++pos) {
             value_type const& value = *pos;
             const_key_type& key = extractor::extract(value);
             std::size_t const key_hash = this->hash(key);
 
             bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
             node_allocator_type alloc = this->node_alloc();
             node_tmp tmp(detail::func::construct_node(alloc, value), alloc);
             node_pointer hint = this->find_node_impl(key, itb);
             buckets_.insert_node_hint(itb, tmp.release(), hint);
             ++size_;
           }
         }
 
         void move_assign_buckets(table& src, std::false_type)
         {
           BOOST_ASSERT(size_ == 0);
           BOOST_ASSERT(max_load_ >= src.size_);
 
           iterator last = src.end();
           node_allocator_type alloc = this->node_alloc();
 
           for (iterator pos = src.begin(); pos != last; ++pos) {
             value_type value = std::move(*pos);
             const_key_type& key = extractor::extract(value);
             std::size_t const key_hash = this->hash(key);
 
             bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
 
             node_pointer hint = this->find_node_impl(key, itb);
             node_tmp tmp(
               detail::func::construct_node(alloc, std::move(value)), alloc);
 
             buckets_.insert_node_hint(itb, tmp.release(), hint);
             ++size_;
           }
         }
       };
 
       //////////////////////////////////////////////////////////////////////////
       // Clear
 
       template <typename Types> inline void table<Types>::clear_impl()
       {
         bucket_iterator itb = buckets_.begin(), last = buckets_.end();
         for (; itb != last;) {
           bucket_iterator next_itb = itb;
           ++next_itb;
           node_pointer* pp = std::addressof(itb->next);
           while (*pp) {
             node_pointer p = *pp;
             buckets_.extract_node_after(itb, pp);
             this->delete_node(p);
             --size_;
           }
           itb = next_itb;
         }
       }
 
       //////////////////////////////////////////////////////////////////////////
       // Reserve & Rehash
 
       // if hash function throws, basic exception safety
       // strong otherwise.
       template <typename Types>
       inline void table<Types>::rehash(std::size_t num_buckets)
       {
         num_buckets = buckets_.bucket_count_for(
           (std::max)(min_buckets(size_, mlf_), num_buckets));
 
         if (num_buckets != this->bucket_count()) {
           this->rehash_impl(num_buckets);
         }
       }
 
       template <class Types>
       inline void table<Types>::reserve(std::size_t num_elements)
       {
         std::size_t num_buckets = min_buckets(num_elements, mlf_);
         this->rehash(num_buckets);
       }
 
       template <class Types>
       inline void table<Types>::reserve_for_insert(std::size_t num_elements)
       {
         if (num_elements > max_load_) {
           std::size_t const num_buckets = static_cast<std::size_t>(
             1.0f + std::ceil(static_cast<float>(num_elements) / mlf_));
 
           this->rehash_impl(num_buckets);
         }
       }
 
       template <class Types>
       inline void table<Types>::rehash_impl(std::size_t num_buckets)
       {
         bucket_array_type new_buckets(
           num_buckets, buckets_.get_allocator());
 
         BOOST_TRY
         {
           boost::unordered::detail::span<bucket_type> bspan = buckets_.raw();
 
           bucket_type* pos = bspan.data;
           std::size_t size = bspan.size;
           bucket_type* last = pos + size;
 
           for (; pos != last; ++pos) {
             bucket_type& b = *pos;
             for (node_pointer p = b.next; p;) {
               node_pointer next_p = p->next;
               transfer_node(p, b, new_buckets);
               p = next_p;
               b.next = p;
             }
           }
         }
         BOOST_CATCH(...)
         {
           for (bucket_iterator pos = new_buckets.begin();
                pos != new_buckets.end(); ++pos) {
             bucket_type& b = *pos;
             for (node_pointer p = b.next; p;) {
               node_pointer next_p = p->next;
               delete_node(p);
               --size_;
               p = next_p;
             }
           }
           buckets_.unlink_empty_buckets();
           BOOST_RETHROW
         }
         BOOST_CATCH_END
 
         buckets_ = std::move(new_buckets);
         recalculate_max_load();
       }
 
 #if defined(BOOST_MSVC)
 #pragma warning(pop)
 #endif
 
       ////////////////////////////////////////////////////////////////////////
       // key extractors
       //
       // no throw
       //
       // 'extract_key' is called with the emplace parameters to return a
       // key if available or 'no_key' is one isn't and will need to be
       // constructed. This could be done by overloading the emplace
       // implementation
       // for the different cases, but that's a bit tricky on compilers without
       // variadic templates.
 
       template <typename Key, typename T> struct is_key
       {
         template <typename T2> static choice1::type test(T2 const&);
         static choice2::type test(Key const&);
 
         enum
         {
           value = sizeof(test(boost::unordered::detail::make<T>())) ==
                   sizeof(choice2::type)
         };
 
         typedef typename std::conditional<value, Key const&, no_key>::type type;
       };
 
       template <class ValueType> struct set_extractor
       {
         typedef ValueType value_type;
         typedef ValueType key_type;
 
         static key_type const& extract(value_type const& v) { return v; }
 
         static key_type const& extract(value_type&& v) { return v; }
 
         static no_key extract() { return no_key(); }
 
         template <class Arg> static no_key extract(Arg const&)
         {
           return no_key();
         }
 
         template <class Arg1, class Arg2, class... Args>
         static no_key extract(Arg1 const&, Arg2 const&, Args const&...)
         {
           return no_key();
         }
       };
 
       template <class ValueType> struct map_extractor
       {
         typedef ValueType value_type;
         typedef typename std::remove_const<typename boost::unordered::detail::
             pair_traits<ValueType>::first_type>::type key_type;
 
         static key_type const& extract(value_type const& v) { return v.first; }
 
         template <class Second>
         static key_type const& extract(std::pair<key_type, Second> const& v)
         {
           return v.first;
         }
 
         template <class Second>
         static key_type const& extract(
           std::pair<key_type const, Second> const& v)
         {
           return v.first;
         }
 
         template <class Arg1>
         static key_type const& extract(key_type const& k, Arg1 const&)
         {
           return k;
         }
 
         static no_key extract() { return no_key(); }
 
         template <class Arg> static no_key extract(Arg const&)
         {
           return no_key();
         }
 
         template <class Arg1, class Arg2>
         static typename std::conditional<
           (is_similar<Arg1, key_type>::value ||
             is_complete_and_move_constructible<key_type>::value),
           converting_key, no_key>::type
         extract(Arg1 const&, Arg2 const&)
         {
           return {};
         }
 
         template <class Arg1, class Arg2, class Arg3, class... Args>
         static no_key extract(
           Arg1 const&, Arg2 const&, Arg3 const&, Args const&...)
         {
           return no_key();
         }
 
         template <template <class...> class Tuple, typename T2>
         static no_key extract(
           std::piecewise_construct_t, Tuple<> const&, T2 const&)
         {
           return no_key();
         }
 
         template <template <typename...> class Tuple, typename T, typename T2,
           typename... Args>
         static auto extract(
           std::piecewise_construct_t, Tuple<T, Args...> const& k, T2 const&) ->
           typename std::enable_if<
             !std::is_same<T, boost::tuples::null_type>::value,
             typename is_key<key_type, T>::type>::type
         {
           using std::get;
           return typename is_key<key_type, T>::type(get<0>(k));
         }
       };
 
       template <class Container, class Predicate>
       typename Container::size_type erase_if(Container& c, Predicate& pred)
       {
         typedef typename Container::size_type size_type;
         typedef typename Container::iterator iterator;
 
         size_type const size = c.size();
 
         for (iterator pos = c.begin(), last = c.end(); pos != last;) {
           if (pred(*pos)) {
             pos = c.erase(pos);
           } else {
             ++pos;
           }
         }
 
         return (size - c.size());
       }
     } // namespace detail
   } // namespace unordered
 } // namespace boost
 
 #endif