简介
deque,底层是双端队列,他要求
- 在开头或末尾插入、删除元素的时间复杂度为 O(1). 这是它和 vector 的主要区别
- 随机访问的时间复杂度为 O(1). 这是它和 list 的主要区别
deque是序列式容器
类模板
1 | template< |
成员函数
迭代器相关
- begin() - 返回指向 deque 第一个元素的迭代器
- end() - 返回指向 deque 中最后一个元素之后的理论元素的迭代器
- rbegin() - 返回指向 deque 中最后一个元素的反向迭代器(反向开始)
- rend() – 返回一个反向迭代器,指向 deque 中第一个元素之前的理论元素
- cbegin() - 返回指向 deque 中第一个元素的const迭代器 (C++11)
- cend() - 返回一个const迭代器,指向 deque 中最后一个元素之后的理论元素 (C++11)
- crbegin() – 返回指向 deque 中最后一个元素的const反向迭代器(反向开始) (C++11)
- crend() - 返回指向 deque 中第一个元素之前的理论元素的const反向迭代器 (C++11)
容量相关
- size() - 返回 deque 中元素数 O(1)
- max_size() - 返回 deque 可以容纳的最大元素数 O(1)
- resize() - 调整 deque 可存储数量
- empty() - 当前 deque 是否为空 O(1)
- shrink_to_fit() - 减少 deque 的容量,将占用内存大小减少到与size()相等 (C++11)
元素访问相关
- [g] - 返回对 deque 位置 g 处的引用 O(1)
- at(g) - 返回对 deque 位置 g 处的引用,同时进行越界检查 O(1)
- front() - 返回对 deque 中第一个元素的引用 O(1)
- back() - 返回对 deque 中最后一个元素的引用 O(1)
- data() - 返回 deque 底层数组的指针 O(1)
修改器相关
- assgin() - 用新的容器替换此容器
- clear() - 清空所有元素,size()置 0
- insert() - 插入一个或多个元素到指定位置
- erase() - 删除指定位置元素
- push_front() - 头部插入元素 O(1)
- pop_front() - 删除头部元素 O(1)
- push_back() - 尾部插入元素 O(1)
- pop_back() - 删除尾部元素 O(1)
- swap() - 交换元素
- emplace() - 插入一个元素到指定位置,调用构造函数 (C++11)
- emplace_front() - 插入一个元素到头部,调用构造函数 (C++11)
- emplace_back() - 插入一个元素到尾部,调用构造函数 (C++11)
deque迭代器详解
deque 的所有迭代器都是随机访问迭代器
1. 正向迭代器
此迭代器是由 begin(), end() 所返回的,其对其的操作为正向,且当 deque 元素不为 const 时可以更改其指向的值,即:
1 | deque<int> v{ 1,2,3,4,5,6 }; |
2. 反向迭代器
此迭代器由 rbegin(), rend() 所返回,对其的操作为反向,且也满足当 deque 元素不为 const时可以更改其指向的值,即:
1 | deque<int> v{ 1,2,3,4,5,6 }; |
3. const迭代器
此迭代器由 cbegin(), cend(), crbegin(), crend() 返回,只能对其操作,不能更改其指向的值,即:
1 | deque<int> v{ 1,2,3,4,5,6 }; |
deque的特性
- 从头部或尾部添加元素,现有元素的内存地址不会改变,因此指针和引用不失效
- 从头部或尾部添加元素,可能需要分配新的内存块, 这会使迭代器失效
- 从中间添加元素,需要移动其它元素,这会使迭代器、指针和引用失效
回到开头将deque的两个特点,是将vector可随机访问和list容易添加元素的优点,但是凡事都是有代价的,在一些从一端添加删除元素的情况下,vector的性能可能比deque要好(比如用作stack时),deque适合用作队列(queue),即一端入另一端出的情况,但具体还是应该根据实际情况而论,详情参见STL-stack
随机访问O(1)
具体而言,deque的具体实现是 map of vectors :用一个大的 map ,管理很多小的 vector ,小的 vector 里存的才是element。因此它能够实现随机访问( map 和 vector 都可以实现随机访问)
deque底层探究
下文转自deque容器底层实现原理,有所删改
前面说到,deque 的实现为 map of vectors,即 deque 存储数据的空间是一段一段等长的连续空间构成,各段空间不一定是连续的,可以位于内存的不同区域
为了管理这些不同的区域,deque 用数组(数组名假定为map)存储着各个连续空间的首地址,也就是说 map数组中存储的都是指针,指向那些真正用来存储数据的各个连续空间
通过建立map数组,deque 申请的这些分段的内存就能实现”整体连续“的效果,换句话说,当 deque 需要在头部或者尾部增加存储空间时,它会申请一段新的连续空间,同时在 map 数组的开头或结尾添加指向该空间的指针,由此该空间就串接到了 deque 容器的头部或尾部
当 map 满了会怎样?很简单,再申请一块更大的连续空间供 map 数组使用,将原有数据(很多指针)拷贝到新的 map 数组中,然后释放旧的空间
deque 容器的分段存储结构,提高了在序列两端添加或删除元素的效率,但也使该容器迭代器的底层实现变得更复杂
deque迭代器的底层实现
由于 deque 底层将序列中的元素分别存储到了不同段的连续空间中,因此要想实现迭代器的功能,必须先解决如下 2 个问题:
- 迭代器在遍历 deque 时,必须能够确认各个连续空间在 map 数组中的位置
- 迭代器在遍历某个具体的连续空间时,必须能够判断自己是否已经处于空间的边缘位置。如果是,则一旦前进或者后退,就需要跳跃到上一个或者下一个连续空间中
为了实现遍历 deque 的功能,其迭代器定义如下的结构:
1 | template<class T,...> |
四个指针的作用
- cur:指向当前正在遍历的元素
- first:指向当前连续空间的首地址
- last:指向当前连续空间的末尾地址
- node:它是一个二级指针,用于指向 map 数组中存储的指向当前连续空间的指针
借助这 4 个指针,deque 迭代器对随机访问迭代器支持的各种运算符进行了重载,能够对 deque 分段连续空间中存储的元素进行遍历,例如:
1 | //当迭代器处于当前连续空间边缘的位置时,如果继续遍历,就需要跳跃到其它的连续空间中,该函数可用来实现此功能 |
deque容器的底层实现
了解了 deque 容器底层存储序列的结构,以及 deque 容器迭代器的内部结构之后,接下来看看 deque 容器究竟是如何实现的
deque 容器除了维护先前讲过的 map 数组,还需要维护 start、finish 这 2 个 deque 迭代器,以下为 deque 容器的定义:
1 | //_Alloc为内存分配器 |
其中,start 迭代器记录着 map 数组中首个连续空间的信息,finish 迭代器记录着 map 数组中最后一个连续空间的信息
另外需要注意的是,和普通 deque 迭代器不同,start 迭代器中的 cur 指针指向的是连续空间中首个元素,而 finish 迭代器中的 cur 指针指向的是连续空间最后一个元素的下一个位置
借助 start 和 finsh,以及 deque 迭代器中重载的诸多运算符,就可以实现 deque 容器提供的大部分成员函数,比如:
1 | //begin() 成员函数 |
我查看vs库中实现与此方法不同,但思路基本相同