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

31、map deque list的实现原理【中高频】

文章目录

      • list:双向链表,适用于频繁在中间 插入和删除操作。在链表中,每个元素都有 指向前后元素的指针,所以 在任何位置进行插入和删除都非常高效。
      • deque:双端队列,可以在头部和尾部 快速插入和删除,适合 在头尾 都需要频繁增删数据的场景
      • map:键值对容器,类似于字典,它也是通过红黑树实现的,因此也是有序存储。适合需要快速查找键值对的场景,比如存储用户信息或用于配置文件读取等

list:双向链表,适用于频繁在中间 插入和删除操作。在链表中,每个元素都有 指向前后元素的指针,所以 在任何位置进行插入和删除都非常高效。

  • 高效插入和删除:在链表中的插入和删除时间复杂度为 (O(1)),不需要像 vector 一样移动其他元素。

  • 访问效率低:由于链表没有连续存储,不能通过索引直接访问某个元素。所以 必须从头或尾遍历,因此访问的效率低。

    在这里插入图片描述

deque:双端队列,可以在头部和尾部 快速插入和删除,适合 在头尾 都需要频繁增删数据的场景

  • 高效双端操作:无论是头部还是尾部插入/删除,时间复杂度均为 (O(1))。

  • 支持随机访问:deque 支持通过索引 直接访问元素,但它的底层存储结构并非一个连续的内存块,而是一个存储指针的数组,里面的每个元素都是指针,指向了内存中的小块连续的内存空间。这个指针数组从中间位置开始存储指针,留下首尾两端,从而便于扩容。
    在这里插入图片描述

    在这里插入图片描述

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq = {1, 2, 3};
    dq.push_front(0);  // 在头部添加元素 0
    dq.push_back(4);   // 在尾部添加元素 4

    // 遍历并输出元素
    for (int val : dq) {
        std::cout << val << " ";
    } // 输出 0 1 2 3 4
    return 0;
}

map:键值对容器,类似于字典,它也是通过红黑树实现的,因此也是有序存储。适合需要快速查找键值对的场景,比如存储用户信息或用于配置文件读取等

  • 有序存储:键值对按照键的顺序存储(所以map不能修改key的值,但可以修改value的值)

  • 键唯一:每个键都是唯一的(如果想保存多个相同的键,可以用multimap)

  • 查找高效:map 的查找、插入和删除操作的时间复杂度为 O(log n)。

    在这里插入图片描述

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m = {{1, "one"}, {2, "two"}};
    m[3] = "three";  // 插入键值对 (3, "three")

    // 遍历并输出键值对
    for (auto& [key, value] : m) {
        std::cout << key << ": " << value << std::endl;
    }
    return 0;
}

原文地址:https://blog.csdn.net/2402_84438596/article/details/146266805
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/586024.html

相关文章:

  • AdaLoRA 参数 配置:CAUSAL_LM“ 表示因果语言模型任务
  • 【数据库】10分钟学会MySQL的增删改查:数据库、表、表记录操作指南
  • 分布式IO模块:架起城轨交通物理层与控制层的信息桥梁
  • WHQL微软驱动签名认证,让企业驱动在Windows系统畅通无阻
  • TPCTF2025 -Web Writeup
  • 10.3 kubelet 中的cgroupManager解析和节点qos顶级目录创建
  • S_on@atwk的意思
  • 差分专题练习 ——基于罗勇军老师的《蓝桥杯算法入门C/C++》
  • STM32---FreeRTOS消息队列
  • 16 | 实现简洁架构的 Store 层
  • Element Ui - 编辑时表单校验信息未清空问题处理
  • 作物移栽机器人的结构设计的介绍
  • Web后端开发之Maven
  • 2025年AI搜索引擎开源项目全景指南:从核心框架到生态工具
  • ARM64 架构地址空间分配深度解析
  • 79. 单词搜索:题解
  • sap关账+策略模式(避免大量if elseif)
  • SpringBoot注解驱动CRUD工具:spring-avue-plus
  • BOE(京东方)携手微博举办“微博影像年”年度影像大展 创新科技赋能专业影像惊艳呈现
  • 芯谷D8563TS:低功耗CMOS实时时钟/日历电路的优选方案