1.map和set的应用

map和set的使用通过查找相关文档即可熟悉。这里给出几道习题用于熟悉map和set的用法：

692. 前K个高频单词使用map解题

KY264 单词识别使用map解题

160. 相交链表使用set解题

138. 复制带随机指针的链表使用map解题

class Solution {
public:Node* copyRandomList(Node* head) {map<Node*,Node*> m;//map映射旧节点和新节点Node* cur = head;while(cur){m[cur] = new Node(cur->val);//新节点使用旧节点的val值创建cur = cur->next;}cur = head;while(cur){m[cur]->next = m[cur->next];//新节点的next指针是旧节点对应的v模型m[cur]->random = m[cur->random];//新节点的random指针是旧节点对应的v模型cur = cur->next;}return m[head];}
};

2.红黑树的封装(部分功能)

namespace ly
{enum Corlor	//枚举颜色{RED, BLACK};template <class KV>	//红黑树的节点并不知道KV到底是什么struct RBTreeNode{RBTreeNode<KV>* _left;RBTreeNode<KV>* _right;RBTreeNode<KV>* _parent;KV _data;Corlor _cor;RBTreeNode(const KV& data):_left(nullptr), _right(nullptr), _parent(nullptr),_data(data), _cor(RED){}};template<class KV,class Ref,class Ptr>//迭代器是指向某一节点的，所以其模板参数为KVstruct RBTreeIterator//也就说迭代器也不知道指向的KV是什么{typedef RBTreeNode<KV> Node;typedef RBTreeIterator<KV, Ref, Ptr> Self;Node* _node;RBTreeIterator(Node* node):_node(node){}Ref operator*()//解引用就是返回一个KV的引用。至于怎么用，由调用的用户决定{return _node->_data;}Ptr operator->()//同理{return &_node->_data;}bool operator!=(const Self& s) const{return _node != s._node;}// 如何实现迭代器++?Self& operator++(){if (_node->_right)//情况1，如果当前节点的右子树不为空{//很明显，下一个节点将是右子树中最左节点Node* min = _node->_right;while (min && min->_left){min = min->_left;}_node = min;}else//情况2，当前节点的右子树为空{//那么迭代器就要往上找//中序遍历的顺序为 左 根 右//也就是说，如果当前节点是其父节点的左孩子//那么下一个位置其父节点//如果当前节点是其父节点的右孩子//说明中序遍历已经走完了，需要重复遍历Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}};//使用三个参数兼容set和map使用一份红黑树//第一个参数可用作查找//第二个参数才是红黑树真正放的节点(要不为K，要不为KV)//第三个参数是从KV提取K的仿函数template <class K, class KV, class KOfKV>class RBTree{public:typedef RBTreeNode<KV> Node;typedef RBTreeIterator<KV, KV&, KV*> iterator;//普通迭代器typedef RBTreeIterator<KV, const KV&, const KV*> const_iterator;//const迭代器iterator begin(){//最左节点便是第一个节点//也就是begin指向的节点Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){//以空作为end迭代器return iterator(nullptr);}const_iterator begin() const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return const_iterator(cur);}const_iterator end() const{return const_iterator(nullptr);}//insert返回键值对//注意，这里返回的迭代器都是普通迭代器pair<iterator,bool> insert(const KV& data){KOfKV kof;//仿函数对象,负责提取KV中的Kif (_root == nullptr){_root = new Node(data);_root->_cor = BLACK;	//根节点的颜色必须是黑色return make_pair(_root, true);//插入成功second设为true}Node* parent = nullptr;Node* cur = _root;while (cur){if (kof(data) < kof(cur->_data)){parent = cur;cur = cur->_left;}else if (kof(data) > kof(cur->_data)){parent = cur;cur = cur->_right;}else{return make_pair(cur,false);//存在则设为false}}cur = new Node(data);Node* ret = cur;//因为等会cur的位置会变，这里先记录一下cur->_cor = RED;	//新插入的节点颜色为红色if (kof(data) < kof(parent->_data)){parent->_left = cur;cur->_parent = parent;}else if (kof(data) > kof(parent->_data)){parent->_right = cur;cur->_parent = parent;}// 此时如果新插入的节点破坏了红黑树的性质，就必须做一些微调while (parent && parent->_cor == RED){// 调整动作Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_cor == RED){// 情况1parent->_cor = uncle->_cor = BLACK;grandfather->_cor = RED;cur = grandfather;parent = cur->_parent;}else	// unle不存在或uncle存在且为黑{if (parent->_left == cur){// 情况2RotateR(grandfather);parent->_cor = BLACK;grandfather->_cor = RED;}else if (parent->_right == cur){// 情况3RotateL(parent);RotateR(grandfather);cur->_cor = BLACK;grandfather->_cor = RED;}break;	//关键}}else if (grandfather->_right == parent)	//镜像即可{Node* uncle = grandfather->_left;if (uncle && uncle->_cor == RED){parent->_cor = uncle->_cor = BLACK;grandfather->_cor = RED;cur = grandfather;parent = cur->_parent;}else{if (parent->_right == cur){// 情况2RotateL(grandfather);parent->_cor = BLACK;grandfather->_cor = RED;}else if (parent->_left == cur){// 情况3RotateR(parent);RotateL(grandfather);cur->_cor = BLACK;grandfather->_cor = RED;}break;	//关键}}}_root->_cor = BLACK;	//确保根节点颜色为黑色return make_pair(ret,true);}private:Node* _root = nullptr;void RotateL(Node* parent){Node* cur = parent->_right;Node* curL = cur->_left;	//cur的左树parent->_right = curL;	//cur的左树变成parent的右树if (curL){curL->_parent = parent;}Node* oldParent = parent->_parent;	//记录parent的父节点parent->_parent = cur;	//cur作为parent的父节点cur->_left = parent;	//parent作为cur的左树if (oldParent == nullptr){_root = cur;	//直接让cur作为根节点(因为parent的旧父节点为空)cur->_parent = nullptr;}else{if (oldParent->_left == parent){oldParent->_left = cur;cur->_parent = oldParent;}else if (oldParent->_right == parent){oldParent->_right = cur;cur->_parent = oldParent;}}}void RotateR(Node* parent){Node* cur = parent->_left;Node* curR = cur->_right;parent->_left = curR;	//cur的右树作为parent的左树if (curR){curR->_parent = parent;}Node* oldParent = parent->_parent;parent->_parent = cur;cur->_right = parent;	//parent作为cur的右树if (oldParent == nullptr){_root = cur;cur->_parent = nullptr;}else{if (oldParent->_left == parent){oldParent->_left = cur;cur->_parent = oldParent;}else if (oldParent->_right == parent){oldParent->_right = cur;cur->_parent = oldParent;}}}};
}

解析：迭代器的++算法。这里也有一道对应力扣的题：面试题 04.06. 后继者

3.map的封装(部分功能)

#include "RBTree.h"
namespace ly
{template<class K, class V>class map{public:struct KeyOfMap//提供给红黑树的仿函数{K operator()(const pair<const K, V>& kv){return kv.first;}};//加上typename表示是某类中的类型而非静态变量typedef typename RBTree<K, pair<const K, V>, KeyOfMap>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, KeyOfMap>::const_iterator const_iterator;iterator begin(){return _rb.begin();}iterator end(){return _rb.end();}const_iterator begin() const{return _rb.begin();}const_iterator end() const{return _rb.end();}pair<iterator, bool> insert(const pair<const K, V>& kv){return _rb.insert(kv);}V& operator[](const K& k){//只通过insert接口实现[]运算符重载//1.先使用临时变量接收insert的返回值pair<iterator, bool> p = insert(make_pair(k, V()));//2.p中的first就是迭代器，指向了insert的节点return p.first->second;}private:RBTree<K, pair<const K, V>, KeyOfMap> _rb;//红黑树对象};
}

4.set的封装(部分功能)

#include "RBTree.h"
namespace ly
{template<class K>class set{public:struct KeyOfSet//提供给红黑树的仿函数{K operator()(const K& k){return k;}};//加上typename表示是某类中的类型而非静态变量//需要注意，通常我们不希望改变set中K值//所以set使用的迭代器都是const迭代器typedef typename RBTree<K, K, KeyOfSet>::const_iterator iterator;typedef typename RBTree<K, K, KeyOfSet>::const_iterator const_iterator;iterator begin() const{return _rb.begin();}iterator end() const{return _rb.end();}pair<iterator, bool> insert(const K& k){/*又因为set使用的const迭代器而底层红黑树的insert接口返回的是普通迭代器而普通迭代器是不能类型转换成const迭代器的*///return _rb.insert(k);//所以需要在底层的迭代器上做更改//使得普通迭代器能够构造出const迭代器//所以，第一步：先使用普通迭代器的pair对象接收返回值pair<typename RBTree<K, K, KeyOfSet>::const_iterator, bool> p = _rb.insert(k);//第二步：再用普通迭代器构造出const迭代器return pair<iterator, bool>(p.first, p.second);}private:RBTree<K, K, KeyOfSet> _rb;//红黑树对象};
}

修改后的迭代器模块：

template<class KV,class Ref,class Ptr>//迭代器是指向某一节点的，所以其模板参数为KVstruct RBTreeIterator//也就说迭代器也不知道指向的KV是什么{typedef RBTreeNode<KV> Node;typedef RBTreeIterator<KV, Ref, Ptr> Self;//普通迭代器typedef RBTreeIterator<KV, KV&, KV*> iterator;Node* _node;RBTreeIterator(Node* node):_node(node){}//构造函数接收一个普通迭代器作为参数RBTreeIterator(const iterator& it):_node(it._node){}//...............省略.............};