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

【c++】set和map的封装

news 2026/5/4 16:15:47

一、框架搭建（如何实现红黑树的复用？）

set和map的底层都是红黑树，但由于存储元素的差异（一个只存储key，一个既存储key又存储value），我们要么创造出两棵稍微不一样的红黑树，或者是改变红黑树的结构，使其能完美匹配上set和map。库里面采用了后者。

1. 分析库里set与map的实现（分析RBTree的两个模板参数 Key, Value）

库里面RBTree的实现一共有5个模板参数，分别是 Key，Value，KeyOfValue，Compare和Alloc，我们主要分析前三个模板参数的作用）。Compare是控制比较规则的仿函数类型，Alloc是内存池。

在这里插入图片描述

对于set，它只有一个用来接收key类型的模板参数Key，并把Key同一个类型命名为key_type与value_type。
对于map，它有两个分别用来接收key和 value类型的模板参数Key和T。将Key重命名为key_type，将pair<const Key, T> 重命名为value_type。
它们复用同一棵红黑树，将4个类型传给红黑树。

在这里插入图片描述

重点观察Value这个模板参数，它的类型是节点所存储的元素的类型。set传过来的是Key类型，map传过来的是pair<const Key, T>类型。利用模板来控制红黑树所存储的类型，满足set和map不同的存储需求。

在这里插入图片描述

我们传递给map的只是key和value的类型，而map要存储的是pair<const key, value>类型（实现key和value的绑定，const实现不可修改以后再加），所以我们需要做一个加工。
既然有了接收存储元素类型的Value类型，而为什么不删除第一个用来单独存储key类型的模板参数Key，似乎用不上它，这个以后就能知道了。

2. 分析第三个模板参数KeyofValue

我们在进行插入时，需要根据key的大小来找到插入的位置，而由于set和map存储类型的不同，set直接用Value（key）类型的元素就好，而map则需要取出Value(pair<const key, value>)里面的key值来找到插入的位置。

在这里插入图片描述

而KeyOfValue这个模板参数就是用来接收功能为取出key的仿函数类型，KeyOfValue是匿名对象。可以参照库里的实现大胆猜测。

在这里插入图片描述

set里面传给KeyOfValue的是一个ideneity<value_type>类型的仿函数，identity在这里是本身的意思，它的功能就是取出key值就是value_type类型的元素它本身，而map里面传给KeyOfValue的是一个select1st<value_type>类型的仿函数，它的功能就是取出key值就是value_type类型元素里的第一个值。

在这里插入图片描述

所以我们在set和map里面的实现里面都要实现一个仿函数用来传递给KeyOfValue。

set：

代码语言：javascript

AI代码解释

namespace mosheng { template<class K> class identity { public: K& operator()(const K& key) { return key; } }; template<class Key> class set { typedef RBTree<Key, Key, identity<Key>> rbType; }; }

map:

代码语言：javascript

AI代码解释

namespace mosheng { template<class K, class KV> class select1st { public: K& operator()(const KV& kv) { return kv.first; } }; template<class Key, class Value> class map { typedef RBTree<Key, std::pair<Key, Value>, select1st<Key, std::pair<Key, Value>> rbType; }; }

不要忘了对应的红黑树的修改，主要是修改insert和find还有对应的模板参数，去用KeyOfValue提取key。然后框架搭建完毕。

代码语言：javascript

AI代码解释

#pragma once enum Colour { RED, BLACK }; template<class Value> struct RBTreeNode { RBTreeNode(Value& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) { }; Value _kv; RBTreeNode<Value>* _left; RBTreeNode<Value>* _right; RBTreeNode<Value>* _parent; Colour _col = RED; }; template<class Key, class Value, class KeyOfValue> class RBTree { typedef RBTreeNode<Value> Node; public: bool Insert(Value& kv) { //处理空树的情况 if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; return true; } //找到要插入的位置 else { Node* cur = _root; Node* parent = nullptr; while (cur) { if (KeyOfValue()(kv) < KeyOfValue()(cur->_kv)) { parent = cur; cur = cur->_left; } else if (KeyOfValue()(kv) > KeyOfValue()(cur->_kv)) { parent = cur; cur = cur->_right; } else { return false; } } //插入新节点 cur = new Node(kv); if (KeyOfValue()(parent->_kv) > KeyOfValue()(kv)) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; //父节点为红色的情况下需要进行处理 if (parent->_col == RED) { while (parent && parent->_col == RED) { //记录节点 Node* grandfather = parent->_parent; Node* uncle = nullptr; if (grandfather->_left == parent) { uncle = grandfather->_right; } else { uncle = grandfather->_left; } //uncle为红色的情况 //仅变色 if (uncle && uncle->_col == RED) { uncle->_col = parent->_col = BLACK; grandfather->_col = RED; //更新 cur = grandfather; parent = cur->_parent; } //uncle为黑色或为空的情况 else { //右旋转 if (grandfather->_left == parent && parent->_left == cur) { RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; break; } //左旋转 else if (grandfather->_right == parent && parent->_right == cur) { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; break; }//左右双旋 else if (grandfather->_left == parent && parent->_right == cur) { RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; break; } //右左双旋 else { RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; break; } } } } } //处理根节点颜色 _root->_col = BLACK; return true; } void InOrder() { _InOrder(_root); cout << endl; } Node* Find(const Key& key) { Node* cur = _root; while (cur) { if (KeyOfValue()(cur->_kv) < key) { cur = cur->_right; } else if (KeyOfValue()(cur->_kv) > key) { cur = cur->_left; } else { return cur; } } return nullptr; } Node* _root = nullptr; };

可以使用匿名对象，但推荐构造一个对象kof来使用仿函数KefOfValue。
为什么保留第一个Key的模板参数在find函数上就有所体现：我们需要Key的类型，因为要根据Key的类型来寻找。KefOfValue无法提取出类型。

二、迭代器的实现

迭代器的实现也就是在节点指针的基础之上做封装操作，并重载一些运算符。map和set的迭代器是双向迭代器，关键是需要实现++和–的重载。

1. 普通迭代器iterator的实现

1.1 先搭一个基本框架

代码语言：javascript

AI代码解释

template<class Value> class TreeIterator { typedef RBTreeNode<Value> Node; typedef TreeIterator<Value> Self; public: TreeIterator(Node* node) :_node(node) {} Value& operator* () { return _node->_kv; } Value* operator->() { return &(_node->_kv); } bool operator==(const Self& s)const { return _node == s->_node; } bool operator!=(const Self& s)const { return _node != s->_node; } private: Node* _node; };

1.2 operator++与operator- -实现

operator++

我们希望达成的效果是++从当前节点移动到下一个按照中序遍历的节点。- -则是反过来。++只需要知道当前节点的下一个节点是哪一个。

在这里插入图片描述

现在我们有一棵红黑树，若当前节点为18，那么我们希望节点18++后的节点是节点25，节点25++后的节点是节点30，以此类推。
首先看节点10，它不是叶子节点，++后需要跳到节点15，也就是它的右节点，这是因为它的右子树不为空，按照中序遍历顺序，可以认为它的左子树是遍历完成的，只需要看它的右子树就行。所以首先要判断当前节点的右子树是否为空。再来看节点30，++后需要跳到节点35，是其右子树的最左节点。若不为空就会跳到节点30的左孩子节点40，节点40的左子树是还未访问过的，所以需要访问它的左子树，一直到最左端。

查看全文

http://www.jsqmd.com/news/751734/