一、标准库中 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 设置为 falseset<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 设置为 falsemap<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.firsttemplate<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_iteratoriterator 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 0map<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}
}