// Internal header for TR1 unordered_set and unordered_map -*- C++ -*-// Copyright (C) 2005, 2006 Free Software Foundation, Inc.//// This file is part of the GNU ISO C++ Library. This library is free// software; you can redistribute it and/or modify it under the// terms of the GNU General Public License as published by the// Free Software Foundation; either version 2, or (at your option)// any later version.// This library is distributed in the hope that it will be useful,// but WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the// GNU General Public License for more details.// You should have received a copy of the GNU General Public License along// with this library; see the file COPYING. If not, write to the Free// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,// USA.// As a special exception, you may use this file as part of a free software// library without restriction. Specifically, if other files instantiate// templates or use macros or inline functions from this file, or you compile// this file and link it with other files to produce an executable, this// file does not by itself cause the resulting executable to be covered by// the GNU General Public License. This exception does not however// invalidate any other reasons why the executable file might be covered by// the GNU General Public License./** @file* This is a TR1 C++ Library header.*/// This header file defines std::tr1::hashtable, which is used to// implement std::tr1::unordered_set, std::tr1::unordered_map,// std::tr1::unordered_multiset, and std::tr1::unordered_multimap.// hashtable has many template parameters, partly to accommodate// the differences between those four classes and partly to// accommodate policy choices that go beyond what TR1 calls for.// ??? Arguably this should be Internal::hashtable, not std::tr1::hashtable.// Class template hashtable attempts to encapsulate all reasonable// variation among hash tables that use chaining. It does not handle// open addressing.// References:// M. Austern, "A Proposal to Add Hash Tables to the Standard// Library (revision 4)," WG21 Document N1456=03-0039, 2003.// D. E. Knuth, The Art of Computer Programming, v. 3, Sorting and Searching.// A. Tavori and V. Dreizin, "Generic Associative Containers", 2004.// ??? Full citation?#ifndef GNU_LIBSTDCXX_TR1_HASHTABLE_#define GNU_LIBSTDCXX_TR1_HASHTABLE_#include <utility> // For std::pair#include <iterator>#include <cstddef>#include <cstdlib>#include <cmath>#include <bits/functexcept.h>#include <tr1/type_traits> // For true_type and false_type//----------------------------------------------------------------------// General utilitiesnamespace Internal{template<bool Flag, typename IfTrue, typename IfFalse>struct IF;template<typename IfTrue, typename IfFalse>struct IF<true, IfTrue, IfFalse>{ typedef IfTrue type; };template <typename IfTrue, typename IfFalse>struct IF<false, IfTrue, IfFalse>{ typedef IfFalse type; };// Helper function: return distance(first, last) for forward// iterators, or 0 for input iterators.template<class Iterator>inline typename std::iterator_traits<Iterator>::difference_typedistance_fw(Iterator first, Iterator last, std::input_iterator_tag){ return 0; }template<class Iterator>inline typename std::iterator_traits<Iterator>::difference_typedistance_fw(Iterator first, Iterator last, std::forward_iterator_tag){ return std::distance(first, last); }template<class Iterator>inline typename std::iterator_traits<Iterator>::difference_typedistance_fw(Iterator first, Iterator last){typedef typename std::iterator_traits<Iterator>::iterator_category tag;return distance_fw(first, last, tag());}} // namespace Internal//----------------------------------------------------------------------// Auxiliary types used for all instantiations of hashtable: nodes// and iterators.// Nodes, used to wrap elements stored in the hash table. A policy// template parameter of class template hashtable controls whether// nodes also store a hash code. In some cases (e.g. strings) this may// be a performance win.namespace Internal{template<typename Value, bool cache_hash_code>struct hash_node;template<typename Value>struct hash_node<Value, true>{Value m_v;std::size_t hash_code;hash_node* m_next;};template<typename Value>struct hash_node<Value, false>{Value m_v;hash_node* m_next;};// Local iterators, used to iterate within a bucket but not between// buckets.template<typename Value, bool cache>struct node_iterator_base{node_iterator_base(hash_node<Value, cache>* p): m_cur(p) { }voidincr(){ m_cur = m_cur->m_next; }hash_node<Value, cache>* m_cur;};template<typename Value, bool cache>inline booloperator==(const node_iterator_base<Value, cache>& x,const node_iterator_base<Value, cache>& y){ return x.m_cur == y.m_cur; }template<typename Value, bool cache>inline booloperator!=(const node_iterator_base<Value, cache>& x,const node_iterator_base<Value, cache>& y){ return x.m_cur != y.m_cur; }template<typename Value, bool constant_iterators, bool cache>struct node_iterator: public node_iterator_base<Value, cache>{typedef Value value_type;typedef typename IF<constant_iterators, const Value*, Value*>::typepointer;typedef typename IF<constant_iterators, const Value&, Value&>::typereference;typedef std::ptrdiff_t difference_type;typedef std::forward_iterator_tag iterator_category;node_iterator(): node_iterator_base<Value, cache>(0) { }explicitnode_iterator(hash_node<Value, cache>* p): node_iterator_base<Value, cache>(p) { }referenceoperator*() const{ return this->m_cur->m_v; }pointeroperator->() const{ return &this->m_cur->m_v; }node_iterator&operator++(){this->incr();return *this;}node_iteratoroperator++(int){node_iterator tmp(*this);this->incr();return tmp;}};template<typename Value, bool constant_iterators, bool cache>struct node_const_iterator: public node_iterator_base<Value, cache>{typedef Value value_type;typedef const Value* pointer;typedef const Value& reference;typedef std::ptrdiff_t difference_type;typedef std::forward_iterator_tag iterator_category;node_const_iterator(): node_iterator_base<Value, cache>(0) { }explicitnode_const_iterator(hash_node<Value, cache>* p): node_iterator_base<Value, cache>(p) { }node_const_iterator(const node_iterator<Value, constant_iterators,cache>& x): node_iterator_base<Value, cache>(x.m_cur) { }referenceoperator*() const{ return this->m_cur->m_v; }pointeroperator->() const{ return &this->m_cur->m_v; }node_const_iterator&operator++(){this->incr();return *this;}node_const_iteratoroperator++(int){node_const_iterator tmp(*this);this->incr();return tmp;}};template<typename Value, bool cache>struct hashtable_iterator_base{hashtable_iterator_base(hash_node<Value, cache>* node,hash_node<Value, cache>** bucket): m_cur_node(node), m_cur_bucket(bucket) { }voidincr(){m_cur_node = m_cur_node->m_next;if (!m_cur_node)m_incr_bucket();}voidm_incr_bucket();hash_node<Value, cache>* m_cur_node;hash_node<Value, cache>** m_cur_bucket;};// Global iterators, used for arbitrary iteration within a hash// table. Larger and more expensive than local iterators.template<typename Value, bool cache>voidhashtable_iterator_base<Value, cache>::m_incr_bucket(){++m_cur_bucket;// This loop requires the bucket array to have a non-null sentinel.while (!*m_cur_bucket)++m_cur_bucket;m_cur_node = *m_cur_bucket;}template<typename Value, bool cache>inline booloperator==(const hashtable_iterator_base<Value, cache>& x,const hashtable_iterator_base<Value, cache>& y){ return x.m_cur_node == y.m_cur_node; }template<typename Value, bool cache>inline booloperator!=(const hashtable_iterator_base<Value, cache>& x,const hashtable_iterator_base<Value, cache>& y){ return x.m_cur_node != y.m_cur_node; }template<typename Value, bool constant_iterators, bool cache>struct hashtable_iterator: public hashtable_iterator_base<Value, cache>{typedef Value value_type;typedef typename IF<constant_iterators, const Value*, Value*>::typepointer;typedef typename IF<constant_iterators, const Value&, Value&>::typereference;typedef std::ptrdiff_t difference_type;typedef std::forward_iterator_tag iterator_category;hashtable_iterator(): hashtable_iterator_base<Value, cache>(0, 0) { }hashtable_iterator(hash_node<Value, cache>* p,hash_node<Value, cache>** b): hashtable_iterator_base<Value, cache>(p, b) { }explicithashtable_iterator(hash_node<Value, cache>** b): hashtable_iterator_base<Value, cache>(*b, b) { }referenceoperator*() const{ return this->m_cur_node->m_v; }pointeroperator->() const{ return &this->m_cur_node->m_v; }hashtable_iterator&operator++(){this->incr();return *this;}hashtable_iteratoroperator++(int){hashtable_iterator tmp(*this);this->incr();return tmp;}};template<typename Value, bool constant_iterators, bool cache>struct hashtable_const_iterator: public hashtable_iterator_base<Value, cache>{typedef Value value_type;typedef const Value* pointer;typedef const Value& reference;typedef std::ptrdiff_t difference_type;typedef std::forward_iterator_tag iterator_category;hashtable_const_iterator(): hashtable_iterator_base<Value, cache>(0, 0) { }hashtable_const_iterator(hash_node<Value, cache>* p,hash_node<Value, cache>** b): hashtable_iterator_base<Value, cache>(p, b) { }explicithashtable_const_iterator(hash_node<Value, cache>** b): hashtable_iterator_base<Value, cache>(*b, b) { }hashtable_const_iterator(const hashtable_iterator<Value,constant_iterators, cache>& x): hashtable_iterator_base<Value, cache>(x.m_cur_node, x.m_cur_bucket) { }referenceoperator*() const{ return this->m_cur_node->m_v; }pointeroperator->() const{ return &this->m_cur_node->m_v; }hashtable_const_iterator&operator++(){this->incr();return *this;}hashtable_const_iteratoroperator++(int){hashtable_const_iterator tmp(*this);this->incr();return tmp;}};} // namespace Internal// ----------------------------------------------------------------------// Many of class template hashtable's template parameters are policy// classes. These are defaults for the policies.namespace Internal{// The two key extraction policies used by the *set and *map variants.template<typename T>struct identity{const T&operator()(const T& t) const{ return t; }};template<typename Pair>struct extract1st{const typename Pair::first_type&operator()(const Pair& p) const{ return p.first; }};// Default range hashing function: use division to fold a large number// into the range [0, N).struct mod_range_hashing{typedef std::size_t first_argument_type;typedef std::size_t second_argument_type;typedef std::size_t result_type;result_typeoperator()(first_argument_type r, second_argument_type N) const{ return r % N; }};// Default ranged hash function H. In principle it should be a// function object composed from objects of type H1 and H2 such that// h(k, N) = h2(h1(k), N), but that would mean making extra copies of// h1 and h2. So instead we'll just use a tag to tell class template// hashtable to do that composition.struct default_ranged_hash { };// Default value for rehash policy. Bucket size is (usually) the// smallest prime that keeps the load factor small enough.struct prime_rehash_policy{prime_rehash_policy(float z = 1.0);floatmax_load_factor() const;// Return a bucket size no smaller than n.std::size_tnext_bkt(std::size_t n) const;// Return a bucket count appropriate for n elementsstd::size_tbkt_for_elements(std::size_t n) const;// n_bkt is current bucket count, n_elt is current element count,// and n_ins is number of elements to be inserted. Do we need to// increase bucket count? If so, return make_pair(true, n), where n// is the new bucket count. If not, return make_pair(false, 0).std::pair<bool, std::size_t>need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const;float m_max_load_factor;float m_growth_factor;mutable std::size_t m_next_resize;};// XXX This is a hack. prime_rehash_policy's member functions, and// certainly the list of primes, should be defined in a .cc file.// We're temporarily putting them in a header because we don't have a// place to put TR1 .cc files yet. There's no good reason for any of// prime_rehash_policy's member functions to be inline, and there's// certainly no good reason for X<> to exist at all.struct lt{template<typename X, typename Y>booloperator()(X x, Y y){ return x < y; }};template<int ulongsize = sizeof(unsigned long)>struct X{static const int n_primes = ulongsize != 8 ? 256 : 256 + 48;static const unsigned long primes[256 + 48 + 1];};template<int ulongsize>const int X<ulongsize>::n_primes;template<int ulongsize>const unsigned long X<ulongsize>::primes[256 + 48 + 1] ={2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul,157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul,277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul,503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul,953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul,1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul,3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul,5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul,19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul,33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul,57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul,159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul,256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul,410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul,1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul,1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul,2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul,4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul,6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul,11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul,16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul,24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul,36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul,54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul,1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul,2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul,3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul,4294967291ul,// Sentinel, so we don't have to test the result of lower_bound,// or, on 64-bit machines, rest of the table.ulongsize != 8 ? 4294967291ul : (unsigned long)6442450933ull,(unsigned long)8589934583ull,(unsigned long)12884901857ull, (unsigned long)17179869143ull,(unsigned long)25769803693ull, (unsigned long)34359738337ull,(unsigned long)51539607367ull, (unsigned long)68719476731ull,(unsigned long)103079215087ull, (unsigned long)137438953447ull,(unsigned long)206158430123ull, (unsigned long)274877906899ull,(unsigned long)412316860387ull, (unsigned long)549755813881ull,(unsigned long)824633720731ull, (unsigned long)1099511627689ull,(unsigned long)1649267441579ull, (unsigned long)2199023255531ull,(unsigned long)3298534883309ull, (unsigned long)4398046511093ull,(unsigned long)6597069766607ull, (unsigned long)8796093022151ull,(unsigned long)13194139533241ull, (unsigned long)17592186044399ull,(unsigned long)26388279066581ull, (unsigned long)35184372088777ull,(unsigned long)52776558133177ull, (unsigned long)70368744177643ull,(unsigned long)105553116266399ull, (unsigned long)140737488355213ull,(unsigned long)211106232532861ull, (unsigned long)281474976710597ull,(unsigned long)562949953421231ull, (unsigned long)1125899906842597ull,(unsigned long)2251799813685119ull, (unsigned long)4503599627370449ull,(unsigned long)9007199254740881ull, (unsigned long)18014398509481951ull,(unsigned long)36028797018963913ull, (unsigned long)72057594037927931ull,(unsigned long)144115188075855859ull,(unsigned long)288230376151711717ull,(unsigned long)576460752303423433ull,(unsigned long)1152921504606846883ull,(unsigned long)2305843009213693951ull,(unsigned long)4611686018427387847ull,(unsigned long)9223372036854775783ull,(unsigned long)18446744073709551557ull,(unsigned long)18446744073709551557ull};inlineprime_rehash_policy::prime_rehash_policy(float z): m_max_load_factor(z), m_growth_factor(2.f), m_next_resize(0){ }inline floatprime_rehash_policy::max_load_factor() const{ return m_max_load_factor; }// Return a prime no smaller than n.inline std::size_tprime_rehash_policy::next_bkt(std::size_t n) const{const unsigned long* const last = X<>::primes + X<>::n_primes;const unsigned long* p = std::lower_bound(X<>::primes, last, n);m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));return *p;}// Return the smallest prime p such that alpha p >= n, where alpha// is the load factor.inline std::size_tprime_rehash_policy::bkt_for_elements(std::size_t n) const{const unsigned long* const last = X<>::primes + X<>::n_primes;const float min_bkts = n / m_max_load_factor;const unsigned long* p = std::lower_bound(X<>::primes, last,min_bkts, lt());m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));return *p;}// Finds the smallest prime p such that alpha p > n_elt + n_ins.// If p > n_bkt, return make_pair(true, p); otherwise return// make_pair(false, 0). In principle this isn't very different from// bkt_for_elements.// The only tricky part is that we're caching the element count at// which we need to rehash, so we don't have to do a floating-point// multiply for every insertion.inline std::pair<bool, std::size_t>prime_rehash_policy::need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const{if (n_elt + n_ins > m_next_resize){float min_bkts = (float(n_ins) + float(n_elt)) / m_max_load_factor;if (min_bkts > n_bkt){min_bkts = std::max(min_bkts, m_growth_factor * n_bkt);const unsigned long* const last = X<>::primes + X<>::n_primes;const unsigned long* p = std::lower_bound(X<>::primes, last,min_bkts, lt());m_next_resize =static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));return std::make_pair(true, *p);}else{m_next_resize =static_cast<std::size_t>(std::ceil(n_bkt * m_max_load_factor));return std::make_pair(false, 0);}}elsereturn std::make_pair(false, 0);}} // namespace Internal//----------------------------------------------------------------------// Base classes for std::tr1::hashtable. We define these base classes// because in some cases we want to do different things depending on// the value of a policy class. In some cases the policy class affects// which member functions and nested typedefs are defined; we handle that// by specializing base class templates. Several of the base class templates// need to access other members of class template hashtable, so we use// the "curiously recurring template pattern" for them.namespace Internal{// class template map_base. If the hashtable has a value type of the// form pair<T1, T2> and a key extraction policy that returns the// first part of the pair, the hashtable gets a mapped_type typedef.// If it satisfies those criteria and also has unique keys, then it// also gets an operator[].template<typename K, typename V, typename Ex, bool unique, typename Hashtable>struct map_base { };template<typename K, typename Pair, typename Hashtable>struct map_base<K, Pair, extract1st<Pair>, false, Hashtable>{typedef typename Pair::second_type mapped_type;};template<typename K, typename Pair, typename Hashtable>struct map_base<K, Pair, extract1st<Pair>, true, Hashtable>{typedef typename Pair::second_type mapped_type;mapped_type&operator[](const K& k);};template<typename K, typename Pair, typename Hashtable>typename map_base<K, Pair, extract1st<Pair>, true, Hashtable>::mapped_type&map_base<K, Pair, extract1st<Pair>, true, Hashtable>::operator[](const K& k){Hashtable* h = static_cast<Hashtable*>(this);typename Hashtable::hash_code_t code = h->m_hash_code(k);std::size_t n = h->bucket_index(k, code, h->bucket_count());typename Hashtable::node* p = h->m_find_node(h->m_buckets[n], k, code);if (!p)return h->m_insert_bucket(std::make_pair(k, mapped_type()),n, code)->second;return (p->m_v).second;}// class template rehash_base. Give hashtable the max_load_factor// functions iff the rehash policy is prime_rehash_policy.template<typename RehashPolicy, typename Hashtable>struct rehash_base { };template<typename Hashtable>struct rehash_base<prime_rehash_policy, Hashtable>{floatmax_load_factor() const{const Hashtable* This = static_cast<const Hashtable*>(this);return This->rehash_policy().max_load_factor();}voidmax_load_factor(float z){Hashtable* This = static_cast<Hashtable*>(this);This->rehash_policy(prime_rehash_policy(z));}};// Class template hash_code_base. Encapsulates two policy issues that// aren't quite orthogonal.// (1) the difference between using a ranged hash function and using// the combination of a hash function and a range-hashing function.// In the former case we don't have such things as hash codes, so// we have a dummy type as placeholder.// (2) Whether or not we cache hash codes. Caching hash codes is// meaningless if we have a ranged hash function.// We also put the key extraction and equality comparison function// objects here, for convenience.// Primary template: unused except as a hook for specializations.template<typename Key, typename Value,typename ExtractKey, typename Equal,typename H1, typename H2, typename H,bool cache_hash_code>struct hash_code_base;// Specialization: ranged hash function, no caching hash codes. H1// and H2 are provided but ignored. We define a dummy hash code type.template<typename Key, typename Value,typename ExtractKey, typename Equal,typename H1, typename H2, typename H>struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, false>{protected:hash_code_base(const ExtractKey& ex, const Equal& eq,const H1&, const H2&, const H& h): m_extract(ex), m_eq(eq), m_ranged_hash(h) { }typedef void* hash_code_t;hash_code_tm_hash_code(const Key& k) const{ return 0; }std::size_tbucket_index(const Key& k, hash_code_t, std::size_t N) const{ return m_ranged_hash(k, N); }std::size_tbucket_index(const hash_node<Value, false>* p, std::size_t N) const{ return m_ranged_hash(m_extract(p->m_v), N); }boolcompare(const Key& k, hash_code_t, hash_node<Value, false>* n) const{ return m_eq(k, m_extract(n->m_v)); }voidstore_code(hash_node<Value, false>*, hash_code_t) const{ }voidcopy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const{ }voidm_swap(hash_code_base& x){std::swap(m_extract, x.m_extract);std::swap(m_eq, x.m_eq);std::swap(m_ranged_hash, x.m_ranged_hash);}protected:ExtractKey m_extract;Equal m_eq;H m_ranged_hash;};// No specialization for ranged hash function while caching hash codes.// That combination is meaningless, and trying to do it is an error.// Specialization: ranged hash function, cache hash codes. This// combination is meaningless, so we provide only a declaration// and no definition.template<typename Key, typename Value,typename ExtractKey, typename Equal,typename H1, typename H2, typename H>struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, true>;// Specialization: hash function and range-hashing function, no// caching of hash codes. H is provided but ignored. Provides// typedef and accessor required by TR1.template<typename Key, typename Value,typename ExtractKey, typename Equal,typename H1, typename H2>struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2,default_ranged_hash, false>{typedef H1 hasher;hasherhash_function() const{ return m_h1; }protected:hash_code_base(const ExtractKey& ex, const Equal& eq,const H1& h1, const H2& h2, const default_ranged_hash&): m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { }typedef std::size_t hash_code_t;hash_code_tm_hash_code(const Key& k) const{ return m_h1(k); }std::size_tbucket_index(const Key&, hash_code_t c, std::size_t N) const{ return m_h2(c, N); }std::size_tbucket_index(const hash_node<Value, false>* p, std::size_t N) const{ return m_h2(m_h1(m_extract(p->m_v)), N); }boolcompare(const Key& k, hash_code_t, hash_node<Value, false>* n) const{ return m_eq(k, m_extract(n->m_v)); }voidstore_code(hash_node<Value, false>*, hash_code_t) const{ }voidcopy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const{ }voidm_swap(hash_code_base& x){std::swap(m_extract, x.m_extract);std::swap(m_eq, x.m_eq);std::swap(m_h1, x.m_h1);std::swap(m_h2, x.m_h2);}protected:ExtractKey m_extract;Equal m_eq;H1 m_h1;H2 m_h2;};// Specialization: hash function and range-hashing function,// caching hash codes. H is provided but ignored. Provides// typedef and accessor required by TR1.template<typename Key, typename Value,typename ExtractKey, typename Equal,typename H1, typename H2>struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2,default_ranged_hash, true>{typedef H1 hasher;hasherhash_function() const{ return m_h1; }protected:hash_code_base(const ExtractKey& ex, const Equal& eq,const H1& h1, const H2& h2, const default_ranged_hash&): m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { }typedef std::size_t hash_code_t;hash_code_tm_hash_code(const Key& k) const{ return m_h1(k); }std::size_tbucket_index(const Key&, hash_code_t c, std::size_t N) const{ return m_h2(c, N); }std::size_tbucket_index(const hash_node<Value, true>* p, std::size_t N) const{ return m_h2(p->hash_code, N); }boolcompare(const Key& k, hash_code_t c, hash_node<Value, true>* n) const{ return c == n->hash_code && m_eq(k, m_extract(n->m_v)); }voidstore_code(hash_node<Value, true>* n, hash_code_t c) const{ n->hash_code = c; }voidcopy_code(hash_node<Value, true>* to,const hash_node<Value, true>* from) const{ to->hash_code = from->hash_code; }voidm_swap(hash_code_base& x){std::swap(m_extract, x.m_extract);std::swap(m_eq, x.m_eq);std::swap(m_h1, x.m_h1);std::swap(m_h2, x.m_h2);}protected:ExtractKey m_extract;Equal m_eq;H1 m_h1;H2 m_h2;};} // namespace internalnamespace std{namespace tr1{//----------------------------------------------------------------------// Class template hashtable, class definition.// Meaning of class template hashtable's template parameters// Key and Value: arbitrary CopyConstructible types.// Allocator: an allocator type ([lib.allocator.requirements]) whose// value type is Value.// ExtractKey: function object that takes a object of type Value// and returns a value of type Key.// Equal: function object that takes two objects of type k and returns// a bool-like value that is true if the two objects are considered equal.// H1: the hash function. A unary function object with argument type// Key and result type size_t. Return values should be distributed// over the entire range [0, numeric_limits<size_t>:::max()].// H2: the range-hashing function (in the terminology of Tavori and// Dreizin). A binary function object whose argument types and result// type are all size_t. Given arguments r and N, the return value is// in the range [0, N).// H: the ranged hash function (Tavori and Dreizin). A binary function// whose argument types are Key and size_t and whose result type is// size_t. Given arguments k and N, the return value is in the range// [0, N). Default: h(k, N) = h2(h1(k), N). If H is anything other// than the default, H1 and H2 are ignored.// RehashPolicy: Policy class with three members, all of which govern// the bucket count. n_bkt(n) returns a bucket count no smaller// than n. bkt_for_elements(n) returns a bucket count appropriate// for an element count of n. need_rehash(n_bkt, n_elt, n_ins)// determines whether, if the current bucket count is n_bkt and the// current element count is n_elt, we need to increase the bucket// count. If so, returns make_pair(true, n), where n is the new// bucket count. If not, returns make_pair(false, <anything>).// ??? Right now it is hard-wired that the number of buckets never// shrinks. Should we allow RehashPolicy to change that?// cache_hash_code: bool. true if we store the value of the hash// function along with the value. This is a time-space tradeoff.// Storing it may improve lookup speed by reducing the number of times// we need to call the Equal function.// constant_iterators: bool. true if iterator and const_iterator are// both constant iterator types. This is true for unordered_set and// unordered_multiset, false for unordered_map and unordered_multimap.// unique_keys: bool. true if the return value of hashtable::count(k)// is always at most one, false if it may be an arbitrary number. This// true for unordered_set and unordered_map, false for unordered_multiset// and unordered_multimap.template<typename Key, typename Value,typename Allocator,typename ExtractKey, typename Equal,typename H1, typename H2,typename H, typename RehashPolicy,bool cache_hash_code,bool constant_iterators,bool unique_keys>class hashtable: public Internal::rehash_base<RehashPolicy,hashtable<Key, Value, Allocator, ExtractKey,Equal, H1, H2, H, RehashPolicy,cache_hash_code, constant_iterators,unique_keys> >,public Internal::hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H,cache_hash_code>,public Internal::map_base<Key, Value, ExtractKey, unique_keys,hashtable<Key, Value, Allocator, ExtractKey,Equal, H1, H2, H, RehashPolicy,cache_hash_code, constant_iterators,unique_keys> >{public:typedef Allocator allocator_type;typedef Value value_type;typedef Key key_type;typedef Equal key_equal;// mapped_type, if present, comes from map_base.// hasher, if present, comes from hash_code_base.typedef typename Allocator::difference_type difference_type;typedef typename Allocator::size_type size_type;typedef typename Allocator::reference reference;typedef typename Allocator::const_reference const_reference;typedef Internal::node_iterator<value_type, constant_iterators,cache_hash_code>local_iterator;typedef Internal::node_const_iterator<value_type, constant_iterators,cache_hash_code>const_local_iterator;typedef Internal::hashtable_iterator<value_type, constant_iterators,cache_hash_code>iterator;typedef Internal::hashtable_const_iterator<value_type, constant_iterators,cache_hash_code>const_iterator;template<typename K, typename Pair, typename Hashtable>friend struct Internal::map_base;private:typedef Internal::hash_node<Value, cache_hash_code> node;typedef typename Allocator::template rebind<node>::othernode_allocator_t;typedef typename Allocator::template rebind<node*>::otherbucket_allocator_t;private:node_allocator_t m_node_allocator;node** m_buckets;size_type m_bucket_count;size_type m_element_count;RehashPolicy m_rehash_policy;node*m_allocate_node(const value_type& v);voidm_deallocate_node(node* n);voidm_deallocate_nodes(node**, size_type);node**m_allocate_buckets(size_type n);voidm_deallocate_buckets(node**, size_type n);public: // Constructor, destructor, assignment, swaphashtable(size_type bucket_hint,const H1&, const H2&, const H&,const Equal&, const ExtractKey&,const allocator_type&);template<typename InIter>hashtable(InIter first, InIter last,size_type bucket_hint,const H1&, const H2&, const H&,const Equal&, const ExtractKey&,const allocator_type&);hashtable(const hashtable&);hashtable&operator=(const hashtable&);~hashtable();void swap(hashtable&);public: // Basic container operationsiteratorbegin(){iterator i(m_buckets);if (!i.m_cur_node)i.m_incr_bucket();return i;}const_iteratorbegin() const{const_iterator i(m_buckets);if (!i.m_cur_node)i.m_incr_bucket();return i;}iteratorend(){ return iterator(m_buckets + m_bucket_count); }const_iteratorend() const{ return const_iterator(m_buckets + m_bucket_count); }size_typesize() const{ return m_element_count; }boolempty() const{ return size() == 0; }allocator_typeget_allocator() const{ return m_node_allocator; }size_typemax_size() const{ return m_node_allocator.max_size(); }public: // Observerskey_equalkey_eq() const{ return this->m_eq; }// hash_function, if present, comes from hash_code_base.public: // Bucket operationssize_typebucket_count() const{ return m_bucket_count; }size_typemax_bucket_count() const{ return max_size(); }size_typebucket_size(size_type n) const{ return std::distance(begin(n), end(n)); }size_typebucket(const key_type& k) const{return this->bucket_index(k, this->m_hash_code(k),this->m_bucket_count);}local_iteratorbegin(size_type n){ return local_iterator(m_buckets[n]); }local_iteratorend(size_type){ return local_iterator(0); }const_local_iteratorbegin(size_type n) const{ return const_local_iterator(m_buckets[n]); }const_local_iteratorend(size_type) const{ return const_local_iterator(0); }floatload_factor() const{return static_cast<float>(size()) / static_cast<float>(bucket_count());}// max_load_factor, if present, comes from rehash_base.// Generalization of max_load_factor. Extension, not found in TR1. Only// useful if RehashPolicy is something other than the default.const RehashPolicy&rehash_policy() const{ return m_rehash_policy; }voidrehash_policy(const RehashPolicy&);public: // lookupiteratorfind(const key_type& k);const_iteratorfind(const key_type& k) const;size_typecount(const key_type& k) const;std::pair<iterator, iterator>equal_range(const key_type& k);std::pair<const_iterator, const_iterator>equal_range(const key_type& k) const;private: // Find, insert and erase helper functions// ??? This dispatching is a workaround for the fact that we don't// have partial specialization of member templates; it would be// better to just specialize insert on unique_keys. There may be a// cleaner workaround.typedef typename Internal::IF<unique_keys,std::pair<iterator, bool>, iterator>::typeInsert_Return_Type;typedef typename Internal::IF<unique_keys,Internal::extract1st<Insert_Return_Type>,Internal::identity<Insert_Return_Type>>::typeInsert_Conv_Type;node*m_find_node(node*, const key_type&,typename hashtable::hash_code_t) const;iteratorm_insert_bucket(const value_type&, size_type,typename hashtable::hash_code_t);std::pair<iterator, bool>m_insert(const value_type&, std::tr1::true_type);iteratorm_insert(const value_type&, std::tr1::false_type);voidm_erase_node(node*, node**);public: // Insert and eraseInsert_Return_Typeinsert(const value_type& v){ return m_insert(v, std::tr1::integral_constant<bool, unique_keys>()); }iteratorinsert(iterator, const value_type& v){ return iterator(Insert_Conv_Type()(this->insert(v))); }const_iteratorinsert(const_iterator, const value_type& v){ return const_iterator(Insert_Conv_Type()(this->insert(v))); }template<typename InIter>voidinsert(InIter first, InIter last);iteratorerase(iterator);const_iteratorerase(const_iterator);size_typeerase(const key_type&);iteratorerase(iterator, iterator);const_iteratorerase(const_iterator, const_iterator);voidclear();public:// Set number of buckets to be appropriate for container of n element.void rehash(size_type n);private:// Unconditionally change size of bucket array to n.void m_rehash(size_type n);};//----------------------------------------------------------------------// Definitions of class template hashtable's out-of-line member functions.template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node*hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::m_allocate_node(const value_type& v){node* n = m_node_allocator.allocate(1);try{get_allocator().construct(&n->m_v, v);n->m_next = 0;return n;}catch(...){m_node_allocator.deallocate(n, 1);__throw_exception_again;}}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>voidhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::m_deallocate_node(node* n){get_allocator().destroy(&n->m_v);m_node_allocator.deallocate(n, 1);}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>voidhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::m_deallocate_nodes(node** array, size_type n){for (size_type i = 0; i < n; ++i){node* p = array[i];while (p){node* tmp = p;p = p->m_next;m_deallocate_node(tmp);}array[i] = 0;}}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node**hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::m_allocate_buckets(size_type n){bucket_allocator_t alloc(m_node_allocator);// We allocate one extra bucket to hold a sentinel, an arbitrary// non-null pointer. Iterator increment relies on this.node** p = alloc.allocate(n + 1);std::fill(p, p + n, (node*) 0);p[n] = reinterpret_cast<node*>(0x1000);return p;}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>voidhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::m_deallocate_buckets(node** p, size_type n){bucket_allocator_t alloc(m_node_allocator);alloc.deallocate(p, n + 1);}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::hashtable(size_type bucket_hint,const H1& h1, const H2& h2, const H& h,const Eq& eq, const Ex& exk,const allocator_type& a): Internal::rehash_base<RP, hashtable>(),Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, h1, h2, h),Internal::map_base<K, V, Ex, u, hashtable>(),m_node_allocator(a),m_bucket_count(0),m_element_count(0),m_rehash_policy(){m_bucket_count = m_rehash_policy.next_bkt(bucket_hint);m_buckets = m_allocate_buckets(m_bucket_count);}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>template<typename InIter>hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::hashtable(InIter f, InIter l,size_type bucket_hint,const H1& h1, const H2& h2, const H& h,const Eq& eq, const Ex& exk,const allocator_type& a): Internal::rehash_base<RP, hashtable>(),Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq,h1, h2, h),Internal::map_base<K, V, Ex, u, hashtable>(),m_node_allocator(a),m_bucket_count(0),m_element_count(0),m_rehash_policy(){m_bucket_count = std::max(m_rehash_policy.next_bkt(bucket_hint),m_rehash_policy.bkt_for_elements(Internal::distance_fw(f, l)));m_buckets = m_allocate_buckets(m_bucket_count);try{for (; f != l; ++f)this->insert(*f);}catch(...){clear();m_deallocate_buckets(m_buckets, m_bucket_count);__throw_exception_again;}}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::hashtable(const hashtable& ht): Internal::rehash_base<RP, hashtable>(ht),Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(ht),Internal::map_base<K, V, Ex, u, hashtable>(ht),m_node_allocator(ht.get_allocator()),m_bucket_count(ht.m_bucket_count),m_element_count(ht.m_element_count),m_rehash_policy(ht.m_rehash_policy){m_buckets = m_allocate_buckets(m_bucket_count);try{for (size_type i = 0; i < ht.m_bucket_count; ++i){node* n = ht.m_buckets[i];node** tail = m_buckets + i;while (n){*tail = m_allocate_node(n->m_v);this->copy_code(*tail, n);tail = &((*tail)->m_next);n = n->m_next;}}}catch(...){clear();m_deallocate_buckets(m_buckets, m_bucket_count);__throw_exception_again;}}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>&hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::operator=(const hashtable& ht){hashtable tmp(ht);this->swap(tmp);return *this;}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::~hashtable(){clear();m_deallocate_buckets(m_buckets, m_bucket_count);}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>voidhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::swap(hashtable& x){// The only base class with member variables is hash_code_base. We// define hash_code_base::m_swap because different specializations// have different members.Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x);// open LWG issue 431// std::swap(m_node_allocator, x.m_node_allocator);std::swap(m_rehash_policy, x.m_rehash_policy);std::swap(m_buckets, x.m_buckets);std::swap(m_bucket_count, x.m_bucket_count);std::swap(m_element_count, x.m_element_count);}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>voidhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::rehash_policy(const RP& pol){m_rehash_policy = pol;size_type n_bkt = pol.bkt_for_elements(m_element_count);if (n_bkt > m_bucket_count)m_rehash(n_bkt);}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iteratorhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::find(const key_type& k){typename hashtable::hash_code_t code = this->m_hash_code(k);std::size_t n = this->bucket_index(k, code, this->bucket_count());node* p = m_find_node(m_buckets[n], k, code);return p ? iterator(p, m_buckets + n) : this->end();}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iteratorhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::find(const key_type& k) const{typename hashtable::hash_code_t code = this->m_hash_code(k);std::size_t n = this->bucket_index(k, code, this->bucket_count());node* p = m_find_node(m_buckets[n], k, code);return p ? const_iterator(p, m_buckets + n) : this->end();}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::size_typehashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::count(const key_type& k) const{typename hashtable::hash_code_t code = this->m_hash_code(k);std::size_t n = this->bucket_index(k, code, this->bucket_count());std::size_t result = 0;for (node* p = m_buckets[n]; p; p = p->m_next)if (this->compare(k, code, p))++result;return result;}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>std::pair<typename hashtable<K, V, A, Ex, Eq, H1,H2, H, RP, c, ci, u>::iterator,typename hashtable<K, V, A, Ex, Eq, H1,H2, H, RP, c, ci, u>::iterator>hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::equal_range(const key_type& k){typename hashtable::hash_code_t code = this->m_hash_code(k);std::size_t n = this->bucket_index(k, code, this->bucket_count());node** head = m_buckets + n;node* p = m_find_node(*head, k, code);if (p){node* p1 = p->m_next;for (; p1; p1 = p1->m_next)if (!this->compare(k, code, p1))break;iterator first(p, head);iterator last(p1, head);if (!p1)last.m_incr_bucket();return std::make_pair(first, last);}elsereturn std::make_pair(this->end(), this->end());}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>std::pair<typename hashtable<K, V, A, Ex, Eq, H1,H2, H, RP, c, ci, u>::const_iterator,typename hashtable<K, V, A, Ex, Eq, H1,H2, H, RP, c, ci, u>::const_iterator>hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::equal_range(const key_type& k) const{typename hashtable::hash_code_t code = this->m_hash_code(k);std::size_t n = this->bucket_index(k, code, this->bucket_count());node** head = m_buckets + n;node* p = m_find_node(*head, k, code);if (p){node* p1 = p->m_next;for (; p1; p1 = p1->m_next)if (!this->compare(k, code, p1))break;const_iterator first(p, head);const_iterator last(p1, head);if (!p1)last.m_incr_bucket();return std::make_pair(first, last);}elsereturn std::make_pair(this->end(), this->end());}// Find the node whose key compares equal to k, beginning the search// at p (usually the head of a bucket). Return nil if no node is found.template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node*hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::m_find_node(node* p, const key_type& k,typename hashtable::hash_code_t code) const{for (; p; p = p->m_next)if (this->compare(k, code, p))return p;return false;}// Insert v in bucket n (assumes no element with its key already present).template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iteratorhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::m_insert_bucket(const value_type& v, size_type n,typename hashtable::hash_code_t code){std::pair<bool, std::size_t> do_rehash= m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);// Allocate the new node before doing the rehash so that we don't// do a rehash if the allocation throws.node* new_node = m_allocate_node(v);try{if (do_rehash.first){const key_type& k = this->m_extract(v);n = this->bucket_index(k, code, do_rehash.second);m_rehash(do_rehash.second);}new_node->m_next = m_buckets[n];this->store_code(new_node, code);m_buckets[n] = new_node;++m_element_count;return iterator(new_node, m_buckets + n);}catch(...){m_deallocate_node(new_node);__throw_exception_again;}}// Insert v if no element with its key is already present.template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>std::pair<typename hashtable<K, V, A, Ex, Eq, H1,H2, H, RP, c, ci, u>::iterator, bool>hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::m_insert(const value_type& v, std::tr1::true_type){const key_type& k = this->m_extract(v);typename hashtable::hash_code_t code = this->m_hash_code(k);size_type n = this->bucket_index(k, code, m_bucket_count);if (node* p = m_find_node(m_buckets[n], k, code))return std::make_pair(iterator(p, m_buckets + n), false);return std::make_pair(m_insert_bucket(v, n, code), true);}// Insert v unconditionally.template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iteratorhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::m_insert(const value_type& v, std::tr1::false_type){std::pair<bool, std::size_t> do_rehash= m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);if (do_rehash.first)m_rehash(do_rehash.second);const key_type& k = this->m_extract(v);typename hashtable::hash_code_t code = this->m_hash_code(k);size_type n = this->bucket_index(k, code, m_bucket_count);// First find the node, avoid leaking new_node if compare throws.node* prev = m_find_node(m_buckets[n], k, code);node* new_node = m_allocate_node(v);if (prev){new_node->m_next = prev->m_next;prev->m_next = new_node;}else{new_node->m_next = m_buckets[n];m_buckets[n] = new_node;}this->store_code(new_node, code);++m_element_count;return iterator(new_node, m_buckets + n);}// For erase(iterator) and erase(const_iterator).template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>voidhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::m_erase_node(node* p, node** b){node* cur = *b;if (cur == p)*b = cur->m_next;else{node* next = cur->m_next;while (next != p){cur = next;next = cur->m_next;}cur->m_next = next->m_next;}m_deallocate_node(p);--m_element_count;}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>template<typename InIter>voidhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::insert(InIter first, InIter last){size_type n_elt = Internal::distance_fw(first, last);std::pair<bool, std::size_t> do_rehash= m_rehash_policy.need_rehash(m_bucket_count, m_element_count, n_elt);if (do_rehash.first)m_rehash(do_rehash.second);for (; first != last; ++first)this->insert(*first);}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iteratorhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::erase(iterator it){iterator result = it;++result;m_erase_node(it.m_cur_node, it.m_cur_bucket);return result;}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iteratorhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::erase(const_iterator it){const_iterator result = it;++result;m_erase_node(it.m_cur_node, it.m_cur_bucket);return result;}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::size_typehashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::erase(const key_type& k){typename hashtable::hash_code_t code = this->m_hash_code(k);size_type n = this->bucket_index(k, code, m_bucket_count);size_type result = 0;node** slot = m_buckets + n;while (*slot && !this->compare(k, code, *slot))slot = &((*slot)->m_next);while (*slot && this->compare(k, code, *slot)){node* p = *slot;*slot = p->m_next;m_deallocate_node(p);--m_element_count;++result;}return result;}// ??? This could be optimized by taking advantage of the bucket// structure, but it's not clear that it's worth doing. It probably// wouldn't even be an optimization unless the load factor is large.template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iteratorhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::erase(iterator first, iterator last){while (first != last)first = this->erase(first);return last;}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iteratorhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::erase(const_iterator first, const_iterator last){while (first != last)first = this->erase(first);return last;}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>voidhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::clear(){m_deallocate_nodes(m_buckets, m_bucket_count);m_element_count = 0;}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>voidhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::rehash(size_type n){m_rehash(std::max(m_rehash_policy.next_bkt(n),m_rehash_policy.bkt_for_elements(m_element_count+ 1)));}template<typename K, typename V,typename A, typename Ex, typename Eq,typename H1, typename H2, typename H, typename RP,bool c, bool ci, bool u>voidhashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::m_rehash(size_type n){node** new_array = m_allocate_buckets(n);try{for (size_type i = 0; i < m_bucket_count; ++i)while (node* p = m_buckets[i]){size_type new_index = this->bucket_index(p, n);m_buckets[i] = p->m_next;p->m_next = new_array[new_index];new_array[new_index] = p;}m_deallocate_buckets(m_buckets, m_bucket_count);m_bucket_count = n;m_buckets = new_array;}catch(...){// A failure here means that a hash function threw an exception.// We can't restore the previous state without calling the hash// function again, so the only sensible recovery is to delete// everything.m_deallocate_nodes(new_array, n);m_deallocate_buckets(new_array, n);m_deallocate_nodes(m_buckets, m_bucket_count);m_element_count = 0;__throw_exception_again;}}}} // Namespace std::tr1#endif /* GNU_LIBSTDCXX_TR1_HASHTABLE_ */