目錄

STL基本概念

STL六大組件

STL的優(yōu)點(diǎn)

STL三大組件

容器

算法

迭代器

普通的迭代器訪問vector容器元素

算法for_each實(shí)現(xiàn)循環(huán)

迭代器指向的元素類型是自定義數(shù)據(jù)類型

迭代器指向容器

常用容器

string容器

string的基本概念

string容器的操作

string的構(gòu)造函數(shù)

string基本賦值操作

string的存取字符串操作

string拼接操作

string的查找與替換

string比較操作

string子串

string插入和刪除操作

string對(duì)象的類型轉(zhuǎn)換

vector容器

vector容器基本概念

vector的數(shù)據(jù)結(jié)構(gòu)

vector的構(gòu)造函數(shù)

vector常用賦值操作

vector大小操作

vector容器數(shù)據(jù)存儲(chǔ)操作

vector容器的插入和刪除

利用swap收縮空間

deque容器

deque容器基本概念

deque容器的實(shí)現(xiàn)原理

deque的api—構(gòu)造函數(shù)

deque的aip—賦值操作

deque的api—容器的大小操作

deque的api—雙端的插入和刪除

deque的api—數(shù)據(jù)存儲(chǔ)

deque的api—插入操作

deque的api—?jiǎng)h除操作

---

STL基本概念

STL(Standard Template Library，標(biāo)準(zhǔn)模板庫(kù))，是惠普實(shí)驗(yàn)室開發(fā)的一系列軟件的統(tǒng)
稱?，F(xiàn)在主要出現(xiàn)在c++中，但是在引入c++之前該技術(shù)已經(jīng)存在很長(zhǎng)時(shí)間了。
STL從廣義上分為：容器(container)算法(algorithm)迭代器(iterator)，容器和算法之間通過迭代器進(jìn)行無縫連接。STL 幾乎所有的代碼都采用了模板類或者模板函數(shù)，這相比傳統(tǒng)的由函數(shù)和類組成的庫(kù)來說提供了更好的代碼重用機(jī)會(huì)。STL(Standard Template Library)標(biāo)準(zhǔn)模板庫(kù)，在我們c++標(biāo)準(zhǔn)程序庫(kù)中隸屬于STL的占到了80%以上。

STL六大組件

容器：保存數(shù)據(jù)的空間結(jié)構(gòu)，如vector、list、deque、set、map等

算法：特定的的求解步驟，如sort、find、copy、for_each。

迭代器：本質(zhì)是一個(gè)指針

仿函數(shù)：函數(shù)對(duì)象，重載了operator()的類

適配器：一種用來修飾容器或者仿函數(shù)或迭代器接口的東西。

空間配置器：負(fù)責(zé)內(nèi)存空間的申請(qǐng) 釋放 管理等

STL的優(yōu)點(diǎn)

STL 具有高可重用性，高性能，高移植性，跨平臺(tái)的優(yōu)點(diǎn)。
高可重用性：STL中幾乎所有的代碼都采用了模板類和模版函數(shù)的方式實(shí)現(xiàn)，這相比于傳統(tǒng)的由函數(shù)和類組成的庫(kù)來說提供了更好的代碼重用機(jī)會(huì)。
高性能：如map 可以高效地從十萬條記錄里面查找出指定的記錄，因?yàn)閙ap 是采用紅黑樹的變體實(shí)現(xiàn)的。

STL三大組件

容器

保存數(shù)據(jù)的(數(shù)據(jù)結(jié)構(gòu))

常用的數(shù)據(jù)結(jié)構(gòu)：數(shù)組(array)，鏈表(list)，tree(樹)，棧(stack)，隊(duì)列(queue)，集合(set)，映射表(map)，根據(jù)數(shù)據(jù)在容器中的排列特性，這些數(shù)據(jù)分為序列式容器和關(guān)聯(lián)式容器兩種。
序列式容器強(qiáng)調(diào)值的排序，序列式容器中的每個(gè)元素均有固定的位置，除非用刪除或插入的操作改變這個(gè)位置。Vector容器、Deque容器、List容器等。
關(guān)聯(lián)式容器是非線性的樹結(jié)構(gòu)，更準(zhǔn)確的說是二叉樹結(jié)構(gòu)。各元素之間沒有嚴(yán)格的物理上的順序關(guān)系，也就是說元素在容器中并沒有保存元素置入容器時(shí)的邏輯順序。關(guān)聯(lián)式容器另一個(gè)顯著特點(diǎn)是：在值中選擇一個(gè)值作為關(guān)鍵字key，這個(gè)關(guān)鍵字對(duì)值起到索引的作用，方便查找。Set/multiset 容器 Map/multimap容器

算法

以有限的步驟，解決邏輯或數(shù)學(xué)上的問題，這一門學(xué)科我們叫做算法(Algorithms).
廣義而言，我們所編寫的每個(gè)程序都是一個(gè)算法，其中的每個(gè)函數(shù)也都是一個(gè)算法，畢竟它們都是用來解決或大或小的邏輯問題或數(shù)學(xué)問題。STL收錄的算法經(jīng)過了數(shù)學(xué)上的效能分析與證明，是極具復(fù)用價(jià)值的，包括常用的排序，查找等等。特定的算法往往搭配特定的數(shù)據(jù)結(jié)構(gòu)，算法與數(shù)據(jù)結(jié)構(gòu)相輔相成。
算法分為：質(zhì)變算法和非質(zhì)變算法。質(zhì)變算法：指運(yùn)算過程中會(huì)改變?cè)搮^(qū)間內(nèi)的元素的內(nèi)容，如拷貝替換刪除等。非質(zhì)變算法：是指運(yùn)算過程中不會(huì)改變?cè)搮^(qū)間內(nèi)的元素的內(nèi)容，如查找遍歷計(jì)數(shù)等。

迭代器

普通的迭代器訪問vector容器元素

#include <iostream>
#include <string.h>
#include <iterator>
#include <vector>
using namespace std;void test01()
{vector<int> v;v.push_back(2);v.push_back(5);v.push_back(4);v.push_back(7);//若需要訪問容器內(nèi)的元素 需要拿到容器首元素的迭代器(指針)vector<int>::iterator it_s = v.begin();vector<int>::iterator it_e = v.end();for(;it_s != it_e;it_s++){cout << *it_s<< " ";}cout << endl;}int main()
{test01();return 0;
}

算法for_each實(shí)現(xiàn)循環(huán)

void printf(int a)
{cout<< a << endl;
}
void test01()
{vector<int> v;v.push_back(2);v.push_back(5);v.push_back(4);v.push_back(7);//若需要訪問容器內(nèi)的元素 需要拿到容器首元素的迭代器(指針)vector<int>::iterator it_s = v.begin();vector<int>::iterator it_e = v.end();/*for(;it_s != it_e;it_s++){cout << *it_s<< " ";}*/cout << endl;for_each(it_s,it_e,printf);//頭地址 尾地址 回調(diào)函數(shù)}

迭代器指向的元素類型是自定義數(shù)據(jù)類型

#include <iostream>
#include <string.h>
#include <iterator>
#include <vector>
using namespace std;class person
{
public:person(int age){this->age = age;}int age;};
void printf(person &p)
{cout << p.age << endl;
}
void test01()
{person p1(1);person p2(2);person p3(3);person p4(4);vector<person> v;v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);vector<person>::iterator it_s = v.begin();vector<person>::iterator it_e = v.end();for(;it_s != it_e;it_s++){//對(duì)容器取* 得到的是<>里的類型printf(*it_s);}cout << endl;
}

迭代器指向容器

#include <iostream>
#include <string.h>
#include <iterator>
#include <vector>
using namespace std;void test01()
{vector< vector<int> > v;//數(shù)據(jù)類型為容器的容器vector<int> v1;vector<int> v2;vector<int> v3;for(int i = 0;i<3;i++){v1.push_back(i);//小容器v1尾部插入 0 1 2v2.push_back(i+10);//v2尾部插入 10 11 12v3.push_back(i+100);//v3尾部插入 100 101 102}//小容器插入大容器v.push_back(v1);v.push_back(v2);	v.push_back(v3);vector<vector<int>>::iterator it = v.begin();//大容器頭地址for(;it!=v.end();it++ ){//*it得到的是<vector<int>>vector<int>::iterator it1 = (*it).begin();//小容器頭vector<int>::iterator it2 = (*it).end();//尾for(;it1!=it2;it1++){cout<< *it1 << endl;}}}int main()
{test01();return 0;
}

常用容器

string容器

string的基本概念

string容器是一個(gè)類 容器中有一個(gè)指針 指針維護(hù)了一個(gè)數(shù)組

string容器提供了copy find insert replace等功能

string容器的操作

string的構(gòu)造函數(shù)

????????string();//創(chuàng)建一個(gè)空的字符串 例如： string str;
????????string(const string& str);//使用一個(gè)string對(duì)象初始化另一個(gè)string對(duì)象
????????string(const char* s);//使用字符串s初始化
????????string(int n, char c);//使用n個(gè)字符c初始化v

#include <iostream>
#include <string.h>
#include <iterator>
#include <vector>
#include <string>
using namespace std;void test01()
{string str;string str1("hello");string str2(str1);string str3(5,'k');cout << str1 << endl;cout << str2 << endl;cout << str3 << endl;
}int main()
{test01();return 0;
}

編譯運(yùn)行

string基本賦值操作

string& operator=(const char* s);//char*類型字符串 賦值給當(dāng)前的字符串
string& operator=(const string &s)；//把字符串s 賦給當(dāng)前的字符串
string& operator=(char c);//字符賦值給當(dāng)前的字符串
string& assign(const char *s)；//把字符串s 賦給當(dāng)前的字符串
string& assign(const char *s, int n)；//把字符串s的前n個(gè)字符賦給當(dāng) 當(dāng)前的字符串string& assign(const string &s)；//把字符串s 賦給當(dāng)前字符串
string&assign(int n, char c)；//用n個(gè)字符c 賦給當(dāng)前字符串
string& assign(const string &s, int start, int n)；//將s從start 開始n個(gè)字符賦值給字符4

#include <iostream>
#include <string.h>
#include <iterator>
#include <vector>
#include <string>
using namespace std;void test01()
{string str("helloworld");string str1("heihei");str = str1;str = "hehe";str = 'c';str.assign(str1);str.assign("jack");str.assign("jack",2);	cout << str << endl;str.assign(5,'c');cout << str << endl;	str.assign(str1,2,3);cout << str << endl;
}int main()
{test01();return 0;
}

編譯運(yùn)行

string的存取字符串操作

char& operator[](int n);//通過[]方式取字符串

char& at(int n);//通過at方法獲取字符

#include <iostream>
#include <string.h>
#include <iterator>
#include <vector>
#include <string>
using namespace std;void test01()
{string str("helloworld");cout << str[4] << endl;//輸出ostr[4] = 'c';cout << str.at(4)<< endl;//輸出c
}int main()
{test01();return 0;
}

string拼接操作

string& operator+=(const string& str)；//重載+=操作符

string& operator+=(const char* str)；//重載+=操作符

string& operator+=(const char c)；//重載+=操作符

string& append(const char *s)；//把字符串s連接到當(dāng)前字符串結(jié)尾

string& append(const char *s, int n)；//把字符串s的前n個(gè)字符連接到當(dāng)前字符串結(jié)尾

string& append(const string &s);//同operator+=()

string& append(const string &s,int pos,int n)//把字符串s中從pos開始的n個(gè)字符連接到當(dāng)前字符串尾

string& append(int n,char c);//在當(dāng)前字符串結(jié)尾添加n個(gè)字符c

#include <iostream>
#include <string.h>
#include <iterator>
#include <vector>
#include <string>
using namespace std;void test01()
{string str1("helloworld");cout << str1 << endl;string str2("123456789");str1 += str2;cout << str1 << endl;str1 += "hehe";cout << str1 << endl;str1 += 'c';cout << str1 << endl;str1.append("hehe");cout << str1 << endl;str1.append("hehe",2);cout << str1 << endl;str1.append(str2,2,3);cout << str1 << endl;
}int main()
{test01();return 0;
}

編譯運(yùn)行

string的查找與替換

int find(const string& str, int pos =0) const；//查找str第一次出現(xiàn)位置，從pos開始查找

int find(const char* s, int pos =0) const; //查找s第一次出現(xiàn)位置，從pos開始查找

int find(const char* s, int pos, int n) const；//從pos 位置查找s的前n個(gè)字符第一次位置

int find(const char c, int pos = 0) const; //查找字符c第一次出現(xiàn)位置

int rfind(const string& str, int pos = npos) const；//查找str最后一次位置，從pos開始查找

int rfind(const char* s, int pos = npos) const；//查找s最后一次出現(xiàn)位置，從pos開始查找

int rfind(const char* s, int pos, int n) const；//從pos 查找s的前n個(gè)字符最后一次位置

int rfind(const char c, int pos =0) const；//查找字符c最后一次出現(xiàn)位置

string& replace(int pos, int n, const string& str)；//替換從pos開始n個(gè)字符為字符串

strstring& replace(int pos, int n, const char* s)；//替換從pos開始的n個(gè)字符為字符串s

#include <iostream>
#include <string.h>
#include <iterator>
#include <vector>
#include <string>
using namespace std;void test01()
{string str1("helloworld");string str2("wor");cout << str1.find(str2)<< endl;cout << str1.find("wor")<< endl;cout << str1.find("world",0,2)<< endl;cout << str1.find('o')<< endl;cout << str1.rfind("rl")<< endl;//rfind 從右往左查str1.replace(2,4,str2);cout << str1 << endl;
}int main()
{test01();return 0;
}

編譯運(yùn)行

string比較操作

compare函數(shù)在>時(shí)返回1，<時(shí)返回-1，==時(shí)返回0

比較區(qū)分大小寫，比較時(shí)參考字典順序，排前面的小 大寫的A比小寫的a小

int compare(const string &s) const;//與字符串s比較

int compare(const char *s) const;//與字符串s比較

void test01()
{
?? ?string str1("helo");
?? ?string str2("world");
?? ?cout << str1.compare(str2) << endl;//輸出-1
}

string子串

string substr(int pos = 0,int n = npos);//返回由pos開始的n個(gè)字符組成的字符串

void test01()
{
? ? string str1("heloworld");
? ? cout << str1.substr(4,3) << endl;//輸出wor
}

string插入和刪除操作

string& insert(int pos, const char* s);//插入字符串

string& insert(int pos, conststring& str);//插入字符串

string& insert(int pos,int n,char c);//在指定位置插入n個(gè)字符串c

string& erase(int pos. int n,char c);//指定位直插入n個(gè)字符c

string& erase(int pos, int n =npos);//刪除從Pos開始的n

#include <iostream>
#include <string.h>
#include <iterator>
#include <vector>
#include <string>
using namespace std;void test01()
{string str1("helloworld");str1.insert(2,"kk");cout << str1 << endl;string str2("helloworld");string str("hello");str2.insert(2,str);cout << str2 << endl;string str3("helloworld");str3.insert(2,10,'r');cout << str3 << endl;string str4("helloworld");str4.erase(3,3);cout << str4 << endl;
}int main()
{test01();return 0;
}

編譯運(yùn)行

string對(duì)象的類型轉(zhuǎn)換

//string 轉(zhuǎn) char*
string str= "itcast";
const char* cstr =str.c_str();
//char* 轉(zhuǎn) string
char*s ="itcast";
string str(s);
在c++中存在一個(gè)從const char到string的隱式類型轉(zhuǎn)換，卻不存在從一個(gè)string對(duì)象到Cstring的自動(dòng)類型轉(zhuǎn)換。對(duì)于string類型的字符串，可以通過cstr()函數(shù)返回string對(duì)象對(duì)應(yīng)的C_string.
通常，程序員在整個(gè)程序中應(yīng)堅(jiān)持使用string類對(duì)象，直到必須將內(nèi)容轉(zhuǎn)化為char時(shí)才將其轉(zhuǎn)換為C_string.

提示：
為了修改 string字符串的內(nèi)容，下標(biāo)操作符[]和 at 都會(huì)返回字符的引用。但當(dāng)字符串的內(nèi)存被重新分配之后，可能發(fā)生錯(cuò)誤.

void test01()
{
?? ?string str("helloworld");?? ?
?? ?str = "world";//調(diào)用str.operator=(char *)

?? ?char *s = NULL;
?? ?//str.c_str();//得到const char *
?? ?//去const
?? ?s = cosnt cast<char *>(str.c_str());
}

vector容器

vector容器基本概念

向量?vector是一種對(duì)象實(shí)體, 能夠容納許多其他類型相同的元素, 因此又被稱為容器。 與string相同, vector 同屬于STL(Standard Template Library, 標(biāo)準(zhǔn)模板庫(kù))中的一種自定義的數(shù)據(jù)類型, 可以廣義上認(rèn)為是數(shù)組的增強(qiáng)版。在使用它時(shí), 需要包含頭文件 ?#include<vector>。vector 容器與數(shù)組相比其優(yōu)點(diǎn)在于它能夠根據(jù)需要隨時(shí)自動(dòng)調(diào)整自身的大小以便容下所要放入的元素。此外, vector 也提供了許多的方法來對(duì)自身進(jìn)行操作。

vector 型變量的聲明以及初始化的形式也有許多, 常用的有以下幾種形式

vector<int> a ; //聲明一個(gè)int型向量a

vector<int> a(10) ; //聲明一個(gè)初始大小為10的向量

vector<int> a(10, 1) ; //聲明一個(gè)初始大小為10且初始值都為1的向量

vector<int> b(a) ; //聲明并用向量a初始化向量b

vector<int> b(a.begin(), a.begin()+3) ; //將a向量中從第0個(gè)到第2個(gè)(共3個(gè))作為向量b的初始值

?除此之外, 還可以直接使用數(shù)組來初始化向量:

int n[] = {1, 2, 3, 4, 5} ; vector<int> a(n, n+5) ; //將數(shù)組n的前5個(gè)元素作為向量a的初值 
vector<int> a(&n[1], &n[4]) ; //將n[1] - n[4]范圍內(nèi)的元素作為向量a的初值

vector的數(shù)據(jù)結(jié)構(gòu)

Vector所采用的數(shù)據(jù)結(jié)構(gòu)非常簡(jiǎn)單，線性連續(xù)空間，它以兩個(gè)迭代器Myfirst和Mylast分別指向配置得來的連續(xù)空間中目前已被使用的范圍，并以迭代器_Myend指向整塊連續(xù)內(nèi)存空間的尾端。
為了降低空間配置時(shí)的速度成本，vector實(shí)際配置的大小可能比客戶端需求大一些，以備將來可能的擴(kuò)充，這邊是容量的概念。換句話說，一個(gè)vector的容量永遠(yuǎn)大于或等于其大小，一旦容量等于大小，便是滿載，下次再有新增元素，整個(gè)vector容器就得另覓居所。
注意：
所謂動(dòng)態(tài)增加大小，并不是在原空間之后續(xù)接新空間(因?yàn)闊o法保證原空間之后尚有可配置的空間)，而是一塊更大的內(nèi)存空間，然后將原數(shù)據(jù)拷貝新空間，并釋放原空間。因此，對(duì)vector的任何操作，一旦引起空間的重新配置，指向原vector的所有迭代器就都失效了。這是程序員容易犯的一個(gè)錯(cuò)誤，務(wù)必小心。

vector的構(gòu)造函數(shù)

vector<T>v；//采用模板實(shí)現(xiàn)類實(shí)現(xiàn)，默認(rèn)構(gòu)造函數(shù)

vector(v.begin(), v.end())；//將頭和尾區(qū)間中的元素拷貝給本身

vector(n, elem)；//構(gòu)造函數(shù)將n個(gè)elem拷貝給本身

vector(const vector &vec)；//拷貝構(gòu)造函數(shù)

void printf(int a)
{
?? ?cout << a << endl;
}

void test01()
{
?? ?vector<int> v1;
?? ?v1.push_back(1);?? ?
?? ?v1.push_back(2);
?? ?v1.push_back(3);
?? ?v1.push_back(4);
?? ?//vector<int> v2(v1);
?? ?//vector<int> v2(v1.begin(), v1.end())；//將頭和尾區(qū)間中的元素拷貝給本身?? ?
?? ?vector<int> v2(v1.begin()+1, v1.end())；//將頭和尾區(qū)間中的元素拷貝給本身
?? ?for_each(v2.begin(),v2.end(),printf);
}

vector常用賦值操作

assign(beg, end)；//將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。

assign(n, elem)；//將n個(gè)elem拷貝賦值給本身。

vector&operator=(const vector &vec)；//重載等號(hào)操作符

swap(vec)；//將vec與本身的元素互換。

void printf(int a)
{
?? ?cout << a << endl;
}

void test01()
{
?? ?vector<int> v1;
?? ?v1.push_back(1);?? ?
?? ?v1.push_back(2);
?? ?v1.push_back(3);
?? ?v1.push_back(4);
?? ?
?? ?vector<int> v2;
?? ?v1.push_back(5);?? ?
?? ?v1.push_back(6);
?? ?v1.push_back(7);
?? ?v1.push_back(8);
?? ?//v2.assign(v1.begin(),v1.end());//將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身
?? ?//v2.assign(10,5);//將n個(gè)elem拷貝賦值給本身
?? ?//v2 = v1;//重載等號(hào)操作符
?? ?v2.swap(v1);//v1和v2的指針指向交換
??
?? ?for_each(v2.begin(),v2.end(),printf);
}

vector大小操作

size()；//返回容器中元素的個(gè)數(shù)
empty();//判斷容器是否為空
resize(int num)；//重新指定容器的長(zhǎng)度為num，若容器變長(zhǎng)，則以默認(rèn)值填充新位置。如果容器變短，則末尾超出容器長(zhǎng)度的元素被刪除。
resize(int num, elem);//重新指定容器的長(zhǎng)度為num，若容器變長(zhǎng)，則以elem值填充新位置。如果容器變短，則末尾超出容器長(zhǎng)度的元素被刪除。
capacity();//容器的容量
reserve(int Len);//容器預(yù)留Len個(gè)元素長(zhǎng)度，預(yù)留位置不初始化，元素不可訪問。

void printf(int a)
{cout << a << endl;
}void test01()
{vector<int> v1;v1.push_back(1);	v1.push_back(2);v1.push_back(3);v1.push_back(4);cout << v1.size() << endl;//大小cout << v1.capacity() << endl;//容量v1.resize(10);if(!v1.empty()){cout << "不為空" << endl;}for_each(v1.begin(),v1.end(),printf());//1234000000vector<int> v2;v2.reserve(1000);//為v2預(yù)留1000個(gè)空間 設(shè)置容量cout << v2.size() << endl;//0cout << v2.capacity() << endl;//1000
}

vector容器數(shù)據(jù)存儲(chǔ)操作

at(int idx)；//返回索引idx 所指的數(shù)據(jù)，如果idx 越界， 拋出out_of_range異常。

operator[]；//返回索引idx所指的數(shù)據(jù)，越界時(shí) 運(yùn)行直接報(bào)錯(cuò)

front()；//返回容器中第一個(gè)數(shù)據(jù)元素

back()；//返回容器中最后一個(gè)數(shù)據(jù)元素

#include <iostream>
#include <string.h>
#include <iterator>
#include <vector>
#include <string>
using namespace std;void printf(int a)
{cout << a << endl;
}void test01()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);cout << v1.at(2) << endl;//3cout << v1[2] << endl;//3cout << v1.front() << endl;//1cout << v1.back() << endl;//4
}int main()
{test01();return 0;
}

vector容器的插入和刪除

insert(const_iterator pos, int count,ele 一 代器指向位置pos插入count 個(gè)元素ele.push_back(ele)；//尾部插入元素ele
pop_back()；//刪除最后一個(gè)元素
erase(const_iterator start, const_iterator end)；//刪除迭代器從start 到end之間的元erase(const_iterator pos);//刪除迭代器指向的元素
clear()；//刪除容器中所有元素

利用swap收縮空間

swap收縮空間的本質(zhì)是指針指向了不同的容器?

#include <iostream>
#include <string.h>
#include <iterator>
#include <vector>
#include <string>
#include <iostream>
#include <vector>
#include <string>
using namespace std;void test01()
{vector<int> v1;for (int i = 0; i < 1000; i++){v1.push_back(i);}cout << v1.size() << " " << v1.capacity() << endl;//1000 1024v1.resize(10);//cout << v1.size()<< " " << v1.capacity() << endl;//10 1024vector<int>(v1).swap(v1);cout << v1.size()<< " " << v1.capacity() << endl;//10 10}int main()
{test01();return 0;
}

deque容器

deque容器基本概念

Deque 容器和vector容器最大的差異，一在于deque允許使用常數(shù)項(xiàng)時(shí)間對(duì)頭端進(jìn)行元素的插入和刪除操作。二在于deque沒有容量的概念，因?yàn)樗莿?dòng)態(tài)的以分段連續(xù)空間組合而成，隨時(shí)可以增加一段新的空間并鏈接起來，換句話說，像vector那樣，”舊空間不足而重新配置一塊更大空間，然后復(fù)制元素，再釋放舊空間”這樣的事情在deque身上是不會(huì)發(fā)生的。也因此，deque沒有必須要提供所謂的空間保留(reserve)功能.
雖然deque容器也提供了Random Access lterator，但是它的迭代器并不是普通的指針，其復(fù)雜度和vector不是一個(gè)量級(jí)，這當(dāng)然影響各個(gè)運(yùn)算的層面。因此，除非有必要，我們應(yīng)該盡可能的使用vector，而不是deque。對(duì)deque進(jìn)行的排序操作，為了最高效率，可將deque先完整的復(fù)制到一個(gè)vector中，對(duì)vector容器進(jìn)行排序，再?gòu)?fù)制回deque

????????雙端數(shù)組deque和vector的區(qū)別

????????vector對(duì)于頭部的插入效率低，數(shù)據(jù)量越大，效率越低

? ? ? ? deque相對(duì)而言，對(duì)頭部的插入刪除速度會(huì)比vector快

? ? ? ? vector訪問元素時(shí)的速度會(huì)比deque快，這和兩者內(nèi)部實(shí)現(xiàn)有關(guān)

deque容器的實(shí)現(xiàn)原理

Deque 容器是連續(xù)的空間，至少邏輯上看來如此，連續(xù)現(xiàn)行空間總是令我們聯(lián)想到 array數(shù)組 和vector,array 無法成長(zhǎng),vector 雖可成長(zhǎng)，卻只能向尾端成長(zhǎng)，而且其成長(zhǎng)其實(shí)是一個(gè)假象，事實(shí)上(1) 申請(qǐng)更大空間 2)原數(shù)據(jù)復(fù)制新空間 3)釋放原空間 三步驟，如果不是 vector 每次配置新的空間時(shí)都留有余裕，其成長(zhǎng)假象所帶來的代價(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ǔ)存空間的主體。

deque的api—構(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ù)。

void print(int a)
{cout << a << endl;
}void test01()
{//構(gòu)造deque<int> d1;d1.push_back(1);d1.push_back(2);d1.push_back(3);deque<int> d2(d1.begin(),d1.end());deque<int> d3(d1);deque<int> d4(10,8);//遍歷for_each(d1.degin(),d1.end(),print);
}

deque的aip—賦值操作

assign(beg，end);//將[beg， end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。

assign(n，elem);//將n個(gè)elem拷貝賦值給本身。

deque& operator=(const deque &deq); //重載等號(hào)操作符

swap(deq);// 將deq與本身的元素互換

????deque<int> d3;
?? ?deque<int> d4;

?? ?d4.assign(d3);
?? ?d4 = d3;
?? ?
?? ?d3.swap(d4);
?? ?for_each(d4.begin(),d4.end(),print);

deque的api—容器的大小操作

deque.size();//返回容器中元素的個(gè)數(shù)

deque.empty();//判斷容器是否為空

deque.resize(num);//重新指定容器的長(zhǎng)度為num,若容器變長(zhǎng)，則以默認(rèn)值填充新位置。如果容器變短，則末尾超出容器的元素被刪除

deque.resizenum，elem); //重新指定容器的長(zhǎng)度為num,若容器變長(zhǎng)，則以elem值填充新位置,如果容器變短，則末尾超出容器長(zhǎng)的的元素被刪除

#include <iostream>
#include <string.h>
#include <iterator>
#include <vector>
#include <string>
#include <algorithm>
#include <deque>
using namespace std;void print(int a)
{cout << a << endl;
}void test01()
{deque<int> d1;d1.push_back(1);d1.push_back(2);d1.push_back(3);cout << d1.size() << endl;if(!d1.empty()){cout << "不為空" << endl;}d1.resize(3);d1.resize(4,5);for_each(d1.begin(),d1.end(),print);}int main()
{test01();return 0;
}

編譯運(yùn)行

deque的api—雙端的插入和刪除

push_back(eLem);//在器尾部添加一個(gè)數(shù)據(jù)
push_front(eLem);//在容器頭部插入一個(gè)數(shù)據(jù)
pop_back();//刪除器最后一個(gè)數(shù)據(jù)
pop_front();//刪除容器第一個(gè)數(shù)據(jù)

deque的api—數(shù)據(jù)存儲(chǔ)

at(idx);//返回索引idx 所指的數(shù)據(jù)，如idx 越界，拋出out_of_range。
operator[];//返回索引dx 所指的數(shù)據(jù)，如idx 越界，不地出異，直接出錯(cuò)。
front();//返回第一個(gè)數(shù)據(jù)。
back();//返回最后一個(gè)數(shù)據(jù)

deque的api—插入操作

insert(pos,eLem);//在pos 位置插入一個(gè)eLem 元素的拷貝，返回新數(shù)據(jù)的位置。
insert(pos,n,elem);//在pos 位置插An 個(gè)eLem 數(shù)據(jù)，無返回值。
insert(pos,beg,end);//在pos 位置插入[beg,end)區(qū)間的數(shù)據(jù)，無返回值。

deque的api—?jiǎng)h除操作

clear();//移除容器的所有數(shù)據(jù)

erase(beg,end);//刪除[beg,end)區(qū)間的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位智

erase(pos);//刪除pos 位置的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置。