网站做360推广需要什么条件,领英怎么注册公司主页,单位门户网站,中国电信企业邮箱21cn目录
一、改造红黑树
1、模板T改造节点
2、提取节点中的key
3、迭代器类
operator
operator--
4、改造insert
5、红黑树迭代器
6、 普通迭代器构造const迭代器
二、set
三、map 在stl中map和set的结构中#xff0c;他们都使用一个红黑树进行封装。 由上图可知
operator--
4、改造insert
5、红黑树迭代器
6、 普通迭代器构造const迭代器
二、set
三、map 在stl中map和set的结构中他们都使用一个红黑树进行封装。 由上图可知set传给红黑树节点的两个模板参数都是key而map传给的红黑树的第一个模板参数是key、第二个参数是pair因此我们首先对上一篇文章中的红黑树进行改造。
一、改造红黑树
#pragma onceenum 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;
};1、模板T改造节点
我们需要将节点结构体RBTreeNode中的数据成员_data的类型改为模板参数T。这样每个节点就可以存储不同类型的数据以适应map的节点存储pair结构set的节点存储key。
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){}
};
2、提取节点中的key
在上述代码中我们可以看到RBTree类的定义如下
templateclass K, class T, class KeyOfT
class RBTree
{// ...
};
其中K是键的类型T是值的类型KeyOfT是一个辅助类也叫作仿函数用于从值中提取键。在set中键和值的类型相同因此KeyOfT可以直接使用K。而在map中键和值的类型不同因此我们需要对KeyOfT进行修改。
对于map类我们需要将KeyOfT修改为适应pairconst K, V类型的辅助类。我们可以定义一个新的辅助类仿函数MapKeyOfT其内部使用重载了函数调用运算符 operator()这个辅助类的作用是从pairconst K, V类型的值中提取出键K。同时我们将RBTree的第三个模板参数修改为MapKeyOfT。
templateclass K, class V
class map
{struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};
private:RBTreeK, pairconst K, V, MapKeyOfT _t;
};
对于set类我们需要将KeyOfT修改为配合map使用的辅助类。我们可以定义一个仿函数SetKeyOfT 通过重载operator()直接返回key。同时我们将第三个模板参数修改为’SetKeyOfT。
templateclass K
class set
{struct SetKeyOfT{const K operator()(const K key){return key;}};
private:RBTreeK, K, SetKeyOfT _t;
};
3、迭代器类
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(){}Self operator--(){}
}; 这段代码定义了一个模板类__RBTreeIterator它有三个模板参数T、Ref和Ptr。
T表示节点中存储的数据类型。Ref表示解引用操作符*返回的引用类型。Ptr表示箭头操作符-返回的指针类型。
这个迭代器类用于遍历红黑树并提供了对节点数据的访问功能。
在这个迭代器类中有一个成员变量Node* _node它指向红黑树中的一个节点。
构造函数__RBTreeIterator(Node* node)用于初始化迭代器对象将_node指针指向传入的节点。拷贝构造函数__RBTreeIterator(const __RBTreeIteratorT, T, T* it)用于从普通迭代器构造const迭代器。它将传入迭代器的_node指针赋值给当前迭代器的_node成员变量。重载解引用操作符*使得可以通过迭代器访问节点的数据。它返回的是Ref类型的引用可以直接修改节点的数据。重载箭头操作符-使得可以通过迭代器访问节点的数据。它返回的是Ptr类型的指针可以通过指针访问节点的数据成员。重载不等于操作符!用于比较两个迭代器是否不相等。它比较两个迭代器的_node指针是否相等。重载前缀递增操作符使得可以将迭代器指向下一个节点。如果当前节点有右子节点则下一个节点是右子树的最左节点否则沿着到根的路径找到第一个孩子是父节点左孩子的祖先节点。重载前缀递减操作符--使得可以将迭代器指向上一个节点。如果当前节点有左子节点则上一个节点是左子树的最右节点否则沿着到根的路径找到第一个孩子是父节点右孩子的祖先节点。
operator 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;}
首先函数检查当前节点的右子节点是否存在。如果存在说明存在右子树下一个节点就是右子树中的最左节点。因此函数将迭代器指向右子树中的最左节点并结束函数的执行。
如果当前节点的右子节点为空说明不存在右子树。在这种情况下函数需要沿着到根的路径向上查找直到找到一个节点该节点是其父节点的左子节点。这是因为在红黑树中右子树为空的节点的下一个节点是其父节点。
函数使用两个指针变量 cur 和 parent 来进行查找。
开始时将 cur 初始化为当前节点将 parent 初始化为 cur 的父节点。然后函数进入一个循环只要 parent 存在且 cur 是 parent 的右子节点就继续向上查找。在循环中将 cur 更新为 parent将 parent 更新为 cur 的父节点。这样函数就可以找到下一个节点并将迭代器指向该节点。
最后函数返回迭代器自身的引用以支持链式操作。
operator-- 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;} 首先函数检查当前节点的左子节点是否存在。如果存在说明存在左子树前一个节点就是左子树中的最右节点。因此函数将迭代器指向左子树中的最右节点并结束函数的执行。
如果当前节点的左子节点为空说明不存在左子树。在这种情况下函数需要沿着到根的路径向上查找直到找到一个节点该节点是其父节点的右子节点。这是因为在红黑树中左子树为空的节点的前一个节点是其父节点。
函数使用两个指针变量 cur 和 parent 来进行查找。
开始时将 cur 初始化为当前节点将 parent 初始化为 cur 的父节点。然后函数进入一个循环只要 parent 存在且 cur 是 parent 的左子节点就继续向上查找。在循环中将 cur 更新为 parent将 parent 更新为 cur 的父节点。这样函数就可以找到前一个节点并将迭代器指向该节点。
最后函数返回迭代器自身的引用以支持链式操作。
4、改造insert
1. 修改函数的参数类型为 const T data以接受要插入的数据。
返回类型 pairiterator, bool 是为了提供更多的信息给调用者以便在插入操作后进行进一步的处理。
pairiterator, bool Insert(const T data) iterator表示插入节点的迭代器。通过返回迭代器调用者可以方便地访问插入的节点进行后续的操作如修改节点的值、删除节点等。 bool表示插入是否成功的标志。通过返回布尔值调用者可以知道插入操作是否成功。如果插入成功布尔值为 true如果插入失败节点已存在布尔值为 false。 2. 将 pairK, V 替换为 T因为现在的节点类型是 RBTreeNodeT。
cur new Node(data);
3. 在函数内部将 _kv 替换为 _data以匹配节点的数据成员名称。
if (cur-_data data){// ...
}
else if (cur-_data data){// ...
}
else{//查找失败return make_pair(iterator(cur), false);
}
4. 新增的 KeyOfT kot; 是为了创建 KeyOfT 类型的对象 kot用于从节点数据类型 T 中提取键值。
KeyOfT kot;
while (cur)
{if (kot(cur-_data) kot(data)){//..}else if (kot(cur-_data) kot(data)){//..}else{//..}
}
5. 在修改后的 Insert 函数中新增的 Node* newnode cur; 是为了在返回 pairiterator, bool 时将插入的节点的迭代器保存下来。
Node* newnode cur;
在原始的代码中返回的迭代器是通过 iterator(cur) 创建的其中 cur 是指向新插入节点的指针。然而在后续的操作中cur 的值可能会发生变化因为在红黑树的调整过程中节点的位置可能会发生改变。为了确保返回的迭代器指向插入的节点我们将 cur 的值保存在 newnode 中。这样在返回 pairiterator, bool 时我们使用 iterator(newnode) 创建迭代器确保迭代器指向插入的节点。因此Node* newnode cur; 的目的是为了保存插入节点的指针以便在返回迭代器时使用。这样可以确保返回的迭代器指向正确的节点而不受后续操作的影响。
6. 在函数的返回语句中使用 make_pair 创建一个 pair 对象其中包含插入的迭代器和插入是否成功的标志。
return make_pair(iterator(newnode), true);
5、红黑树迭代器
templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
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);}
首先我们定义了两个迭代器类型 iterator 和 const_iterator分别对应可修改和只读的迭代器。这些迭代器是通过 __RBTreeIterator 结构体模板实例化得到的。然后我们定义了 begin() 和 end() 函数分别用于返回红黑树的起始迭代器和结束迭代器。在 begin() 函数中我们从根节点开始沿着左子节点的路径向下遍历直到找到最左边的节点。这个节点就是红黑树中最小的节点也是起始节点。我们将其作为参数传递给 __RBTreeIterator 构造函数创建一个迭代器对象并将其返回。在 end() 函数中我们直接返回一个迭代器对象其指针成员 _node 设置为 nullptr表示结束位置。对于 const 重载的版本逻辑与非 const 版本相同只是返回的是 const_iterator 类型的迭代器对象。
6、 普通迭代器构造const迭代器
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){}
}
const __RBTreeIteratorT, T, T* it 部分没有显式的强制类型转换。它是一个常量引用用于接收普通迭代器对象的引用作为参数如果需要将普通迭代器对象转换为const迭代器对象编译器会自动进行隐式类型转换。因为参数加上了const修饰符这意味着它是一个常量引用。当使用普通迭代器对象调用构造函数时编译器会进行隐式类型转换将普通迭代器对象转换为const迭代器对象。
二、set
#pragma once#include RBTree.hnamespace MySet
{templateclass Kclass 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;};
}
在命名空间MySet中定义了一个内部结构体SetKeyOfT它是一个仿函数用于从键中提取键值。在这个仿函数中重载了函数调用操作符operator()接受一个键key作为参数并返回该键本身。接下来是set类的定义。它使用了模板参数K表示集合中元素的类型。在set类中使用了RBTree类来实现红黑树的功能。RBTree的模板参数为K、K和SetKeyOfT表示键的类型、值的类型和键提取仿函数的类型。set类中定义了两个迭代器类型iterator和const_iterator它们分别是RBTreeK, K, SetKeyOfT::const_iterator的别名。这两个迭代器类型用于遍历集合中的元素。set类还提供了begin和end方法用于返回集合的起始迭代器和结束迭代器。begin方法返回的是红黑树的起始迭代器而end方法返回的是红黑树的结束迭代器。此外set类还提供了insert方法用于向集合中插入元素。它接受一个键key作为参数并返回一个pair对象其中包含一个迭代器和一个布尔值。迭代器指向插入的元素布尔值表示插入是否成功。最后set类中有一个私有成员变量_t它是一个RBTreeK, K, SetKeyOfT类型的对象用于存储集合的元素。
三、map
#pragma once#include RBTree.hnamespace MyMap
{templateclass K, class Vclass 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;};
命名空间MyMap中定义了一个内部结构体MapKeyOfT它是一个仿函数用于从键值对中提取键。在这个仿函数中重载了函数调用操作符operator()接受一个键值对kv作为参数并返回该键值对中的键first。接下来是map类的定义。它使用了两个模板参数K和V分别表示键和值的类型。在map类中使用了RBTree类来实现红黑树的功能。RBTree的模板参数为K、pairconst K, V和MapKeyOfT表示键的类型、键值对的类型和键提取仿函数的类型。map类中定义了一个迭代器类型iterator它是RBTreeK, pairconst K, V, MapKeyOfT::iterator的别名。这个迭代器类型用于遍历映射中的键值对。map类提供了begin和end方法用于返回映射的起始迭代器和结束迭代器。begin方法返回的是红黑树的起始迭代器而end方法返回的是红黑树的结束迭代器。此外map类还重载了下标操作符[]使得可以通过键访问对应的值。它接受一个键key作为参数并返回对应的值的引用。如果键不存在于映射中则会自动插入一个新的键值对并返回对应值的引用。map类还提供了insert方法用于向映射中插入键值对。它接受一个键值对kv作为参数并返回一个pair对象其中包含一个迭代器和一个布尔值。迭代器指向插入的键值对布尔值表示插入是否成功。最后map类中有一个私有成员变量_t它是一个RBTreeK, pairconst K, V, MapKeyOfT类型的对象用于存储映射的键值对。
