libstdc++
hashtable_policy.h
Go to the documentation of this file.
1 // Internal policy header for unordered_set and unordered_map -*- C++ -*-
2 
3 // Copyright (C) 2010-2013 Free Software Foundation, Inc.
4 //
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)
9 // any later version.
10 
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.
15 
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.
19 
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/>.
24 
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}
29  */
30 
31 #ifndef _HASHTABLE_POLICY_H
32 #define _HASHTABLE_POLICY_H 1
33 
34 namespace std _GLIBCXX_VISIBILITY(default)
35 {
36 _GLIBCXX_BEGIN_NAMESPACE_VERSION
37 
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>
42  class _Hashtable;
43 
44 _GLIBCXX_END_NAMESPACE_VERSION
45 
46 namespace __detail
47 {
48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
49 
50  /**
51  * @defgroup hashtable-detail Base and Implementation Classes
52  * @ingroup unordered_associative_containers
53  * @{
54  */
55  template<typename _Key, typename _Value,
56  typename _ExtractKey, typename _Equal,
57  typename _H1, typename _H2, typename _Hash, typename _Traits>
59 
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,
66  { return 0; }
67 
68  template<class _Iterator>
69  inline typename std::iterator_traits<_Iterator>::difference_type
70  __distance_fw(_Iterator __first, _Iterator __last,
72  { return std::distance(__first, __last); }
73 
74  template<class _Iterator>
75  inline typename std::iterator_traits<_Iterator>::difference_type
76  __distance_fw(_Iterator __first, _Iterator __last)
77  {
78  typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
79  return __distance_fw(__first, __last, _Tag());
80  }
81 
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&>()))>
86  { };
87 
88  struct _Identity
89  {
90  template<typename _Tp>
91  _Tp&&
92  operator()(_Tp&& __x) const
93  { return std::forward<_Tp>(__x); }
94  };
95 
96  struct _Select1st
97  {
98  template<typename _Tp>
99  auto
100  operator()(_Tp&& __x) const
101  -> decltype(std::get<0>(std::forward<_Tp>(__x)))
102  { return std::get<0>(std::forward<_Tp>(__x)); }
103  };
104 
105  // Auxiliary types used for all instantiations of _Hashtable nodes
106  // and iterators.
107 
108  /**
109  * struct _Hashtable_traits
110  *
111  * Important traits for hash tables.
112  *
113  * @tparam _Cache_hash_code Boolean value. True if the value of
114  * the hash function is stored along with the value. This is a
115  * time-space tradeoff. Storing it may improve lookup speed by
116  * reducing the number of times we need to call the _Equal
117  * function.
118  *
119  * @tparam _Constant_iterators Boolean value. True if iterator and
120  * const_iterator are both constant iterator types. This is true
121  * for unordered_set and unordered_multiset, false for
122  * unordered_map and unordered_multimap.
123  *
124  * @tparam _Unique_keys Boolean value. True if the return value
125  * of _Hashtable::count(k) is always at most one, false if it may
126  * be an arbitrary number. This is true for unordered_set and
127  * unordered_map, false for unordered_multiset and
128  * unordered_multimap.
129  */
130  template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys>
132  {
133  template<bool _Cond>
134  using __bool_constant = integral_constant<bool, _Cond>;
135 
136  using __hash_cached = __bool_constant<_Cache_hash_code>;
137  using __constant_iterators = __bool_constant<_Constant_iterators>;
138  using __unique_keys = __bool_constant<_Unique_keys>;
139  };
140 
141  /**
142  * struct _Hash_node_base
143  *
144  * Nodes, used to wrap elements stored in the hash table. A policy
145  * template parameter of class template _Hashtable controls whether
146  * nodes also store a hash code. In some cases (e.g. strings) this
147  * may be a performance win.
148  */
150  {
151  _Hash_node_base* _M_nxt;
152 
153  _Hash_node_base() : _M_nxt() { }
154 
155  _Hash_node_base(_Hash_node_base* __next) : _M_nxt(__next) { }
156  };
157 
158  /**
159  * Primary template struct _Hash_node.
160  */
161  template<typename _Value, bool _Cache_hash_code>
162  struct _Hash_node;
163 
164  /**
165  * Specialization for nodes with caches, struct _Hash_node.
166  *
167  * Base class is __detail::_Hash_node_base.
168  */
169  template<typename _Value>
170  struct _Hash_node<_Value, true> : _Hash_node_base
171  {
172  _Value _M_v;
173  std::size_t _M_hash_code;
174 
175  template<typename... _Args>
176  _Hash_node(_Args&&... __args)
177  : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { }
178 
179  _Hash_node*
180  _M_next() const { return static_cast<_Hash_node*>(_M_nxt); }
181  };
182 
183  /**
184  * Specialization for nodes without caches, struct _Hash_node.
185  *
186  * Base class is __detail::_Hash_node_base.
187  */
188  template<typename _Value>
189  struct _Hash_node<_Value, false> : _Hash_node_base
190  {
191  _Value _M_v;
192 
193  template<typename... _Args>
194  _Hash_node(_Args&&... __args)
195  : _M_v(std::forward<_Args>(__args)...) { }
196 
197  _Hash_node*
198  _M_next() const { return static_cast<_Hash_node*>(_M_nxt); }
199  };
200 
201  /// Base class for node iterators.
202  template<typename _Value, bool _Cache_hash_code>
204  {
206 
207  __node_type* _M_cur;
208 
210  : _M_cur(__p) { }
211 
212  void
213  _M_incr()
214  { _M_cur = _M_cur->_M_next(); }
215  };
216 
217  template<typename _Value, bool _Cache_hash_code>
218  inline bool
219  operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
221  { return __x._M_cur == __y._M_cur; }
222 
223  template<typename _Value, bool _Cache_hash_code>
224  inline bool
225  operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
226  const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
227  { return __x._M_cur != __y._M_cur; }
228 
229  /// Node iterators, used to iterate through all the hashtable.
230  template<typename _Value, bool __constant_iterators, bool __cache>
232  : public _Node_iterator_base<_Value, __cache>
233  {
234  private:
236  using __node_type = typename __base_type::__node_type;
237 
238  public:
239  typedef _Value value_type;
240  typedef std::ptrdiff_t difference_type;
242 
243  using pointer = typename std::conditional<__constant_iterators,
244  const _Value*, _Value*>::type;
245 
246  using reference = typename std::conditional<__constant_iterators,
247  const _Value&, _Value&>::type;
248 
250  : __base_type(0) { }
251 
252  explicit
253  _Node_iterator(__node_type* __p)
254  : __base_type(__p) { }
255 
256  reference
257  operator*() const
258  { return this->_M_cur->_M_v; }
259 
260  pointer
261  operator->() const
262  { return std::__addressof(this->_M_cur->_M_v); }
263 
265  operator++()
266  {
267  this->_M_incr();
268  return *this;
269  }
270 
272  operator++(int)
273  {
274  _Node_iterator __tmp(*this);
275  this->_M_incr();
276  return __tmp;
277  }
278  };
279 
280  /// Node const_iterators, used to iterate through all the hashtable.
281  template<typename _Value, bool __constant_iterators, bool __cache>
283  : public _Node_iterator_base<_Value, __cache>
284  {
285  private:
287  using __node_type = typename __base_type::__node_type;
288 
289  public:
290  typedef _Value value_type;
291  typedef std::ptrdiff_t difference_type;
293 
294  typedef const _Value* pointer;
295  typedef const _Value& reference;
296 
298  : __base_type(0) { }
299 
300  explicit
301  _Node_const_iterator(__node_type* __p)
302  : __base_type(__p) { }
303 
304  _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
305  __cache>& __x)
306  : __base_type(__x._M_cur) { }
307 
308  reference
309  operator*() const
310  { return this->_M_cur->_M_v; }
311 
312  pointer
313  operator->() const
314  { return std::__addressof(this->_M_cur->_M_v); }
315 
317  operator++()
318  {
319  this->_M_incr();
320  return *this;
321  }
322 
324  operator++(int)
325  {
326  _Node_const_iterator __tmp(*this);
327  this->_M_incr();
328  return __tmp;
329  }
330  };
331 
332  // Many of class template _Hashtable's template parameters are policy
333  // classes. These are defaults for the policies.
334 
335  /// Default range hashing function: use division to fold a large number
336  /// into the range [0, N).
338  {
339  typedef std::size_t first_argument_type;
340  typedef std::size_t second_argument_type;
341  typedef std::size_t result_type;
342 
343  result_type
344  operator()(first_argument_type __num, second_argument_type __den) const
345  { return __num % __den; }
346  };
347 
348  /// Default ranged hash function H. In principle it should be a
349  /// function object composed from objects of type H1 and H2 such that
350  /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of
351  /// h1 and h2. So instead we'll just use a tag to tell class template
352  /// hashtable to do that composition.
354 
355  /// Default value for rehash policy. Bucket size is (usually) the
356  /// smallest prime that keeps the load factor small enough.
358  {
359  _Prime_rehash_policy(float __z = 1.0)
360  : _M_max_load_factor(__z), _M_next_resize(0) { }
361 
362  float
363  max_load_factor() const noexcept
364  { return _M_max_load_factor; }
365 
366  // Return a bucket size no smaller than n.
367  std::size_t
368  _M_next_bkt(std::size_t __n) const;
369 
370  // Return a bucket count appropriate for n elements
371  std::size_t
372  _M_bkt_for_elements(std::size_t __n) const
373  { return __builtin_ceil(__n / (long double)_M_max_load_factor); }
374 
375  // __n_bkt is current bucket count, __n_elt is current element count,
376  // and __n_ins is number of elements to be inserted. Do we need to
377  // increase bucket count? If so, return make_pair(true, n), where n
378  // is the new bucket count. If not, return make_pair(false, 0).
380  _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
381  std::size_t __n_ins) const;
382 
383  typedef std::size_t _State;
384 
385  _State
386  _M_state() const
387  { return _M_next_resize; }
388 
389  void
390  _M_reset(_State __state)
391  { _M_next_resize = __state; }
392 
393  enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
394 
395  static const std::size_t _S_growth_factor = 2;
396 
397  float _M_max_load_factor;
398  mutable std::size_t _M_next_resize;
399  };
400 
401  // Base classes for std::_Hashtable. We define these base classes
402  // because in some cases we want to do different things depending on
403  // the value of a policy class. In some cases the policy class
404  // affects which member functions and nested typedefs are defined;
405  // we handle that by specializing base class templates. Several of
406  // the base class templates need to access other members of class
407  // template _Hashtable, so we use a variant of the "Curiously
408  // Recurring Template Pattern" (CRTP) technique.
409 
410  /**
411  * Primary class template _Map_base.
412  *
413  * If the hashtable has a value type of the form pair<T1, T2> and a
414  * key extraction policy (_ExtractKey) that returns the first part
415  * of the pair, the hashtable gets a mapped_type typedef. If it
416  * satisfies those criteria and also has unique keys, then it also
417  * gets an operator[].
418  */
419  template<typename _Key, typename _Value, typename _Alloc,
420  typename _ExtractKey, typename _Equal,
421  typename _H1, typename _H2, typename _Hash,
422  typename _RehashPolicy, typename _Traits,
423  bool _Unique_keys = _Traits::__unique_keys::value>
424  struct _Map_base { };
425 
426  /// Partial specialization, __unique_keys set to false.
427  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
428  typename _H1, typename _H2, typename _Hash,
429  typename _RehashPolicy, typename _Traits>
430  struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
431  _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
432  {
433  using mapped_type = typename std::tuple_element<1, _Pair>::type;
434  };
435 
436  /// Partial specialization, __unique_keys set to true.
437  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
438  typename _H1, typename _H2, typename _Hash,
439  typename _RehashPolicy, typename _Traits>
440  struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
441  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
442  {
443  private:
444  using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair,
445  _Select1st,
446  _Equal, _H1, _H2, _Hash,
447  _Traits>;
448 
449  using __hashtable = _Hashtable<_Key, _Pair, _Alloc,
450  _Select1st, _Equal,
451  _H1, _H2, _Hash, _RehashPolicy, _Traits>;
452 
453  using __hash_code = typename __hashtable_base::__hash_code;
454  using __node_type = typename __hashtable_base::__node_type;
455 
456  public:
457  using key_type = typename __hashtable_base::key_type;
458  using iterator = typename __hashtable_base::iterator;
459  using mapped_type = typename std::tuple_element<1, _Pair>::type;
460 
461  mapped_type&
462  operator[](const key_type& __k);
463 
464  mapped_type&
465  operator[](key_type&& __k);
466 
467  // _GLIBCXX_RESOLVE_LIB_DEFECTS
468  // DR 761. unordered_map needs an at() member function.
469  mapped_type&
470  at(const key_type& __k);
471 
472  const mapped_type&
473  at(const key_type& __k) const;
474  };
475 
476  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
477  typename _H1, typename _H2, typename _Hash,
478  typename _RehashPolicy, typename _Traits>
479  typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
480  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
481  ::mapped_type&
482  _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
483  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
484  operator[](const key_type& __k)
485  {
486  __hashtable* __h = static_cast<__hashtable*>(this);
487  __hash_code __code = __h->_M_hash_code(__k);
488  std::size_t __n = __h->_M_bucket_index(__k, __code);
489  __node_type* __p = __h->_M_find_node(__n, __k, __code);
490 
491  if (!__p)
492  {
493  __p = __h->_M_allocate_node(std::piecewise_construct,
494  std::tuple<const key_type&>(__k),
495  std::tuple<>());
496  return __h->_M_insert_unique_node(__n, __code, __p)->second;
497  }
498 
499  return (__p->_M_v).second;
500  }
501 
502  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
503  typename _H1, typename _H2, typename _Hash,
504  typename _RehashPolicy, typename _Traits>
505  typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
506  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
507  ::mapped_type&
508  _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
509  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
510  operator[](key_type&& __k)
511  {
512  __hashtable* __h = static_cast<__hashtable*>(this);
513  __hash_code __code = __h->_M_hash_code(__k);
514  std::size_t __n = __h->_M_bucket_index(__k, __code);
515  __node_type* __p = __h->_M_find_node(__n, __k, __code);
516 
517  if (!__p)
518  {
519  __p = __h->_M_allocate_node(std::piecewise_construct,
520  std::forward_as_tuple(std::move(__k)),
521  std::tuple<>());
522  return __h->_M_insert_unique_node(__n, __code, __p)->second;
523  }
524 
525  return (__p->_M_v).second;
526  }
527 
528  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
529  typename _H1, typename _H2, typename _Hash,
530  typename _RehashPolicy, typename _Traits>
531  typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
532  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
533  ::mapped_type&
534  _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
535  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
536  at(const key_type& __k)
537  {
538  __hashtable* __h = static_cast<__hashtable*>(this);
539  __hash_code __code = __h->_M_hash_code(__k);
540  std::size_t __n = __h->_M_bucket_index(__k, __code);
541  __node_type* __p = __h->_M_find_node(__n, __k, __code);
542 
543  if (!__p)
544  __throw_out_of_range(__N("_Map_base::at"));
545  return (__p->_M_v).second;
546  }
547 
548  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
549  typename _H1, typename _H2, typename _Hash,
550  typename _RehashPolicy, typename _Traits>
551  const typename _Map_base<_Key, _Pair, _Alloc, _Select1st,
552  _Equal, _H1, _H2, _Hash, _RehashPolicy,
553  _Traits, true>::mapped_type&
554  _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
555  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
556  at(const key_type& __k) const
557  {
558  const __hashtable* __h = static_cast<const __hashtable*>(this);
559  __hash_code __code = __h->_M_hash_code(__k);
560  std::size_t __n = __h->_M_bucket_index(__k, __code);
561  __node_type* __p = __h->_M_find_node(__n, __k, __code);
562 
563  if (!__p)
564  __throw_out_of_range(__N("_Map_base::at"));
565  return (__p->_M_v).second;
566  }
567 
568  /**
569  * Primary class template _Insert_base.
570  *
571  * insert member functions appropriate to all _Hashtables.
572  */
573  template<typename _Key, typename _Value, typename _Alloc,
574  typename _ExtractKey, typename _Equal,
575  typename _H1, typename _H2, typename _Hash,
576  typename _RehashPolicy, typename _Traits>
578  {
579  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
580  _Equal, _H1, _H2, _Hash,
581  _RehashPolicy, _Traits>;
582 
583  using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
584  _Equal, _H1, _H2, _Hash,
585  _Traits>;
586 
587  using value_type = typename __hashtable_base::value_type;
588  using iterator = typename __hashtable_base::iterator;
589  using const_iterator = typename __hashtable_base::const_iterator;
590  using size_type = typename __hashtable_base::size_type;
591 
592  using __unique_keys = typename __hashtable_base::__unique_keys;
593  using __ireturn_type = typename __hashtable_base::__ireturn_type;
594  using __iconv_type = typename __hashtable_base::__iconv_type;
595 
596  __hashtable&
597  _M_conjure_hashtable()
598  { return *(static_cast<__hashtable*>(this)); }
599 
600  __ireturn_type
601  insert(const value_type& __v)
602  {
603  __hashtable& __h = _M_conjure_hashtable();
604  return __h._M_insert(__v, __unique_keys());
605  }
606 
607  iterator
608  insert(const_iterator, const value_type& __v)
609  { return __iconv_type()(insert(__v)); }
610 
611  void
612  insert(initializer_list<value_type> __l)
613  { this->insert(__l.begin(), __l.end()); }
614 
615  template<typename _InputIterator>
616  void
617  insert(_InputIterator __first, _InputIterator __last);
618  };
619 
620  template<typename _Key, typename _Value, typename _Alloc,
621  typename _ExtractKey, typename _Equal,
622  typename _H1, typename _H2, typename _Hash,
623  typename _RehashPolicy, typename _Traits>
624  template<typename _InputIterator>
625  void
626  _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
627  _RehashPolicy, _Traits>::
628  insert(_InputIterator __first, _InputIterator __last)
629  {
630  using __rehash_type = typename __hashtable::__rehash_type;
631  using __rehash_state = typename __hashtable::__rehash_state;
632  using pair_type = std::pair<bool, std::size_t>;
633 
634  size_type __n_elt = __detail::__distance_fw(__first, __last);
635 
636  __hashtable& __h = _M_conjure_hashtable();
637  __rehash_type& __rehash = __h._M_rehash_policy;
638  const __rehash_state& __saved_state = __rehash._M_state();
639  pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
640  __h._M_element_count,
641  __n_elt);
642 
643  if (__do_rehash.first)
644  __h._M_rehash(__do_rehash.second, __saved_state);
645 
646  for (; __first != __last; ++__first)
647  __h._M_insert(*__first, __unique_keys());
648  }
649 
650  /**
651  * Primary class template _Insert.
652  *
653  * Select insert member functions appropriate to _Hashtable policy choices.
654  */
655  template<typename _Key, typename _Value, typename _Alloc,
656  typename _ExtractKey, typename _Equal,
657  typename _H1, typename _H2, typename _Hash,
658  typename _RehashPolicy, typename _Traits,
659  bool _Constant_iterators = _Traits::__constant_iterators::value,
660  bool _Unique_keys = _Traits::__unique_keys::value>
661  struct _Insert;
662 
663  /// Specialization.
664  template<typename _Key, typename _Value, typename _Alloc,
665  typename _ExtractKey, typename _Equal,
666  typename _H1, typename _H2, typename _Hash,
667  typename _RehashPolicy, typename _Traits>
668  struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
669  _RehashPolicy, _Traits, true, true>
670  : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
671  _H1, _H2, _Hash, _RehashPolicy, _Traits>
672  {
673  using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
674  _Equal, _H1, _H2, _Hash,
675  _RehashPolicy, _Traits>;
676  using value_type = typename __base_type::value_type;
677  using iterator = typename __base_type::iterator;
678  using const_iterator = typename __base_type::const_iterator;
679 
680  using __unique_keys = typename __base_type::__unique_keys;
681  using __hashtable = typename __base_type::__hashtable;
682 
683  using __base_type::insert;
684 
686  insert(value_type&& __v)
687  {
688  __hashtable& __h = this->_M_conjure_hashtable();
689  return __h._M_insert(std::move(__v), __unique_keys());
690  }
691 
692  iterator
693  insert(const_iterator, value_type&& __v)
694  { return insert(std::move(__v)).first; }
695  };
696 
697  /// Specialization.
698  template<typename _Key, typename _Value, typename _Alloc,
699  typename _ExtractKey, typename _Equal,
700  typename _H1, typename _H2, typename _Hash,
701  typename _RehashPolicy, typename _Traits>
702  struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
703  _RehashPolicy, _Traits, true, false>
704  : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
705  _H1, _H2, _Hash, _RehashPolicy, _Traits>
706  {
707  using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
708  _Equal, _H1, _H2, _Hash,
709  _RehashPolicy, _Traits>;
710  using value_type = typename __base_type::value_type;
711  using iterator = typename __base_type::iterator;
712  using const_iterator = typename __base_type::const_iterator;
713 
714  using __unique_keys = typename __base_type::__unique_keys;
715  using __hashtable = typename __base_type::__hashtable;
716 
717  using __base_type::insert;
718 
719  iterator
720  insert(value_type&& __v)
721  {
722  __hashtable& __h = this->_M_conjure_hashtable();
723  return __h._M_insert(std::move(__v), __unique_keys());
724  }
725 
726  iterator
727  insert(const_iterator, value_type&& __v)
728  { return insert(std::move(__v)); }
729  };
730 
731  /// Specialization.
732  template<typename _Key, typename _Value, typename _Alloc,
733  typename _ExtractKey, typename _Equal,
734  typename _H1, typename _H2, typename _Hash,
735  typename _RehashPolicy, typename _Traits, bool _Unique_keys>
736  struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
737  _RehashPolicy, _Traits, false, _Unique_keys>
738  : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
739  _H1, _H2, _Hash, _RehashPolicy, _Traits>
740  {
741  using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
742  _Equal, _H1, _H2, _Hash,
743  _RehashPolicy, _Traits>;
744  using value_type = typename __base_type::value_type;
745  using iterator = typename __base_type::iterator;
746  using const_iterator = typename __base_type::const_iterator;
747 
748  using __unique_keys = typename __base_type::__unique_keys;
749  using __hashtable = typename __base_type::__hashtable;
750  using __ireturn_type = typename __base_type::__ireturn_type;
751  using __iconv_type = typename __base_type::__iconv_type;
752 
753  using __base_type::insert;
754 
755  template<typename _Pair>
756  using __is_cons = std::is_constructible<value_type, _Pair&&>;
757 
758  template<typename _Pair>
759  using _IFcons = std::enable_if<__is_cons<_Pair>::value>;
760 
761  template<typename _Pair>
762  using _IFconsp = typename _IFcons<_Pair>::type;
763 
764  template<typename _Pair, typename = _IFconsp<_Pair>>
765  __ireturn_type
766  insert(_Pair&& __v)
767  {
768  __hashtable& __h = this->_M_conjure_hashtable();
769  return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
770  }
771 
772  template<typename _Pair, typename = _IFconsp<_Pair>>
773  iterator
774  insert(const_iterator, _Pair&& __v)
775  { return __iconv_type()(insert(std::forward<_Pair>(__v))); }
776  };
777 
778  /**
779  * Primary class template _Rehash_base.
780  *
781  * Give hashtable the max_load_factor functions and reserve iff the
782  * rehash policy is _Prime_rehash_policy.
783  */
784  template<typename _Key, typename _Value, typename _Alloc,
785  typename _ExtractKey, typename _Equal,
786  typename _H1, typename _H2, typename _Hash,
787  typename _RehashPolicy, typename _Traits>
788  struct _Rehash_base;
789 
790  /// Specialization.
791  template<typename _Key, typename _Value, typename _Alloc,
792  typename _ExtractKey, typename _Equal,
793  typename _H1, typename _H2, typename _Hash, typename _Traits>
794  struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
795  _H1, _H2, _Hash, _Prime_rehash_policy, _Traits>
796  {
797  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
798  _Equal, _H1, _H2, _Hash,
799  _Prime_rehash_policy, _Traits>;
800 
801  float
802  max_load_factor() const noexcept
803  {
804  const __hashtable* __this = static_cast<const __hashtable*>(this);
805  return __this->__rehash_policy().max_load_factor();
806  }
807 
808  void
809  max_load_factor(float __z)
810  {
811  __hashtable* __this = static_cast<__hashtable*>(this);
812  __this->__rehash_policy(_Prime_rehash_policy(__z));
813  }
814 
815  void
816  reserve(std::size_t __n)
817  {
818  __hashtable* __this = static_cast<__hashtable*>(this);
819  __this->rehash(__builtin_ceil(__n / max_load_factor()));
820  }
821  };
822 
823  /**
824  * Primary class template _Hashtable_ebo_helper.
825  *
826  * Helper class using EBO when it is not forbidden, type is not
827  * final, and when it worth it, type is empty.
828  */
829  template<int _Nm, typename _Tp,
830  bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
832 
833  /// Specialization using EBO.
834  template<int _Nm, typename _Tp>
835  struct _Hashtable_ebo_helper<_Nm, _Tp, true>
836  : private _Tp
837  {
838  _Hashtable_ebo_helper() = default;
839 
840  _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp)
841  { }
842 
843  static const _Tp&
844  _S_cget(const _Hashtable_ebo_helper& __eboh)
845  { return static_cast<const _Tp&>(__eboh); }
846 
847  static _Tp&
848  _S_get(_Hashtable_ebo_helper& __eboh)
849  { return static_cast<_Tp&>(__eboh); }
850  };
851 
852  /// Specialization not using EBO.
853  template<int _Nm, typename _Tp>
854  struct _Hashtable_ebo_helper<_Nm, _Tp, false>
855  {
856  _Hashtable_ebo_helper() = default;
857 
858  _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp)
859  { }
860 
861  static const _Tp&
862  _S_cget(const _Hashtable_ebo_helper& __eboh)
863  { return __eboh._M_tp; }
864 
865  static _Tp&
866  _S_get(_Hashtable_ebo_helper& __eboh)
867  { return __eboh._M_tp; }
868 
869  private:
870  _Tp _M_tp;
871  };
872 
873  /**
874  * Primary class template _Local_iterator_base.
875  *
876  * Base class for local iterators, used to iterate within a bucket
877  * but not between buckets.
878  */
879  template<typename _Key, typename _Value, typename _ExtractKey,
880  typename _H1, typename _H2, typename _Hash,
881  bool __cache_hash_code>
883 
884  /**
885  * Primary class template _Hash_code_base.
886  *
887  * Encapsulates two policy issues that aren't quite orthogonal.
888  * (1) the difference between using a ranged hash function and using
889  * the combination of a hash function and a range-hashing function.
890  * In the former case we don't have such things as hash codes, so
891  * we have a dummy type as placeholder.
892  * (2) Whether or not we cache hash codes. Caching hash codes is
893  * meaningless if we have a ranged hash function.
894  *
895  * We also put the key extraction objects here, for convenience.
896  * Each specialization derives from one or more of the template
897  * parameters to benefit from Ebo. This is important as this type
898  * is inherited in some cases by the _Local_iterator_base type used
899  * to implement local_iterator and const_local_iterator. As with
900  * any iterator type we prefer to make it as small as possible.
901  *
902  * Primary template is unused except as a hook for specializations.
903  */
904  template<typename _Key, typename _Value, typename _ExtractKey,
905  typename _H1, typename _H2, typename _Hash,
906  bool __cache_hash_code>
908 
909  /// Specialization: ranged hash function, no caching hash codes. H1
910  /// and H2 are provided but ignored. We define a dummy hash code type.
911  template<typename _Key, typename _Value, typename _ExtractKey,
912  typename _H1, typename _H2, typename _Hash>
913  struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
914  : private _Hashtable_ebo_helper<0, _ExtractKey>,
915  private _Hashtable_ebo_helper<1, _Hash>
916  {
917  private:
920 
921  protected:
922  typedef void* __hash_code;
924 
925  // We need the default constructor for the local iterators.
926  _Hash_code_base() = default;
927 
928  _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&,
929  const _Hash& __h)
930  : __ebo_extract_key(__ex), __ebo_hash(__h) { }
931 
932  __hash_code
933  _M_hash_code(const _Key& __key) const
934  { return 0; }
935 
936  std::size_t
937  _M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const
938  { return _M_ranged_hash()(__k, __n); }
939 
940  std::size_t
941  _M_bucket_index(const __node_type* __p, std::size_t __n) const
942  { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); }
943 
944  void
945  _M_store_code(__node_type*, __hash_code) const
946  { }
947 
948  void
949  _M_copy_code(__node_type*, const __node_type*) const
950  { }
951 
952  void
953  _M_swap(_Hash_code_base& __x)
954  {
955  std::swap(_M_extract(), __x._M_extract());
956  std::swap(_M_ranged_hash(), __x._M_ranged_hash());
957  }
958 
959  const _ExtractKey&
960  _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
961 
962  _ExtractKey&
963  _M_extract() { return __ebo_extract_key::_S_get(*this); }
964 
965  const _Hash&
966  _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); }
967 
968  _Hash&
969  _M_ranged_hash() { return __ebo_hash::_S_get(*this); }
970  };
971 
972  // No specialization for ranged hash function while caching hash codes.
973  // That combination is meaningless, and trying to do it is an error.
974 
975  /// Specialization: ranged hash function, cache hash codes. This
976  /// combination is meaningless, so we provide only a declaration
977  /// and no definition.
978  template<typename _Key, typename _Value, typename _ExtractKey,
979  typename _H1, typename _H2, typename _Hash>
980  struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
981 
982  /// Specialization: hash function and range-hashing function, no
983  /// caching of hash codes.
984  /// Provides typedef and accessor required by C++ 11.
985  template<typename _Key, typename _Value, typename _ExtractKey,
986  typename _H1, typename _H2>
987  struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
988  _Default_ranged_hash, false>
989  : private _Hashtable_ebo_helper<0, _ExtractKey>,
990  private _Hashtable_ebo_helper<1, _H1>,
991  private _Hashtable_ebo_helper<2, _H2>
992  {
993  private:
997 
998  public:
999  typedef _H1 hasher;
1000 
1001  hasher
1002  hash_function() const
1003  { return _M_h1(); }
1004 
1005  protected:
1006  typedef std::size_t __hash_code;
1008 
1009  // We need the default constructor for the local iterators.
1010  _Hash_code_base() = default;
1011 
1012  _Hash_code_base(const _ExtractKey& __ex,
1013  const _H1& __h1, const _H2& __h2,
1014  const _Default_ranged_hash&)
1015  : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
1016 
1017  __hash_code
1018  _M_hash_code(const _Key& __k) const
1019  { return _M_h1()(__k); }
1020 
1021  std::size_t
1022  _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const
1023  { return _M_h2()(__c, __n); }
1024 
1025  std::size_t
1026  _M_bucket_index(const __node_type* __p,
1027  std::size_t __n) const
1028  { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); }
1029 
1030  void
1031  _M_store_code(__node_type*, __hash_code) const
1032  { }
1033 
1034  void
1035  _M_copy_code(__node_type*, const __node_type*) const
1036  { }
1037 
1038  void
1039  _M_swap(_Hash_code_base& __x)
1040  {
1041  std::swap(_M_extract(), __x._M_extract());
1042  std::swap(_M_h1(), __x._M_h1());
1043  std::swap(_M_h2(), __x._M_h2());
1044  }
1045 
1046  const _ExtractKey&
1047  _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1048 
1049  _ExtractKey&
1050  _M_extract() { return __ebo_extract_key::_S_get(*this); }
1051 
1052  const _H1&
1053  _M_h1() const { return __ebo_h1::_S_cget(*this); }
1054 
1055  _H1&
1056  _M_h1() { return __ebo_h1::_S_get(*this); }
1057 
1058  const _H2&
1059  _M_h2() const { return __ebo_h2::_S_cget(*this); }
1060 
1061  _H2&
1062  _M_h2() { return __ebo_h2::_S_get(*this); }
1063  };
1064 
1065  /// Specialization: hash function and range-hashing function,
1066  /// caching hash codes. H is provided but ignored. Provides
1067  /// typedef and accessor required by C++ 11.
1068  template<typename _Key, typename _Value, typename _ExtractKey,
1069  typename _H1, typename _H2>
1070  struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
1071  _Default_ranged_hash, true>
1072  : private _Hashtable_ebo_helper<0, _ExtractKey>,
1073  private _Hashtable_ebo_helper<1, _H1>,
1074  private _Hashtable_ebo_helper<2, _H2>
1075  {
1076  private:
1077  // Gives access to _M_h2() to the local iterator implementation.
1078  friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
1079  _Default_ranged_hash, true>;
1080 
1084 
1085  public:
1086  typedef _H1 hasher;
1087 
1088  hasher
1089  hash_function() const
1090  { return _M_h1(); }
1091 
1092  protected:
1093  typedef std::size_t __hash_code;
1095 
1096  _Hash_code_base(const _ExtractKey& __ex,
1097  const _H1& __h1, const _H2& __h2,
1098  const _Default_ranged_hash&)
1099  : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
1100 
1101  __hash_code
1102  _M_hash_code(const _Key& __k) const
1103  { return _M_h1()(__k); }
1104 
1105  std::size_t
1106  _M_bucket_index(const _Key&, __hash_code __c,
1107  std::size_t __n) const
1108  { return _M_h2()(__c, __n); }
1109 
1110  std::size_t
1111  _M_bucket_index(const __node_type* __p, std::size_t __n) const
1112  { return _M_h2()(__p->_M_hash_code, __n); }
1113 
1114  void
1115  _M_store_code(__node_type* __n, __hash_code __c) const
1116  { __n->_M_hash_code = __c; }
1117 
1118  void
1119  _M_copy_code(__node_type* __to, const __node_type* __from) const
1120  { __to->_M_hash_code = __from->_M_hash_code; }
1121 
1122  void
1123  _M_swap(_Hash_code_base& __x)
1124  {
1125  std::swap(_M_extract(), __x._M_extract());
1126  std::swap(_M_h1(), __x._M_h1());
1127  std::swap(_M_h2(), __x._M_h2());
1128  }
1129 
1130  const _ExtractKey&
1131  _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1132 
1133  _ExtractKey&
1134  _M_extract() { return __ebo_extract_key::_S_get(*this); }
1135 
1136  const _H1&
1137  _M_h1() const { return __ebo_h1::_S_cget(*this); }
1138 
1139  _H1&
1140  _M_h1() { return __ebo_h1::_S_get(*this); }
1141 
1142  const _H2&
1143  _M_h2() const { return __ebo_h2::_S_cget(*this); }
1144 
1145  _H2&
1146  _M_h2() { return __ebo_h2::_S_get(*this); }
1147  };
1148 
1149  /**
1150  * Primary class template _Equal_helper.
1151  *
1152  */
1153  template <typename _Key, typename _Value, typename _ExtractKey,
1154  typename _Equal, typename _HashCodeType,
1155  bool __cache_hash_code>
1157 
1158  /// Specialization.
1159  template<typename _Key, typename _Value, typename _ExtractKey,
1160  typename _Equal, typename _HashCodeType>
1161  struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true>
1162  {
1163  static bool
1164  _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
1165  const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n)
1166  { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v)); }
1167  };
1168 
1169  /// Specialization.
1170  template<typename _Key, typename _Value, typename _ExtractKey,
1171  typename _Equal, typename _HashCodeType>
1172  struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false>
1173  {
1174  static bool
1175  _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
1176  const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n)
1177  { return __eq(__k, __extract(__n->_M_v)); }
1178  };
1179 
1180 
1181  /// Specialization.
1182  template<typename _Key, typename _Value, typename _ExtractKey,
1183  typename _H1, typename _H2, typename _Hash>
1184  struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1185  _H1, _H2, _Hash, true>
1186  : private _Hashtable_ebo_helper<0, _H2>
1187  {
1188  protected:
1190  using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1191  _H1, _H2, _Hash, true>;
1192 
1193  public:
1194  _Local_iterator_base() = default;
1197  std::size_t __bkt, std::size_t __bkt_count)
1198  : __base_type(__base._M_h2()),
1199  _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1200 
1201  void
1202  _M_incr()
1203  {
1204  _M_cur = _M_cur->_M_next();
1205  if (_M_cur)
1206  {
1207  std::size_t __bkt
1208  = __base_type::_S_get(*this)(_M_cur->_M_hash_code,
1209  _M_bucket_count);
1210  if (__bkt != _M_bucket)
1211  _M_cur = nullptr;
1212  }
1213  }
1214 
1215  _Hash_node<_Value, true>* _M_cur;
1216  std::size_t _M_bucket;
1217  std::size_t _M_bucket_count;
1218  };
1219 
1220  /// Specialization.
1221  template<typename _Key, typename _Value, typename _ExtractKey,
1222  typename _H1, typename _H2, typename _Hash>
1223  struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1224  _H1, _H2, _Hash, false>
1225  : private _Hash_code_base<_Key, _Value, _ExtractKey,
1226  _H1, _H2, _Hash, false>
1227  {
1228  protected:
1229  using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1230  _H1, _H2, _Hash, false>;
1231 
1232  public:
1233  _Local_iterator_base() = default;
1236  std::size_t __bkt, std::size_t __bkt_count)
1237  : __hash_code_base(__base),
1238  _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1239 
1240  void
1241  _M_incr()
1242  {
1243  _M_cur = _M_cur->_M_next();
1244  if (_M_cur)
1245  {
1246  std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
1247  if (__bkt != _M_bucket)
1248  _M_cur = nullptr;
1249  }
1250  }
1251 
1252  _Hash_node<_Value, false>* _M_cur;
1253  std::size_t _M_bucket;
1254  std::size_t _M_bucket_count;
1255  };
1256 
1257  template<typename _Key, typename _Value, typename _ExtractKey,
1258  typename _H1, typename _H2, typename _Hash, bool __cache>
1259  inline bool
1260  operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
1261  _H1, _H2, _Hash, __cache>& __x,
1262  const _Local_iterator_base<_Key, _Value, _ExtractKey,
1263  _H1, _H2, _Hash, __cache>& __y)
1264  { return __x._M_cur == __y._M_cur; }
1265 
1266  template<typename _Key, typename _Value, typename _ExtractKey,
1267  typename _H1, typename _H2, typename _Hash, bool __cache>
1268  inline bool
1269  operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
1270  _H1, _H2, _Hash, __cache>& __x,
1271  const _Local_iterator_base<_Key, _Value, _ExtractKey,
1272  _H1, _H2, _Hash, __cache>& __y)
1273  { return __x._M_cur != __y._M_cur; }
1274 
1275  /// local iterators
1276  template<typename _Key, typename _Value, typename _ExtractKey,
1277  typename _H1, typename _H2, typename _Hash,
1278  bool __constant_iterators, bool __cache>
1280  : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1281  _H1, _H2, _Hash, __cache>
1282  {
1283  private:
1284  using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1285  _H1, _H2, _Hash, __cache>;
1286  using __hash_code_base = typename __base_type::__hash_code_base;
1287  public:
1288  typedef _Value value_type;
1289  typedef typename std::conditional<__constant_iterators,
1290  const _Value*, _Value*>::type
1291  pointer;
1292  typedef typename std::conditional<__constant_iterators,
1293  const _Value&, _Value&>::type
1294  reference;
1295  typedef std::ptrdiff_t difference_type;
1297 
1298  _Local_iterator() = default;
1299 
1300  _Local_iterator(const __hash_code_base& __base,
1302  std::size_t __bkt, std::size_t __bkt_count)
1303  : __base_type(__base, __p, __bkt, __bkt_count)
1304  { }
1305 
1306  reference
1307  operator*() const
1308  { return this->_M_cur->_M_v; }
1309 
1310  pointer
1311  operator->() const
1312  { return std::__addressof(this->_M_cur->_M_v); }
1313 
1315  operator++()
1316  {
1317  this->_M_incr();
1318  return *this;
1319  }
1320 
1322  operator++(int)
1323  {
1324  _Local_iterator __tmp(*this);
1325  this->_M_incr();
1326  return __tmp;
1327  }
1328  };
1329 
1330  /// local const_iterators
1331  template<typename _Key, typename _Value, typename _ExtractKey,
1332  typename _H1, typename _H2, typename _Hash,
1333  bool __constant_iterators, bool __cache>
1335  : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1336  _H1, _H2, _Hash, __cache>
1337  {
1338  private:
1339  using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1340  _H1, _H2, _Hash, __cache>;
1341  using __hash_code_base = typename __base_type::__hash_code_base;
1342 
1343  public:
1344  typedef _Value value_type;
1345  typedef const _Value* pointer;
1346  typedef const _Value& reference;
1347  typedef std::ptrdiff_t difference_type;
1349 
1350  _Local_const_iterator() = default;
1351 
1352  _Local_const_iterator(const __hash_code_base& __base,
1354  std::size_t __bkt, std::size_t __bkt_count)
1355  : __base_type(__base, __p, __bkt, __bkt_count)
1356  { }
1357 
1358  _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
1359  _H1, _H2, _Hash,
1360  __constant_iterators,
1361  __cache>& __x)
1362  : __base_type(__x)
1363  { }
1364 
1365  reference
1366  operator*() const
1367  { return this->_M_cur->_M_v; }
1368 
1369  pointer
1370  operator->() const
1371  { return std::__addressof(this->_M_cur->_M_v); }
1372 
1374  operator++()
1375  {
1376  this->_M_incr();
1377  return *this;
1378  }
1379 
1381  operator++(int)
1382  {
1383  _Local_const_iterator __tmp(*this);
1384  this->_M_incr();
1385  return __tmp;
1386  }
1387  };
1388 
1389  /**
1390  * Primary class template _Hashtable_base.
1391  *
1392  * Helper class adding management of _Equal functor to
1393  * _Hash_code_base type.
1394  *
1395  * Base class templates are:
1396  * - __detail::_Hash_code_base
1397  * - __detail::_Hashtable_ebo_helper
1398  */
1399  template<typename _Key, typename _Value,
1400  typename _ExtractKey, typename _Equal,
1401  typename _H1, typename _H2, typename _Hash, typename _Traits>
1402  struct _Hashtable_base
1403  : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
1404  _Traits::__hash_cached::value>,
1405  private _Hashtable_ebo_helper<0, _Equal>
1406  {
1407  public:
1408  typedef _Key key_type;
1409  typedef _Value value_type;
1410  typedef _Equal key_equal;
1411  typedef std::size_t size_type;
1412  typedef std::ptrdiff_t difference_type;
1413 
1414  using __traits_type = _Traits;
1415  using __hash_cached = typename __traits_type::__hash_cached;
1416  using __constant_iterators = typename __traits_type::__constant_iterators;
1417  using __unique_keys = typename __traits_type::__unique_keys;
1418 
1419  using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1420  _H1, _H2, _Hash,
1421  __hash_cached::value>;
1422 
1423  using __hash_code = typename __hash_code_base::__hash_code;
1424  using __node_type = typename __hash_code_base::__node_type;
1425 
1426  using iterator = __detail::_Node_iterator<value_type,
1427  __constant_iterators::value,
1428  __hash_cached::value>;
1429 
1430  using const_iterator = __detail::_Node_const_iterator<value_type,
1431  __constant_iterators::value,
1432  __hash_cached::value>;
1433 
1434  using local_iterator = __detail::_Local_iterator<key_type, value_type,
1435  _ExtractKey, _H1, _H2, _Hash,
1436  __constant_iterators::value,
1437  __hash_cached::value>;
1438 
1439  using const_local_iterator = __detail::_Local_const_iterator<key_type,
1440  value_type,
1441  _ExtractKey, _H1, _H2, _Hash,
1442  __constant_iterators::value,
1443  __hash_cached::value>;
1444 
1445  using __ireturn_type = typename std::conditional<__unique_keys::value,
1447  iterator>::type;
1448 
1449  using __iconv_type = typename std::conditional<__unique_keys::value,
1450  _Select1st, _Identity
1451  >::type;
1452  private:
1453  using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>;
1454  using _EqualHelper = _Equal_helper<_Key, _Value, _ExtractKey, _Equal,
1455  __hash_code, __hash_cached::value>;
1456 
1457  protected:
1458  using __node_base = __detail::_Hash_node_base;
1459  using __bucket_type = __node_base*;
1460 
1461  _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2,
1462  const _Hash& __hash, const _Equal& __eq)
1463  : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
1464  { }
1465 
1466  bool
1467  _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const
1468  {
1469  return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
1470  __k, __c, __n);
1471  }
1472 
1473  void
1474  _M_swap(_Hashtable_base& __x)
1475  {
1476  __hash_code_base::_M_swap(__x);
1477  std::swap(_M_eq(), __x._M_eq());
1478  }
1479 
1480  const _Equal&
1481  _M_eq() const { return _EqualEBO::_S_cget(*this); }
1482 
1483  _Equal&
1484  _M_eq() { return _EqualEBO::_S_get(*this); }
1485  };
1486 
1487  /**
1488  * struct _Equality_base.
1489  *
1490  * Common types and functions for class _Equality.
1491  */
1493  {
1494  protected:
1495  template<typename _Uiterator>
1496  static bool
1497  _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1498  };
1499 
1500  // See std::is_permutation in N3068.
1501  template<typename _Uiterator>
1502  bool
1503  _Equality_base::
1504  _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1505  _Uiterator __first2)
1506  {
1507  for (; __first1 != __last1; ++__first1, ++__first2)
1508  if (!(*__first1 == *__first2))
1509  break;
1510 
1511  if (__first1 == __last1)
1512  return true;
1513 
1514  _Uiterator __last2 = __first2;
1515  std::advance(__last2, std::distance(__first1, __last1));
1516 
1517  for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1518  {
1519  _Uiterator __tmp = __first1;
1520  while (__tmp != __it1 && !bool(*__tmp == *__it1))
1521  ++__tmp;
1522 
1523  // We've seen this one before.
1524  if (__tmp != __it1)
1525  continue;
1526 
1527  std::ptrdiff_t __n2 = 0;
1528  for (__tmp = __first2; __tmp != __last2; ++__tmp)
1529  if (*__tmp == *__it1)
1530  ++__n2;
1531 
1532  if (!__n2)
1533  return false;
1534 
1535  std::ptrdiff_t __n1 = 0;
1536  for (__tmp = __it1; __tmp != __last1; ++__tmp)
1537  if (*__tmp == *__it1)
1538  ++__n1;
1539 
1540  if (__n1 != __n2)
1541  return false;
1542  }
1543  return true;
1544  }
1545 
1546  /**
1547  * Primary class template _Equality.
1548  *
1549  * This is for implementing equality comparison for unordered
1550  * containers, per N3068, by John Lakos and Pablo Halpern.
1551  * Algorithmically, we follow closely the reference implementations
1552  * therein.
1553  */
1554  template<typename _Key, typename _Value, typename _Alloc,
1555  typename _ExtractKey, typename _Equal,
1556  typename _H1, typename _H2, typename _Hash,
1557  typename _RehashPolicy, typename _Traits,
1558  bool _Unique_keys = _Traits::__unique_keys::value>
1559  struct _Equality;
1560 
1561  /// Specialization.
1562  template<typename _Key, typename _Value, typename _Alloc,
1563  typename _ExtractKey, typename _Equal,
1564  typename _H1, typename _H2, typename _Hash,
1565  typename _RehashPolicy, typename _Traits>
1566  struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1567  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
1568  {
1569  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1570  _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1571 
1572  bool
1573  _M_equal(const __hashtable&) const;
1574  };
1575 
1576  template<typename _Key, typename _Value, typename _Alloc,
1577  typename _ExtractKey, typename _Equal,
1578  typename _H1, typename _H2, typename _Hash,
1579  typename _RehashPolicy, typename _Traits>
1580  bool
1581  _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1582  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
1583  _M_equal(const __hashtable& __other) const
1584  {
1585  const __hashtable* __this = static_cast<const __hashtable*>(this);
1586 
1587  if (__this->size() != __other.size())
1588  return false;
1589 
1590  for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1591  {
1592  const auto __ity = __other.find(_ExtractKey()(*__itx));
1593  if (__ity == __other.end() || !bool(*__ity == *__itx))
1594  return false;
1595  }
1596  return true;
1597  }
1598 
1599  /// Specialization.
1600  template<typename _Key, typename _Value, typename _Alloc,
1601  typename _ExtractKey, typename _Equal,
1602  typename _H1, typename _H2, typename _Hash,
1603  typename _RehashPolicy, typename _Traits>
1604  struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1605  _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1606  : public _Equality_base
1607  {
1608  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1609  _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1610 
1611  bool
1612  _M_equal(const __hashtable&) const;
1613  };
1614 
1615  template<typename _Key, typename _Value, typename _Alloc,
1616  typename _ExtractKey, typename _Equal,
1617  typename _H1, typename _H2, typename _Hash,
1618  typename _RehashPolicy, typename _Traits>
1619  bool
1620  _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1621  _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
1622  _M_equal(const __hashtable& __other) const
1623  {
1624  const __hashtable* __this = static_cast<const __hashtable*>(this);
1625 
1626  if (__this->size() != __other.size())
1627  return false;
1628 
1629  for (auto __itx = __this->begin(); __itx != __this->end();)
1630  {
1631  const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
1632  const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
1633 
1634  if (std::distance(__xrange.first, __xrange.second)
1635  != std::distance(__yrange.first, __yrange.second))
1636  return false;
1637 
1638  if (!_S_is_permutation(__xrange.first, __xrange.second,
1639  __yrange.first))
1640  return false;
1641 
1642  __itx = __xrange.second;
1643  }
1644  return true;
1645  }
1646 
1647  /**
1648  * This type is to combine a _Hash_node_base instance with an allocator
1649  * instance through inheritance to benefit from EBO when possible.
1650  */
1651  template<typename _NodeAlloc>
1652  struct _Before_begin : public _NodeAlloc
1653  {
1654  _Hash_node_base _M_node;
1655 
1656  _Before_begin(const _Before_begin&) = default;
1657  _Before_begin(_Before_begin&&) = default;
1658 
1659  template<typename _Alloc>
1660  _Before_begin(_Alloc&& __a)
1661  : _NodeAlloc(std::forward<_Alloc>(__a))
1662  { }
1663  };
1664 
1665  //@} hashtable-detail
1666 _GLIBCXX_END_NAMESPACE_VERSION
1667 } // namespace __detail
1668 } // namespace std
1669 
1670 #endif // _HASHTABLE_POLICY_H
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition: move.h:76
constexpr piecewise_construct_t piecewise_construct
piecewise_construct
Definition: stl_pair.h:79
ISO C++ entities toplevel namespace is std.
Default ranged hash function H. In principle it should be a function object composed from objects of ...
Marking input iterators.
Node iterators, used to iterate through all the hashtable.
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
Node const_iterators, used to iterate through all the hashtable.
Base class for node iterators.
Common iterator class.
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
Forward iterators support a superset of input iterator operations.
Specialization: ranged hash function, no caching hash codes. H1 and H2 are provided but ignored...
void swap(_Tp &, _Tp &) noexcept(__and_< is_nothrow_move_constructible< _Tp >, is_nothrow_move_assignable< _Tp >>::value)
Swaps two values.
Definition: move.h:166
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
Definition: functions.h:446
Default range hashing function: use division to fold a large number into the range [0...