建设银行园湖路支行网站,外贸网站建设需要注意什么,安装wordpress出现乱码,dw编辑器文章目录 一.map/set 的封装思路1.封装思路2.红黑树节点调整3.map 和 set 的定义4.仿函数 KeyOfValue5.map/set 的插入 二.map/set 迭代器实现1.迭代器的定义2.解引用运算符重载3.成员访问运算符重载4.(不)等于运算符重载5.begin() 与 end()6. 运算符重载7.-- 运算符重载8.[ ]下… 文章目录 一.map/set 的封装思路1.封装思路2.红黑树节点调整3.map 和 set 的定义4.仿函数 KeyOfValue5.map/set 的插入 二.map/set 迭代器实现1.迭代器的定义2.解引用运算符重载3.成员访问运算符重载4.(不)等于运算符重载5.begin() 与 end()6. 运算符重载7.-- 运算符重载8.[ ]下标访问运算符重载 三.源码1.RBTree2.map.h3.set.h 预备知识
一.map/set 的封装思路
在实现了红黑树的部分功能后我们可以便可以将红黑树作为底层结构来封装map 和set其中map是 K-Value 模型 而 set 是 Key 模型。
我们接下来将使用模板、仿函数和一棵红黑树实现 map和set。
1.封装思路
因为 map 存储的是pair 而 set 存储的是 Key 所以其解决的根本方向就是 如果是 map红黑树中就按照 pair 的 K进行比较从而插入 如果是 set红黑树中就按照 Key 值进行比较从而插入。
让 map / set 主动传出待比较的数据红黑树只用根据数据间关系进行插入即可不用在乎待比较的数据是何种结构。
2.红黑树节点调整
上文我们实现的红黑树是按照键值对的方式进行存储的而接下来我们要同时封装 map/set故不能直接定死存储的结构所以我们在此进行修改。 将原来的kv 模型改为data模型data 即是比较的数据内容。 注意将 Kv模型改为 data后插入与查找中比较的代码都要进行更新稍后会讲解。
3.map 和 set 的定义
map 和 set 底层都使用的红黑树所以我们 map/set 的功能就是调用红黑树的成员函数即可。
templateclass K, class V
class Map
{
private:RBTreeK, pairK, V _t;
};templateclass K
class Set
{
private:RBTreeK,K _t;
};因为Map有两个模板参数而 Set 只有一个模板参数。所以当我们使用的一个红黑树实现时要进行匹配处理。即使 Set 是一个模板参数在调用红黑树时也要传入两个模板参数。因为第一个模板参数是匹配 Map 满足红黑树的两个模板参数而第二个模板参数是为了让底层红黑树拿到比较的数据。
为什么Map除了传入pair外第一个参数直接传入 K为什么不能省略
因为Find的存在map中Find函数是直接按pair中的 K 进行查找的所以要额外设置该参数。
4.仿函数 KeyOfValue
接下来我们就要将数据取出供红黑树比较了如果是 map就按pair中的 K去比较如果是 set就按Key比较。
为此我们可以在 map 和 set 内部定义一个仿函数将其数据取出。
templateclass K, class V
class Map
{//Map-keyofvalue 仿函数struct MapKeyOfvalue{const K operator()(const std::pairK, V kv){return kv.first;}};
private:RBTreeK, pairK, V _t;
};templateclass K
class Set
{//Set-keyofvalue 仿函数struct SetKeyOfvalue{const K operator()(const K key){return key;}};
private:RBTreeK,K _t;
};然后我们将其仿函数也作为模板传入红黑树中对应的红黑树要添加一个模板参数来接收该仿函数。
改动代码如下 改动这些之后我们便要将红黑树中比较数据大小的地方进行修改
用仿函数将数据取出然后进行比较
//根据模板参数创建仿函数
KeyOfvalue kovalue;
if (!_root)
{_root new Node(data);_root-_col BLACK;return true;
}
Node* parent nullptr;
Node* cur _root;
while (cur)
{//比较处————进行改动if (kovalue(cur-_data) kovalue(data)){parent cur;cur cur-_left;}//比较处————进行改动else if (kovalue(cur-_data) kovalue(data)){parent cur;cur cur-_right;}else{return false;}
}
//创建新节点使用data进行构造
cur new Node(data);
//比较处————进行改动
if (kovalue(parent-_data) kovalue(data))
{parent-_left cur;
}
else
{parent-_right cur;
}
cur-_parent parent;这样红黑树便可以适配 map/set 的插入了。
5.map/set 的插入
接下来map/set 的插入直接套用红黑树的即可。
代码如下
//map的插入插入pair
bool insert(const pairK, V kv)
{return _t.Insert(kv);
}//set的插入插入key
bool insert(const K key)
{return _t.Insert(key);
}二.map/set 迭代器实现
1.迭代器的定义
// 节点数据 引用/const引用 指针/const指针
template class T,class Ref,class Ptr
struct __RBTreeIterator
{typedef RBTreeNodeT Node;typedef __RBTreeIteratorT, Ref, Ptr self;Node* _node;
public:__RBTreeIterator(Node* node):_node(node){}
}首先我们要明确其实 map/set 只是一层套壳其中的功能都是由红黑树实现后再封装到map/set中供我们使用迭代器也不例外。
2.解引用运算符重载
解引用即返回该节点的存储的数据主要用于 set 中返回该数据的引用。
Ref operator*()
{return _node-_data;
}3.成员访问运算符重载
成员访问操作符即返回该节点的地址主要用于 map 中方便访问 pair 中的first以及second。
Ptr operator-()
{return (_node-_data);
}4.(不)等于运算符重载
bool operator(const self s)
{return _node s._node;
}bool operator!(const self s)
{return _node ! s._node;
}5.begin() 与 end()
迭代器常用成员函数begin()与end()其中begin()对应红黑树的最左节点end()对应最后一个节点的下一个节点即nullptr(为了简化并未设置哨兵节点实现将其完美实现)
iterator begin()
{Node* left _root;while (left left-_left){left left-_left;}return iterator(left);
}iterator end()
{return iterator(nullptr);
}如果 map/set 中想使用红黑树中的迭代器我们需要在 map/set 中进行声明。
声明如下
如果想取一个类模板中的一个类型要使用 typedname 进行声明。 告诉编译器这是一个类型并不是一个静态变量
//如果想取一个类模板中的一个类型要使用 typedname 进行声明。
//告诉编译器这是一个类型并不是一个静态变量
typedef typename RBTreeK, pairK, V, MapKeyOfvalue::iterator iterator;6. 运算符重载
首先我们需要明确迭代器是让当前迭代器指向红黑树中序遍历的下一个节点。 以下图的35节点为例。 当迭代器指向 35 时进行 指向右子树最左节点即 40。当迭代器指向 40 时进行 右子树为空指向父节点即 45。当迭代器指向 45 时进行 指向右子树最左节点即 48。当迭代器指向 48 时进行 指向未遍历的父节点即 50。 分析上面的情况发现迭代器 始终围绕着右子树是否存在进行。
现在我们将其抽象化分析其规律
右子树不为空进行 则是指向右子树中序的第一个(最左节点)。右子树为空 找孩子不是父亲右节点的祖先。
self operator()
{//如果右子树存在if (_node-_right){Node* left _node-_right;//则寻找右子树的最左节点while (left-_left){left left-_left;}_node left;}//如果右子树不存在else{//找孩子不是父亲右节点的节点Node* parent _node-_parent;Node* cur _node;while (cur parent-_right){cur cur-_parent;parent parent-_parent;//防止最后一个节点寻找祖先导致程序崩溃if (parent nullptr){break;}}_node parent;}return *this;
}需要注意当 到最后一个节点的时候。有可能在寻找非父亲右节点的祖先时父节点一路走到 nullptr 的情况如图 所以在每次 parent 更新时都进行一次判断即可。
7.-- 运算符重载
有了前面的模拟实现实现 --就是反着遍历即可。
左子树不为空进行 -- 则是指向左子树中序的最后一个(最右节点)。左子树为空-- 找孩子不是父亲左节点的祖先。
self operator--()
{//如果左子树存在if (_node-left){//找左子树的最右节点Node* right _node-_left;while (right-_right){right right-_right;}_node rihgt;}//如果左子树不存在else{//找孩子不是父亲左节点的节点Node* parent _node-parent;Node* cur _node;while (parent-_left cur){cur cur-_parent;parent parent-_parent;if (parent nullptr){break;}}_node parent;}return *this;
}8.[ ]下标访问运算符重载
我们来看 map 的[]下标访问操作符其中 []返回的是mapped_type(pair) 类型。 再看 set 中的insert也是返回 pair虽然很反常但是官方库中确实是这样书写的。 因为 set 没有[]运算符重载所以 set 中不必提供该函数只用在 map 中提供即可。
首先我们向 map 中 insert 数据 pairpair的第一个参数为用户传入的 key 值第二个参数则是用户声明的第二个模板参数的默认构造函数(如果是 int则调用 int的构造函数如果是string则默认构造 string)。
pairiterator, bool result insert(make_pair(key, V()));然后我们返回迭代器指向的 pair 数据中的second。
//result.first取出迭代器使用-运算符重载取出data地址访问second并返回
return result.first-second;V operator[](const K key)
{pairiterator, bool result insert(make_pair(key, V()));//如果存在则插入失败//如果不存在则插入数据//无论是否存在,都返回 second;return result.first-second;
}三.源码
1.RBTree
enum Colour
{RED,BLACK,
};templateclass T
struct RBTreeNode
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Colour _col;RBTreeNode(const T data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};templateclass T, class Ref, class Ptr
struct __RBTreeIterator
{typedef RBTreeNodeT Node;typedef __RBTreeIteratorT, Ref, Ptr Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}// 1、typedef __RBTreeIteratorT, T, T* itertaor; 拷贝构造// 2、 typedef __RBTreeIteratorT, const T, const T* const_itertaor;// 支持普通迭代器构造const迭代器的构造函数__RBTreeIterator(const __RBTreeIteratorT, T, T* it):_node(it._node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}Self operator(){if (_node-_right){// 1、右不为空下一个就是右子树的最左节点Node* subLeft _node-_right;while (subLeft-_left){subLeft subLeft-_left;}_node subLeft;}else{// 2、右为空沿着到根的路径找孩子是父亲左的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur parent;parent parent-_parent;}_node parent;}return *this;}Self operator--(){if (_node-_left){// 1、左不为空找左子树最右节点Node* subRight _node-_left;while (subRight-_right){subRight subRight-_right;}_node subRight;}else{// 2、左为空孩子是父亲的右的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_left){cur parent;parent parent-_parent;}_node parent;}return *this;}
};// 仿函数
templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:~RBTree(){_Destroy(_root);_root nullptr;}
public:typedef __RBTreeIteratorT, T, T* itertaor;typedef __RBTreeIteratorT, const T, const T* const_itertaor;itertaor begin(){Node* cur _root;while (cur cur-_left){cur cur-_left;}return itertaor(cur);}itertaor end(){return itertaor(nullptr);}const_itertaor begin() const{Node* cur _root;while (cur cur-_left){cur cur-_left;}return const_itertaor(cur);}const_itertaor end() const{return const_itertaor(nullptr);}Node* Find(const K key){Node* cur _root;KeyOfT kot;while (cur){if (kot(cur-_data) key){cur cur-_right;}else if (kot(cur-_data) key){cur cur-_left;}else{return cur;}}return nullptr;}pairitertaor, bool Insert(const T data){if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(itertaor(_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(itertaor(cur), false);}}cur new Node(data);Node* newnode cur;if (kot(parent-_data) kot(data)){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;if (grandfather-_left parent){Node* uncle grandfather-_right;// 情况1u存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续往上调整cur grandfather;parent cur-_parent;}else // 情况23u不存在/u存在且为黑旋转变色{// g// p u// c if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;//parent-_col RED;grandfather-_col RED;}break;}}else // (grandfather-_right parent){// g// u p// cNode* uncle grandfather-_left;// 情况1u存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续往上调整cur grandfather;parent cur-_parent;}else // 情况23u不存在/u存在且为黑旋转变色{// g// u p// cif (cur parent-_right){RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return make_pair(itertaor(newnode), true);;}bool IsBalance(){if (_root _root-_col RED){cout 根节点颜色是红色 endl;return false;}int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}// 连续红色节点return _Check(_root, 0, benchmark);}int Height(){return _Height(_root);}private:void _Destroy(Node* root){if (root nullptr){return;}_Destroy(root-_left);_Destroy(root-_right);delete root;}int _Height(Node* root){if (root NULL)return 0;int leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;}bool _Check(Node* root, int blackNum, int benchmark){if (root nullptr){if (benchmark ! blackNum){cout 某条路径黑色节点的数量不相等 endl;return false;}return true;}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return _Check(root-_left, blackNum, benchmark) _Check(root-_right, blackNum, benchmark);}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppnode parent-_parent;subR-_left parent;parent-_parent subR;if (ppnode nullptr){_root subR;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* ppnode parent-_parent;subL-_right parent;parent-_parent subL;if (parent _root){_root subL;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}}private:Node* _root nullptr;
};2.map.h
templateclass K, class V
class map
{struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};
public:typedef typename RBTreeK, pairconst K, V, MapKeyOfT::itertaor iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}V operator[](const K key){pairiterator, bool ret _t.Insert(make_pair(key, V()));return ret.first-second;}pairiterator, bool insert(const pairconst K, V kv){return _t.Insert(kv);}
private:RBTreeK, pairconst K, V, MapKeyOfT _t;
};void test_map1()
{mapstring, string dict;dict.insert(make_pair(sort, ));dict.insert(make_pair(string, ַ));dict.insert(make_pair(count, ));dict.insert(make_pair(string, (ַ))); // ʧmapstring, string::iterator it dict.begin();while (it ! dict.end()){cout it-first : it-second endl;/*it-first 1111;it-second 111;*/it;}cout endl;for (auto kv : dict){cout kv.first : kv.second endl;}cout endl;
};3.set.h
templateclass K
class set
{struct SetKeyOfT{const K operator()(const K key){return key;}};
public:typedef typename RBTreeK, K, SetKeyOfT::const_itertaor iterator;typedef typename RBTreeK, K, SetKeyOfT::const_itertaor const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pairiterator, bool insert(const K key){return _t.Insert(key);}
private:RBTreeK, K, SetKeyOfT _t;
};
