1、deque容器的基本概念
Vector容器是單向開口的連續(xù)內(nèi)存空間，deque則是一種雙向開口的連續(xù)線性空間，又稱雙端動(dòng)態(tài)數(shù)組。所謂的雙向開口，意思是可以在頭尾兩端分別做元素的插入和刪除操作，當(dāng)然，vector容器也可以在頭尾兩端插入元素，但是在其頭部操作效率奇差，無法被接受。
2、與vector區(qū)別不同
Deque容器和vector容器最大的差異。
一在于deque允許使用常數(shù)項(xiàng)時(shí)間對頭端進(jìn)行元素的插入和刪除 操作。
二在于deque沒有容量的概念，因?yàn)樗莿?dòng)態(tài)的以分段連續(xù)空間組合而成，隨時(shí)可以增加一段新的空間并鏈接起來，換句話說，像vector那樣，”舊空間不足而重新配置一塊更大空間，然后復(fù)制元素，再釋放舊空間”這樣的事情在deque身上是不會(huì)發(fā)生的。也因此，deque沒有必須要提供所謂的空間保留(reserve)功能. 雖然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指針， 其復(fù)雜度和vector不是一個(gè)量級(jí)，這當(dāng)然影響各個(gè)運(yùn)算的層面。
因此，除非有必要，我們應(yīng)該盡可能的 使用vector，而不是deque。對deque進(jìn)行的排序操作，為了最高效率，可將deque先完整的復(fù)制到一個(gè)vector中，對vector容器進(jìn)行排序，再復(fù)制回deque。
3、deque容器的實(shí)現(xiàn)原理
Deque容器是連續(xù)的空間，至少邏輯上看來如此，連續(xù)現(xiàn)行空間總是令我們聯(lián)想到array和vector,array 無法成長，vector雖可成長，卻只能向尾端成長，而且其成長其實(shí)是一個(gè)假象，事實(shí)上(1) 申請更大空間 (2)原數(shù)據(jù)復(fù)制新空間 (3)釋放原空間 三步驟，如果不是vector每次配置新的空間時(shí)都留有余裕，其成長假象所帶來的代價(jià)是非常昂貴的。 Deque是由一段一段的定量的連續(xù)空間構(gòu)成。一旦有必要在deque前端或者尾端增加新的空間，便配置一段連續(xù)定量的空間，串接在deque的頭端或者尾端。Deque最大的工作就是維護(hù)這些分段連續(xù)的內(nèi)存空間的整體性的假象，并提供隨機(jī)存取的接口，避開了重新配置空間，復(fù)制，釋放的輪回，代價(jià)就是復(fù)雜的迭代器架構(gòu)。 既然deque是分段連續(xù)內(nèi)存空間，那么就必須有中央控制，維持整體連續(xù)的假象，數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)及迭代器的前進(jìn)后退操作頗為繁瑣。Deque代碼的實(shí)現(xiàn)遠(yuǎn)比vector或list都多得多。 Deque采取一塊所謂的map(注意，不是STL的map容器)作為主控，這里所謂的map是一小塊連續(xù)的內(nèi)存空間，其中每一個(gè)元素(此處成為一個(gè)結(jié)點(diǎn))都是一個(gè)指針，指向另一段連續(xù)性內(nèi)存空間，稱作緩沖區(qū)。緩沖區(qū)才是deque的存儲(chǔ)空間的主體。
4、deque容器常用API
4.1deque構(gòu)造函數(shù)
deque<T> deqT;//默認(rèn)構(gòu)造形式 deque(beg, end);//構(gòu)造函數(shù)將[beg, end)區(qū)間中的元素拷貝給本身。 deque(n, elem);//構(gòu)造函數(shù)將n個(gè)elem拷貝給本身。 deque(const deque &deq);//拷貝構(gòu)造函數(shù)
4.2deque賦值操作
assign(beg, end);//將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。 assign(n, elem);//將n個(gè)elem拷貝賦值給本身。
deque& operator=(const deque &deq); //重載等號(hào)操作符 swap(deq);// 將deq與本身的元素互換
案例：
#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<deque>
using namespace std;void printDequeInt(deque<int> &d)
{
deque<int>::iterator it = d.begin();
for(;it!=d.end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;}
void test01(){
deque<int> d1(5,100);
printDequeInt(d1);
deque<int> d2;
d2.assign(d1.begin(), d1.begin()+2);
printDequeInt(d2);
deque<int> d3(5,10);
printDequeInt(d1);
printDequeInt(d3);
d1.swap(d3);
printDequeInt(d1);
printDequeInt(d3);}int main(){
test01() ;
return EXIT_SUCCESS;}
4.3deque大小操作
deque.size();//返回容器中元素的個(gè)數(shù)
deque.empty();//判斷容器是否為空
deque.resize(num);//重新指定容器的長度為num,若容器變長，則以默認(rèn)值填充新位置。如果容器變 短，則末尾超出容器長度的元素被刪除。
deque.resize(num, elem); //重新指定容器的長度為num,若容器變長，則以elem值填充新位置,如果 容器變短，則末尾超出容器長度的元素被刪除
4.4deque雙端插入和刪除操作
push_back(elem);//在容器尾部添加一個(gè)數(shù)據(jù) push_front(elem);//在容器頭部插入一個(gè)數(shù)據(jù) pop_back();//刪除容器最后一個(gè)數(shù)據(jù) pop_front();//刪除容器第一個(gè)數(shù)據(jù)
案例：
#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<deque>
using namespace std;void printDequeInt(deque<int> &d)
{
deque<int>::iterator it = d.begin();
for(;it!=d.end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;}
void test01(){
deque<int> d1;
d1.push_back(10);
d1.push_back(20);
d1.push_back(30);
d1.push_front(40);
d1.push_front(50);
d1.push_front(60);
printDequeInt(d1);
//尾部刪除
d1.pop_back();
printDequeInt(d1);//60 50 40 10 20
d1.pop_front();
printDequeInt(d1);//50 40 10 20
cout<<d1[2]<<endl;//10
cout<<d1.at(2)<<endl;//10
d1.insert(d1.begin()+2, 3, 100);
printDequeInt(d1);//50 40 100 100 100 10 20
d1.erase(d1.begin()+2, d1.begin()+5);
printDequeInt(d1);//50 40 10 20
}int main(){
test01() ;
return EXIT_SUCCESS;}
4.5deque數(shù)據(jù)存取
at(idx);//返回索引idx所指的數(shù)據(jù)，如果idx越界，拋出out_of_range。 operator[];//返回索引idx所指的數(shù)據(jù)，如果idx越界，不拋出異常，直接出錯(cuò)。 front();//返回第一個(gè)數(shù)據(jù)。back();//返回最后一個(gè)數(shù)據(jù)。
4.6deque插入操作
insert(pos,elem);//在pos位置插入一個(gè)elem元素的拷貝，返回新數(shù)據(jù)的位置。 insert(pos,n,elem);//在pos位置插入n個(gè)elem數(shù)據(jù)，無返回值。 insert(pos,beg,end);//在pos位置插入[beg,end)區(qū)間的數(shù)據(jù)，無返回值。
4.7deque刪除操作
clear();//移除容器的所有數(shù)據(jù) erase(beg,end);//刪除[beg,end)區(qū)間的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置。 erase(pos);//刪除pos位置的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置。
5、deque容器使用案例
有5名選手：選手ABCDE，10個(gè)評(píng)委分別對每一名選手打分，去除最高分，去除評(píng)委中最低分，取平均分。 1. 創(chuàng)建五名選手，放到vector中 2. 遍歷vector容器，取出來每一個(gè)選手，執(zhí)行for循環(huán)，可以把10個(gè)評(píng)分打分存到deque容器中 3. sort算法對deque容器中分?jǐn)?shù)排序，pop_back pop_front去除最高和最低分 4. deque容器遍歷一遍，累加分?jǐn)?shù)，累加分?jǐn)?shù)/d.size() 5. person.score = 平均分
#include <iostream>#include <string>#include <vector>#include <deque>#include <stdlib.h>//srand rand#include <time.h>//time#include <algorithm>//sortusing namespace std;
class Person
{
private:
string name;
int score;
public:
Person(){}
Person(string name, int score)
{
this‐>name = name;
this‐>score = score;
}
void showPerson(void)
{
cout<<"姓名:"<<name<<", 分?jǐn)?shù):"<<score<<endl;
}
void setScore(int score)
{
this‐>score = score;
}
};
void ceatePlayer(vector<Person> &v)
{
int i=0;
string tmp="ABCDE";
for(i=0;i<5;i++)
{
string name="選手";
name += tmp[i];
v.push_back(Person(name, 0));
}
}
void printVectorPerson(vector<Person> &v)
{
vector<Person>::iterator it=v.begin();
for(;it!=v.end();it++)
{
(*it).showPerson();
}
}
void playGame(vector<Person> &v)
{
//設(shè)置隨機(jī)數(shù)種子
srand(time(NULL));
vector<Person>::iterator it=v.begin();
for(; it!=v.end();it++)
{
//*it代表的就是每位選手
//定義一個(gè)deque容器存放評(píng)委的分?jǐn)?shù)
deque<int> d;
int i=0;
for(i=0;i<10;i++)
{
int score = 0;
score = rand()%41+60;//60~100
//將評(píng)委的分?jǐn)?shù)放入 d容器中
d.push_back(score);
}
//對容器排序(默認(rèn)從小‐‐‐>大排序)
sort(d.begin(), d.end());
//去掉一個(gè)最高分
d.pop_back();
//去掉一個(gè)最低分
d.pop_front();
//求總分?jǐn)?shù)
int sum = accumulate(d.begin(), d.end(), 0);
//求平均成績
int avg = sum/d.size();
//將平均成績賦值給選手
(*it).setScore(avg);
}
}
int main(int argc, char *argv[])
{
vector<Person> v;
//創(chuàng)建5名選手
ceatePlayer(v);
//遍歷容器
printVectorPerson(v);
//參加比賽
playGame(v);
cout<<"------------"<<endl;
//遍歷容器
printVectorPerson(v);
return 0;
}
更多關(guān)于物聯(lián)網(wǎng)培訓(xùn)的問題，歡迎咨詢千鋒教育在線名師，如果想要了解我們的師資、課程、項(xiàng)目實(shí)操的話可以點(diǎn)擊咨詢課程顧問，獲取試聽資格來試聽我們的課程，在線零距離接觸千鋒教育大咖名師，讓你輕松從入門到精通。
京公網(wǎng)安備 11010802030320號(hào)