STL set 和 map

一、标准库中 set 和 multiset 的使用

set 是一颗 K 模型的红黑树，可以存储任意类型，multiset 和 set 的区别是 multiset 允许插入重复值，set 不允许

模板参数 T 表示存储元素的类型，Compare 表示存储元素的比较方法，Alloc 是空间配置器，一般不用传

set 和 multiset 常用接口使用：

#include <iostream>
#include <set>

using namespace std;

void setUsing()
{
	// set 不允许插入重复值
	// insert 返回值为 pair<iterator, bool>
	// 如果插入的值不存在，则返回值 pair 中的 first 指向新插入的元素，second 设置为 true
	// 如果插入的值已存在，则返回值 pair 中的 first 指向已有的元素，second 设置为 false
	set<int> s;
	cout << s.insert(3).second << " ";
	cout << s.insert(1).second << " ";
	cout << s.insert(1).second << " ";
	cout << s.insert(4).second << " ";
	cout << s.insert(2).second << " ";
	cout << s.insert(1).second << " ";
	cout << endl; // 输出 1 1 0 1 1 0

	// set 不允许修改元素内容，因此 iterator 和 const_iterator 是相同的
	set<int>::iterator sit = s.begin();
	while (sit != s.end())
	{
		// *sit *= 10;
		cout << *sit << " ";
		++sit;
	}
	cout << endl; // 输出 1 2 3 4

	// find 成功返回指向该元素的迭代器，失败返回 end()
	sit = s.find(1);
	if (sit != s.end()) cout << *sit << endl; // 输出 1

	// 返回 set 中元素的数目
	cout << s.count(1) << endl; // 输出 1
}

void multisetUsing()
{
	// multiset 允许插入重复值
	std::multiset<int> s;
	s.insert(3);
	s.insert(1);
	s.insert(1);
	s.insert(4);
	s.insert(2);
	s.insert(1);

	for (auto e : s) cout << e << " ";
	cout << endl; // 输出 1 1 1 2 3 4

	// find 成功返回指向该元素的迭代器，失败返回 end()
	std::set<int>::iterator sit = s.find(1);
	if (sit != s.end()) cout << *sit << endl; // 输出 1

	// 返回 set 中元素的数目
	cout << s.count(1) << endl; // 输出 3
}

int main()
{
	setUsing();
	cout << endl;

	multisetUsing();
	cout << endl;

	return 0;
}

二、标准库中 map 和 multimap 的使用

map 是一颗 KV 模型的红黑树，可以存储任意类型，multimap 和 map 的区别是 multimap 允许插入 key 值重复的 <key, value> 键值对，map 不允许

模板参数 Key 表示 <key, value> 中 key 的类型，T 表示 <key, value> 中 value 的类型，Compare 表示存储元素的比较方法，Alloc 是空间配置器，一般不用传

map 和 multimap 常用接口使用：

#include <iostream>
#include <map>
#include <string>

using namespace std;

void mapUsing1()
{
	// map 不允许插入 key 值重复的 <key, value> 键值对
	// insert 返回值为 pair<iterator, bool>
	// 如果插入的 key 值不存在，则返回值 pair 中的 first 指向新插入的元素，second 设置为 true
	// 如果插入的 key 值已存在，则返回值 pair 中的 first 指向已有的元素，second 设置为 false
	map<string, string> dict;
	cout << dict.insert(make_pair("sort", "排序")).second << " ";
	cout << dict.insert(make_pair("string", "字符串")).second << " ";
	cout << dict.insert(make_pair("count", "计数")).second << " ";
	cout << dict.insert(make_pair("string", ""字符串"")).second << " ";
	cout << endl; // 输出 1 1 1 0

	// map 不允许修改元素内容，因此 iterator 和 const_iterator 是相同的
	map<string, string>::iterator mit = dict.begin();
	while (mit != dict.end())
	{
		cout << mit->first << ":" << mit->second << " ";
		++mit;
	}
	cout << endl; // 输出 count:计数 sort:排序 string:字符串 

	// find 通过 key 查找，成功返回指向该元素的迭代器，失败返回 end() 
	mit = dict.find("string");
	if (mit != dict.end()) cout << mit->second << endl; // 输出 字符串

	// 返回 map 中 key 的数目
	cout << dict.count("string") << endl; // 输出 1

	// operator[key] 等价于 ( *(( this->insert(make_pair(key, mapped_type())) ).first) ).second
	// 如果 key 存在，则返回对应的 <key, value> 中 value 的引用
	// 如果 key 不存在，则先插入 <key, mapped_type()> ，再返回 <key, mapped_type()> 中 value 的引用(这里的 mapped_type 是指 value 的类型)
	dict["string"] = ""字符串"";
	dict["right"] = "右边";
	for (auto& e : dict) cout << e.first << ":" << e.second << " ";
	cout << endl; // 输出 count:计数 right:右边 sort:排序 string:"字符串" 
}

// 统计每种水果出现的次数
void mapUsing2()
{
	string fruit[] = {"西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨"};
	map<string, int> fruitCount;

	for (auto &e : fruit) fruitCount[e]++;
	for (auto &e : fruitCount) cout << e.first << ":" << e.second << " ";
	cout << endl; // 输出 梨:1 苹果:5 西瓜:4 香蕉:2
}

void multimapUsing()
{
	// multimap 允许插入 key 值重复的 <key, value> 键值对
	std::multimap<std::string, std::string> m;
	m.insert(std::make_pair("string", "字符串"));
	m.insert(std::make_pair("string", ""字符串""));

	for (auto &e : m) cout << e.first << ":" << e.second << " ";
	cout << endl; // 输出 string:字符串 string:"字符串" 

	// 返回 map 中 key 的数目
	cout << m.count("string") << endl; // 输出 2
}

int main()
{
	mapUsing1();
	cout << endl;

	mapUsing2();
	cout << endl;

	multimapUsing();
	cout << endl;

	return 0;
}

三、set 和 map 底层红黑树的模拟实现

#pragma once

#include <utility>

namespace starrycat
{
	// 结点的颜色
	enum Color { RED, BLACK };

	// 红黑树的结点
	template<class VALUE>
	struct RBTreeNode
	{
		VALUE _data;
		RBTreeNode<VALUE>* _left;
		RBTreeNode<VALUE>* _right;
		RBTreeNode<VALUE>* _parent;
		Color _color;	// 结点的颜色

		RBTreeNode<VALUE>(const VALUE& data = VALUE())
			: _data(data)
			, _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _color(RED)	// 为了方便树的结构调整，新结点默认为红色
		{}
	};

	template<class T, class Ref, class Ptr>
	struct __rb__iterator
	{
		typedef RBTreeNode<T> Node;
		typedef __rb__iterator<T, Ref, Ptr> Self;
		typedef __rb__iterator<T, T&, T*> iterator;

		__rb__iterator<T, Ref, Ptr>(Node* node) : _node(node) {}
		__rb__iterator<T, Ref, Ptr>(const iterator& it) : _node(it._node) {}

		bool operator==(const Self& s) const { return _node == s._node; }
		bool operator!=(const Self& s) const { return _node != s._node; }
		Ref operator*() const { return _node->_data; }
		Ptr operator->() const { return &_node->_data; }

		void increment()
		{
			if (_node->_right)
			{
				// 根据中序遍历(左根右)，如果右子树存在，则迭代器的下一个位置为右子树的最左结点
				Node* cur = _node->_right;
				while (cur->_left) cur = cur->_left;

				_node = cur;
			}
			else
			{
				// 根据中序遍历(左根右)，如果右子树不存在，则迭代器的下一个位置为左子树包含当前结点的最近祖先结点
				Node* cur = _node;
				Node* parent = _node->_parent;
				while (parent && parent->_right == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}

				_node = parent;
			}
		}

		Self& operator++()
		{
			increment();
			return *this;
		}

		Self operator++(int)
		{
			Self tmp = *this;
			increment();
			return tmp;
		}

		void decrement()
		{
			if (_node->_left)
			{
				// 根据中序遍历(右根左)，如果左子树存在，则迭代器的下一个位置为左子树的最右结点
				Node* cur = _node->_left;
				while (cur->_right) cur = cur->_right;

				_node = cur;
			}
			else
			{
				// 根据中序遍历(右根左)，如果左子树不存在，则迭代器的下一个位置为右子树包含当前结点的最近祖先结点
				Node* cur = _node;
				Node* parent = _node->_parent;
				while (parent && parent->_left == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}

				_node = parent;
			}
		}

		Self& operator--()
		{
			decrement();
			return *this;
		}

		Self operator--(int)
		{
			Self tmp = *this;
			decrement();
			return tmp;
		}

		Node* _node;
	};

	template<class K>
	struct Less
	{
		bool operator()(const K& key1, const K& key2)
		{
			return key1 < key2;
		}
	};

	// 在查找删除数据时，map 需要用 K 作为参数的类型
	// T 是红黑树结点存储的类型，作为 set 的底层时只存储 key，作为 map 的底层时存储 <const key, value>
	// 在插入数据时，set 可以直接比较红黑树结点中的 data，而 map 则需要比较红黑树结点中的 data.first
	// 如果是 set，KEYOFT(data) 返回 data，如果是 map，KEYOFT(data) 返回 data.first
	template<class K, class T, class KEYOFT, class COMPARE = Less<K>>
	class RBTree
	{
		typedef RBTreeNode<T> Node;
	public:
		typedef __rb__iterator<T, T&, T*> iterator;
		typedef __rb__iterator<T, const T&, const T*> const_iterator;
	public:
		RBTree<K, T, KEYOFT, COMPARE>()
			: _root(nullptr)
		{}

		iterator begin()
		{
			// 根据中序遍历(左根右)，迭代器的起始位置为树的最左结点 
			Node* cur = _root;
			while (cur && cur->_left) cur = cur->_left;

			return cur;
		}

		iterator end()
		{
			return nullptr;
		}

		const_iterator begin() const
		{
			// 根据中序遍历(左根右)，迭代器的起始位置为树的最左结点 
			Node* cur = _root;
			while (cur->_left) cur = cur->_left;

			return cur;
		}

		const_iterator end() const
		{
			return nullptr;
		}

		// 插入
		std::pair<iterator, bool> Insert(const T& data)
		{
			KEYOFT kot;
			COMPARE cmp;

			// 按照二叉搜索树的方式插入结点，保证该树插入结点之后还是二叉搜索树
			if (_root == nullptr)
			{
				_root = new Node(data);
				_root->_color = BLACK;
				return std::make_pair(iterator(_root), true);;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cmp(kot(data), kot(cur->_data)))
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cmp(kot(cur->_data), kot(data)))
				{
					parent = cur;
					cur = cur->_right;
				}
				else return std::make_pair(iterator(cur), false);
			}

			Node* newnode = new Node(data);
			cur = newnode;
			if (cmp(kot(data), kot(parent->_data))) parent->_left = cur;
			else parent->_right = cur;

			cur->_parent = parent;

			// 更新颜色
			while (parent && parent->_color == RED)
			{
				Node* grandfather = parent->_parent;
				if (grandfather->_left == parent)
				{
					Node* uncle = grandfather->_right;
					
					// u 存在且为红
					// u 不存在或存在且为黑
					if (uncle && uncle->_color == RED)
					{
						grandfather->_color = RED;
						parent->_color = BLACK;
						uncle->_color = BLACK;

						// 继续判断是否违反了红黑树的性质
						cur = grandfather;
						parent = grandfather->_parent;
					}
					else
					{
						// p 为 g 的左，cur 为 p 的左 右单旋
						// p 为 g 的左，cur 为 p 的右 先左旋再右旋
						if (parent->_left == cur)
						{
							RotateR(grandfather);
							grandfather->_color = RED;
							parent->_color = BLACK;
						}
						else
						{
							RotateL(parent);
							RotateR(grandfather);
							grandfather->_color = RED;
							cur->_color = BLACK;
						}
					}
				}
				else
				{
					Node* uncle = grandfather->_left;

					// u 存在且为红
					// u 不存在或存在且为黑
					if (uncle && uncle->_color == RED)
					{
						grandfather->_color = RED;
						parent->_color = BLACK;
						uncle->_color = BLACK;

						// 继续判断是否违反了红黑树的性质
						cur = grandfather;
						parent = grandfather->_parent;
					}
					else
					{
						// p 为 g 的右，cur 为 p 的右 左单旋
						// p 为 g 的右，cur 为 p 的左 先右旋再左旋
						if (parent->_right == cur)
						{
							RotateL(grandfather);
							grandfather->_color = RED;
							parent->_color = BLACK;
						}
						else
						{
							RotateR(parent);
							RotateL(grandfather);
							grandfather->_color = RED;
							cur->_color = BLACK;
						}
					}
				}
			}

			_root->_color = BLACK;
			return std::make_pair(iterator(newnode), true);
		}

		iterator Find(const K& key)
		{
			KEYOFT kot;
			COMPARE cmp;

			Node* cur = _root;
			while (cur)
			{
				if (cmp(key, kot(cur->_data))) cur = cur->_left;
				else if (cmp(kot(cur->_data), key)) cur = cur->_right;
				else return cur;
			}

			return nullptr;
		}

	private:
		void RotateR(Node* parent)
		{
			Node* pparent = parent->_parent;
			Node* subL = parent->_left;
			Node* subLR = subL->_right;

			parent->_left = subLR;
			if (subLR) subLR->_parent = parent;

			subL->_right = parent;
			parent->_parent = subL;

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

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

			parent->_right = subRL;
			if (subRL) subRL->_parent = parent;

			subR->_left = parent;
			parent->_parent = subR;

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

	private:
		Node* _root;
	};
}

四、set 类 和 map 类的模拟实现

set 类 和 map 类常用接口模拟实现：

// test.cc
#include "set.hpp"
#include "map.hpp"

int main()
{
	starrycat::setTest1();

	starrycat::mapTest1();
	starrycat::mapTest2();
	
	return 0;
}

// set.hpp
#pragma once

#include "RBTree.h"
#include <iostream>
#include <utility>

namespace starrycat
{
	template <class K>
	struct SET_KEYOFT
	{
		const K &operator()(const K &key)
		{
			return key;
		}
	};

	template <class K>
	class set
	{
	public:
		// set 不允许修改元素内容，因此 iterator 和 const_iterator 是相同的
		typedef typename RBTree<K, K, SET_KEYOFT<K>>::const_iterator iterator;
		typedef typename RBTree<K, K, SET_KEYOFT<K>>::const_iterator const_iterator;

	public:
		// 红黑树底层实现了 iterator 构造 const_iterator
		iterator begin() const { return _rb.begin(); }
		iterator end() const { return _rb.end(); }
		std::pair<iterator, bool> insert(const K &key) { return _rb.Insert(key); }

	private:
		RBTree<K, K, SET_KEYOFT<K>> _rb;
	};

	void setTest1()
	{
		set<int> s;
		int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
		for (auto e : a) s.insert(e);

		set<int>::iterator sit = s.begin();
		while (sit != s.end())
		{
			// *sit *= 10;
			std::cout << *sit << " ";
			++sit;
		}
		std::cout << std::endl; // 输出 3 7 9 11 14 15 16 18 26
	}
}

// map.hpp
#pragma once

#include "RBTree.h"
#include <iostream>
#include <string>

namespace starrycat
{
	template<class K, class V>
	struct MAP_KEYOFT
	{
		const K& operator()(const std::pair<const K, V>& data)
		{
			return data.first;
		}
	};

	template<class K, class V>
	class map
	{
	public:
		typedef typename RBTree<K, std::pair<const K, V>, MAP_KEYOFT<K, V>>::iterator iterator;
		typedef iterator const_iterator;
	public:
		iterator begin() { return _rb.begin(); }
		const_iterator begin() const { return _rb.begin(); }
 		iterator end() { return _rb.end(); }
 		const_iterator end() const { return _rb.end(); }
		std::pair<iterator, bool> insert(const std::pair<K, V>& data) { return _rb.Insert(data); }
		V& operator[](const K& key) { return ( *(( insert(std::make_pair(key, V())) ).first) ).second; }

	private:
		RBTree<K, std::pair<const K, V>, MAP_KEYOFT<K, V>> _rb;
	};

	void mapTest1()
	{
		map<std::string, std::string> dict;
		std::cout << dict.insert(std::make_pair("sort", "排序")).second << " ";
		std::cout << dict.insert(std::make_pair("string", "字符串")).second << " ";
		std::cout << dict.insert(std::make_pair("count", "计数")).second << " ";
		std::cout << dict.insert(std::make_pair("string", ""字符串"")).second << " ";
		std::cout << std::endl; // 输出 1 1 1 0

		map<std::string, std::string>::iterator mit = dict.begin();
		while (mit != dict.end())
		{
			std::cout << mit->first << ":" << mit->second << " ";
			++mit;
		}
		std::cout << std::endl; // 输出 count:计数 sort:排序 string:字符串 

		dict["string"] = ""字符串"";
		dict["right"] = "右边";
		for (auto& e : dict) std::cout << e.first << ":" << e.second << " ";
		std::cout << std::endl; // 输出 count:计数 right:右边 sort:排序 string:"字符串" 
	}

	// 统计每种水果出现的次数
	void mapTest2()
	{
		std::string fruit[] = {"西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨"};
		map<std::string, int> fruitCount;

		for (auto &e : fruit) fruitCount[e]++;
		for (auto &e : fruitCount) std::cout << e.first << ":" << e.second << " ";
		std::cout << std::endl; // 输出 梨:1 苹果:5 西瓜:4 香蕉:2
	}
}