STL — hash_map/hash_set源代码剖析

你的名字 2022-06-01 23:48 169阅读 0赞

# hash\_map/hash\_set源代码剖析 #

虽然STL只规范复杂度与接口，并不规范实现方法，但STL set多半以RB\_Tree. SGI 则是在 STL标准之外另又提供了一个所谓的hash\_set

，以 hashTable 的底层机制. 由于hash\_set所供应的操作接口，hashTable都提供了，所以几乎所有的hash\_set操作行为，都只是转调用

hashTable的 操作 行为而已.

运用set为的是能够快速搜寻元素，这一点，不论其底层是RB\_Tree或者hashtable都可以达到任务，但是请注意，RB\_tree有自动排序功能

，而 hashtable 没有，反应出来的结果就是，set的元素有自动排序的功能而hash\_set没有. 我们直接看代码：

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
    //这4个参数的作用分别是:
    //vlalue :  键值型别  hashFcn : hash function的函数型别  ExtracKey : 从节点中取出键值的方法
    //Alloc ： 老生常谈 空间配置器.
    template <class Value, class HashFcn = hash<Value>,
    class EqualKey = equal_to<Value>,
    class Alloc = alloc>
    #else
    template <class Value, class HashFcn, class EqualKey, class Alloc = alloc>
    #endif
    class hash_set
    {
    private:
    	//这里该set的底层就是一个哈希表，而set就是一个马甲.
    	//以下使用的identiy<> 定义于<stl_function.h>中
    	typedef hashtable<Value, Value, HashFcn, identity<Value>,
    		EqualKey, Alloc> ht;
    	ht rep;
    
    public:
    	//常见型别声明.
    	typedef typename ht::key_type key_type;
    	typedef typename ht::value_type value_type;
    	typedef typename ht::hasher hasher;
    	typedef typename ht::key_equal key_equal;
    
    	typedef typename ht::size_type size_type;
    	typedef typename ht::difference_type difference_type;
    	typedef typename ht::const_pointer pointer;
    	typedef typename ht::const_pointer const_pointer;
    	typedef typename ht::const_reference reference;
    	typedef typename ht::const_reference const_reference;
    
    	typedef typename ht::const_iterator iterator;
    	typedef typename ht::const_iterator const_iterator;
    
    	hasher hash_funct() const { return rep.hash_funct(); }
    	key_equal key_eq() const { return rep.key_eq(); }
    
    public:
    	//缺省使用大小为100的表格，将被hash table调整为最接近且较大之质数.
    	hash_set() : rep(100, hasher(), key_equal()) {}
    	explicit hash_set(size_type n) : rep(n, hasher(), key_equal()) {}
    	hash_set(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
    	hash_set(size_type n, const hasher& hf, const key_equal& eql)
    		: rep(n, hf, eql) {}
    
    	//以下的插入，全部使用insert_unique()，不允许键值重复.
    	hash_set(const value_type* f, const value_type* l)
    		: rep(100, hasher(), key_equal()) {
    		rep.insert_unique(f, l);
    	}
    	hash_set(const value_type* f, const value_type* l, size_type n)
    		: rep(n, hasher(), key_equal()) {
    		rep.insert_unique(f, l);
    	}
    	hash_set(const value_type* f, const value_type* l, size_type n,
    		const hasher& hf)
    		: rep(n, hf, key_equal()) {
    		rep.insert_unique(f, l);
    	}
    	hash_set(const value_type* f, const value_type* l, size_type n,
    		const hasher& hf, const key_equal& eql)
    		: rep(n, hf, eql) {
    		rep.insert_unique(f, l);
    	}
    
    	hash_set(const_iterator f, const_iterator l)
    		: rep(100, hasher(), key_equal()) {
    		rep.insert_unique(f, l);
    	}
    	hash_set(const_iterator f, const_iterator l, size_type n)
    		: rep(n, hasher(), key_equal()) {
    		rep.insert_unique(f, l);
    	}
    	hash_set(const_iterator f, const_iterator l, size_type n,
    		const hasher& hf)
    		: rep(n, hf, key_equal()) {
    		rep.insert_unique(f, l);
    	}
    	hash_set(const_iterator f, const_iterator l, size_type n,
    		const hasher& hf, const key_equal& eql)
    		: rep(n, hf, eql) {
    		rep.insert_unique(f, l);
    	}
    
    public:
    	//几乎所有操作，都是hash table的版本，传递调用即可.
    	size_type size() const { return rep.size(); }
    	size_type max_size() const { return rep.max_size(); }
    	bool empty() const { return rep.empty(); }
    	void swap(hash_set& hs) { rep.swap(hs.rep); }
    	friend bool operator== __STL_NULL_TMPL_ARGS(const hash_set&,
    		const hash_set&);
    
    	iterator begin() const { return rep.begin(); }
    	iterator end() const { return rep.end(); }
    
    public:
    	pair<iterator, bool> insert(const value_type& obj)
    	{
    		pair<typename ht::iterator, bool> p = rep.insert_unique(obj);
    		return pair<iterator, bool>(p.first, p.second);
    	}
    #ifdef __STL_MEMBER_TEMPLATES
    	template <class InputIterator>
    	void insert(InputIterator f, InputIterator l) { rep.insert_unique(f, l); }
    #else
    	void insert(const value_type* f, const value_type* l) {
    		rep.insert_unique(f, l);
    	}
    	void insert(const_iterator f, const_iterator l) { rep.insert_unique(f, l); }
    #endif /*__STL_MEMBER_TEMPLATES */
    	pair<iterator, bool> insert_noresize(const value_type& obj)
    	{
    		pair<typename ht::iterator, bool> p = rep.insert_unique_noresize(obj);
    		return pair<iterator, bool>(p.first, p.second);
    	}
    
    	iterator find(const key_type& key) const { return rep.find(key); }
    
    	size_type count(const key_type& key) const { return rep.count(key); }
    
    	pair<iterator, iterator> equal_range(const key_type& key) const
    	{
    		return rep.equal_range(key);
    	}
    
    	size_type erase(const key_type& key) { return rep.erase(key); }
    	void erase(iterator it) { rep.erase(it); }
    	void erase(iterator f, iterator l) { rep.erase(f, l); }
    	void clear() { rep.clear(); }
    
    public:
    	void resize(size_type hint) { rep.resize(hint); }
    	size_type bucket_count() const { return rep.bucket_count(); }
    	size_type max_bucket_count() const { return rep.max_bucket_count(); }
    	size_type elems_in_bucket(size_type n) const
    	{
    		return rep.elems_in_bucket(n);
    	}
    };
    
    template <class Value, class HashFcn, class EqualKey, class Alloc>
    inline bool operator==(const hash_set<Value, HashFcn, EqualKey, Alloc>& hs1,
    	const hash_set<Value, HashFcn, EqualKey, Alloc>& hs2)
    {
    	return hs1.rep == hs2.rep;
    }

hash\_map的源代码实现：

//以下的hash<>是个function object 定义于<stl_hash_fun.h>中
    template <class Key, class T, class HashFcn = hash<Key>,
    class EqualKey = equal_to<Key>,
    class Alloc = alloc>
    #else
    template <class Key, class T, class HashFcn, class EqualKey,
    class Alloc = alloc>
    #endif
    class hash_map
    {
    private:
    	//以下使用的select1st<>定义于<stl_function.h>中.
    	typedef hashtable<pair<const Key, T>, Key, HashFcn,
    		select1st<pair<const Key, T> >, EqualKey, Alloc> ht;
    	ht rep; //底层机制以hash table完成.
    
    public:
    	//缺省使用大小为100的表格，将由hash table调整为最接近且较大之质数.
    	typedef typename ht::key_type key_type;
    	typedef T data_type;
    	typedef T mapped_type;
    	typedef typename ht::value_type value_type;
    	typedef typename ht::hasher hasher;
    	typedef typename ht::key_equal key_equal;
    
    	typedef typename ht::size_type size_type;
    	typedef typename ht::difference_type difference_type;
    	typedef typename ht::pointer pointer;
    	typedef typename ht::const_pointer const_pointer;
    	typedef typename ht::reference reference;
    	typedef typename ht::const_reference const_reference;
    
    	typedef typename ht::iterator iterator;
    	typedef typename ht::const_iterator const_iterator;
    
    	hasher hash_funct() const { return rep.hash_funct(); }
    	key_equal key_eq() const { return rep.key_eq(); }
    
    public:
    	hash_map() : rep(100, hasher(), key_equal()) {}
    	explicit hash_map(size_type n) : rep(n, hasher(), key_equal()) {}
    	hash_map(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
    	hash_map(size_type n, const hasher& hf, const key_equal& eql)
    		: rep(n, hf, eql) {}
    	//以下的插入操作全部使用insert_unique()，不允许键值重复.
    	hash_map(const value_type* f, const value_type* l)
    		: rep(100, hasher(), key_equal()) {
    		rep.insert_unique(f, l);
    	}
    	hash_map(const value_type* f, const value_type* l, size_type n)
    		: rep(n, hasher(), key_equal()) {
    		rep.insert_unique(f, l);
    	}
    	hash_map(const value_type* f, const value_type* l, size_type n,
    		const hasher& hf)
    		: rep(n, hf, key_equal()) {
    		rep.insert_unique(f, l);
    	}
    	hash_map(const value_type* f, const value_type* l, size_type n,
    		const hasher& hf, const key_equal& eql)
    		: rep(n, hf, eql) {
    		rep.insert_unique(f, l);
    	}
    
    	hash_map(const_iterator f, const_iterator l)
    		: rep(100, hasher(), key_equal()) {
    		rep.insert_unique(f, l);
    	}
    	hash_map(const_iterator f, const_iterator l, size_type n)
    		: rep(n, hasher(), key_equal()) {
    		rep.insert_unique(f, l);
    	}
    	hash_map(const_iterator f, const_iterator l, size_type n,
    		const hasher& hf)
    		: rep(n, hf, key_equal()) {
    		rep.insert_unique(f, l);
    	}
    	hash_map(const_iterator f, const_iterator l, size_type n,
    		const hasher& hf, const key_equal& eql)
    		: rep(n, hf, eql) {
    		rep.insert_unique(f, l);
    	}
    #endif /*__STL_MEMBER_TEMPLATES */
    
    public:
    	//所有操作几乎都有hash table对于版本，传递调用就行.
    	size_type size() const { return rep.size(); }
    	size_type max_size() const { return rep.max_size(); }
    	bool empty() const { return rep.empty(); }
    	void swap(hash_map& hs) { rep.swap(hs.rep); }
    	friend bool
    		operator== __STL_NULL_TMPL_ARGS(const hash_map&, const hash_map&);
    
    	iterator begin() { return rep.begin(); }
    	iterator end() { return rep.end(); }
    	const_iterator begin() const { return rep.begin(); }
    	const_iterator end() const { return rep.end(); }
    
    public:
    	pair<iterator, bool> insert(const value_type& obj)
    	{
    		return rep.insert_unique(obj);
    	}
    #ifdef __STL_MEMBER_TEMPLATES
    	template <class InputIterator>
    	void insert(InputIterator f, InputIterator l) { rep.insert_unique(f, l); }
    #else
    	void insert(const value_type* f, const value_type* l) {
    		rep.insert_unique(f, l);
    	}
    	void insert(const_iterator f, const_iterator l) { rep.insert_unique(f, l); }
    #endif /*__STL_MEMBER_TEMPLATES */
    	pair<iterator, bool> insert_noresize(const value_type& obj)
    	{
    		return rep.insert_unique_noresize(obj);
    	}
    
    	iterator find(const key_type& key) { return rep.find(key); }
    	const_iterator find(const key_type& key) const { return rep.find(key); }
    
    	T& operator[](const key_type& key) {
    		return rep.find_or_insert(value_type(key, T())).second;
    	}
    
    	size_type count(const key_type& key) const { return rep.count(key); }
    
    	pair<iterator, iterator> equal_range(const key_type& key)
    	{
    		return rep.equal_range(key);
    	}
    	pair<const_iterator, const_iterator> equal_range(const key_type& key) const
    	{
    		return rep.equal_range(key);
    	}
    
    	size_type erase(const key_type& key) { return rep.erase(key); }
    	void erase(iterator it) { rep.erase(it); }
    	void erase(iterator f, iterator l) { rep.erase(f, l); }
    	void clear() { rep.clear(); }
    
    public:
    	void resize(size_type hint) { rep.resize(hint); }
    	size_type bucket_count() const { return rep.bucket_count(); }
    	size_type max_bucket_count() const { return rep.max_bucket_count(); }
    	size_type elems_in_bucket(size_type n) const
    	{
    		return rep.elems_in_bucket(n);
    	}
    };
    
    template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
    inline bool operator==(const hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm1,
    	const hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm2)
    {
    	return hm1.rep == hm2.rep;
    }