C++ deque（1）

1.deque介绍

deque的扩容不像vector那样麻烦 直接新开一个buffer 不用重新开空间再把数据全部移过去

deque本质上是一个指针数组和vector<vector>不一样，vector<vector>本质上是一个vector对象数组！并且vector<vector>的buffer是不一样大的 而deque的每个buffer大小是固定的

指针数组满了之后直接扩容就可以了，并且代价很低基本可以忽略不记（只用拷贝指针数组的全部指针就可以了）

数据插入的时候 优先往中间插入 因为这样你尾插和头插就不用去挪动数据了！ 

2.deque和vector与list的对比

相比vector

优点：

1.极大的缓解了扩容问题，头插 头删问题

缺点

1.但是[ ]不够极致 deque要计算在哪个buffer的第几个（计算方法如下）

相比list

优点：

1.可以支持下表随机访问

2.cpu高速缓存 效率不错 

缺点：

1.头尾插入删除都不错 但是中间插入删除呢？（很拉跨）

这个时候就很麻烦

有两种方式

（1）挪动数据  代价很大不用说了（并且只能挪插入的那个buffer 不能挪其它buffer）

（2）扩容 对当前buffer扩容 但是不建议这么弄 包括库里面也不是这样实现的

这（buffer大小）会影响[]的使用（看上图）[]效率会进一步降低

3.deque的优势和不足

优势：

deque有一个最大的优势 就是非常适合高频的头插头删和尾插尾删

很适合用来适配栈和队列的默认容器

不足:

非常不适合中间插入和删除

方括号用的不多的时候可以用deque

deque的实现是非常复杂的 比vector和list复杂很多

这里只是一个简单介绍