用红黑树封装实现map和set

目录

1、map和set的底层

2、map与set中的key关键值

3、红黑树迭代器的实现。

1、++操作

2、-- 操作

3、==和!=操作

4、在红黑树中封装迭代器

5、map和set对迭代器的封装

1、map

map中[]的重载

2、set

---

1、map和set的底层

        map和set都是基于红黑树实现的。红黑树是一种自平衡的二叉搜索树，它保持着良好的平衡性能，插入、删除、查找的时间复杂度都是O(log n)。在C++ STL中，map和set都是使用红黑树作为底层数据结构来实现的。红黑树在前面文章模拟实现过，可以参考

rep_type通常是用来表示set容器内部红黑树的节点类型。在STL头文件中，通常会定义rep_type作为红黑树节点的类型，用于表示set容器和map容器内部的数据结构。 

可以看到set和map的源代码中都使用了红黑树作为底层数据结构。

可以看到红黑树中的数据类型只有一个，

而在map和set中都有key值，也有数据类型，map的数据类型是键值对pair<const key,T>,set中的数据类型也是key。

2、map与set中的key关键值

那么我们该如何模拟实现呢？

🚀map传给红黑树的模板参数是pair键值对

🚀set传给红黑树的模板参数是key值

 红黑树该如何判断key值来比较大小呢，这个时候我们需要使用仿函数的方法，因为红黑树比较节点只看key值。我们选择仿函数的方法：

map.h文件：

template<class K,class V>
class MYmap
{struct KeyofMap{const K& operator ()(const pair<K,V> &kv){return kv.first;}};
private:RBTree<K, pair<const K, V>, KeyofMap> _t;
};

set.h文件：

template<class T>
class Myset
{struct SetKeyofvalue{const T& operator()(const T& key){return key;}};
private:RBTree<T, const T, SetKeyofvalue> _t;
};

set存放的数据本身就是key，但是为了与红黑树结构：

以及map的结构统一，所以也需要实现一个。

3、红黑树迭代器的实现。

1、++操作

++操作也就是找到下一个比它大的值，那么就有两种可能：

1.右子树的最小值。

//如果右子树不为空，那么比这个元素大的下一个节点就是右子树的最小元素

//也就是右子树的最左节点

2.如果没有右子树，那么向上查找，直到找到一个节点是其父节点的左字数，该父节点就是符合条件的值。

Self& operator++(){//如果右子树不为空，那么比这个元素大的下一个节点就是右子树的最小元素//也就是右子树的最左节点if (_node->_right){Node* subrm = _node->_right;while (subrm->_left){subrm = subrm->_left;}_node = subrm;}//如果右子树为空，那么向上查找，直到找到一个节点是其父节点的左子树else{Node* cur = _node;Node* parent = cur->_parent;while (parent&& parent->_right == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}

2、-- 操作

--操作也就是找到下一个比它小的值，那么就有两种可能：

1.左子树存在

//找出这个迭代器前面一个比它小的元素，如果左子树存在，那么就先找左边最大的节点
//也就是右子树的最右节点

2.左子树不存在

 //如果左子树为空，那么向上查找，直到找到一个节点是其父节点的右子树

Self& operator --(){//找出这个迭代器前面一个比它小的元素，如果左子树存在，那么就先找左边最大的节点//也就是右子树的最右节点if (_node->_left){Node* sublmax = _node->_left;while (sublmax->_right){sublmax = sublmax->_right;}_node = sublmax;}//如果左子树为空，那么向上查找，直到找到一个节点是其父节点的右子树else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}

3、==和!=操作

//重载！=运算符bool operator!=(const Self& s){return _node != s._node;}//重载==运算符bool operator == (const Self & s){return _node == s._node;}

比较的内容是迭代器指向的节点是不是相同，不是比较节点的key值，同时也不需要修改，所以这里只需要const引用即可。

红黑树迭代器完整实现代码：

//红黑树迭代器
template<class T>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}T& operator *(){return _node->_data;}T* operator ->(){return &_node->_data;}Self& operator++(){//如果右子树不为空，那么比这个元素大的下一个节点就是右子树的最小元素//也就是右子树的最左节点if (_node->_right){Node* subrm = _node->_right;while (subrm->_left){subrm = subrm->_left;}_node = subrm;}//如果右子树为空，那么向上查找，直到找到一个节点是其父节点的左子树else{Node* cur = _node;Node* parent = cur->_parent;while (parent&& parent->_right == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator --(){//找出这个迭代器前面一个比它小的元素，如果左子树存在，那么就先找左边最大的节点//也就是右子树的最右节点if (_node->_left){Node* sublmax = _node->_left;while (sublmax->_right){sublmax = sublmax->_right;}_node = sublmax;}//如果左子树为空，那么向上查找，直到找到一个节点是其父节点的右子树else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}//重载！=运算符bool operator!=(const Self& s){return _node != s._node;}//重载==运算符bool operator == (const Self & s){return _node == s._node;}};

4、在红黑树中封装迭代器

在红黑树中，起始节点begin()是最左节点

结束位置是空位置节点

本文采用上面的实现方法。

为了实现左闭右开，STL库采用的是end指向哨兵位头结点，最左边节点也和头相连。

template<class K,class T,class KeyofT>
class RBTree
{
public:typedef __RBTreeIterator<T> iterator;typedef RBTreeNode<T> Node;KeyofT kot;iterator begin(){Node* subleft = _root;while (subleft && subleft->_left){subleft = subleft->_left;}return iterator(subleft);}iterator end(){return iterator(nullptr);}
private:Node* _root=nullptr;
};

5、map和set对迭代器的封装

1、map

typedef typename RBTree<K, pair<const K, V>, KeyofMap>::iterator iterator;

这里要使用typename

当在模板中使用嵌套类型或依赖于模板参数的类型推导时，需要使用typename关键字来告诉编译器这是一个类型而不是一个变量。这通常出现在模板中使用嵌套类型或依赖于模板参数的类型推导时。

map中[]的重载

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

 map中的[]可以实现查找，修改，插入三个功能。

当使用[]操作符访问map中的元素时，

如果该键已经存在，则返回对应的值；

如果该键不存在，则会插入一个新的键值对，并返回一个默认构造的值。

在红黑树中也要对insert进行修改来匹配 

 

我们来测试一下修改（更改value值）:

#pragma once
#include"RBTree.h"template<class K,class V>
class MYmap
{struct KeyofMap{const K& operator ()(const pair<K,V> &kv){return kv.first;}};
public:typedef typename RBTree<K, pair<const K, V>, KeyofMap>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}V& operator[](const K& key){pair<iterator, bool> ret = Insert(make_pair(key, V()));return ret.first->second;}pair<iterator,bool> Insert(const pair<const K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, KeyofMap> _t;
};

2、set

#pragma once
#include"RBTree.h"
template<class T>
class Myset
{struct SetKeyofvalue{const T& operator()(const T& key){return key;}};public:typedef typename RBTree<T,const T, SetKeyofvalue>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator,bool> Insert(const T& key){return _t.Insert(key);}private:RBTree<T, const T, SetKeyofvalue> _t;
};

在C++的std::map和std::set容器中，元素的键值是不可更改的，这是因为这两个容器是基于红黑树实现的，红黑树的性质要求元素的键值在插入后不能被修改，否则会破坏红黑树的结构。

所以在实现时，map使用了

RBTree<K, pair<const K, V>, KeyofMap> _t;

set使用了

RBTree<T, const T, SetKeyofvalue> _t; 

来保证key值不会被修改。 

下面给出红黑树完整的插入函数：

pair<iterator,bool> Insert(const  T& data){if (_root == nullptr){_root = new Node(data, BLACK);Node* newnode = _root;//根的双亲为头结点return make_pair(iterator(newnode), true);}Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if(kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return make_pair(cur,false);}}cur = new Node(data, RED);Node* newnode = cur;if (kot(cur->_data) < kot(parent->_data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while (parent && parent->_color == RED){Node* grandparent = parent->_parent;if (parent == grandparent->_left){Node* uncle = grandparent->_right;if (uncle && uncle->_color == RED){grandparent->_color = RED;parent->_color = BLACK;uncle->_color = BLACK;cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_left){RotateR(grandparent);parent->_color = BLACK;grandparent->_color = RED;}else{RotateL(parent);RotateR(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}else{Node* uncle = grandparent->_left;if (uncle && uncle->_color == RED){grandparent->_color = RED;parent->_color = BLACK;uncle->_color = BLACK;cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandparent);parent->_color = BLACK;grandparent->_color = RED;}else{RotateR(parent);RotateL(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}}_root->_color = BLACK;return make_pair(iterator(newnode),true);}

通过封装实现Map和Set，可以使用红黑树的特性来实现键值对的存储和查找，同时保持数据结构的平衡性和高效性。以上就是用红黑树封装实现map和set，当然这只是简单实现，对于更好地理解和使用这个容器比较有帮助。