libcxx initial import
git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@103490 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/__hash_table b/include/__hash_table
new file mode 100644
index 0000000..f1327d5
--- /dev/null
+++ b/include/__hash_table
@@ -0,0 +1,1761 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// ÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊThe LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP__HASH_TABLE
+#define _LIBCPP__HASH_TABLE
+
+#include <__config>
+#include <initializer_list>
+#include <memory>
+#include <iterator>
+#include <algorithm>
+#include <cmath>
+
+#pragma GCC system_header
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+size_t __next_prime(size_t);
+
+template <class _NodePtr>
+struct __hash_node_base
+{
+ typedef __hash_node_base __first_node;
+ typedef _NodePtr pointer;
+
+ pointer __next_;
+
+ __hash_node_base() : __next_(nullptr) {}
+};
+
+template <class _Tp, class _VoidPtr>
+struct __hash_node
+ : public __hash_node_base
+ <
+ typename pointer_traits<_VoidPtr>::template
+#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
+ rebind<__hash_node<_Tp, _VoidPtr> >
+#else
+ rebind<__hash_node<_Tp, _VoidPtr> >::other
+#endif
+ >
+{
+ typedef _Tp value_type;
+
+ size_t __hash_;
+ value_type __value_;
+};
+
+template <class, class, class, class> class __hash_table;
+template <class> class __hash_const_iterator;
+template <class> class __hash_map_iterator;
+template <class> class __hash_map_const_iterator;
+template <class, class, class, class, class> class unordered_map;
+
+template <class _NodePtr>
+class __hash_iterator
+{
+ typedef _NodePtr __node_pointer;
+
+ __node_pointer __node_;
+
+public:
+ typedef forward_iterator_tag iterator_category;
+ typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type;
+ typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
+ typedef value_type& reference;
+ typedef typename pointer_traits<__node_pointer>::template
+#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
+ rebind<value_type>
+#else
+ rebind<value_type>::other
+#endif
+ pointer;
+
+ __hash_iterator() {}
+
+ reference operator*() const {return __node_->__value_;}
+ pointer operator->() const {return addressof(__node_->__value_);}
+
+ __hash_iterator& operator++()
+ {
+ __node_ = __node_->__next_;
+ return *this;
+ }
+
+ __hash_iterator operator++(int)
+ {
+ __hash_iterator __t(*this);
+ ++(*this);
+ return __t;
+ }
+
+ friend bool operator==(const __hash_iterator& __x, const __hash_iterator& __y)
+ {return __x.__node_ == __y.__node_;}
+ friend bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y)
+ {return __x.__node_ != __y.__node_;}
+
+private:
+ __hash_iterator(__node_pointer __node)
+ : __node_(__node)
+ {}
+
+ template <class, class, class, class> friend class __hash_table;
+ template <class> friend class __hash_const_iterator;
+ template <class> friend class __hash_map_iterator;
+ template <class, class, class, class, class> friend class unordered_map;
+ template <class, class, class, class, class> friend class unordered_multimap;
+};
+
+template <class _ConstNodePtr>
+class __hash_const_iterator
+{
+ typedef _ConstNodePtr __node_pointer;
+
+ __node_pointer __node_;
+
+ typedef typename remove_const<
+ typename pointer_traits<__node_pointer>::element_type
+ >::type __node;
+
+public:
+ typedef forward_iterator_tag iterator_category;
+ typedef typename __node::value_type value_type;
+ typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
+ typedef const value_type& reference;
+ typedef typename pointer_traits<__node_pointer>::template
+#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
+ rebind<const value_type>
+#else
+ rebind<const value_type>::other
+#endif
+ pointer;
+ typedef typename pointer_traits<__node_pointer>::template
+#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
+ rebind<__node>
+#else
+ rebind<__node>::other
+#endif
+ __non_const_node_pointer;
+ typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator;
+
+ __hash_const_iterator() {}
+ __hash_const_iterator(const __non_const_iterator& __x)
+ : __node_(__x.__node_)
+ {}
+
+ reference operator*() const {return __node_->__value_;}
+ pointer operator->() const {return addressof(__node_->__value_);}
+
+ __hash_const_iterator& operator++()
+ {
+ __node_ = __node_->__next_;
+ return *this;
+ }
+
+ __hash_const_iterator operator++(int)
+ {
+ __hash_const_iterator __t(*this);
+ ++(*this);
+ return __t;
+ }
+
+ friend bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
+ {return __x.__node_ == __y.__node_;}
+ friend bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
+ {return __x.__node_ != __y.__node_;}
+
+private:
+ __hash_const_iterator(__node_pointer __node)
+ : __node_(__node)
+ {}
+
+ template <class, class, class, class> friend class __hash_table;
+ template <class> friend class __hash_map_const_iterator;
+ template <class, class, class, class, class> friend class unordered_map;
+ template <class, class, class, class, class> friend class unordered_multimap;
+};
+
+template <class> class __hash_const_local_iterator;
+
+template <class _NodePtr>
+class __hash_local_iterator
+{
+ typedef _NodePtr __node_pointer;
+
+ __node_pointer __node_;
+ size_t __bucket_;
+ size_t __bucket_count_;
+
+ typedef pointer_traits<__node_pointer> __pointer_traits;
+public:
+ typedef forward_iterator_tag iterator_category;
+ typedef typename __pointer_traits::element_type::value_type value_type;
+ typedef typename __pointer_traits::difference_type difference_type;
+ typedef value_type& reference;
+ typedef typename __pointer_traits::template
+#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
+ rebind<value_type>
+#else
+ rebind<value_type>::other
+#endif
+ pointer;
+
+ __hash_local_iterator() {}
+
+ reference operator*() const {return __node_->__value_;}
+ pointer operator->() const {return &__node_->__value_;}
+
+ __hash_local_iterator& operator++()
+ {
+ __node_ = __node_->__next_;
+ if (__node_ != nullptr && __node_->__hash_ % __bucket_count_ != __bucket_)
+ __node_ = nullptr;
+ return *this;
+ }
+
+ __hash_local_iterator operator++(int)
+ {
+ __hash_local_iterator __t(*this);
+ ++(*this);
+ return __t;
+ }
+
+ friend bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
+ {return __x.__node_ == __y.__node_;}
+ friend bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
+ {return __x.__node_ != __y.__node_;}
+
+private:
+ __hash_local_iterator(__node_pointer __node, size_t __bucket,
+ size_t __bucket_count)
+ : __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 __hash_const_local_iterator;
+ template <class> friend class __hash_map_iterator;
+};
+
+template <class _ConstNodePtr>
+class __hash_const_local_iterator
+{
+ typedef _ConstNodePtr __node_pointer;
+
+ __node_pointer __node_;
+ size_t __bucket_;
+ size_t __bucket_count_;
+
+ typedef pointer_traits<__node_pointer> __pointer_traits;
+ typedef typename __pointer_traits::element_type __node;
+ typedef typename remove_const<__node>::type __non_const_node;
+ typedef typename pointer_traits<__node_pointer>::template
+#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
+ rebind<__non_const_node>
+#else
+ rebind<__non_const_node>::other
+#endif
+ __non_const_node_pointer;
+ typedef __hash_local_iterator<__non_const_node_pointer>
+ __non_const_iterator;
+public:
+ typedef forward_iterator_tag iterator_category;
+ typedef typename remove_const<
+ typename __pointer_traits::element_type::value_type
+ >::type value_type;
+ typedef typename __pointer_traits::difference_type difference_type;
+ typedef const value_type& reference;
+ typedef typename __pointer_traits::template
+#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
+ rebind<const value_type>
+#else
+ rebind<const value_type>::other
+#endif
+ pointer;
+
+ __hash_const_local_iterator() {}
+ __hash_const_local_iterator(const __non_const_iterator& __x)
+ : __node_(__x.__node_),
+ __bucket_(__x.__bucket_),
+ __bucket_count_(__x.__bucket_count_)
+ {}
+
+ reference operator*() const {return __node_->__value_;}
+ pointer operator->() const {return &__node_->__value_;}
+
+ __hash_const_local_iterator& operator++()
+ {
+ __node_ = __node_->__next_;
+ if (__node_ != nullptr && __node_->__hash_ % __bucket_count_ != __bucket_)
+ __node_ = nullptr;
+ return *this;
+ }
+
+ __hash_const_local_iterator operator++(int)
+ {
+ __hash_const_local_iterator __t(*this);
+ ++(*this);
+ return __t;
+ }
+
+ friend bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
+ {return __x.__node_ == __y.__node_;}
+ friend bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
+ {return __x.__node_ != __y.__node_;}
+
+private:
+ __hash_const_local_iterator(__node_pointer __node, size_t __bucket,
+ size_t __bucket_count)
+ : __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 __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;
+
+ __bucket_list_deallocator()
+ : __data_(0) {}
+ __bucket_list_deallocator(const allocator_type& __a, size_type __size)
+ : __data_(__size, __a) {}
+
+#ifdef _LIBCPP_MOVE
+
+ __bucket_list_deallocator(__bucket_list_deallocator&& __x)
+ : __data_(_STD::move(__x.__data_))
+ {
+ __x.size() = 0;
+ }
+
+#endif
+
+ size_type& size() {return __data_.first();}
+ size_type size() const {return __data_.first();}
+
+ allocator_type& __alloc() {return __data_.second();}
+ const allocator_type& __alloc() const {return __data_.second();}
+
+ void operator()(pointer __p)
+ {
+ __alloc_traits::deallocate(__alloc(), __p, size());
+ }
+};
+
+template <class> class __hash_map_node_destructor;
+
+template <class _Alloc>
+class __hash_node_destructor
+{
+ typedef _Alloc allocator_type;
+ typedef allocator_traits<allocator_type> __alloc_traits;
+ typedef typename __alloc_traits::value_type::value_type value_type;
+public:
+ typedef typename __alloc_traits::pointer pointer;
+private:
+
+ allocator_type& __na_;
+
+ __hash_node_destructor& operator=(const __hash_node_destructor&);
+
+public:
+ bool __value_constructed;
+
+ explicit __hash_node_destructor(allocator_type& __na)
+ : __na_(__na),
+ __value_constructed(false)
+ {}
+
+ void operator()(pointer __p)
+ {
+ if (__value_constructed)
+ __alloc_traits::destroy(__na_, addressof(__p->__value_));
+ if (__p)
+ __alloc_traits::deallocate(__na_, __p, 1);
+ }
+
+ template <class> friend class __hash_map_node_destructor;
+};
+
+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;
+public:
+ typedef value_type& reference;
+ typedef const value_type& const_reference;
+ typedef typename __alloc_traits::pointer pointer;
+ typedef typename __alloc_traits::const_pointer const_pointer;
+ typedef typename __alloc_traits::size_type size_type;
+ typedef typename __alloc_traits::difference_type difference_type;
+public:
+ // Create __node
+ typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node;
+ typedef typename __node::__first_node __first_node;
+ typedef typename __alloc_traits::template
+#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
+ rebind_alloc<__node>
+#else
+ rebind_alloc<__node>::other
+#endif
+ __node_allocator;
+ typedef allocator_traits<__node_allocator> __node_traits;
+ typedef typename __node_traits::pointer __node_pointer;
+ typedef typename __node_traits::const_pointer __node_const_pointer;
+
+private:
+
+ typedef typename __node_traits::template
+#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
+ rebind_alloc<__node_pointer>
+#else
+ rebind_alloc<__node_pointer>::other
+#endif
+ __pointer_allocator;
+ typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
+ typedef unique_ptr<__node_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 ---
+
+ size_type& size() {return __p2_.first();}
+public:
+ size_type size() const {return __p2_.first();}
+
+ hasher& hash_function() {return __p2_.second();}
+ const hasher& hash_function() const {return __p2_.second();}
+
+ float& max_load_factor() {return __p3_.first();}
+ float max_load_factor() const {return __p3_.first();}
+
+ key_equal& key_eq() {return __p3_.second();}
+ const key_equal& key_eq() const {return __p3_.second();}
+
+ __node_allocator& __node_alloc() {return __p1_.second();}
+ const __node_allocator& __node_alloc() const {return __p1_.second();}
+
+public:
+ typedef __hash_iterator<__node_pointer> iterator;
+ typedef __hash_const_iterator<__node_const_pointer> const_iterator;
+ typedef __hash_local_iterator<__node_pointer> local_iterator;
+ typedef __hash_const_local_iterator<__node_const_pointer> const_local_iterator;
+
+ __hash_table();
+ __hash_table(const hasher& __hf, const key_equal& __eql);
+ __hash_table(const hasher& __hf, const key_equal& __eql,
+ const allocator_type& __a);
+ explicit __hash_table(const allocator_type& __a);
+ __hash_table(const __hash_table& __u);
+ __hash_table(const __hash_table& __u, const allocator_type& __a);
+#ifdef _LIBCPP_MOVE
+ __hash_table(__hash_table&& __u);
+ __hash_table(__hash_table&& __u, const allocator_type& __a);
+#endif
+ ~__hash_table();
+
+ __hash_table& operator=(const __hash_table& __u);
+#ifdef _LIBCPP_MOVE
+ __hash_table& operator=(__hash_table&& __u);
+#endif
+ template <class _InputIterator>
+ void __assign_unique(_InputIterator __first, _InputIterator __last);
+ template <class _InputIterator>
+ void __assign_multi(_InputIterator __first, _InputIterator __last);
+
+ size_type max_size() const
+ {
+ return allocator_traits<__pointer_allocator>::max_size(
+ __bucket_list_.get_deleter().__alloc());
+ }
+
+ pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
+ iterator __node_insert_multi(__node_pointer __nd);
+ iterator __node_insert_multi(const_iterator __p,
+ __node_pointer __nd);
+
+#ifdef _LIBCPP_MOVE
+ template <class... _Args>
+ pair<iterator, bool> __emplace_unique(_Args&&... __args);
+ template <class... _Args>
+ iterator __emplace_multi(_Args&&... __args);
+ template <class... _Args>
+ iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
+#endif
+
+ pair<iterator, bool> __insert_unique(const value_type& __x);
+
+#ifdef _LIBCPP_MOVE
+ template <class _P>
+ pair<iterator, bool> __insert_unique(_P&& __x);
+#endif
+
+#ifdef _LIBCPP_MOVE
+ template <class _P>
+ iterator __insert_multi(_P&& __x);
+ template <class _P>
+ iterator __insert_multi(const_iterator __p, _P&& __x);
+#else
+ iterator __insert_multi(const value_type& __x);
+ iterator __insert_multi(const_iterator __p, const value_type& __x);
+#endif
+
+ void clear();
+ void rehash(size_type __n);
+ void reserve(size_type __n)
+ {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}
+ size_type bucket_count() const
+ {
+ return __bucket_list_.get_deleter().size();
+ }
+
+ iterator begin();
+ iterator end();
+ const_iterator begin() const;
+ const_iterator end() const;
+
+ template <class _Key>
+ size_type bucket(const _Key& __k) const
+ {return hash_function()(__k) % bucket_count();}
+
+ template <class _Key>
+ iterator find(const _Key& __x);
+ template <class _Key>
+ const_iterator find(const _Key& __x) const;
+
+ typedef __hash_node_destructor<__node_allocator> _D;
+ typedef unique_ptr<__node, _D> __node_holder;
+
+ iterator erase(const_iterator __p);
+ iterator erase(const_iterator __first, const_iterator __last);
+ template <class _Key>
+ size_type __erase_unique(const _Key& __k);
+ template <class _Key>
+ size_type __erase_multi(const _Key& __k);
+ __node_holder remove(const_iterator __p);
+
+ template <class _Key>
+ size_type __count_unique(const _Key& __k) const;
+ template <class _Key>
+ size_type __count_multi(const _Key& __k) const;
+
+ template <class _Key>
+ pair<iterator, iterator>
+ __equal_range_unique(const _Key& __k);
+ template <class _Key>
+ pair<const_iterator, const_iterator>
+ __equal_range_unique(const _Key& __k) const;
+
+ template <class _Key>
+ pair<iterator, iterator>
+ __equal_range_multi(const _Key& __k);
+ template <class _Key>
+ pair<const_iterator, const_iterator>
+ __equal_range_multi(const _Key& __k) const;
+
+ void swap(__hash_table& __u);
+
+ size_type max_bucket_count() const
+ {return __bucket_list_.get_deleter().__alloc().max_size();}
+ size_type bucket_size(size_type __n) const;
+ float load_factor() const
+ {
+ size_type __bc = bucket_count();
+ return __bc != 0 ? (float)size() / __bc : 0.f;
+ }
+ void max_load_factor(float __mlf)
+ {max_load_factor() = _STD::max(__mlf, load_factor());}
+
+ local_iterator begin(size_type __n)
+ {return local_iterator(__bucket_list_[__n], __n, bucket_count());}
+ local_iterator end(size_type __n)
+ {return local_iterator(nullptr, __n, bucket_count());}
+ const_local_iterator cbegin(size_type __n) const
+ {return const_local_iterator(__bucket_list_[__n], __n, bucket_count());}
+ const_local_iterator cend(size_type __n) const
+ {return const_local_iterator(nullptr, __n, bucket_count());}
+private:
+ void __rehash(size_type __n);
+
+#ifdef _LIBCPP_MOVE
+ template <class ..._Args>
+ __node_holder __construct_node(_Args&& ...__args);
+ __node_holder __construct_node(value_type&& __v, size_t __hash);
+#else
+ __node_holder __construct_node(const value_type& __v);
+#endif
+ __node_holder __construct_node(const value_type& __v, size_t __hash);
+
+ void __copy_assign_alloc(const __hash_table& __u)
+ {__copy_assign_alloc(__u, integral_constant<bool,
+ __node_traits::propagate_on_container_copy_assignment::value>());}
+ void __copy_assign_alloc(const __hash_table& __u, true_type);
+ void __copy_assign_alloc(const __hash_table& __u, false_type) {}
+
+ void __move_assign(__hash_table& __u, false_type);
+ void __move_assign(__hash_table& __u, true_type);
+ void __move_assign_alloc(__hash_table& __u)
+ {__move_assign_alloc(__u, integral_constant<bool,
+ __node_traits::propagate_on_container_move_assignment::value>());}
+ void __move_assign_alloc(__hash_table& __u, true_type)
+ {
+ __bucket_list_.get_deleter().__alloc() =
+ _STD::move(__u.__bucket_list_.get_deleter().__alloc());
+ __node_alloc() = _STD::move(__u.__node_alloc());
+ }
+ void __move_assign_alloc(__hash_table&, false_type) {}
+
+ template <class _A>
+ static
+ void
+ __swap_alloc(_A& __x, _A& __y)
+ {
+ __swap_alloc(__x, __y,
+ integral_constant<bool,
+ allocator_traits<_A>::propagate_on_container_swap::value
+ >());
+ }
+
+ template <class _A>
+ static
+ void
+ __swap_alloc(_A& __x, _A& __y, true_type)
+ {
+ using _STD::swap;
+ swap(__x, __y);
+ }
+
+ template <class _A>
+ static
+ void
+ __swap_alloc(_A& __x, _A& __y, false_type) {}
+
+ void __deallocate(__node_pointer __np);
+ __node_pointer __detach();
+};
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+inline
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
+ : __p2_(0),
+ __p3_(1.0f)
+{
+}
+
+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_(__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_(__node_allocator(__a)),
+ __p2_(0),
+ __p3_(1.0f)
+{
+}
+
+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_(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_(__node_allocator(__a)),
+ __p2_(0, __u.hash_function()),
+ __p3_(__u.__p3_)
+{
+}
+
+#ifdef _LIBCPP_MOVE
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
+ : __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_[__p1_.first().__next_->__hash_ % bucket_count()] =
+ static_cast<__node_pointer>(addressof(__p1_.first()));
+ __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_(__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_[__p1_.first().__next_->__hash_ % bucket_count()] =
+ static_cast<__node_pointer>(addressof(__p1_.first()));
+ size() = __u.size();
+ __u.size() = 0;
+ }
+ }
+}
+
+#endif
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
+{
+ __deallocate(__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 != &__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_pointer __np)
+{
+ __node_allocator& __na = __node_alloc();
+ while (__np != nullptr)
+ {
+ __node_pointer __next = __np->__next_;
+ __node_traits::destroy(__na, addressof(__np->__value_));
+ __node_traits::deallocate(__na, __np, 1);
+ __np = __next;
+ }
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach()
+{
+ size_type __bc = bucket_count();
+ for (size_type __i = 0; __i < __bc; ++__i)
+ __bucket_list_[__i] = nullptr;
+ size() = 0;
+ __node_pointer __cache = __p1_.first().__next_;
+ __p1_.first().__next_ = nullptr;
+ return __cache;
+}
+
+#ifdef _LIBCPP_MOVE
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
+ __hash_table& __u, true_type)
+{
+ 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_[__p1_.first().__next_->__hash_ % bucket_count()] =
+ static_cast<__node_pointer>(addressof(__p1_.first()));
+ __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)
+ {
+ __node_pointer __cache = __detach();
+#ifndef _LIBCPP_NO_EXCEPTIONS
+ try
+ {
+#endif
+ const_iterator __i = __u.begin();
+ while (__cache != nullptr && __u.size() != 0)
+ {
+ __cache->__value_ = _STD::move(__u.remove(__i++)->__value_);
+ __node_pointer __next = __cache->__next_;
+ __node_insert_multi(__cache);
+ __cache = __next;
+ }
+#ifndef _LIBCPP_NO_EXCEPTIONS
+ }
+ catch (...)
+ {
+ __deallocate(__cache);
+ throw;
+ }
+#endif
+ __deallocate(__cache);
+ }
+ const_iterator __i = __u.begin();
+ while (__u.size() != 0)
+ {
+ __node_holder __h =
+ __construct_node(_STD::move(__u.remove(__i++)->__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)
+{
+ __move_assign(__u, integral_constant<bool,
+ __node_traits::propagate_on_container_move_assignment::value>());
+ return *this;
+}
+
+#endif
+
+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)
+{
+ if (bucket_count() != 0)
+ {
+ __node_pointer __cache = __detach();
+#ifndef _LIBCPP_NO_EXCEPTIONS
+ try
+ {
+#endif
+ for (; __cache != nullptr && __first != __last; ++__first)
+ {
+ __cache->__value_ = *__first;
+ __node_pointer __next = __cache->__next_;
+ __node_insert_unique(__cache);
+ __cache = __next;
+ }
+#ifndef _LIBCPP_NO_EXCEPTIONS
+ }
+ catch (...)
+ {
+ __deallocate(__cache);
+ throw;
+ }
+#endif
+ __deallocate(__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)
+{
+ if (bucket_count() != 0)
+ {
+ __node_pointer __cache = __detach();
+#ifndef _LIBCPP_NO_EXCEPTIONS
+ try
+ {
+#endif
+ for (; __cache != nullptr && __first != __last; ++__first)
+ {
+ __cache->__value_ = *__first;
+ __node_pointer __next = __cache->__next_;
+ __node_insert_multi(__cache);
+ __cache = __next;
+ }
+#ifndef _LIBCPP_NO_EXCEPTIONS
+ }
+ catch (...)
+ {
+ __deallocate(__cache);
+ throw;
+ }
+#endif
+ __deallocate(__cache);
+ }
+ for (; __first != __last; ++__first)
+ __insert_multi(*__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()
+{
+ 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()
+{
+ 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
+{
+ 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
+{
+ return const_iterator(nullptr);
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear()
+{
+ if (size() > 0)
+ {
+ __deallocate(__p1_.first().__next_);
+ __p1_.first().__next_ = nullptr;
+ size_type __bc = bucket_count();
+ for (size_type __i; __i < __bc; ++__i)
+ __bucket_list_[__i] = nullptr;
+ size() = 0;
+ }
+}
+
+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->__value_);
+ size_type __bc = bucket_count();
+ bool __inserted = false;
+ __node_pointer __ndptr;
+ size_t __chash;
+ if (__bc != 0)
+ {
+ __chash = __nd->__hash_ % __bc;
+ __ndptr = __bucket_list_[__chash];
+ if (__ndptr != nullptr)
+ {
+ for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
+ __ndptr->__hash_ % __bc == __chash;
+ __ndptr = __ndptr->__next_)
+ {
+ if (key_eq()(__ndptr->__value_, __nd->__value_))
+ goto __done;
+ }
+ }
+ }
+ {
+ if (size()+1 > __bc * max_load_factor() || __bc == 0)
+ {
+ rehash(_STD::max<size_type>(2 * __bc + 1,
+ size_type(ceil(float(size() + 1) / max_load_factor()))));
+ __bc = bucket_count();
+ __chash = __nd->__hash_ % __bc;
+ }
+ // insert_after __bucket_list_[__chash], or __first_node if bucket is null
+ __node_pointer __pn = __bucket_list_[__chash];
+ if (__pn == nullptr)
+ {
+ __pn = static_cast<__node_pointer>(addressof(__p1_.first()));
+ __nd->__next_ = __pn->__next_;
+ __pn->__next_ = __nd;
+ // fix up __bucket_list_
+ __bucket_list_[__chash] = __pn;
+ if (__nd->__next_ != nullptr)
+ __bucket_list_[__nd->__next_->__hash_ % __bc] = __nd;
+ }
+ else
+ {
+ __nd->__next_ = __pn->__next_;
+ __pn->__next_ = __nd;
+ }
+ __ndptr = __nd;
+ // increment size
+ ++size();
+ __inserted = true;
+ }
+__done:
+ return pair<iterator, bool>(iterator(__ndptr), __inserted);
+}
+
+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->__value_);
+ size_type __bc = bucket_count();
+ if (size()+1 > __bc * max_load_factor() || __bc == 0)
+ {
+ rehash(_STD::max<size_type>(2 * __bc + 1,
+ size_type(ceil(float(size() + 1) / max_load_factor()))));
+ __bc = bucket_count();
+ }
+ size_t __chash = __cp->__hash_ % __bc;
+ __node_pointer __pn = __bucket_list_[__chash];
+ if (__pn == nullptr)
+ {
+ __pn = static_cast<__node_pointer>(addressof(__p1_.first()));
+ __cp->__next_ = __pn->__next_;
+ __pn->__next_ = __cp;
+ // fix up __bucket_list_
+ __bucket_list_[__chash] = __pn;
+ if (__cp->__next_ != nullptr)
+ __bucket_list_[__cp->__next_->__hash_ % __bc] = __cp;
+ }
+ else
+ {
+ for (bool __found = false; __pn->__next_ != nullptr &&
+ __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_->__value_, __cp->__value_)))
+ {
+ if (!__found)
+ __found = true;
+ else
+ break;
+ }
+ }
+ __cp->__next_ = __pn->__next_;
+ __pn->__next_ = __cp;
+ if (__cp->__next_ != nullptr)
+ {
+ size_t __nhash = __cp->__next_->__hash_ % __bc;
+ if (__nhash != __chash)
+ __bucket_list_[__nhash] = __cp;
+ }
+ }
+ ++size();
+ return iterator(__cp);
+}
+
+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->__value_))
+ {
+ __node_pointer __np = const_cast<__node_pointer>(__p.__node_);
+ __cp->__hash_ = __np->__hash_;
+ size_type __bc = bucket_count();
+ if (size()+1 > __bc * max_load_factor() || __bc == 0)
+ {
+ rehash(_STD::max<size_type>(2 * __bc + 1,
+ size_type(ceil(float(size() + 1) / max_load_factor()))));
+ __bc = bucket_count();
+ }
+ size_t __chash = __cp->__hash_ % __bc;
+ __node_pointer __pp = __bucket_list_[__chash];
+ while (__pp->__next_ != __np)
+ __pp = __pp->__next_;
+ __cp->__next_ = __np;
+ __pp->__next_ = __cp;
+ ++size();
+ return iterator(__cp);
+ }
+ return __node_insert_multi(__cp);
+}
+
+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>::__insert_unique(const value_type& __x)
+{
+ size_t __hash = hash_function()(__x);
+ size_type __bc = bucket_count();
+ bool __inserted = false;
+ __node_pointer __nd;
+ size_t __chash;
+ if (__bc != 0)
+ {
+ __chash = __hash % __bc;
+ __nd = __bucket_list_[__chash];
+ if (__nd != nullptr)
+ {
+ for (__nd = __nd->__next_; __nd != nullptr &&
+ __nd->__hash_ % __bc == __chash;
+ __nd = __nd->__next_)
+ {
+ if (key_eq()(__nd->__value_, __x))
+ goto __done;
+ }
+ }
+ }
+ {
+ __node_holder __h = __construct_node(__x, __hash);
+ if (size()+1 > __bc * max_load_factor() || __bc == 0)
+ {
+ rehash(_STD::max<size_type>(2 * __bc + 1,
+ size_type(ceil(float(size() + 1) / max_load_factor()))));
+ __bc = bucket_count();
+ __chash = __hash % __bc;
+ }
+ // insert_after __bucket_list_[__chash], or __first_node if bucket is null
+ __node_pointer __pn = __bucket_list_[__chash];
+ if (__pn == nullptr)
+ {
+ __pn = static_cast<__node_pointer>(addressof(__p1_.first()));
+ __h->__next_ = __pn->__next_;
+ __pn->__next_ = __h.get();
+ // fix up __bucket_list_
+ __bucket_list_[__chash] = __pn;
+ if (__h->__next_ != nullptr)
+ __bucket_list_[__h->__next_->__hash_ % __bc] = __h.get();
+ }
+ else
+ {
+ __h->__next_ = __pn->__next_;
+ __pn->__next_ = __h.get();
+ }
+ __nd = __h.release();
+ // increment size
+ ++size();
+ __inserted = true;
+ }
+__done:
+ return pair<iterator, bool>(iterator(__nd), __inserted);
+}
+
+#ifdef _LIBCPP_MOVE
+
+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(_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;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _P>
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_P&& __x)
+{
+ __node_holder __h = __construct_node(_STD::forward<_P>(__x));
+ pair<iterator, bool> __r = __node_insert_unique(__h.get());
+ if (__r.second)
+ __h.release();
+ return __r;
+}
+
+#endif
+
+#ifdef _LIBCPP_MOVE
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _P>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_P&& __x)
+{
+ __node_holder __h = __construct_node(_STD::forward<_P>(__x));
+ iterator __r = __node_insert_multi(__h.get());
+ __h.release();
+ return __r;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _P>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
+ _P&& __x)
+{
+ __node_holder __h = __construct_node(_STD::forward<_P>(__x));
+ iterator __r = __node_insert_multi(__p, __h.get());
+ __h.release();
+ return __r;
+}
+
+#else
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x)
+{
+ __node_holder __h = __construct_node(__x);
+ iterator __r = __node_insert_multi(__h.get());
+ __h.release();
+ 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>::__insert_multi(const_iterator __p,
+ const value_type& __x)
+{
+ __node_holder __h = __construct_node(__x);
+ iterator __r = __node_insert_multi(__p, __h.get());
+ __h.release();
+ return __r;
+}
+
+#endif
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
+{
+ __n = __next_prime(_STD::max<size_type>(__n, size() > 0));
+ size_type __bc = bucket_count();
+ if (__n > __bc)
+ __rehash(__n);
+ else
+ {
+ __n = _STD::max<size_type>
+ (
+ __n,
+ __next_prime(size_t(ceil(float(size()) / max_load_factor())))
+ );
+ if (__n < __bc)
+ __rehash(__n);
+ }
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__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;
+ __node_pointer __pp(static_cast<__node_pointer>(addressof(__p1_.first())));
+ __node_pointer __cp = __pp->__next_;
+ if (__cp != nullptr)
+ {
+ size_type __chash = __cp->__hash_ % __nbc;
+ __bucket_list_[__chash] = __pp;
+ size_type __phash = __chash;
+ for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr;
+ __cp = __pp->__next_)
+ {
+ __chash = __cp->__hash_ % __nbc;
+ if (__chash == __phash)
+ __pp = __cp;
+ else
+ {
+ if (__bucket_list_[__chash] == nullptr)
+ {
+ __bucket_list_[__chash] = __pp;
+ __pp = __cp;
+ __phash = __chash;
+ }
+ else
+ {
+ __node_pointer __np = __cp;
+ for (; __np->__next_ != nullptr &&
+ key_eq()(__cp->__value_, __np->__next_->__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 = __hash % __bc;
+ __node_pointer __nd = __bucket_list_[__chash];
+ if (__nd != nullptr)
+ {
+ for (__nd = __nd->__next_; __nd != nullptr &&
+ __nd->__hash_ % __bc == __chash;
+ __nd = __nd->__next_)
+ {
+ if (key_eq()(__nd->__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 = __hash % __bc;
+ __node_const_pointer __nd = __bucket_list_[__chash];
+ if (__nd != nullptr)
+ {
+ for (__nd = __nd->__next_; __nd != nullptr &&
+ __nd->__hash_ % __bc == __chash;
+ __nd = __nd->__next_)
+ {
+ if (key_eq()(__nd->__value_, __k))
+ return const_iterator(__nd);
+ }
+ }
+
+ }
+ return end();
+}
+
+#ifdef _LIBCPP_MOVE
+
+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)
+{
+ __node_allocator& __na = __node_alloc();
+ __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
+ __node_traits::construct(__na, addressof(__h->__value_), _STD::forward<_Args>(__args)...);
+ __h.get_deleter().__value_constructed = true;
+ __h->__hash_ = hash_function()(__h->__value_);
+ __h->__next_ = nullptr;
+ return __h;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v,
+ size_t __hash)
+{
+ __node_allocator& __na = __node_alloc();
+ __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
+ __node_traits::construct(__na, addressof(__h->__value_), _STD::move(__v));
+ __h.get_deleter().__value_constructed = true;
+ __h->__hash_ = __hash;
+ __h->__next_ = nullptr;
+ return _STD::move(__h);
+}
+
+#else
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v)
+{
+ __node_allocator& __na = __node_alloc();
+ __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
+ __node_traits::construct(__na, addressof(__h->__value_), __v);
+ __h.get_deleter().__value_constructed = true;
+ __h->__hash_ = hash_function()(__h->__value_);
+ __h->__next_ = nullptr;
+ return _STD::move(__h);
+}
+
+#endif
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v,
+ size_t __hash)
+{
+ __node_allocator& __na = __node_alloc();
+ __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
+ __node_traits::construct(__na, addressof(__h->__value_), __v);
+ __h.get_deleter().__value_constructed = true;
+ __h->__hash_ = __hash;
+ __h->__next_ = nullptr;
+ return _STD::move(__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)
+{
+ __node_pointer __np = const_cast<__node_pointer>(__p.__node_);
+ 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);
+ }
+ __node_pointer __np = const_cast<__node_pointer>(__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)
+{
+ // current node
+ __node_pointer __cn = const_cast<__node_pointer>(__p.__node_);
+ size_type __bc = bucket_count();
+ size_t __chash = __cn->__hash_ % __bc;
+ // find previous node
+ __node_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 == addressof(__p1_.first()) || __pn->__hash_ % __bc != __chash)
+ {
+ if (__cn->__next_ == nullptr || __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 = __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, _D(__node_alloc()));
+}
+
+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)
+{
+ {
+ __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());
+ __swap_alloc(__bucket_list_.get_deleter().__alloc(),
+ __u.__bucket_list_.get_deleter().__alloc());
+ __swap_alloc(__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_[__p1_.first().__next_->__hash_ % bucket_count()] =
+ static_cast<__node_pointer>(addressof(__p1_.first()));
+ if (__u.size() > 0)
+ __u.__bucket_list_[__u.__p1_.first().__next_->__hash_ % __u.bucket_count()] =
+ static_cast<__node_pointer>(addressof(__u.__p1_.first()));
+}
+
+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
+{
+ __node_const_pointer __np = __bucket_list_[__n];
+ size_type __bc = bucket_count();
+ size_type __r = 0;
+ if (__np != nullptr)
+ {
+ for (__np = __np->__next_; __np != nullptr &&
+ __np->__hash_ % __bc == __n;
+ __np = __np->__next_, ++__r)
+ ;
+ }
+ return __r;
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP__HASH_TABLE