1.deque 的简介

deque：双端队列容器
①deque 系由一块一块的固定大小的连续空间构成（块与块之间是不连续）。一旦有必要在 deque 的前端或尾端增加新的空间，便配置一块固定大小的连续空间，串接在整个 deque 的头端或尾端。

②deque 的最大任务，便是在这些分块的固定大小连续空间上，维护其整体连续的假象，并提供随机存取的接口（随机迭代器），代价则是迭代器架构较为复杂。

③deque 采用一块所谓的_M_map（注意，不是 STL 的 map 容器）作为主控。这里所谓_M_map 是一小块连续空间，其中每个元素（此处称为一个节点，node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是 deque 的储存空间主体。

④底层数据结构：动态开辟的二位数组，一维数组从2开始，以2倍的方式进行扩容，每次扩容后，原来第二维的数组从新的第一维数组的下标的oldsize/2开始存放，上下都预留相同的空行，方便支持deque的首尾元素的添加

⑤

示例：

#include<iostream>
#include<deque>
using namespace std;

template < class _Tp>
struct _Deque_iterator          //迭代器
{
	typedef _Tp** _Map_pointer;

	_Tp * _M_cur;
	_Tp * _M_first;
	_Tp * _M_last;
	_Map_pointer _M_node;
};

template < class _Tp>
class _Deque_base                //deque存储结构
{
	typedef _Deque_iterator<_Tp> iterator;
protected:
	_Tp * *_M_map;
	size_t _M_map_size;
	iterator _M_start;
	iterator _M_finish;
};

int main()
{
	std::deque<int> iqu;
	return 0;
}

2.deque的常用成员函数：

iqu[ ]：用来访问双向队列中单个的元素。
iqu.front()：返回第一个元素的引用。
iqu.back()：返回最后一个元素的引用。
iqu.push_front(x)：把元素x插入到双向队列的头部。O(1)
iqu.pop_front()：弹出双向队列的第一个元素。O(1)
iqu.push_back(x)：把元素x插入到双向队列的尾部。O(1)
iqu.pop_back()：弹出双向队列的最后一个元素。O(1)
iqu.insert(it,20),O(n)
iqu.erase(it);从it指向的位置删除元素O(n)

示例：

int main()
{
	std::deque<int> iqu;
	for (int i = 1; i <= 5; ++i)
	{
		iqu.push_back(i);
	}
	deque<int>::iterator it;
	for (it = iqu.begin();it != iqu.end();it++)
	{
		cout << *it ;
	}
	cout << endl;
	cout << iqu.front() << endl;
	cout << iqu.back() << endl;
	iqu.push_front(0);
	iqu.push_back(6);
	for (it = iqu.begin();it != iqu.end();it++)
	{
		cout << *it ;
	}
	iqu.pop_front();
	iqu.pop_back();
	cout << endl;
	for (it = iqu.begin();it != iqu.end();it++)
	{
		cout << *it;
	}
	return 0;
}

3.deque图解

①

for (int i = 1; i <= 5; ++i)
{
	iqu.push_back(i);
}

②

iqu.pop_front();

③会增加新的缓冲区

 for (int i = 6; i <= 16; ++i)
 {
     iqu.push_back(i);
 }

4.deque 与 vector 的区别

vector特点：动态数组，内存是连续的，2倍的方式进行扩容；

deque特点：动态开辟的二维数组空间，内存并不连续，第二维是独立new出来的，属于分段连续。固定长度，扩容的时候，第一维的数组进行二倍扩容

①deque 两端都能够快速插入和删除元素 O（1），vector 只在尾端进行插入和删除 O（1）。

②deque 的元素存取和迭代器操作会稍微慢一些，因为 deque 的内部结构会多一个间接过程。

③deque 中的迭代器是特殊的智能指针，而不是一般指针，它需要在不同的区块之间跳转。因为 deque 使用不止一块内存（而 vector 必须使用一块连续内存）。

④deque 不支持对容量和内存重分配时机的控制，除了首尾两端安插、删除元素外，其他地方安插、删除元素都将导致元素的 pointer、reference、iterator 失效。不过，deque 的内存重分配机制优于 vector，因为 deque 不必在内存重分配时复制所有的元素。deque 的内存区块不再被使用时，会被释放

⑤deque和list，比vector容器多出来的增加删除函数接口：
push_front和pop_front.

最后

以上就是风趣保温杯为你收集整理的c++ 之deque1.deque 的简介2.deque的常用成员函数：3.deque图解4.deque 与 vector 的区别的全部内容，希望文章能够帮你解决c++ 之deque1.deque 的简介2.deque的常用成员函数：3.deque图解4.deque 与 vector 的区别所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。