当前位置：首页 > news >正文

利用红黑树封装map和set

news 2025/7/4 1:27:40

前言：

我们已经学过了如何去实现一棵完整的红黑树，而我们所知道的map和set容器的底层都是由红黑树实现的，因此我们今天来学习如何用红黑树来实现封装map和set。

本来我们需要两个红黑树去分别封装map和set，但是代码会有重复、冗余，因此我们采用泛型编程的思想，同一颗红黑树通过传不同的模板参数来分别实现map和set。就是为了复用同一个类模板的红黑树，让代码变的简洁，体现了泛型编程的思想。

比如这里的模板参数T，如果传的是K类型的，代表使用的是set，如果参数传的是pair类型的就代表是map。

问题：为什么要用两个模板参数，前面的K有什么用，我们不是只需要后面的T就可以区分这两个容器了吗？

当我们使用find这个函数的时候，传的参数必须是K类型的，因为如果我们只传后面的T模板参数，那么使用map查找值的时候，find函数的查找值的类型不可能是pair类型的，因此这里我们需要多添加一个模板参数，让find()的时候，保持一致。

这里又有一个问题，我们如何比较T类型的值？

在insert函数里面，我们需要通过比较T类型的值大小，但是如果是pair类型的值，如何比较呢？

下面是系统默认的pair的比较方式

，这与我们的比较理念有偏差，我们只希望比较first内容的值，不让second内容的值参与进来，那我们该如何解决呢？

利用仿函数解决。

我们之前只知道仿函数可以用来比较大小，但其实仿函数可以做很多事情。

比如这里，我们定义了一个仿函数之后呢，你给仿函数一个值，仿函数就会返回一个其他的值

KeyOfT仿函数取出T对象中的key！

但是在红黑树中，不清楚T类型到底是K还是key-value，但是map和set知道，因此我们可以将这个仿函数定义在我们的map和set里面，进行一个传参。

下面是map的仿函数

template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const pair<K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};

set的仿函数

	template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const K& key){return _t.Insert(key);}private:RBTree<K, const K, SetKeyOfT> _t;};

上面便是仿函数的新玩法

红黑树迭代器的实现：

++it如何实现，总体思路还是左子树、根节点、右子树的中序遍历

it指向结点，右不为空，下一个就是右子树的最左结点
it指向结点，右为空，意味这个结点的子树中序访问完了，下一个结点找祖先里面孩子 == 父亲左的那个祖先

原码：

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* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{// 祖先里面孩子是父亲左的那个Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator--(){// return *this;}bool operator!=(const Self& s){return _node != s._node;}bool operato==(const Self& s){return _node == s._node;}
};

而我们的map和set只需要调用相应的接口即可。

typename的妙用

如何复用红黑树？

--it？

查看全文

http://www.lryc.cn/news/425159.html