diff options
Diffstat (limited to 'contrib/llvm-project/libcxx/include/ext/hash_map')
| -rw-r--r-- | contrib/llvm-project/libcxx/include/ext/hash_map | 1132 |
1 files changed, 508 insertions, 624 deletions
diff --git a/contrib/llvm-project/libcxx/include/ext/hash_map b/contrib/llvm-project/libcxx/include/ext/hash_map index 176b59fa9ed6..7ac268d5dcbd 100644 --- a/contrib/llvm-project/libcxx/include/ext/hash_map +++ b/contrib/llvm-project/libcxx/include/ext/hash_map @@ -209,11 +209,11 @@ template <class Key, class T, class Hash, class Pred, class Alloc> #include <functional> #if defined(__DEPRECATED) && __DEPRECATED -#if defined(_LIBCPP_WARNING) - _LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>") -#else -# warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map> -#endif +# if defined(_LIBCPP_WARNING) +_LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>") +# else +# warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map> +# endif #endif #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -222,760 +222,644 @@ template <class Key, class T, class Hash, class Pred, class Alloc> namespace __gnu_cxx { -template <class _Tp, class _Hash, - bool = std::is_empty<_Hash>::value && !std::__libcpp_is_final<_Hash>::value - > -class __hash_map_hasher - : private _Hash -{ +template <class _Tp, class _Hash, bool = std::is_empty<_Hash>::value && !std::__libcpp_is_final<_Hash>::value > +class __hash_map_hasher : private _Hash { public: - _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : _Hash() {} - _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : _Hash(__h) {} - _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const {return *this;} - _LIBCPP_HIDE_FROM_ABI - size_t operator()(const _Tp& __x) const - {return static_cast<const _Hash&>(*this)(__x.first);} - _LIBCPP_HIDE_FROM_ABI - size_t operator()(const typename _Tp::first_type& __x) const - {return static_cast<const _Hash&>(*this)(__x);} + _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : _Hash() {} + _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : _Hash(__h) {} + _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const { return *this; } + _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Tp& __x) const { return static_cast<const _Hash&>(*this)(__x.first); } + _LIBCPP_HIDE_FROM_ABI size_t operator()(const typename _Tp::first_type& __x) const { + return static_cast<const _Hash&>(*this)(__x); + } }; template <class _Tp, class _Hash> -class __hash_map_hasher<_Tp, _Hash, false> -{ - _Hash __hash_; +class __hash_map_hasher<_Tp, _Hash, false> { + _Hash __hash_; + public: - _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : __hash_() {} - _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : __hash_(__h) {} - _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const {return __hash_;} - _LIBCPP_HIDE_FROM_ABI - size_t operator()(const _Tp& __x) const - {return __hash_(__x.first);} - _LIBCPP_HIDE_FROM_ABI - size_t operator()(const typename _Tp::first_type& __x) const - {return __hash_(__x);} + _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : __hash_() {} + _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : __hash_(__h) {} + _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const { return __hash_; } + _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Tp& __x) const { return __hash_(__x.first); } + _LIBCPP_HIDE_FROM_ABI size_t operator()(const typename _Tp::first_type& __x) const { return __hash_(__x); } }; -template <class _Tp, class _Pred, - bool = std::is_empty<_Pred>::value && !std::__libcpp_is_final<_Pred>::value - > -class __hash_map_equal - : private _Pred -{ +template <class _Tp, class _Pred, bool = std::is_empty<_Pred>::value && !std::__libcpp_is_final<_Pred>::value > +class __hash_map_equal : private _Pred { public: - _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : _Pred() {} - _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : _Pred(__p) {} - _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const {return *this;} - _LIBCPP_HIDE_FROM_ABI - bool operator()(const _Tp& __x, const _Tp& __y) const - {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} - _LIBCPP_HIDE_FROM_ABI - bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const - {return static_cast<const _Pred&>(*this)(__x, __y.first);} - _LIBCPP_HIDE_FROM_ABI - bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const - {return static_cast<const _Pred&>(*this)(__x.first, __y);} - _LIBCPP_HIDE_FROM_ABI - bool operator()(const typename _Tp::first_type& __x, - const typename _Tp::first_type& __y) const - {return static_cast<const _Pred&>(*this)(__x, __y);} + _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : _Pred() {} + _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : _Pred(__p) {} + _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const { return *this; } + _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const _Tp& __y) const { + return static_cast<const _Pred&>(*this)(__x.first, __y.first); + } + _LIBCPP_HIDE_FROM_ABI bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const { + return static_cast<const _Pred&>(*this)(__x, __y.first); + } + _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const { + return static_cast<const _Pred&>(*this)(__x.first, __y); + } + _LIBCPP_HIDE_FROM_ABI bool + operator()(const typename _Tp::first_type& __x, const typename _Tp::first_type& __y) const { + return static_cast<const _Pred&>(*this)(__x, __y); + } }; template <class _Tp, class _Pred> -class __hash_map_equal<_Tp, _Pred, false> -{ - _Pred __pred_; +class __hash_map_equal<_Tp, _Pred, false> { + _Pred __pred_; + public: - _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : __pred_() {} - _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : __pred_(__p) {} - _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const {return __pred_;} - _LIBCPP_HIDE_FROM_ABI - bool operator()(const _Tp& __x, const _Tp& __y) const - {return __pred_(__x.first, __y.first);} - _LIBCPP_HIDE_FROM_ABI - bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const - {return __pred_(__x, __y.first);} - _LIBCPP_HIDE_FROM_ABI - bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const - {return __pred_(__x.first, __y);} - _LIBCPP_HIDE_FROM_ABI - bool operator()(const typename _Tp::first_type& __x, - const typename _Tp::first_type& __y) const - {return __pred_(__x, __y);} + _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : __pred_() {} + _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : __pred_(__p) {} + _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const { return __pred_; } + _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const _Tp& __y) const { return __pred_(__x.first, __y.first); } + _LIBCPP_HIDE_FROM_ABI bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const { + return __pred_(__x, __y.first); + } + _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const { + return __pred_(__x.first, __y); + } + _LIBCPP_HIDE_FROM_ABI bool + operator()(const typename _Tp::first_type& __x, const typename _Tp::first_type& __y) const { + return __pred_(__x, __y); + } }; template <class _Alloc> -class __hash_map_node_destructor -{ - typedef _Alloc allocator_type; - typedef std::allocator_traits<allocator_type> __alloc_traits; - typedef typename __alloc_traits::value_type::__node_value_type value_type; +class __hash_map_node_destructor { + typedef _Alloc allocator_type; + typedef std::allocator_traits<allocator_type> __alloc_traits; + typedef typename __alloc_traits::value_type::__node_value_type value_type; + public: - typedef typename __alloc_traits::pointer pointer; + typedef typename __alloc_traits::pointer pointer; + private: - typedef typename value_type::first_type first_type; - typedef typename value_type::second_type second_type; + typedef typename value_type::first_type first_type; + typedef typename value_type::second_type second_type; - allocator_type& __na_; + allocator_type& __na_; public: - bool __first_constructed; - bool __second_constructed; + bool __first_constructed; + bool __second_constructed; - _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_map_node_destructor const&) = default; - __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete; + _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_map_node_destructor const&) = default; + __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete; - _LIBCPP_HIDE_FROM_ABI - explicit __hash_map_node_destructor(allocator_type& __na) - : __na_(__na), - __first_constructed(false), - __second_constructed(false) - {} + _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na) + : __na_(__na), __first_constructed(false), __second_constructed(false) {} #ifndef _LIBCPP_CXX03_LANG - _LIBCPP_HIDE_FROM_ABI - __hash_map_node_destructor(std::__hash_node_destructor<allocator_type>&& __x) - : __na_(__x.__na_), - __first_constructed(__x.__value_constructed), - __second_constructed(__x.__value_constructed) - { - __x.__value_constructed = false; - } + _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(std::__hash_node_destructor<allocator_type>&& __x) + : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) { + __x.__value_constructed = false; + } #else // _LIBCPP_CXX03_LANG - _LIBCPP_HIDE_FROM_ABI - __hash_map_node_destructor(const std::__hash_node_destructor<allocator_type>& __x) - : __na_(__x.__na_), - __first_constructed(__x.__value_constructed), - __second_constructed(__x.__value_constructed) - { - const_cast<bool&>(__x.__value_constructed) = false; - } + _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const std::__hash_node_destructor<allocator_type>& __x) + : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) { + const_cast<bool&>(__x.__value_constructed) = false; + } #endif // _LIBCPP_CXX03_LANG - _LIBCPP_HIDE_FROM_ABI - void operator()(pointer __p) - { - if (__second_constructed) - __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().second)); - if (__first_constructed) - __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().first)); - if (__p) - __alloc_traits::deallocate(__na_, __p, 1); - } + _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) { + if (__second_constructed) + __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().second)); + if (__first_constructed) + __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().first)); + if (__p) + __alloc_traits::deallocate(__na_, __p, 1); + } }; template <class _HashIterator> -class _LIBCPP_TEMPLATE_VIS __hash_map_iterator -{ - _HashIterator __i_; +class _LIBCPP_TEMPLATE_VIS __hash_map_iterator { + _HashIterator __i_; + + typedef const typename _HashIterator::value_type::first_type key_type; + typedef typename _HashIterator::value_type::second_type mapped_type; - typedef const typename _HashIterator::value_type::first_type key_type; - typedef typename _HashIterator::value_type::second_type mapped_type; public: - typedef std::forward_iterator_tag iterator_category; - typedef std::pair<key_type, mapped_type> value_type; - typedef typename _HashIterator::difference_type difference_type; - typedef value_type& reference; - typedef std::__rebind_pointer_t<typename _HashIterator::pointer, value_type> - pointer; - - _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() {} - - _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) : __i_(__i) {} - - _LIBCPP_HIDE_FROM_ABI reference operator*() const {return *operator->();} - _LIBCPP_HIDE_FROM_ABI pointer operator->() const {return (pointer)__i_.operator->();} - - _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() {++__i_; return *this;} - _LIBCPP_HIDE_FROM_ABI - __hash_map_iterator operator++(int) - { - __hash_map_iterator __t(*this); - ++(*this); - return __t; - } - - friend _LIBCPP_HIDE_FROM_ABI - bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) - {return __x.__i_ == __y.__i_;} - friend _LIBCPP_HIDE_FROM_ABI - bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) - {return __x.__i_ != __y.__i_;} - - template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_map; - template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_multimap; - template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; - template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; - template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator; + typedef std::forward_iterator_tag iterator_category; + typedef std::pair<key_type, mapped_type> value_type; + typedef typename _HashIterator::difference_type difference_type; + typedef value_type& reference; + typedef std::__rebind_pointer_t<typename _HashIterator::pointer, value_type> pointer; + + _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() {} + + _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) : __i_(__i) {} + + _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *operator->(); } + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return (pointer)__i_.operator->(); } + + _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() { + ++__i_; + return *this; + } + _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) { + __hash_map_iterator __t(*this); + ++(*this); + return __t; + } + + friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) { + return __x.__i_ == __y.__i_; + } + friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) { + return __x.__i_ != __y.__i_; + } + + template <class, class, class, class, class> + friend class _LIBCPP_TEMPLATE_VIS hash_map; + template <class, class, class, class, class> + friend class _LIBCPP_TEMPLATE_VIS hash_multimap; + template <class> + friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; + template <class> + friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; + template <class> + friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator; }; template <class _HashIterator> -class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator -{ - _HashIterator __i_; +class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator { + _HashIterator __i_; + + typedef const typename _HashIterator::value_type::first_type key_type; + typedef typename _HashIterator::value_type::second_type mapped_type; - typedef const typename _HashIterator::value_type::first_type key_type; - typedef typename _HashIterator::value_type::second_type mapped_type; public: - typedef std::forward_iterator_tag iterator_category; - typedef std::pair<key_type, mapped_type> value_type; - typedef typename _HashIterator::difference_type difference_type; - typedef const value_type& reference; - typedef std::__rebind_pointer_t<typename _HashIterator::pointer, const value_type> - pointer; - - _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() {} - - _LIBCPP_HIDE_FROM_ABI - __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {} - _LIBCPP_HIDE_FROM_ABI - __hash_map_const_iterator( - __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) - : __i_(__i.__i_) {} - - _LIBCPP_HIDE_FROM_ABI - reference operator*() const {return *operator->();} - _LIBCPP_HIDE_FROM_ABI - pointer operator->() const {return (pointer)__i_.operator->();} - - _LIBCPP_HIDE_FROM_ABI - __hash_map_const_iterator& operator++() {++__i_; return *this;} - _LIBCPP_HIDE_FROM_ABI - __hash_map_const_iterator operator++(int) - { - __hash_map_const_iterator __t(*this); - ++(*this); - return __t; - } - - friend _LIBCPP_HIDE_FROM_ABI - bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) - {return __x.__i_ == __y.__i_;} - friend _LIBCPP_HIDE_FROM_ABI - bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) - {return __x.__i_ != __y.__i_;} - - template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_map; - template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_multimap; - template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; - template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; + typedef std::forward_iterator_tag iterator_category; + typedef std::pair<key_type, mapped_type> value_type; + typedef typename _HashIterator::difference_type difference_type; + typedef const value_type& reference; + typedef std::__rebind_pointer_t<typename _HashIterator::pointer, const value_type> pointer; + + _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() {} + + _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {} + _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) + : __i_(__i.__i_) {} + + _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *operator->(); } + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return (pointer)__i_.operator->(); } + + _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() { + ++__i_; + return *this; + } + _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) { + __hash_map_const_iterator __t(*this); + ++(*this); + return __t; + } + + friend _LIBCPP_HIDE_FROM_ABI bool + operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) { + return __x.__i_ == __y.__i_; + } + friend _LIBCPP_HIDE_FROM_ABI bool + operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) { + return __x.__i_ != __y.__i_; + } + + template <class, class, class, class, class> + friend class _LIBCPP_TEMPLATE_VIS hash_map; + template <class, class, class, class, class> + friend class _LIBCPP_TEMPLATE_VIS hash_multimap; + template <class> + friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; + template <class> + friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; }; -template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = std::equal_to<_Key>, +template <class _Key, + class _Tp, + class _Hash = hash<_Key>, + class _Pred = std::equal_to<_Key>, class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > -class _LIBCPP_TEMPLATE_VIS hash_map -{ +class _LIBCPP_TEMPLATE_VIS hash_map { public: - // types - typedef _Key key_type; - typedef _Tp mapped_type; - typedef _Tp data_type; - typedef _Hash hasher; - typedef _Pred key_equal; - typedef _Alloc allocator_type; - typedef std::pair<const key_type, mapped_type> value_type; - typedef value_type& reference; - typedef const value_type& const_reference; + // types + typedef _Key key_type; + typedef _Tp mapped_type; + typedef _Tp data_type; + typedef _Hash hasher; + typedef _Pred key_equal; + typedef _Alloc allocator_type; + typedef std::pair<const key_type, mapped_type> value_type; + typedef value_type& reference; + typedef const value_type& const_reference; private: - typedef std::pair<key_type, mapped_type> __value_type; - typedef __hash_map_hasher<__value_type, hasher> __hasher; - typedef __hash_map_equal<__value_type, key_equal> __key_equal; - typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type; - - typedef std::__hash_table<__value_type, __hasher, - __key_equal, __allocator_type> __table; - - __table __table_; - - typedef typename __table::__node_pointer __node_pointer; - typedef typename __table::__node_const_pointer __node_const_pointer; - typedef typename __table::__node_traits __node_traits; - typedef typename __table::__node_allocator __node_allocator; - typedef typename __table::__node __node; - typedef __hash_map_node_destructor<__node_allocator> _Dp; - typedef std::unique_ptr<__node, _Dp> __node_holder; - typedef std::allocator_traits<allocator_type> __alloc_traits; + typedef std::pair<key_type, mapped_type> __value_type; + typedef __hash_map_hasher<__value_type, hasher> __hasher; + typedef __hash_map_equal<__value_type, key_equal> __key_equal; + typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type; + + typedef std::__hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table; + + __table __table_; + + typedef typename __table::__node_pointer __node_pointer; + typedef typename __table::__node_const_pointer __node_const_pointer; + typedef typename __table::__node_traits __node_traits; + typedef typename __table::__node_allocator __node_allocator; + typedef typename __table::__node __node; + typedef __hash_map_node_destructor<__node_allocator> _Dp; + typedef std::unique_ptr<__node, _Dp> __node_holder; + typedef std::allocator_traits<allocator_type> __alloc_traits; + public: - 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; - - typedef __hash_map_iterator<typename __table::iterator> iterator; - typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; - - _LIBCPP_HIDE_FROM_ABI hash_map() { } - explicit _LIBCPP_HIDE_FROM_ABI hash_map(size_type __n, const hasher& __hf = hasher(), - const key_equal& __eql = key_equal()); - _LIBCPP_HIDE_FROM_ABI hash_map(size_type __n, const hasher& __hf, - const key_equal& __eql, - const allocator_type& __a); - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI hash_map(_InputIterator __first, _InputIterator __last); - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI hash_map(_InputIterator __first, _InputIterator __last, - size_type __n, const hasher& __hf = hasher(), - const key_equal& __eql = key_equal()); - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI hash_map(_InputIterator __first, _InputIterator __last, - size_type __n, const hasher& __hf, - const key_equal& __eql, - const allocator_type& __a); - _LIBCPP_HIDE_FROM_ABI hash_map(const hash_map& __u); - - _LIBCPP_HIDE_FROM_ABI - allocator_type get_allocator() const - {return allocator_type(__table_.__node_alloc());} - - _LIBCPP_HIDE_FROM_ABI - bool empty() const {return __table_.size() == 0;} - _LIBCPP_HIDE_FROM_ABI - size_type size() const {return __table_.size();} - _LIBCPP_HIDE_FROM_ABI - size_type max_size() const {return __table_.max_size();} - - _LIBCPP_HIDE_FROM_ABI - iterator begin() {return __table_.begin();} - _LIBCPP_HIDE_FROM_ABI - iterator end() {return __table_.end();} - _LIBCPP_HIDE_FROM_ABI - const_iterator begin() const {return __table_.begin();} - _LIBCPP_HIDE_FROM_ABI - const_iterator end() const {return __table_.end();} - - _LIBCPP_HIDE_FROM_ABI - std::pair<iterator, bool> insert(const value_type& __x) - {return __table_.__insert_unique(__x);} - _LIBCPP_HIDE_FROM_ABI - iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;} - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI - void insert(_InputIterator __first, _InputIterator __last); - - _LIBCPP_HIDE_FROM_ABI - void erase(const_iterator __p) {__table_.erase(__p.__i_);} - _LIBCPP_HIDE_FROM_ABI - size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} - _LIBCPP_HIDE_FROM_ABI - void erase(const_iterator __first, const_iterator __last) - {__table_.erase(__first.__i_, __last.__i_);} - _LIBCPP_HIDE_FROM_ABI - void clear() {__table_.clear();} - - _LIBCPP_HIDE_FROM_ABI - void swap(hash_map& __u) {__table_.swap(__u.__table_);} - - _LIBCPP_HIDE_FROM_ABI - hasher hash_funct() const - {return __table_.hash_function().hash_function();} - _LIBCPP_HIDE_FROM_ABI - key_equal key_eq() const - {return __table_.key_eq().key_eq();} - - _LIBCPP_HIDE_FROM_ABI - iterator find(const key_type& __k) {return __table_.find(__k);} - _LIBCPP_HIDE_FROM_ABI - const_iterator find(const key_type& __k) const {return __table_.find(__k);} - _LIBCPP_HIDE_FROM_ABI - size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} - _LIBCPP_HIDE_FROM_ABI - std::pair<iterator, iterator> equal_range(const key_type& __k) - {return __table_.__equal_range_unique(__k);} - _LIBCPP_HIDE_FROM_ABI - std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const - {return __table_.__equal_range_unique(__k);} - - _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k); - - _LIBCPP_HIDE_FROM_ABI - size_type bucket_count() const {return __table_.bucket_count();} - _LIBCPP_HIDE_FROM_ABI - size_type max_bucket_count() const {return __table_.max_bucket_count();} - - _LIBCPP_HIDE_FROM_ABI - size_type elems_in_bucket(size_type __n) const - {return __table_.bucket_size(__n);} - - _LIBCPP_HIDE_FROM_ABI - void resize(size_type __n) {__table_.__rehash_unique(__n);} + 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; + + typedef __hash_map_iterator<typename __table::iterator> iterator; + typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; + + _LIBCPP_HIDE_FROM_ABI hash_map() {} + explicit _LIBCPP_HIDE_FROM_ABI + hash_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); + _LIBCPP_HIDE_FROM_ABI hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI hash_map(_InputIterator __first, _InputIterator __last); + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI + hash_map(_InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal()); + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI + hash_map(_InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf, + const key_equal& __eql, + const allocator_type& __a); + _LIBCPP_HIDE_FROM_ABI hash_map(const hash_map& __u); + + _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); } + + _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; } + _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); } + _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); } + + _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); } + _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); } + _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); } + _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); } + + _LIBCPP_HIDE_FROM_ABI std::pair<iterator, bool> insert(const value_type& __x) { + return __table_.__insert_unique(__x); + } + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; } + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); + + _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p.__i_); } + _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); } + _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { + __table_.erase(__first.__i_, __last.__i_); + } + _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); } + + _LIBCPP_HIDE_FROM_ABI void swap(hash_map& __u) { __table_.swap(__u.__table_); } + + _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function().hash_function(); } + _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); } + + _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } + _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } + _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); } + _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) { + return __table_.__equal_range_unique(__k); + } + _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { + return __table_.__equal_range_unique(__k); + } + + _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k); + + _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); } + _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); } + + _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); } + + _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_unique(__n); } private: - _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(const key_type& __k); + _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(const key_type& __k); }; template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( - size_type __n, const hasher& __hf, const key_equal& __eql) - : __table_(__hf, __eql) -{ - __table_.__rehash_unique(__n); +hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(size_type __n, const hasher& __hf, const key_equal& __eql) + : __table_(__hf, __eql) { + __table_.__rehash_unique(__n); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( - size_type __n, const hasher& __hf, const key_equal& __eql, - const allocator_type& __a) - : __table_(__hf, __eql, __a) -{ - __table_.__rehash_unique(__n); + size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) + : __table_(__hf, __eql, __a) { + __table_.__rehash_unique(__n); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> template <class _InputIterator> -hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( - _InputIterator __first, _InputIterator __last) -{ - insert(__first, __last); +hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(_InputIterator __first, _InputIterator __last) { + insert(__first, __last); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> template <class _InputIterator> hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( - _InputIterator __first, _InputIterator __last, size_type __n, - const hasher& __hf, const key_equal& __eql) - : __table_(__hf, __eql) -{ - __table_.__rehash_unique(__n); - insert(__first, __last); + _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) + : __table_(__hf, __eql) { + __table_.__rehash_unique(__n); + insert(__first, __last); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> template <class _InputIterator> hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( - _InputIterator __first, _InputIterator __last, size_type __n, - const hasher& __hf, const key_equal& __eql, const allocator_type& __a) - : __table_(__hf, __eql, __a) -{ - __table_.__rehash_unique(__n); - insert(__first, __last); + _InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf, + const key_equal& __eql, + const allocator_type& __a) + : __table_(__hf, __eql, __a) { + __table_.__rehash_unique(__n); + insert(__first, __last); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( - const hash_map& __u) - : __table_(__u.__table_) -{ - __table_.__rehash_unique(__u.bucket_count()); - insert(__u.begin(), __u.end()); +hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(const hash_map& __u) : __table_(__u.__table_) { + __table_.__rehash_unique(__u.bucket_count()); + insert(__u.begin(), __u.end()); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder -hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) -{ - __node_allocator& __na = __table_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, std::addressof(__h->__get_value().first), __k); - __h.get_deleter().__first_constructed = true; - __node_traits::construct(__na, std::addressof(__h->__get_value().second)); - __h.get_deleter().__second_constructed = true; - return __h; +hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) { + __node_allocator& __na = __table_.__node_alloc(); + __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); + __node_traits::construct(__na, std::addressof(__h->__get_value().first), __k); + __h.get_deleter().__first_constructed = true; + __node_traits::construct(__na, std::addressof(__h->__get_value().second)); + __h.get_deleter().__second_constructed = true; + return __h; } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> template <class _InputIterator> -inline -void -hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, - _InputIterator __last) -{ - for (; __first != __last; ++__first) - __table_.__insert_unique(*__first); +inline void hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { + for (; __first != __last; ++__first) + __table_.__insert_unique(*__first); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -_Tp& -hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) -{ - iterator __i = find(__k); - if (__i != end()) - return __i->second; - __node_holder __h = __construct_node(__k); - std::pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); - __h.release(); - return __r.first->second; +_Tp& hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) { + iterator __i = find(__k); + if (__i != end()) + return __i->second; + __node_holder __h = __construct_node(__k); + std::pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); + __h.release(); + return __r.first->second; } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -inline _LIBCPP_HIDE_FROM_ABI -void -swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, - hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) -{ - __x.swap(__y); +inline _LIBCPP_HIDE_FROM_ABI void +swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { + __x.swap(__y); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> _LIBCPP_HIDE_FROM_ABI bool -operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, - const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) -{ - if (__x.size() != __y.size()) - return false; - typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator - const_iterator; - for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); - __i != __ex; ++__i) - { - const_iterator __j = __y.find(__i->first); - if (__j == __ey || !(*__i == *__j)) - return false; - } - return true; +operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { + if (__x.size() != __y.size()) + return false; + typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator; + for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) { + const_iterator __j = __y.find(__i->first); + if (__j == __ey || !(*__i == *__j)) + return false; + } + return true; } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -inline _LIBCPP_HIDE_FROM_ABI -bool -operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, - const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) -{ - return !(__x == __y); +inline _LIBCPP_HIDE_FROM_ABI bool +operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { + return !(__x == __y); } -template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = std::equal_to<_Key>, +template <class _Key, + class _Tp, + class _Hash = hash<_Key>, + class _Pred = std::equal_to<_Key>, class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > -class _LIBCPP_TEMPLATE_VIS hash_multimap -{ +class _LIBCPP_TEMPLATE_VIS hash_multimap { public: - // types - typedef _Key key_type; - typedef _Tp mapped_type; - typedef _Tp data_type; - typedef _Hash hasher; - typedef _Pred key_equal; - typedef _Alloc allocator_type; - typedef std::pair<const key_type, mapped_type> value_type; - typedef value_type& reference; - typedef const value_type& const_reference; + // types + typedef _Key key_type; + typedef _Tp mapped_type; + typedef _Tp data_type; + typedef _Hash hasher; + typedef _Pred key_equal; + typedef _Alloc allocator_type; + typedef std::pair<const key_type, mapped_type> value_type; + typedef value_type& reference; + typedef const value_type& const_reference; private: - typedef std::pair<key_type, mapped_type> __value_type; - typedef __hash_map_hasher<__value_type, hasher> __hasher; - typedef __hash_map_equal<__value_type, key_equal> __key_equal; - typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type; - - typedef std::__hash_table<__value_type, __hasher, - __key_equal, __allocator_type> __table; - - __table __table_; - - typedef typename __table::__node_traits __node_traits; - typedef typename __table::__node_allocator __node_allocator; - typedef typename __table::__node __node; - typedef __hash_map_node_destructor<__node_allocator> _Dp; - typedef std::unique_ptr<__node, _Dp> __node_holder; - typedef std::allocator_traits<allocator_type> __alloc_traits; + typedef std::pair<key_type, mapped_type> __value_type; + typedef __hash_map_hasher<__value_type, hasher> __hasher; + typedef __hash_map_equal<__value_type, key_equal> __key_equal; + typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type; + + typedef std::__hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table; + + __table __table_; + + typedef typename __table::__node_traits __node_traits; + typedef typename __table::__node_allocator __node_allocator; + typedef typename __table::__node __node; + typedef __hash_map_node_destructor<__node_allocator> _Dp; + typedef std::unique_ptr<__node, _Dp> __node_holder; + typedef std::allocator_traits<allocator_type> __alloc_traits; + public: - 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; - - typedef __hash_map_iterator<typename __table::iterator> iterator; - typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; - - _LIBCPP_HIDE_FROM_ABI - hash_multimap() { } - explicit _LIBCPP_HIDE_FROM_ABI hash_multimap(size_type __n, const hasher& __hf = hasher(), - const key_equal& __eql = key_equal()); - _LIBCPP_HIDE_FROM_ABI hash_multimap(size_type __n, const hasher& __hf, - const key_equal& __eql, - const allocator_type& __a); - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI hash_multimap(_InputIterator __first, _InputIterator __last); - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI hash_multimap(_InputIterator __first, _InputIterator __last, - size_type __n, const hasher& __hf = hasher(), - const key_equal& __eql = key_equal()); - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI hash_multimap(_InputIterator __first, _InputIterator __last, - size_type __n, const hasher& __hf, - const key_equal& __eql, - const allocator_type& __a); - _LIBCPP_HIDE_FROM_ABI hash_multimap(const hash_multimap& __u); - - _LIBCPP_HIDE_FROM_ABI - allocator_type get_allocator() const - {return allocator_type(__table_.__node_alloc());} - - _LIBCPP_HIDE_FROM_ABI - bool empty() const {return __table_.size() == 0;} - _LIBCPP_HIDE_FROM_ABI - size_type size() const {return __table_.size();} - _LIBCPP_HIDE_FROM_ABI - size_type max_size() const {return __table_.max_size();} - - _LIBCPP_HIDE_FROM_ABI - iterator begin() {return __table_.begin();} - _LIBCPP_HIDE_FROM_ABI - iterator end() {return __table_.end();} - _LIBCPP_HIDE_FROM_ABI - const_iterator begin() const {return __table_.begin();} - _LIBCPP_HIDE_FROM_ABI - const_iterator end() const {return __table_.end();} - - _LIBCPP_HIDE_FROM_ABI - iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} - _LIBCPP_HIDE_FROM_ABI - iterator insert(const_iterator, const value_type& __x) {return insert(__x);} - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI - void insert(_InputIterator __first, _InputIterator __last); - - _LIBCPP_HIDE_FROM_ABI - void erase(const_iterator __p) {__table_.erase(__p.__i_);} - _LIBCPP_HIDE_FROM_ABI - size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} - _LIBCPP_HIDE_FROM_ABI - void erase(const_iterator __first, const_iterator __last) - {__table_.erase(__first.__i_, __last.__i_);} - _LIBCPP_HIDE_FROM_ABI - void clear() {__table_.clear();} - - _LIBCPP_HIDE_FROM_ABI - void swap(hash_multimap& __u) {__table_.swap(__u.__table_);} - - _LIBCPP_HIDE_FROM_ABI - hasher hash_funct() const - {return __table_.hash_function().hash_function();} - _LIBCPP_HIDE_FROM_ABI - key_equal key_eq() const - {return __table_.key_eq().key_eq();} - - _LIBCPP_HIDE_FROM_ABI - iterator find(const key_type& __k) {return __table_.find(__k);} - _LIBCPP_HIDE_FROM_ABI - const_iterator find(const key_type& __k) const {return __table_.find(__k);} - _LIBCPP_HIDE_FROM_ABI - size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} - _LIBCPP_HIDE_FROM_ABI - std::pair<iterator, iterator> equal_range(const key_type& __k) - {return __table_.__equal_range_multi(__k);} - _LIBCPP_HIDE_FROM_ABI - std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const - {return __table_.__equal_range_multi(__k);} - - _LIBCPP_HIDE_FROM_ABI - size_type bucket_count() const {return __table_.bucket_count();} - _LIBCPP_HIDE_FROM_ABI - size_type max_bucket_count() const {return __table_.max_bucket_count();} - - _LIBCPP_HIDE_FROM_ABI - size_type elems_in_bucket(size_type __n) const - {return __table_.bucket_size(__n);} - - _LIBCPP_HIDE_FROM_ABI - void resize(size_type __n) {__table_.__rehash_multi(__n);} + 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; + + typedef __hash_map_iterator<typename __table::iterator> iterator; + typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; + + _LIBCPP_HIDE_FROM_ABI hash_multimap() {} + explicit _LIBCPP_HIDE_FROM_ABI + hash_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); + _LIBCPP_HIDE_FROM_ABI + hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI hash_multimap(_InputIterator __first, _InputIterator __last); + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI + hash_multimap(_InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal()); + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI hash_multimap( + _InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf, + const key_equal& __eql, + const allocator_type& __a); + _LIBCPP_HIDE_FROM_ABI hash_multimap(const hash_multimap& __u); + + _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); } + + _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; } + _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); } + _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); } + + _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); } + _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); } + _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); } + _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); } + + _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); } + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x); } + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); + + _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p.__i_); } + _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); } + _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { + __table_.erase(__first.__i_, __last.__i_); + } + _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); } + + _LIBCPP_HIDE_FROM_ABI void swap(hash_multimap& __u) { __table_.swap(__u.__table_); } + + _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function().hash_function(); } + _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); } + + _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } + _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } + _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); } + _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) { + return __table_.__equal_range_multi(__k); + } + _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { + return __table_.__equal_range_multi(__k); + } + + _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); } + _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); } + + _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); } + + _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_multi(__n); } }; template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( - size_type __n, const hasher& __hf, const key_equal& __eql) - : __table_(__hf, __eql) -{ - __table_.__rehash_multi(__n); +hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql) + : __table_(__hf, __eql) { + __table_.__rehash_multi(__n); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( - size_type __n, const hasher& __hf, const key_equal& __eql, - const allocator_type& __a) - : __table_(__hf, __eql, __a) -{ - __table_.__rehash_multi(__n); + size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) + : __table_(__hf, __eql, __a) { + __table_.__rehash_multi(__n); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> template <class _InputIterator> -hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( - _InputIterator __first, _InputIterator __last) -{ - insert(__first, __last); +hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(_InputIterator __first, _InputIterator __last) { + insert(__first, __last); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> template <class _InputIterator> hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( - _InputIterator __first, _InputIterator __last, size_type __n, - const hasher& __hf, const key_equal& __eql) - : __table_(__hf, __eql) -{ - __table_.__rehash_multi(__n); - insert(__first, __last); + _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) + : __table_(__hf, __eql) { + __table_.__rehash_multi(__n); + insert(__first, __last); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> template <class _InputIterator> hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( - _InputIterator __first, _InputIterator __last, size_type __n, - const hasher& __hf, const key_equal& __eql, const allocator_type& __a) - : __table_(__hf, __eql, __a) -{ - __table_.__rehash_multi(__n); - insert(__first, __last); + _InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf, + const key_equal& __eql, + const allocator_type& __a) + : __table_(__hf, __eql, __a) { + __table_.__rehash_multi(__n); + insert(__first, __last); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( - const hash_multimap& __u) - : __table_(__u.__table_) -{ - __table_.__rehash_multi(__u.bucket_count()); - insert(__u.begin(), __u.end()); +hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(const hash_multimap& __u) : __table_(__u.__table_) { + __table_.__rehash_multi(__u.bucket_count()); + insert(__u.begin(), __u.end()); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> template <class _InputIterator> -inline -void -hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, - _InputIterator __last) -{ - for (; __first != __last; ++__first) - __table_.__insert_multi(*__first); +inline void hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { + for (; __first != __last; ++__first) + __table_.__insert_multi(*__first); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -inline _LIBCPP_HIDE_FROM_ABI -void -swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, - hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) -{ - __x.swap(__y); +inline _LIBCPP_HIDE_FROM_ABI void +swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { + __x.swap(__y); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -_LIBCPP_HIDE_FROM_ABI bool -operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, - const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) -{ - if (__x.size() != __y.size()) - return false; - typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator - const_iterator; - typedef std::pair<const_iterator, const_iterator> _EqRng; - for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) - { - _EqRng __xeq = __x.equal_range(__i->first); - _EqRng __yeq = __y.equal_range(__i->first); - if (std::distance(__xeq.first, __xeq.second) != - std::distance(__yeq.first, __yeq.second) || - !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) - return false; - __i = __xeq.second; - } - return true; +_LIBCPP_HIDE_FROM_ABI bool operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, + const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { + if (__x.size() != __y.size()) + return false; + typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator; + typedef std::pair<const_iterator, const_iterator> _EqRng; + for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) { + _EqRng __xeq = __x.equal_range(__i->first); + _EqRng __yeq = __y.equal_range(__i->first); + if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) || + !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) + return false; + __i = __xeq.second; + } + return true; } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -inline _LIBCPP_HIDE_FROM_ABI -bool -operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, - const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) -{ - return !(__x == __y); +inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, + const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { + return !(__x == __y); } } // namespace __gnu_cxx |