代码编织梦想

deque

  1. 可以队首和队尾插入,也可以队首和队尾弹出

  2. 支持随机访问,即可以直接用下标来访问元素。它和vector有点像,因为它可以index索引和at()函数索引,当然,也可以迭代器索引。

  3. 此外,它可以进行指定尺寸的构造,queue就不可以指定尺寸构造。

构造函数

deque<int> q1;
deque<int> q2(6,8);//6个值为8的成员
deque<int> q3(q2.begin() + 2, q2.end());
deque<int> q4(q2);

迭代器

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AuIBjgSo-1669195255380)(C:/Users/l/AppData/Roaming/Typora/typora-user-images/image-20221123160955743.png)]

常用操作

操作明显多于queue和pq

empty(); //判断容器是否为空
clear();  //清空容器的所有数据
size(); //返回容器中的元素的个数
resize(num); //重新指定容器的长度为num,若容器变长,则以默认值填充新位置。//如果容器变短,则末尾超出容器长度的元素被删除。
resize(num,elem); //重新指定容器的长度为num,若容器变长,则以elem值填充新位置。如果容器变短,则超出容器长度的元素被删除。
clear();  //清空容器的所有数据
swap();

访问操作

at(int idx); //返回索引idx所指的数据
operator[]; //返回索引idx所指的数据
front(); //返回容器中第一个数据元素
back(); //返回容器中最后一个数据元素

插入删除覆盖

deque<int>::iterator it = bar.begin();
push_back(elem);  //在容器尾部添加一个数据
push_front(elem);  //在容器头部插入一个数据
pop_back();  //删除容器最后一个数据
pop_front();  //删除容器第一个数据

insert(pos,elem);  //在pos位置插入一个elem元素的拷贝,返回新数据的位置。
insert(pos,n,elem); //在pos位置插入n个elem数据,无返回值
insert(pos,beg,end);  //在pos位置插入[beg,end)区间的数据,无返回值

erase(beg,end);  //删除[beg,end)区间的数据,返回下一个数据的位置。
erase(pos); //删除pos位置的数据,返回下一个数据的位置。

assign(beg, end);  //将[beg,end)区间中的数据拷贝赋值给本身。
assign(n,elem); //将n个elem拷贝赋值给本身。

关于push和emplace的区别

https://blog.csdn.net/jokerMingge/article/details/119736247

C++11

emplace()
emplace_back()
emplace_front()
emplace_cbegin
emplace_crbegin    
emplace_cend
emplace_crend ;
shrink_to_fit();  //请求容器减少内存使用以适应其大小。 

与其他container的区别

头插

vector对于头部的插入效率低,数据量越大,效率越低,例如头部后有十万个数据,则往头部插入一个数据时,十万个数据都需要往后挪一挪才能在头部插入数据。deque相对而言,对头部的插入删除速度会比vector快。deque在头部和尾部进行数据插入和删除操作更加高效。

如果没有频繁在头部或尾部进行插入和删除操作,deque比list和forward_list的性能更差。

访问

vector访问元素时的速度会比deque快。

存储

与vector不同的是,deque不能保证所有的元素存储在连续的空间中,在deque中通过指针加量方式访问元素可能会导致非法的操作。

vector使用使用动态数组,该数组通常需要动态增长;deque中的元素可能分散在不同的存储块中,在deque中保存一些必要的信息,通常用来在常数范围内直接访问deque中的任何一个元素,所以deque的内部实现比vector复杂,但是这些额外信息使得dque在某些情况下增长更加的高效,特别是在序列比较大,重新分配成本比较高的情况下。

内部工作原理

和 vector 容器采用连续的线性空间不同,deque 容器存储数据的空间是由一段一段等长的连续空间构成,各段空间之间并不一定是连续的,可以位于在内存的不同区域。为了管理这些连续空间,deque 容器用数组存储着各个连续空间的首地址。也就是说,数组中存储的都是指针,指向那些真正用来存储数据的各个连续空间。

通过建立数组,deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果。换句话说,当 deque 容器需要在头部或尾部增加存储空间时,它会申请一段新的连续空间,同时在数组的开头或结尾添加指向该空间的指针,由此该空间就串接到了 deque的头部或尾部。

priority_queue

优先队列是一种会按照默认或自定义的优先级进行自动排序的队列,其特点是优先级高的元素排在队首,低的排在队尾。

创建

数据类型:可以是int、double等基本类型,也可以是自定义的结构体。
容器类型:一般为deque(双端列表)、vector(向量容器),可省略,省略时以vector为默认容器。
pq:优先队列名。

priority_queue< 数据类型,容器类型,优先规则> pq;
priority_queue<int> pq;
priority_queue<int,vector<int>,less<int> > pq;   //以less为排列规则(大顶堆,表示顶堆元素比其他都大)
priority_queue<int,vector<int>,greater<int> > pq; //以greater为排列规则(小顶堆,表示顶堆元素比其他都小)

常用操作

pq.push();    //入队
pq.pop();     //出队
pq.size()     //返回当前对中元素个数
pq.top();     //优先队列   取队首元素
pq.empty();   //判断是否为空(空返回 1,非空返回 0)
C++11
pq.swap()
pq.emplace()

与queue的区别在于queue有front()和back(),而pq只有top()

queue

(58条消息) C++队列queue用法详解_KEPROM的博客-CSDN博客_c++ queue

一般直接用deque。deque的功能比queue更全,而且queue底层也是用deque创建的

创建

queue<数据类型,容器类型> q;

数据类型:可以是int、double等基本类型,也可以是自定义的结构体。
容器类型:一般为deque或者list(双向链表),可省略,省略时以deque为默认容器。

queue<int> q;  //使用默认的双端队列为底层容器创建一个空的queue队列对象q,数据元素为int类型。
queue<int,list<int>> q1;
queue<int,list<int>> q2(q1);
/*复制构造函数(queue(const queue&)),用一个queue对象创建新的queue对象。 
利用queue对象q1,创建一个以双向链表为底层容器的queue对象q2*/
  1. 和 stack 一样,queue 也没有迭代器。访问元素的唯一方式是遍历容器内容,并移除访问过的每一个元素。
  2. 只能队尾插入,队首弹出。
  3. queue不初始化元素个数或者初始化值

常用操作

q.push(x);      //入队,将元素 x 从队尾插入(尾插法)
q.pop();        //出队,删除对首元素,并返回其值
q.size();       //返回队中元素个数
q.front();      //返回队首元素
q.back();       //返回队尾元素
q.empty();      //判断是否为空(空返回 1,非空返回 0)
C++11
q.swap(q2)
q.emplace(x)	//入队

empty()函数可以判断队列是否为空,但没有clear来清空,可以创建空的queue用swap函数交换

queue q2;
if (q1.empty()) {
cout << “q1 is empty” << endl;
}
q1.swap(q2);
if (q1.empty()) {
cout << “q1 is empty after swap” << endl;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lanyi_ly/article/details/128004341

c++优先队列(priority_queue)用法详解_吕白_的博客-爱代码爱编程_priority_queue用法

既然是队列那么先要包含头文件#include <queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队 优先队列具有队列的所有特性,包括基本操作,只是在这

C/C++编程:优先队列priority_queue-爱代码爱编程

priority_queue本质是一个堆。 1 . 头文件是#include 2 . 关于priority_queue中元素的比较 模板申明带3个参数:priority_queue<Type, Container, Functional>,其中Type 为数据类型,Container为保存数据的容器,Functional 为元素

C++优先队列(priority_queue)-爱代码爱编程

一、定义 包含头文件#include <queue> 普通队列(queue)是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。 在优先队列(priority_queue)中,元素被赋予优先级。当访问元素时,具有最高优先级的元素排在队列前面,优先出队。 默认的情况下,priority_queue是利用一个最大堆(max-heap

C++中优先队列priority_queue的基础用法-爱代码爱编程

文章目录 前言头文件结构定义队列排序优先队列使用实现排序取出数组中最大的k个数自定义结构自定义比较函数的另一种写法常用函数总结 前言 学习优先队列之前先看个单词队列 queue, 这个单词的读法很多人都能读对吧,音标是 /kjuː/ ,再看一个双端队列 deque,它的音标是 /dek/,应该有人读错了吧,反正我是没读对,刚开始看见一次错一次

c++——优先队列(priority_queue)-爱代码爱编程

优先队列详解/C++ 优先队列 1.概念:什么是优先队列呢?在优先队列中,元素被赋予优先级,当访问元素时,具有最高级优先级的元素先被访问 .即优先队列具有最高级先出的行为特征。它可以说是队列和排序的完美结合体,不仅可以存储数据,还可以将这些数据按照我们设定的规则进行排序。 2.定义:优先队列在头文件#include 中;其声明格式为:priority_q

C++_优先级队列(priority_queue) & 仿函数-爱代码爱编程

文章目录 1.priority_queue的介绍2 priority_queue的使用2.1 代码示例3.模拟实现priority_queue4.例题链接4.1 代码解析5.仿函数的介绍6.仿函数的优点7.仿函数代码示例8.priority_queue中的仿函数 1.priority_queue的介绍 template <class T

C++和python: priority_queue优先队列-爱代码爱编程

文章目录 使用理论简单实现C++python 使用 priority_queue包含在头文件queue中,与通常的queue不同的就在于可以自定义其中数据的优先级,让优先级高的排在队列前面,优先出队,插入的效率为logn。 优先队列具有队列的所有特性,包括基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的 top 访问队头元

优先队列(priority_queue)的原理及用法-爱代码爱编程

一、优先队列的原理及使用 std::priority_queue:在优先队列中,优先级高的元素先出队列,并非按照先进先出的要求,类似一个堆(heap)。其模板声明带有三个参数,priority_queue<Type, Container, Functional>, 其中Type为数据类型,Container为保存数据的容器,Functiona

C++优先队列priority_queue详解-爱代码爱编程

 priority_queue也是在写算法中很厉害且常用的一种数据结构 看着有点复杂,使用的时候视觉效果也是真的复杂 QAQ 普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。 在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 的行为特征。 一、前言 既然

C++优先队列(priority_queue)-爱代码爱编程

首先要包含头文件#include<queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队。优先队列具有队列的所有特性,包括队列的基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的。 基本操作 它的基本操作和队列基本操作相同: top 访问队头元素empty 队列是否为

c++---优先队列(priority_queue)-爱代码爱编程

C ++中的优先队列是STL中的派生容器,它仅考虑最高优先级元素。队列遵循FIFO策略,而优先队列根据优先级弹出元素,即,优先级最高的元素首先弹出。 与普通队列区别: 在优先队列中,队列中的每个元素都与某个优先级相关联,但是优先级在队列数据结构中不存在。 优先队列中具有最高优先级的元素将被首先删除,而队列遵循FIFO(先进先出)策略,这意味着先插入

c++priority_queue详解_wjc_sss的博客-爱代码爱编程

priority_queue详解 定义 1.priority_queue 容器适配器模拟的也是队列这种存储结构,即使用此容器适配器存储元素只能“从一端进(称为队尾),从另一端出(称为队头)”,且每次只能访问 priority_queue 中位于队头的元素。但是,priority_queue 容器适配器中元素的存和取,遵循的并不是 “First in,F

c++优先级队列priority_queue详解及其模拟实现_爱编程的小李同学的博客-爱代码爱编程

文章目录 前言一、priority_queue的介绍和使用1、priority_queue的介绍2、priority_queue的使用二、priority_queue模拟实现 前言 在优先队列中,优先级高的元素先出队列,并非按照先进先出的要求,类似一个堆(heap)。其模板声明带有三个参数,priority_queue<Type, Co

剖分(树形差分)_wyw___的博客-爱代码爱编程

E-剖分_牛客小白月赛62 (nowcoder.com) 题目描述 牛牛有一颗包含n个结点的二叉树,这些结点编号为1 ...n。这颗树被定义为:1、以结点1为根。 2、编号为α结点的两个儿子编号分别为:2 xa和2×巴+ 1。3、每个结点的权重初始都为0。 牛牛接下来会对这颗树进行m次操作,操作的格式是以下四种之—: 1、op a(这里op = 1)代表