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

河南濮阳最新消息今天网站关键词排名优化

河南濮阳最新消息今天,网站关键词排名优化,域名交易网站,查询房产信息个人的房产信息查询目录 一、栈的模拟和deque容器 1.deque 1.1deque结构 1.2deque优缺点 2.stack模拟 二、队列的模拟 三、priority_queue优先级队列 1.优先级队列模拟 2.添加仿函数 一、栈的模拟和deque容器 在之前,我们学过了C语言版本的栈,可以看这篇文章 栈和…

 

目录

一、栈的模拟和deque容器

1.deque

1.1deque结构

1.2deque优缺点

2.stack模拟

二、队列的模拟

三、priority_queue优先级队列

1.优先级队列模拟

2.添加仿函数


一、栈的模拟和deque容器

在之前,我们学过了C语言版本的栈,可以看这篇文章 栈和队列。

但是C语言没有模板,我们只能固定一个类型去写,在C++中引入了模板的概念,我们只需要写一份,在调用中给到类型,编译器会自动去帮我们推导是栈里面元素的类型,会非常方便。

1.deque

我们可以看到,库函数里面的栈调用的是一个deque容器。

deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。

1.1deque结构

首先deque有一个中控数组,这个数据是指针数组,存放的内容是指针,每个指针都指向的一块空间的起始地址。

他的迭代器有  cur(当前数据当前位置)  fisrt(数据起始位置)last(数据结尾位置) node(指向数据的指针)。

头插就去找到最前面的那个有效指针进行头插,尾插就找最后面那个有效指针尾插,遍历就通过迭代器每一个空间块从头遍历到位,就换下一个空间块。

 

1.2deque优缺点

deque实际上是一个缝合怪,他结合了vector和list的内容,将他们糅合在了一起。

优点

与vector比较,deque的优势是 :头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素,因此其效率是必vector高的。

与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。

 但是他也有缺点

deque容器不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list。

那么为何他能在栈和队列中使用,并成为默认容器呢?

因为栈和队列需要尾插,尾删,队列需要尾插,头删deque容器完全可以适配这些需求,因为不需要遍历,并且deque扩容时不需要挪动数据,这也是的deque的效率变高。

2.stack模拟

stack的模拟非常简单,调用模板Container容器的函数就可以了,也不需要迭代器(不用遍历),也不需要构造函数析构函数什么的,因为Container容器是自定义类型,会自动调用的相关构造析构拷贝函数。

#pragma once
#include<deque>
namespace kky
{template<class T, class Container = deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}

二、队列的模拟

队列模拟跟stack差不都,多了一个back接口,出数据的时候要调用pop_front()

#pragma once
#include<deque>
namespace kky
{template<class T, class Container = deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& front(){return _con.front();}const T& back(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}

三、priority_queue优先级队列

优先级队列出数据的时候,会先出优先级高的数据。

如何来判断优先级的高低呢?

这跟你传的数据类型有关,先举个例子

我们插入了   1,10,8,5,6   但出数据的时候缺省按照数据的大小顺序来出的,在这里使用数据的大小来看段他们优先级的高低。

优先级队列出数据时会帮我们做好排序,他的本质就是堆,通过堆的向上向下调整来处理优先级问题。具体堆排序的过程可以看选择排序中的堆排序。

1.优先级队列模拟

优先级队列的模拟实现就是要建堆,每一次插入数据都要进行向上调整,保证是大堆或者小堆。

出数据的时候将第一个数据和最后一个数据互换,再进行尾删,因为第一个数据是我们想要出的数据,将他和最后一个数据交换再尾删,就可以提取出这个数据了,同时现在只有第一个元素不符合小堆或者大堆的情况,其他元素都符合,因此进行一次从索引为0位置的向下调整即可。

namespace kky
{template<class T,class Container = vector<T>>class priority_queue{public:void adjust_up(size_t child){while(child>0){size_t parent = (child - 1) / 2;if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;}else{break;}}}void adjust_down(size_t parent){int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1]){child++;}if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size()-1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}

刚刚的代码构建了一个大堆,但是我们如果想要构建小堆,难不成又要重写一份代码吗?  那必定不是可能的。 

2.添加仿函数

在C语言中,我们可以通过函数指针来处理顺序的问题,但是函数指针类型很繁琐,并且不容易理解,C++推出了仿函数来帮助我们处理这类问题。

写一个类,仅仅重载了operator(),返回类型为bool,在后面进行判断的时候,我们就可以调用这个类对象的(),类似于函数一样,就可以处理了,

template<class T>
class Less
{
public:bool operator()(const T& x1, const T& x2){return x1 < x2;}
};

第一个方式太丑陋了,一般使用第二种方式去调用。

那之前,我们代码中的判断语句,都可以通过调用仿函数更改了 

给模板参数再添加一个类

template<class T, class Container = vector<T>,class Compare = Less<T>>

现在就可以开始更改了 

只需要注意顺序即可,需要这样判断的都可以更改,参考如下代码

namespace kky
{template<class T, class Container = vector<T>,class Compare = Less<T>>class priority_queue{public:void adjust_up(size_t child){Compare com;while (child > 0){size_t parent = (child - 1) / 2;if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;}else{break;}}}void adjust_down(size_t parent){Compare com;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child+1])){child++;}if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}

 这是我们写的Less仿函数,如果你想让优先级队列建小堆,就可以写再写一个仿函数

template<class T>
class Greater
{
public:bool operator()(const T& x1, const T& x2){return x1 > x2;}
};

需要的时候调用一下即可 

http://www.yidumall.com/news/25212.html

相关文章:

  • 怎么把自己做的网页上传网站网络推广赚钱平台有哪些
  • 个人网站报价中国站长之家官网
  • 信用网站建设方案网站seo资讯
  • 网站开发工作标准焦作网络推广哪家好
  • 如何用网络营销推广优化网站的意思
  • dede免费网站模板大数据免费查询平台
  • 自助建站系统官方版百度指数平台
  • wordpress 4.7.3 id智能网站排名优化
  • 洛阳网站设计哪家专业今日头条官网登录入口
  • 一级做a免费观看视频网站商业推广费用一般多少
  • 减少网站跳出率适合发软文的平台
  • 网站怎么做百度排名厦门人才网
  • 张家口企业网站建设建网站软件工具
  • 微信网站开发怎么做网址导航推广
  • 物流网站制作怎么做百度一下搜索引擎大全
  • 买了域名怎么做网站满十八岁可以申请abc认证吗
  • 广东梅州兴宁做网站公司七台河网站seo
  • 沈阳企业建站百度网页游戏大厅
  • phpweb网站建设谷歌搜索引擎在线
  • 如果在阿里云上做自己的网站最有效的恶意点击
  • 北京住房和城乡建设网官网关键词seo深圳
  • 广州 建网站seo兼职
  • 做网站资金来源是什么深圳最新疫情
  • 做的网站响应速度慢线上渠道推广有哪些方式
  • 武汉互联网企业排名成都seo推广员
  • 永康物流网站百度认证
  • 做网站之前要先购买服务器吗网络推广靠谱吗
  • 柳州网站开发沈阳seo网站推广
  • 可以自学网站开发网站营销网
  • 在线原型设计网站查询网入口