【C++】unordered系列容器的封装

2024-07-08 1156阅读

【C++】unordered系列容器的封装

你很自由 充满了无限可能 这是很棒的事 我衷心祈祷你可以相信自己 无悔地燃烧自己的人生 -- 东野圭吾 《解忧杂货店》

unordered系列的封装

  • 1 unordered_map 和 unordered_set
  • 2 改造哈希桶
    • 2.1 模版参数
    • 2.2 加入迭代器
    • 3 上层封装
      • 3.1 unordered_set
      • 3.2 unordered_map
      • 4 面试题分析
      • Thanks♪(･ω･)ﾉ谢谢阅读！！！
      • 下一篇文章见！！！

        1 unordered_map 和 unordered_set

        unordered系列的库是以哈希桶为底层的容器，其是用来快速寻找指定数据。这里主要介绍unordered_map和unordered_set。

        unordered_map
        1. unordered_map是用来储存 键值对的容器，可以通过Key快速寻找到其对应的value,注意Key和value的类型可以不一样。并且key不可更改，value可以更改！
        2. unordered_map内部并不是按照特定顺序储存的，而是按照key转换得到的数组下标来进行存储，因此内部是无序的！
        3. unordered_map通过key查找元素比map快非常多！！！但对应迭代的速度比较慢。
        4. unordered_map允许[ ]下标访问！
        5. unordered_map只有正向迭代器！没有反向迭代器！
        unordered_set
        1. unordered_set是只储存key值的容器！和set相似，用来去重或者判断是否存在！
        2. unordered_set内部并不是按照特定顺序储存的，而是按照key转换得到的数组下标来进行存储，因此内部是无序的！
          1. unordered_set通过key查找元素比set快非常多！！！但对应迭代的速度比较慢。
        4. unordered_set不提供[ ]下标访问！
        5. unordered_set只有正向迭代器！没有反向迭代器！

        他们都提供以下接口：

        迭代器
        函数功能介绍
        begin返回unordered_map第一个元素的迭代器
        end返回unordered_map最后一个元素下一个位置的迭代器
        cbegin返回unordered_map第一个元素的const迭代器
        cend返回unordered_map最后一个元素下一个位置的const迭代器
        功能函数
        函数功能介绍
        iterator find(const K& key)返回key在哈希桶中的位置
        size_t count(const K& key)返回哈希桶中关键码为key的键值对的个数
        insert向容器中插入键值对
        erase删除容器中的键值对
        void clear()清空容器中有效元素个数
        void swap(unordered_map&)交换两个容器中的元素
        桶操作
        函数功能介绍
        size_t bucket_count()const返回哈希桶中桶的总个数
        size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数
        size_t bucket(const K& key)返回元素key所在的桶号

        接下来我们就来实现这些功能！

        2 改造哈希桶

        2.1 模版参数

        unordered_map 和 unordered_set的底层是开散列版本的哈希表（哈希桶），但是他们两个储存的数据却不一样：一个是键值对pair , 一个是键值key。所以为了可以让哈希桶适配，就要进行泛型编程的改造，增加模版参数。由上层的unordered_map 和 unordered_set控制底层的哈希桶存储什么数据，因此我们需要添加一个class T模版参数，供上层决定储存什么数据。与之对应的，从数据中获取key的仿函数。

        这样加上将转换key为size_t的仿函数，共用四个模版参数：

        1. class k : 表明键值key的类型，这是最基本的。
        2. class T: 储存的数据类型：pair 或 key。
        3. class KeyOfT: 如何从T中获取key，这是很关键的，是我感觉最巧妙的一环，通过仿函数来适配不同类型，太妙了！
        4. class HashFunc:将key值转换为size_t的数组下标。

        通过这四个模版参数，就可以通过传入对应的参数来保证适配！（迭代器我们后续来实现）

        template
class HashTable
{
public:
	typedef HashNode Node;
	iterator begin()
	{}
	iterator end()
	{}
	const_iterator begin() const 
	{}
	const_iterator end() const 
	{}
	
	HashTable()
		:hs(),
		kot()
	{
		_table.resize(10, nullptr);
		_n = 0;
	}
	//插入数据
	pair insert(const T kv)
	{}
	//删除
	bool erase(const K& key)
	{}
	//查找
	iterator find(const K& key)
	{}
private:
	//底层是一个指针数组
	vector _table;
	//有效数量
	size_t _n;
	//仿函数
	Hash hs;
	KeyOfT kot;
};

        我们的模版参数修改之后，我们的函数体也要进行改造，不能直接写死，要符合泛型编程：

        函数基本都是修改了原本的cur->_kv。first 变为 kot(cur->_kv)，通过仿函数来获取key值，并且返回值设置为迭代器。这样无论我们传入的是pair 或 key，都可以通过仿函数获取对应的key值！下面给出插入函数的代码，其余函数的改造类似！

        插入函数 
        //插入数据
pair insert(const T kv)
{
	iterator it = find(kot(kv));
	if (it != end())
		return make_pair(it, false);
	//扩容
	if (_n == _table.size() * 0.7)
	{
		//直接把原本的节点移动到新的table中即可
		vector newtable(2 * _table.size());
		//遍历整个数组
		for (int i = 0; i _next;
					//计算新的映射
					//kot(cur->_kv) 来获取 T 中的key
					size_t hashi = hs(kot(cur->_kv)) % newtable.size();
					//进行头插
					cur->_next = newtable[hashi];
					newtable[hashi] = cur;
					cur = next;
				}
			}
		}
		_table.swap(newtable);
	}
	//首先寻找到合适下标
	size_t hashi = hs(kot(kv)) % _table.size();
	//进行头插
	Node* newnode = new Node(kv);
	newnode->_next = _table[hashi];
	_table[hashi] = newnode;
	++_n;
	return make_pair(iterator(newnode , this), true);
}

        2.2 加入迭代器

        实现封装一定少不了迭代器!!!迭代器可是强大的武器，有了迭代器就可以使用基于范围的for循环，还可以通过迭代器来访问修改数据。

        那么我们就要来写一个迭代器，来供我们使用。

        哈希表的迭代器和之前写过的迭代器有所不同，我们来看奥：我们搭建一个基本框架:

        1. 首先我们需要一个节点指针，这是迭代器中的关键元素，用来访问数据
        2. 然后我们的迭代器其要支持++运算，可以移动到下一个节点。移动规则：当前桶没走完就移动到下一个元素， 当前桶走完了就移动到下一个桶的第一个元素，而移动到下一个桶需要哈希表表,所以内部需要有一个哈希表
        3. 还要提供基本的!= == * ->运算。
        4. 注意构造函数要使用const HashTable* ht低权限，因为我们不会对其修改，还要避免上层传入``const HashTable* `,所以要做好预防！
        template
struct _HTIterator
{
	typedef _HTIterator Self;
	//成员
	Node* _node;
	//哈希表
	const HashTable* _pht;
	//构造函数
	_HTIterator(Node* node, const HashTable* ht)
		:_node(node),
		_pht(ht)
	{}
	//++
	Self& operator++()
	{
	}
	//判断很好写
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
	Ref operator*() const
	{
		return _node->_kv;
	}
	Ptr operator->() const
	{
		return &_node->_kv;
	}
};

        如果我们将迭代器正常放在哈希表的外面，会发现报错：编译器不认识 HashTable,很正常，因为HashTable在其后面才进行定义，所以我们可以在迭代器之前加一个HashTable前置声明！或者使用内部类，把迭代器放HashTable内部就好了！

        然后我们就来解决这个++的问题：

        1. 如果当前桶还没有走到最后，就要移动到下一个节点，使用cur = cur ->next即可！
        2. 如果走完当前桶了（next指针是nullptr时），就要向后寻找下一个桶了。
        3. 如果找到了就继续进行，没有找到，说明走完了
        //++
Self& operator++()
{
	Hash hs;
	KeyOfT kot;
	//++
	//当前桶没走完就移动到下一个 桶走完了就移动到下一个桶 
	if (_node->_next) _node = _node->_next;
	else
	{
		//桶走完了就移动到下一个桶
		size_t i = hs(kot(_node->_kv)) % _pht->_table.size();
		i++;
		for (; i _table.size(); i++)
		{
			if (_pht->_table[i])
				break;
		}
		//走完循环有两种可能，要进行判断
		if (i == _pht->_table.size())
			_node = nullptr;
		else
		{
			_node = _pht->_table[i];
		}
	}
	return *this;
}

        这样我们的迭代器就完成了，再在hashtable中实例化普通迭代器和const迭代器：

        //迭代器
typedef _HTIterator iterator;
//const 迭代器
typedef _HTIterator const_iterator;

        然后加入我们begin()和end(）函数

        1. begin()：从哈希表的第一个桶开始寻找，找到桶中的第一个元素
        2. end() : 设置为空就可以
        iterator begin()
{
	for (size_t i = 0; i  

        这样底层就实现好了，接下来我们开始在上层做动作！
         

        3 上层封装
         

        底层的哈希桶我们已经改造完毕了，接下来就是在上层来调用：
         

        3.1 unordered_set
         

        先来看unordered_set，其底层要注意：
         

        1. unordered_set储存是key值，注意不可修改！要设置为const变量
        2. 使用仿函数SetKeyOfT来从T中获取Key值
        3. 上层要通过给对应的哈希函数
        4. 大部分函数直接调用底层Hashtable中的函数就可以！
        5. 在实例化迭代器时，需要使用typename关键字来明确指出iterator是一个类型，而不是一个变量或者别的什么。
        这样我们可以搭建起一个框架
         

        //仿函数
template
struct SetKeyOfT
{
	const K operator()(const K& k)
	{
		return k;
	}
};
template
class my_unoerder_set
{
public:
	//迭代器
	typedef typename HashTable::iterator iterator;
	typedef typename HashTable::const_iterator const_iterator;
	pair insert(const K& k)
	{
		return _table.insert(k);
	}
	iterator find(const K& k)
	{
		return _table.find(k);
	}
	bool erase(const K& k)
	{
		return _table.erase(k);
	}
	iterator begin()
	{
		return _table.begin();
	}
	iterator end()
	{
		return _table.end();
	}
	const_iterator begin() const
	{
		return _table.begin();
	}
	const_iterator end() const 
	{
		return _table.end();
	}
private:
	HashTable _table;
};

         

        这样就设置好了，我们来测试一下：
         

        void test_set1()
{
	my_unoerder_set S;
	vector arr = { "sort" , "hello" , "JLX" , "Hi" };
	for (auto e : arr)
	{
		S.insert(e);
	}
	my_unoerder_set::iterator it = S.begin();
	cout 
		//(*it)++;
		std::cout 
		//e++;
		cout 
	const K& operator()(const pair
		return kv.first;
	}
};
template
public:
	//迭代器
	typedef typename HashTable
VPS购买请点击我

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

相关阅读

目录[+]