html基本知识_域名批量查询_百度搜索数据_公众号排名优化

C++第十七讲：map和set封装

1.源码发现不同
2.Mymap && Myset
- 2.1红黑树的源码更改
- 2.2迭代器的实现
- - 2.2.1源码的迭代器区别
  - 2.2.2const iterator的实现
- 2.3insert的实现
- 2.4operator[]的理解

这一讲比较困难，我们首先会通过看map和set底层的源码，发现出和我们上一讲写的红黑树的不同，再深入地明白为什么底层是这样设计的，建议自己能够明白insert和迭代器的实现，理解operator[]的实现

1.源码发现不同

//stl_rbtree.h
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>// stl_set.h
template <class Key, class Compare = less<Key>, class Alloc = alloc>// stl_map.h
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>

我们观看源码会得到疑问：set只需要一个key就行了，map需要key和value，set和map底层封装的是红黑树，那么为什么红黑树的模板参数既有key，又有value？
因为map和set底层都是红黑树，所以为了进行统一，就将红黑树的模板参数设置成了key和value，set的value其实就是key（typedef），而map的value就是pair，那么设置两个key有什么用呢？因为对于find函数来说，不管是map还是set，都需要通过key来进行查找索引，而参数只有一个，所以需要两个key
在这里插入图片描述

2.Mymap && Myset

我们先明确map和set的封装结构：

namespace YWL
{template<class K, class V>class map{private:RBTree<K, pair<K, V>> _rbtree;};
}namespace YWL
{template<class K>class set{private:RBTree<K, K> _rbtree;};
}

2.1红黑树的源码更改

在这里插入图片描述

2.2迭代器的实现

我们先实现迭代器，迭代器实现需要begin，end，解引用*，->以及++、–的oeprator

迭代器的实现的难点在于迭代器的++和–操作，迭代器的指向更新问题，这里我们只演示++，–自己写：
在这里插入图片描述

Self& operator++()
{if (_node->_right){Node* minleft = _node->_right;while (minleft->_left) minleft = minleft->_left;_ndoe = minleft;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}

有了++的方法思路，那么–的方法思路就翻过来进行思考即可，而end()指向的是nullptr，所以对于空情况要做特殊处理，当为end–时，直接指向中序最后一个结点即可，这里我们给出代码，不给思路：

Self& operator--()
{if (_node == nullptr) // end(){// --end()，特殊处理，走到中序最后一个结点，整棵树的最右结点Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if (_node->_left){// 左子树不为空，中序左子树最后一个Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{// 孩子是父亲右的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}

2.2.1源码的迭代器区别

stl源码实现的迭代器中，增加了一个哨兵位，该结点的左指向中序遍历第一个值，右指向中序遍历最后一个值，该结点充当end()，当end–时，其实时该节点的右节点，begin其实就是该节点的左节点，其它并没有什么差别：
在这里插入图片描述

2.2.2const iterator的实现

set的iterator不⽀持修改，我们把set的第⼆个模板参数改成const K即可， RBTree<K, const K, SetKeyOfT> _t;

map的iterator不⽀持修改key但是可以修改value，我们把map的第⼆个模板参数pair的第⼀个参数改成const K即可， RBTree<K, pair<const K, V>, MapKeyOfT> _t;
在这里插入图片描述
下面错误更正：const K&作为返回值，因为返回值是const类型

2.3insert的实现

1.因为二叉搜索树的插入需要进行数据的比较，而对于pair来说，并不能够明确知道是比较key还是比较value，所以我们要写一个MapKeyoft和SetKeyoft用来获取Map和Set中用来对比的key值
2.Map和Set的封装插入，stl中设置的返回值是一个pair类型，即返回了插入位置的迭代器，又返回了插入是否成功，所以说更加优秀

//1.注意点1：返回值的不同
pair<iterator, bool> Insert(const T& data)
{if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//2.返回值的不同return make_pair(Iterator(_root, _root), true);}Node* parent = nullptr;Node* cur = _root;//3.通过KeyOFT来进行比较插入KeyOfT kot;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, _root), false);}}cur = new Node(data);Node* newnode = cur;cur->_col = RED;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;// uncle存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else  // uncle不存在，或者存在且为黑{if (cur == parent->_left){// 旋转+变色//    g//  p   u//cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;// 叔叔存在且为红，-》变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且为黑{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//    g//  u   p// cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(Iterator(newnode, _root), false);
}

2.4operator[]的理解

因为只有map有operator[]，传入的值是key，使用时是dict[“insert”] = “”;，所以说需要返回的是value的引用，方便修改value的内容：

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