C++——map和set

码农世界 2024-06-06 前端 124 次浏览 0个评论

前言：这篇文章将继续分享C++的两大新容器——map和set。

我们前边所分享的vector、list等容器，它们的底层是顺序表，链表等序列式容器，它们的作用是单纯的存储数据，数据与数据之间几乎毫无关联。
而接下来要分享的map和set，则是以搜索二叉树为底层的关联式容器，不仅仅可以存储数据，还可以用于快速查找数据，存储的数据与数据之间通常有很强的关联性。
map和set的底层为搜索二叉树（红黑树）。
目录

一.map和set理解

1.set

2.map

二.map和set实现

1.基本框架

2.迭代器

3.map重载[]

总结

一.map和set理解

1.set

set从简单的角度理解，就是一颗二叉搜索树，每个节点存放一个元素，并且不允许有相同元素的节点出现，被要求的是，节点的值不能被修改，但可以增加或删除。

2.map

而map则是在set的基础上，将存储数据更替为键值对pair，其中K一般是不能更改的，而V是能够更改的。

二.map和set实现

由于map和set的底层都是红黑树，所以这里我们分享一种map和set共用一份红黑树代码的实现方式。

1.基本框架

首先我们要知道，map和set存储的数据类型是有区别的，前者为pair键值对，后者为单一的数据类型K，所以对于红黑树的数据类型，我们需要做出更改：
```
template
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	T _data;
	Colour _col;
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};
```
能够看出，我们直接将数据类型改为模版T，用来替换pair和K，数据直接用data代替。

当进行插入操作时，我们又会面临一些问题：
- 如果是set，当进行比较操作时直接比较K，无妨。
- 但是如果是map，比较时则会比较pair，虽然pair类型可以进行比较，但是其底层的比较方式却与我们想要的结果不同。
  为了让map也进行key的比较，我们引入仿函数，通过仿函数，来获取到map中pair的key：
```
		struct MapKeyOfT
		{
			const K& operator(const pair& kv)
			{
				return kv.first;
			}
		};
		struct SetKeyOfT
		{
			const K& operator(const K& key)
			{
				return key;
			}
		};
```
  为了帮助map完成操作，set也同样需要一个仿函数。
  
  由于仿函数需要创建对象使用，所以我们还需引入新的模版KeyOfT：
```
template
class RBTree
{
	typedef RBTreeNode Node;
public:
	//插入
	bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;//根给黑色
			return true;
		}
		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
```
  那么为什么我们这里还要保留模版参数K呢？？
  
  这是因为当使用find函数和erase等函数时，无论是map还是set，我们只需要传入K即可。
  
  进行数据比较时，只需调用仿函数，即可完成key的比较。
  
  到此，两个容器的基本框架才算完成：
```
#include"RBTree.h"
namespace MyMapSet
{
	template
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		bool Insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree _t;
	};
}
```
```
#include"RBTree.h"
namespace MyMapSet
{
	template
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair& kv)
			{
				return kv.first;
			}
		};
	public:
		bool Insert(const pair& kv)
		{
			return _t.Insert(kv);
		}
	private:
		RBTree, MapKeyOfT> _t;
	};
}
```
  2.迭代器
  
  那么map和set只要是C++的容器，就一定会存在迭代器，下面我们直接通过代码来分析迭代器的常用功能该如何实现。
```
template
struct __RBTreeIterator
{
	typedef RBTreeNode Node;
	typedef __RBTreeIterator Self;
	Node* _node;
	__RBTreeIterator(Node* node)
		:_node(node)
	{}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
};
```
  创建一个迭代器类能更好的帮助我们在红黑树类中实现迭代器功能。
  
  这些功能容易理解，这里就不做过多解释。
  
  下面我们来分析关键功能++。
  
  首先红黑树是二叉搜索树，其数据本质上是按升序的顺序排序，所以当使用++时，我们得到的一定是按升序的下一个数据。
  
  而我们已经知道，红黑树的中序遍历结果即为升序，所以在一棵同时包含父子节点的树中，其三个节点的大小顺序为：左子节点 < 根节点 < 右子节点。
  
  所以如果该节点为左子节点，那么++之后的节点就是其父节点，如果该节点为父节点，那么++之后的节点则会是其右子树的最小节点。而如果该节点为右子节点，那么就说明其为该棵同时包含父子节点的树中的最大节点，此时就要循环往上遍历，直至循环至根节点，说明此时已经为整棵树的最大节点，再++即为空。
  
  或者循环过程中cur节点为父节点的子节点，再++则为父节点。
```
	Self& operator++()
	{
		if (_node->_right)//有右子树，去找右子树的最左子节点
		{
			Node* leftMin = _node->_right;
			while (leftMin && leftMin->_left)
			{
				leftMin = leftMin->_left;
			}
			_node = leftMin;
		}
		else//没有右子树，则找到其父节点
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)//如果该节点为父节点的右子树，则向上循环
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;//直至循环至根节点，或者循环过程中cur节点为父节点的子节点
		}
		return *this;
	}
```
  完成迭代器类的实现之后，紧接着就是将其封装在红黑树类中：
```
template
class RBTree
{
	typedef RBTreeNode Node;
public:
	typedef __RBTreeIterator Iterator;
	Iterator Begin()
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}
		return Iterator(leftMin);
	}
	Iterator End()
	{
		return Iterator(nullptr);
	}
```
  而迭代器的begin，即为整棵树的最左节点，end即为空。
  
  最后再将其分别封装到map和set中，即可完成迭代器的实现：
  
  set：
```
	public:
		typedef typename RBTree::Iterator iterator;
		iterator begin()
		{
			return _t.Begin();
		}
		iterator end()
		{
			return _t.End();
		}
```
  map：
```
	public:
		typedef typename RBTree, MapKeyOfT>::Iterator iterator;
		iterator begin()
		{
			return _t.Begin();
		}
		iterator end()
		{
			return _t.End();
		}
```
  测试如下：
  
  最后还有一个值得关注的问题，就是set和map的key都是不能被修改的，但是我们上边的代码并不能实现：
  
  这是不合理的，而解决的方法为：
  
  map：
  
  RBTree, MapKeyOfT> _t;
  
  typedef typename RBTree, MapKeyOfT>::Iterator iterator;
  set：
  
  RBTree _t;
  typedef typename RBTree::Iterator iterator;
  
  在封装时即将key定义为const类型，便可保证其不能被修改。
  
  3.map重载[]
  
  map不同于set的另外一点就在于其重载了运算符[]，可以使得map通过key来直接得到其value。
  
  当key存在时，就返回其对应的value，不存在则会新插入该key，并返回其迭代器。
  
  所以想要重载[]，我们还需对插入函数进行改进：
```
pair Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;//根给黑色
			return make_pair(Iterator(_root),true);//树为空，创建并返回迭代器
		}
		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(Iterator(cur), false);//节点存在，返回
			}
		}
        cur = new Node(data);
		Node* newnode = cur;//插入后cur会变，所以提前记录
		cur->_col = RED;//新增节点给红色
        //此处省略插入步骤
       _root->_col = BLACK;
		return make_pair(Iterator(newnode), true);//树不为空，但不存在，返回新节点
	}
```
  要将插入函数的返回值改为pair类型，同时包含Iterator和bool。
  
  此时我们便可在map中重载[]：
```
		V& operator[](const K& key)
		{
			pair ret = _t.Insert(make_pair(key,V()));
			return ret.first->second;
		}
```
  定义ret去接收返回值，其中ret.first得到的是迭代器，而迭代器中也包含data的pair类型，所以再取second即可返回value。
  
  测试如下：
  
  总结
  
  关于map和set就分享这么多，喜欢本篇文章记得一键三连，我们下期再见！