C++_deque

2019-10-02 0 条评论 38 次阅读 0 人点赞

deque的文档

  1. deque即双端队列,双端队列是动态大小的序列式容器,其可以向两端进行伸缩。
  2. 特定的库可以以不同的方式实现deque,但通常都是一种动态数组。不论在核中情况下,它都允许通过随机访问迭代器直接访问单个元素,可以根据需要动态的伸缩。
  3. deque提供了一些与vector相似的功能,但deque在头部和尾部进行数据插入和删除操作更加高效。与vector不同的是,deque不能保证所有的元素存储在连续的空间中,在deque中通过指针加偏移的当时访问元素可能会导致非法的操作。
  4. vector与list提供了相似的接口,因此其具有类似的用途,但是内部的实现原理不同:vector使用了动态数组,该数组通常需要动态增长;deque中的元素可能分散在不同的存储块中,在deque中保存了一些必要的信息,通常用来在常数范围内直接访问deque中的任何一个元素,所以deque的内部实现比vector复杂,但是这些额外信息使得deque在某些情况下增长更加的高效,特别是在序列比较大,重新分配成本比较高的情况下。、
  5. 除频繁在头部或者尾部进行插入和删除操作外,deque比list和forward_list的性能更差。

1. deque的使用

1.1 构造函数

函数声明 接口说明
deque() 构造空的双端队列
deque(n, val = value_type()) 用n个值为val的元素构造双端队列
deque(InputIterator first, InputIterator last) 用 [first, last) 的区间构造双端队列
deque(const deque& x) 双端队列的拷贝构造函数

1.2 deque的迭代器

双端队列的底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”的假象,落在了deque的迭代器身上。

函数声明 接口说明
[begin(), end()) begin: 容器起始位置 end: 最后一个元素下一个位置
[rbegin(), rend()) 反向迭代器rbegin在end位置,rend在begin
[cbegin(), cend()) const迭代器,与begin和end位置相同,但不能修改其空间内容
[crbegin(), crend()) const反向迭代器,与crbegin在cend位置,crend在cbegin位置

1.3 deque的容器操作

函数声明 接口说明
size() 返回deque中有效元素个数
empty() 检测deque是否为空,是返回true,否则返回false
resize(sz, value) 将deque中的元素改变到sz,多出的空间用value填充

1.4 deque中修改操作

函数声明 接口说明
push_back() 和 pop_back() deque的尾插和尾删
push_front() 和 pop_front() 插入 / 删除deque头部元素
insert(pos, value) 和 erase(pos) deque任意位置插入和删除
swap() 交换两个deque中的内容
clear() 将deque中的元素清空

2. deque的应用场景

deque在序列式容器中比较鸡肋,因为如果只是简单的存储元素,使用vector即可,如果对元素任意位置进行插入或者删除操作比较多,使用list即可,所以一般很少去使用deque。deque最大的应用,就是用其作为标准库中stack和queue的底层结构。

L_KingMing

这个人太懒什么东西都没留下

文章评论(0)