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

C++ 之【map和set的模拟实现】(只涉及map和set的插入、迭代器以及map的operator[]函数)

news 2025/8/31 12:08:18

1.树节点存储数据的类型

2.KeyOfT仿函数

3.迭代insert函数

4.内部实现的迭代器

(1)红黑树迭代器的常规操作

(2)红黑树迭代器++操作

(3)红黑树迭代器--操作

(4)红黑树中操纵迭代器

5.外部封装迭代器

(1)set封装迭代器

(2)map封装迭代器

6.map的operator[]

(1)再次迭代insert函数(最终版本)

(1)set迭代insert函数

(2)map迭代insert函数及 [ ]

map和set底层是红黑树，即map和set只是对红黑树进行封装再实现

下面使用的红黑树是在上一期博客模拟实现的红黑树的基础上进行迭代更新的

1.树节点存储数据的类型

template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Color _col;RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){ }
};template<class K, class T>
class RBTree
{typedef RBTreeNode<T> Node;
public:private:Node* _root = nullptr;
};

(1)为了使同一个类模板适配set和map容器，将节点存储数据类型参数化，那么
外界传入pair就是map，传入key就是set

(2)红黑树模板中第一个参数用来表示键值类型，第二个参数表示节点存储数据类型

参数K(第一个参数)存在的意义之一是，保证map能够进行键值比较操作，因为
set中键值类型与传入的T类型一致，map中T类型却是pair<K, V>（与键值类型K不一致）
如果不传入参数K，那find函数等需要键值类型的函数就被实现

2.KeyOfT仿函数

Node* find(const K& key)
{if (!_root)return nullptr;KeyOfT kot;Node* cur = _root;while (cur){//节点中存在的数据不一定是键值，利用仿函数，取出键值if (kof(cur->_data) > key){cur = cur->_left;}else if (kot(cur->_data) < key){cur = cur->_right;}else{return cur;}}return nullptr;
}

正如注释所言，树节点中存放的数据有可能是pair，此时pair无法和键值类型K进行比较

解决方法就是：map和set封装红黑树时传入对应的仿函数(此时的set仍然陪跑)

将pair中的键值取出来进行比较大小，此时还应有一个仿函数用来控制键值比较的规则：

即用户可传入的仿函数
template<class K, class Com>
class set
{
private:RBTree<K, K, SetKeyOfT, Com> _t;
};template<class K, class T, class KeyOfT, class Com>
class RBTree
{typedef RBTreeNode<T> Node;KeyOfT kot;Com _com;if (_com(kof(cur->_data),key))...........private:Node* _root = nullptr;
};

3.迭代insert函数

bool Insert(const T& data)
{if (!_root){_root = new Node(data);_root->_col = BLACK;//单参数构造return make_pair(_root, true);}KeyOfT kot;Node* parent = _root;Node* cur = _root;while (cur){if (kot(data) > kot(cur->_data)){parent = cur;cur = cur->_right;}else if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(data);Node* newnode = cur;cur->_parent = parent;if (kot(data) > kot(parent->_data)){parent->_right = cur;}else{parent->_left = cur;}//控制红黑节点while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle 不存在 或者 存在且为黑{//		g//	  p//cur if (cur == parent->_left){RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}//	g//p//	cur else{RotateL(parent);RotateR(grandfather);parent->_col = grandfather->_col = RED;cur->_col = BLACK;}break;}}else//parent == grandfather->right{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle 不存在 或者 存在且为黑{//g//	p//	cur if (cur == parent->_right){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}//	g//		p//	cur else{RotateR(parent);RotateL(grandfather);parent->_col = grandfather->_col = RED;cur->_col = BLACK;}break;}}}_root->_col = BLACK;return true;
}

修改插入数据的参数类型，利用KeyOfT仿函数进行比较操作，set、map完成封装操作后程序就可以实现插入操作了
//map和set的insert只是去调用红黑树的insert，这就是封装
bool insert(const pair<K, V>& kv)
{return _t.Insert(kv);
}
bool insert(const K& key)
{return _t.Insert(key);
}

4.内部实现的迭代器

C++库里面的红黑树有一个哨兵位的树节点

但是如果有一个哨兵位的话，插入时可能需要维护哨兵位的左右指针，删除时可能需要维护哨兵位的parent(指向根节点)，旋转时同样需要注意哨兵位的指向，所以呢，模拟实现的时候没有增加哨兵位的节点，这里也不增加

(1)红黑树迭代器的常规操作

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);
}bool operator!= (const self& s){return _node != s._node;}
};

(1)使用一个类定义迭代器，包括但不限于解引用、成员访问、加加减减操作

(2)普通迭代器和const迭代器的区别就是解引用和成员访问后对内容的权限，而不是++--

这里使用一个类模板，通过外界传入的参数即可产生普通迭代器和const迭代器

不懂的朋友可参考我的博客模拟实现list

(3)红黑树的迭代器封装了树节点指针

(4)使用struct定义迭代器，方便后续使用

(2)红黑树迭代器++操作

迭代器实现的是中序遍历，所以

当节点的右子树不为空，迭代器移动到右子树的最小(左)节点

当节点的右子树为空，说明需要向上寻找移动到的节点了

self& operator++()
{if (!_node){assert(false);}if (_node->_right){//右子树的最小节点就是下一个节点Node* leftMin = _node->_right;while (leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else{//右子树为空，说明需要向上移动了Node* cur = _node;Node* parent = cur->_parent;//cur是parent的左孩子节点，parent就是下一个访问节点//cur是parent的右孩子节点，说明parent已经被访问过了(中序遍历)，需要继续想上寻找//直到cur是parent的左孩子节点，或者遇到parent为空while (parent && parent->_right == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}

(3)红黑树迭代器--操作

迭代器实现的是中序遍历，所以

当节点的左子树不为空，迭代器移动到右子树的最大(右)节点

当节点的左子树为空，说明需要向上寻找移动到的节点了

self& operator--()
{if (!_node){assert(false);}if (_node->_left){//左子树不为空，移动到左子树的最大节点Node* leftMax = _node->_lef;while (leftMax->_right){leftMax = leftMax->_right;}_node = leftMax;}else{//左子树为空，需要向上寻找Node* cur = _node;Node* parent = cur->_parent;//cur是parent的右孩子节点，parnet就是要移动到的节点//cur是parent的左孩子节点，说明parent已经被访问过了//++是左 根 右，--是右 根 左，cur是左，parent是根，继续向上寻找while (parent && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}

前置加加、前置减减操作都已实现，后置加加、减减只需保存先前的值即可，这里不再赘诉

(4)红黑树中操纵迭代器

由图易得，begin返回的是最左节点，end返回的是空节点

typedef __TreeIterator<T, T&, T*> iterator;
typedef __TreeIterator<T, const T&, const T*> const_iterator;iterator begin()
{//最小节点Node* leftMin = _root;//条件一是为了防止树为空while (leftMin && leftMin->_left){leftMin = leftMin->_left;}//单参数构造迭代器return leftMin;
}iterator end()
{return nullptr;
}const_iterator begin()const
{//最小节点Node* leftMin = _root;//条件一是为了防止树为空while (leftMin && leftMin->_left){leftMin = leftMin->_left;}//单参数构造迭代器return leftMin;
}const_iterator end()const
{return nullptr;
}