C++ STL : 模拟实现STL中的关联式容器map和set

关联式容器

关联式容器和序列式容器都是存储数据的，但是唯一不同的地方就是关联式容器存储的是以<key, value>的键值对pair，并且关联型容器如map和unordered_map等容器都是以红黑树和哈希桶等结构作为底层，在数据检索和插入删除的效率也比序列式容器高。

键值对

键值对其实就是一种用来表示映射关系的一种结构，结构中包含一个Key和一个value。key代表着索引的键值，而value代表着索引映射的数据，通过一个Key来映射一个value。例如我们可以通过身份证来找到一个人的信息，或者通过学号来找到一个学生。

下面是SGI版本的STL库中实现的pair

template <class T1, class T2>struct pair{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair(): first(T1()), second(T2()){}pair(const T1& a, const T2& b): first(a), second(b){}};

底层红黑树的改造

数据结构：红黑树的原理以及实现（C++）

红黑树的实现上一篇博客已经完成，但是如果想用来实现map和set，来需要进行改造

仿函数

因为我们需要使用一棵红黑树来实现KV模型的map和K模型的set，为了实现代码复用，此时就需要用仿函数来解决这个问题，我们需要用到三个模板参数

template<class K, class T, class KOfV>

这里的K指的是key的类型，T是参数的类型。

对于KV模型的map来说，他的K即是key的类型，而T则是键值对pair<K, V>。

对于K模型的set来说，他的K即是key的类型，而T也是key的类型。这样做的原因是保持代码的一致性，方便我们进行代码复用。

同时，我们还需要考虑如何从参数中获取key，k模型的set还好说，因为它的参数T本身就是key，但是kv模型的map则存在了问题，因为它参数T是一个pair<K,V>的键值对，他的key是参数的first，此时两边就会存在差异。

甚至对于其他模型，还有其他的获取Key的方法。

因为容器需要考虑的是泛用性，所以对于这种问题，可以增加一个仿函数作为模板参数，让使用者自己提供从T中获取key的方法即可。

例如map

struct MapKeyOfValue{const K& operator()(const std::pair<K, V>& kv){return kv.first;}};

set

struct SetKeyOfValue{const K & operator()(const K & key){return key;}};

红黑树的迭代器

红黑树的遍历，其实也就是中序遍历，那也就是说，迭代器的遍历要基于中序。而中序的起点和终点分别是红黑树的最左子树和最右子树，那么问题来了，begin对应的是最左子树，而end对应的是最右子树的下一个位置，这个位置该怎么处理？按照迭代器的性质来说，最后一个位置一般都是不存储任何数据的多余的空间，并且那块空间是可以进行操作的，因为我们可能需要通过对end来进行–倒序遍历，所以直接给nullptr也是行不通的。

所以我们可以设计一个这样的结构，通过添加一个head节点来解决这个问题。

头节点的左子树指向最左节点，右子树指向最右节点。同时，头节点与根节点互相为对方的父节点。并且将头结点设置为红色，和根节点区分开来。

此时，begin为最左节点，end即为head节点。所以迭代器的遍历就从最左节点出发，按照中序遍历走完走到最右节点，然后当走到尽头时，下一步就是走到end也就是head节点。而如果是从end–,就直接让head访问到他的右子树即可。

template<class T, class Ptr, class Ref>class __RBTreeIterator{public:typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ptr, Ref> Self;__RBTreeIterator(Node* node) : _node(node){}Ref operator *(){return _node->_data;}//调用时其实调用的是->->，这里返回的是数据对象的指针，然后再从指针中取数据。编译器优化所以只看到一个Ptr operator ->(){return &_node->_data;}//红黑树迭代器的++ --其实就是其在中序遍历中的次序变化Self& operator++(){/*中序遍历：先访问所有节点的左子树，接着访问这些节点的右子树。而++，其实就是其在中序遍历的下一个位置1.如果当前节点的右子树不为空，则说明当前节点的右子树还没遍历完，下一个位置则是右子树的最左节点。2.如果此时右子树为空，则说明当前节点的所有子树访问完，但是当前节点也可能为其他树的右子树，所以一直往上，找到孩子为父亲的左子树的结点，那个父亲的位置则是下一个位置*/if (_node->_right){Node* cur = _node->_right;//找到右子树的最左节点while (cur->_left){cur = cur->_left;}_node = cur;}else{Node* parent = _node->_parent;Node* cur = _node;//往上找，直到父节点为空或者孩子节点为父节点的左子树while (parent->_right == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self operator++(int){Self temp(*this);++(*this);return temp;}/*而--，其实就是其在中序遍历的上一个位置，思路和++差不多1.如果当前节点的左子树不为空，则访问左子树的最右节点2.如果此时左子树为空，则说明子树的最左节点已经访问，接着就往上查找，找到孩子为父亲的右节点的位置，那个父亲就是下一个位置*/Self& operator--(){if (_node->_parent->_parent == _node && _node->_color == RED){//如果此节点为头结点，则说明--应该回到最右子树的位置，也就是头结点的右子树，而因为头结点和根节点形成闭环，所以当//_node->_parent->_parent == _node，并且color为红时，说明为_head。_node = _node->_right;}else if (_node->_left){Node* cur = _node->_left;//找到左子树的最右节点while (cur && cur->_right){cur = cur->_right;}_node = cur;}else{Node* parent = _node->_parent;Node* cur = _node;//往上找，直到父节点为空或者孩子节点为父节点的右子树while (parent->_right != cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self operator--(int){Self temp(*this);--(*this);return temp;}bool operator==(const Self& s){return _node == s._node;}bool operator!=(const Self& s){return _node != s._node;}private:Node* _node;};

完整代码

按照上面说的对红黑树进行改造

#pragma once#include<iostream>namespace lee{enum Color{BLACK,RED,};template<class T>struct RBTreeNode{RBTreeNode(const T& data = T(), const Color& color = RED) : _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _color(color){}Node* _left;Node* _right;Node* _parent;T _data;Color _color;};template<class T, class Ptr, class Ref>class __RBTreeIterator{public:typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ptr, Ref> Self;__RBTreeIterator(Node* node) : _node(node){}Ref operator *(){return _node->_data;}//调用时其实调用的是->->，这里返回的是数据对象的指针，然后再从指针中取数据。编译器优化所以只看到一个Ptr operator ->(){return &_node->_data;}//红黑树迭代器的++ --其实就是其在中序遍历中的次序变化Self& operator++(){/*中序遍历：先访问所有节点的左子树，接着访问这些节点的右子树。而++，其实就是其在中序遍历的下一个位置1.如果当前节点的右子树不为空，则说明当前节点的右子树还没遍历完，下一个位置则是右子树的最左节点。2.如果此时右子树为空，则说明当前节点的所有子树访问完，但是当前节点也可能为其他树的右子树，所以一直往上，找到孩子为父亲的左子树的结点，那个父亲的位置则是下一个位置*/if (_node->_right){Node* cur = _node->_right;//找到右子树的最左节点while (cur->_left){cur = cur->_left;}_node = cur;}else{Node* parent = _node->_parent;Node* cur = _node;//往上找，直到父节点为空或者孩子节点为父节点的左子树while (parent->_right == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self operator++(int){Self temp(*this);++(*this);return temp;}/*而--，其实就是其在中序遍历的上一个位置，思路和++差不多1.如果当前节点的左子树不为空，则访问左子树的最右节点2.如果此时左子树为空，则说明子树的最左节点已经访问，接着就往上查找，找到孩子为父亲的右节点的位置，那个父亲就是下一个位置*/Self& operator--(){if (_node->_parent->_parent == _node && _node->_color == RED){//如果此节点为头结点，则说明--应该回到最右子树的位置，也就是头结点的右子树，而因为头结点和根节点形成闭环，所以当//_node->_parent->_parent == _node，并且color为红时，说明为_head。_node = _node->_right;}else if (_node->_left){Node* cur = _node->_left;//找到左子树的最右节点while (cur && cur->_right){cur = cur->_right;}_node = cur;}else{Node* parent = _node->_parent;Node* cur = _node;//往上找，直到父节点为空或者孩子节点为父节点的右子树while (parent->_right != cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self operator--(int){Self temp(*this);--(*this);return temp;}bool operator==(const Self& s){return _node == s._node;}bool operator!=(const Self& s){return _node != s._node;}private:Node* _node;};template<class K, class T, class KOfV>class RBTree{public:typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, T*, T&> iterator;typedef __RBTreeIterator<T, const T*, const T&> const_iterator;RBTree() : _head(new Node(T(), RED)){_head->_left = _head;_head->_right = _head;_head->_parent = _head;}~RBTree(){destory(_head->_parent);}//头结点的左子树即是begin()iterator begin() {return iterator(_head->_left);}//头结点本身就是end()iterator end() {return iterator(_head);}const_iterator begin() const{return iterator(_head->_left);}const_iterator end() const{return iterator(_head);}Node* leftMax(){Node* cur = _head->_parent;while (cur && cur->_left){cur = cur->_left;}return cur;}Node* rightMax(){Node* cur = _head->_parent;while (cur && cur->_right){cur = cur->_right;}return cur;}void _InOrderTravel(Node* root) const{if (root == nullptr)return;_InOrderTravel(root->_left);std::cout << root->_data.first << ':' << root->_data.second << std::endl;_InOrderTravel(root->_right);}void InOrderTravel() const{_InOrderTravel(_head->_parent);}void destory(Node*& root){Node* node = root;if (!root)return;destory(node->_left);destory(node->_right);delete node;node = nullptr;}//右旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;//如果subLR存在，则让他的父节点指向parent。if (subLR){subLR->_parent = parent;}subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;//两种情况//如果parent为根节点，则让subL成为新的根节点if (parent == _head->_parent){_head->_parent = subL;subL->_parent = _head;}//如果不是根节点，则改变subL与其祖父节点的指向关系else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}//左旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _head->_parent){_head->_parent = subR;subR->_parent = _head;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}iterator Find(const T& data){//根据二叉搜索树的性质，从根节点出发，比根节点大则查找右子树，比根节点小则查找左子树Node* cur = _head->_parent;KOfV kofv;while (cur){//比根节点大则查找右子树if (koft(data) > kofv(cur->_data)){cur = cur->_right;}//比根节点小则查找左子树else if (koft(data) < kofv(cur->_data)){cur = cur->_left;}//相同则返回else{return iterator(cur);}}//遍历完则说明查找不到，返回falsereturn iterator(_head);}std::pair<iterator, bool> Insert(const T& data){KOfV kofv;//按照二叉搜索树的规则先找到位置//创建根节点if (_head->_parent == _head){Node* root = new Node(data, BLACK);//形成环形结构root->_parent = _head;_head->_left = root;_head->_right = root;_head->_parent = root;return std::make_pair(iterator(_head->_parent), true);}Node* cur = _head->_parent;Node* parent = _head;while (cur){if (kofv(data) > kofv(cur->_data)){parent = cur;cur = cur->_right;}else if (kofv(data) < kofv(cur->_data)){parent = cur;cur = cur->_left;}else{return std::make_pair(iterator(cur), false);}}//新插入节点为红色cur = new Node(data, RED);//保存插入的结点，因为后面会往上更新红黑树，所以cur可能会变化。Node* newNode = cur;//判断插入位置if (kofv(cur->_data) > kofv(parent->_data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//更新红黑树，如果父节点的颜色为黑，则说明满足条件，不需要处理，如果为红，则说明不满足，需要处理。while (cur != _head->_parent->_parent && parent && parent->_color == RED){Node* ppNode = parent->_parent;//如果父节点为祖父的左子树if (ppNode->_left == parent){//此时判断叔叔节点的状态，红黑树状态取决于叔叔Node* uncle = ppNode->_right;//第一种情况，如果叔叔节点存在且为红，则直接把父亲和叔叔变黑，祖父节点边红即可。然后再从祖父的位置继续往上调整if (uncle && uncle->_color == RED){//变色uncle->_color = parent->_color = BLACK;ppNode->_color = RED;//继续往上cur = ppNode;parent = cur->_parent;}/*叔叔节点为黑或者不存在，此时有两种情况情况二：cur为父节点的左子树，即直线状态。情况三：cur为父节点的右子树，即折线状态。情况二单旋一次后更改颜色即可完成对于情况三，如果将其进行一次旋转后再稍微处理，就可以转换成情况二*/else{//因为这里的双旋和AVL不一样，可以不用处理平衡因子，所以如果为折线则先旋转处理后，将其转换为直线处理即可。//第三种情况，折线状态，转换为直线状态处理if (parent->_right == cur){RotateL(parent);//单旋后再交换节点，即可变成直线状态。std::swap(parent, cur);}//处理第二种状态RotateR(ppNode);parent->_color = BLACK;ppNode->_color = RED;//处理完成break;}}//如果父亲为祖父的右子树else{//此时叔叔为左子树。Node* uncle = ppNode->_left;if (uncle && uncle->_color == RED){uncle->_color = parent->_color = BLACK;ppNode->_color = RED;cur = ppNode;parent = cur->_parent;}else{if (parent->_left == cur){RotateR(parent);std::swap(cur, parent);}RotateL(ppNode);ppNode->_color = RED;parent->_color = BLACK;break;}}}//为了防止不小心把根节点改为红色，最后手动改为黑色即可_head->_parent->_color = BLACK;//插入后更新头结点的状态。_head->_left = leftMax();_head->_right = rightMax();return std::make_pair(iterator(newNode), true);}/*判断是否为红黑树，就是判断其是否满足红黑树的特性特性：1.根节点必须为黑节点2.不存在连续的红结点3.从某一节点出发到其所有的叶子节点，其中经过的黑色节点数量相等*/bool IsRBTree(){if (_head->_parent == nullptr){//空树也是红黑树return true;}//违反性质1if (_head->_parent->_color != BLACK){return false;}//获取从根节点出发的任意一条子路径的黑色节点数，这里选取最左子树。Node* cur = _head->_parent;size_t blackCount = 0;size_t count = 0;while (cur){if (cur->_color == BLACK){blackCount++;}cur = cur->_left;}//递归判断其他路径的黑色节点数return _IsRBTree(_head->_parent, count, blackCount);}bool _IsRBTree(Node* root, size_t count, const size_t blackCount){//此时说明已经走到叶子节点，判断黑色节点数是否相等，不相等则违反性质3if (root == nullptr){if (count != blackCount){return false;}else{return true;}}//如果没走完，就接着判断其他情况//判断性质2，如果存在连续的红结点，则返回错误Node* parent = root->_parent;if (parent && root->_color == RED && parent->_color == RED){return false;}//如果当前节点为黑色，则记录if (root->_color == BLACK){count++;}//接着递归判断当前节点的所有路径return _IsRBTree(root->_left, count, blackCount) && _IsRBTree(root->_right, count, blackCount);}private://封装一个头结点，头结点的父亲指向根节点，左子树指向begin()也就是最左节点，右子树则为最右节点，这么做的意义是因为end(）要返回最右节点的下一个节点。//并且头结点为红色，用于区分根节点Node* _head;};}

set

set的文档介绍

文档介绍
set是按照一定次序存储元素的容器在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。set在底层是用红黑树实现的。
注意事项
与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。set中插入元素时，只需要插入value即可，不需要构造键值对。set中的元素不可以重复(因此可以使用set进行去重)。使用set的迭代器遍历set中的元素，可以得到有序序列set中的元素默认按照小于来比较set中查找某个元素，时间复杂度为：O(logN)set中的元素不允许修改(为什么?)set中的底层使用红黑树实现

set的实现

#pragma once#include"RBTree.hpp"namespace lee{template<class K>class set{public:struct SetKeyOfValue{const K & operator()(const K & key){return key;}};typedef typename RBTree<K, K, SetKeyOfValue>::iterator iterator;typedef typename RBTree<K, K, SetKeyOfValue>::const_iterator const_iterator;iterator begin(){return _tree.begin();}iterator end(){return _tree.end();}iterator find(const K& key){return _tree.Find(key);}std::pair<iterator, bool> insert(const K& key){return _tree.Insert(key);}private:RBTree<K, K, SetKeyOfValue> _tree;};};

map

map的文档介绍

文档介绍
map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值 key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，
为其取别名称为pair: typedef pair value_type;在内部，map中的元素总是按照键值key进行比较排序的。map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。map通常被实现为红黑树
注意事项
map中的的元素是键值对map中的key是唯一的，并且不能修改默认按照小于的方式对key进行比较map中的元素如果用迭代器去遍历，可以得到一个有序的序列map的底层为平衡搜索树(红黑树)，查找效率比较高支持[]操作符，operator[]中实际进行插入查找。

map的实现

operator[]

在map中，我们可以通过[]操作符来实现数据的查找和删除，这是个十分便利的东西，那么他是如何实现的呢？

其实他底层调用的是Insert，而Insert的返回值是一对键值对pair，pair的成员是那个位置的迭代器还有插入是否成功的bool值，因为map的key是具有唯一性的，所以使用[]第一次访问时，就相当于通过key来插入了一个默认value类型的数据，如果已经有了，就不插入而是相当于使用了查找的功能，然后通过返回的迭代器，来获取到value的引用。

V& operator[](const K& key){std::pair<iterator, bool> ret = _tree.Insert(std::make_pair(key, V()));return ret.first->second;}

完整代码

#pragma once#include"RBTree.hpp"namespace lee{template<class K, class V>class map{public:struct MapKeyOfValue{const K& operator()(const std::pair<K, V>& kv){return kv.first;}};//模板要在调用时才会初始化，所以这里要加上typename表明为类型名typedef typename RBTree<K, std::pair<K, V>, MapKeyOfValue>::iterator iterator;typedef typename RBTree<K, std::pair<K, V>, MapKeyOfValue>::const_iterator const_iterator;iterator begin(){return _tree.begin();}iterator end(){return _tree.end();}iterator find(const K& key){return _tree.Find(std::make_pair(key, V()));}std::pair<iterator, bool> insert(const std::pair<K, V>& kv){return _tree.Insert(kv);}V& operator[](const K& key){std::pair<iterator, bool> ret = _tree.Insert(std::make_pair(key, V()));return ret.first->second;}private:RBTree<K, std::pair<K, V>, MapKeyOfValue> _tree;};};

multimap/multiset

multi的意思就是多的意思，而multimap和multiset就是可以具有重复key值的map和set,实现起来也很简单，和上面的代码一样，只需要改变插入时的判断即可，因为原来的插入如果key值相同时，就直接返回false。

只需要在第一项中的>改为>=即可

while (cur){if (kofv(data) >= kofv(cur->_data)){parent = cur;cur = cur->_right;}else if (kofv(data) < kofv(cur->_data)){parent = cur;cur = cur->_left;}else{return std::make_pair(iterator(cur), false);}}