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

四线城市做网站建设怎么样郑州网约车租赁公司

news 2025/9/18 9:36:07
四线城市做网站建设怎么样,郑州网约车租赁公司,高清短视频素材库无水印,有什么网站做图片宣传海报目录 一、框架思考 三个问题 问题1的解决 问题2的解决： 问题3的解决： 二、泛型编程 1、仿函数的泛型编程 2、迭代器的泛型编程 3、typename： 4、/--重载 三、原码 红黑树 map set 一、框架思考 map和set都是使用红黑树底层&…

目录

一、框架思考

三个问题

问题1的解决

问题2的解决：

问题3的解决：

二、泛型编程

1、仿函数的泛型编程

2、迭代器的泛型编程

3、typename：

4、++/--重载

三、原码

红黑树

map

set

一、框架思考

map和set都是使用红黑树底层，要怎么实现同一个底层，但是实现不同的功能呢？

三个问题


1、map是pair模型，而set是key模型

2、map和set的迭代器用法是一样的，如何实现？

3、插入时，set和map插入的类型不同，如何实现？

我们是一个简单的实现，而不是全部，所以抓重点，化繁为简
只关注和当前我么要实现功能有关系的部分，其他的统统不关注

问题1的解决


RBTree的节点传的是一个模板

template<class T>
struct BRTreeNode
{BRTreeNode<T>* _parent;BRTreeNode<T>* _right;BRTreeNode<T>* _left;T _data;Colour _col;BRTreeNode(const T& data):_parent(nullptr), _right(nullptr), _left(nullptr), _data(data), _col(RED){}};

map传<K,pair<K,V>>
set传<K,K>

我set要用的是key模型的BRTree，所以传的是<K，K>
我map要的是key-value模型的BRTree，所以传的是<K，pair<K,V>>
对应的BRTree传对应的模板到Node，实现不同类型的Node节点

问题2的解决：

map和set底层都是红黑树，其行为都是一致的，问题在于节点数据类型的不同，所以，红黑树的底层迭代器实现都是一样的，设置为模板，因此和问题1的解决思路是一致的。

问题3的解决：


set和map的比较不一样
set的比较是直接key，而map的比较是用kv.first
不确定是map还是set，不能写死，怎么办？
可以写一个内部类的仿函数
这个仿函数，对于set返回的是其key值
对于map返回的是其kv.first值
仿函数是一个强大的功能，你想怎么实现就怎么实现

模板写成一样的，功能是一样的，但是不同的对象类具体实现不同的功能

具体解决请看以下的泛型编程过程：

二、泛型编程

1、仿函数的泛型编程


set和map的key值不一样
如何使用同一份红黑树实现不同的比较逻辑？
当对红黑树实例化时，多传一个参数，即仿函数
在红黑树底层使用一个模板仿函数
在各自的map和set写好各自的类，用于模板仿函数的实例化
这样，虽然在底层，仿函数的行为都是一致的
但是，因为模板参数不同，其返回值也就不同

set的仿函数：

	struct  SetKeyOfT{const K& operator()(const K& key){return key;}};

map的仿函数：

		struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};

红黑树部分的仿函数

		KeyOfT kot;kot(data)


2、迭代器的泛型编程

set和map有各自的数据类型
但是器迭代器的形式是一样的
如何做到？
迭代器实现，实在红黑树部分实现的
将之设置为模板
传set，就是se对应的迭代器
传map，就是map对应的迭代器

set的迭代器：

	typedef typename BRTree<const K,  K, SetKeyOfT>::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}

map的迭代器：

	typedef typename BRTree<K, pair< K, V>, MapKeyOfT>::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return  _t.End();}

红黑树的迭代器：

//迭代器
//referrence :引用
template<class T, class Ptr, class Ref>//迭代器模板：数据类型、指针类型、解引用
struct __RBTreeiterator
{typedef BRTreeNode<T> Node;typedef __RBTreeiterator<T, Ptr, Ref> Self;//这个迭代器的对象Node* _node;__RBTreeiterator( Node* node):_node(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)//如果右孩子不为空，找到右子树最小孩子{Node* leftMin = _node->_right;while (leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else//右孩子为空{Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_right)//当孩子作为父亲的左，这个父亲就是要访问的节点{cur = parent;parent = parent->_parent;}_node = parent;}return *this;//this为这个对象指针}};

一般的迭代器的功能：
解引用*
指针访问->
比较相等
++
--

3、typename：

在没有实例化的对象，访问其内嵌类型 
会出现分不清楚的问题：
因为静态成员、内部类、内部成员的访问都可以使用类域的方式去访问
没有实例化，就不知道访问哪一个 

在没有实例化模板的类对象去取器内嵌类型时，加一个typename
意义就是告诉编译器，等到实例化的时候再去找对应的内嵌类型

4、++/--重载

红黑树采用的是中序遍历
中序遍历，++返回的是当前节点中序遍历的下一个节点
顺序是：左，根、右
因此，需要分情况
如果当前节点有右孩子，那就是右孩子的最左节点

如果当前节点没有右孩子，那么说明自己这棵子树已经访问完毕
需要访问该子树的父亲，因为该子树是作为父亲的左孩子
按照中序遍历的思想，左子树访问完毕，接下来要访问的就是根

红黑树

#pragma once
#pragma once
#include<vector>
#include<iostream>
using namespace std;enum Colour
{BLACK,RED
};//node实例化，只给一个T
template<class T>
struct BRTreeNode
{BRTreeNode<T>* _parent;BRTreeNode<T>* _right;BRTreeNode<T>* _left;T _data;Colour _col;BRTreeNode(const T& data):_parent(nullptr), _right(nullptr), _left(nullptr), _data(data), _col(RED){}};//迭代器
//referrence :引用
template<class T, class Ptr, class Ref>//迭代器模板：数据类型、指针类型、解引用
struct __RBTreeiterator
{typedef BRTreeNode<T> Node;typedef __RBTreeiterator<T, Ptr, Ref> Self;//这个迭代器的对象Node* _node;__RBTreeiterator( Node* node):_node(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)//如果右孩子不为空，找到右子树最小孩子{Node* leftMin = _node->_right;while (leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else//右孩子为空{Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_right)//当孩子作为父亲的左，这个父亲就是要访问的节点{cur = parent;parent = parent->_parent;}_node = parent;}return *this;//this为这个对象指针}};template<class K, class T, class KeyOfT>
class BRTree
{typedef BRTreeNode<T> Node;
public:typedef  __RBTreeiterator<T, T*, T&>Iterator;//提供迭代器接口Iterator Begin(){Node* leftMin = _root;while (leftMin && leftMin->_left)//如果为空，直接返回{leftMin = leftMin->_left;}//返回一个迭代器//return leftMin;单参数的构造函数支持隐式类型转换return Iterator(leftMin);}Iterator End(){//遍历，要访问到最大的值为止//一般end位置为空return Iterator(nullptr);}bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}KeyOfT kot;Node* cur = _root;Node* parent = nullptr;while (cur){//现在，不知道是k还是k-v模型//set访问的直接是key，而map访问的.first//所以，对应不同的返回值，仿函数解决if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else if (kot(data) > kot(cur->_data)){parent = cur;cur = cur->_right;}else//找到相等key{return false;}}cur = new Node(data);cur->_col = RED;if (kot(data) < kot(parent->_data))//插入左{parent->_left = cur;}else //插入右{parent->_right = cur;}cur->_parent = parent;//插入之后，要进行颜色调整while (parent && parent->_col == RED)//如果为空/黑色节点，直接结束{//Node* grandfather = parent->_parent;if (parent == grandfather->_left)//p为左，u为右{Node* uncle = grandfather->_right;//如果叔叔存在，且为红色if (uncle && uncle->_col == RED){//修改颜色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}else//叔叔不存在/叔叔存在且为黑色{if (cur == parent->_left){//		   g//	   p      u//  c//RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		   g//	   p      u//      c//RotateL(parent);//		   g//	   c      u//  p//RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else//p为右，u为左{Node* uncle = grandfather->_left;//如果叔叔存在，且为红色if (uncle && uncle->_col == RED){//修改颜色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}else//叔叔不存在/叔叔存在且为黑色{if (cur == parent->_right){//		   g//	   u      p//					c//RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		   g//	   u      p//          c//RotateR(parent);//		   g//	   u      c//  				p//RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}//右旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)//subLR可能为空{subLR->_parent = parent;}subL->_right = parent;Node* ppNode = parent->_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;}}//左旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}//检查平衡bool isBalance(){if (_root->_col == RED){return false;}//找到任意一条路黑色节点个数Node* cur = _root;int refNum = 0;while (cur){if (cur->_col == BLACK){refNum++;}cur = cur->_left;}return Check(_root, 0, refNum);return 1;}void Inoder(){_Inoder(_root);cout << endl;}private:bool Check(Node* root, int blackNum, const int refNum){//到路径结束位置检查黑色节点if (root == nullptr){if (blackNum != refNum){cout << "黑色节点不相等" << endl;return false;}// << blackNum << endl;return true;}//检查红色节点if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "连续红节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}void _Inoder(const Node* root){if (root == nullptr){return;}_Inoder(root->_left);cout << root->_kv.first << ":" << _root->_kv.second << endl;_Inoder(root->_right);}private:Node* _root = nullptr;};

map

#pragma once
#include"BRTree.h"//对map的封装namespace myNameSpace
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public://插入bool insert(const  pair <K, V>& kv){return _t.Insert(kv);}//封装红黑树的迭代器typedef typename BRTree<K, pair< K, V>, MapKeyOfT>::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return  _t.End();}BRTree< K, pair <K, V>, MapKeyOfT> _t;};void test_map(){/*map<int, int> m;m.insert({1,1});m.insert({2,2});m.insert({3,1});m.insert({7,1});map<int,int>::iterator it = m.begin();while (it != m.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;*/map<string, int> m1;m1.insert({ "hello",1});m1.insert({ "world",2});m1.insert({ "find",1});m1.insert({ "peace",1});map<string, int>::iterator it1 = m1.begin();while (it1 != m1.end()){cout << it1->first << ":" << it1->second << endl;++it1;}cout << endl;}}

set

#pragma once
#include"BRTree.h"namespace myNameSpace {template<class K>class set {struct  SetKeyOfT{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _t.Insert(key);}//对于红黑树的迭代器,需要实例化红黑树的迭代器//所以需要在红黑树的基础上封装迭代器typedef typename BRTree<const K,  K, SetKeyOfT>::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}private:BRTree<const K,K, SetKeyOfT> _t;};void test_set(){set<int> s;s.insert(1);s.insert(2);s.insert(4);s.insert(7);s.insert(8);s.insert(9);set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;}}

http://www.yayakq.cn/news/533026/

相关文章：

  • 免费的游戏网站建设wordpress 4.7.2
  • 中国建设招标网网站湖南省住房和城乡建设厅门户网站
  • 上海城乡住房建设部网站首页如何在阿里云上建设网站
  • 自己做电影网站seo关键词软件
  • 莱芜网站建设自助建站优化从事网站类网站建设的
  • 网站建设的布局对网络推广的影响新乡做网站价格
  • 手机网站开发 教程大连装修公司前十名
  • 做视频网站设备需求宝安中心区房价走势
  • php装修网站源码天津房产网
  • h5彩票网站怎么做发布软文
  • ppt模板下载素材网站网页制作专业搜题
  • 网站制作需求表wordpress中页面伪静态
  • 网站开发公司 logo免费加速器看国外网站
  • 上传视频网站开发女生学计算机哪个专业简单
  • 网站建站销售提成vs做的网站怎么发布
  • 上海网站建设 paiky北京网站改版公司
  • 义乌网站中小企业网站建设济南兴田德润电话
  • 1g内存的服务器可以建设几个网站wordpress服务框
  • 简述商业网站建设的流程福州市住房和城乡建设部网站
  • 海口网络平台网站开发新手怎么用DW建设一个网站
  • asp.net网站开发简明教程企业网站建设兴田德润很赞
  • 泰安网站推广优化重庆做网站制作公司
  • 免费效果图网站网站建设的步骤以及流程
  • 品牌做网站电商赚钱吗
  • 自己做购物网站怎么做wordpress用户名密码破解
  • 网站维护平台做公司的网站大概多少钱
  • 品牌企业网站案例短网址生成器是什么意思
  • 网站建设需要哪些信息网站的服务器选择
  • 青海建设厅网站wordpress 上传图片 500
  • 深圳电子网站开发建设工程施工合同2017