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

【C++】STL之deque

news 来源：原创 2025/6/28 13:29:32

deque

Deque 的底层既不直接依赖 vector 也不依赖 list，而是结合了两者的思想，采用了一种分块（chunk）存储与动态指针数组（map）结合的结构。以下是详细分析：

1. 底层结构设计

Deque 的核心设计是分块存储 + 动态指针数组（map）：

分块存储：
Deque 的元素被分散存储在多个固定大小的连续内存块（称为 buffer 或 chunk）中。
- 每个块的容量固定（例如 512 字节或存储固定数量的元素，如 16 个）。
- 块之间通过指针连接，但物理内存不连续（类似链表），但块内部是连续的（类似数组）。
中央控制器（map）：
Deque 使用一个动态数组（类似 vector）管理这些块的指针，称为 map。
- map 本身是一个指针数组，每个元素指向一个块的起始地址。
- map 可以双向扩容（头部或尾部插入新块的指针），但通常实现中会预留前后空间，减少频繁扩容。

2. 为什么不是 `vector` 或 `list`？

(1) 与 `vector` 的区别

内存连续性：
vector 要求所有元素在物理内存上连续，而 Deque 的块内连续，块间不连续。
- Deque 的头尾插入可以快速分配新块，无需移动已有元素。
- vector 的头部插入需要整体移动元素，效率低（O(n)）。
扩容策略：
- vector 扩容时需要重新分配更大的内存并复制所有元素（O(n)）。
- Deque 只需在 map 中插入新块指针（分摊 O(1)）。

(2) 与 `list` 的区别

内存局部性：
- list 的每个元素单独分配内存（节点），空间开销大且访问效率低。
- Deque 的块内连续存储，缓存友好，随机访问效率远高于 list。
扩容方式：
- list 每次插入只需分配一个节点（O(1)）。
- Deque 的块是预分配的，只有当块用满时才分配新块，减少内存碎片。

3. Deque 的核心优势

高效的头尾插入：
头尾插入只需操作 map 的前后指针，或分配新块，时间复杂度为分摊 O(1)。
较好的随机访问：
通过 map 快速定位元素所在的块，再通过块内偏移访问元素，时间复杂度 O(1)。
内存效率：
分块设计减少大规模数据复制的开销，同时保留局部连续性。

4. 实现细节示例（以 C++ STL 为例）

在 C++ 标准库的实现中：

map 是类似 vector 的动态数组，但支持双向扩展。
- 当 map 空间不足时，会重新分配更大的内存，将旧指针复制到新 map 的中间位置，预留前后空间。
每个块（buffer）是独立分配的数组，大小通常为 512 字节 或固定元素数量。

5. 总结：何时选择 Deque？

适用场景：
- 频繁在头尾插入/删除元素（如队列或栈）。
- 需要中等频率的随机访问（优于 list，但弱于 vector）。
不适用场景：
- 需要绝对的内存连续性（如与 C 接口交互时只能用 vector）。
- 频繁在中间位置插入/删除（此时 list 或树结构更优）。

Deque 的底层设计是一种折中方案，结合了数组（块内连续）和链表（块间松散连接）的优点，同时通过动态指针数组（map）高效管理块，因此既不直接依赖 vector 也不依赖 list。

【C++】STL之deque

deque Deque 的底层既不直接依赖 vector 也不依赖 list，而是结合了两者的思想，采用了一种分块（chunk）存储与动态指针数组（map）结合的结构。以下是详细分析： 1. 底层结构设计 Deque 的核心设计…...

编程日记 2025/6/28 13:29:32

HTB - BigBang靶机记录

HTB - BigBanghttps://mp.weixin.qq.com/s/D7yR00kHdiIfoOFk_jHa9w...

编程日记 2025/5/22 9:00:55

AI时代的能力重构与终身进化

在数字技术加速迭代、职业边界日益模糊的当下，自我提升已从“阶段式学习”演变为“持续性进化”。这一转型的底层逻辑在于：个体能力需从“知识积累”转向“能力重构”，以适应AI技术重塑的社会分工与价值创造模式。本文将从认知升级、技能进化、生态构建三个维度，解析AI时代…...

编程日记 2025/6/25 18:50:02

Java—— 正则表达式方法及捕获分组

识别正则表达式的方法方法名说明public String[] matches(String regex) 判断字符串是否满足正则表达式的规则 public string replaceAll(String regex,string newstr) 按照正则表达式的规则进行替换 public string[] split(String regex) 按照正则表达式的规则切割字符串…...

编程日记 2025/6/27 2:12:47

《100天精通Python——基础篇 2025 第2天：Python解释器安装与基础语法入门》

目录一、Windows安装Python1.1 下载并安装 Python1.2 测试安装是否成功二、Linux系统安装Python(新手可以跳过)2.1 基于RockyLinux系统安装Python(编译安装)2.2 基于Ubuntu系统安装Python(编译安装)2.3 macOS 安装python解释器三、如何运行Python程序？3.1 Python…...

编程日记 2025/6/28 13:27:14

Linux平台实现低延迟的RTSP、RTMP播放

在流媒体播放器的开发过程中，RTSP（实时流协议）和RTMP（实时消息协议）是广泛应用的流媒体协议。本博客将介绍如何使用大牛直播SDK实现一个Linux平台下的RTSP/RTMP播放器。大牛直播SDK的Linux平台播放SDK，支持…...

编程日记 2025/5/6 15:03:36

安宝特案例 | AR技术在院外心脏骤停急救中的革命性应用

00 案例背景在院外心脏骤停 (OHCA) 的突发救援中，时间与效率直接决定着患者的生命。传统急救模式下，急救人员常通过视频或电话与医院医生进行沟通，以描述患者状况并依照指令行动。然而，这种信息传递方式往往因信息不完整或传递延…...

编程日记 2025/6/28 13:24:25

chili3d调试笔记9 参数化建模+ai生成立方体

mainwindow 怎么渲染boxnode https://github.com/ticket180/chili3d chili3d ai画立方体...

编程日记 2025/5/2 13:57:05

代码 #include<bits/stdc.h> using namespace std; int main(){int n,m;cin>>n>>m;string s;for(int i0;i<n;i){int x;cin>>x;schar(x0);}while(m--){int x;cin>>x;if(x1){int l1;string s1;cin>>l1;for(int i0;i<l1;i){int a;cin&…...

编程日记 2025/6/26 10:28:34

React在什么情况下需要用useReducer

在 React 中，useReducer 是一个用于管理复杂状态逻辑的 Hook。它是 useState 的替代方案，适用于状态更新逻辑复杂或状态之间相互关联的场景。什么时候需要使用 useReducer 状态更新逻辑复杂： 如果状态更新涉及多个操作或有复杂的逻辑&#x…...

编程日记 2025/6/28 13:27:12

要从给定的数据结构中提取所有的 itemList 并将其放入一个新的数组中

const data [{id:1,itemList:[{id:1-1,list:0},{id:1-2,list:0}]},{id:2,itemList:[{id:2-1,list:0}]} ]使用 forEach const newItemList [];data.forEach(item > {newItemList.push(...item.itemList); });console.log(newItemList);reduce const newItemList data.re…...

编程日记 2025/6/28 13:28:19

程序员鱼皮最新项目-----AI超级智能体教程（一）

文章目录 1.前言1.什么是AI大模型2.什么是多模态3.阿里云百炼平台介绍3.1文本调试展示3.2阿里云和dashscope的关系3.3平台智能体应用3.4工作流的创建3.5智能体编排应用 1.前言最近鱼皮大佬出了一套关于这个AI 的教程，关注鱼皮大佬很久了，鱼皮大佬确实在…...

编程日记 2025/5/3 19:30:00

17.磁珠在EMC设计中的运用

磁珠在EMC设计中的运用 1. 磁珠的高频等效特性2. 磁珠的参数分析与选型3. 磁珠应用中的隐患问题 1. 磁珠的高频等效特性和磁环类似，低频段感性jwL为主，高频段阻性R为主。 2. 磁珠的参数分析与选型不需要太在意磁珠在100MHz时的电阻值，选型…...

编程日记 2025/6/28 6:21:33

常见接口测试常见面试题（JMeter）

JMeter 是 Apache 提供的开源性能测试工具，主要用于对 Web 应用、REST API、数据库、FTP 等进行性能、负载和功能测试。它支持多种协议，如 HTTP、HTTPS、JDBC、SOAP、FTP 等。在一个线程组中，JMeter 的执行顺序通常为：配置元件…...

编程日记 2025/4/30 1:27:03

2026届华为海思秋暑期IC实习秋招笔试真题（2025.04.23更新）

今天给大家分享下华为海思2025.04.23号最新IC笔试真题。华为海思IC前端中后端(COT&XPU)岗位笔试机考题更多华为海思数字IC岗秋招实习笔试真题，可以私信小编。数字后端培训实战项目六大典型后端实现案例秒杀数字后端实现中clock gating使能端setup viola…...

编程日记 2025/6/26 1:25:01

水域陆地两相宜，便携漏电探测仪

在自然灾害如洪水、地震、台风及火灾中，建筑物和电力设施易因结构破坏、线路老化或设备浸水导致绝缘失效，引发漏电事故。漏电不仅直接威胁人员生命安全，还可能引发二次火灾或爆炸，尤其在潮湿环境下导电性增强，触电风险…...

编程日记 2025/6/26 8:03:28

论文笔记（七十九）STOMP: Stochastic Trajectory Optimization for Motion Planning

STOMP: Stochastic Trajectory Optimization for Motion Planning 文章概括摘要一、引言二、相关工作三、STOMP 算法A. 探索B. 轨迹更新四、机械臂的运动规划A. 设置B. 代价函数1）障碍物代价：2）约束代价：3）扭矩代价&a…...

编程日记 2025/6/26 10:44:18

如何应对客户提出的不合理需求

在项目执行过程中，客户经常会提出一些看似不合理的需求，这些需求可能超出了预算、时间范围，或与项目初期的目标不符。应对这些不合理需求的最佳方法是通过清晰沟通、设定合理期望、与客户共同探索解决方案来有效管理这些需求。例如&#xff0…...

编程日记 2025/6/26 1:25:34

SEO的关键词研究与优化第一章

关键词研究和优化是SEO的核心。通过深入了解目标受众使用的搜索词，我们可以优化网站内容，提高搜索引擎排名，并吸引更多相关流量。本章将详细探讨关键词研究的方法、和最佳实践。关键词类型对比分析 1. 关键词研究的基础了解不同类型的关键…...

编程日记 2025/6/27 2:12:35

A2A Agent 框架结构化分析报告

A2A Agent 框架结构化分析报告第一章绪论 1.1 引言在全球数字化转型的浪潮中，人工智能（Artificial Intelligence, AI）技术正以前所未有的速度改变着我们的生活和工作方式。然而，随着AI系统的广泛应用，单一AI系统…...

编程日记 2025/5/20 10:08:19

日语学习-日语知识点小记-构建基础-JLPT-N4阶段（10）：つもり计划/打算

日语学习-日语知识点小记-构建基础-JLPT-N4阶段（10）： つもり　计划/打算 1、前言（1）情况说明（2）工程师的信仰 2、知识点（1）つもり　计划/打算（２&a…...

编程日记 2025/5/26 23:52:23

对patch深入理解下篇：Patch+LSTM实现以及改进策略整理

我在去年11月份写了pat入理解的上篇，主要介绍patch的原理和代码实现过程。文章发布后很多朋友催更下篇，其实一直在积累素材，因为介绍完原理和实现之后，下一步肯定是要考虑如何改进。在这之前，首先，我们接着…...

编程日记 2025/4/30 7:24:06

线程同步与互斥(互斥)

目录线程互斥进程线程间的互斥相关背景概念互斥量mutex 互斥量的接⼝初始化互斥量初始化互斥量有两种⽅法销毁互斥量互斥量加锁和解锁加锁的使用互斥量实现原理探究互斥量的封装 Mutex.hpp Main.cc 线程互斥进程线程间的互斥相关背景概念临界资源&…...

编程日记 2025/6/26 14:25:28

基于RFID的智能家居系统设计与实现

标题:基于RFID的智能家居系统设计与实现内容:1.摘要随着物联网技术的飞速发展，智能家居系统成为了人们关注的焦点。本研究的目的是设计并实现一个基于RFID（射频识别）的智能家居系统，以提高家居的智能化水平和用户的生活便利性。…...

编程日记 2025/6/26 7:25:34

JAVA设计模式——（六）装饰模式（Decorator Pattern）

JAVA设计模式——（六）装饰模式（Decorator Pattern） 介绍理解实现被装饰类被装饰类的具体实现装饰类装饰类具体实现测试适用场景介绍动态给一个对象添加一些额外的功能，动态的扩展其功能。理解装饰模式&#xf…...

编程日记 2025/6/26 6:54:05

CGAL 网格等高线计算

文章目录一、简介二、实现代码三、实现效果一、简介这里等高线的计算其实很简单，使用不同高度的水平面与网格进行相交，最后获取不同高度的相交线即可。二、实现代码 #include <iostream> #include <iterator> #include <map>...

编程日记 2025/6/26 4:48:20

Sharding-JDBC 系列专题 - 第十篇：ShardingSphere 生态与未来趋势

Sharding-JDBC 系列专题 - 第十篇：ShardingSphere 生态与未来趋势本系列专题旨在帮助开发者全面掌握 Sharding-JDBC，一个轻量级的分布式数据库中间件。本篇作为系列的第十篇，也是本系列的总结篇，将全面回顾 Apache ShardingSphere 生态，包括其核心组件、功能模块和与其他…...

编程日记 2025/5/27 5:26:49

ETL 数据集成都包含哪些？

一、ETL 数据集成都包含哪些？ 数字化时代数据已成为企业最为宝贵的资产之一。然而，企业的数据往往分散在多个不同的系统和平台中，如关系型数据库、文件系统、API 等。为了将这些分散的数据整合起来，为企业决策提供全面、准确的支…...

编程日记 2025/5/3 21:01:07

windows系统自定义powshell批处理脚本

windows自定义powshell批处理脚本前几天看到大神自定义批处理骚操作操作，觉得很有意思，本篇文章记录一下入门学习笔记。 PowerShell 是一种功能强大的脚本语言和命令行外壳，基于.NET Framework，广泛应用于 Windows 系统管理、自…...

编程日记 2025/6/27 2:32:13

【计算机视觉】CV实战项目 - 基于YOLOv5与DeepSORT的智能交通监控系统：原理、实战与优化

基于YOLOv5与DeepSORT的智能交通监控系统：原理、实战与优化一、项目架构与技术解析1.1 核心算法架构1.2 学术基础二、实战环境配置2.1 硬件要求与系统配置2.2 分步安装指南三、核心功能实战3.1 基础车辆计数3.2 自定义检测类别3.3 多区域计数配置四、性能优化技…...

编程日记 2025/6/26 23:37:13

Java基础系列-HashMap源码解析3-红黑树

文章目录红黑树定义与AVL树对比插入节点插入节点是根节点插入节点的叔叔是红色插入节点的叔叔是黑色构建示例删除节点只有左子树/只有右子树只有左孩子/只有右孩子没有孩子如果双黑节点的兄弟是黑色：如果双黑节点的兄弟是红色： 总结红黑树定义与…...

编程日记 2025/6/26 21:28:41

Linux系统的延迟任务及定时任务

延迟任务的发起在系统中我们可以使用at命令来发起延迟任务 at命令执行是调用的是atd服务，即使系统最小化安装atd也会被安装到系统中 at 任务信息存放在系统中/var/spool/at目录中 at 任务的日志文件被存放到/var/log/cron中 at 任务执行时如果遇到系统处于关闭状态…...

编程日记 2025/6/27 11:51:07

【蓝桥杯】水质检测

水质检测题目描述小明需要在一条 2 n 2 \times n 2n 的河床上铺设水质检测器。在他铺设之前，河床上已经存在一些检测器。如果两个检测器上下或者左右相邻，那么这两个检测器就是互相连通的。连通具有传递性，即如果 A A A 和 B B B 连通…...

编程日记 2025/4/28 8:58:54

【晶振】晶振的工作原理及其与单片机关系

晶振（晶体振荡器）是电子设备中常见的元件，其核心功能是提供稳定的时钟信号，而单片机（MCU）依赖这一信号来同步内部操作。以下是晶振的工作原理及其与单片机关系的详细说明：一、晶振的工作原理压电效应与谐振晶振的核心是石英晶体，利用其压电效应：当在晶体两端施加电…...

编程日记 2025/6/27 12:07:57

配置 C/C++ 语言智能感知（IntelliSense）的 c_cpp_properties.json 文件内容

配置 C/C 语言智能感知（IntelliSense）的 c_cpp_properties.json 文件内容 {"configurations": [{"name": "Linux","includePath": ["${workspaceFolder}/**","/opt/ros/humble/include/**&quo…...

编程日记 2025/5/25 22:35:53

Postgresql源码（143）统计信息基础知识（带实例）

概念与总结高频值（Most Common Values, MCV） 存储在 most_common_vals 中。每个高频值的频率通过 most_common_freqs 单独记录（例如 0.010966667 等）。MCV 用于优化等值查询（如 poid 33）&…...

编程日记 2025/5/14 17:54:50

【含文档+PPT+源码】基于SpringBoot+vue的疫苗接种系统的设计与实现

项目介绍本课程演示的是一款基于SpringBootvue的疫苗接种系统的设计与实现，主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的 Java 学习者。 1.包含：项目源码、项目文档、数据库脚本、软件工具等所有资料 2.带你从零开始部署运行本套系…...

编程日记 2025/5/4 8:03:07

解决 Dart Sass 的旧 JS API 弃用警告的详细步骤和解决方案

以下是解决 Dart Sass 的旧 JS API 弃用警告的详细步骤和解决方案： 错误原因 Dart Sass 1.x 版本中使用的旧 JavaScript API（如 sass.render() 或 sass.compile() 的旧调用方式）将在 2.0.0 版本中被移除。需迁移到新 API 以避免未来报错。…...

编程日记 2025/6/26 19:11:43

Concepts (C++20)

C20 Concepts Concepts 是 C20 引入的核心特性，用于显式约束模板参数，提升代码可读性和错误提示。以下通过代码示例和原理分步骤解析其用法。 1. 基本概念目标：显式声明模板参数必须满足的条件。优势：替代复杂的 SFINAE 和 ena…...

编程日记 2025/5/20 11:14:19

CVE-2024-23897-Jenkins 2.441之前版本存在任意文件读取漏洞

1.漏洞介绍 Jenkins 2.441及更早版本，以及LTS 2.426.2及更早版本没有禁用其CLI命令解析器的一个功能，该功能会将参数中字符后跟的文件路径替换为该文件的内容，允许未经身份验证的攻击者读取Jenkins控制器文件系统上的任意文件。 2.poc利用下…...

编程日记 2025/6/27 2:25:20

利用 SSE 实现文字吐字效果：技术与实践

利用 SSE 实现文字吐字效果：技术与实践引言在现代 Web 应用开发中，实时交互功能愈发重要。例如，在线聊天、实时数据监控、游戏中的实时更新等场景，都需要服务器能够及时将数据推送给客户端。传统的请求 - 响应模式在处理实时性要求较高的场景时显得力不从心，而 Server…...

编程日记 2025/6/27 17:39:02

离线部署kubernetes

麒麟Linux服务器 AMR架构 🧰 离线部署 Kubernetes v1.25.9（麒麟系统 Docker） 一、验证Docker部署状态 ‌检查Docker服务运行状态‌ systemctl status docker 预期输出应显示 Active: active (running)，表明服务已启动‌18。 ‌…...

编程日记 2025/6/26 19:58:15

2024武汉邀请赛B.Countless Me

题目链接 #include<bits/stdc.h> using namespace std; using lllong long;int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll n; cin>>n;vector<ll>a(n1);ll res0;for(int i1;i<n;i) cin>>a[i],resa[i];ll ans0;for(int i32;i>…...

编程日记 2025/5/8 2:37:37

第53讲农学科研中的AI伦理与可解释性——探索SHAP值、LIME等可解释工具与科研可信性建设之道

目录一、为什么农学科研中需要“可解释AI”？ ✅ 场景示例：二、常见可解释AI工具介绍 1. SHAP（SHapley Additive exPlanations） 2. LIME（Local Interpretable Model-agnostic Explanations）三、AI伦理问题在农学中的体现 🧭 公平性与偏见 🔐 数据隐私 🤖…...

编程日记 2025/5/8 17:56:14

《Python3网络爬虫开发实战（第二版）》配套案例 spa6

Scrape | Moviehttps://spa6.scrape.center/ 请求影片列表api时，不仅有分页参数，还多了一个token，通过重发请求发现token有时间限制，所以得逆向token的生成代码。通过xhr断点定位到接口请求位置刷新页面或者点翻页按钮&#x…...

编程日记 2025/6/27 7:06:17

面试题：Java程序CPU 100%问题排查指南

Java程序CPU 100%问题排查指南当Java程序出现CPU使用率达到100%的情况时，通常意味着程序存在性能瓶颈或无限循环等问题。以下是系统化的排查方法和解决方案： 1. 快速定位问题线程使用top命令初步定位 top -H -p <java_pid> # 查看Java进程的所有线程CPU占用线程…...

编程日记 2025/5/2 23:09:31

YOLOv12的注意力机制革新与实时检测性能分析——基于架构优化与历史版本对比

目录一、摘要二、引言三、YOLO架构的技术演变四、YOLOv12的架构设计主干网特征提取头部特征融合和目标检测五、YOLOv12的架构创新区域注意力模块残差高效层聚合网络（R-ELAN） 其他改进和效率提升六、YOLOv12 的基准评估延迟与精度…...

编程日记 2025/6/27 16:04:32

Ollama工具调用（Tool Calls）业务应用案例

场景：电商客服自动处理退货请求业务需求：用户通过聊天界面申请退货，模型需调用外部工具验证订单状态、触发退货流程，并返回处理结果。 1. 定义工具列表在请求中声明模型可调用的工具（函数）及其参数格式…...

编程日记 2025/6/2 22:38:30

输入捕获模式测频率

前提工作： PA6、PA0通过跳线相连，PA6测试PA0的输出频率本来只有下列函数，改变占空比但是我们需要测试频率，需要动态改变频率。 void PWM_SetCompare1(uint16_t Compare) {TIM_SetCompare1(TIM2, Compare); //设置CCR1的值 }…...

编程日记 2025/5/31 8:12:52

【Vue3 实战】插槽封装与懒加载

一、为什么需要插槽？从一个面板组件说起在电商首页开发中，经常遇到这样的场景： 「新鲜好物」「人气推荐」同样类型模块都需要相同的标题栏，但内容区布局不同这时候，插槽（Slot）就像一个「内容…...

编程日记 2025/6/26 23:19:54

deque

1. 底层结构设计

2. 为什么不是 vector 或 list？

(1) 与 vector 的区别

(2) 与 list 的区别