AI 助理
备案控制台
开发者社区 物联网 文章 正文

C++基础知识（八：STL标准库 deque ）

2024-07-03 214
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： deque在C++的STL(Standard Template Library)中是一个非常强大的容器，它的全称是“Double-Ended Queue”，即双端队列。deque结合了数组和链表的优点，提供了在两端进行高效插入和删除操作的能力，同时保持了随机访问的特性。

目录

双端队列和普通队列的区别？

普通队列（queue）

双端队列（deque）

总结区别

deque的特点：

deque的基本操作：

构造与初始化：

插入与删除：

访问元素：

其他操作：

示例代码：

什么时候用deque，什么时候用vector，什么时候用list?

std::vector

std::deque

std::list

总结

deque在C++的STL(Standard Template Library)中是一个非常强大的容器，它的全称是“Double-Ended Queue”，即双端队列。deque结合了数组和链表的优点，提供了在两端进行高效插入和删除操作的能力，同时保持了随机访问的特性。

双端队列和普通队列的区别？

普通队列（queue）

  • 先进先出（FIFO）原则：普通队列遵循先进先出的原则，这意味着最先加入队列的元素将是最先被移除的。
  • 操作限制：在普通队列中，新的元素只能从队尾（rear）添加（enqueue），而元素的移除只能从队头（front）进行（dequeue）。

双端队列（deque）

  • 灵活的操作：双端队列允许在队列的两端进行插入和删除操作。这意呀着元素可以从队头（front）或队尾（rear）添加或移除。
  • 不限制操作端：双端队列没有固定的操作端限制，因此它不是严格意义上的FIFO数据结构，而是更加灵活。

总结区别

  1. 操作端：
  • 普通队列只允许在一端插入（队尾）和另一端删除（队头）。
  • 双端队列允许在两端进行插入和删除。
  1. 数据访问：
  • 普通队列中，数据访问遵循先进先出原则。
  • 双端队列中，数据访问更灵活，可以在两端进行访问，不严格遵循先进先出原则。
  1. 使用场景：
  • 普通队列常用于需要按顺序处理任务的情况，如打印机任务队列、事件处理队列等。
  • 双端队列适用于需要灵活操作数据的情况，如滑动窗口算法、最近最少使用（LRU）缓存算法等。

deque的特点：

  1. 动态大小：deque可以动态地增加或减少元素数量。
  2. 随机访问：deque支持通过下标直接访问元素，时间复杂度为O(1)。
  3. 两端操作：deque可以在头部和尾部进行快速的插入和删除操作，时间复杂度通常为O(1)。
  4. 内部实现：deque使用一种复杂的内部结构来实现其特性，它将数据分割成多个连续的块，每个块的大小通常是固定的，这样既保证了随机访问的效率，又允许在两端进行高效的插入和删除。

deque的基本操作：

  • 构造与初始化：
  • std::deque<int> d; // 创建一个空的deque
  • std::deque<int> d(10, 5); // 创建一个含有10个元素，每个元素值为5的deque
  • 插入与删除：
  • d.push_front(1); // 在deque前端插入元素
  • d.push_back(2); // 在deque后端插入元素
  • d.pop_front(); // 删除deque前端的元素
  • d.pop_back(); // 删除deque后端的元素
  • d.insert(d.begin(), 0); // 在指定位置插入元素
  • d.erase(d.begin()); // 删除指定位置的元素
  • 访问元素：
  • d.front(); // 访问deque的第一个元素
  • d.back(); // 访问deque的最后一个元素
  • d.at(index); // 访问指定索引的元素，如果索引越界会抛出异常
  • d[index]; // 直接通过下标访问元素
  • 其他操作：
  • d.size(); // 获取deque中的元素数量
  • d.empty(); // 检查deque是否为空
  • d.clear(); // 清空deque中的所有元素

示例代码：

Cpp

#include <iostream>
#include <deque>
int main()
{
    std::deque<int> d;
    // 插入元素
    d.push_back(1);
    d.push_front(2);
    d.push_back(3);
    // 访问元素
    std::cout << "Front: " << d.front() << ", Back: " << d.back() << std::endl;
    // 删除元素
    d.pop_front();
    d.pop_back();
    for (std::size_t i = 0; i < d.size(); ++i)
    {
        std::cout << "d-value: " << d[i] << std::endl;
    }
    return 0;
}

image.gif

image.gif 编辑

什么时候用deque，什么时候用vector，什么时候用list?

std::vector

  • 使用场景：
  • 当你需要频繁的随机访问元素时。
  • 当插入和删除操作主要发生在容器的末端时。
  • 当容器的大小在初始化后变化不大，或者可以预先分配足够空间时。
  • 优点：
  • 提供随机访问，访问时间复杂度为O(1)。
  • 插入和删除元素在末尾时效率高，时间复杂度为O(1)。
  • 内存使用紧凑，元素在一块连续的内存区域中。
  • 缺点：
  • 在中间或开头插入或删除元素时效率低，时间复杂度为O(n)。

std::deque

  • 使用场景：
  • 当你需要在容器的头部和尾部频繁地插入和删除元素时。
  • 当你希望保持随机访问能力时。
  • 优点：
  • 支持在头部和尾部的高效插入和删除，时间复杂度通常为O(1)。
  • 提供随机访问，时间复杂度为O(1)。
  • 缺点：
  • 在中间位置插入或删除元素效率不如std::list。
  • 内存使用比std::vector分散，因为元素分布在多个块中。

std::list

  • 使用场景：
  • 当你需要在容器的任意位置频繁插入和删除元素时。
  • 当随机访问不是主要操作时。
  • 优点：
  • 在列表的任意位置插入和删除元素都非常高效，时间复杂度为O(1)。
  • 不需要连续的内存空间，因此在内存分配方面更灵活。
  • 缺点：
  • 不支持随机访问，访问时间复杂度为O(n)。
  • 遍历整个列表时可能比std::vector或std::deque慢。

总结

  • 如果需要大量随机访问且插入删除操作集中在末尾，使用std::vector。
  • 如果需要在两端高效插入删除且随机访问，使用std::deque。
  • 如果需要在任意位置频繁插入删除且不关心随机访问，使用std::list。
文章标签：
C++
容器
前端开发
索引
算法
关键词：
C++ stl
C++库
C++ stl库
C++ deque
C++基础知识
笨笨小乌龟
目录
相关文章
ephemerals__
|
4月前
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map（附源码）
本文基于红黑树的实现，模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改，实现了两种容器的功能。主要步骤包括：1) 修改红黑树节点结构以支持不同数据类型；2) 使用仿函数适配键值比较逻辑；3) 实现双向迭代器支持遍历操作；4) 封装`insert`、`find`等接口，并为`map`实现`operator[]`。最终，通过测试代码验证了功能的正确性。此实现减少了代码冗余，展示了模板与仿函数的强大灵活性。
ephemerals__
114 2
ephemerals__
|
4月前
|
存储 算法 C++
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现，内部元素按键自动升序排列，存储键值对，支持通过键访问或修改值；而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能，并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别，强调了`map`在处理键值关系时的优势。
ephemerals__
221 73
ephemerals__
|
4月前
|
存储 算法 C++
【c++丨STL】set/multiset的使用
本文深入解析了STL中的`set`和`multiset`容器，二者均为关联式容器，底层基于红黑树实现。`set`支持唯一性元素存储并自动排序，适用于高效查找场景；`multiset`允许重复元素。两者均具备O(logN)的插入、删除与查找复杂度。文章详细介绍了构造函数、迭代器、容量接口、增删操作（如`insert`、`erase`）、查找统计（如`find`、`count`）及`multiset`特有的区间操作（如`lower_bound`、`upper_bound`、`equal_range`）。最后预告了`map`容器的学习，其作为键值对存储的关联式容器，同样基于红黑树，具有高效操作特性。
ephemerals__
166 3
ephemerals__
|
5月前
|
存储 算法 C++
【c++丨STL】priority_queue（优先级队列）的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`（优先级队列）。`priority_queue`根据严格的弱排序标准设计，确保其第一个元素始终是最大元素。它底层使用堆结构实现，支持大堆和小堆，默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`，通过仿函数控制堆的类型，并调用封装容器的接口实现功能。最后，感谢大家的支持与关注。
ephemerals__
216 1
平凡程序猿~
|
5月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象（下）
在上一篇博客中，我们学习了C++的基础类与对象概念，包括类的定义、对象的使用和构造函数的作用。在这一篇，我们将深入探讨C++类的一些重要特性，如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象，以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念，提升代码的健壮性、灵活性和可维护性。
平凡程序猿~
114 0
hahaha无
|
1月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果：注意：类模板中的成员函数若是放在类外定义时，需要加模板参数列表。return 0;
hahaha无
45 0
hahaha无
|
1月前
|
存储 编译器 程序员
c++的类（附含explicit关键字，友元，内部类）
本文介绍了C++中类的核心概念与用法，涵盖封装、继承、多态三大特性。重点讲解了类的定义（`class`与`struct`）、访问限定符（`private`、`public`、`protected`）、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数（构造函数、析构函数、拷贝构造、赋值重载）以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员（变量与函数）、友元（友元函数与友元类）的概念及其使用场景，并简要介绍了内部类的特性。
hahaha无
115 0
ephemerals__
|
3月前
|
编译器 C++ 容器
【c++11】c++11新特性（上）（列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式）
C++11为C++带来了革命性变化，引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式，initializer_list简化了容器多元素初始化；右值引用和移动语义优化了资源管理，减少拷贝开销；类新增移动构造和移动赋值函数提升性能；lambda表达式提供匿名函数对象，增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展，提升了开发效率与程序性能。
ephemerals__
115 12
蓝易云
|
4月前
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨，我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性，而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧，对于提升C++编程水平至关重要。
蓝易云
98 16
预备女程序员a
|
4月前
|
编译器 C++
类和对象（中 ）C++
本文详细讲解了C++中的默认成员函数，包括构造函数、析构函数、拷贝构造函数、赋值运算符重载和取地址运算符重载等内容。重点分析了各函数的特点、使用场景及相互关系，如构造函数的主要任务是初始化对象，而非创建空间；析构函数用于清理资源；拷贝构造与赋值运算符的区别在于前者用于创建新对象，后者用于已存在的对象赋值。同时，文章还探讨了运算符重载的规则及其应用场景，并通过实例加深理解。最后强调，若类中存在资源管理，需显式定义拷贝构造和赋值运算符以避免浅拷贝问题。
预备女程序员a
55 1