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 // Functor recycling a pool of nodes and using allocation once the pool is
107 template<typename _Key
, typename _Value
, typename _Alloc
,
108 typename _ExtractKey
, typename _Equal
,
109 typename _H1
, typename _H2
, typename _Hash
,
110 typename _RehashPolicy
, typename _Traits
>
111 struct _ReuseOrAllocNode
114 using __hashtable
= _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
115 _Equal
, _H1
, _H2
, _Hash
,
116 _RehashPolicy
, _Traits
>;
117 using __val_alloc_type
= typename
__hashtable::_Value_alloc_type
;
118 using __val_alloc_traits
= typename
__hashtable::_Value_alloc_traits
;
119 using __node_alloc_traits
= typename
__hashtable::_Node_alloc_traits
;
120 using __node_type
= typename
__hashtable::__node_type
;
123 _ReuseOrAllocNode(__node_type
* __nodes
, __hashtable
& __h
)
124 : _M_nodes(__nodes
), _M_h(__h
) { }
125 _ReuseOrAllocNode(const _ReuseOrAllocNode
&) = delete;
128 { _M_h
._M_deallocate_nodes(_M_nodes
); }
130 template<typename _Arg
>
132 operator()(_Arg
&& __arg
) const
136 __node_type
* __node
= _M_nodes
;
137 _M_nodes
= _M_nodes
->_M_next();
138 __node
->_M_nxt
= nullptr;
139 __val_alloc_type
__a(_M_h
._M_node_allocator());
140 __val_alloc_traits::destroy(__a
, __node
->_M_valptr());
143 __val_alloc_traits::construct(__a
, __node
->_M_valptr(),
144 std::forward
<_Arg
>(__arg
));
148 __node
->~__node_type();
149 __node_alloc_traits::deallocate(_M_h
._M_node_allocator(),
151 __throw_exception_again
;
155 return _M_h
._M_allocate_node(std::forward
<_Arg
>(__arg
));
159 mutable __node_type
* _M_nodes
;
163 // Functor similar to the previous one but without any pool of node to recycle.
164 template<typename _Key
, typename _Value
, typename _Alloc
,
165 typename _ExtractKey
, typename _Equal
,
166 typename _H1
, typename _H2
, typename _Hash
,
167 typename _RehashPolicy
, typename _Traits
>
171 using __hashtable
= _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
172 _Equal
, _H1
, _H2
, _Hash
,
173 _RehashPolicy
, _Traits
>;
174 using __node_type
= typename
__hashtable::__node_type
;
177 _AllocNode(__hashtable
& __h
)
180 template<typename _Arg
>
182 operator()(_Arg
&& __arg
) const
183 { return _M_h
._M_allocate_node(std::forward
<_Arg
>(__arg
)); }
189 // Auxiliary types used for all instantiations of _Hashtable nodes
193 * struct _Hashtable_traits
195 * Important traits for hash tables.
197 * @tparam _Cache_hash_code Boolean value. True if the value of
198 * the hash function is stored along with the value. This is a
199 * time-space tradeoff. Storing it may improve lookup speed by
200 * reducing the number of times we need to call the _Equal
203 * @tparam _Constant_iterators Boolean value. True if iterator and
204 * const_iterator are both constant iterator types. This is true
205 * for unordered_set and unordered_multiset, false for
206 * unordered_map and unordered_multimap.
208 * @tparam _Unique_keys Boolean value. True if the return value
209 * of _Hashtable::count(k) is always at most one, false if it may
210 * be an arbitrary number. This is true for unordered_set and
211 * unordered_map, false for unordered_multiset and
212 * unordered_multimap.
214 template<bool _Cache_hash_code
, bool _Constant_iterators
, bool _Unique_keys
>
215 struct _Hashtable_traits
218 using __bool_constant
= integral_constant
<bool, _Cond
>;
220 using __hash_cached
= __bool_constant
<_Cache_hash_code
>;
221 using __constant_iterators
= __bool_constant
<_Constant_iterators
>;
222 using __unique_keys
= __bool_constant
<_Unique_keys
>;
226 * struct _Hash_node_base
228 * Nodes, used to wrap elements stored in the hash table. A policy
229 * template parameter of class template _Hashtable controls whether
230 * nodes also store a hash code. In some cases (e.g. strings) this
231 * may be a performance win.
233 struct _Hash_node_base
235 _Hash_node_base
* _M_nxt
;
237 _Hash_node_base() : _M_nxt() { }
239 _Hash_node_base(_Hash_node_base
* __next
) : _M_nxt(__next
) { }
243 * struct _Hash_node_value_base
245 * Node type with the value to store.
247 template<typename _Value
>
248 struct _Hash_node_value_base
: _Hash_node_base
250 __gnu_cxx::__aligned_buffer
<_Value
> _M_storage
;
254 { return _M_storage
._M_ptr(); }
257 _M_valptr() const noexcept
258 { return _M_storage
._M_ptr(); }
262 { return *_M_valptr(); }
265 _M_v() const noexcept
266 { return *_M_valptr(); }
270 * Primary template struct _Hash_node.
272 template<typename _Value
, bool _Cache_hash_code
>
276 * Specialization for nodes with caches, struct _Hash_node.
278 * Base class is __detail::_Hash_node_value_base.
280 template<typename _Value
>
281 struct _Hash_node
<_Value
, true> : _Hash_node_value_base
<_Value
>
283 std::size_t _M_hash_code
;
286 _M_next() const { return static_cast<_Hash_node
*>(this->_M_nxt
); }
290 * Specialization for nodes without caches, struct _Hash_node.
292 * Base class is __detail::_Hash_node_value_base.
294 template<typename _Value
>
295 struct _Hash_node
<_Value
, false> : _Hash_node_value_base
<_Value
>
298 _M_next() const { return static_cast<_Hash_node
*>(this->_M_nxt
); }
301 /// Base class for node iterators.
302 template<typename _Value
, bool _Cache_hash_code
>
303 struct _Node_iterator_base
305 using __node_type
= _Hash_node
<_Value
, _Cache_hash_code
>;
309 _Node_iterator_base(__node_type
* __p
)
314 { _M_cur
= _M_cur
->_M_next(); }
317 template<typename _Value
, bool _Cache_hash_code
>
319 operator==(const _Node_iterator_base
<_Value
, _Cache_hash_code
>& __x
,
320 const _Node_iterator_base
<_Value
, _Cache_hash_code
>& __y
)
321 { return __x
._M_cur
== __y
._M_cur
; }
323 template<typename _Value
, bool _Cache_hash_code
>
325 operator!=(const _Node_iterator_base
<_Value
, _Cache_hash_code
>& __x
,
326 const _Node_iterator_base
<_Value
, _Cache_hash_code
>& __y
)
327 { return __x
._M_cur
!= __y
._M_cur
; }
329 /// Node iterators, used to iterate through all the hashtable.
330 template<typename _Value
, bool __constant_iterators
, bool __cache
>
331 struct _Node_iterator
332 : public _Node_iterator_base
<_Value
, __cache
>
335 using __base_type
= _Node_iterator_base
<_Value
, __cache
>;
336 using __node_type
= typename
__base_type::__node_type
;
339 typedef _Value value_type
;
340 typedef std::ptrdiff_t difference_type
;
341 typedef std::forward_iterator_tag iterator_category
;
343 using pointer
= typename
std::conditional
<__constant_iterators
,
344 const _Value
*, _Value
*>::type
;
346 using reference
= typename
std::conditional
<__constant_iterators
,
347 const _Value
&, _Value
&>::type
;
353 _Node_iterator(__node_type
* __p
)
354 : __base_type(__p
) { }
358 { return this->_M_cur
->_M_v(); }
362 { return this->_M_cur
->_M_valptr(); }
374 _Node_iterator
__tmp(*this);
380 /// Node const_iterators, used to iterate through all the hashtable.
381 template<typename _Value
, bool __constant_iterators
, bool __cache
>
382 struct _Node_const_iterator
383 : public _Node_iterator_base
<_Value
, __cache
>
386 using __base_type
= _Node_iterator_base
<_Value
, __cache
>;
387 using __node_type
= typename
__base_type::__node_type
;
390 typedef _Value value_type
;
391 typedef std::ptrdiff_t difference_type
;
392 typedef std::forward_iterator_tag iterator_category
;
394 typedef const _Value
* pointer
;
395 typedef const _Value
& reference
;
397 _Node_const_iterator()
401 _Node_const_iterator(__node_type
* __p
)
402 : __base_type(__p
) { }
404 _Node_const_iterator(const _Node_iterator
<_Value
, __constant_iterators
,
406 : __base_type(__x
._M_cur
) { }
410 { return this->_M_cur
->_M_v(); }
414 { return this->_M_cur
->_M_valptr(); }
416 _Node_const_iterator
&
426 _Node_const_iterator
__tmp(*this);
432 // Many of class template _Hashtable's template parameters are policy
433 // classes. These are defaults for the policies.
435 /// Default range hashing function: use division to fold a large number
436 /// into the range [0, N).
437 struct _Mod_range_hashing
439 typedef std::size_t first_argument_type
;
440 typedef std::size_t second_argument_type
;
441 typedef std::size_t result_type
;
444 operator()(first_argument_type __num
,
445 second_argument_type __den
) const noexcept
446 { return __num
% __den
; }
449 /// Default ranged hash function H. In principle it should be a
450 /// function object composed from objects of type H1 and H2 such that
451 /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of
452 /// h1 and h2. So instead we'll just use a tag to tell class template
453 /// hashtable to do that composition.
454 struct _Default_ranged_hash
{ };
456 /// Default value for rehash policy. Bucket size is (usually) the
457 /// smallest prime that keeps the load factor small enough.
458 struct _Prime_rehash_policy
460 _Prime_rehash_policy(float __z
= 1.0)
461 : _M_max_load_factor(__z
), _M_next_resize(0) { }
464 max_load_factor() const noexcept
465 { return _M_max_load_factor
; }
467 // Return a bucket size no smaller than n.
469 _M_next_bkt(std::size_t __n
) const;
471 // Return a bucket count appropriate for n elements
473 _M_bkt_for_elements(std::size_t __n
) const
474 { return __builtin_ceil(__n
/ (long double)_M_max_load_factor
); }
476 // __n_bkt is current bucket count, __n_elt is current element count,
477 // and __n_ins is number of elements to be inserted. Do we need to
478 // increase bucket count? If so, return make_pair(true, n), where n
479 // is the new bucket count. If not, return make_pair(false, 0).
480 std::pair
<bool, std::size_t>
481 _M_need_rehash(std::size_t __n_bkt
, std::size_t __n_elt
,
482 std::size_t __n_ins
) const;
484 typedef std::size_t _State
;
488 { return _M_next_resize
; }
492 { _M_next_resize
= 0; }
495 _M_reset(_State __state
)
496 { _M_next_resize
= __state
; }
498 enum { _S_n_primes
= sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
500 static const std::size_t _S_growth_factor
= 2;
502 float _M_max_load_factor
;
503 mutable std::size_t _M_next_resize
;
506 // Base classes for std::_Hashtable. We define these base classes
507 // because in some cases we want to do different things depending on
508 // the value of a policy class. In some cases the policy class
509 // affects which member functions and nested typedefs are defined;
510 // we handle that by specializing base class templates. Several of
511 // the base class templates need to access other members of class
512 // template _Hashtable, so we use a variant of the "Curiously
513 // Recurring Template Pattern" (CRTP) technique.
516 * Primary class template _Map_base.
518 * If the hashtable has a value type of the form pair<T1, T2> and a
519 * key extraction policy (_ExtractKey) that returns the first part
520 * of the pair, the hashtable gets a mapped_type typedef. If it
521 * satisfies those criteria and also has unique keys, then it also
522 * gets an operator[].
524 template<typename _Key
, typename _Value
, typename _Alloc
,
525 typename _ExtractKey
, typename _Equal
,
526 typename _H1
, typename _H2
, typename _Hash
,
527 typename _RehashPolicy
, typename _Traits
,
528 bool _Unique_keys
= _Traits::__unique_keys::value
>
529 struct _Map_base
{ };
531 /// Partial specialization, __unique_keys set to false.
532 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
533 typename _H1
, typename _H2
, typename _Hash
,
534 typename _RehashPolicy
, typename _Traits
>
535 struct _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
536 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, false>
538 using mapped_type
= typename
std::tuple_element
<1, _Pair
>::type
;
541 /// Partial specialization, __unique_keys set to true.
542 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
543 typename _H1
, typename _H2
, typename _Hash
,
544 typename _RehashPolicy
, typename _Traits
>
545 struct _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
546 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>
549 using __hashtable_base
= __detail::_Hashtable_base
<_Key
, _Pair
,
551 _Equal
, _H1
, _H2
, _Hash
,
554 using __hashtable
= _Hashtable
<_Key
, _Pair
, _Alloc
,
556 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>;
558 using __hash_code
= typename
__hashtable_base::__hash_code
;
559 using __node_type
= typename
__hashtable_base::__node_type
;
562 using key_type
= typename
__hashtable_base::key_type
;
563 using iterator
= typename
__hashtable_base::iterator
;
564 using mapped_type
= typename
std::tuple_element
<1, _Pair
>::type
;
567 operator[](const key_type
& __k
);
570 operator[](key_type
&& __k
);
572 // _GLIBCXX_RESOLVE_LIB_DEFECTS
573 // DR 761. unordered_map needs an at() member function.
575 at(const key_type
& __k
);
578 at(const key_type
& __k
) const;
581 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
582 typename _H1
, typename _H2
, typename _Hash
,
583 typename _RehashPolicy
, typename _Traits
>
584 typename _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
585 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>
587 _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
588 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>::
589 operator[](const key_type
& __k
)
591 __hashtable
* __h
= static_cast<__hashtable
*>(this);
592 __hash_code __code
= __h
->_M_hash_code(__k
);
593 std::size_t __n
= __h
->_M_bucket_index(__k
, __code
);
594 __node_type
* __p
= __h
->_M_find_node(__n
, __k
, __code
);
598 __p
= __h
->_M_allocate_node(std::piecewise_construct
,
599 std::tuple
<const key_type
&>(__k
),
601 return __h
->_M_insert_unique_node(__n
, __code
, __p
)->second
;
604 return __p
->_M_v().second
;
607 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
608 typename _H1
, typename _H2
, typename _Hash
,
609 typename _RehashPolicy
, typename _Traits
>
610 typename _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
611 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>
613 _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
614 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>::
615 operator[](key_type
&& __k
)
617 __hashtable
* __h
= static_cast<__hashtable
*>(this);
618 __hash_code __code
= __h
->_M_hash_code(__k
);
619 std::size_t __n
= __h
->_M_bucket_index(__k
, __code
);
620 __node_type
* __p
= __h
->_M_find_node(__n
, __k
, __code
);
624 __p
= __h
->_M_allocate_node(std::piecewise_construct
,
625 std::forward_as_tuple(std::move(__k
)),
627 return __h
->_M_insert_unique_node(__n
, __code
, __p
)->second
;
630 return __p
->_M_v().second
;
633 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
634 typename _H1
, typename _H2
, typename _Hash
,
635 typename _RehashPolicy
, typename _Traits
>
636 typename _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
637 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>
639 _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
640 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>::
641 at(const key_type
& __k
)
643 __hashtable
* __h
= static_cast<__hashtable
*>(this);
644 __hash_code __code
= __h
->_M_hash_code(__k
);
645 std::size_t __n
= __h
->_M_bucket_index(__k
, __code
);
646 __node_type
* __p
= __h
->_M_find_node(__n
, __k
, __code
);
649 __throw_out_of_range(__N("_Map_base::at"));
650 return __p
->_M_v().second
;
653 template<typename _Key
, typename _Pair
, typename _Alloc
, typename _Equal
,
654 typename _H1
, typename _H2
, typename _Hash
,
655 typename _RehashPolicy
, typename _Traits
>
656 const typename _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
,
657 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
658 _Traits
, true>::mapped_type
&
659 _Map_base
<_Key
, _Pair
, _Alloc
, _Select1st
, _Equal
,
660 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
, true>::
661 at(const key_type
& __k
) const
663 const __hashtable
* __h
= static_cast<const __hashtable
*>(this);
664 __hash_code __code
= __h
->_M_hash_code(__k
);
665 std::size_t __n
= __h
->_M_bucket_index(__k
, __code
);
666 __node_type
* __p
= __h
->_M_find_node(__n
, __k
, __code
);
669 __throw_out_of_range(__N("_Map_base::at"));
670 return __p
->_M_v().second
;
674 * Primary class template _Insert_base.
676 * insert member functions appropriate to all _Hashtables.
678 template<typename _Key
, typename _Value
, typename _Alloc
,
679 typename _ExtractKey
, typename _Equal
,
680 typename _H1
, typename _H2
, typename _Hash
,
681 typename _RehashPolicy
, typename _Traits
>
685 using __hashtable
= _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
686 _Equal
, _H1
, _H2
, _Hash
,
687 _RehashPolicy
, _Traits
>;
689 using __hashtable_base
= _Hashtable_base
<_Key
, _Value
, _ExtractKey
,
690 _Equal
, _H1
, _H2
, _Hash
,
693 using value_type
= typename
__hashtable_base::value_type
;
694 using iterator
= typename
__hashtable_base::iterator
;
695 using const_iterator
= typename
__hashtable_base::const_iterator
;
696 using size_type
= typename
__hashtable_base::size_type
;
698 using __unique_keys
= typename
__hashtable_base::__unique_keys
;
699 using __ireturn_type
= typename
__hashtable_base::__ireturn_type
;
700 using __node_gen_type
= _AllocNode
<_Key
, _Value
, _Alloc
, _ExtractKey
,
701 _Equal
, _H1
, _H2
, _Hash
,
702 _RehashPolicy
, _Traits
>;
705 _M_conjure_hashtable()
706 { return *(static_cast<__hashtable
*>(this)); }
708 template<typename _InputIterator
, typename _NodeGetter
>
710 _M_insert_range(_InputIterator __first
, _InputIterator __last
,
715 insert(const value_type
& __v
)
717 __hashtable
& __h
= _M_conjure_hashtable();
718 __node_gen_type
__node_gen(__h
);
719 return __h
._M_insert(__v
, __node_gen
, __unique_keys());
723 insert(const_iterator __hint
, const value_type
& __v
)
725 __hashtable
& __h
= _M_conjure_hashtable();
726 __node_gen_type
__node_gen(__h
);
727 return __h
._M_insert(__hint
, __v
, __node_gen
, __unique_keys());
731 insert(initializer_list
<value_type
> __l
)
732 { this->insert(__l
.begin(), __l
.end()); }
734 template<typename _InputIterator
>
736 insert(_InputIterator __first
, _InputIterator __last
)
738 __hashtable
& __h
= _M_conjure_hashtable();
739 __node_gen_type
__node_gen(__h
);
740 return _M_insert_range(__first
, __last
, __node_gen
);
744 template<typename _Key
, typename _Value
, typename _Alloc
,
745 typename _ExtractKey
, typename _Equal
,
746 typename _H1
, typename _H2
, typename _Hash
,
747 typename _RehashPolicy
, typename _Traits
>
748 template<typename _InputIterator
, typename _NodeGetter
>
750 _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
, _H1
, _H2
, _Hash
,
751 _RehashPolicy
, _Traits
>::
752 _M_insert_range(_InputIterator __first
, _InputIterator __last
,
753 const _NodeGetter
& __node_gen
)
755 using __rehash_type
= typename
__hashtable::__rehash_type
;
756 using __rehash_state
= typename
__hashtable::__rehash_state
;
757 using pair_type
= std::pair
<bool, std::size_t>;
759 size_type __n_elt
= __detail::__distance_fw(__first
, __last
);
761 __hashtable
& __h
= _M_conjure_hashtable();
762 __rehash_type
& __rehash
= __h
._M_rehash_policy
;
763 const __rehash_state
& __saved_state
= __rehash
._M_state();
764 pair_type __do_rehash
= __rehash
._M_need_rehash(__h
._M_bucket_count
,
765 __h
._M_element_count
,
768 if (__do_rehash
.first
)
769 __h
._M_rehash(__do_rehash
.second
, __saved_state
);
771 for (; __first
!= __last
; ++__first
)
772 __h
._M_insert(*__first
, __node_gen
, __unique_keys());
776 * Primary class template _Insert.
778 * Select insert member functions appropriate to _Hashtable policy choices.
780 template<typename _Key
, typename _Value
, typename _Alloc
,
781 typename _ExtractKey
, typename _Equal
,
782 typename _H1
, typename _H2
, typename _Hash
,
783 typename _RehashPolicy
, typename _Traits
,
784 bool _Constant_iterators
= _Traits::__constant_iterators::value
,
785 bool _Unique_keys
= _Traits::__unique_keys::value
>
789 template<typename _Key
, typename _Value
, typename _Alloc
,
790 typename _ExtractKey
, typename _Equal
,
791 typename _H1
, typename _H2
, typename _Hash
,
792 typename _RehashPolicy
, typename _Traits
>
793 struct _Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
, _H1
, _H2
, _Hash
,
794 _RehashPolicy
, _Traits
, true, true>
795 : public _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
796 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>
798 using __base_type
= _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
799 _Equal
, _H1
, _H2
, _Hash
,
800 _RehashPolicy
, _Traits
>;
801 using value_type
= typename
__base_type::value_type
;
802 using iterator
= typename
__base_type::iterator
;
803 using const_iterator
= typename
__base_type::const_iterator
;
805 using __unique_keys
= typename
__base_type::__unique_keys
;
806 using __hashtable
= typename
__base_type::__hashtable
;
807 using __node_gen_type
= typename
__base_type::__node_gen_type
;
809 using __base_type::insert
;
811 std::pair
<iterator
, bool>
812 insert(value_type
&& __v
)
814 __hashtable
& __h
= this->_M_conjure_hashtable();
815 __node_gen_type
__node_gen(__h
);
816 return __h
._M_insert(std::move(__v
), __node_gen
, __unique_keys());
820 insert(const_iterator __hint
, value_type
&& __v
)
822 __hashtable
& __h
= this->_M_conjure_hashtable();
823 __node_gen_type
__node_gen(__h
);
824 return __h
._M_insert(__hint
, std::move(__v
), __node_gen
,
830 template<typename _Key
, typename _Value
, typename _Alloc
,
831 typename _ExtractKey
, typename _Equal
,
832 typename _H1
, typename _H2
, typename _Hash
,
833 typename _RehashPolicy
, typename _Traits
>
834 struct _Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
, _H1
, _H2
, _Hash
,
835 _RehashPolicy
, _Traits
, true, false>
836 : public _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
837 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>
839 using __base_type
= _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
840 _Equal
, _H1
, _H2
, _Hash
,
841 _RehashPolicy
, _Traits
>;
842 using value_type
= typename
__base_type::value_type
;
843 using iterator
= typename
__base_type::iterator
;
844 using const_iterator
= typename
__base_type::const_iterator
;
846 using __unique_keys
= typename
__base_type::__unique_keys
;
847 using __hashtable
= typename
__base_type::__hashtable
;
848 using __node_gen_type
= typename
__base_type::__node_gen_type
;
850 using __base_type::insert
;
853 insert(value_type
&& __v
)
855 __hashtable
& __h
= this->_M_conjure_hashtable();
856 __node_gen_type
__node_gen(__h
);
857 return __h
._M_insert(std::move(__v
), __node_gen
, __unique_keys());
861 insert(const_iterator __hint
, value_type
&& __v
)
863 __hashtable
& __h
= this->_M_conjure_hashtable();
864 __node_gen_type
__node_gen(__h
);
865 return __h
._M_insert(__hint
, std::move(__v
), __node_gen
,
871 template<typename _Key
, typename _Value
, typename _Alloc
,
872 typename _ExtractKey
, typename _Equal
,
873 typename _H1
, typename _H2
, typename _Hash
,
874 typename _RehashPolicy
, typename _Traits
, bool _Unique_keys
>
875 struct _Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
, _H1
, _H2
, _Hash
,
876 _RehashPolicy
, _Traits
, false, _Unique_keys
>
877 : public _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
878 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>
880 using __base_type
= _Insert_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
881 _Equal
, _H1
, _H2
, _Hash
,
882 _RehashPolicy
, _Traits
>;
883 using value_type
= typename
__base_type::value_type
;
884 using iterator
= typename
__base_type::iterator
;
885 using const_iterator
= typename
__base_type::const_iterator
;
887 using __unique_keys
= typename
__base_type::__unique_keys
;
888 using __hashtable
= typename
__base_type::__hashtable
;
889 using __ireturn_type
= typename
__base_type::__ireturn_type
;
891 using __base_type::insert
;
893 template<typename _Pair
>
894 using __is_cons
= std::is_constructible
<value_type
, _Pair
&&>;
896 template<typename _Pair
>
897 using _IFcons
= std::enable_if
<__is_cons
<_Pair
>::value
>;
899 template<typename _Pair
>
900 using _IFconsp
= typename _IFcons
<_Pair
>::type
;
902 template<typename _Pair
, typename
= _IFconsp
<_Pair
>>
906 __hashtable
& __h
= this->_M_conjure_hashtable();
907 return __h
._M_emplace(__unique_keys(), std::forward
<_Pair
>(__v
));
910 template<typename _Pair
, typename
= _IFconsp
<_Pair
>>
912 insert(const_iterator __hint
, _Pair
&& __v
)
914 __hashtable
& __h
= this->_M_conjure_hashtable();
915 return __h
._M_emplace(__hint
, __unique_keys(),
916 std::forward
<_Pair
>(__v
));
921 * Primary class template _Rehash_base.
923 * Give hashtable the max_load_factor functions and reserve iff the
924 * rehash policy is _Prime_rehash_policy.
926 template<typename _Key
, typename _Value
, typename _Alloc
,
927 typename _ExtractKey
, typename _Equal
,
928 typename _H1
, typename _H2
, typename _Hash
,
929 typename _RehashPolicy
, typename _Traits
>
933 template<typename _Key
, typename _Value
, typename _Alloc
,
934 typename _ExtractKey
, typename _Equal
,
935 typename _H1
, typename _H2
, typename _Hash
, typename _Traits
>
936 struct _Rehash_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
937 _H1
, _H2
, _Hash
, _Prime_rehash_policy
, _Traits
>
939 using __hashtable
= _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
940 _Equal
, _H1
, _H2
, _Hash
,
941 _Prime_rehash_policy
, _Traits
>;
944 max_load_factor() const noexcept
946 const __hashtable
* __this
= static_cast<const __hashtable
*>(this);
947 return __this
->__rehash_policy().max_load_factor();
951 max_load_factor(float __z
)
953 __hashtable
* __this
= static_cast<__hashtable
*>(this);
954 __this
->__rehash_policy(_Prime_rehash_policy(__z
));
958 reserve(std::size_t __n
)
960 __hashtable
* __this
= static_cast<__hashtable
*>(this);
961 __this
->rehash(__builtin_ceil(__n
/ max_load_factor()));
966 * Primary class template _Hashtable_ebo_helper.
968 * Helper class using EBO when it is not forbidden (the type is not
969 * final) and when it is worth it (the type is empty.)
971 template<int _Nm
, typename _Tp
,
972 bool __use_ebo
= !__is_final(_Tp
) && __is_empty(_Tp
)>
973 struct _Hashtable_ebo_helper
;
975 /// Specialization using EBO.
976 template<int _Nm
, typename _Tp
>
977 struct _Hashtable_ebo_helper
<_Nm
, _Tp
, true>
980 _Hashtable_ebo_helper() = default;
982 _Hashtable_ebo_helper(const _Tp
& __tp
) : _Tp(__tp
)
986 _S_cget(const _Hashtable_ebo_helper
& __eboh
)
987 { return static_cast<const _Tp
&>(__eboh
); }
990 _S_get(_Hashtable_ebo_helper
& __eboh
)
991 { return static_cast<_Tp
&>(__eboh
); }
994 /// Specialization not using EBO.
995 template<int _Nm
, typename _Tp
>
996 struct _Hashtable_ebo_helper
<_Nm
, _Tp
, false>
998 _Hashtable_ebo_helper() = default;
1000 _Hashtable_ebo_helper(const _Tp
& __tp
) : _M_tp(__tp
)
1004 _S_cget(const _Hashtable_ebo_helper
& __eboh
)
1005 { return __eboh
._M_tp
; }
1008 _S_get(_Hashtable_ebo_helper
& __eboh
)
1009 { return __eboh
._M_tp
; }
1016 * Primary class template _Local_iterator_base.
1018 * Base class for local iterators, used to iterate within a bucket
1019 * but not between buckets.
1021 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1022 typename _H1
, typename _H2
, typename _Hash
,
1023 bool __cache_hash_code
>
1024 struct _Local_iterator_base
;
1027 * Primary class template _Hash_code_base.
1029 * Encapsulates two policy issues that aren't quite orthogonal.
1030 * (1) the difference between using a ranged hash function and using
1031 * the combination of a hash function and a range-hashing function.
1032 * In the former case we don't have such things as hash codes, so
1033 * we have a dummy type as placeholder.
1034 * (2) Whether or not we cache hash codes. Caching hash codes is
1035 * meaningless if we have a ranged hash function.
1037 * We also put the key extraction objects here, for convenience.
1038 * Each specialization derives from one or more of the template
1039 * parameters to benefit from Ebo. This is important as this type
1040 * is inherited in some cases by the _Local_iterator_base type used
1041 * to implement local_iterator and const_local_iterator. As with
1042 * any iterator type we prefer to make it as small as possible.
1044 * Primary template is unused except as a hook for specializations.
1046 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1047 typename _H1
, typename _H2
, typename _Hash
,
1048 bool __cache_hash_code
>
1049 struct _Hash_code_base
;
1051 /// Specialization: ranged hash function, no caching hash codes. H1
1052 /// and H2 are provided but ignored. We define a dummy hash code type.
1053 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1054 typename _H1
, typename _H2
, typename _Hash
>
1055 struct _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
, _Hash
, false>
1056 : private _Hashtable_ebo_helper
<0, _ExtractKey
>,
1057 private _Hashtable_ebo_helper
<1, _Hash
>
1060 using __ebo_extract_key
= _Hashtable_ebo_helper
<0, _ExtractKey
>;
1061 using __ebo_hash
= _Hashtable_ebo_helper
<1, _Hash
>;
1064 typedef void* __hash_code
;
1065 typedef _Hash_node
<_Value
, false> __node_type
;
1067 // We need the default constructor for the local iterators.
1068 _Hash_code_base() = default;
1070 _Hash_code_base(const _ExtractKey
& __ex
, const _H1
&, const _H2
&,
1072 : __ebo_extract_key(__ex
), __ebo_hash(__h
) { }
1075 _M_hash_code(const _Key
& __key
) const
1079 _M_bucket_index(const _Key
& __k
, __hash_code
, std::size_t __n
) const
1080 { return _M_ranged_hash()(__k
, __n
); }
1083 _M_bucket_index(const __node_type
* __p
, std::size_t __n
) const
1084 noexcept( noexcept(declval
<const _Hash
&>()(declval
<const _Key
&>(), (std::size_t)0)) )
1085 { return _M_ranged_hash()(_M_extract()(__p
->_M_v()), __n
); }
1088 _M_store_code(__node_type
*, __hash_code
) const
1092 _M_copy_code(__node_type
*, const __node_type
*) const
1096 _M_swap(_Hash_code_base
& __x
)
1098 std::swap(_M_extract(), __x
._M_extract());
1099 std::swap(_M_ranged_hash(), __x
._M_ranged_hash());
1103 _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1106 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1109 _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); }
1112 _M_ranged_hash() { return __ebo_hash::_S_get(*this); }
1115 // No specialization for ranged hash function while caching hash codes.
1116 // That combination is meaningless, and trying to do it is an error.
1118 /// Specialization: ranged hash function, cache hash codes. This
1119 /// combination is meaningless, so we provide only a declaration
1120 /// and no definition.
1121 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1122 typename _H1
, typename _H2
, typename _Hash
>
1123 struct _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
, _Hash
, true>;
1125 /// Specialization: hash function and range-hashing function, no
1126 /// caching of hash codes.
1127 /// Provides typedef and accessor required by C++ 11.
1128 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1129 typename _H1
, typename _H2
>
1130 struct _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
,
1131 _Default_ranged_hash
, false>
1132 : private _Hashtable_ebo_helper
<0, _ExtractKey
>,
1133 private _Hashtable_ebo_helper
<1, _H1
>,
1134 private _Hashtable_ebo_helper
<2, _H2
>
1137 using __ebo_extract_key
= _Hashtable_ebo_helper
<0, _ExtractKey
>;
1138 using __ebo_h1
= _Hashtable_ebo_helper
<1, _H1
>;
1139 using __ebo_h2
= _Hashtable_ebo_helper
<2, _H2
>;
1145 hash_function() const
1149 typedef std::size_t __hash_code
;
1150 typedef _Hash_node
<_Value
, false> __node_type
;
1152 // We need the default constructor for the local iterators.
1153 _Hash_code_base() = default;
1155 _Hash_code_base(const _ExtractKey
& __ex
,
1156 const _H1
& __h1
, const _H2
& __h2
,
1157 const _Default_ranged_hash
&)
1158 : __ebo_extract_key(__ex
), __ebo_h1(__h1
), __ebo_h2(__h2
) { }
1161 _M_hash_code(const _Key
& __k
) const
1162 { return _M_h1()(__k
); }
1165 _M_bucket_index(const _Key
&, __hash_code __c
, std::size_t __n
) const
1166 { return _M_h2()(__c
, __n
); }
1169 _M_bucket_index(const __node_type
* __p
, std::size_t __n
) const
1170 noexcept( noexcept(declval
<const _H1
&>()(declval
<const _Key
&>()))
1171 && noexcept(declval
<const _H2
&>()((__hash_code
)0, (std::size_t)0)) )
1172 { return _M_h2()(_M_h1()(_M_extract()(__p
->_M_v())), __n
); }
1175 _M_store_code(__node_type
*, __hash_code
) const
1179 _M_copy_code(__node_type
*, const __node_type
*) const
1183 _M_swap(_Hash_code_base
& __x
)
1185 std::swap(_M_extract(), __x
._M_extract());
1186 std::swap(_M_h1(), __x
._M_h1());
1187 std::swap(_M_h2(), __x
._M_h2());
1191 _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1194 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1197 _M_h1() const { return __ebo_h1::_S_cget(*this); }
1200 _M_h1() { return __ebo_h1::_S_get(*this); }
1203 _M_h2() const { return __ebo_h2::_S_cget(*this); }
1206 _M_h2() { return __ebo_h2::_S_get(*this); }
1209 /// Specialization: hash function and range-hashing function,
1210 /// caching hash codes. H is provided but ignored. Provides
1211 /// typedef and accessor required by C++ 11.
1212 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1213 typename _H1
, typename _H2
>
1214 struct _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
,
1215 _Default_ranged_hash
, true>
1216 : private _Hashtable_ebo_helper
<0, _ExtractKey
>,
1217 private _Hashtable_ebo_helper
<1, _H1
>,
1218 private _Hashtable_ebo_helper
<2, _H2
>
1221 // Gives access to _M_h2() to the local iterator implementation.
1222 friend struct _Local_iterator_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
,
1223 _Default_ranged_hash
, true>;
1225 using __ebo_extract_key
= _Hashtable_ebo_helper
<0, _ExtractKey
>;
1226 using __ebo_h1
= _Hashtable_ebo_helper
<1, _H1
>;
1227 using __ebo_h2
= _Hashtable_ebo_helper
<2, _H2
>;
1233 hash_function() const
1237 typedef std::size_t __hash_code
;
1238 typedef _Hash_node
<_Value
, true> __node_type
;
1240 _Hash_code_base(const _ExtractKey
& __ex
,
1241 const _H1
& __h1
, const _H2
& __h2
,
1242 const _Default_ranged_hash
&)
1243 : __ebo_extract_key(__ex
), __ebo_h1(__h1
), __ebo_h2(__h2
) { }
1246 _M_hash_code(const _Key
& __k
) const
1247 { return _M_h1()(__k
); }
1250 _M_bucket_index(const _Key
&, __hash_code __c
,
1251 std::size_t __n
) const
1252 { return _M_h2()(__c
, __n
); }
1255 _M_bucket_index(const __node_type
* __p
, std::size_t __n
) const
1256 noexcept( noexcept(declval
<const _H2
&>()((__hash_code
)0,
1258 { return _M_h2()(__p
->_M_hash_code
, __n
); }
1261 _M_store_code(__node_type
* __n
, __hash_code __c
) const
1262 { __n
->_M_hash_code
= __c
; }
1265 _M_copy_code(__node_type
* __to
, const __node_type
* __from
) const
1266 { __to
->_M_hash_code
= __from
->_M_hash_code
; }
1269 _M_swap(_Hash_code_base
& __x
)
1271 std::swap(_M_extract(), __x
._M_extract());
1272 std::swap(_M_h1(), __x
._M_h1());
1273 std::swap(_M_h2(), __x
._M_h2());
1277 _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1280 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1283 _M_h1() const { return __ebo_h1::_S_cget(*this); }
1286 _M_h1() { return __ebo_h1::_S_get(*this); }
1289 _M_h2() const { return __ebo_h2::_S_cget(*this); }
1292 _M_h2() { return __ebo_h2::_S_get(*this); }
1296 * Primary class template _Equal_helper.
1299 template <typename _Key
, typename _Value
, typename _ExtractKey
,
1300 typename _Equal
, typename _HashCodeType
,
1301 bool __cache_hash_code
>
1302 struct _Equal_helper
;
1305 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1306 typename _Equal
, typename _HashCodeType
>
1307 struct _Equal_helper
<_Key
, _Value
, _ExtractKey
, _Equal
, _HashCodeType
, true>
1310 _S_equals(const _Equal
& __eq
, const _ExtractKey
& __extract
,
1311 const _Key
& __k
, _HashCodeType __c
, _Hash_node
<_Value
, true>* __n
)
1312 { return __c
== __n
->_M_hash_code
&& __eq(__k
, __extract(__n
->_M_v())); }
1316 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1317 typename _Equal
, typename _HashCodeType
>
1318 struct _Equal_helper
<_Key
, _Value
, _ExtractKey
, _Equal
, _HashCodeType
, false>
1321 _S_equals(const _Equal
& __eq
, const _ExtractKey
& __extract
,
1322 const _Key
& __k
, _HashCodeType
, _Hash_node
<_Value
, false>* __n
)
1323 { return __eq(__k
, __extract(__n
->_M_v())); }
1328 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1329 typename _H1
, typename _H2
, typename _Hash
>
1330 struct _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1331 _H1
, _H2
, _Hash
, true>
1332 : private _Hashtable_ebo_helper
<0, _H2
>
1335 using __base_type
= _Hashtable_ebo_helper
<0, _H2
>;
1336 using __hash_code_base
= _Hash_code_base
<_Key
, _Value
, _ExtractKey
,
1337 _H1
, _H2
, _Hash
, true>;
1340 _Local_iterator_base() = default;
1341 _Local_iterator_base(const __hash_code_base
& __base
,
1342 _Hash_node
<_Value
, true>* __p
,
1343 std::size_t __bkt
, std::size_t __bkt_count
)
1344 : __base_type(__base
._M_h2()),
1345 _M_cur(__p
), _M_bucket(__bkt
), _M_bucket_count(__bkt_count
) { }
1350 _M_cur
= _M_cur
->_M_next();
1354 = __base_type::_S_get(*this)(_M_cur
->_M_hash_code
,
1356 if (__bkt
!= _M_bucket
)
1361 _Hash_node
<_Value
, true>* _M_cur
;
1362 std::size_t _M_bucket
;
1363 std::size_t _M_bucket_count
;
1367 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1368 typename _H1
, typename _H2
, typename _Hash
>
1369 struct _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1370 _H1
, _H2
, _Hash
, false>
1371 : private _Hash_code_base
<_Key
, _Value
, _ExtractKey
,
1372 _H1
, _H2
, _Hash
, false>
1375 using __hash_code_base
= _Hash_code_base
<_Key
, _Value
, _ExtractKey
,
1376 _H1
, _H2
, _Hash
, false>;
1379 _Local_iterator_base() = default;
1380 _Local_iterator_base(const __hash_code_base
& __base
,
1381 _Hash_node
<_Value
, false>* __p
,
1382 std::size_t __bkt
, std::size_t __bkt_count
)
1383 : __hash_code_base(__base
),
1384 _M_cur(__p
), _M_bucket(__bkt
), _M_bucket_count(__bkt_count
) { }
1389 _M_cur
= _M_cur
->_M_next();
1392 std::size_t __bkt
= this->_M_bucket_index(_M_cur
, _M_bucket_count
);
1393 if (__bkt
!= _M_bucket
)
1398 _Hash_node
<_Value
, false>* _M_cur
;
1399 std::size_t _M_bucket
;
1400 std::size_t _M_bucket_count
;
1403 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1404 typename _H1
, typename _H2
, typename _Hash
, bool __cache
>
1406 operator==(const _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1407 _H1
, _H2
, _Hash
, __cache
>& __x
,
1408 const _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1409 _H1
, _H2
, _Hash
, __cache
>& __y
)
1410 { return __x
._M_cur
== __y
._M_cur
; }
1412 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1413 typename _H1
, typename _H2
, typename _Hash
, bool __cache
>
1415 operator!=(const _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1416 _H1
, _H2
, _Hash
, __cache
>& __x
,
1417 const _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1418 _H1
, _H2
, _Hash
, __cache
>& __y
)
1419 { return __x
._M_cur
!= __y
._M_cur
; }
1422 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1423 typename _H1
, typename _H2
, typename _Hash
,
1424 bool __constant_iterators
, bool __cache
>
1425 struct _Local_iterator
1426 : public _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1427 _H1
, _H2
, _Hash
, __cache
>
1430 using __base_type
= _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1431 _H1
, _H2
, _Hash
, __cache
>;
1432 using __hash_code_base
= typename
__base_type::__hash_code_base
;
1434 typedef _Value value_type
;
1435 typedef typename
std::conditional
<__constant_iterators
,
1436 const _Value
*, _Value
*>::type
1438 typedef typename
std::conditional
<__constant_iterators
,
1439 const _Value
&, _Value
&>::type
1441 typedef std::ptrdiff_t difference_type
;
1442 typedef std::forward_iterator_tag iterator_category
;
1444 _Local_iterator() = default;
1446 _Local_iterator(const __hash_code_base
& __base
,
1447 _Hash_node
<_Value
, __cache
>* __p
,
1448 std::size_t __bkt
, std::size_t __bkt_count
)
1449 : __base_type(__base
, __p
, __bkt
, __bkt_count
)
1454 { return this->_M_cur
->_M_v(); }
1458 { return this->_M_cur
->_M_valptr(); }
1470 _Local_iterator
__tmp(*this);
1476 /// local const_iterators
1477 template<typename _Key
, typename _Value
, typename _ExtractKey
,
1478 typename _H1
, typename _H2
, typename _Hash
,
1479 bool __constant_iterators
, bool __cache
>
1480 struct _Local_const_iterator
1481 : public _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1482 _H1
, _H2
, _Hash
, __cache
>
1485 using __base_type
= _Local_iterator_base
<_Key
, _Value
, _ExtractKey
,
1486 _H1
, _H2
, _Hash
, __cache
>;
1487 using __hash_code_base
= typename
__base_type::__hash_code_base
;
1490 typedef _Value value_type
;
1491 typedef const _Value
* pointer
;
1492 typedef const _Value
& reference
;
1493 typedef std::ptrdiff_t difference_type
;
1494 typedef std::forward_iterator_tag iterator_category
;
1496 _Local_const_iterator() = default;
1498 _Local_const_iterator(const __hash_code_base
& __base
,
1499 _Hash_node
<_Value
, __cache
>* __p
,
1500 std::size_t __bkt
, std::size_t __bkt_count
)
1501 : __base_type(__base
, __p
, __bkt
, __bkt_count
)
1504 _Local_const_iterator(const _Local_iterator
<_Key
, _Value
, _ExtractKey
,
1506 __constant_iterators
,
1513 { return this->_M_cur
->_M_v(); }
1517 { return this->_M_cur
->_M_valptr(); }
1519 _Local_const_iterator
&
1526 _Local_const_iterator
1529 _Local_const_iterator
__tmp(*this);
1536 * Primary class template _Hashtable_base.
1538 * Helper class adding management of _Equal functor to
1539 * _Hash_code_base type.
1541 * Base class templates are:
1542 * - __detail::_Hash_code_base
1543 * - __detail::_Hashtable_ebo_helper
1545 template<typename _Key
, typename _Value
,
1546 typename _ExtractKey
, typename _Equal
,
1547 typename _H1
, typename _H2
, typename _Hash
, typename _Traits
>
1548 struct _Hashtable_base
1549 : public _Hash_code_base
<_Key
, _Value
, _ExtractKey
, _H1
, _H2
, _Hash
,
1550 _Traits::__hash_cached::value
>,
1551 private _Hashtable_ebo_helper
<0, _Equal
>
1554 typedef _Key key_type
;
1555 typedef _Value value_type
;
1556 typedef _Equal key_equal
;
1557 typedef std::size_t size_type
;
1558 typedef std::ptrdiff_t difference_type
;
1560 using __traits_type
= _Traits
;
1561 using __hash_cached
= typename
__traits_type::__hash_cached
;
1562 using __constant_iterators
= typename
__traits_type::__constant_iterators
;
1563 using __unique_keys
= typename
__traits_type::__unique_keys
;
1565 using __hash_code_base
= _Hash_code_base
<_Key
, _Value
, _ExtractKey
,
1567 __hash_cached::value
>;
1569 using __hash_code
= typename
__hash_code_base::__hash_code
;
1570 using __node_type
= typename
__hash_code_base::__node_type
;
1572 using iterator
= __detail::_Node_iterator
<value_type
,
1573 __constant_iterators::value
,
1574 __hash_cached::value
>;
1576 using const_iterator
= __detail::_Node_const_iterator
<value_type
,
1577 __constant_iterators::value
,
1578 __hash_cached::value
>;
1580 using local_iterator
= __detail::_Local_iterator
<key_type
, value_type
,
1581 _ExtractKey
, _H1
, _H2
, _Hash
,
1582 __constant_iterators::value
,
1583 __hash_cached::value
>;
1585 using const_local_iterator
= __detail::_Local_const_iterator
<key_type
,
1587 _ExtractKey
, _H1
, _H2
, _Hash
,
1588 __constant_iterators::value
,
1589 __hash_cached::value
>;
1591 using __ireturn_type
= typename
std::conditional
<__unique_keys::value
,
1592 std::pair
<iterator
, bool>,
1595 using _EqualEBO
= _Hashtable_ebo_helper
<0, _Equal
>;
1596 using _EqualHelper
= _Equal_helper
<_Key
, _Value
, _ExtractKey
, _Equal
,
1597 __hash_code
, __hash_cached::value
>;
1600 using __node_base
= __detail::_Hash_node_base
;
1601 using __bucket_type
= __node_base
*;
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 is to combine a _Hash_node_base instance with an allocator
1791 * instance through inheritance to benefit from EBO when possible.
1793 template<typename _NodeAlloc
>
1794 struct _Before_begin
: public _NodeAlloc
1796 _Hash_node_base _M_node
;
1798 _Before_begin(const _Before_begin
&) = default;
1799 _Before_begin(_Before_begin
&&) = default;
1801 template<typename _Alloc
>
1802 _Before_begin(_Alloc
&& __a
)
1803 : _NodeAlloc(std::forward
<_Alloc
>(__a
))
1807 //@} hashtable-detail
1808 _GLIBCXX_END_NAMESPACE_VERSION
1809 } // namespace __detail
1812 #endif // _HASHTABLE_POLICY_H