一文带你了解C++中deque的使用

目录
  • 1)deque的定义及基本用法
  • 2)deque的迭代器
  • 3)deque的性能
  • 4)deque的应用:滑动窗口问题

1)deque的定义及基本用法

要使用deque,我们需要包含头文件,定义deque对象如下:

#include <deque>
using namespace std;
deque<int> dq; // 定义deque对象dq,其中元素类型为int型

deque支持的基本操作如下:

  • 在deque的队首插入元素:push_front()方法。
  • 在deque的队尾插入元素:push_back()方法。
  • 删除deque队首的元素:pop_front()方法。
  • 删除deque队尾的元素:pop_back()方法。
  • deque的长度:size()方法。
  • 判断deque是否为空:empty()方法。
  • 访问deque队首元素:front()方法。
  • 访问deque队尾元素:back()方法。

示例代码如下:

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    deque<int> dq;
    dq.push_front(1);   // 在队首插入元素1
    dq.push_back(2);    // 在队尾插入元素2
    dq.push_front(3);   // 在队首插入元素3
    dq.pop_back();      // 删除队尾元素2
    cout << "长度:" << dq.size() << endl;      // 打印长度
    while(!dq.empty()){
        cout << dq.front() << ' ';     // 打印队列中的每一个元素
        dq.pop_front();     // 删除队首元素
    }
    return 0;
}

执行结果:

长度:2
3 1

2)deque的迭代器

deque支持迭代器,可以按照指针的方式遍历deque中的所有元素。deque迭代器支持前向访问,但不支持随机访问,即不支持下标操作。deque迭代器又分为普通迭代器和反向迭代器,可以分别用begin(),end(),rbegin(),rend()方法来获取。

示例代码如下:

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    deque<int> dq;
    dq.push_front(1);
    dq.push_back(2);
    dq.push_back(3);
    dq.push_front(4);
    cout << "正向遍历:";
    for(deque<int>::iterator it=dq.begin();it!=dq.end();it++)
        cout << *it << ' ';    // 打印所有元素
    cout << endl;
    cout << "反向遍历:";
    for(deque<int>::reverse_iterator it=dq.rbegin();it!=dq.rend();it++)
        cout << *it << ' ';    // 打印所有元素(反向)
    cout << endl;
    return 0;
}

执行结果:

正向遍历:4 1 2 3 
反向遍历:3 2 1 4

3)deque的性能

对于在最差情况下,即内存池容量已满的情况,deque在表现上比较优,它的时间复杂度为O(1),因为deque在前端和后端进行插入和删除的操作所需时间复杂度为O(1),但如果在中间进行插入和删除,则时间复杂度为O(N),因为因为需要把后面的元素往后移动。同时,它的空间复杂度为O(N),其中N表示deque中元素的个数。

4)deque的应用:滑动窗口问题

滑动窗口问题是指在一个序列中找出所有长度为k的子序列,并且每次移动一个单位,重复执行这个操作,最终得到所有的子序列。这个问题在处理字符串问题,尤其是搜索问题中经常出现。我们可以用deque来解决这个问题,将待处理的数据元素存入到deque中,每次向右滑动窗口的时候从左边移除最先加入的元素,同时从右边添加一个新的元素。

示例代码如下:

#include <iostream>
#include <deque>

using namespace std;

void printMax(int arr[], int n, int k)
{
    deque<int> dq; // 存储元素下标,用于判断窗口是否失效,同时也维护了单调性
    for (int i=0; i<k; i++) {
        while (!dq.empty() && arr[i] >= arr[dq.back()])
            dq.pop_back();  // 维护单调性,删除队列中元素使其单调递增
        dq.push_back(i);    // 将元素下标存入队列
    }
    for (int i=k; i<n; i++) {
        cout << arr[dq.front()] << " ";    // 打印当前窗口中的最大值
        while (!dq.empty() && dq.front() <= i-k)
            dq.pop_front(); // 删除队首元素,判断队首元素是否已失效
        while (!dq.empty() && arr[i] >= arr[dq.back()])
            dq.pop_back();  // 维护单调性,删除队列中元素使其单调递增
        dq.push_back(i);    // 将元素下标存入队列
    }
    cout << arr[dq.front()] << endl;    // 打印最后一个窗口中的最大值
}

int main()
{
    int arr[] = {4, 3, 5, 4, 2, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    printMax(arr, n, k);
    return 0;
}

此示例代码中,我们定义了一个deque用于存储元素下标,同时维护单调性,使得队列中的元素单调递增。在每次可取的滑动窗口过程中,只需找到队列中的最大值。这个示例中的时间复杂度为O(N)。

以上便是关于C++中deque的基本用法和应用的相关介绍,希望对你有所帮助。

到此这篇关于一文带你了解C++中deque的使用的文章就介绍到这了,更多相关C++ deque内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++顺序容器(vector、deque、list)的使用详解

    目录 一:STL(Standard Template Library),即标准模板库,是一个高效的C++程序库 二:STL组件 三:容器 四:类型成员 五:迭代器 六:顺序容器 七:顺序容器--向量(vector) 八:顺序容器--双端队列--deque 九:顺序容器 --列表--list 一:STL(Standard Template Library),即标准模板库,是一个高效的C++程序库 1.从实现层次看,整个STL是以一种类型参数化(type parameterized)的方式实现的,基

  • C++中常见容器类的使用方法详解(vector/deque/map/set)

    目录 综合示例 1. vector:动态数组,支持随机访问 2. list:双向链表,支持双向遍历和插入删除 3. deque:双端队列,支持首尾插入删除和随机访问 4. map:红黑树实现的关联数组,支持按键访问和遍历 5. set:红黑树实现的集合,支持按值访问和遍历 6. unordered_map:哈希表实现的关联数组,支持按键访问和遍历 7. unordered_set:哈希表实现的集合,支持按值访问和遍历 检索方法示例 1. vector:根据下标检索 2. deque:根据下标检索

  • C++ STL入门教程(3) deque双向队列使用方法

    一.简介 deque(Double Ended Queues,双向队列)和向量很相似,但是它允许在容器头部快速插入和删除(就像在尾部一样). 二.完整程序代码 /*请务必运行以下程序后对照阅读*/ #include <deque> #include <iostream> #include <algorithm> #include <stdexcept> using namespace std; void print(int num) { cout <&

  • C++ deque与vector对比的优缺点

    目录 deque容器 deque的迭代器 deque的成员函数 deque容器 deque的相关文档 deque与vector十分的相识.vector是单向开口的连续线性空间(单向扩容),deque则是一种双向开口的连续线性空间(双向扩容).双向开口:可以在头尾两端分别做元素的插入和删除操作.区别就在此,vector当然也可以在头尾两端进行操作,但是其头部操作的效率奇差,无法被接受,如:stack与queue的容量适配器就在二者其中,选择deque(当然使用vector也可). vector与d

  • 深入分析C++中deque的使用

    首先,当考虑到内存分配和执行性能的时候,使用std::deque要比std::vector好. Deque总览 deque和vector一样都是标准模板库中的内容,deque是双端队列,在接口上和vector非常相似,在许多操作的地方可以直接替换.假如读者已经能够有效地使用vector容器,下面提供deque的成员函数和操作,进行对比参考. 函数 描述 c.assign(beg,end)c.assign(n,elem)  将[beg; end)区间中的数据赋值给c.将n个elem的拷贝赋值给c.

  • C++ deque容器的用法详解

    deque(双端队列)是由一段一段的定量连续空间构成,可以向两端发展,因此不论在尾部或头部安插元素都十分迅速. 在中间部分安插元素则比较费时,因为必须移动其它元素. deque容器的构造函数 //deque和vector的区别 //deque对于头部的插入和删除效率低,数据量越大,效率越低 //deque相对而言,对于头部的插入和删除比vector快 //deque访问元素时的速度比vector要慢,和两者的内部实现有关 #include <iostream> #include <deq

  • 一文带你理解 Vue 中的生命周期

    目录 1.beforeCreate & created 2.beforeMount & mounted 3.beforeUpdate & updated 4.beforeDestroy & destroyed 5.activated & deactivated 前言: 每个 Vue 实例在被创建之前都要经过一系列的初始化过程.例如需要设置数据监听.编译模板.挂载实例到 DOM.在数据变化时更新 DOM 等.同时在这个过程中也会运行一些叫做生命周期钩子的函数,给予用户

  • 一文带你掌握Java8中Lambda表达式 函数式接口及方法构造器数组的引用

    目录 函数式接口概述 函数式接口示例 1.Runnable接口 2.自定义函数式接口 3.作为参数传递 Lambda 表达式 内置函数式接口 Lambda简述 Lambda语法 方法引用 构造器引用 数组引用 函数式接口概述 只包含一个抽象方法的接口,称为函数式接口. 可以通过 Lambda 表达式来创建该接口的对象. 可以在一个接口上使用 @FunctionalInterface 注解,这样做可以检查它是否是一个函数式接口.同时 javadoc 也会包含一条声明,说明这个接口是一个函数式接口.

  • 一文带你了解Java中的ForkJoin

    目录 什么是ForkJoin? ForkJoinTask 任务 ForkJoinPool 线程池 工作窃取算法 构造方法 提交方法 创建工人(线程) 例:ForkJoinTask实现归并排序 ForkJoin计算流程 前言: ForkJoin是在Java7中新加入的特性,大家可能对其比较陌生,但是Java8中Stream的并行流parallelStream就是依赖于ForkJoin.在ForkJoin体系中最为关键的就是ForkJoinTask和ForkJoinPool,ForkJoin就是利用

  • 一文带你了解Java中的Object类及类中方法

    目录 1. Object类介绍 2. 重写toString方法打印对象 3. 对象比较equals方法 4. hashCode方法 1. Object类介绍 Object是Java默认提供的一个类.Java里面除了Object类,所有的类都是存在继承关系的.默认会继承Object父 类.即所有类的对象都可以使用Object的引用进行接收. 范例:使用Object接收所有类的对象 class Person{} class Student{} public class Test { public s

  • 一文带你了解Qt中槽的使用

    目录 一.建立槽和按钮之间的连接 二.槽函数的定义 一.建立槽和按钮之间的连接 connect(信号发送者,发送的信号,信号接收者,信号接收者的槽函数) 1.例子 connect(ui->pushButton,SIGNAL(clicked(bool)),this,SLOT(showinfo())); 解释: 信号反发送者:pushButton(这是一个按钮),发送信号:clicked(点击按钮),信号接收者:this(本类),信号接收者的槽函数:showinfo(点击按钮后响应的函数) 二.槽函

  • 一文带你了解Golang中interface的设计与实现

    目录 前言 接口是什么 iface 和 eface 结构体 _type 是什么 itab 是什么 生成的 itab 是怎么被使用的 itab 关键方法的实现 根据 interfacetype 和 _type 初始化 itab 接口断言过程总览(类型转换的关键) panicdottypeI 与 panicdottypeE iface 和 eface 里面的 data 是怎么来的 convT* 方法 Java 里面的小整数享元模式 总结 在上一篇文章<go interface 基本用法>中,我们了

  • 一文带你了解Vue3中toRef和toRefs的用法

    toRef 顾名思义,不是ref 响应式数据,给它转成ref 响应式数据 通俗易懂的理解: <template> <h3>姓名:{{ person.name }}</h3> <h3>年龄:{{ person.age }}</h3> <h3>薪资:{{ person.job.j1.salary }}</h3> <button @click="person.name += '!'">修改姓名&l

  • 一文带你了解Python中的双下方法

    目录 前言 1. init方法 2. 运算符的双下方法 2.1 比较运算符 2.2 算术运算符 2.3 反向算术运算符 2.4 增量赋值运算符 2.4 位运算符 3.字符串表示 4.数值转换 5.集合相关的双下方法 6.迭代相关的双下方法 7.类相关的双下方法 7.1 实例的创建和销毁 7.2 属性管理 7.3 属性描述符 8.总结 前言 大家在写 Python 代码的时候有没有这样的疑问. 为什么数学中的+号,在字符串运算中却变成拼接功能,如'ab' + 'cd'结果为abcd:而*号变成了重

  • 一文带你了解MySQL中触发器的操作

    目录 概述 介绍 触发器的特性 操作—创建触发器 操作—new和old 操作—查看触发器 操作—删除触发器 注意事项 概述 介绍 触发器,就是一种特殊的存储过程.触发器和存储过程一样是一个能够完成特定功能.存储在数据库服务器上的SQL片段,但是触发器无需调用,当对数据库表中的数据执行DML操作时自动触发这个SQL片段的执行,无需手动条用. 在MySQL中,只有执行insert,delete,update操作时才能触发触发器的执行 触发器的这种特性可以协助应用在数据库端确保数据的完整性,日志记录,

  • 一文带你了解Java中IO流与Guava的使用

    目录 Guava IO 分类 常用的流 示例 Guava中的IO 其他 结束语 Guava IO 日常系统交互中,文件的上传下载都是常见的,一般我们会通过jdk提供的IO操作库帮助我们实现.IO指的是数据相对当前操作程序的入与出,将数据通过 输出流从程序输出,或者通过输入流将数据(从文件.网络.数据等)写入到程序,这里的IO指的是基于流作为载体进行数据传输.如果把数据比作合理的水,河就是IO流,也是数据的载体. Java为我们提供了非常多的操作IO的接口与类,帮助开发者实现不同源间的数据传输,比

随机推荐