EIC code displayed by LXR master/​include/​c++/​v1/​__cxx03/​__hash_table	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

Warning, /include/c++/v1/__cxx03/__hash_table is written in an unsupported language. File is not indexed.

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___CXX03___HASH_TABLE
 #define _LIBCPP___CXX03___HASH_TABLE
 
 #include <__cxx03/__algorithm/max.h>
 #include <__cxx03/__algorithm/min.h>
 #include <__cxx03/__assert>
 #include <__cxx03/__bit/countl.h>
 #include <__cxx03/__config>
 #include <__cxx03/__functional/hash.h>
 #include <__cxx03/__functional/invoke.h>
 #include <__cxx03/__iterator/iterator_traits.h>
 #include <__cxx03/__memory/addressof.h>
 #include <__cxx03/__memory/allocator_traits.h>
 #include <__cxx03/__memory/compressed_pair.h>
 #include <__cxx03/__memory/construct_at.h>
 #include <__cxx03/__memory/pointer_traits.h>
 #include <__cxx03/__memory/swap_allocator.h>
 #include <__cxx03/__memory/unique_ptr.h>
 #include <__cxx03/__type_traits/can_extract_key.h>
 #include <__cxx03/__type_traits/conditional.h>
 #include <__cxx03/__type_traits/is_const.h>
 #include <__cxx03/__type_traits/is_constructible.h>
 #include <__cxx03/__type_traits/is_nothrow_assignable.h>
 #include <__cxx03/__type_traits/is_nothrow_constructible.h>
 #include <__cxx03/__type_traits/is_pointer.h>
 #include <__cxx03/__type_traits/is_reference.h>
 #include <__cxx03/__type_traits/is_swappable.h>
 #include <__cxx03/__type_traits/remove_const.h>
 #include <__cxx03/__type_traits/remove_cvref.h>
 #include <__cxx03/__utility/forward.h>
 #include <__cxx03/__utility/move.h>
 #include <__cxx03/__utility/pair.h>
 #include <__cxx03/__utility/swap.h>
 #include <__cxx03/cmath>
 #include <__cxx03/cstring>
 #include <__cxx03/initializer_list>
 #include <__cxx03/new> // __launder
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__cxx03/__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Key, class _Tp>
 struct __hash_value_type;
 
 template <class _Tp>
 struct __is_hash_value_type_imp : false_type {};
 
 template <class _Key, class _Value>
 struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value> > : true_type {};
 
 template <class... _Args>
 struct __is_hash_value_type : false_type {};
 
 template <class _One>
 struct __is_hash_value_type<_One> : __is_hash_value_type_imp<__remove_cvref_t<_One> > {};
 
 _LIBCPP_EXPORTED_FROM_ABI size_t __next_prime(size_t __n);
 
 template <class _NodePtr>
 struct __hash_node_base {
   typedef typename pointer_traits<_NodePtr>::element_type __node_type;
   typedef __hash_node_base __first_node;
   typedef __rebind_pointer_t<_NodePtr, __first_node> __node_base_pointer;
   typedef _NodePtr __node_pointer;
 
 #if defined(_LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB)
   typedef __node_base_pointer __next_pointer;
 #else
   typedef __conditional_t<is_pointer<__node_pointer>::value, __node_base_pointer, __node_pointer> __next_pointer;
 #endif
 
   __next_pointer __next_;
 
   _LIBCPP_HIDE_FROM_ABI __next_pointer __ptr() _NOEXCEPT {
     return static_cast<__next_pointer>(pointer_traits<__node_base_pointer>::pointer_to(*this));
   }
 
   _LIBCPP_HIDE_FROM_ABI __node_pointer __upcast() _NOEXCEPT {
     return static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(*this));
   }
 
   _LIBCPP_HIDE_FROM_ABI size_t __hash() const _NOEXCEPT { return static_cast<__node_type const&>(*this).__hash_; }
 
   _LIBCPP_HIDE_FROM_ABI __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
   _LIBCPP_HIDE_FROM_ABI explicit __hash_node_base(__next_pointer __next) _NOEXCEPT : __next_(__next) {}
 };
 
 template <class _Tp, class _VoidPtr>
 struct __hash_node : public __hash_node_base< __rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > > {
   typedef _Tp __node_value_type;
   using _Base          = __hash_node_base<__rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > >;
   using __next_pointer = typename _Base::__next_pointer;
 
   size_t __hash_;
 
   // We allow starting the lifetime of nodes without initializing the value held by the node,
   // since that is handled by the hash table itself in order to be allocator-aware.
 #ifndef _LIBCPP_CXX03_LANG
 
 private:
   union {
     _Tp __value_;
   };
 
 public:
   _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }
 #else
 
 private:
   _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];
 
 public:
   _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); }
 #endif
 
   _LIBCPP_HIDE_FROM_ABI explicit __hash_node(__next_pointer __next, size_t __hash) : _Base(__next), __hash_(__hash) {}
   _LIBCPP_HIDE_FROM_ABI ~__hash_node() {}
 };
 
 inline _LIBCPP_HIDE_FROM_ABI bool __is_hash_power2(size_t __bc) { return __bc > 2 && !(__bc & (__bc - 1)); }
 
 inline _LIBCPP_HIDE_FROM_ABI size_t __constrain_hash(size_t __h, size_t __bc) {
   return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : (__h < __bc ? __h : __h % __bc);
 }
 
 inline _LIBCPP_HIDE_FROM_ABI size_t __next_hash_pow2(size_t __n) {
   return __n < 2 ? __n : (size_t(1) << (numeric_limits<size_t>::digits - __libcpp_clz(__n - 1)));
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 class __hash_table;
 
 template <class _NodePtr>
 class _LIBCPP_TEMPLATE_VIS __hash_iterator;
 template <class _ConstNodePtr>
 class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
 template <class _NodePtr>
 class _LIBCPP_TEMPLATE_VIS __hash_local_iterator;
 template <class _ConstNodePtr>
 class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
 template <class _HashIterator>
 class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
 template <class _HashIterator>
 class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
 
 template <class _Tp>
 struct __hash_key_value_types {
   static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, "");
   typedef _Tp key_type;
   typedef _Tp __node_value_type;
   typedef _Tp __container_value_type;
   static const bool __is_map = false;
 
   _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(_Tp const& __v) { return __v; }
   _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(__node_value_type const& __v) { return __v; }
   _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) { return std::addressof(__n); }
   _LIBCPP_HIDE_FROM_ABI static __container_value_type&& __move(__node_value_type& __v) { return std::move(__v); }
 };
 
 template <class _Key, class _Tp>
 struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > {
   typedef _Key key_type;
   typedef _Tp mapped_type;
   typedef __hash_value_type<_Key, _Tp> __node_value_type;
   typedef pair<const _Key, _Tp> __container_value_type;
   typedef __container_value_type __map_value_type;
   static const bool __is_map = true;
 
   _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(__container_value_type const& __v) { return __v.first; }
 
   template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __node_value_type>::value, int> = 0>
   _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(_Up& __t) {
     return __t.__get_value();
   }
 
   template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __container_value_type>::value, int> = 0>
   _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(_Up& __t) {
     return __t;
   }
 
   _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) {
     return std::addressof(__n.__get_value());
   }
   _LIBCPP_HIDE_FROM_ABI static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) { return __v.__move(); }
 };
 
 template <class _Tp, class _AllocPtr, class _KVTypes = __hash_key_value_types<_Tp>, bool = _KVTypes::__is_map>
 struct __hash_map_pointer_types {};
 
 template <class _Tp, class _AllocPtr, class _KVTypes>
 struct __hash_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> {
   typedef typename _KVTypes::__map_value_type _Mv;
   typedef __rebind_pointer_t<_AllocPtr, _Mv> __map_value_type_pointer;
   typedef __rebind_pointer_t<_AllocPtr, const _Mv> __const_map_value_type_pointer;
 };
 
 template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>
 struct __hash_node_types;
 
 template <class _NodePtr, class _Tp, class _VoidPtr>
 struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> >
     : public __hash_key_value_types<_Tp>,
       __hash_map_pointer_types<_Tp, _VoidPtr>
 
 {
   typedef __hash_key_value_types<_Tp> __base;
 
 public:
   typedef ptrdiff_t difference_type;
   typedef size_t size_type;
 
   typedef __rebind_pointer_t<_NodePtr, void> __void_pointer;
 
   typedef typename pointer_traits<_NodePtr>::element_type __node_type;
   typedef _NodePtr __node_pointer;
 
   typedef __hash_node_base<__node_pointer> __node_base_type;
   typedef __rebind_pointer_t<_NodePtr, __node_base_type> __node_base_pointer;
 
   typedef typename __node_base_type::__next_pointer __next_pointer;
 
   typedef _Tp __node_value_type;
   typedef __rebind_pointer_t<_VoidPtr, __node_value_type> __node_value_type_pointer;
   typedef __rebind_pointer_t<_VoidPtr, const __node_value_type> __const_node_value_type_pointer;
 
 private:
   static_assert(!is_const<__node_type>::value, "_NodePtr should never be a pointer to const");
   static_assert(is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value,
                 "_VoidPtr does not point to unqualified void type");
   static_assert(is_same<__rebind_pointer_t<_VoidPtr, __node_type>, _NodePtr>::value,
                 "_VoidPtr does not rebind to _NodePtr.");
 };
 
 template <class _HashIterator>
 struct __hash_node_types_from_iterator;
 template <class _NodePtr>
 struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 template <class _NodePtr>
 struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 template <class _NodePtr>
 struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 template <class _NodePtr>
 struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 
 template <class _NodeValueTp, class _VoidPtr>
 struct __make_hash_node_types {
   typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp;
   typedef __rebind_pointer_t<_VoidPtr, _NodeTp> _NodePtr;
   typedef __hash_node_types<_NodePtr> type;
 };
 
 template <class _NodePtr>
 class _LIBCPP_TEMPLATE_VIS __hash_iterator {
   typedef __hash_node_types<_NodePtr> _NodeTypes;
   typedef _NodePtr __node_pointer;
   typedef typename _NodeTypes::__next_pointer __next_pointer;
 
   __next_pointer __node_;
 
 public:
   typedef forward_iterator_tag iterator_category;
   typedef typename _NodeTypes::__node_value_type value_type;
   typedef typename _NodeTypes::difference_type difference_type;
   typedef value_type& reference;
   typedef typename _NodeTypes::__node_value_type_pointer pointer;
 
   _LIBCPP_HIDE_FROM_ABI __hash_iterator() _NOEXCEPT : __node_(nullptr) {}
 
   _LIBCPP_HIDE_FROM_ABI reference operator*() const {
     _LIBCPP_ASSERT_NON_NULL(
         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container iterator");
     return __node_->__upcast()->__get_value();
   }
 
   _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
     _LIBCPP_ASSERT_NON_NULL(
         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container iterator");
     return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
   }
 
   _LIBCPP_HIDE_FROM_ABI __hash_iterator& operator++() {
     _LIBCPP_ASSERT_NON_NULL(
         __node_ != nullptr, "Attempted to increment a non-incrementable unordered container iterator");
     __node_ = __node_->__next_;
     return *this;
   }
 
   _LIBCPP_HIDE_FROM_ABI __hash_iterator operator++(int) {
     __hash_iterator __t(*this);
     ++(*this);
     return __t;
   }
 
   friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) {
     return __x.__node_ == __y.__node_;
   }
   friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) {
     return !(__x == __y);
   }
 
 private:
   _LIBCPP_HIDE_FROM_ABI explicit __hash_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) {}
 
   template <class, class, class, class>
   friend class __hash_table;
   template <class>
   friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
   template <class>
   friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
   template <class, class, class, class, class>
   friend class _LIBCPP_TEMPLATE_VIS unordered_map;
   template <class, class, class, class, class>
   friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
 };
 
 template <class _NodePtr>
 class _LIBCPP_TEMPLATE_VIS __hash_const_iterator {
   static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, "");
   typedef __hash_node_types<_NodePtr> _NodeTypes;
   typedef _NodePtr __node_pointer;
   typedef typename _NodeTypes::__next_pointer __next_pointer;
 
   __next_pointer __node_;
 
 public:
   typedef __hash_iterator<_NodePtr> __non_const_iterator;
 
   typedef forward_iterator_tag iterator_category;
   typedef typename _NodeTypes::__node_value_type value_type;
   typedef typename _NodeTypes::difference_type difference_type;
   typedef const value_type& reference;
   typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
 
   _LIBCPP_HIDE_FROM_ABI __hash_const_iterator() _NOEXCEPT : __node_(nullptr) {}
 
   _LIBCPP_HIDE_FROM_ABI __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT : __node_(__x.__node_) {}
 
   _LIBCPP_HIDE_FROM_ABI reference operator*() const {
     _LIBCPP_ASSERT_NON_NULL(
         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_iterator");
     return __node_->__upcast()->__get_value();
   }
   _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
     _LIBCPP_ASSERT_NON_NULL(
         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_iterator");
     return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
   }
 
   _LIBCPP_HIDE_FROM_ABI __hash_const_iterator& operator++() {
     _LIBCPP_ASSERT_NON_NULL(
         __node_ != nullptr, "Attempted to increment a non-incrementable unordered container const_iterator");
     __node_ = __node_->__next_;
     return *this;
   }
 
   _LIBCPP_HIDE_FROM_ABI __hash_const_iterator operator++(int) {
     __hash_const_iterator __t(*this);
     ++(*this);
     return __t;
   }
 
   friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) {
     return __x.__node_ == __y.__node_;
   }
   friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) {
     return !(__x == __y);
   }
 
 private:
   _LIBCPP_HIDE_FROM_ABI explicit __hash_const_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) {}
 
   template <class, class, class, class>
   friend class __hash_table;
   template <class>
   friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
   template <class, class, class, class, class>
   friend class _LIBCPP_TEMPLATE_VIS unordered_map;
   template <class, class, class, class, class>
   friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
 };
 
 template <class _NodePtr>
 class _LIBCPP_TEMPLATE_VIS __hash_local_iterator {
   typedef __hash_node_types<_NodePtr> _NodeTypes;
   typedef _NodePtr __node_pointer;
   typedef typename _NodeTypes::__next_pointer __next_pointer;
 
   __next_pointer __node_;
   size_t __bucket_;
   size_t __bucket_count_;
 
 public:
   typedef forward_iterator_tag iterator_category;
   typedef typename _NodeTypes::__node_value_type value_type;
   typedef typename _NodeTypes::difference_type difference_type;
   typedef value_type& reference;
   typedef typename _NodeTypes::__node_value_type_pointer pointer;
 
   _LIBCPP_HIDE_FROM_ABI __hash_local_iterator() _NOEXCEPT : __node_(nullptr) {}
 
   _LIBCPP_HIDE_FROM_ABI reference operator*() const {
     _LIBCPP_ASSERT_NON_NULL(
         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container local_iterator");
     return __node_->__upcast()->__get_value();
   }
 
   _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
     _LIBCPP_ASSERT_NON_NULL(
         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container local_iterator");
     return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
   }
 
   _LIBCPP_HIDE_FROM_ABI __hash_local_iterator& operator++() {
     _LIBCPP_ASSERT_NON_NULL(
         __node_ != nullptr, "Attempted to increment a non-incrementable unordered container local_iterator");
     __node_ = __node_->__next_;
     if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
       __node_ = nullptr;
     return *this;
   }
 
   _LIBCPP_HIDE_FROM_ABI __hash_local_iterator operator++(int) {
     __hash_local_iterator __t(*this);
     ++(*this);
     return __t;
   }
 
   friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) {
     return __x.__node_ == __y.__node_;
   }
   friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) {
     return !(__x == __y);
   }
 
 private:
   _LIBCPP_HIDE_FROM_ABI explicit __hash_local_iterator(
       __next_pointer __node, size_t __bucket, size_t __bucket_count) _NOEXCEPT
       : __node_(__node),
         __bucket_(__bucket),
         __bucket_count_(__bucket_count) {
     if (__node_ != nullptr)
       __node_ = __node_->__next_;
   }
 
   template <class, class, class, class>
   friend class __hash_table;
   template <class>
   friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
   template <class>
   friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
 };
 
 template <class _ConstNodePtr>
 class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator {
   typedef __hash_node_types<_ConstNodePtr> _NodeTypes;
   typedef _ConstNodePtr __node_pointer;
   typedef typename _NodeTypes::__next_pointer __next_pointer;
 
   __next_pointer __node_;
   size_t __bucket_;
   size_t __bucket_count_;
 
   typedef pointer_traits<__node_pointer> __pointer_traits;
   typedef typename __pointer_traits::element_type __node;
   typedef __remove_const_t<__node> __non_const_node;
   typedef __rebind_pointer_t<__node_pointer, __non_const_node> __non_const_node_pointer;
 
 public:
   typedef __hash_local_iterator<__non_const_node_pointer> __non_const_iterator;
 
   typedef forward_iterator_tag iterator_category;
   typedef typename _NodeTypes::__node_value_type value_type;
   typedef typename _NodeTypes::difference_type difference_type;
   typedef const value_type& reference;
   typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
 
   _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) {}
 
   _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
       : __node_(__x.__node_),
         __bucket_(__x.__bucket_),
         __bucket_count_(__x.__bucket_count_) {}
 
   _LIBCPP_HIDE_FROM_ABI reference operator*() const {
     _LIBCPP_ASSERT_NON_NULL(
         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
     return __node_->__upcast()->__get_value();
   }
 
   _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
     _LIBCPP_ASSERT_NON_NULL(
         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
     return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
   }
 
   _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator& operator++() {
     _LIBCPP_ASSERT_NON_NULL(
         __node_ != nullptr, "Attempted to increment a non-incrementable unordered container const_local_iterator");
     __node_ = __node_->__next_;
     if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
       __node_ = nullptr;
     return *this;
   }
 
   _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator operator++(int) {
     __hash_const_local_iterator __t(*this);
     ++(*this);
     return __t;
   }
 
   friend _LIBCPP_HIDE_FROM_ABI bool
   operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) {
     return __x.__node_ == __y.__node_;
   }
   friend _LIBCPP_HIDE_FROM_ABI bool
   operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) {
     return !(__x == __y);
   }
 
 private:
   _LIBCPP_HIDE_FROM_ABI explicit __hash_const_local_iterator(
       __next_pointer __node_ptr, size_t __bucket, size_t __bucket_count) _NOEXCEPT
       : __node_(__node_ptr),
         __bucket_(__bucket),
         __bucket_count_(__bucket_count) {
     if (__node_ != nullptr)
       __node_ = __node_->__next_;
   }
 
   template <class, class, class, class>
   friend class __hash_table;
   template <class>
   friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
 };
 
 template <class _Alloc>
 class __bucket_list_deallocator {
   typedef _Alloc allocator_type;
   typedef allocator_traits<allocator_type> __alloc_traits;
   typedef typename __alloc_traits::size_type size_type;
 
   __compressed_pair<size_type, allocator_type> __data_;
 
 public:
   typedef typename __alloc_traits::pointer pointer;
 
   _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
       : __data_(0, __default_init_tag()) {}
 
   _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator(const allocator_type& __a, size_type __size)
       _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
       : __data_(__size, __a) {}
 
   _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator(__bucket_list_deallocator&& __x)
       _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
       : __data_(std::move(__x.__data_)) {
     __x.size() = 0;
   }
 
   _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT { return __data_.first(); }
   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __data_.first(); }
 
   _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT { return __data_.second(); }
   _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT { return __data_.second(); }
 
   _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { __alloc_traits::deallocate(__alloc(), __p, size()); }
 };
 
 template <class _Alloc>
 class __hash_map_node_destructor;
 
 template <class _Alloc>
 class __hash_node_destructor {
   typedef _Alloc allocator_type;
   typedef allocator_traits<allocator_type> __alloc_traits;
 
 public:
   typedef typename __alloc_traits::pointer pointer;
 
 private:
   typedef __hash_node_types<pointer> _NodeTypes;
 
   allocator_type& __na_;
 
 public:
   bool __value_constructed;
 
   _LIBCPP_HIDE_FROM_ABI __hash_node_destructor(__hash_node_destructor const&)            = default;
   _LIBCPP_HIDE_FROM_ABI __hash_node_destructor& operator=(const __hash_node_destructor&) = delete;
 
   _LIBCPP_HIDE_FROM_ABI explicit __hash_node_destructor(allocator_type& __na, bool __constructed = false) _NOEXCEPT
       : __na_(__na),
         __value_constructed(__constructed) {}
 
   _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {
     if (__value_constructed) {
       __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__get_value()));
       std::__destroy_at(std::addressof(*__p));
     }
     if (__p)
       __alloc_traits::deallocate(__na_, __p, 1);
   }
 
   template <class>
   friend class __hash_map_node_destructor;
 };
 
 #if _LIBCPP_STD_VER >= 17
 template <class _NodeType, class _Alloc>
 struct __generic_container_node_destructor;
 
 template <class _Tp, class _VoidPtr, class _Alloc>
 struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc> : __hash_node_destructor<_Alloc> {
   using __hash_node_destructor<_Alloc>::__hash_node_destructor;
 };
 #endif
 
 template <class _Key, class _Hash, class _Equal>
 struct __enforce_unordered_container_requirements {
 #ifndef _LIBCPP_CXX03_LANG
   static_assert(__check_hash_requirements<_Key, _Hash>::value,
                 "the specified hash does not meet the Hash requirements");
   static_assert(is_copy_constructible<_Equal>::value, "the specified comparator is required to be copy constructible");
 #endif
   typedef int type;
 };
 
 template <class _Key, class _Hash, class _Equal>
 #ifndef _LIBCPP_CXX03_LANG
 _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Equal const&, _Key const&, _Key const&>::value,
                          "the specified comparator type does not provide a viable const call operator")
 _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Hash const&, _Key const&>::value,
                          "the specified hash functor does not provide a viable const call operator")
 #endif
     typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type
     __diagnose_unordered_container_requirements(int);
 
 // This dummy overload is used so that the compiler won't emit a spurious
 // "no matching function for call to __diagnose_unordered_xxx" diagnostic
 // when the overload above causes a hard error.
 template <class _Key, class _Hash, class _Equal>
 int __diagnose_unordered_container_requirements(void*);
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 class __hash_table {
 public:
   typedef _Tp value_type;
   typedef _Hash hasher;
   typedef _Equal key_equal;
   typedef _Alloc allocator_type;
 
 private:
   typedef allocator_traits<allocator_type> __alloc_traits;
   typedef typename __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type _NodeTypes;
 
 public:
   typedef typename _NodeTypes::__node_value_type __node_value_type;
   typedef typename _NodeTypes::__container_value_type __container_value_type;
   typedef typename _NodeTypes::key_type key_type;
   typedef value_type& reference;
   typedef const value_type& const_reference;
   typedef typename __alloc_traits::pointer pointer;
   typedef typename __alloc_traits::const_pointer const_pointer;
 #ifndef _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE
   typedef typename __alloc_traits::size_type size_type;
 #else
   typedef typename _NodeTypes::size_type size_type;
 #endif
   typedef typename _NodeTypes::difference_type difference_type;
 
 public:
   // Create __node
 
   typedef typename _NodeTypes::__node_type __node;
   typedef __rebind_alloc<__alloc_traits, __node> __node_allocator;
   typedef allocator_traits<__node_allocator> __node_traits;
   typedef typename _NodeTypes::__void_pointer __void_pointer;
   typedef typename _NodeTypes::__node_pointer __node_pointer;
   typedef typename _NodeTypes::__node_pointer __node_const_pointer;
   typedef typename _NodeTypes::__node_base_type __first_node;
   typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;
   typedef typename _NodeTypes::__next_pointer __next_pointer;
 
 private:
   // check for sane allocator pointer rebinding semantics. Rebinding the
   // allocator for a new pointer type should be exactly the same as rebinding
   // the pointer using 'pointer_traits'.
   static_assert(is_same<__node_pointer, typename __node_traits::pointer>::value,
                 "Allocator does not rebind pointers in a sane manner.");
   typedef __rebind_alloc<__node_traits, __first_node> __node_base_allocator;
   typedef allocator_traits<__node_base_allocator> __node_base_traits;
   static_assert(is_same<__node_base_pointer, typename __node_base_traits::pointer>::value,
                 "Allocator does not rebind pointers in a sane manner.");
 
 private:
   typedef __rebind_alloc<__node_traits, __next_pointer> __pointer_allocator;
   typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
   typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;
   typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits;
   typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;
 
   // --- Member data begin ---
   __bucket_list __bucket_list_;
   __compressed_pair<__first_node, __node_allocator> __p1_;
   __compressed_pair<size_type, hasher> __p2_;
   __compressed_pair<float, key_equal> __p3_;
   // --- Member data end ---
 
   _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT { return __p2_.first(); }
 
 public:
   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __p2_.first(); }
 
   _LIBCPP_HIDE_FROM_ABI hasher& hash_function() _NOEXCEPT { return __p2_.second(); }
   _LIBCPP_HIDE_FROM_ABI const hasher& hash_function() const _NOEXCEPT { return __p2_.second(); }
 
   _LIBCPP_HIDE_FROM_ABI float& max_load_factor() _NOEXCEPT { return __p3_.first(); }
   _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __p3_.first(); }
 
   _LIBCPP_HIDE_FROM_ABI key_equal& key_eq() _NOEXCEPT { return __p3_.second(); }
   _LIBCPP_HIDE_FROM_ABI const key_equal& key_eq() const _NOEXCEPT { return __p3_.second(); }
 
   _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __p1_.second(); }
   _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __p1_.second(); }
 
 public:
   typedef __hash_iterator<__node_pointer> iterator;
   typedef __hash_const_iterator<__node_pointer> const_iterator;
   typedef __hash_local_iterator<__node_pointer> local_iterator;
   typedef __hash_const_local_iterator<__node_pointer> const_local_iterator;
 
   _LIBCPP_HIDE_FROM_ABI __hash_table() _NOEXCEPT_(
       is_nothrow_default_constructible<__bucket_list>::value&& is_nothrow_default_constructible<__first_node>::value&&
           is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_default_constructible<hasher>::value&&
               is_nothrow_default_constructible<key_equal>::value);
   _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql);
   _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
   _LIBCPP_HIDE_FROM_ABI explicit __hash_table(const allocator_type& __a);
   _LIBCPP_HIDE_FROM_ABI __hash_table(const __hash_table& __u);
   _LIBCPP_HIDE_FROM_ABI __hash_table(const __hash_table& __u, const allocator_type& __a);
   _LIBCPP_HIDE_FROM_ABI __hash_table(__hash_table&& __u) _NOEXCEPT_(
       is_nothrow_move_constructible<__bucket_list>::value&& is_nothrow_move_constructible<__first_node>::value&&
           is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<hasher>::value&&
               is_nothrow_move_constructible<key_equal>::value);
   _LIBCPP_HIDE_FROM_ABI __hash_table(__hash_table&& __u, const allocator_type& __a);
   _LIBCPP_HIDE_FROM_ABI ~__hash_table();
 
   _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(const __hash_table& __u);
   _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(__hash_table&& __u)
       _NOEXCEPT_(__node_traits::propagate_on_container_move_assignment::value&&
                      is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
                          is_nothrow_move_assignable<key_equal>::value);
   template <class _InputIterator>
   _LIBCPP_HIDE_FROM_ABI void __assign_unique(_InputIterator __first, _InputIterator __last);
   template <class _InputIterator>
   _LIBCPP_HIDE_FROM_ABI void __assign_multi(_InputIterator __first, _InputIterator __last);
 
   _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {
     return std::min<size_type>(__node_traits::max_size(__node_alloc()), numeric_limits<difference_type >::max());
   }
 
 private:
   _LIBCPP_HIDE_FROM_ABI __next_pointer __node_insert_multi_prepare(size_t __cp_hash, value_type& __cp_val);
   _LIBCPP_HIDE_FROM_ABI void __node_insert_multi_perform(__node_pointer __cp, __next_pointer __pn) _NOEXCEPT;
 
   _LIBCPP_HIDE_FROM_ABI __next_pointer __node_insert_unique_prepare(size_t __nd_hash, value_type& __nd_val);
   _LIBCPP_HIDE_FROM_ABI void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT;
 
 public:
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
   _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd);
   _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
 
   template <class _Key, class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
 
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
 
   template <class _Pp>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) {
     return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());
   }
 
   template <class _First,
             class _Second,
             __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, int> = 0>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) {
     return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s));
   }
 
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) {
     return __emplace_unique_impl(std::forward<_Args>(__args)...);
   }
 
   template <class _Pp>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
     return __emplace_unique_impl(std::forward<_Pp>(__x));
   }
   template <class _Pp>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
     return __emplace_unique_key_args(__x, std::forward<_Pp>(__x));
   }
   template <class _Pp>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
     return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x));
   }
 
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args);
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
 
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(__container_value_type&& __x) {
     return __emplace_unique_key_args(_NodeTypes::__get_key(__x), std::move(__x));
   }
 
   template <class _Pp, __enable_if_t<!__is_same_uncvref<_Pp, __container_value_type>::value, int> = 0>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(_Pp&& __x) {
     return __emplace_unique(std::forward<_Pp>(__x));
   }
 
   template <class _Pp>
   _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(_Pp&& __x) {
     return __emplace_multi(std::forward<_Pp>(__x));
   }
 
   template <class _Pp>
   _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(const_iterator __p, _Pp&& __x) {
     return __emplace_hint_multi(__p, std::forward<_Pp>(__x));
   }
 
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(const __container_value_type& __x) {
     return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
   }
 
 #if _LIBCPP_STD_VER >= 17
   template <class _NodeHandle, class _InsertReturnType>
   _LIBCPP_HIDE_FROM_ABI _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh);
   template <class _NodeHandle>
   _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh);
   template <class _Table>
   _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_unique(_Table& __source);
 
   template <class _NodeHandle>
   _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(_NodeHandle&& __nh);
   template <class _NodeHandle>
   _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);
   template <class _Table>
   _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_multi(_Table& __source);
 
   template <class _NodeHandle>
   _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(key_type const& __key);
   template <class _NodeHandle>
   _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(const_iterator __it);
 #endif
 
   _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
   _LIBCPP_HIDE_FROM_ABI void __rehash_unique(size_type __n) { __rehash<true>(__n); }
   _LIBCPP_HIDE_FROM_ABI void __rehash_multi(size_type __n) { __rehash<false>(__n); }
   _LIBCPP_HIDE_FROM_ABI void __reserve_unique(size_type __n) {
     __rehash_unique(static_cast<size_type>(std::ceil(__n / max_load_factor())));
   }
   _LIBCPP_HIDE_FROM_ABI void __reserve_multi(size_type __n) {
     __rehash_multi(static_cast<size_type>(std::ceil(__n / max_load_factor())));
   }
 
   _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __bucket_list_.get_deleter().size(); }
 
   _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT;
   _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT;
   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT;
   _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT;
 
   template <class _Key>
   _LIBCPP_HIDE_FROM_ABI size_type bucket(const _Key& __k) const {
     _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
         bucket_count() > 0, "unordered container::bucket(key) called when bucket_count() == 0");
     return std::__constrain_hash(hash_function()(__k), bucket_count());
   }
 
   template <class _Key>
   _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __x);
   template <class _Key>
   _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __x) const;
 
   typedef __hash_node_destructor<__node_allocator> _Dp;
   typedef unique_ptr<__node, _Dp> __node_holder;
 
   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);
   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last);
   template <class _Key>
   _LIBCPP_HIDE_FROM_ABI size_type __erase_unique(const _Key& __k);
   template <class _Key>
   _LIBCPP_HIDE_FROM_ABI size_type __erase_multi(const _Key& __k);
   _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT;
 
   template <class _Key>
   _LIBCPP_HIDE_FROM_ABI size_type __count_unique(const _Key& __k) const;
   template <class _Key>
   _LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const;
 
   template <class _Key>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_unique(const _Key& __k);
   template <class _Key>
   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_unique(const _Key& __k) const;
 
   template <class _Key>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_multi(const _Key& __k);
   template <class _Key>
   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_multi(const _Key& __k) const;
 
   _LIBCPP_HIDE_FROM_ABI void swap(__hash_table& __u)
 #if _LIBCPP_STD_VER <= 11
       _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal> &&
                  (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
                   __is_nothrow_swappable_v<__pointer_allocator>) &&
                  (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>));
 #else
       _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal>);
 #endif
 
   _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return max_size(); }
   _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const;
   _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT {
     size_type __bc = bucket_count();
     return __bc != 0 ? (float)size() / __bc : 0.f;
   }
   _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) _NOEXCEPT {
     // While passing a non-positive load factor is undefined behavior, in practice the result will be benign (the
     // call will be equivalent to `max_load_factor(load_factor())`, which is also the case for passing a valid value
     // less than the current `load_factor`).
     _LIBCPP_ASSERT_PEDANTIC(__mlf > 0, "unordered container::max_load_factor(lf) called with lf <= 0");
     max_load_factor() = std::max(__mlf, load_factor());
   }
 
   _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) {
     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
         __n < bucket_count(), "unordered container::begin(n) called with n >= bucket_count()");
     return local_iterator(__bucket_list_[__n], __n, bucket_count());
   }
 
   _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) {
     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
         __n < bucket_count(), "unordered container::end(n) called with n >= bucket_count()");
     return local_iterator(nullptr, __n, bucket_count());
   }
 
   _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const {
     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
         __n < bucket_count(), "unordered container::cbegin(n) called with n >= bucket_count()");
     return const_local_iterator(__bucket_list_[__n], __n, bucket_count());
   }
 
   _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const {
     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
         __n < bucket_count(), "unordered container::cend(n) called with n >= bucket_count()");
     return const_local_iterator(nullptr, __n, bucket_count());
   }
 
 private:
   template <bool _UniqueKeys>
   _LIBCPP_HIDE_FROM_ABI void __rehash(size_type __n);
   template <bool _UniqueKeys>
   _LIBCPP_HIDE_FROM_ABI void __do_rehash(size_type __n);
 
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args);
 
   template <class _First, class... _Rest>
   _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
 
   _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u) {
     __copy_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());
   }
   _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u, true_type);
   _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table&, false_type) {}
 
   _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, false_type);
   _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, true_type)
       _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
                      is_nothrow_move_assignable<key_equal>::value);
   _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table& __u) _NOEXCEPT_(
       !__node_traits::propagate_on_container_move_assignment::value ||
       (is_nothrow_move_assignable<__pointer_allocator>::value && is_nothrow_move_assignable<__node_allocator>::value)) {
     __move_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
   }
   _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table& __u, true_type) _NOEXCEPT_(
       is_nothrow_move_assignable<__pointer_allocator>::value&& is_nothrow_move_assignable<__node_allocator>::value) {
     __bucket_list_.get_deleter().__alloc() = std::move(__u.__bucket_list_.get_deleter().__alloc());
     __node_alloc()                         = std::move(__u.__node_alloc());
   }
   _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
 
   _LIBCPP_HIDE_FROM_ABI void __deallocate_node(__next_pointer __np) _NOEXCEPT;
   _LIBCPP_HIDE_FROM_ABI __next_pointer __detach() _NOEXCEPT;
 
   template <class, class, class, class, class>
   friend class _LIBCPP_TEMPLATE_VIS unordered_map;
   template <class, class, class, class, class>
   friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
 };
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 inline __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() _NOEXCEPT_(
     is_nothrow_default_constructible<__bucket_list>::value&& is_nothrow_default_constructible<__first_node>::value&&
         is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_default_constructible<hasher>::value&&
             is_nothrow_default_constructible<key_equal>::value)
     : __p2_(0, __default_init_tag()), __p3_(1.0f, __default_init_tag()) {}
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 inline __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, const key_equal& __eql)
     : __bucket_list_(nullptr, __bucket_list_deleter()), __p1_(), __p2_(0, __hf), __p3_(1.0f, __eql) {}
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(
     const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
       __p1_(__default_init_tag(), __node_allocator(__a)),
       __p2_(0, __hf),
       __p3_(1.0f, __eql) {}
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
       __p1_(__default_init_tag(), __node_allocator(__a)),
       __p2_(0, __default_init_tag()),
       __p3_(1.0f, __default_init_tag()) {}
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
     : __bucket_list_(nullptr,
                      __bucket_list_deleter(allocator_traits<__pointer_allocator>::select_on_container_copy_construction(
                                                __u.__bucket_list_.get_deleter().__alloc()),
                                            0)),
       __p1_(__default_init_tag(),
             allocator_traits<__node_allocator>::select_on_container_copy_construction(__u.__node_alloc())),
       __p2_(0, __u.hash_function()),
       __p3_(__u.__p3_) {}
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, const allocator_type& __a)
     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
       __p1_(__default_init_tag(), __node_allocator(__a)),
       __p2_(0, __u.hash_function()),
       __p3_(__u.__p3_) {}
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) _NOEXCEPT_(
     is_nothrow_move_constructible<__bucket_list>::value&& is_nothrow_move_constructible<__first_node>::value&&
         is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<hasher>::value&&
             is_nothrow_move_constructible<key_equal>::value)
     : __bucket_list_(std::move(__u.__bucket_list_)),
       __p1_(std::move(__u.__p1_)),
       __p2_(std::move(__u.__p2_)),
       __p3_(std::move(__u.__p3_)) {
   if (size() > 0) {
     __bucket_list_[std::__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = __p1_.first().__ptr();
     __u.__p1_.first().__next_                                                              = nullptr;
     __u.size()                                                                             = 0;
   }
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, const allocator_type& __a)
     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
       __p1_(__default_init_tag(), __node_allocator(__a)),
       __p2_(0, std::move(__u.hash_function())),
       __p3_(std::move(__u.__p3_)) {
   if (__a == allocator_type(__u.__node_alloc())) {
     __bucket_list_.reset(__u.__bucket_list_.release());
     __bucket_list_.get_deleter().size()     = __u.__bucket_list_.get_deleter().size();
     __u.__bucket_list_.get_deleter().size() = 0;
     if (__u.size() > 0) {
       __p1_.first().__next_     = __u.__p1_.first().__next_;
       __u.__p1_.first().__next_ = nullptr;
       __bucket_list_[std::__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = __p1_.first().__ptr();
       size()                                                                                 = __u.size();
       __u.size()                                                                             = 0;
     }
   }
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() {
 #if defined(_LIBCPP_CXX03_LANG)
   static_assert(is_copy_constructible<key_equal>::value, "Predicate must be copy-constructible.");
   static_assert(is_copy_constructible<hasher>::value, "Hasher must be copy-constructible.");
 #endif
 
   __deallocate_node(__p1_.first().__next_);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(const __hash_table& __u, true_type) {
   if (__node_alloc() != __u.__node_alloc()) {
     clear();
     __bucket_list_.reset();
     __bucket_list_.get_deleter().size() = 0;
   }
   __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
   __node_alloc()                         = __u.__node_alloc();
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) {
   if (this != std::addressof(__u)) {
     __copy_assign_alloc(__u);
     hash_function()   = __u.hash_function();
     key_eq()          = __u.key_eq();
     max_load_factor() = __u.max_load_factor();
     __assign_multi(__u.begin(), __u.end());
   }
   return *this;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np) _NOEXCEPT {
   __node_allocator& __na = __node_alloc();
   while (__np != nullptr) {
     __next_pointer __next    = __np->__next_;
     __node_pointer __real_np = __np->__upcast();
     __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__get_value()));
     std::__destroy_at(std::addressof(*__real_np));
     __node_traits::deallocate(__na, __real_np, 1);
     __np = __next;
   }
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT {
   size_type __bc = bucket_count();
   for (size_type __i = 0; __i < __bc; ++__i)
     __bucket_list_[__i] = nullptr;
   size()                 = 0;
   __next_pointer __cache = __p1_.first().__next_;
   __p1_.first().__next_  = nullptr;
   return __cache;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u, true_type)
     _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
                    is_nothrow_move_assignable<key_equal>::value) {
   clear();
   __bucket_list_.reset(__u.__bucket_list_.release());
   __bucket_list_.get_deleter().size()     = __u.__bucket_list_.get_deleter().size();
   __u.__bucket_list_.get_deleter().size() = 0;
   __move_assign_alloc(__u);
   size()                = __u.size();
   hash_function()       = std::move(__u.hash_function());
   max_load_factor()     = __u.max_load_factor();
   key_eq()              = std::move(__u.key_eq());
   __p1_.first().__next_ = __u.__p1_.first().__next_;
   if (size() > 0) {
     __bucket_list_[std::__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = __p1_.first().__ptr();
     __u.__p1_.first().__next_                                                              = nullptr;
     __u.size()                                                                             = 0;
   }
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u, false_type) {
   if (__node_alloc() == __u.__node_alloc())
     __move_assign(__u, true_type());
   else {
     hash_function()   = std::move(__u.hash_function());
     key_eq()          = std::move(__u.key_eq());
     max_load_factor() = __u.max_load_factor();
     if (bucket_count() != 0) {
       __next_pointer __cache = __detach();
 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
       try {
 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
         const_iterator __i = __u.begin();
         while (__cache != nullptr && __u.size() != 0) {
           __cache->__upcast()->__get_value() = std::move(__u.remove(__i++)->__get_value());
           __next_pointer __next              = __cache->__next_;
           __node_insert_multi(__cache->__upcast());
           __cache = __next;
         }
 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
       } catch (...) {
         __deallocate_node(__cache);
         throw;
       }
 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
       __deallocate_node(__cache);
     }
     const_iterator __i = __u.begin();
     while (__u.size() != 0) {
       __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__get_value()));
       __node_insert_multi(__h.get());
       __h.release();
     }
   }
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 inline __hash_table<_Tp, _Hash, _Equal, _Alloc>&
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) _NOEXCEPT_(
     __node_traits::propagate_on_container_move_assignment::value&& is_nothrow_move_assignable<__node_allocator>::value&&
         is_nothrow_move_assignable<hasher>::value&& is_nothrow_move_assignable<key_equal>::value) {
   __move_assign(__u, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
   return *this;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _InputIterator>
 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, _InputIterator __last) {
   typedef iterator_traits<_InputIterator> _ITraits;
   typedef typename _ITraits::value_type _ItValueType;
   static_assert(is_same<_ItValueType, __container_value_type>::value,
                 "__assign_unique may only be called with the containers value type");
 
   if (bucket_count() != 0) {
     __next_pointer __cache = __detach();
 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
     try {
 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
       for (; __cache != nullptr && __first != __last; ++__first) {
         __cache->__upcast()->__get_value() = *__first;
         __next_pointer __next              = __cache->__next_;
         __node_insert_unique(__cache->__upcast());
         __cache = __next;
       }
 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
     } catch (...) {
       __deallocate_node(__cache);
       throw;
     }
 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
     __deallocate_node(__cache);
   }
   for (; __first != __last; ++__first)
     __insert_unique(*__first);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _InputIterator>
 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, _InputIterator __last) {
   typedef iterator_traits<_InputIterator> _ITraits;
   typedef typename _ITraits::value_type _ItValueType;
   static_assert(
       (is_same<_ItValueType, __container_value_type>::value || is_same<_ItValueType, __node_value_type>::value),
       "__assign_multi may only be called with the containers value type"
       " or the nodes value type");
   if (bucket_count() != 0) {
     __next_pointer __cache = __detach();
 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
     try {
 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
       for (; __cache != nullptr && __first != __last; ++__first) {
         __cache->__upcast()->__get_value() = *__first;
         __next_pointer __next              = __cache->__next_;
         __node_insert_multi(__cache->__upcast());
         __cache = __next;
       }
 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
     } catch (...) {
       __deallocate_node(__cache);
       throw;
     }
 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
     __deallocate_node(__cache);
   }
   for (; __first != __last; ++__first)
     __insert_multi(_NodeTypes::__get_value(*__first));
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT {
   return iterator(__p1_.first().__next_);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT {
   return iterator(nullptr);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT {
   return const_iterator(__p1_.first().__next_);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT {
   return const_iterator(nullptr);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT {
   if (size() > 0) {
     __deallocate_node(__p1_.first().__next_);
     __p1_.first().__next_ = nullptr;
     size_type __bc        = bucket_count();
     for (size_type __i = 0; __i < __bc; ++__i)
       __bucket_list_[__i] = nullptr;
     size() = 0;
   }
 }
 
 // Prepare the container for an insertion of the value __value with the hash
 // __hash. This does a lookup into the container to see if __value is already
 // present, and performs a rehash if necessary. Returns a pointer to the
 // existing element if it exists, otherwise nullptr.
 //
 // Note that this function does forward exceptions if key_eq() throws, and never
 // mutates __value or actually inserts into the map.
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 _LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare(size_t __hash, value_type& __value) {
   size_type __bc = bucket_count();
 
   if (__bc != 0) {
     size_t __chash         = std::__constrain_hash(__hash, __bc);
     __next_pointer __ndptr = __bucket_list_[__chash];
     if (__ndptr != nullptr) {
       for (__ndptr = __ndptr->__next_;
            __ndptr != nullptr &&
            (__ndptr->__hash() == __hash || std::__constrain_hash(__ndptr->__hash(), __bc) == __chash);
            __ndptr = __ndptr->__next_) {
         if ((__ndptr->__hash() == __hash) && key_eq()(__ndptr->__upcast()->__get_value(), __value))
           return __ndptr;
       }
     }
   }
   if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
     __rehash_unique(std::max<size_type>(
         2 * __bc + !std::__is_hash_power2(__bc), size_type(std::ceil(float(size() + 1) / max_load_factor()))));
   }
   return nullptr;
 }
 
 // Insert the node __nd into the container by pushing it into the right bucket,
 // and updating size(). Assumes that __nd->__hash is up-to-date, and that
 // rehashing has already occurred and that no element with the same key exists
 // in the map.
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 _LIBCPP_HIDE_FROM_ABI void
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform(__node_pointer __nd) _NOEXCEPT {
   size_type __bc = bucket_count();
   size_t __chash = std::__constrain_hash(__nd->__hash(), __bc);
   // insert_after __bucket_list_[__chash], or __first_node if bucket is null
   __next_pointer __pn = __bucket_list_[__chash];
   if (__pn == nullptr) {
     __pn          = __p1_.first().__ptr();
     __nd->__next_ = __pn->__next_;
     __pn->__next_ = __nd->__ptr();
     // fix up __bucket_list_
     __bucket_list_[__chash] = __pn;
     if (__nd->__next_ != nullptr)
       __bucket_list_[std::__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
   } else {
     __nd->__next_ = __pn->__next_;
     __pn->__next_ = __nd->__ptr();
   }
   ++size();
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) {
   __nd->__hash_                  = hash_function()(__nd->__get_value());
   __next_pointer __existing_node = __node_insert_unique_prepare(__nd->__hash(), __nd->__get_value());
 
   // Insert the node, unless it already exists in the container.
   bool __inserted = false;
   if (__existing_node == nullptr) {
     __node_insert_unique_perform(__nd);
     __existing_node = __nd->__ptr();
     __inserted      = true;
   }
   return pair<iterator, bool>(iterator(__existing_node), __inserted);
 }
 
 // Prepare the container for an insertion of the value __cp_val with the hash
 // __cp_hash. This does a lookup into the container to see if __cp_value is
 // already present, and performs a rehash if necessary. Returns a pointer to the
 // last occurrence of __cp_val in the map.
 //
 // Note that this function does forward exceptions if key_eq() throws, and never
 // mutates __value or actually inserts into the map.
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare(size_t __cp_hash, value_type& __cp_val) {
   size_type __bc = bucket_count();
   if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
     __rehash_multi(std::max<size_type>(
         2 * __bc + !std::__is_hash_power2(__bc), size_type(std::ceil(float(size() + 1) / max_load_factor()))));
     __bc = bucket_count();
   }
   size_t __chash      = std::__constrain_hash(__cp_hash, __bc);
   __next_pointer __pn = __bucket_list_[__chash];
   if (__pn != nullptr) {
     for (bool __found = false;
          __pn->__next_ != nullptr && std::__constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
          __pn = __pn->__next_) {
       //      __found    key_eq()     action
       //      false       false       loop
       //      true        true        loop
       //      false       true        set __found to true
       //      true        false       break
       if (__found !=
           (__pn->__next_->__hash() == __cp_hash && key_eq()(__pn->__next_->__upcast()->__get_value(), __cp_val))) {
         if (!__found)
           __found = true;
         else
           break;
       }
     }
   }
   return __pn;
 }
 
 // Insert the node __cp into the container after __pn (which is the last node in
 // the bucket that compares equal to __cp). Rehashing, and checking for
 // uniqueness has already been performed (in __node_insert_multi_prepare), so
 // all we need to do is update the bucket and size(). Assumes that __cp->__hash
 // is up-to-date.
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform(
     __node_pointer __cp, __next_pointer __pn) _NOEXCEPT {
   size_type __bc = bucket_count();
   size_t __chash = std::__constrain_hash(__cp->__hash_, __bc);
   if (__pn == nullptr) {
     __pn          = __p1_.first().__ptr();
     __cp->__next_ = __pn->__next_;
     __pn->__next_ = __cp->__ptr();
     // fix up __bucket_list_
     __bucket_list_[__chash] = __pn;
     if (__cp->__next_ != nullptr)
       __bucket_list_[std::__constrain_hash(__cp->__next_->__hash(), __bc)] = __cp->__ptr();
   } else {
     __cp->__next_ = __pn->__next_;
     __pn->__next_ = __cp->__ptr();
     if (__cp->__next_ != nullptr) {
       size_t __nhash = std::__constrain_hash(__cp->__next_->__hash(), __bc);
       if (__nhash != __chash)
         __bucket_list_[__nhash] = __cp->__ptr();
     }
   }
   ++size();
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) {
   __cp->__hash_       = hash_function()(__cp->__get_value());
   __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__get_value());
   __node_insert_multi_perform(__cp, __pn);
 
   return iterator(__cp->__ptr());
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(const_iterator __p, __node_pointer __cp) {
   if (__p != end() && key_eq()(*__p, __cp->__get_value())) {
     __next_pointer __np = __p.__node_;
     __cp->__hash_       = __np->__hash();
     size_type __bc      = bucket_count();
     if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
       __rehash_multi(std::max<size_type>(
           2 * __bc + !std::__is_hash_power2(__bc), size_type(std::ceil(float(size() + 1) / max_load_factor()))));
       __bc = bucket_count();
     }
     size_t __chash      = std::__constrain_hash(__cp->__hash_, __bc);
     __next_pointer __pp = __bucket_list_[__chash];
     while (__pp->__next_ != __np)
       __pp = __pp->__next_;
     __cp->__next_ = __np;
     __pp->__next_ = static_cast<__next_pointer>(__cp);
     ++size();
     return iterator(static_cast<__next_pointer>(__cp));
   }
   return __node_insert_multi(__cp);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Key, class... _Args>
 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) {
   size_t __hash   = hash_function()(__k);
   size_type __bc  = bucket_count();
   bool __inserted = false;
   __next_pointer __nd;
   size_t __chash;
   if (__bc != 0) {
     __chash = std::__constrain_hash(__hash, __bc);
     __nd    = __bucket_list_[__chash];
     if (__nd != nullptr) {
       for (__nd = __nd->__next_;
            __nd != nullptr && (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
            __nd = __nd->__next_) {
         if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
           goto __done;
       }
     }
   }
   {
     __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args)...);
     if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
       __rehash_unique(std::max<size_type>(
           2 * __bc + !std::__is_hash_power2(__bc), size_type(std::ceil(float(size() + 1) / max_load_factor()))));
       __bc    = bucket_count();
       __chash = std::__constrain_hash(__hash, __bc);
     }
     // insert_after __bucket_list_[__chash], or __first_node if bucket is null
     __next_pointer __pn = __bucket_list_[__chash];
     if (__pn == nullptr) {
       __pn          = __p1_.first().__ptr();
       __h->__next_  = __pn->__next_;
       __pn->__next_ = __h.get()->__ptr();
       // fix up __bucket_list_
       __bucket_list_[__chash] = __pn;
       if (__h->__next_ != nullptr)
         __bucket_list_[std::__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr();
     } else {
       __h->__next_  = __pn->__next_;
       __pn->__next_ = static_cast<__next_pointer>(__h.get());
     }
     __nd = static_cast<__next_pointer>(__h.release());
     // increment size
     ++size();
     __inserted = true;
   }
 __done:
   return pair<iterator, bool>(iterator(__nd), __inserted);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class... _Args>
 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args) {
   __node_holder __h        = __construct_node(std::forward<_Args>(__args)...);
   pair<iterator, bool> __r = __node_insert_unique(__h.get());
   if (__r.second)
     __h.release();
   return __r;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class... _Args>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) {
   __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
   iterator __r      = __node_insert_multi(__h.get());
   __h.release();
   return __r;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class... _Args>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(const_iterator __p, _Args&&... __args) {
   __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
   iterator __r      = __node_insert_multi(__p, __h.get());
   __h.release();
   return __r;
 }
 
 #if _LIBCPP_STD_VER >= 17
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _NodeHandle, class _InsertReturnType>
 _LIBCPP_HIDE_FROM_ABI _InsertReturnType
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(_NodeHandle&& __nh) {
   if (__nh.empty())
     return _InsertReturnType{end(), false, _NodeHandle()};
   pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
   if (__result.second)
     __nh.__release_ptr();
   return _InsertReturnType{__result.first, __result.second, std::move(__nh)};
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _NodeHandle>
 _LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(const_iterator, _NodeHandle&& __nh) {
   if (__nh.empty())
     return end();
   pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
   if (__result.second)
     __nh.__release_ptr();
   return __result.first;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _NodeHandle>
 _LIBCPP_HIDE_FROM_ABI _NodeHandle
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(key_type const& __key) {
   iterator __i = find(__key);
   if (__i == end())
     return _NodeHandle();
   return __node_handle_extract<_NodeHandle>(__i);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _NodeHandle>
 _LIBCPP_HIDE_FROM_ABI _NodeHandle __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(const_iterator __p) {
   allocator_type __alloc(__node_alloc());
   return _NodeHandle(remove(__p).release(), __alloc);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Table>
 _LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique(_Table& __source) {
   static_assert(is_same<__node, typename _Table::__node>::value, "");
 
   for (typename _Table::iterator __it = __source.begin(); __it != __source.end();) {
     __node_pointer __src_ptr       = __it.__node_->__upcast();
     size_t __hash                  = hash_function()(__src_ptr->__get_value());
     __next_pointer __existing_node = __node_insert_unique_prepare(__hash, __src_ptr->__get_value());
     auto __prev_iter               = __it++;
     if (__existing_node == nullptr) {
       (void)__source.remove(__prev_iter).release();
       __src_ptr->__hash_ = __hash;
       __node_insert_unique_perform(__src_ptr);
     }
   }
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _NodeHandle>
 _LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(_NodeHandle&& __nh) {
   if (__nh.empty())
     return end();
   iterator __result = __node_insert_multi(__nh.__ptr_);
   __nh.__release_ptr();
   return __result;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _NodeHandle>
 _LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh) {
   if (__nh.empty())
     return end();
   iterator __result = __node_insert_multi(__hint, __nh.__ptr_);
   __nh.__release_ptr();
   return __result;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Table>
 _LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi(_Table& __source) {
   static_assert(is_same<typename _Table::__node, __node>::value, "");
 
   for (typename _Table::iterator __it = __source.begin(); __it != __source.end();) {
     __node_pointer __src_ptr = __it.__node_->__upcast();
     size_t __src_hash        = hash_function()(__src_ptr->__get_value());
     __next_pointer __pn      = __node_insert_multi_prepare(__src_hash, __src_ptr->__get_value());
     (void)__source.remove(__it++).release();
     __src_ptr->__hash_ = __src_hash;
     __node_insert_multi_perform(__src_ptr, __pn);
   }
 }
 #endif // _LIBCPP_STD_VER >= 17
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <bool _UniqueKeys>
 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __n) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK {
   if (__n == 1)
     __n = 2;
   else if (__n & (__n - 1))
     __n = std::__next_prime(__n);
   size_type __bc = bucket_count();
   if (__n > __bc)
     __do_rehash<_UniqueKeys>(__n);
   else if (__n < __bc) {
     __n = std::max<size_type>(
         __n,
         std::__is_hash_power2(__bc) ? std::__next_hash_pow2(size_t(std::ceil(float(size()) / max_load_factor())))
                                     : std::__next_prime(size_t(std::ceil(float(size()) / max_load_factor()))));
     if (__n < __bc)
       __do_rehash<_UniqueKeys>(__n);
   }
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <bool _UniqueKeys>
 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__do_rehash(size_type __nbc) {
   __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
   __bucket_list_.reset(__nbc > 0 ? __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
   __bucket_list_.get_deleter().size() = __nbc;
   if (__nbc > 0) {
     for (size_type __i = 0; __i < __nbc; ++__i)
       __bucket_list_[__i] = nullptr;
     __next_pointer __pp = __p1_.first().__ptr();
     __next_pointer __cp = __pp->__next_;
     if (__cp != nullptr) {
       size_type __chash       = std::__constrain_hash(__cp->__hash(), __nbc);
       __bucket_list_[__chash] = __pp;
       size_type __phash       = __chash;
       for (__pp = __cp, void(), __cp = __cp->__next_; __cp != nullptr; __cp = __pp->__next_) {
         __chash = std::__constrain_hash(__cp->__hash(), __nbc);
         if (__chash == __phash)
           __pp = __cp;
         else {
           if (__bucket_list_[__chash] == nullptr) {
             __bucket_list_[__chash] = __pp;
             __pp                    = __cp;
             __phash                 = __chash;
           } else {
             __next_pointer __np = __cp;
             if _LIBCPP_CONSTEXPR_SINCE_CXX17 (!_UniqueKeys) {
               for (; __np->__next_ != nullptr &&
                      key_eq()(__cp->__upcast()->__get_value(), __np->__next_->__upcast()->__get_value());
                    __np = __np->__next_)
                 ;
             }
             __pp->__next_                    = __np->__next_;
             __np->__next_                    = __bucket_list_[__chash]->__next_;
             __bucket_list_[__chash]->__next_ = __cp;
           }
         }
       }
     }
   }
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Key>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) {
   size_t __hash  = hash_function()(__k);
   size_type __bc = bucket_count();
   if (__bc != 0) {
     size_t __chash      = std::__constrain_hash(__hash, __bc);
     __next_pointer __nd = __bucket_list_[__chash];
     if (__nd != nullptr) {
       for (__nd = __nd->__next_;
            __nd != nullptr && (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
            __nd = __nd->__next_) {
         if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
           return iterator(__nd);
       }
     }
   }
   return end();
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Key>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const {
   size_t __hash  = hash_function()(__k);
   size_type __bc = bucket_count();
   if (__bc != 0) {
     size_t __chash      = std::__constrain_hash(__hash, __bc);
     __next_pointer __nd = __bucket_list_[__chash];
     if (__nd != nullptr) {
       for (__nd = __nd->__next_;
            __nd != nullptr && (__hash == __nd->__hash() || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
            __nd = __nd->__next_) {
         if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
           return const_iterator(__nd);
       }
     }
   }
   return end();
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class... _Args>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&&... __args) {
   static_assert(!__is_hash_value_type<_Args...>::value, "Construct cannot be called with a hash value type");
   __node_allocator& __na = __node_alloc();
   __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
 
   // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value
   // held inside the node, since we need to use the allocator's construct() method for that.
   //
   // We don't use the allocator's construct() method to construct the node itself since the
   // Cpp17FooInsertable named requirements don't require the allocator's construct() method
   // to work on anything other than the value_type.
   std::__construct_at(std::addressof(*__h), /* next = */ nullptr, /* hash = */ 0);
 
   // Now construct the value_type using the allocator's construct() method.
   __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__get_value()), std::forward<_Args>(__args)...);
   __h.get_deleter().__value_constructed = true;
 
   __h->__hash_ = hash_function()(__h->__get_value());
   return __h;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _First, class... _Rest>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest) {
   static_assert(!__is_hash_value_type<_First, _Rest...>::value, "Construct cannot be called with a hash value type");
   __node_allocator& __na = __node_alloc();
   __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
   std::__construct_at(std::addressof(*__h), /* next = */ nullptr, /* hash = */ __hash);
   __node_traits::construct(
       __na, _NodeTypes::__get_ptr(__h->__get_value()), std::forward<_First>(__f), std::forward<_Rest>(__rest)...);
   __h.get_deleter().__value_constructed = true;
   return __h;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) {
   __next_pointer __np = __p.__node_;
   _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
       __p != end(), "unordered container::erase(iterator) called with a non-dereferenceable iterator");
   iterator __r(__np);
   ++__r;
   remove(__p);
   return __r;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, const_iterator __last) {
   for (const_iterator __p = __first; __first != __last; __p = __first) {
     ++__first;
     erase(__p);
   }
   __next_pointer __np = __last.__node_;
   return iterator(__np);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Key>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) {
   iterator __i = find(__k);
   if (__i == end())
     return 0;
   erase(__i);
   return 1;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Key>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) {
   size_type __r = 0;
   iterator __i  = find(__k);
   if (__i != end()) {
     iterator __e = end();
     do {
       erase(__i++);
       ++__r;
     } while (__i != __e && key_eq()(*__i, __k));
   }
   return __r;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT {
   // current node
   __next_pointer __cn = __p.__node_;
   size_type __bc      = bucket_count();
   size_t __chash      = std::__constrain_hash(__cn->__hash(), __bc);
   // find previous node
   __next_pointer __pn = __bucket_list_[__chash];
   for (; __pn->__next_ != __cn; __pn = __pn->__next_)
     ;
   // Fix up __bucket_list_
   // if __pn is not in same bucket (before begin is not in same bucket) &&
   //    if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
   if (__pn == __p1_.first().__ptr() || std::__constrain_hash(__pn->__hash(), __bc) != __chash) {
     if (__cn->__next_ == nullptr || std::__constrain_hash(__cn->__next_->__hash(), __bc) != __chash)
       __bucket_list_[__chash] = nullptr;
   }
   // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
   if (__cn->__next_ != nullptr) {
     size_t __nhash = std::__constrain_hash(__cn->__next_->__hash(), __bc);
     if (__nhash != __chash)
       __bucket_list_[__nhash] = __pn;
   }
   // remove __cn
   __pn->__next_ = __cn->__next_;
   __cn->__next_ = nullptr;
   --size();
   return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true));
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Key>
 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const {
   return static_cast<size_type>(find(__k) != end());
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Key>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const {
   size_type __r      = 0;
   const_iterator __i = find(__k);
   if (__i != end()) {
     const_iterator __e = end();
     do {
       ++__i;
       ++__r;
     } while (__i != __e && key_eq()(*__i, __k));
   }
   return __r;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Key>
 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(const _Key& __k) {
   iterator __i = find(__k);
   iterator __j = __i;
   if (__i != end())
     ++__j;
   return pair<iterator, iterator>(__i, __j);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Key>
 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(const _Key& __k) const {
   const_iterator __i = find(__k);
   const_iterator __j = __i;
   if (__i != end())
     ++__j;
   return pair<const_iterator, const_iterator>(__i, __j);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Key>
 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(const _Key& __k) {
   iterator __i = find(__k);
   iterator __j = __i;
   if (__i != end()) {
     iterator __e = end();
     do {
       ++__j;
     } while (__j != __e && key_eq()(*__j, __k));
   }
   return pair<iterator, iterator>(__i, __j);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Key>
 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(const _Key& __k) const {
   const_iterator __i = find(__k);
   const_iterator __j = __i;
   if (__i != end()) {
     const_iterator __e = end();
     do {
       ++__j;
     } while (__j != __e && key_eq()(*__j, __k));
   }
   return pair<const_iterator, const_iterator>(__i, __j);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
 #if _LIBCPP_STD_VER <= 11
     _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal> &&
                (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
                 __is_nothrow_swappable_v<__pointer_allocator>) &&
                (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>))
 #else
     _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal>)
 #endif
 {
   _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
       __node_traits::propagate_on_container_swap::value || this->__node_alloc() == __u.__node_alloc(),
       "unordered container::swap: Either propagate_on_container_swap "
       "must be true or the allocators must compare equal");
   {
     __node_pointer_pointer __npp = __bucket_list_.release();
     __bucket_list_.reset(__u.__bucket_list_.release());
     __u.__bucket_list_.reset(__npp);
   }
   std::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
   std::__swap_allocator(__bucket_list_.get_deleter().__alloc(), __u.__bucket_list_.get_deleter().__alloc());
   std::__swap_allocator(__node_alloc(), __u.__node_alloc());
   std::swap(__p1_.first().__next_, __u.__p1_.first().__next_);
   __p2_.swap(__u.__p2_);
   __p3_.swap(__u.__p3_);
   if (size() > 0)
     __bucket_list_[std::__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = __p1_.first().__ptr();
   if (__u.size() > 0)
     __u.__bucket_list_[std::__constrain_hash(__u.__p1_.first().__next_->__hash(), __u.bucket_count())] =
         __u.__p1_.first().__ptr();
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const {
   _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
       __n < bucket_count(), "unordered container::bucket_size(n) called with n >= bucket_count()");
   __next_pointer __np = __bucket_list_[__n];
   size_type __bc      = bucket_count();
   size_type __r       = 0;
   if (__np != nullptr) {
     for (__np = __np->__next_; __np != nullptr && std::__constrain_hash(__np->__hash(), __bc) == __n;
          __np = __np->__next_, (void)++__r)
       ;
   }
   return __r;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 inline _LIBCPP_HIDE_FROM_ABI void
 swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
   __x.swap(__y);
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___CXX03___HASH_TABLE

This page was automatically generated by the 2.3.7 LXR engine. The LXR team