C++ 第九节——map/set(用法+底层原理+模拟实现)

有了前面红黑树的底子，我们这一节的任务就比较轻松了。

关于Map和Set是什么东西，我们来借助网络文献进行解释。

首先，我们需要知道的是，Map和Set的底层都是红黑树。

即是一种平衡的二叉搜索树，也就是二叉平衡搜索树。

而set就是我们前面说到的Key模型，而map就是<K,V>模型。

我们接下来将一边对比，一边介绍。

set和map的介绍

先来看set:

通过查阅文档有关set的声明，我们可以发现：

这里的T就是我们所说的Key，就是key_type或者说是value_type，即比较大小，比较的就是这些东西。

而后的Compare，就是比较的方式。其是一个仿函数，就是告诉set，我的比较方式是怎样的。这里可参照链表的有关叙述，这里就不再赘述。

紧接着，就着下面的接口模型，我们可以简单地创建一个set然后遍历它。

 这里的都是一些成员函数，没有什么好说的了。

 像这些函数，我们早就已经用烂掉了。类比着前面的一些容器，我们在这里也就略过，具体我们可以看下面的用法实例。

我们再来看一下find函数吧：

 它的意思已经很明确了也。
就是说，找到了那个位置，就返回那个位置的迭代器。否则，就返回set::end()。

void test_set()
{
	set<int> s;       //创建
	s.insert(3); 
	s.insert(4);
	s.insert(8);
	s.insert(10);
	s.insert(1);
	s.insert(26);
	s.insert(7);
	s.insert(2);
	s.insert(3);      //插入
	set<int>::iterator is = s.begin();  //定义迭代器
	while (is != s.end())
	{
		cout << *is << " ";             //循环打印
		is++;
	}

	cout << endl;
	for (auto e : s)                    //另外一种打印方式——用范围for打印
	{
		cout << e << " ";
	}
	//排序+去重
}

void test_set1()
{
	set<string> ss;
	ss.insert("hello");                 //不断插入字符串
	ss.insert("map");
	ss.insert("set");
	ss.insert("string");
	ss.insert("wrong");
	set<string>::iterator it = ss.find("wron");  //查找，找到了则返回相应位置的迭代器，找不到 
                                                 //就返回ss.end()
	if (it == ss.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "找到了" << endl;
	}
}

int main()
{
	test_set();
    test_set1();
	return 0;
}

打印出来的结果如上图。

同样的道理，我们再来看看map

map和set其实已经非常像了，它就是多了一个参数。（就是我们上面说烂掉的K,V模型，在存储着key的值的时候，每一个Key的值后面还跟着一个Value）

 如上图所示，其在后面跟着的实际还有着一个T。也就是我们所说的value。

它的用法与set略有一点不同的是，我们需要用pair来进行插入。而关于pair是什么，我们在上一节就已经提到过，在这里，我们再来说一遍：

就是说，pair本质上也是一个类，它存储着两个类型的值，它的用处和好处就是当返回一个pair的时候，就相当于返回了两个值。

所以pair就相当于了一个打包的功能。我将两个值打包在一块，然后一块返回。（不过它本质上还是一个类）

当然，我们也可以用make_pair来去实现 

make_pair本质上是对pair类型的一个再封装。

 可以看到，一个make_pair的返回值，实际上就是一个pair。

下面的代码蕴藏了很多东西，其中包括很多内容的不同写法。各位可以细细品味一下。

void test_map1()
{
	map<int, double> m;  //K V模型
	m.insert(pair<int, double>(1, 1.1));//调用pair的构造函数，构造一个匿名对象
	m.insert(pair<int, double>(2, 2.1));
	m.insert(pair<int, double>(5, 3.4));
	m.insert(make_pair(2, 2.2));       //调用函数模板，构造对象，好处是不需要声明pair的参数， 
                                       //让函数去自己推演，用起来更方便
//	key相同就会插入失败
	map<int, double>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << (*it).first<<":"<<(*it).second << endl;
		cout << it->first << ":" << it -> second << endl;
		it++;
	}
	cout << endl;
}


void test_map2()
{
	typedef map<string, string> DICT;
	typedef pair<string, string> D_KV;
	DICT dict;
	dict.insert(D_KV("hello", "你好"));
	dict.insert(D_KV("fine", "我好"));
	dict.insert(D_KV("nice", "很好"));
	dict.insert(D_KV("no", "不好"));
	dict.insert(D_KV("OK", "好"));
	DICT::iterator it = dict.find("hello");
	if (it != dict.end())
	{
		cout << it->second << endl;
		string& str = it->second;
		str.insert(0, "{");
		str += "}";
		cout << str << endl;
	}
}

void test_map3()
{
	//也可以从文件当中去读！！文件操作！！！
	string arr[] = { "苹果","苹果" ,"苹果", "西瓜","梨子","西瓜","榴莲","香蕉","香蕉","苹果" };
	map<string, int> mp;
	/*for (const auto& str : arr)
	{
		map<string, int>::iterator it = mp.find(str);
		if (it != mp.end())
		{
			it->second++;
		}
		else
		{
			mp.insert(pair<string, int>(str, 1));
		}
	}*/
	//统计次数的方式1
	/*for (const auto& e : arr)
	{
		pair<map<string, int>::iterator, bool> ret = mp.insert(pair<string, int>(e, 1));
		if (ret.second == false)
		{
			ret.first->second++;
		}
	}*/
	//统计方式2


//	下面是统计方式3
	for (const auto& e : arr)
	{
		mp[e]++;   //[]的返回值为mapped_value，第一个返回值为一个iterator的迭代器，第二个为一个bool类型的值。
	}
	for (const auto& e : mp)
	{
		cout << e.first << ":" << e.second << endl;
	}

	map<string, string> dic;
	dic.insert(make_pair("insert", "插入"));
	dic["left"];        //插入
	dic["left"] = "左边";  //修改
	dic["right"] = "右边"; //插入+修改
	dic["left"] = "左边、剩余";
	 //mapped_value& operator[](const key_value& K)
	//{ return (this->insert(make_pair(K,mapped_value())).first).second}
}

void test_map4()
{
	string arr[] = { "苹果","苹果" ,"苹果", "西瓜","梨子","西瓜","榴莲","香蕉","香蕉","苹果" };
	map<string, int> mp;
	for (const auto& e : arr)
	{
		mp[e]++;   //[]的返回值为mapped_value，第一个返回值为一个iterator的迭代器，第二个为一个bool类型的值。
	}
	//假设需要对水果次序排序
	vector<map<string, int>::iterator> vp;            //我们用迭代器的目的，就是为了减少拷贝，深拷贝很浪费时间
	map<string, int>::iterator it = mp.begin();
	while (it != mp.end())
	{
		vp.push_back(it);
		it++;
	}
	sort(vp.begin(), vp.end(), Comp());

	//也可以直接利用map排序        存在拷贝问题   拷贝了pair数据
	map<int, string,greater<int>> mmp;
	for (const auto& e : mp)
	{
		mmp.insert(make_pair(e.second, e.first));
	}
	set<map<string, int>::iterator, Comp> SortSet;  //也可以利用set去排
	while (it != mp.end())
	{
		SortSet.insert(it);
		it++;
	}
	typedef map<string, int>::iterator M_IT;

	priority_queue<M_IT, vector<M_IT>, Comp> pq;


	while (it != mp.end())
	{
		pq.push(it);
		it++;
	}
}

void test_map5()
{
	map<string, string> dict;
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("left", "还是左边"));

	multimap<string, string> mdict;
	mdict.insert(make_pair("left", "左边"));    //允许键值冗余；不存在[]
	mdict.insert(make_pair("left", "还是左边"));

}

关于map的实际应用价值，其中有一个就是用来字典查找。

就如上面的例子所示，通过Key的值来去查找，如果找到了的话，我们就可以将其pair->second打印出来。

有关map和set的用法的内容，就暂时到这里了。还是比较简单的

我们下面来看其模拟实现：

set和map的模拟实现：

我们用一个红黑树同时实现map和set两种容器的封装。

我们这次重点来关注其是怎么实现这样的封装以及有关迭代器的实现的知识。关于红黑树的一些知识，本节就已经不再是重点关注的对象了。

废话少说，我们直接上代码。还是那句话，一切尽在代码中。实际上，这里的迭代器的模拟和链表还是非常的像的。

BRTree.h（我们复用上一节的红黑树的代码）

#pragma once
#include<iostream>
using namespace std;
enum Colour
{
	RED,
	BLACK,
};
template<class T>              //这里的模板统一改成T,即要么是K，要么是pair<K,V>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Colour _col;              //给出个参考颜色（用于标识红或者黑）

	RBTreeNode(const T& x)  //红黑树结点的构造函数
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_data(x)
		,_col(RED)
	{}

};




template<class T, class Ref, class Ptr>   //T T& T*
struct __TreeIterator
{
	typedef Ref reference;
	typedef Ptr pointer;

	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T, Ref, Ptr> Self;

	Node* _node;
	__TreeIterator(Node* node)
		:_node(node)
	{}


	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	bool operator != (const Self& s) const
	{
		return _node != s._node;
	}
	bool operator==(const Self& s) const
	{
		return !(_node != s._node);
	}
	Self operator++()                  //前置++
	{
		if (_node->_right)
		{
			Node* left = _node->_right;
			while (left->_left)
			{
				left = left->_left;
			}
			_node = left;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	Self operator--()
	{
		if (_node->_left)//根结点的左子树不为空
		{
			Node* right = _node->_left;//那么就去找左子树的最右结点
			while (right->_right)
			{
				right = right->_right;
			}
			_node = right;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
};

//迭代器适配器
template <class Iterator>
struct ReverseIterator
{
	typedef typename Iterator::reference Ref;
	typedef typename Iterator::pointer Ptr;
	typedef ReverseIterator<Iterator> Self;
	//迭代器萃取?
	ReverseIterator(Iterator it)
		:_it(it)
	{}

	Ref operator*()
	{
		return *_it;
	}
	Ptr operator->()
	{
		return _it.operator->();//?
	}
	Self& operator--()
	{
		++_it;
		return *this;
	}
	Self& operator++()
	{
		--_it;
		return *this;
	}

	bool operator !=(const Self& s) const
	{
		return !(_it == s._it);
	}


	Iterator _it;
};


template<class K, class T ,class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __TreeIterator<T, T&, T*> iterator;
	typedef __TreeIterator<T, const T&, const T*> const_iterator;
	typedef ReverseIterator<iterator> reverse_iterator;

	reverse_iterator rbegin()
	{
		Node* right = _root;
		while (right && right->_right)
		{
			right = right->_right;
		}
		return reverse_iterator(iterator(right));
	}

	reverse_iterator rend()
	{
		return  reverse_iterator(iterator(nullptr));
	}

	iterator begin()
	{
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}
		return iterator(left);
	}

	iterator end()
	{
		return iterator(nullptr);
	}

	RBTree()
		:_root(nullptr)      //构造函数初始化
	{}


	//拷贝构造和operator自己实现

	void Destroy(Node* root)//销毁函数
	{

		if (root == nullptr)
			return;
		Destroy(root->_left);  //通过不断递归来去实现，类比二叉搜索树
		Destroy(root->_right);
		delete root;
	}
	~RBTree()            //析构函数——去调用销毁函数
	{
		Destroy(_root);
	}


	Node* Find(const K& key)  //查找（类比搜索二叉树）
	{
		KeyOfT oft;
		Node* cur = _root;
		while (cur)
		{
			if (oft(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else if (oft(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	pair<iterator ,bool> insert(const T& data)//插入
	{
		KeyOfT oft;

		if (_root == nullptr)           
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(_root, true);
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (oft(cur->_data) < oft(data))//如果要实现mutimap 和 mutiset ，那就是(oft(cur->_data) <= oft(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if(oft(cur->_data) > oft(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(iterator(_root), false);
			}
		}
		Node* newnode = new Node(data);
		newnode->_col = RED;               //标记为红

		if (oft(parent->_data) < oft(data))
		{
			parent->_right = newnode;
			newnode->_parent = parent;
		}
		else
		{
			parent->_left = newnode;
			newnode->_parent = parent;
		}
		cur = newnode;                         //前面的和搜索二叉树的插入完全一样，就标记了一下颜色。这里不再过多赘述
		
		
		while (parent && parent->_col == RED)  //如果父亲存在，且颜色为红色就要处理
		{
			//关键看叔叔
			Node* grandfather = parent->_parent;//并且祖父一定存在
			if (parent == grandfather ->  _left)   //如果父亲是祖父的左孩子
			{
				Node* uncle = grandfather->_right;    //那么叔叔就是祖父的右孩子
				if (uncle && uncle->_col == RED)      //如果叔叔存在且为红（情况一）
				{
					parent->_col = uncle->_col = BLACK;//把父亲和叔叔变成黑
					grandfather->_col = RED;    //祖父变成红

					//继续往上处理
					cur = grandfather;         //将祖父的位置给孙子
					parent = cur->_parent;     //父亲变为祖父的父亲
				}
				else  //情况2+3：叔叔不存在或者叔叔存在且为黑
				{
					//情况2：单旋
					if (cur == parent->_left)   //如果孩子是父亲的左孩子
					{
						RotateR(grandfather);  //右单旋
						grandfather->_col = RED;  //再变色
						parent->_col = BLACK;
					}
					else//情况3：双旋
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;         //最终变的还是祖父的颜色和父亲的颜色
						grandfather->_col = RED;    //祖父的颜色变成红，父亲的颜色变成黑
					}
					break;
				}
			}
			else  //parent == grandparent -> _right   情况是相同的
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)//情况1
				{
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else//情况2+3
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else //cur为父亲的左
					{
						//双旋
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					//插入结束
					break;
				}
			}
		}
		_root->_col = BLACK;
		return make_pair(iterator(newnode), true);
	}

	//剩余的就不解释了，和搜索二叉树、AVLTree都是一样的道理
	//只不过这里的旋转就不需要再调节平衡因子了。
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		RotateL(parent->_left);
		RotateR(parent);
	}

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		RotateR(parent->_right);
		RotateL(parent);

	}


	void RotateL(Node* parent)    //左单旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* parentparent = parent->_parent;
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}   //两个一组
		subR->_left = parent;
		parent->_parent = subR;//两个一组

		//连接主体，找到组织
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentparent->_left == parent)
			{
				parentparent->_left = subR;

			}
			else
			{
				parentparent->_right = subR;

			}
			subR->_parent = parentparent;
		}
	}

	void RotateR(Node* parent) //右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;
		Node* parentparent = parent->_parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentparent->_left == parent)
			{
				parentparent->_left = subL;
			}
			else
			{
				parentparent->_right = subL;
			}
			subL->_parent = parentparent;
		}
	}

	bool _CheckBlance(Node* root, int blackNum, int count)
	{
		if (root == nullptr)
		{
			if (count != blackNum)
			{
				cout << "黑色节点数量不等" << endl;
			}
			return true;
		}
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在连续的红色结点" << endl;
			return false;
		}
		if (root->_col == BLACK)
		{
			count++;
		}
		return _CheckBlance(root->_left,blackNum ,count)
			&& _CheckBlance(root->_right, blackNum, count);
	}

	bool CheckBlance()
	{
		if (_root == nullptr)
		{
			return true;
		}

		if (_root->_col == RED)
		{
			cout << "根结点是红色的"<<endl;
			return false;
		}

		//找最左路径做黑色结点的参考值
		int blackNum = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK)
			{
				blackNum++;
			}

			left = left->_left;
		}
		int count = 0;
		return _CheckBlance(_root, blackNum, count);
	}
private:
	Node* _root;
};

map.h

#pragma once
#include"BRTree.h"
namespace jxwd
{
	template<class K, class V>
	class map
	{
	public:
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::reverse_iterator reverse_iterator;

		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
		reverse_iterator rbegin()
		{
			return _t.rbegin();
		}
		reverse_iterator rend()
		{
			return _t.rend();
		}
		
		pair<iterator, bool> insert(const pair<const K, V>& kv)
		{
			return	_t.insert(kv);
		}

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _t.insert(kv);
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert(make_pair(key, V()));
			return ret.first->second;
		}
	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
	};
}

set.h

#pragma once
#include "BRTree.h"
namespace jxwd
{
	template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator;
		reverse_iterator rbegin()
		{
			return _t.rbegin();
		}
		reverse_iterator rend()
		{
			return _t.rend();
		}
		bool insert(const K& k)
		{
			_t.insert(k);
			return true;
		}
		iterator end()
		{
			return _t.end();
		}
		iterator begin()
		{
			return _t.begin();
		}
	private:
		RBTree<K, K ,SetKeyOfT> _t;
	};
}

test.cpp

#include"set.h"
#include"map.h"

int main()
{

	jxwd::map<int, int> t;
	t.insert(make_pair(3, 3));
	t.insert(make_pair(2, 2));
	t.insert(make_pair(1, 1));
	t.insert(make_pair(0, 7));
	t.insert(make_pair(6, 2));
	t[2] = 7;
	jxwd::map<int, int>::reverse_iterator it = t.rbegin();
	while (it != t.rend())
	{
		cout << (*it).first << ":" << (*it).second << endl;
		cout << it->first<< ":" << it->second << endl;

		++it;
	}


	jxwd::set<int> tt;
	tt.insert(3);
	tt.insert(1);
	tt.insert(2);
	tt.insert(4);
	jxwd::set<int>::reverse_iterator sit = tt.rbegin();
	while (sit != tt.rend())
	{
		cout << *sit << endl;
		++sit;
	}
	cout << endl;;
	return 0;
}

最后的代码运行截图：

真的是懒得打字了😀，一切尽在代码中。

相信大家都能看懂😀。