• 【C++进阶之路】封装unordered_set 、unordered_map

    文章目录

    前言

     之前博主写过哈希表的原理的文章，今天我们就一起学习一下库里面的unordered_set与unordered_map,并利用之前的框架搭建出来一个简单的unordered_set与unordered_map。

    一、基本框架

    1.HashTable

    	//KeyOfT实现类型的泛化，KeyOfF实现不同类型的映射函数的实现方式的泛化。
    template<class K, class T,class KeyOfT,class KeyOfF = KeyOff<K>>
    class HashTable
    {
        template<class K, class T, class Ref, class Ptr,class KeyOfT,class KeyOfF>
        friend struct HashIterator;//友元模板的迭代器的声明。
        typedef HashNode<T> Node;//结点的声明。
    public:
        typedef HashIterator<K, T,T&,T*, KeyOfT,KeyOfF> iterator;//普通迭代器
        
        typedef HashIterator<K, T,const T&, const T*, KeyOfT,KeyOfF> const_iterator;
        //const迭代器

		//迭代器
        iterator begin();
        iterator end();
        const_iterator begin() const;
        const_iterator end() const;
        
        //构造函数
        HashTable(size_t n = 17);
        
        //析构函数
        ~HashTable();
       
       //插入函数
        pair<iterator,bool> insert(const T& data);
        
        //删除函数
        bool erase(const K& key);

    private:
        vector<Node*> _table;
        size_t _n = 0;//有效结点的个数
    };
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    2.unordered_set

    template<class K>
	class unordered_set
	{
		typedef K key_type;
		typedef K val_type;
		struct SetOfT
		{
			//取Set里面的key
		};
		typedef HashTable<K, K, SetOfT> hash_type;
		typedef typename hash_type::const_iterator iterator;
		typedef iterator const_iterator;
	public:
		const_iterator begin() const;

		const_iterator end() const;

		bool insert(const key_type& key);

		bool erase(const key_type& key);


	private:

		hash_type _hash;
	};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    3.unordered_map

    	template<class K,class V>
	class unordered_map
	{
		typedef K key_type;
		typedef pair<const K, V> val_type;
		typedef V map_type;
		struct MapOfT
		{
			key_type operator()(const val_type& x)
			{
				return x.first;
			}
		};

		typedef HashTable<key_type, val_type, MapOfT> hash_type;
		typedef typename hash_type::iterator iterator;
		typedef typename hash_type::const_iterator const_iterator;

	public:
		iterator begin();

		iterator end();

		const_iterator begin() const;

		const_iterator end() const;

		bool insert(const pair<K, V>& data);

		map_type& operator[](const key_type& key );

		bool erase(const K& key);

	private:
		hash_type _hash;
	};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    二、基本实现

    1.类型的泛化

    由于unordered_map与unordered_set的底层用的都是哈希表，但是：

    • unordered_set的val_type是key
    • unordered_map的val_type是pair

    哈希表的val_type为pair,因此需要对哈希表再泛化，将哈希表的val_type改为T，实现泛化，并且对Node结点的结构也要进行修改，将其变为：

        template<class T>
    struct HashNode
    {
        HashNode(const T& val = T())
            :_data(val)
        {}
        T _data;
        HashNode* _next = nullptr;
    };

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    插入接口也变为：

        bool insert(const T& data);
    //此处是返回值是未实现迭代器之前的接口函数。

    • 1
    • 2

    如此，unordered_map与unordered_set 通过传参进行控制T的类型，进而实现泛化。

    2.仿函数

     但是由于对哈希表来说我们需要取出key来进行哈希映射，由于：

    • unordered_set传入的模板参数T就是key
    • unordered_map传入的模板参数T是pair

    因此为了取出unordered_map的key，需要在unordered_map与unordered_set传参时实现一个能取出key的功能，也就是仿函数。

    因此

    • HashTable的模板参数：
    								//取出T里面的key
	template<class K, class T,class KeyOfT,class KeyOfF = KeyOff<K>>
	    class HashTable;

    • 1
    • 2
    • 3
    • unordered_set的仿函数
    	struct SetOfT
	{
		key_type operator()(const val_type& key)
		{
			return key;
		}
	};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • unordered_map的仿函数
    	struct MapOfT
	{
		key_type operator()(const val_type& x)
		{
			return x.first;
		}
	};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    3.迭代器

    • 说明：迭代器为正向迭代器，库里面不存在反向迭代器，因为单链表不支持倒着走，并且没有意义。

    3.1基本框架

        template<class K, class T, class KeyOfK,class KeyOfF>
    class HashTable;
    template<class K, class T,class Ref, class Ptr, class KeyOfT ,class KeyOfF>
    struct HashIterator
    {
        typedef HashNode<T> Node;
        typedef HashIterator<K, T,Ref,Ptr, KeyOfT,KeyOfF> self;
        typedef HashTable<K, T, KeyOfT, KeyOfF> Table;
        typedef HashIterator<K, T, T&, T*, KeyOfT,KeyOfF> iterator;
        HashIterator(Node* node,const Table* table)
            :_node(node)
            ,_hash(table)
        {}
        HashIterator(const iterator& it)
            :_node(it._node)
            ,_hash(it._hash)
        {}
        self operator ++();

        Ref operator*();

        Ptr operator->();

        bool operator != (const self& it);
   
        bool operator == (const self& it);

    private:
        Node* _node;
        const Table* _hash;//哈希表的指针
    };

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

     看到这样的结构，其实会感觉奇怪，因为里面竟然多了一个指针，深入思考不难理解，其实我们在遍历完一条链上的数据时，需要跳到下一条链上，这时该如何跳呢？是不是该用到哈希表？这里的指针就是哈希表，用来帮助我们寻找下一条链。

    因此：这里的HashTable的前置声明，和在哈希表中出现的友元模板的声明就可以解释通了。

    3.2 ++

    • 核心逻辑：如果当前链，当前结点的下一个元素，不为空，跳到下一个结点，为空，则找到哈希表中不为空的下一条链的第一个结点。
     self operator ++()
  {
      Node* cur = _node;
      assert(cur);
      if (cur->_next)
      {
          _node = cur->_next;
          return *this;
      }
      else
      {
          KeyOfF getkey;
          KeyOfT kot;

          K key = kot(cur->_data);
          int innode = getkey(key) % _hash->_table.size();
          ++innode;
          while (innode < (int)_hash->_table.size())
          {
              if (_hash->_table[innode])
              {
                  _node = _hash->_table[innode];
                  return *this;
              }
              ++innode;
          }
          //空。
          _node = nullptr;
          return *this;
      }
  }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    3.3 构造函数

    • 细节1
         HashIterator(Node* node,const Table* table)
         :_node(node)
         ,_hash(table)
     {}

    • 1
    • 2
    • 3
    • 4
    • 这里的Table* 前面加的const修饰不是没有原因的，因为在哈希表中的const迭代器：
    const_iterator end() const;

    • 1

     这里的const是修饰的this指针，也就是 Table*, 但是由于是被const修饰表明其指向的内容不可以被修改，因此如果Table* 不加const，表明权限放大，会报错的，因此，这里为了实现const迭代器需要在Table* 前const。

    • 细节2
    	//哈希表的定义
	typedef HashIterator<K, T,T&,T*, KeyOfT,KeyOfF> iterator;
	typedef HashIterator<K, T,const T&, const T*, KeyOfT\
	,KeyOfF> const_iterator;
	//迭代器的定义
 	 typedef HashIterator<K, T, T&, T*, KeyOfT,KeyOfF> iterator;
     HashIterator(const iterator& it)
         :_node(it._node)
         ,_hash(it._hash)
     {}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 迭代器的类是struct，默认成员公有可以突破类域进行访问。
    • 当迭代器为const迭代器时，这里的iterator为const迭代器，可以实现不同类型之间进行转换的效果。
    • 迭代器的参数多一个T，看似没有用，其实在这里定义iterater时有奇效。

    3.3 完整代码

        template<class K, class T, class KeyOfK,class KeyOfF>
    class HashTable;
    template<class K, class T,class Ref, class Ptr, \
    class KeyOfT ,class KeyOfF>
    struct HashIterator
    {
        typedef HashNode<T> Node;
        typedef HashIterator<K, T,Ref,Ptr, KeyOfT,KeyOfF> self;
        typedef HashTable<K, T, KeyOfT, KeyOfF> Table;
        typedef HashIterator<K, T, T&, T*, KeyOfT,KeyOfF> iterator;
        HashIterator(Node* node,const Table* table)
            :_node(node)
            ,_hash(table)
        {}
        HashIterator(const iterator& it)
            :_node(it._node)
            ,_hash(it._hash)
        {}
        self operator ++()
        {
            Node* cur = _node;
            assert(cur);
            if (cur->_next)
            {
                _node = cur->_next;
                return *this;
            }
            else
            {
                KeyOfF getkey;
                KeyOfT kot;

                K key = kot(cur->_data);
                int innode = getkey(key) % _hash->_table.size();
                ++innode;
                while (innode < (int)_hash->_table.size())
                {
                    if (_hash->_table[innode])
                    {
                        _node = _hash->_table[innode];
                        return *this;
                    }
                    ++innode;
                }
                //空。
                _node = nullptr;
                return *this;
            }
        }
        Ref operator*()
        {
            return _node->_data;
        }
        Ptr operator->()
        {
            return &_node->_data;
        }
        bool operator != (const self& it)
        {
            return _node != it._node;
        }   
        bool operator == (const self& it)
        {
            return _node == it._node;
        }
    private:
        Node* _node;
        const Table* _hash;
    };

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    4.insert

     在实现了之前的仿函数与迭代器我们的insert的最终版本即可出来了：

      pair<iterator,bool> insert(const T& data)
  {
      KeyOfF getkey;
      KeyOfT kot;
      size_t loadfactor = _n * 10 / _table.size();
      if (loadfactor >= 10)
      {
          //换新表
          size_t newsize = 2 * _table.size();
          HashTable<K, T,KeyOfT> new_table(newsize);
          //只能移数据
          for (int i = 0; i < (int)_table.size(); i++)
          {
              Node* node = _table[i];
              int innode = i % newsize;
              while (node)
              {
                  node->_next = new_table._table[innode];
                  new_table._table[innode] = node;

                  node = node->_next;
              }
          }
          //交换数据
          swap(_table, new_table._table);
      }

      int innode = getkey(kot(data)) % _table.size();
       Node* head = _table[innode];
      while (head)
      {
          if (head->_data == data)//排除重复数据
          {
              return make_pair(iterator(head,this),false);
          }
          head = head->_next;
      }
      Node* newnode = new(Node)(data);
      //指向头结点，更新头结点。
      newnode->_next = _table[innode];
      _table[innode] = newnode;
      _n++;
      return make_pair(iterator(newnode,this),true);
  }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • unordered_set的实现
    	bool insert(const key_type& key)
	{
		return _hash.insert(key).second;
	}
	//返回迭代器的版本
	const_iterator insert(const key_type& key)
	{
		pair<typename hash_type::iterator, bool> x = \
		_hash.insert(key);
		//利用之前模板写的构造函数，进行不同类型之间的转化。
		pair<const_iterator, bool> data(x.first, x.second);
		return data.first;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • unordered_map的实现
    	bool insert(const pair<K, V>& data)
	{
		return _hash.insert(data).second;
	}

    • 1
    • 2
    • 3
    • 4

    5. []

    • 只有map才能实现
    	map_type& operator[](const key_type& key )
	{
		pair<iterator, bool> x = _hash.insert(make_pair(key,\
		 map_type()));

		return x.first->second;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    总结

     有之前的封装map与set的经验，想必这里按部就班一步一步进行实现，一步一步进行纠错是不难实现的，最后如果觉得文章有所帮助的话，不妨点个赞鼓励一下吧！

  • 相关阅读:
    学习react笔记（生命周期）
    为SpringBoot Admin监控的服务端加上登录认证
    Text2SQL之不装了，我也是RAG
    boost-asio-1-定时器使用
    超级适合小白！学Java必读书籍，强烈推荐
    基于uni-app+vue3渲染markdown格式|uniapp软键盘顶起问题解决方案
    力扣295.数据流的中位数[困难]
    AbstractHandlerMethodAdapter类简介说明
    Node.js 安装配置
    爬虫数据清洗可视化实战-就业形势分析
  • 原文地址：https://blog.csdn.net/Shun_Hua/article/details/133426288