std::deque底层实现

 一.概述-类分析

        每一个容器继承自己的base版本,base中储存重要的数据结构,deque主要由中控数组指针,中控数组大小以及首尾迭代器构成。这些元素放置在_Deque_impl<_Tp>类中,这个类公有继承allocator类型(实际上这样设计不好,不能说他的类型与allocator有关)。deque实际上表面是线性连续的,实质是分段的。主要通过迭代器模拟了连续容器的特点,对都是迭代器的功劳。迭代器元素如_Deque_iterator<_Tp>所示。主要保存元素分界,cur读写模拟头,以及指向中控数组的指针。

内部分布如下:

二.deque迭代器如何模拟连续空间

        deque迭代器主要通过操作符重载去模拟连续空间的特点,主要通过判断加减访问操作是否跨越缓冲区,跨越了几个缓冲区。然后通过中控数组进行缓冲区跳转,读写头重置的操作。给用户一种连续的错觉。

        语法糖:使用前置++去构造后置++,前置--去构造后置--(大家风范欸)

 三.优点

1.deque在扩容时,只拷贝中控数组指针且将元素拷贝至新的虚拟内存空间中断,头尾留冗余,相比vector开销更低。

2.相比vector可以在头尾两端高效插入。

3.相比List采用连续Buffer储存元素,页内碎片更少。

4.insert操作会判断插入位置与头尾两端的距离,选择较为近的位置移动元素,插入效率比vector高。

5.默认作为stack、queue适配器的底层容器。

相关推荐

  1. 详解Qml的底层实现

    2024-07-19 13:42:01       51 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-19 13:42:01       52 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-19 13:42:01       54 阅读
  3. 在Django里面运行非项目文件

    2024-07-19 13:42:01       45 阅读
  4. Python语言-面向对象

    2024-07-19 13:42:01       55 阅读

热门阅读

  1. oracle创建服务

    2024-07-19 13:42:01       17 阅读
  2. 音视频中文件的复用和解复用

    2024-07-19 13:42:01       18 阅读
  3. PHP 调用 JD 详情 API 接口:提升电商体验的关键

    2024-07-19 13:42:01       16 阅读
  4. 域名解析出错的解决办法

    2024-07-19 13:42:01       16 阅读
  5. 裸金属服务器

    2024-07-19 13:42:01       20 阅读
  6. [Makefile] 第四章:大型项目中的makefile

    2024-07-19 13:42:01       14 阅读
  7. 前端传值到后端,后端解析为科学计数法

    2024-07-19 13:42:01       13 阅读
  8. 2024 年 6 大 SwaggerHub 替代方案

    2024-07-19 13:42:01       13 阅读
  9. PHP 与 1688 详情 API 接口的完美对接

    2024-07-19 13:42:01       16 阅读
  10. 在状态流图中重用自定义C代码

    2024-07-19 13:42:01       12 阅读