hashtable

linux下编程用 编译软件

  template<int dummy>
    struct X
    {
      static const int n_primes = 256;
      static const unsigned long primes[n_primes + 1];
    };

  template<int dummy>
    const int X<dummy>::n_primes;

  template<int dummy>
    const unsigned long X<dummy>::primes[n_primes + 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,
      4294967291ul // sentinel so we don't have to test result of lower_bound
    };

  inline
  prime_rehash_policy::
  prime_rehash_policy(float z)
  : m_max_load_factor(z), m_growth_factor(2.f), m_next_resize(0)
  { }

  inline float
  prime_rehash_policy::
  max_load_factor() const
  { return m_max_load_factor; }

  // Return a prime no smaller than n.
  inline std::size_t
  prime_rehash_policy::
  next_bkt(std::size_t n) const
  {
    const unsigned long* const last = X<0>::primes + X<0>::n_primes;
    const unsigned long* p = std::lower_bound (X<0>::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_t
  prime_rehash_policy::
  bkt_for_elements(std::size_t n) const
  {
    const unsigned long* const last = X<0>::primes + X<0>::n_primes;
    const float min_bkts = n / m_max_load_factor;
    const unsigned long* p = std::lower_bound (X<0>::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<0>::primes + X<0>::n_primes;
	    const unsigned long* p = std::lower_bound (X<0>::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);
	  }
      }
    else
      return 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)
      {
	Hashtable* h = static_cast<Hashtable*>(this);
	typename Hashtable::iterator it = 
	  h->insert(std::make_pair(k, mapped_type())).first;
	return it->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>
    {
      float
      max_load_factor() const
      {
	const Hashtable* This = static_cast<const Hashtable*>(this);
	return This->rehash_policy().max_load_factor();
      }

      void
      max_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_t
      m_hash_code(const Key& k) const
      { return 0; }
  
      std::size_t
      bucket_index(const Key& k, hash_code_t, std::size_t N) const
      { return m_ranged_hash (k, N); }

      std::size_t
      bucket_index(const hash_node<Value, false>* p, std::size_t N) const
      { return m_ranged_hash (m_extract (p->m_v), N); }
  
      bool
      compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const
      { return m_eq (k, m_extract(n->m_v)); }

      void
      store_code(hash_node<Value, false>*, hash_code_t) const
      { }

      void
      copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const
      { }
      
      void
      m_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;
      
      hasher
      hash_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_t
      m_hash_code(const Key& k) const
      { return m_h1(k); }
      
      std::size_t
      bucket_index(const Key&, hash_code_t c, std::size_t N) const
      { return m_h2 (c, N); }

      std::size_t
      bucket_index(const hash_node<Value, false>* p, std::size_t N) const
      { return m_h2 (m_h1 (m_extract (p->m_v)), N); }

      bool
      compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const
      { return m_eq (k, m_extract(n->m_v)); }

      void
      store_code(hash_node<Value, false>*, hash_code_t) const
      { }

      void
      copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const
      { }

      void
      m_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;
      
      hasher
      hash_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_t
      m_hash_code(const Key& k) const
      { return m_h1(k); }
  
      std::size_t
      bucket_index(const Key&, hash_code_t c, std::size_t N) const
      { return m_h2 (c, N); }

      std::size_t
      bucket_index(const hash_node<Value, true>* p, std::size_t N) const
      { return m_h2 (p->hash_code, N); }

      bool
      compare(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)); }

      void
      store_code(hash_node<Value, true>* n, hash_code_t c) const
      { n->hash_code = c; }

      void
      copy_code(hash_node<Value, true>* to,
		const hash_node<Value, true>* from) const
      { to->hash_code = from->hash_code; }

      void
      m_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 internal

namespace 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)