C++ deque容器

deque

deque是C++STL库中的一个容器，常用来当stack、queue的适配器。在算法领域中，适用于解决单调队列单调栈等问题。下面我们就来认识一下deque容器。

文章目录

• deque
• • 1. vector与list区别
  • 2. deque的介绍和使用
  • • 2.1 deque的介绍
    • 2.2 deque的使用
    • • 2.2.1 数据访问(**Element access**):
      • 2.2.2 增删改查(**Modifiers**):
  • 3. deque底层实现
  • • 3.1 deque底层结构
    • • 3.1.1 deque结构
      • 3.1.2 iterator(迭代器)结构
      • • 遍历方式：
    • 3.2 deque 随机访问
    • 3.3 头插尾插
    • • 3.3.1 尾插
      • 3.3.2 头插
    • 3.4 insert/erase处理
  • 4. deque的应用场景
  • • 4.1 deque的缺陷
    • 4.2 deque的应用场景

1. vector与list区别

那么有没有一种数据结构可以结合上面两者的优点设计出一种可以随机访问并且不需要经常的进行重新扩容操作，并且弥补顺序表头插头删困难数据结构。——这个数据结构就是双端队列(deque)

2. deque的介绍和使用

2.1 deque的介绍

deque的文档介绍

deque吸取了vector的随机迭代器，支持 ++ -- + - 操作，访问某个数据的效率可以达到O(1)，并且使用方便，大多数接口与vector一致

deque称之为双端队列，顾名思义就是支持两端插入删除的特殊队列，所以deque一般也是运用经常头插头删和尾插尾删的场景。

2.2 deque的使用

下面就举几个最常见，并且适合deque使用的接口(大多数和vector、list用法一致)

2.2.1 数据访问(Element access):

2.2.2 增删改查(Modifiers):

这里重点讲着四种接口主要缘由是deque一般情况就适合这四种操作(效率高，时间复杂度O(1))，当然也支持insert、erase等操作(效率极低，不推荐使用)。

3. deque底层实现

3.1 deque底层结构

3.1.1 deque结构

利用指针数组的概念将各个数组的地址存储在一个数组中，这样可以大大节约重新扩容的成本，只需要要将指针数组进行扩容然后拷贝各个指针就行了。

对指针数组的概念模糊的可以看这篇文章——深入理解指针（2）-CSDN博客

3.1.2 iterator(迭代器)结构

struct _deque_iterator
{
    T* cur;
	T* first;
 	T* last;
  	map_pointer node;
};

遍历方式：

先从begin()如图start的位置开始，然后对cur进行++后移，当 cur==last ，就将 node++ 并且first、cur、last迭代到该node上的属性，直到 cur == finish.cur

3.2 deque 随机访问

如果一个数组中存储n个数据对象

如果我们想要访问第 32 个数据，很简答的方法就是将 32 / n 就是 node的相对位置，32 % n 就是其与 该node 的first 的相对位置

3.3 头插尾插

3.3.1 尾插

尾插操作就是将end()如图finish迭代器，如果 cur == last 那就检查指针数组是否还有空间存储后插指针，如果没有进行重新扩容，然后存储数据 cur++

3.3.2 头插

头插就是尾插向前，独特的是在数组中插入数据是从 last 往 first 填(从右往左)。

3.4 insert/erase处理

insert和erase都需要大量的挪动数据，那么这里就有两种方式可以达到挪动数据的目的

1. 保持每个数组的大小相同，这就需要整个deque的数据进行挪动

   优点：随机访问效率高、遍历效率高

   缺点：挪动数据量大

2. 不需保持每个数组的大小相同，那我们就只需要对进行insert/erase位置所在的数组进行挪动(可能需要扩容)

   优点：挪动数据量相对小

   缺点：牺牲了随机访问和遍历的效率

实际上大多数编译器的源码实现都采用第一种方式。

4. deque的应用场景

4.1 deque的缺陷

优势：

1. 与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素

2. 与list比较，其底层是连续空间，空间利用率比较高，缓存利用率高，不需要存储额外字段。

3. 头插头删以及尾插尾删效率高

缺陷：

1. 不适合遍历，因为在遍历时，deque的迭代器要频繁的去检查其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list。
2. 不适合中间插入和删除
3. 虽然是随机迭代器，支持算法库中的sort，但是实际的效率却不如将其拷贝给vector再用vector进行排序，再重新拷贝会deque

4.2 deque的应用场景

1. 用来帮助某些算法的实现，如单调队列单调栈等。

2. STL用其作为stack的queue的底层数据结构

   stack是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；

   queue是一种先进先出的特殊线性数据结构，只要具有 push_back() 和 pop_front() 操作的线性结构，都可以作为queue的底层容器，比如list。

   但是STL中对stack和queue默认选择deque作为其底层容器，主要因为：

   1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
   2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要挪动大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

   结合了deque的优点，而完美的避开了其缺陷。

感谢你的支持，喜欢本文记得点赞收藏噢。