1 .关联式容器

C++中的map是标准模板库（STL）中的一种关联容器，它存储的是键值对（key-value pairs），其中每个键都是唯一的。

键值对：

• 用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。

​

创建键值对对象：

1. pair<T1, T2>(x, y) 使用构造函数的方式构造一个匿名对象
2. make_pair(x, y) 是一个函数模板，其中返回的是一个pair的匿名对象

​

         2 .红黑树模板参数

• set是K模型的容器，而map是KV模型的容器，这里我们如何用一棵KV模型的红黑树同时实现map和set。
• 这里我们就需要控制map和set传入底层红黑树的模板参数，为了与原红黑树的模板参数进行区分，我们将红黑树第二个模板参数的名字改为T。

template<class K, class T>
class RBTree

T模板参数可能只是键值Key，也可能是由Key和Value共同构成的上述键值对。

• 如果是set容器，那么它传入底层红黑树的模板参数就是两个Key

template<class K>
class set
{
public://其他内容
private:RBTree<K, K> _t;
};

如果是map容器，那么它传入底层红黑树的模板参数就是Key以及Key和Value构成的键值对：

template<class K, class V>
class map
{
public://其他内容
private:RBTree<K, pair<K, V>> _t;
};

问题：能不能不要红黑树的第一个模板参数，只保留第二个模板参数？

• 红黑树的第一个模板参数是不能省略的。
• 对于set容器来说，省略红黑树的第一个参数没问题，因为set传入红黑树的第二个参数与第一个参数是一样的。
• 但是对于map容器来说就不行了，因为map容器所提供的接口当中有些是只要求给出键值Key的，比如find和erase。

结点当中存储的数据

• 对于set容器来说，底层红黑树结点当中存储K和T都是一样的，
• 但是对于map容器来说，底层红黑树就只能存储T了。
• 由于底层红黑树并不知道上层容器到底是map还是set，因此红黑树的结点当中直接存储T就行了。
• 因此，当上层容器是set的时候，结点当中存储的是键值Key；
• 当上层容器是map的时候，结点当中存储的就是<K, V>键值对。

//红黑树节点
template<class T>
struct RBTreeNode
{//三叉链RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;//存储的数据T _data;//结点的颜色int _col; //红/黑//构造函数RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};

         3 . 模板参数中增加仿函数

• 由于结点当中存储的是T，这个T可能是Key，也可能是<Key, Value>键值对。那么当我们需要进行结点的键值比较时。就需要知道用什么数据比较大小。
• 当上层容器是set的时候T就是键值Key，直接用T进行比较即可，
• 当上层容器是map的时候，我们需要从<Key, Value>键值对当中取出键值Key后，再用Key值进行比较。或者按照其他方法
• 上层容器map需要向底层红黑树提供一个仿函数，用于获取T当中的键值Key。

所以：当底层红黑树当中需要比较两个结点的键值时，就可以通过这个仿函数来获取T当中的键值了。

template<class K, class V>
class map
{//仿函数——重载（）struct MapKeyOfT{const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值Key{return kv.first;}};
private:RBTree<K, pair<K, V>, MapKeyOfT> _t;
};

• 由于我们的map和set都是用的同一颗树，所以对于底层红黑树来说，它不知道上层容器是map还是set。
• 因此当需要进行两个结点键值的比较时，底层红黑树都会通过传入的仿函数来获取键值Key，进而进行两个结点键值的比较。
• 所以，set容器也需要向底层红黑树传入一个仿函数并且是必不可少的。因为与map用的同一颗树。

template<class K>
class set
{//仿函数struct SetKeyOfT{const K& operator()(const K& key) //返回键值Key{return key;}};
private:RBTree<K, K, SetKeyOfT> _t;
};

• 此时，set容器传入底层红黑树的就是set的仿函数，map容器传入底层红黑树的就是map的仿函数。
• 所以当底层红黑树需要进行两个结点之间键值的比较时，都会通过传入的仿函数来获取相应结点的键值，然后再进行比较。

示例：

• //查找函数
  iterator Find(const K& key)
  {KeyOfT kot;Node* cur = _root;while (cur){
  //kot(x)就是获取x中比较大小的一部分if (key < kot(cur->_data)){cur = cur->_left; //找右孩子}else if (key > kot(cur->_data)){cur = cur->_right; //找左孩子}else //找到了目标结点就返回该节点{return iterator(cur); }}return end(); //查找失败
  }
  

当然，所有进行结点键值比较的地方，均需要通过仿函数获取对应结点的键值后再进行键值的比较。 

         4 . 正向迭代器

• map的迭代器是一种指针，指向map中的元素。map的迭代器有两种类型：const_iterator和iterator。const_iterator用于只读访问，而iterator可以读写。
• 红黑树的正向迭代器实际上就是对结点指针进行了封装，因此在正向迭代器当中实际上就只有一个成员变量，那就是正向迭代器所封装结点的指针。

迭代器的特性

• map的迭代器遵循双向迭代器的要求，可以向前和向后遍历。

• 迭代器失效：迭代器在map被修改时（插入或删除）可能会失效。

• map的迭代器可以通过解引用操作符（*）来访问指向的元素，或者使用箭头操作符（->）来访问元素的成员。

//正向迭代器
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
//取别名 方便后面写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; //返回结点数据的指针
}

重载==和!=运算符时，直接判断两个迭代器所封装的结点，这个节点Node里面实现过：

//判断两个正向迭代器是否不同
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 = 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 = parent;parent = parent->_parent;}_node = parent; //--后变为该结点}return *this;
}

 正向迭代器实现后，我们需要在红黑树的实现当中进行迭代器类型的typedef。

注意：这棵树是要被外层的map和set封装的，他们要看见树中的iterator才能使用。

• 因此，为了让外部能够使用typedef后的正向迭代器类型iterator，我们需要在public区域进行typedef。

 实现成员函数begin和end：

• begin函数返回中序序列当中第一个结点的正向迭代器，即最左结点。
• end函数返回中序序列当中最后一个结点下一个位置的正向迭代器，这里直接用空指针构造一个正向迭代器。

template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node; //结点的类型
public:typedef __TreeIterator<T, T&, T*> iterator; //正向迭代器iterator begin(){//寻找最左结点Node* left = _root;while (left&&left->_left){left = left->_left;}//返回最左结点的正向迭代器return iterator(left);}iterator end(){//返回由nullptr构造得到的正向迭代器return iterator(nullptr);}
private:Node* _root; //红黑树的根结点
};

C++标准库中的实现： 

C++STL库当中实现红黑树时，在红黑树的根结点处增加了一个头结点。

该头结点的左指针指向红黑树当中的最左结点，右指针指向红黑树当中的最右结点，父指针指向红黑树的根结点。

在该结构下：

• 实现begin()时，直接用头结点的左孩子构造一个正向迭代器即可。
• 实现rbegin()时，直接用头结点的右孩子构造一个反向迭代器即可（实际是先用该结点构造一个正向迭代器，再用正向迭代器构造出反向迭代器）。
• 实现end()和rend()时，直接用头结点构造出正向和反向迭代器即可。
• 此后，通过对逻辑的控制，就可以实现end()进行–操作后得到最后一个结点的正向迭代器。

实现该结构需要更改当前很多函数的逻辑，例如：

• 插入结点时，若插入到了红黑树最左结点的左边，或最右结点的右边，此时需要更新头结点左右指针的指向

         5 .反向迭代器

• 红黑树的反向迭代器实际上就是正向迭代器的一个封装，前面我们在list的时候讲过过。红黑树的反向迭代器就是一个迭代器适配器。
• 在反向迭代器当中只有一个成员变量，那就是反向迭代器封装的正向迭代器。反向迭代器中的成员函数，都是通过调用正向迭代器对应的函数来完成相应功能的。

//反向迭代器---迭代器适配器
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator
{typedef ReverseIterator<Iterator, Ref, Ptr> Self;//反向迭代器所封装的正向迭代器Iterator _it;
正向迭代器构造一个反向迭代器ReverseIterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){//return _it->;//return _it.operator->();return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s){return _it != s._it;}
};

有了反向迭代器后，我们需要在红黑树的实现当中进行迭代器类型的typedef，并在红黑树当中实现成员函数rbegin和rend：

template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node; 
public: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(){//返回由nullptr构造得到的反向迭代器return reverse_iterator(iterator(nullptr));}
private:Node* _root; 
};

         6 .set的模拟实现

注意：我们需要将键值对的第一个Key加上const，在map和set中我们不能取修改键，值可以修改。因为修改了键后，他的位置就可能需要重新调整了。

template<class K>
class set
{//仿函数struct SetKeyOfT{const K& operator()(const K& key) //返回键值Key{return key;}};
public:typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator; //正向迭代器typedef typename RBTree<K, K, SetKeyOfT>::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 K& key){return _t.Insert(key);}//删除函数void erase(const K& key){_t.Erase(key);}//查找函数iterator find(const K& key){return _t.Find(key);}
private:RBTree<K, const K, SetKeyOfT> _t;
};

         7 .map的模拟实现

template<class K, class V>
class map
{//仿函数struct MapKeyOfT{const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值Key{return kv.first;}};
public:typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; //正向迭代器typedef typename RBTree<K, pair<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);}//[]运算符重载函数V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));iterator it = ret.first;return it->second;}//删除函数void erase(const K& key){_t.Erase(key);}//查找函数iterator find(const K& key){return _t.Find(key);}
private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

         8 .map—set总体代码​​​​​​​

map_set · HYD/C++ - 码云 - 开源中国