1 // Internal policy header for unordered_set and unordered_map -*- C++ -*-
3 // Copyright (C) 2010-2013 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file bits/hashtable_policy.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly.
28 * @headername{unordered_map,unordered_set}
31 #ifndef _HASHTABLE_POLICY_H
32 #define _HASHTABLE_POLICY_H 1
34 namespace std
_GLIBCXX_VISIBILITY(default)
36 _GLIBCXX_BEGIN_NAMESPACE_VERSION
38 template<typename _Key
, typename _Value
, typename _Alloc
,
39 typename _ExtractKey
, typename _Equal
,
40 typename _H1
, typename _H2
, typename _Hash
,
41 typename _RehashPolicy
, typename _Traits
>
44 _GLIBCXX_END_NAMESPACE_VERSION
48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
51 * @defgroup hashtable-detail Base and Implementation Classes
52 * @ingroup unordered_associative_containers
55 template<typename _Key
, typename _Value
,
56 typename _ExtractKey
, typename _Equal
,
57 typename _H1
, typename _H2
, typename _Hash
, typename _Traits
>
58 struct _Hashtable_base
;
60 // Helper function: return distance(first, last) for forward
61 // iterators, or 0 for input iterators.
62 template<class _Iterator
>
63 inline typename
std::iterator_traits
<_Iterator
>::difference_type
64 __distance_fw(_Iterator __first
, _Iterator __last
,
65 std::input_iterator_tag
)
68 template<class _Iterator
>
69 inline typename
std::iterator_traits
<_Iterator
>::difference_type
70 __distance_fw(_Iterator __first
, _Iterator __last
,
71 std::forward_iterator_tag
)
72 { return std::distance(__first
, __last
); }
74 template<class _Iterator
>
75 inline typename
std::iterator_traits
<_Iterator
>::difference_type
76 __distance_fw(_Iterator __first
, _Iterator __last
)
78 typedef typename
std::iterator_traits
<_Iterator
>::iterator_category _Tag
;
79 return __distance_fw(__first
, __last
, _Tag());
82 // Helper type used to detect whether the hash functor is noexcept.
83 template <typename _Key
, typename _Hash
>
84 struct __is_noexcept_hash
: std::integral_constant
<bool,
85 noexcept(declval
<const _Hash
&>()(declval
<const _Key
&>()))>
90 template<typename _Tp
>
92 operator()(_Tp
&& __x
) const
93 { return std::forward
<_Tp
>(__x
); }
98 template<typename _Tp
>
100 operator()(_Tp
&& __x
) const
101 -> decltype(std::get
<0>(std::forward
<_Tp
>(__x
)))
102 { return std::get
<0>(std::forward
<_Tp
>(__x
)); }
105 template<typename _NodeAlloc
>
106 struct _Hashtable_alloc
;
108 // Functor recycling a pool of nodes and using allocation once the pool is
110 template<typename _NodeAlloc
>
111 struct _ReuseOrAllocNode
114 using __node_alloc_type
= _NodeAlloc
;
115 using __hashtable_alloc
= _Hashtable_alloc
<__node_alloc_type
>;
116 using __value_alloc_type
= typename
__hashtable_alloc::__value_alloc_type
;
117 using __value_alloc_traits
=
118 typename
__hashtable_alloc::__value_alloc_traits
;
119 using __node_alloc_traits
=
120 typename
__hashtable_alloc::__node_alloc_traits
;
121 using __node_type
= typename
__hashtable_alloc::__node_type
;
124 _ReuseOrAllocNode(__node_type
* __nodes
, __hashtable_alloc
& __h
)
125 : _M_nodes(__nodes
), _M_h(__h
) { }
126 _ReuseOrAllocNode(const _ReuseOrAllocNode
&) = delete;
129 { _M_h
._M_deallocate_nodes(_M_nodes
); }
131 template<typename _Arg
>
133 operator()(_Arg
&& __arg
) const
137 __node_type
* __node
= _M_nodes
;
138 _M_nodes
= _M_nodes
->_M_next();
139 __node
->_M_nxt
= nullptr;
140 __value_alloc_type
__a(_M_h
._M_node_allocator());
141 __value_alloc_traits::destroy(__a
, __node
->_M_valptr());
144 __value_alloc_traits::construct(__a
, __node
->_M_valptr(),
145 std::forward
<_Arg
>(__arg
));
149 __node
->~__node_type();
150 __node_alloc_traits::deallocate(_M_h
._M_node_allocator(),
152 __throw_exception_again
;
156 return _M_h
._M_allocate_node(std::forward
<_Arg
>(__arg
));
160 mutable __node_type
* _M_nodes
;
161 __hashtable_alloc
& _M_h
;
164 // Functor similar to the previous one but without any pool of node to recycle.
165 template<typename _NodeAlloc
>
169 using __hashtable_alloc
= _Hashtable_alloc
<_NodeAlloc
>;
170 using __node_type
= typename
__hashtable_alloc::__node_type
;
173 _AllocNode(__hashtable_alloc
& __h
)
176 template<typename _Arg
>
178 operator()(_Arg
&& __arg
) const
179 { return _M_h
._M_allocate_node(std::forward
<_Arg
>(__arg
)); }
182 __hashtable_alloc
& _M_h
;
185 // Auxiliary types used for all instantiations of _Hashtable nodes
189 * struct _Hashtable_traits
191 * Important traits for hash tables.
193 * @tparam _Cache_hash_code Boolean value. True if the value of
194 * the hash function is stored along with the value. This is a
195 * time-space tradeoff. Storing it may improve lookup speed by
196 * reducing the number of times we need to call the _Equal
199 * @tparam _Constant_iterators Boolean value. True if iterator and
200 * const_iterator are both constant iterator types. This is true
201 * for unordered_set and unordered_multiset, false for
202 * unordered_map and unordered_multimap.
204 * @tparam _Unique_keys Boolean value. True if the return value
205 * of _Hashtable::count(k) is always at most one, false if it may
206 * be an arbitrary number. This is true for unordered_set and
207 * unordered_map, false for unordered_multiset and
208 * unordered_multimap.
210 template<bool _Cache_hash_code
, bool _Constant_iterators
, bool _Unique_keys
>
211 struct _Hashtable_traits
214 using __bool_constant
= integral_constant
<bool, _Cond
>;
216 using __hash_cached
= __bool_constant
<_Cache_hash_code
>;
217 using __constant_iterators
= __bool_constant
<_Constant_iterators
>;
218 using __unique_keys
= __bool_constant
<_Unique_keys
>;
222 * struct _Hash_node_base
224 * Nodes, used to wrap elements stored in the hash table. A policy
225 * template parameter of class template _Hashtable controls whether
226 * nodes also store a hash code. In some cases (e.g. strings) this
227 * may be a performance win.
229 struct _Hash_node_base
231 _Hash_node_base
* _M_nxt
;
233 _Hash_node_base() : _M_nxt() { }
235 _Hash_node_base(_Hash_node_base
* __next
) : _M_nxt(__next
) { }
239 * struct _Hash_node_value_base
241 * Node type with the value to store.
243 template<typename _Value
>
244 struct _Hash_node_value_base
: _Hash_node_base
246 typedef _Value value_type
;
248 __gnu_cxx::__aligned_buffer
<_Value
> _M_storage
;
252 { return _M_storage
._M_ptr(); }
255 _M_valptr() const noexcept
256 { return _M_storage
._M_ptr(); }
260 { return *_M_valptr(); }
263 _M_v() const noexcept
264 { return *_M_valptr(); }
268 * Primary template struct _Hash_node.
270 template<typename _Value
, bool _Cache_hash_code
>
274 * Specialization for nodes with caches, struct _Hash_node.
276 * Base class is __detail::_Hash_node_value_base.
278 template<typename _Value
>
279 struct _Hash_node
<_Value
, true> : _Hash_node_value_base
<_Value
>
281 std::size_t _M_hash_code
;
284 _M_next() const { return static_cast<_Hash_node
*>(this->_M_nxt
); }
288 * Specialization for nodes without caches, struct _Hash_node.
290 * Base class is __detail::_Hash_node_value_base.
292 template<typename _Value
>
293 struct _Hash_node
<_Value
, false> : _Hash_node_value_base
<_Value
>
296 _M_next() const { return static_cast<_Hash_node
*>(this->_M_nxt
); }
299 /// Base class for node iterators.
300 template<typename _Value
, bool _Cache_hash_code
>
301 struct _Node_iterator_base
303 using __node_type
= _Hash_node
<_Value
, _Cache_hash_code
>;
307 _Node_iterator_base(__node_type
* __p
)
312 { _M_cur
= _M_cur
->_M_next(); }
315 template<typename _Value
, bool _Cache_hash_code
>
317 operator==(const _Node_iterator_base
<_Value
, _Cache_hash_code
>& __x
,
318 const _Node_iterator_base
<_Value
, _Cache_hash_code
>& __y
)
319 { return __x
._M_cur
== __y
._M_cur
; }
321 template<typename _Value
, bool _Cache_hash_code
>
323 operator!=(const _Node_iterator_base
<_Value
, _Cache_hash_code
>& __x
,
324 const _Node_iterator_base
<_Value
, _Cache_hash_code
>& __y
)
325 { return __x
._M_cur
!= __y
._M_cur
; }
327 /// Node iterators, used to iterate through all the hashtable.
328 template<typename _Value
, bool __constant_iterators
, bool __cache
>
329 struct _Node_iterator
330 : public _Node_iterator_base
<_Value
, __cache
>
333 using __base_type
= _Node_iterator_base
<_Value
, __cache
>;
334 using __node_type
= typename
__base_type::__node_type
;
337 typedef _Value value_type
;
338 typedef std::ptrdiff_t difference_type
;
339 typedef std::forward_iterator_tag iterator_category
;
341 using pointer
= typename
std::conditional
<__constant_iterators
,
342 const _Value
*, _Value
*>::type
;
344 using reference
= typename
std::conditional
<__constant_iterators
,
345 const _Value
&, _Value
&>::type
;
351 _Node_iterator(__node_type
* __p
)
352 : __base_type(__p
) { }
356 { return this->_M_cur
->_M_v(); }
360 { return this->_M_cur
->_M_valptr(); }
372 _Node_iterator
__tmp(*this);
378 /// Node const_iterators, used to iterate through all the hashtable.
379 template<typename _Value
, bool __constant_iterators
, bool __cache
>
380 struct _Node_const_iterator
381 : public _Node_iterator_base
<_Value
, __cache
>
384 using __base_type
= _Node_iterator_base
<_Value
, __cache
>;
385 using __node_type
= typename
__base_type::__node_type
;
388 typedef _Value value_type
;
389 typedef std::ptrdiff_t difference_type
;
390 typedef std::forward_iterator_tag iterator_category
;
392 typedef const _Value
* pointer
;
393 typedef const _Value
& reference
;
395 _Node_const_iterator()
399 _Node_const_iterator(__node_type
* __p
)
400 : __base_type(__p
) { }
402 _Node_const_iterator(const _Node_iterator
<_Value
, __constant_iterators
,
404 : __base_type(__x
._M_cur
) { }
408 { return this->_M_cur
->_M_v(); }
412 { return this->_M_cur
->_M_valptr(); }
414 _Node_const_iterator
&
424 _Node_const_iterator
__tmp(*this);
430 // Many of class template _Hashtable's template parameters are policy
431 // classes. These are defaults for the policies.
433 /// Default range hashing function: use division to fold a large number
434 /// into the range [0, N).
435 struct _Mod_range_hashing
437 typedef std::size_t first_argument_type
;
438 typedef std::size_t second_argument_type
;
439 typedef std::size_t result_type
;
442 operator()(first_argument_type __num
,
443 second_argument_type __den
) const noexcept
444 { return __num
% __den
; }
447 /// Default ranged hash function H. In principle it should be a
448 /// function object composed from objects of type H1 and H2 such that
449 /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of
450 /// h1 and h2. So instead we'll just use a tag to tell class template
451 /// hashtable to do that composition.
452 struct _Default_ranged_hash
{ };
454 /// Default value for rehash policy. Bucket size is (usually) the
455 /// smallest prime that keeps the load factor small enough.
456 struct _Prime_rehash_policy
458 _Prime_rehash_policy(float __z
= 1.0)
459 : _M_max_load_factor(__z
), _M_next_resize(0) { }
462 max_load_factor() const noexcept
463 { return _M_max_load_factor
; }
465 // Return a bucket size no smaller than n.
467 _M_next_bkt(std::size_t __n
) const;
469 // Return a bucket count appropriate for n elements
471 _M_bkt_for_elements(std::size_t __n
) const
472 { return __builtin_ceil(__n
/ (long double)_M_max_load_factor
); }
474 // __n_bkt is current bucket count, __n_elt is current element count,
475 // and __n_ins is number of elements to be inserted. Do we need to
476 // increase bucket count? If so, return make_pair(true, n), where n
477 // is the new bucket count. If not, return make_pair(false, 0).
478 std::pair
<bool, std::size_t>
479 _M_need_rehash(std::size_t __n_bkt
, std::size_t __n_elt
,
480 std::size_t __n_ins
) const;
482 typedef std::size_t _State
;
486 { return _M_next_resize
; }
490 { _M_next_resize
= 0; }
493 _M_reset(_State __state
)
494 { _M_next_resize
= __state
; }
496 enum { _S_n_primes
= sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
498 static const std::size_t _S_growth_factor
= 2;
500 float _M_max_load_factor
;
501 mutable std::size_t _M_next_resize
;
504 // Base classes for std::_Hashtable. We define these base classes
505 // because in some cases we want to do different things depending on
506 // the value of a policy class. In some cases the policy class
507 // affects which member functions and nested typedefs are defined;
508 // we handle that by specializing base class templates. Several of
509 // the base class templates need to access other members of class
510 // template _Hashtable, so we use a variant of the "Curiously
511 // Recurring Template Pattern" (CRTP) technique.
514 * Primary class template _Map_base.
516 * If the hashtable has a value type of the form pair<T1, T2> and a
517 * key extraction policy (_ExtractKey) that returns the first part
518 * of the pair, the hashtable gets a mapped_type typedef. If it
519 * satisfies those criteria and also has unique keys, then it also
520 * gets an operator[].
522 template<typename _Key
, typename _Value
, typename _Alloc
,
523 typename _ExtractKey
, typename _Equal
,
524 typename _H1
, typename _H2
, typename _Hash
,
525 typename _RehashPolicy
, typename _Traits
,
526 bool _Unique_keys
= _Traits::__unique_keys::value
>
527 struct _Map_base
{ };
529 /// Partial specialization, __unique_keys set to false.
530 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
531 typename _H1
, typename _H2
, typename _Hash
,
532 typename _RehashPolicy
, typename _Traits
>
533 struct _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
534 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, false>
536 using mapped_type
= typename
std::tuple_element
<1, _Pair
>::type
;
539 /// Partial specialization, __unique_keys set to true.
540 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
541 typename _H1
, typename _H2
, typename _Hash
,
542 typename _RehashPolicy
, typename _Traits
>
543 struct _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
544 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>
547 using __hashtable_base
= __detail::_Hashtable_base
<_Key
, _Pair
,
549 _Equal
, _H1
, _H2
, _Hash
,
552 using __hashtable
= _Hashtable
<_Key
, _Pair
, _Alloc
,
554 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>;
556 using __hash_code
= typename
__hashtable_base::__hash_code
;
557 using __node_type
= typename
__hashtable_base::__node_type
;
560 using key_type
= typename
__hashtable_base::key_type
;
561 using iterator
= typename
__hashtable_base::iterator
;
562 using mapped_type
= typename
std::tuple_element
<1, _Pair
>::type
;
565 operator[](const key_type
& __k
);
568 operator[](key_type
&& __k
);
570 // _GLIBCXX_RESOLVE_LIB_DEFECTS
571 // DR 761. unordered_map needs an at() member function.
573 at(const key_type
& __k
);
576 at(const key_type
& __k
) const;
579 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
580 typename _H1
, typename _H2
, typename _Hash
,
581 typename _RehashPolicy
, typename _Traits
>
582 typename _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
583 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>
585 _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
586 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>::
587 operator[](const key_type
& __k
)
589 __hashtable
* __h
= static_cast<__hashtable
*>(this);
590 __hash_code __code
= __h
->_M_hash_code(__k
);
591 std::size_t __n
= __h
->_M_bucket_index(__k
, __code
);
592 __node_type
* __p
= __h
->_M_find_node(__n
, __k
, __code
);
596 __p
= __h
->_M_allocate_node(std::piecewise_construct
,
597 std::tuple
<const key_type
&>(__k
),
599 return __h
->_M_insert_unique_node(__n
, __code
, __p
)->second
;
602 return __p
->_M_v().second
;
605 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
606 typename _H1
, typename _H2
, typename _Hash
,
607 typename _RehashPolicy
, typename _Traits
>
608 typename _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
609 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>
611 _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
612 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>::
613 operator[](key_type
&& __k
)
615 __hashtable
* __h
= static_cast<__hashtable
*>(this);
616 __hash_code __code
= __h
->_M_hash_code(__k
);
617 std::size_t __n
= __h
->_M_bucket_index(__k
, __code
);
618 __node_type
* __p
= __h
->_M_find_node(__n
, __k
, __code
);
622 __p
= __h
->_M_allocate_node(std::piecewise_construct
,
623 std::forward_as_tuple(std::move(__k
)),
625 return __h
->_M_insert_unique_node(__n
, __code
, __p
)->second
;
628 return __p
->_M_v().second
;
631 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
632 typename _H1
, typename _H2
, typename _Hash
,
633 typename _RehashPolicy
, typename _Traits
>
634 typename _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
635 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>
637 _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
638 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>::
639 at(const key_type
& __k
)
641 __hashtable
* __h
= static_cast<__hashtable
*>(this);
642 __hash_code __code
= __h
->_M_hash_code(__k
);
643 std::size_t __n
= __h
->_M_bucket_index(__k
, __code
);
644 __node_type
* __p
= __h
->_M_find_node(__n
, __k
, __code
);
647 __throw_out_of_range(__N("_Map_base::at"));
648 return __p
->_M_v().second
;
651 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
652 typename _H1
, typename _H2
, typename _Hash
,
653 typename _RehashPolicy
, typename _Traits
>
654 const typename _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
,
655 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
656 _Traits
, true>::mapped_type
&
657 _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
658 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>::
659 at(const key_type
& __k
) const
661 const __hashtable
* __h
= static_cast<const __hashtable
*>(this);
662 __hash_code __code
= __h
->_M_hash_code(__k
);
663 std::size_t __n
= __h
->_M_bucket_index(__k
, __code
);
664 __node_type
* __p
= __h
->_M_find_node(__n
, __k
, __code
);
667 __throw_out_of_range(__N("_Map_base::at"));
668 return __p
->_M_v().second
;
672 * Primary class template _Insert_base.
674 * insert member functions appropriate to all _Hashtables.
676 template<typename _Key
, typename _Value
, typename _Alloc
,
677 typename _ExtractKey
, typename _Equal
,
678 typename _H1
, typename _H2
, typename _Hash
,
679 typename _RehashPolicy
, typename _Traits
>
683 using __hashtable
= _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
684 _Equal
, _H1
, _H2
, _Hash
,
685 _RehashPolicy
, _Traits
>;
687 using __hashtable_base
= _Hashtable_base
<_Key
, _Value
, _ExtractKey
,
688 _Equal
, _H1
, _H2
, _Hash
,
691 using value_type
= typename
__hashtable_base::value_type
;
692 using iterator
= typename
__hashtable_base::iterator
;
693 using const_iterator
= typename
__hashtable_base::const_iterator
;
694 using size_type
= typename
__hashtable_base::size_type
;
696 using __unique_keys
= typename
__hashtable_base::__unique_keys
;
697 using __ireturn_type
= typename
__hashtable_base::__ireturn_type
;
698 using __node_type
= _Hash_node
<_Value
, _Traits::__hash_cached::value
>;
699 using __node_alloc_type
=
700 typename __alloctr_rebind
<_Alloc
, __node_type
>::__type
;
701 using __node_gen_type
= _AllocNode
<__node_alloc_type
>;
704 _M_conjure_hashtable()
705 { return *(static_cast<__hashtable
*>(this)); }
707 template<typename _InputIterator
, typename _NodeGetter
>
709 _M_insert_range(_InputIterator __first
, _InputIterator __last
,
714 insert(const value_type
& __v
)
716 __hashtable
& __h
= _M_conjure_hashtable();
717 __node_gen_type
__node_gen(__h
);
718 return __h
._M_insert(__v
, __node_gen
, __unique_keys());
722 insert(const_iterator __hint
, const value_type
& __v
)
724 __hashtable
& __h
= _M_conjure_hashtable();
725 __node_gen_type
__node_gen(__h
);
726 return __h
._M_insert(__hint
, __v
, __node_gen
, __unique_keys());
730 insert(initializer_list
<value_type
> __l
)
731 { this->insert(__l
.begin(), __l
.end()); }
733 template<typename _InputIterator
>
735 insert(_InputIterator __first
, _InputIterator __last
)
737 __hashtable
& __h
= _M_conjure_hashtable();
738 __node_gen_type
__node_gen(__h
);
739 return _M_insert_range(__first
, __last
, __node_gen
);
743 template<typename _Key
, typename _Value
, typename _Alloc
,
744 typename _ExtractKey
, typename _Equal
,
745 typename _H1
, typename _H2
, typename _Hash
,
746 typename _RehashPolicy
, typename _Traits
>
747 template<typename _InputIterator
, typename _NodeGetter
>
749 _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
, _H1
, _H2
, _Hash
,
750 _RehashPolicy
, _Traits
>::
751 _M_insert_range(_InputIterator __first
, _InputIterator __last
,
752 const _NodeGetter
& __node_gen
)
754 using __rehash_type
= typename
__hashtable::__rehash_type
;
755 using __rehash_state
= typename
__hashtable::__rehash_state
;
756 using pair_type
= std::pair
<bool, std::size_t>;
758 size_type __n_elt
= __detail::__distance_fw(__first
, __last
);
760 __hashtable
& __h
= _M_conjure_hashtable();
761 __rehash_type
& __rehash
= __h
._M_rehash_policy
;
762 const __rehash_state
& __saved_state
= __rehash
._M_state();
763 pair_type __do_rehash
= __rehash
._M_need_rehash(__h
._M_bucket_count
,
764 __h
._M_element_count
,
767 if (__do_rehash
.first
)
768 __h
._M_rehash(__do_rehash
.second
, __saved_state
);
770 for (; __first
!= __last
; ++__first
)
771 __h
._M_insert(*__first
, __node_gen
, __unique_keys());
775 * Primary class template _Insert.
777 * Select insert member functions appropriate to _Hashtable policy choices.
779 template<typename _Key
, typename _Value
, typename _Alloc
,
780 typename _ExtractKey
, typename _Equal
,
781 typename _H1
, typename _H2
, typename _Hash
,
782 typename _RehashPolicy
, typename _Traits
,
783 bool _Constant_iterators
= _Traits::__constant_iterators::value
,
784 bool _Unique_keys
= _Traits::__unique_keys::value
>
788 template<typename _Key
, typename _Value
, typename _Alloc
,
789 typename _ExtractKey
, typename _Equal
,
790 typename _H1
, typename _H2
, typename _Hash
,
791 typename _RehashPolicy
, typename _Traits
>
792 struct _Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
, _H1
, _H2
, _Hash
,
793 _RehashPolicy
, _Traits
, true, true>
794 : public _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
795 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>
797 using __base_type
= _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
798 _Equal
, _H1
, _H2
, _Hash
,
799 _RehashPolicy
, _Traits
>;
800 using value_type
= typename
__base_type::value_type
;
801 using iterator
= typename
__base_type::iterator
;
802 using const_iterator
= typename
__base_type::const_iterator
;
804 using __unique_keys
= typename
__base_type::__unique_keys
;
805 using __hashtable
= typename
__base_type::__hashtable
;
806 using __node_gen_type
= typename
__base_type::__node_gen_type
;
808 using __base_type::insert
;
810 std::pair
<iterator
, bool>
811 insert(value_type
&& __v
)
813 __hashtable
& __h
= this->_M_conjure_hashtable();
814 __node_gen_type
__node_gen(__h
);
815 return __h
._M_insert(std::move(__v
), __node_gen
, __unique_keys());
819 insert(const_iterator __hint
, value_type
&& __v
)
821 __hashtable
& __h
= this->_M_conjure_hashtable();
822 __node_gen_type
__node_gen(__h
);
823 return __h
._M_insert(__hint
, std::move(__v
), __node_gen
,
829 template<typename _Key
, typename _Value
, typename _Alloc
,
830 typename _ExtractKey
, typename _Equal
,
831 typename _H1
, typename _H2
, typename _Hash
,
832 typename _RehashPolicy
, typename _Traits
>
833 struct _Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
, _H1
, _H2
, _Hash
,
834 _RehashPolicy
, _Traits
, true, false>
835 : public _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
836 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>
838 using __base_type
= _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
839 _Equal
, _H1
, _H2
, _Hash
,
840 _RehashPolicy
, _Traits
>;
841 using value_type
= typename
__base_type::value_type
;
842 using iterator
= typename
__base_type::iterator
;
843 using const_iterator
= typename
__base_type::const_iterator
;
845 using __unique_keys
= typename
__base_type::__unique_keys
;
846 using __hashtable
= typename
__base_type::__hashtable
;
847 using __node_gen_type
= typename
__base_type::__node_gen_type
;
849 using __base_type::insert
;
852 insert(value_type
&& __v
)
854 __hashtable
& __h
= this->_M_conjure_hashtable();
855 __node_gen_type
__node_gen(__h
);
856 return __h
._M_insert(std::move(__v
), __node_gen
, __unique_keys());
860 insert(const_iterator __hint
, value_type
&& __v
)
862 __hashtable
& __h
= this->_M_conjure_hashtable();
863 __node_gen_type
__node_gen(__h
);
864 return __h
._M_insert(__hint
, std::move(__v
), __node_gen
,
870 template<typename _Key
, typename _Value
, typename _Alloc
,
871 typename _ExtractKey
, typename _Equal
,
872 typename _H1
, typename _H2
, typename _Hash
,
873 typename _RehashPolicy
, typename _Traits
, bool _Unique_keys
>
874 struct _Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
, _H1
, _H2
, _Hash
,
875 _RehashPolicy
, _Traits
, false, _Unique_keys
>
876 : public _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
877 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>
879 using __base_type
= _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
880 _Equal
, _H1
, _H2
, _Hash
,
881 _RehashPolicy
, _Traits
>;
882 using value_type
= typename
__base_type::value_type
;
883 using iterator
= typename
__base_type::iterator
;
884 using const_iterator
= typename
__base_type::const_iterator
;
886 using __unique_keys
= typename
__base_type::__unique_keys
;
887 using __hashtable
= typename
__base_type::__hashtable
;
888 using __ireturn_type
= typename
__base_type::__ireturn_type
;
890 using __base_type::insert
;
892 template<typename _Pair
>
893 using __is_cons
= std::is_constructible
<value_type
, _Pair
&&>;
895 template<typename _Pair
>
896 using _IFcons
= std::enable_if
<__is_cons
<_Pair
>::value
>;
898 template<typename _Pair
>
899 using _IFconsp
= typename _IFcons
<_Pair
>::type
;
901 template<typename _Pair
, typename
= _IFconsp
<_Pair
>>
905 __hashtable
& __h
= this->_M_conjure_hashtable();
906 return __h
._M_emplace(__unique_keys(), std::forward
<_Pair
>(__v
));
909 template<typename _Pair
, typename
= _IFconsp
<_Pair
>>
911 insert(const_iterator __hint
, _Pair
&& __v
)
913 __hashtable
& __h
= this->_M_conjure_hashtable();
914 return __h
._M_emplace(__hint
, __unique_keys(),
915 std::forward
<_Pair
>(__v
));
920 * Primary class template _Rehash_base.
922 * Give hashtable the max_load_factor functions and reserve iff the
923 * rehash policy is _Prime_rehash_policy.
925 template<typename _Key
, typename _Value
, typename _Alloc
,
926 typename _ExtractKey
, typename _Equal
,
927 typename _H1
, typename _H2
, typename _Hash
,
928 typename _RehashPolicy
, typename _Traits
>
932 template<typename _Key
, typename _Value
, typename _Alloc
,
933 typename _ExtractKey
, typename _Equal
,
934 typename _H1
, typename _H2
, typename _Hash
, typename _Traits
>
935 struct _Rehash_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
936 _H1
, _H2
, _Hash
, _Prime_rehash_policy
, _Traits
>
938 using __hashtable
= _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
939 _Equal
, _H1
, _H2
, _Hash
,
940 _Prime_rehash_policy
, _Traits
>;
943 max_load_factor() const noexcept
945 const __hashtable
* __this
= static_cast<const __hashtable
*>(this);
946 return __this
->__rehash_policy().max_load_factor();
950 max_load_factor(float __z
)
952 __hashtable
* __this
= static_cast<__hashtable
*>(this);
953 __this
->__rehash_policy(_Prime_rehash_policy(__z
));
957 reserve(std::size_t __n
)
959 __hashtable
* __this
= static_cast<__hashtable
*>(this);
960 __this
->rehash(__builtin_ceil(__n
/ max_load_factor()));
965 * Primary class template _Hashtable_ebo_helper.
967 * Helper class using EBO when it is not forbidden (the type is not
968 * final) and when it is worth it (the type is empty.)
970 template<int _Nm
, typename _Tp
,
971 bool __use_ebo
= !__is_final(_Tp
) && __is_empty(_Tp
)>
972 struct _Hashtable_ebo_helper
;
974 /// Specialization using EBO.
975 template<int _Nm
, typename _Tp
>
976 struct _Hashtable_ebo_helper
<_Nm
, _Tp
, true>
979 _Hashtable_ebo_helper() = default;
981 template<typename _OtherTp
>
982 _Hashtable_ebo_helper(_OtherTp
&& __tp
)
983 : _Tp(std::forward
<_OtherTp
>(__tp
))
987 _S_cget(const _Hashtable_ebo_helper
& __eboh
)
988 { return static_cast<const _Tp
&>(__eboh
); }
991 _S_get(_Hashtable_ebo_helper
& __eboh
)
992 { return static_cast<_Tp
&>(__eboh
); }
995 /// Specialization not using EBO.
996 template<int _Nm
, typename _Tp
>
997 struct _Hashtable_ebo_helper
<_Nm
, _Tp
, false>
999 _Hashtable_ebo_helper() = default;
1001 template<typename _OtherTp
>
1002 _Hashtable_ebo_helper(_OtherTp
&& __tp
)
1003 : _M_tp(std::forward
<_OtherTp
>(__tp
))
1007 _S_cget(const _Hashtable_ebo_helper
& __eboh
)
1008 { return __eboh
._M_tp
; }
1011 _S_get(_Hashtable_ebo_helper
& __eboh
)
1012 { return __eboh
._M_tp
; }
1019 * Primary class template _Local_iterator_base.
1021 * Base class for local iterators, used to iterate within a bucket
1022 * but not between buckets.
1024 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1025 typename _H1
, typename _H2
, typename _Hash
,
1026 bool __cache_hash_code
>
1027 struct _Local_iterator_base
;
1030 * Primary class template _Hash_code_base.
1032 * Encapsulates two policy issues that aren't quite orthogonal.
1033 * (1) the difference between using a ranged hash function and using
1034 * the combination of a hash function and a range-hashing function.
1035 * In the former case we don't have such things as hash codes, so
1036 * we have a dummy type as placeholder.
1037 * (2) Whether or not we cache hash codes. Caching hash codes is
1038 * meaningless if we have a ranged hash function.
1040 * We also put the key extraction objects here, for convenience.
1041 * Each specialization derives from one or more of the template
1042 * parameters to benefit from Ebo. This is important as this type
1043 * is inherited in some cases by the _Local_iterator_base type used
1044 * to implement local_iterator and const_local_iterator. As with
1045 * any iterator type we prefer to make it as small as possible.
1047 * Primary template is unused except as a hook for specializations.
1049 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1050 typename _H1
, typename _H2
, typename _Hash
,
1051 bool __cache_hash_code
>
1052 struct _Hash_code_base
;
1054 /// Specialization: ranged hash function, no caching hash codes. H1
1055 /// and H2 are provided but ignored. We define a dummy hash code type.
1056 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1057 typename _H1
, typename _H2
, typename _Hash
>
1058 struct _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
, _Hash
, false>
1059 : private _Hashtable_ebo_helper
<0, _ExtractKey
>,
1060 private _Hashtable_ebo_helper
<1, _Hash
>
1063 using __ebo_extract_key
= _Hashtable_ebo_helper
<0, _ExtractKey
>;
1064 using __ebo_hash
= _Hashtable_ebo_helper
<1, _Hash
>;
1067 typedef void* __hash_code
;
1068 typedef _Hash_node
<_Value
, false> __node_type
;
1070 // We need the default constructor for the local iterators.
1071 _Hash_code_base() = default;
1073 _Hash_code_base(const _ExtractKey
& __ex
, const _H1
&, const _H2
&,
1075 : __ebo_extract_key(__ex
), __ebo_hash(__h
) { }
1078 _M_hash_code(const _Key
& __key
) const
1082 _M_bucket_index(const _Key
& __k
, __hash_code
, std::size_t __n
) const
1083 { return _M_ranged_hash()(__k
, __n
); }
1086 _M_bucket_index(const __node_type
* __p
, std::size_t __n
) const
1087 noexcept( noexcept(declval
<const _Hash
&>()(declval
<const _Key
&>(), (std::size_t)0)) )
1088 { return _M_ranged_hash()(_M_extract()(__p
->_M_v()), __n
); }
1091 _M_store_code(__node_type
*, __hash_code
) const
1095 _M_copy_code(__node_type
*, const __node_type
*) const
1099 _M_swap(_Hash_code_base
& __x
)
1101 std::swap(_M_extract(), __x
._M_extract());
1102 std::swap(_M_ranged_hash(), __x
._M_ranged_hash());
1106 _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1109 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1112 _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); }
1115 _M_ranged_hash() { return __ebo_hash::_S_get(*this); }
1118 // No specialization for ranged hash function while caching hash codes.
1119 // That combination is meaningless, and trying to do it is an error.
1121 /// Specialization: ranged hash function, cache hash codes. This
1122 /// combination is meaningless, so we provide only a declaration
1123 /// and no definition.
1124 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1125 typename _H1
, typename _H2
, typename _Hash
>
1126 struct _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
, _Hash
, true>;
1128 /// Specialization: hash function and range-hashing function, no
1129 /// caching of hash codes.
1130 /// Provides typedef and accessor required by C++ 11.
1131 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1132 typename _H1
, typename _H2
>
1133 struct _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
,
1134 _Default_ranged_hash
, false>
1135 : private _Hashtable_ebo_helper
<0, _ExtractKey
>,
1136 private _Hashtable_ebo_helper
<1, _H1
>,
1137 private _Hashtable_ebo_helper
<2, _H2
>
1140 using __ebo_extract_key
= _Hashtable_ebo_helper
<0, _ExtractKey
>;
1141 using __ebo_h1
= _Hashtable_ebo_helper
<1, _H1
>;
1142 using __ebo_h2
= _Hashtable_ebo_helper
<2, _H2
>;
1148 hash_function() const
1152 typedef std::size_t __hash_code
;
1153 typedef _Hash_node
<_Value
, false> __node_type
;
1155 // We need the default constructor for the local iterators.
1156 _Hash_code_base() = default;
1158 _Hash_code_base(const _ExtractKey
& __ex
,
1159 const _H1
& __h1
, const _H2
& __h2
,
1160 const _Default_ranged_hash
&)
1161 : __ebo_extract_key(__ex
), __ebo_h1(__h1
), __ebo_h2(__h2
) { }
1164 _M_hash_code(const _Key
& __k
) const
1165 { return _M_h1()(__k
); }
1168 _M_bucket_index(const _Key
&, __hash_code __c
, std::size_t __n
) const
1169 { return _M_h2()(__c
, __n
); }
1172 _M_bucket_index(const __node_type
* __p
, std::size_t __n
) const
1173 noexcept( noexcept(declval
<const _H1
&>()(declval
<const _Key
&>()))
1174 && noexcept(declval
<const _H2
&>()((__hash_code
)0, (std::size_t)0)) )
1175 { return _M_h2()(_M_h1()(_M_extract()(__p
->_M_v())), __n
); }
1178 _M_store_code(__node_type
*, __hash_code
) const
1182 _M_copy_code(__node_type
*, const __node_type
*) const
1186 _M_swap(_Hash_code_base
& __x
)
1188 std::swap(_M_extract(), __x
._M_extract());
1189 std::swap(_M_h1(), __x
._M_h1());
1190 std::swap(_M_h2(), __x
._M_h2());
1194 _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1197 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1200 _M_h1() const { return __ebo_h1::_S_cget(*this); }
1203 _M_h1() { return __ebo_h1::_S_get(*this); }
1206 _M_h2() const { return __ebo_h2::_S_cget(*this); }
1209 _M_h2() { return __ebo_h2::_S_get(*this); }
1212 /// Specialization: hash function and range-hashing function,
1213 /// caching hash codes. H is provided but ignored. Provides
1214 /// typedef and accessor required by C++ 11.
1215 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1216 typename _H1
, typename _H2
>
1217 struct _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
,
1218 _Default_ranged_hash
, true>
1219 : private _Hashtable_ebo_helper
<0, _ExtractKey
>,
1220 private _Hashtable_ebo_helper
<1, _H1
>,
1221 private _Hashtable_ebo_helper
<2, _H2
>
1224 // Gives access to _M_h2() to the local iterator implementation.
1225 friend struct _Local_iterator_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
,
1226 _Default_ranged_hash
, true>;
1228 using __ebo_extract_key
= _Hashtable_ebo_helper
<0, _ExtractKey
>;
1229 using __ebo_h1
= _Hashtable_ebo_helper
<1, _H1
>;
1230 using __ebo_h2
= _Hashtable_ebo_helper
<2, _H2
>;
1236 hash_function() const
1240 typedef std::size_t __hash_code
;
1241 typedef _Hash_node
<_Value
, true> __node_type
;
1243 _Hash_code_base(const _ExtractKey
& __ex
,
1244 const _H1
& __h1
, const _H2
& __h2
,
1245 const _Default_ranged_hash
&)
1246 : __ebo_extract_key(__ex
), __ebo_h1(__h1
), __ebo_h2(__h2
) { }
1249 _M_hash_code(const _Key
& __k
) const
1250 { return _M_h1()(__k
); }
1253 _M_bucket_index(const _Key
&, __hash_code __c
,
1254 std::size_t __n
) const
1255 { return _M_h2()(__c
, __n
); }
1258 _M_bucket_index(const __node_type
* __p
, std::size_t __n
) const
1259 noexcept( noexcept(declval
<const _H2
&>()((__hash_code
)0,
1261 { return _M_h2()(__p
->_M_hash_code
, __n
); }
1264 _M_store_code(__node_type
* __n
, __hash_code __c
) const
1265 { __n
->_M_hash_code
= __c
; }
1268 _M_copy_code(__node_type
* __to
, const __node_type
* __from
) const
1269 { __to
->_M_hash_code
= __from
->_M_hash_code
; }
1272 _M_swap(_Hash_code_base
& __x
)
1274 std::swap(_M_extract(), __x
._M_extract());
1275 std::swap(_M_h1(), __x
._M_h1());
1276 std::swap(_M_h2(), __x
._M_h2());
1280 _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1283 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1286 _M_h1() const { return __ebo_h1::_S_cget(*this); }
1289 _M_h1() { return __ebo_h1::_S_get(*this); }
1292 _M_h2() const { return __ebo_h2::_S_cget(*this); }
1295 _M_h2() { return __ebo_h2::_S_get(*this); }
1299 * Primary class template _Equal_helper.
1302 template <typename _Key
, typename _Value
, typename _ExtractKey
,
1303 typename _Equal
, typename _HashCodeType
,
1304 bool __cache_hash_code
>
1305 struct _Equal_helper
;
1308 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1309 typename _Equal
, typename _HashCodeType
>
1310 struct _Equal_helper
<_Key
, _Value
, _ExtractKey
, _Equal
, _HashCodeType
, true>
1313 _S_equals(const _Equal
& __eq
, const _ExtractKey
& __extract
,
1314 const _Key
& __k
, _HashCodeType __c
, _Hash_node
<_Value
, true>* __n
)
1315 { return __c
== __n
->_M_hash_code
&& __eq(__k
, __extract(__n
->_M_v())); }
1319 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1320 typename _Equal
, typename _HashCodeType
>
1321 struct _Equal_helper
<_Key
, _Value
, _ExtractKey
, _Equal
, _HashCodeType
, false>
1324 _S_equals(const _Equal
& __eq
, const _ExtractKey
& __extract
,
1325 const _Key
& __k
, _HashCodeType
, _Hash_node
<_Value
, false>* __n
)
1326 { return __eq(__k
, __extract(__n
->_M_v())); }
1331 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1332 typename _H1
, typename _H2
, typename _Hash
>
1333 struct _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1334 _H1
, _H2
, _Hash
, true>
1335 : private _Hashtable_ebo_helper
<0, _H2
>
1338 using __base_type
= _Hashtable_ebo_helper
<0, _H2
>;
1339 using __hash_code_base
= _Hash_code_base
<_Key
, _Value
, _ExtractKey
,
1340 _H1
, _H2
, _Hash
, true>;
1343 _Local_iterator_base() = default;
1344 _Local_iterator_base(const __hash_code_base
& __base
,
1345 _Hash_node
<_Value
, true>* __p
,
1346 std::size_t __bkt
, std::size_t __bkt_count
)
1347 : __base_type(__base
._M_h2()),
1348 _M_cur(__p
), _M_bucket(__bkt
), _M_bucket_count(__bkt_count
) { }
1353 _M_cur
= _M_cur
->_M_next();
1357 = __base_type::_S_get(*this)(_M_cur
->_M_hash_code
,
1359 if (__bkt
!= _M_bucket
)
1364 _Hash_node
<_Value
, true>* _M_cur
;
1365 std::size_t _M_bucket
;
1366 std::size_t _M_bucket_count
;
1370 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1371 typename _H1
, typename _H2
, typename _Hash
>
1372 struct _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1373 _H1
, _H2
, _Hash
, false>
1374 : private _Hash_code_base
<_Key
, _Value
, _ExtractKey
,
1375 _H1
, _H2
, _Hash
, false>
1378 using __hash_code_base
= _Hash_code_base
<_Key
, _Value
, _ExtractKey
,
1379 _H1
, _H2
, _Hash
, false>;
1382 _Local_iterator_base() = default;
1383 _Local_iterator_base(const __hash_code_base
& __base
,
1384 _Hash_node
<_Value
, false>* __p
,
1385 std::size_t __bkt
, std::size_t __bkt_count
)
1386 : __hash_code_base(__base
),
1387 _M_cur(__p
), _M_bucket(__bkt
), _M_bucket_count(__bkt_count
) { }
1392 _M_cur
= _M_cur
->_M_next();
1395 std::size_t __bkt
= this->_M_bucket_index(_M_cur
, _M_bucket_count
);
1396 if (__bkt
!= _M_bucket
)
1401 _Hash_node
<_Value
, false>* _M_cur
;
1402 std::size_t _M_bucket
;
1403 std::size_t _M_bucket_count
;
1406 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1407 typename _H1
, typename _H2
, typename _Hash
, bool __cache
>
1409 operator==(const _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1410 _H1
, _H2
, _Hash
, __cache
>& __x
,
1411 const _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1412 _H1
, _H2
, _Hash
, __cache
>& __y
)
1413 { return __x
._M_cur
== __y
._M_cur
; }
1415 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1416 typename _H1
, typename _H2
, typename _Hash
, bool __cache
>
1418 operator!=(const _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1419 _H1
, _H2
, _Hash
, __cache
>& __x
,
1420 const _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1421 _H1
, _H2
, _Hash
, __cache
>& __y
)
1422 { return __x
._M_cur
!= __y
._M_cur
; }
1425 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1426 typename _H1
, typename _H2
, typename _Hash
,
1427 bool __constant_iterators
, bool __cache
>
1428 struct _Local_iterator
1429 : public _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1430 _H1
, _H2
, _Hash
, __cache
>
1433 using __base_type
= _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1434 _H1
, _H2
, _Hash
, __cache
>;
1435 using __hash_code_base
= typename
__base_type::__hash_code_base
;
1437 typedef _Value value_type
;
1438 typedef typename
std::conditional
<__constant_iterators
,
1439 const _Value
*, _Value
*>::type
1441 typedef typename
std::conditional
<__constant_iterators
,
1442 const _Value
&, _Value
&>::type
1444 typedef std::ptrdiff_t difference_type
;
1445 typedef std::forward_iterator_tag iterator_category
;
1447 _Local_iterator() = default;
1449 _Local_iterator(const __hash_code_base
& __base
,
1450 _Hash_node
<_Value
, __cache
>* __p
,
1451 std::size_t __bkt
, std::size_t __bkt_count
)
1452 : __base_type(__base
, __p
, __bkt
, __bkt_count
)
1457 { return this->_M_cur
->_M_v(); }
1461 { return this->_M_cur
->_M_valptr(); }
1473 _Local_iterator
__tmp(*this);
1479 /// local const_iterators
1480 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1481 typename _H1
, typename _H2
, typename _Hash
,
1482 bool __constant_iterators
, bool __cache
>
1483 struct _Local_const_iterator
1484 : public _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1485 _H1
, _H2
, _Hash
, __cache
>
1488 using __base_type
= _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1489 _H1
, _H2
, _Hash
, __cache
>;
1490 using __hash_code_base
= typename
__base_type::__hash_code_base
;
1493 typedef _Value value_type
;
1494 typedef const _Value
* pointer
;
1495 typedef const _Value
& reference
;
1496 typedef std::ptrdiff_t difference_type
;
1497 typedef std::forward_iterator_tag iterator_category
;
1499 _Local_const_iterator() = default;
1501 _Local_const_iterator(const __hash_code_base
& __base
,
1502 _Hash_node
<_Value
, __cache
>* __p
,
1503 std::size_t __bkt
, std::size_t __bkt_count
)
1504 : __base_type(__base
, __p
, __bkt
, __bkt_count
)
1507 _Local_const_iterator(const _Local_iterator
<_Key
, _Value
, _ExtractKey
,
1509 __constant_iterators
,
1516 { return this->_M_cur
->_M_v(); }
1520 { return this->_M_cur
->_M_valptr(); }
1522 _Local_const_iterator
&
1529 _Local_const_iterator
1532 _Local_const_iterator
__tmp(*this);
1539 * Primary class template _Hashtable_base.
1541 * Helper class adding management of _Equal functor to
1542 * _Hash_code_base type.
1544 * Base class templates are:
1545 * - __detail::_Hash_code_base
1546 * - __detail::_Hashtable_ebo_helper
1548 template<typename _Key
, typename _Value
,
1549 typename _ExtractKey
, typename _Equal
,
1550 typename _H1
, typename _H2
, typename _Hash
, typename _Traits
>
1551 struct _Hashtable_base
1552 : public _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
, _Hash
,
1553 _Traits::__hash_cached::value
>,
1554 private _Hashtable_ebo_helper
<0, _Equal
>
1557 typedef _Key key_type
;
1558 typedef _Value value_type
;
1559 typedef _Equal key_equal
;
1560 typedef std::size_t size_type
;
1561 typedef std::ptrdiff_t difference_type
;
1563 using __traits_type
= _Traits
;
1564 using __hash_cached
= typename
__traits_type::__hash_cached
;
1565 using __constant_iterators
= typename
__traits_type::__constant_iterators
;
1566 using __unique_keys
= typename
__traits_type::__unique_keys
;
1568 using __hash_code_base
= _Hash_code_base
<_Key
, _Value
, _ExtractKey
,
1570 __hash_cached::value
>;
1572 using __hash_code
= typename
__hash_code_base::__hash_code
;
1573 using __node_type
= typename
__hash_code_base::__node_type
;
1575 using iterator
= __detail::_Node_iterator
<value_type
,
1576 __constant_iterators::value
,
1577 __hash_cached::value
>;
1579 using const_iterator
= __detail::_Node_const_iterator
<value_type
,
1580 __constant_iterators::value
,
1581 __hash_cached::value
>;
1583 using local_iterator
= __detail::_Local_iterator
<key_type
, value_type
,
1584 _ExtractKey
, _H1
, _H2
, _Hash
,
1585 __constant_iterators::value
,
1586 __hash_cached::value
>;
1588 using const_local_iterator
= __detail::_Local_const_iterator
<key_type
,
1590 _ExtractKey
, _H1
, _H2
, _Hash
,
1591 __constant_iterators::value
,
1592 __hash_cached::value
>;
1594 using __ireturn_type
= typename
std::conditional
<__unique_keys::value
,
1595 std::pair
<iterator
, bool>,
1598 using _EqualEBO
= _Hashtable_ebo_helper
<0, _Equal
>;
1599 using _EqualHelper
= _Equal_helper
<_Key
, _Value
, _ExtractKey
, _Equal
,
1600 __hash_code
, __hash_cached::value
>;
1603 _Hashtable_base(const _ExtractKey
& __ex
, const _H1
& __h1
, const _H2
& __h2
,
1604 const _Hash
& __hash
, const _Equal
& __eq
)
1605 : __hash_code_base(__ex
, __h1
, __h2
, __hash
), _EqualEBO(__eq
)
1609 _M_equals(const _Key
& __k
, __hash_code __c
, __node_type
* __n
) const
1611 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
1616 _M_swap(_Hashtable_base
& __x
)
1618 __hash_code_base::_M_swap(__x
);
1619 std::swap(_M_eq(), __x
._M_eq());
1623 _M_eq() const { return _EqualEBO::_S_cget(*this); }
1626 _M_eq() { return _EqualEBO::_S_get(*this); }
1630 * struct _Equality_base.
1632 * Common types and functions for class _Equality.
1634 struct _Equality_base
1637 template<typename _Uiterator
>
1639 _S_is_permutation(_Uiterator
, _Uiterator
, _Uiterator
);
1642 // See std::is_permutation in N3068.
1643 template<typename _Uiterator
>
1646 _S_is_permutation(_Uiterator __first1
, _Uiterator __last1
,
1647 _Uiterator __first2
)
1649 for (; __first1
!= __last1
; ++__first1
, ++__first2
)
1650 if (!(*__first1
== *__first2
))
1653 if (__first1
== __last1
)
1656 _Uiterator __last2
= __first2
;
1657 std::advance(__last2
, std::distance(__first1
, __last1
));
1659 for (_Uiterator __it1
= __first1
; __it1
!= __last1
; ++__it1
)
1661 _Uiterator __tmp
= __first1
;
1662 while (__tmp
!= __it1
&& !bool(*__tmp
== *__it1
))
1665 // We've seen this one before.
1669 std::ptrdiff_t __n2
= 0;
1670 for (__tmp
= __first2
; __tmp
!= __last2
; ++__tmp
)
1671 if (*__tmp
== *__it1
)
1677 std::ptrdiff_t __n1
= 0;
1678 for (__tmp
= __it1
; __tmp
!= __last1
; ++__tmp
)
1679 if (*__tmp
== *__it1
)
1689 * Primary class template _Equality.
1691 * This is for implementing equality comparison for unordered
1692 * containers, per N3068, by John Lakos and Pablo Halpern.
1693 * Algorithmically, we follow closely the reference implementations
1696 template<typename _Key
, typename _Value
, typename _Alloc
,
1697 typename _ExtractKey
, typename _Equal
,
1698 typename _H1
, typename _H2
, typename _Hash
,
1699 typename _RehashPolicy
, typename _Traits
,
1700 bool _Unique_keys
= _Traits::__unique_keys::value
>
1704 template<typename _Key
, typename _Value
, typename _Alloc
,
1705 typename _ExtractKey
, typename _Equal
,
1706 typename _H1
, typename _H2
, typename _Hash
,
1707 typename _RehashPolicy
, typename _Traits
>
1708 struct _Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1709 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>
1711 using __hashtable
= _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1712 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>;
1715 _M_equal(const __hashtable
&) const;
1718 template<typename _Key
, typename _Value
, typename _Alloc
,
1719 typename _ExtractKey
, typename _Equal
,
1720 typename _H1
, typename _H2
, typename _Hash
,
1721 typename _RehashPolicy
, typename _Traits
>
1723 _Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1724 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>::
1725 _M_equal(const __hashtable
& __other
) const
1727 const __hashtable
* __this
= static_cast<const __hashtable
*>(this);
1729 if (__this
->size() != __other
.size())
1732 for (auto __itx
= __this
->begin(); __itx
!= __this
->end(); ++__itx
)
1734 const auto __ity
= __other
.find(_ExtractKey()(*__itx
));
1735 if (__ity
== __other
.end() || !bool(*__ity
== *__itx
))
1742 template<typename _Key
, typename _Value
, typename _Alloc
,
1743 typename _ExtractKey
, typename _Equal
,
1744 typename _H1
, typename _H2
, typename _Hash
,
1745 typename _RehashPolicy
, typename _Traits
>
1746 struct _Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1747 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, false>
1748 : public _Equality_base
1750 using __hashtable
= _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1751 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>;
1754 _M_equal(const __hashtable
&) const;
1757 template<typename _Key
, typename _Value
, typename _Alloc
,
1758 typename _ExtractKey
, typename _Equal
,
1759 typename _H1
, typename _H2
, typename _Hash
,
1760 typename _RehashPolicy
, typename _Traits
>
1762 _Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1763 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, false>::
1764 _M_equal(const __hashtable
& __other
) const
1766 const __hashtable
* __this
= static_cast<const __hashtable
*>(this);
1768 if (__this
->size() != __other
.size())
1771 for (auto __itx
= __this
->begin(); __itx
!= __this
->end();)
1773 const auto __xrange
= __this
->equal_range(_ExtractKey()(*__itx
));
1774 const auto __yrange
= __other
.equal_range(_ExtractKey()(*__itx
));
1776 if (std::distance(__xrange
.first
, __xrange
.second
)
1777 != std::distance(__yrange
.first
, __yrange
.second
))
1780 if (!_S_is_permutation(__xrange
.first
, __xrange
.second
,
1784 __itx
= __xrange
.second
;
1790 * This type deals with all allocation and keeps an allocator instance through
1791 * inheritance to benefit from EBO when possible.
1793 template<typename _NodeAlloc
>
1794 struct _Hashtable_alloc
: private _Hashtable_ebo_helper
<0, _NodeAlloc
>
1797 using __ebo_node_alloc
= _Hashtable_ebo_helper
<0, _NodeAlloc
>;
1799 using __node_type
= typename
_NodeAlloc::value_type
;
1800 using __node_alloc_type
= _NodeAlloc
;
1801 // Use __gnu_cxx to benefit from _S_always_equal and al.
1802 using __node_alloc_traits
= __gnu_cxx::__alloc_traits
<__node_alloc_type
>;
1804 using __value_type
= typename
__node_type::value_type
;
1805 using __value_alloc_type
=
1806 typename __alloctr_rebind
<__node_alloc_type
, __value_type
>::__type
;
1807 using __value_alloc_traits
= std::allocator_traits
<__value_alloc_type
>;
1809 using __node_base
= __detail::_Hash_node_base
;
1810 using __bucket_type
= __node_base
*;
1811 using __bucket_alloc_type
=
1812 typename __alloctr_rebind
<__node_alloc_type
, __bucket_type
>::__type
;
1813 using __bucket_alloc_traits
= std::allocator_traits
<__bucket_alloc_type
>;
1815 _Hashtable_alloc(const _Hashtable_alloc
&) = default;
1816 _Hashtable_alloc(_Hashtable_alloc
&&) = default;
1818 template<typename _Alloc
>
1819 _Hashtable_alloc(_Alloc
&& __a
)
1820 : __ebo_node_alloc(std::forward
<_Alloc
>(__a
))
1825 { return __ebo_node_alloc::_S_get(*this); }
1827 const __node_alloc_type
&
1828 _M_node_allocator() const
1829 { return __ebo_node_alloc::_S_cget(*this); }
1831 template<typename
... _Args
>
1833 _M_allocate_node(_Args
&&... __args
);
1836 _M_deallocate_node(__node_type
* __n
);
1838 // Deallocate the linked list of nodes pointed to by __n
1840 _M_deallocate_nodes(__node_type
* __n
);
1843 _M_allocate_buckets(std::size_t __n
);
1846 _M_deallocate_buckets(__bucket_type
*, std::size_t __n
);
1849 // Definitions of class template _Hashtable_alloc's out-of-line member
1851 template<typename _NodeAlloc
>
1852 template<typename
... _Args
>
1853 typename _Hashtable_alloc
<_NodeAlloc
>::__node_type
*
1854 _Hashtable_alloc
<_NodeAlloc
>::_M_allocate_node(_Args
&&... __args
)
1856 auto __nptr
= __node_alloc_traits::allocate(_M_node_allocator(), 1);
1857 __node_type
* __n
= std::__addressof(*__nptr
);
1860 __value_alloc_type
__a(_M_node_allocator());
1861 ::new ((void*)__n
) __node_type();
1862 __value_alloc_traits::construct(__a
, __n
->_M_valptr(),
1863 std::forward
<_Args
>(__args
)...);
1868 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr
, 1);
1869 __throw_exception_again
;
1873 template<typename _NodeAlloc
>
1875 _Hashtable_alloc
<_NodeAlloc
>::_M_deallocate_node(__node_type
* __n
)
1877 typedef typename
__node_alloc_traits::pointer _Ptr
;
1878 auto __ptr
= std::pointer_traits
<_Ptr
>::pointer_to(*__n
);
1879 __value_alloc_type
__a(_M_node_allocator());
1880 __value_alloc_traits::destroy(__a
, __n
->_M_valptr());
1881 __n
->~__node_type();
1882 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr
, 1);
1885 template<typename _NodeAlloc
>
1887 _Hashtable_alloc
<_NodeAlloc
>::_M_deallocate_nodes(__node_type
* __n
)
1891 __node_type
* __tmp
= __n
;
1892 __n
= __n
->_M_next();
1893 _M_deallocate_node(__tmp
);
1897 template<typename _NodeAlloc
>
1898 typename _Hashtable_alloc
<_NodeAlloc
>::__bucket_type
*
1899 _Hashtable_alloc
<_NodeAlloc
>::_M_allocate_buckets(std::size_t __n
)
1901 __bucket_alloc_type
__alloc(_M_node_allocator());
1903 auto __ptr
= __bucket_alloc_traits::allocate(__alloc
, __n
);
1904 __bucket_type
* __p
= std::__addressof(*__ptr
);
1905 __builtin_memset(__p
, 0, __n
* sizeof(__bucket_type
));
1909 template<typename _NodeAlloc
>
1911 _Hashtable_alloc
<_NodeAlloc
>::_M_deallocate_buckets(__bucket_type
* __bkts
,
1914 typedef typename
__bucket_alloc_traits::pointer _Ptr
;
1915 auto __ptr
= std::pointer_traits
<_Ptr
>::pointer_to(*__bkts
);
1916 __bucket_alloc_type
__alloc(_M_node_allocator());
1917 __bucket_alloc_traits::deallocate(__alloc
, __ptr
, __n
);
1920 //@} hashtable-detail
1921 _GLIBCXX_END_NAMESPACE_VERSION
1922 } // namespace __detail
1925 #endif // _HASHTABLE_POLICY_H