【C++练级之路】【Lv.17】【STL】set类和map类的模拟实现

快乐的流畅 2024-06-17 14:05:03 阅读 81

快乐的流畅:个人主页

个人专栏:《C语言》《数据结构世界》《进击的C++》

远方有一堆篝火,在为久候之人燃烧!

文章目录

引言一、红黑树(改造版)1.1 结点1.2 迭代器1.2.1 operator++1.2.2 operator- - 1.3 本体1.3.1 成员变量1.3.2 begin和end1.3.3 Find1.3.4 Insert 二、set2.1 成员变量与仿函数2.2 begin和end2.3 find2.4 insert 三、map3.1 成员变量与仿函数3.2 begin和end3.3 find3.4 insert3.5 operator[ ]

引言

STL库中的set类和map类,其底层原理都是通过红黑树来实现的。尽管set和map可以各自实现一棵红黑树,但是为了提高代码的复用率,STL库中将红黑树进行了一定的改造,实现以相同的底层实现不同的容器

一、红黑树(改造版)

1.1 结点

enum Color{ RED,BLACK};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){ }};

细节:

数据类型改为T,因为要同时适用set(存储键值)和map(存储键值对)

1.2 迭代

改造后的红黑树,最重要的功能之一就是支持双向迭代器,以最左结点为首,以最右结点为尾。

template<class T, class Ref, class Ptr>struct RBTreeIterator{ typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;RBTreeIterator(Node* node): _node(node){ }RBTreeIterator(const Iterator& it): _node(it._node){ }Ref operator*(){ return _node->_data;}Ptr operator->(){ return &(operator*());}bool operator!=(const Self& s){ return _node != s._node;}bool operator==(const Self& s){ return _node == s._node;}};

细节:

一些基本的迭代器范式操作已经给出,重点的++与- -操作后面详细实现迭代器的拷贝构造函数有两个用途: 以普通迭代器拷贝出普通迭代器(普通迭代器调用时)以普通迭代器拷贝出const迭代器(const迭代器调用时)

1.2.1 operator++

Self& operator++(){ if (_node->_right)//右不为空,找右子树的最左结点{ Node* subLeft = _node->_right;while (subLeft->_left){ subLeft = subLeft->_left;}_node = subLeft;}else//右为空,向上找孩子是父亲左的那个父亲{ Node* parent = _node->_parent;Node* cur = _node;while (parent && parent->_right == cur){ cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self operator++(int){ Self tmp = *this;++*this;return tmp;}

细节:

前置++的思路: 右不为空,找右子树的最左结点右为空,向上找孩子是父亲左的那个父亲 后置++:复用前置++,返回临时对象

1.2.2 operator- -

Self& operator--(){ if (_node->_left)//左不为空,找左子树的最右结点{ Node* subRight = _node->_left;while (subRight->_right){ subRight = subRight->_right;}_node = subRight;}else//左为空,向上找孩子是父亲右的那个父亲{ Node* parent = _node->_parent;Node* cur = _node;while (parent && parent->_left == cur){ cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self operator--(int){ Self tmp = *this;--*this;return tmp;}

细节:

前置- -的思路: 左不为空,找左子树的最右结点左为空,向上找孩子是父亲右的那个父亲 后置- -:复用前置- -,返回临时对象

1.3 本体

1.3.1 成员变量

template<class K, class T, class KeyOfT>class RBTree{ protected:typedef RBTreeNode<T> Node;public:protected:Node* _root = nullptr;};

细节:

模板参数第一个为K,键值类型(比较时会用到)模板参数第二个为T,同时适用set(存储键值)和map(存储键值对)模板参数第三个为KeyOfT(仿函数类型),用于获取不同数据T的键值key来进行比较

1.3.2 begin和end

typedef RBTreeIterator<T, T&, T*> iterator;typedef RBTreeIterator<T, const T&, const T*> const_iterator;iterator begin(){ Node* cur = _root;while (cur->_left){ cur = cur->_left;}return iterator(cur);}const_iterator begin() const{ Node* cur = _root;while (cur->_left){ cur = cur->_left;}return const_iterator(cur);}iterator end(){ return iterator(nullptr);}const_iterator end() const{ return const_iterator(nullptr);}

细节:begin返回最左节点的迭代器,end返回空迭代器

1.3.3 Find

iterator Find(const K& key){ if (_root == nullptr){ return iterator(nullptr);}KeyOfT kot;Node* cur = _root;while (cur){ if (kot(cur->_data) < key){ cur = cur->_right;}else if (kot(cur->_data) > key){ cur = cur->_left;}else{ return iterator(cur);}}return iterator(nullptr);}

细节:

返回迭代器运用仿函数进行键值比较

1.3.4 Insert

pair<iterator, bool> Insert(const T& data){ if (_root == nullptr){ _root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}KeyOfT kot;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(iterator(cur), false);}}Node* newnode = new Node(data);cur = newnode;if (kot(parent->_data) < kot(data)){ parent->_right = cur;}else{ parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){ Node* grandparent = parent->_parent;if (grandparent->_right == parent)//uncle在左,parent在右{ Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED)//uncle为红,变色+向上调整{ parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else//uncle为空或为黑,变色+旋转{ if (parent->_right == cur)//左单旋{ RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else//右左旋{ RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}}}else//parent在左,uncle在右{ Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{ if (parent->_left == cur)//右单旋{ RotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else//左右旋{ RotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}

细节:

返回pair,第一个参数为迭代器,第二个参数为布尔值(记录是否插入成功)运用仿函数进行键值比较

二、set

2.1 成员变量与仿函数

template<class K>class set{ struct SetKeyOfT{ const K& operator()(const K& key){ return key;}};public:protected:RBTree<K, K, SetKeyOfT> _t;};

细节:

set类仿函数,直接返回参数key成员变量的第二个模板参数为K,第三个模板参数为SetKeyOfT

2.2 begin和end

typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin(){ return _t.begin();}const_iterator begin() const{ return _t.begin();}iterator end(){ return _t.end();}const_iterator end() const{ return _t.end();}

细节:

加上typename关键字,编译器才能识别类型set中存储的键值key均不允许修改,所以其普通迭代器和const迭代器均为红黑树的const迭代器由于set的普通迭代器也是红黑树的const迭代器,调用普通begin()时,便有从普通迭代器到const迭代器的转换,此时之前写的拷贝构造(以普通迭代器拷贝构造const迭代器)便派上用场了。

2.3 find

iterator find(const K& key){ return _t.Find(key);}

2.4 insert

pair<iterator, bool> insert(const K& key){ return _t.Insert(key);}

细节:

插入参数类型为K(键值)此时也有从普通迭代器到const迭代器的转换

三、map

3.1 成员变量与仿函数

template<class K, class V>class map{ struct MapKeyOfT{ const K& operator()(const pair<const K, V>& kv){ return kv.first;}};public:protected:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};

细节:

map类仿函数,返回参数pair的first成员变量的第二个模板参数为pair,第三个模板参数为MapKeyOfT

3.2 begin和end

typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;iterator begin(){ return _t.begin();}const_iterator begin() const{ return _t.begin();}iterator end(){ return _t.end();}const_iterator end() const{ return _t.end();}

细节:

加上typename关键字,编译器才能识别类型map同样不允许修改key,故加上const修饰,但是允许修改存储的value,所以普通和const迭代器一一对应


此时,可能有人会问,那刚刚set不允许修改key,为什么不也直接用const修饰呢?请看以下这段代码:

typedef RBTreeIterator<T, const T&, const T*> const_iterator;

如果变成第二个模板参数T传入const K,那么就会形成两个连续的const,这是不被允许的。所以才想了其他方法来补救。

3.3 find

iterator find(const K& key){ return _t.Find(key);}

3.4 insert

pair<iterator, bool> insert(const pair<const K, V>& kv){ return _t.Insert(kv);}

细节:插入参数类型为pair(键值对)

3.5 operator[ ]

map最好用的重载运算符[ ],我们肯定也要实现,平常插入和修改使用[ ]更加方便。

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

细节:

插入成功便是插入,插入失败便是查找+修改返回value的引用,可以直接插入或修改

真诚点赞,手有余香


声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。