數(shù)據(jù)結(jié)構(gòu) -- C++ STL中的數(shù)據(jù)結(jié)構(gòu)與算法[1]
什么是 STL
STL是Standard Template Library的簡稱逾滥，中文名標(biāo)準(zhǔn)模板庫谍夭，惠普實驗室開發(fā)的一系列軟件的統(tǒng)稱讹挎。它是由Alexander Stepanov趴泌、Meng Lee和David R Musser在惠普實驗室工作時所開發(fā)出來的倒戏。從根本上說，STL是一些“容器”與“算法”的集合瞭吃，所謂的這些“容器”無非就是已經(jīng)實現(xiàn)好了數(shù)據(jù)結(jié)構(gòu)碌嘀，能夠讓程序設(shè)計者更為方便的進(jìn)行調(diào)用，“算法”則顧名思義就是已預(yù)先實現(xiàn)好了的算法集合歪架。
STL的目的是標(biāo)準(zhǔn)化組件筏餐，這樣就不用重新開發(fā)，可以使用現(xiàn)成的組件牡拇。STL現(xiàn)在是C++的一部分魁瞪，因此不用安裝額外的庫文件。STL的版本很多惠呼，有很多公司或者工作室自定義STL形成各種各樣的自定義標(biāo)準(zhǔn)导俘。。
在C++標(biāo)準(zhǔn)中剔蹋，STL被組織為下面的13個頭文件：<algorithm>旅薄、<deque>、<functional>泣崩、<iterator>少梁、<vector>、<list>矫付、<map>凯沪、<memory>、<numeric>买优、<queue>妨马、<set>挺举、<stack>和<utility>。
STL中包含的幾大內(nèi)容：
1.容器（Container）
是一種數(shù)據(jù)結(jié)構(gòu)烘跺，也是本章節(jié)提的重點湘纵，如list(鏈表)，vector(向量數(shù)組)滤淳，stack(棧)梧喷，隊列(queue) ，以模板類的方法提供脖咐，為了訪問容器中的數(shù)據(jù)伤柄，可以使用由容器類輸出的迭代器。
- 迭代器（Iterator）
是一種特殊的指針文搂，它提供了訪問容器中對象的方法，在程序設(shè)計中秤朗，它扮演了容器和算法之間的膠合劑煤蹭，利用迭代器可以快速而安全的對容器內(nèi)容進(jìn)行操作，或是進(jìn)行算法模板的使用取视。
- 算法（Algorithm）
（部分書籍稱為泛型算法硝皂，generic algorithms），是一類常用的算法模板作谭，既可以對容器進(jìn)行操作稽物，同時其開放性也讓算法類本身可以針對數(shù)組或者是自定義結(jié)構(gòu)體等結(jié)構(gòu)進(jìn)行直接的操作。
- *仿函數(shù)（Function object）（又稱為函數(shù)對象折欠，function object）
是一種行為類似函數(shù)贝或，這樣講可能有些抽象，我們可以理解為一種高級的锐秦，重載了()操作符的結(jié)構(gòu)體與類咪奖。
5.*迭代適配器（Iterator Adaptor）
是一種用來修飾容器或者仿函數(shù)的接口，它使得得帶適配器使算法能夠以逆向模式酱床，安插模式進(jìn)行工作羊赵，甚至還可以與流配合，它對容器起到非常大的輔助作用扇谣，同時他還將迭代器進(jìn)行了更高級別的抽象昧捷。
- *空間配制器（allocator）
是負(fù)責(zé)空間的配置與管理，重點就是對容器的空間申請和空間釋放進(jìn)行管理罐寨，你可以理解為C的malloc和free函數(shù)靡挥，C++的new和delete關(guān)鍵字。
Vector容器
1. 概念
Vector可以翻譯為向量鸯绿，或向量數(shù)組芹血，至于為什么以向量命名贮泞，可以理解為一維空間也是存在向量的。
Vector是最簡單的序列是容器幔烛，就像數(shù)組一樣啃擦，向量使用連續(xù)的存儲位置作為元素，這意味著它們的元素也可以使用常量指向其元素的偏移來訪問饿悬，與數(shù)組一樣有效令蛉。但與數(shù)組不同，它們的大小可以動態(tài)變化狡恬，其存儲由容器自動處理珠叔。
總結(jié)一下Vector就是一個動態(tài)創(chuàng)建空間，且預(yù)先加載了常用的數(shù)組操作的數(shù)組
2. 相關(guān)文件
頭文件：#include <vector>
3. 初始化
格式為：vector<Data_Types> name;
我們以int類型作為參數(shù)為例弟劲，進(jìn)行創(chuàng)建祷安。
vector<int> v1; //創(chuàng)建一個空的向量v1
vector<int> v2(10); //創(chuàng)建一個向量v2，其已開辟10個元素的空間兔乞，相當(dāng)于int v[10];
vector<int> v3(10,5); //創(chuàng)建一個向量v3汇鞭，其已開辟10個元素的空間并全部賦值為5
vector<int> v4(v3.begin(),v3.end()); //創(chuàng)建一個向量v3,其內(nèi)容為向量v3的內(nèi)容
vector<int> v5(v4); //創(chuàng)建一個向量v5，其包含了v4的全部內(nèi)容
4. 迭代器
顧名思義庸追，迭代器是一種安全的訪問控制器霍骄，它本身是一種指針，用于直接的元素訪問淡溯。其遍歷訪問的大致思路是读整，創(chuàng)建容器的迭代器，讓迭代器指向第一個元素咱娶，逐步向后移動并最終指向最后一個元素結(jié)束米间。
遍歷代碼舉例：
vector<int> v; //創(chuàng)建一個向量vs
vector<int>::iterator it; //C98標(biāo)準(zhǔn)
for(it=v.begin();it!=v.end();it++){
cout<<*it<<' ';
}
當(dāng)然，遍歷也可以直接使用下標(biāo)訪問：
for(int i=0;i<v.size();i++){
cout<<v[i]<<' ';
}
5.常用接口（常用的）
Vector的接口有非常多膘侮，不同的C++語言標(biāo)準(zhǔn)也不同车伞，這里只提供一些常用的進(jìn)行簡介，具體的使用可以翻閱官方文檔（英文）喻喳，或是別人的翻譯稿另玖。
我們使用 vector<int> v; 預(yù)先創(chuàng)建了一個向量。
a) 向量尾插入push_back()
在向量的末尾添加一個新元素val表伦，并自動讓容器大小增大一個谦去。
函數(shù)原型：
void push_back (const value_type& val);
使用舉例：
v.push_back(10); //插入一個數(shù)據(jù)10
b) 向量尾刪除pop_back()
移除向量尾的最后一個元素，并且將容器大小減小一個蹦哼，
函數(shù)原型：void pop_back();
使用舉例：
v.pop_back();
c) 插入insert()
插入元素到指定位置鳄哭，通過在元素之前在指定位置插入新元素來擴(kuò)展向量，從而有效地增加容器大小所插入的元素數(shù)量纲熏。
函數(shù)原型：
插入單一數(shù)據(jù)到指定位置：
iterator insert (iterator position, const value_type& val);
插入一段數(shù)據(jù)到指定位置：
void insert (iterator position, size_type n, const value_type& val);
插入一段別的容器的數(shù)據(jù)到指定位置：
*template *
void insert (iterator position, InputIterator first, InputIterator last);
使用舉例：
v.insert(v.begin(),10); //在向量最前端插入數(shù)據(jù)10
v.insert(v.begin(),5,20); //在向量最前端插入5個數(shù)據(jù)20
vector<int> k(2,50); //創(chuàng)建一個新的向量k,其擁有2個元素內(nèi)容均為50
v.insert(v.begin(),k.begin(),k.end()); //在向量v最前端插入向量K的全部內(nèi)容
d) 刪除erase()
刪除一個元素妆丘，或者是一段區(qū)間的元素锄俄，將會自動縮減空間使用。
函數(shù)原型：
iterator erase (iterator position);
iterator erase (iterator first, iterator last);
使用舉例
v.erase(v.begin()); //刪除第一個元素
v.erase(v.begin(),v.begin()+4); //刪除從第一個開始后4個元素（包括第一個）
List容器
1.概念
鏈表是線性表 勺拣，STL鏈表是單鏈表的形式奶赠。
2.頭文件
頭文件：#include <list>
3.初始化
格式為：explicit list (const allocator_type& alloc = allocator_type());
我們以int類型作為參數(shù)為例進(jìn)行創(chuàng)建，其創(chuàng)建方法與vector無異
list<int> l1; //創(chuàng)建一個空鏈表
list<int> l2(10); //創(chuàng)建一個鏈表其有10個空元素
list<int> l3(5,20); //創(chuàng)建一個鏈表其有5個元素內(nèi)容為20
list<int> l4(l3.begin(),l3.end()); //創(chuàng)建一個鏈表其內(nèi)容為l3的內(nèi)容
list<int> l5(l4); //創(chuàng)建一個鏈表其內(nèi)容為l4的內(nèi)容
4. 迭代器
遍歷代碼舉例(其方法和vector版本無異只是更加精簡)：
list<int> li;
for(list<int>::iterator it=li.begin();it!=li.end();it++){
cout<<*it<<' ';
}
5. 常用接口
a)判斷是否為空empty()
返回一個bool類型的值药有，只存在真和假毅戈，當(dāng)鏈表為空時為真，不為空時為假
函數(shù)原型
bool empty() const;
b)獲取大小size()
返回鏈表元素的個數(shù)
函數(shù)原型
size_type size() const;
c) 鏈表前插入push_front() &&刪除 pop_front()
push_front()表示在鏈表最前端插入一個數(shù)據(jù)愤惰，pop_front()表示在鏈表最前端刪除一個數(shù)據(jù)苇经。
函數(shù)原型
void push_front (const value_type& val);
void pop_front();
d) 鏈表后插入push_back() &&刪除 pop_back()
push_back()表示在鏈表尾插入一個數(shù)據(jù)，pop_back()表示將鏈表尾刪除一個數(shù)據(jù)宦言。
函數(shù)原型：
void push_back (const value_type& val);
void pop_back();
e) 插入insert()
插入元素到指定位置扇单，通過在元素之前在指定位置插入新元素來擴(kuò)展向量，從而有效地增加容器大小所插入的元素數(shù)量奠旺。
函數(shù)原型：
插入單一數(shù)據(jù)到指定位置：
iterator insert (iterator position, const value_type& val);
插入一段數(shù)據(jù)到指定位置：
void insert (iterator position, size_type n, const value_type& val);
插入一段別的容器的數(shù)據(jù)到指定位置：
template <class InputIterator>
void insert (iterator position, InputIterator first, InputIterator last);
f) 刪除erase()
刪除一個元素蜘澜，或者是一段區(qū)間的元素，將會自動縮減空間使用凉倚。
函數(shù)原型：
iterator erase (iterator position);
iterator erase (iterator first, iterator last);
stack棧容器
1. 棧
回顧一下之前所學(xué)的棧，棧是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)嫂沉，而實現(xiàn)方式需要創(chuàng)建多個結(jié)構(gòu)體稽寒，通過鏈?zhǔn)降姆绞竭M(jìn)行實現(xiàn)，這是標(biāo)準(zhǔn)的棧的思路趟章，而在STL中椥硬冢可以以更為簡單的方式實現(xiàn)。
2. 頭文件
頭文件 #include<stack>
3. 初始化
格式為：explicit stack (const container_type& ctnr = container_type());
我們以int類型作為參數(shù)為例進(jìn)行創(chuàng)建蚓土，其創(chuàng)建方法與vector無異
stack<int> s;
stack<int> v(s);
標(biāo)準(zhǔn)的棧創(chuàng)建方法是直接創(chuàng)建空棧宏侍，由于棧的特殊性質(zhì)，讓他擁有其他容器的參數(shù)可以這樣創(chuàng)建蜀漆，這種多參數(shù)的方式可能有一些復(fù)雜谅河，一般也很少這樣使用。
vector<int> v(3,100);
stack<int,vector<int> > s(v); //注意确丢，> >符號之間需要有一個空格隔開
通過標(biāo)準(zhǔn)的方式創(chuàng)建向量數(shù)組绷耍，然后通過復(fù)制構(gòu)造函數(shù)的方式進(jìn)行創(chuàng)建，其內(nèi)容就是vector數(shù)組的全部內(nèi)容鲜侥。
4. 迭代器
棧和隊列都屬于一種特殊的數(shù)據(jù)結(jié)構(gòu)褂始，只能通過訪問頂層數(shù)據(jù)并不斷剔除數(shù)據(jù)的方法進(jìn)行全部訪問，因此沒有直接的迭代器描函。
5. 常用接口
我們使用stack<int> s 預(yù)先創(chuàng)建了一個棧崎苗，命名為s狐粱，方便舉例
a)大小size()
返回鏈表元素的個數(shù)
函數(shù)原型：size_type size() const;
b) 返回棧頂元素top()
返回棧頂元素內(nèi)容
函數(shù)原型：
reference& top();
const_reference& top() const;
c) 入棧push()
往棧頂中插入一個元素。
函數(shù)原型： void push (const value_type& val);
d)出棧pop()
將棧頂元素釋放胆数，注意pop()函數(shù)是沒有返回值的肌蜻，如果要想訪問后刪除需要先top再pop使用。
函數(shù)原型：void pop();
s.pop();
e) 判空empty()
返回一個bool類型的值幅慌，只存在真和假宋欺，當(dāng)棧為空時為真，不為空時為假
函數(shù)原型
bool empty() const;
Queue容器
1. 再談隊列
回顧一下之前所學(xué)的隊列胰伍，隊列和棧不同齿诞，隊列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，STL的隊列內(nèi)容極其重要骂租，雖然內(nèi)容較少但是請務(wù)必掌握祷杈，STL的隊列是快速構(gòu)建搜索算法以及相關(guān)的數(shù)論圖論的狀態(tài)存儲的基礎(chǔ)。
2.相關(guān)文件
頭文件：#include<queue>
3.初始化
格式為：
explicit queue (const container_type& ctnr = container_type());
我們以int類型作為參數(shù)為例進(jìn)行創(chuàng)建渗饮。
queue<int> q; //創(chuàng)建一個空的沒有數(shù)據(jù)的隊列q
queue<int> qoo(q); //創(chuàng)建一個隊列其元素為q的全部內(nèi)容
標(biāo)準(zhǔn)的隊列創(chuàng)建方法是直接創(chuàng)建空隊列再進(jìn)行其他的操作但汞，由于隊列的特殊性質(zhì)，擁有其他容器的參數(shù)可以這樣創(chuàng)建互站，這種多參數(shù)的方式可能有一些復(fù)雜私蕾，一般也很少這樣使用。
vector<int> v(3,100);
queue<int,vector<int> > s(v); //注意胡桃，> >符號之間需要有一個空格隔開
通過標(biāo)準(zhǔn)的方式創(chuàng)建向量數(shù)組踩叭，然后通過復(fù)制構(gòu)造函數(shù)的方式進(jìn)行創(chuàng)建，其內(nèi)容就是vector數(shù)組的全部內(nèi)容翠胰。
4. 迭代器
棧和隊列都屬于一種特殊的數(shù)據(jù)結(jié)構(gòu)容贝，只能通過訪問頂層數(shù)據(jù)并不斷剔除數(shù)據(jù)的方法進(jìn)行全部訪問，因此沒有直接的迭代器之景。
5. 常用接口
我們預(yù)先通過queue<int> q創(chuàng)建了一個隊列斤富，命名為q，方便舉例锻狗。
a)大小size()
返回鏈表元素的個數(shù)
函數(shù)原型：size_type size() const;
b) 入隊push()
進(jìn)行入隊操作满力，在隊尾處進(jìn)行插入
函數(shù)原型：void push (const value_type& val);
q.push(100);
c) 出隊pop()
進(jìn)行出隊操作，在對頭出進(jìn)行彈出
函數(shù)原型：void pop();
q.pop();
d)訪問隊頭元素front()
訪問對頭元素轻纪，可以返回其數(shù)值脚囊，也可以進(jìn)行相應(yīng)的操作，這里更加建議多使用front()訪問隊頭數(shù)據(jù)桐磁，因為我們進(jìn)行出隊操作均是從隊頭進(jìn)行出隊的悔耘。
函數(shù)原型：
value_type& front();
const value_type& front() const;
q.front()+=500; //對隊頭元素進(jìn)行修改
e) 訪問隊尾元素back()
訪問隊尾元素，較為少用我擂。
函數(shù)原型：
value_type& back();
const value_type& back() const;
q.back()+=500; //對隊尾元素進(jìn)行修改
f) 判空empty()
返回一個bool類型的值衬以，只存在真和假缓艳，當(dāng)隊列為空時為真，不為空時為假
