Deuqe概念

容器deque和vector非常相似，屬于序列式容器。都是采用動態數組來管理元素，提供隨機存取，并且有著和vector一樣的接口。不同的是deque具有首尾兩端進行快速插入、刪除的能力。

Deque結構

如圖1是deque的邏輯結構，從表面上看，deque具有連續性的存儲空間，并支持隨機存取功能。實際上deque并不是我們所看到的樣子，其內部結構，如圖2所示。
deque在實現上主要有以下兩點：

1.由一段一段的定量連續空間構成，第一個區塊朝某個方向擴展，最后一個區塊朝相反方向擴展；
2.管理這些分段的定量連續空間，維護其整體連續的假象，并提供隨機存取的接口；

圖 1 deque的邏輯結構


圖 2 deque的內部結構

Deque的能力

與vector相比，deque功能上的不同之處在于：

首尾兩端都能快速的安插、刪除元素，因此需要在兩端安插、刪除元素時，最好采用deque。存在元素時，deque的內部結構會多一個間接過程，操作元素的效率會比vector低一些。迭代器需要在不同區塊間跳轉，所以必須是特殊的智能指針，非一般指針。deque不支持對容量和內存重分配時機的控制，除了首尾兩端安插、刪除元素外，其他地方安插、刪除元素都將導致元素的pointer、reference、iterator失效。不過，deque的內存重分配機制優于vector，因為deque不必在內存重分配時復制所有的元素。deque的內存區塊不再被使用時，會被釋放。

deque的操作函數：

Deque的操作函數和vector操作函數基本一模一樣，操作函數列表見STL之vector函數詳解
duque的各項操作只有以下幾點和vector不同：

deque不提供容量操作( capacity()、reserve() )deque提供push_front()、pop_front()函數直接操作頭部

Deque的特點：

從deque的內部結構可知，deque元素是分布在一段段連續空間上，因此deque具有如下特點：

1、支持隨機訪問，即支持[]以及at()，但是性能沒有vector好。

2、可以在內部進行插入和刪除操作，但性能不及list。

由于deque在性能上并不是最高效的，有時候對deque元素進行排序，更高效的做法是，將deque的元素移到到vector再進行排序，然后在移到回來。

舉例

我們操作deque時，不需要關心其內部結構的實現，我們按照deque的邏輯結構進行操作，可以認為deque是動態的一維數組，可在首尾進行插入、刪除操作，下標從0開始。

#include "stdafx.h"
#include <deque>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

void DequeExample()
{
	deque<string> strDeq;//空隊列
	strDeq.assign(3, string("string"));//賦值

	//打印deque的內容
	for (unsigned i = 0; i < strDeq.size(); i++)
	{
		cout << "strDeq[" << i << "] :"  << strDeq[i] << endl;
	}
	
	cout << "push_front and push_back elem to deque" << endl;
	
	//首尾插入元素
	strDeq.push_front("first string");
	strDeq.push_back("last string");

	//打印deque的內容
	for (unsigned i = 0; i < strDeq.size(); i++)
	{
		cout << "strDeq[" << i << "] :" << strDeq[i] << endl;
	}

	cout << "pop_front and pop_back elem from deque" << endl;
	
	//首尾彈出元素
	strDeq.pop_front();
	strDeq.pop_back();

	//打印deque的內容
	for (unsigned i = 0; i < strDeq.size(); i++)
	{
		cout << "strDeq[" << i << "] :"  << strDeq[i] << endl;
	}
}

運行結果

參考文章：
1.http://blog.csdn.net/xiajun07061225/article/details/7442816

2.http://blog.csdn.net/hackbuteer1/article/details/7729451

總結

以上是生活随笔為你收集整理的STL之deque详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。