hashtable

linux下编程用 编译软件

  // 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;

    private:
      typedef Internal::hash_node<Value, cache_hash_code>    node;
      typedef typename Allocator::template rebind<node>::other
        node_allocator_t;
      typedef typename Allocator::template rebind<node*>::other
        bucket_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);
  
      void
      m_deallocate_node(node* n);
  
      void
      m_deallocate_nodes(node**, size_type);

      node**
      m_allocate_buckets(size_type n);
  
      void
      m_deallocate_buckets(node**, size_type n);

    public:			    // Constructor, destructor, assignment, swap
      hashtable(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 operations
      iterator
      begin()
      {
	iterator i(m_buckets);
	if (!i.m_cur_node)
	  i.m_incr_bucket();
	return i;
      }

      const_iterator
      begin() const
      {
	const_iterator i(m_buckets);
	if (!i.m_cur_node)
	  i.m_incr_bucket();
	return i;
      }

      iterator
      end()
      { return iterator(m_buckets + m_bucket_count); }

      const_iterator
      end() const
      { return const_iterator(m_buckets + m_bucket_count); }

      size_type
      size() const
      { return m_element_count; }
  
      bool
      empty() const
      { return size() == 0; }

      allocator_type
      get_allocator() const
      { return m_node_allocator; }
  
      size_type
      max_size() const
      { return m_node_allocator.max_size(); }

    public:                             // Observers
      key_equal
      key_eq() const
      { return this->m_eq; }

      // hash_function, if present, comes from hash_code_base.

    public:				// Bucket operations
      size_type
      bucket_count() const
      { return m_bucket_count; }
  
      size_type
      max_bucket_count() const
      { return max_size(); }
  
      size_type
      bucket_size(size_type n) const
      { return std::distance(begin(n), end(n)); }
  
      size_type
      bucket(const key_type& k) const
      { 
	return this->bucket_index(k, this->m_hash_code(k),
				  this->m_bucket_count);
      }

      local_iterator
      begin(size_type n)
      { return local_iterator(m_buckets[n]); }
  
      local_iterator
      end(size_type)
      { return local_iterator(0); }
  
      const_local_iterator
      begin(size_type n) const
      { return const_local_iterator(m_buckets[n]); }
  
      const_local_iterator
      end(size_type) const
      { return const_local_iterator(0); }

      float
      load_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; }
      
      void 
      rehash_policy(const RehashPolicy&);

    public:				// lookup
      iterator
      find(const key_type&);

      const_iterator
      find(const key_type& k) const;

      size_type
      count(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:			// 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>::type
        Insert_Return_Type;

      typedef typename Internal::IF<unique_keys,
				    Internal::extract1st<Insert_Return_Type>,
				    Internal::identity<Insert_Return_Type>
                                   >::type
        Insert_Conv_Type;

      node*
      find_node(node* p, const key_type& k,
		typename hashtable::hash_code_t c) const;

      std::pair<iterator, bool>
      insert(const value_type&, std::tr1::true_type);
  
      iterator
      insert(const value_type&, std::tr1::false_type);

      void
      erase_node(node*, node**);

    public:				// Insert and erase
      Insert_Return_Type
      insert(const value_type& v) 
      { 
	return this->insert(v, std::tr1::integral_constant<bool,
			    unique_keys>());
      }

      iterator
      insert(iterator, const value_type& v)
      { return iterator(Insert_Conv_Type()(this->insert(v))); }
      
      const_iterator
      insert(const_iterator, const value_type& v)
      { return const_iterator(Insert_Conv_Type()(this->insert(v))); }

      template<typename InIter>
        void
        insert(InIter first, InIter last);

      iterator
      erase(iterator);

      const_iterator
      erase(const_iterator);

      size_type
      erase(const key_type&);

      iterator
      erase(iterator, iterator);

      const_iterator
      erase(const_iterator, const_iterator);

      void
      clear();

    public:
      // Set number of buckets to be apropriate 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>
    void
    hashtable<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>
    void
    hashtable<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>
    void
    hashtable<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_t 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);