C/C++學(xué)習(xí)之路: STL

---

目錄

STL概述

STL三大組件

常用容器

---

1. STL概述

STL(Standard Template Library,標(biāo)準(zhǔn)模板庫)，主要出現(xiàn)在 c++中，但是在引入 c++之前該技術(shù)已經(jīng)存在很長(zhǎng)時(shí)間了。

STL 從廣義上分為: 容器(container) ，算法(algorithm) 和迭代器(iterator)，容器和算法之間通過迭代器進(jìn)行無縫連接。

STL 幾乎所有的代碼都采用了模板類或者模板函數(shù)，這相比傳統(tǒng)的由函數(shù)和類組成的庫來說提供了更好的代碼重用機(jī)會(huì)。

1. STL六大組件簡(jiǎn)介

STL提供了六大組件，彼此之間可以組合套用，這六大組件分別是: 容器、算法、迭代器、仿函數(shù)、適配器、空間配置器。

容器：各種數(shù)據(jù)結(jié)構(gòu)，如vector、list、deque、set、map等，用來存放數(shù)據(jù)，從實(shí)現(xiàn)角度來看，STL容器是一種class template。

算法：各種常用的算法，如sort、find、copy、for_each。從實(shí)現(xiàn)的角度來看，STL算法是一種function tempalte.

迭代器：扮演了容器與算法之間的膠合劑，共有五種類型，從實(shí)現(xiàn)角度來看，迭代器是一種將operator* ,operator->，operator++，operator–等指針相關(guān)操作予以重載的class template。

所有STL容器都附帶有自己專屬的迭代器，只有容器的設(shè)計(jì)者才知道如何遍歷自己的元素。

原生指針(native pointer)也是一種迭代器。

仿函數(shù)：行為類似函數(shù)，可作為算法的某種策略。從實(shí)現(xiàn)角度來看，仿函數(shù)是一種重載了operator()的class 或者class template

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

空間配置器：負(fù)責(zé)空間的配置與管理。從實(shí)現(xiàn)角度看，配置器是一個(gè)實(shí)現(xiàn)了動(dòng)態(tài)空間配置、空間管理、空間釋放的class tempalte.

STL六大組件的交互關(guān)系，容器通過空間配置器取得數(shù)據(jù)存儲(chǔ)空間，算法通過迭代器存儲(chǔ)容器中的內(nèi)容，仿函數(shù)可以協(xié)助算法完成不同的策略的變化，適配器可以修飾仿函數(shù)。

2. STL優(yōu)點(diǎn)

STL 是 C++的一部分，因此不用額外安裝什么，它被內(nèi)建在你的編譯器之內(nèi)。

STL 的一個(gè)重要特點(diǎn)是數(shù)據(jù)結(jié)構(gòu)和算法的分離。盡管這是個(gè)簡(jiǎn)單的概念，但是這種分離使得 STL 變得非常通用。

例如在 STL 的 vector 容器中，可以放入元素、基礎(chǔ)數(shù)據(jù)類型變量、元素的地址。

STL 的 sort() 排序函數(shù)可以用來操作 vector，list 等容器。

STL 具有高可重用性，高性能，高移植性，跨平臺(tái)的優(yōu)點(diǎn)。

高可重用性：STL 中幾乎所有的代碼都采用了模板類和模版函數(shù)的方式實(shí)現(xiàn)，這相比于傳統(tǒng)的由函數(shù)和類組成的庫來說提供了更好的代碼重用機(jī)會(huì)

高性能：如 map 可以高效地從十萬條記錄里面查找出指定的記錄，因?yàn)?map 是采用紅黑樹的變體實(shí)現(xiàn)的。(紅黑樹是平橫二叉樹的一種)

高移植性：如在項(xiàng)目 A 上用 STL 編寫的模塊，可以直接移植到項(xiàng)目 B 上。

---

2. STL三大組件

1. 容器

容器分為序列式容器和關(guān)聯(lián)式容器兩種。

序列式容器就是容器元素在容器中的位置是由元素進(jìn)入容器的時(shí)間和地點(diǎn)來決定。Vector容器、Deque容器、List容器、Stack容器、Queue容器。

關(guān)聯(lián)式容器是指容器已經(jīng)有了一定的規(guī)則，容器元素在容器中的位置由我的規(guī)則來決定。Set/multiset容器 Map/multimap容器。

2. 算法

算法分為：質(zhì)變算法和非質(zhì)變算法。

質(zhì)變算法：是指運(yùn)算過程中會(huì)更改區(qū)間內(nèi)的元素的內(nèi)容。例如拷貝，替換，刪除等等

非質(zhì)變算法：是指運(yùn)算過程中不會(huì)更改區(qū)間內(nèi)的元素內(nèi)容，例如查找、計(jì)數(shù)、遍歷、尋找極值等等

3. 迭代器

迭代器(iterator)是一種抽象的設(shè)計(jì)概念，現(xiàn)實(shí)程序語言中并沒有直接對(duì)應(yīng)于這個(gè)概念的實(shí)物。其中iterator模式定義如下：提供一種方法，使之能夠依序?qū)ぴL某個(gè)容器所含的各個(gè)元素，而又無需暴露該容器的內(nèi)部表示方式。

迭代器的設(shè)計(jì)思維-STL的關(guān)鍵所在，STL的中心思想在于將數(shù)據(jù)容器(container)和算法(algorithms)分開，彼此獨(dú)立設(shè)計(jì)，最后再一貼膠著劑將他們撮合在一起。從技術(shù)角度來看，容器和算法的泛型化并不困難，c++的class template和function template可分別達(dá)到目標(biāo)，如果設(shè)計(jì)出兩這個(gè)之間的良好的膠著劑，才是大難題。

輸入迭代器	提供對(duì)數(shù)據(jù)的只讀訪問
輸出迭代器	提供對(duì)數(shù)據(jù)的只寫訪問
前向迭代器	提供讀寫操作，并能向前推進(jìn)迭代器
雙向迭代器	提供讀寫操作，并能向前和向后操作
隨機(jī)訪問迭代器	提供讀寫操作，并能在數(shù)據(jù)中隨機(jī)移動(dòng)

---

3. 常用容器

1. string容器

1. string容器基本概念

C風(fēng)格字符串(以空字符結(jié)尾的字符數(shù)組)太過復(fù)雜難于掌握，不適合大程序的開發(fā)，所以C++標(biāo)準(zhǔn)庫定義了一種string類，定義在頭文件<string>。

String和c風(fēng)格字符串對(duì)比：

char是一個(gè)指針，String是一個(gè)類，string封裝了char，管理這個(gè)字符串，是一個(gè)char*型的容器。

String封裝了很多實(shí)用的成員方法，查找find，拷貝copy，刪除delete 替換replace，插入insert

不用考慮內(nèi)存釋放和越界，string管理char*所分配的內(nèi)存。每一次string的復(fù)制，取值都由string類負(fù)責(zé)維護(hù)，不用擔(dān)心復(fù)制越界和取值越界等。

2. string容器常用操作

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

string s1(); // si = "" string s2("Hello"); // s2 = "Hello" string s3(4, 'K'); // s3 = "KKKK" string s4("12345", 1, 3); //s4 = "234"，即 "12345" 的從下標(biāo) 1 開始，長(zhǎng)度為 3 的子串

2. string基本賦值操作

可以用 char* 類型的變量、常量，以及 char 類型的變量、常量對(duì) string 對(duì)象進(jìn)行賦值。例如：

string s1; s1 = "Hello"; // s1 = "Hello" s2 = 'K'; // s2 = "K”

string 類還有 assign 成員函數(shù)，可以用來對(duì) string 對(duì)象賦值。assign 成員函數(shù)返回對(duì)象自身的引用。例如：

string s1("12345"), s2; s3.assign(s1); // s3 = s1 s2.assign(s1, 1, 2); // s2 = "23"，即 s1 的子串(1, 2) s2.assign(4, 'K'); // s2 = "KKKK" s2.assign("abcde", 2, 3); // s2 = "cde"，即 "abcde" 的子串(2, 3)

3. 求字符串的長(zhǎng)度

length 成員函數(shù)返回字符串的長(zhǎng)度。size 成員函數(shù)可以實(shí)現(xiàn)同樣的功能。

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

4. string對(duì)象中字符串的連接

除了可以使用+和+=運(yùn)算符對(duì) string 對(duì)象執(zhí)行字符串的連接操作外，string 類還有 append 成員函數(shù)，可以用來向字符串后面添加內(nèi)容。append 成員函數(shù)返回對(duì)象自身的引用。例如：

string s1("123"), s2("abc"); s1.append(s2); // s1 = "123abc" s1.append(s2, 1, 2); // s1 = "123abcbc" s1.append(3, 'K'); // s1 = "123abcbcKKK" s1.append("ABCDE", 2, 3); // s1 = "123abcbcKKKCDE"，添加 "ABCDE" 的子串(2, 3)

5. string查找和替換

string 類有一些查找子串和字符的成員函數(shù)，它們的返回值都是子串或字符在 string 對(duì)象字符串中的位置（即下標(biāo)）。如果查不到，則返回 string::npos。string: :npos 是在 string 類中定義的一個(gè)靜態(tài)常量。這些函數(shù)如下：

find：從前往后查找子串或字符出現(xiàn)的位置。

rfind：從后往前查找子串或字符出現(xiàn)的位置。

find_first_of：從前往后查找何處出現(xiàn)另一個(gè)字符串中包含的字符。例如：

s1.find_first_of(“abc”); //查找s1中第一次出現(xiàn)"abc"中任一字符的位置

find_last_of：從后往前查找何處出現(xiàn)另一個(gè)字符串中包含的字符。

find_first_not_of：從前往后查找何處出現(xiàn)另一個(gè)字符串中沒有包含的字符。

find_last_not_of：從后往前查找何處出現(xiàn)另一個(gè)字符串中沒有包含的字符。

#include <iostream> #include <string> using namespace std; int main() {string s1("Source Code");int n;if ((n = s1.find('u')) != string::npos) //查找 u 出現(xiàn)的位置cout << "1) " << n << "," << s1.substr(n) << endl;//輸出 l)2,urce Codeif ((n = s1.find("Source", 3)) == string::npos)//從下標(biāo)3開始查找"Source"，找不到cout << "2) " << "Not Found" << endl; //輸出 2) Not Foundif ((n = s1.find("Co")) != string::npos)//查找子串"Co"。能找到，返回"Co"的位置cout << "3) " << n << ", " << s1.substr(n) << endl;//輸出 3) 7, Codeif ((n = s1.find_first_of("ceo")) != string::npos)//查找第一次出現(xiàn)或 'c'、'e'或'o'的位置cout << "4) " << n << ", " << s1.substr(n) << endl;//輸出 4) l, ource Codeif ((n = s1.find_last_of('e')) != string::npos)//查找最后一個(gè) 'e' 的位置cout << "5) " << n << ", " << s1.substr(n) << endl; //輸出 5) 10, eif ((n = s1.find_first_not_of("eou", 1)) != string::npos)//從下標(biāo)1開始查找第一次出現(xiàn)非 'e'、'o' 或 'u' 字符的位置cout << "6) " << n << ", " << s1.substr(n) << endl;//輸出 6) 3, rce Codereturn 0; }

6. string比較操作

除了可以用 <、<=、==、!=、>=、> 運(yùn)算符比較 string 對(duì)象外，string 類還有 compare 成員函數(shù)，可用于比較字符串。compare 成員函數(shù)有以下返回值：

小于 0 表示當(dāng)前的字符串小。

等于 0 表示兩個(gè)字符串相等。

大于 0 表示另一個(gè)字符串小。

/* string s1("hello"), s2("hello, world"); int n = s1.compare(s2); n = s1.compare(1, 2, s2, 0, 3); //比較s1的子串 (1,2) 和s2的子串 (0,3) n = s1.compare(0, 2, s2); // 比較s1的子串 (0,2) 和 s2 n = s1.compare("Hello"); n = s1.compare(1, 2, "Hello"); //比較 s1 的子串(1,2)和"Hello” n = s1.compare(1, 2, "Hello", 1, 2); //比較 s1 的子串(1,2)和 "Hello" 的子串(1,2)

7. string子串

substr 成員函數(shù)可以用于求子串 (n, m)，原型如下：

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

調(diào)用時(shí)，如果省略 m 或 m 超過了字符串的長(zhǎng)度，則求出來的子串就是從下標(biāo) n 開始一直到字符串結(jié)束的部分。例如：

string s1 = "this is ok"; string s2 = s1.substr(2, 4); // s2 = "is i" s2 = s1.substr(2); // s2 = "is is ok"

8. string插入和刪除操作

insert 成員函數(shù)可以在 string 對(duì)象中插入另一個(gè)字符串，返回值為對(duì)象自身的引用。例如：

string s1("Limitless"), s2("00"); s1.insert(2, "123"); //在下標(biāo) 2 處插入字符串"123"，s1 = "Li123mitless" s1.insert(3, s2); //在下標(biāo) 2 處插入 s2 , s1 = "Li10023mitless" s1.insert(3, 5, 'X'); //在下標(biāo) 3 處插入 5 個(gè) 'X'，s1 = "Li1XXXXX0023mitless"

erase 成員函數(shù)可以刪除 string 對(duì)象中的子串，返回值為對(duì)象自身的引用。例如：

string s1("Real Steel"); s1.erase(1, 3); //刪除子串(1, 3)，此后 s1 = "R Steel" s1.erase(5); //刪除下標(biāo)5及其后面的所有字符，此后 s1 = "R Ste"

9. string和c-style字符串轉(zhuǎn)換

//string 轉(zhuǎn) char* string str = "itcast"; const char* cstr = str.c_str(); //char* 轉(zhuǎn) string char* s = "itcast"; string sstr(s);

在c++中存在一個(gè)從const char*到string的隱式類型轉(zhuǎn)換，卻不存在從一個(gè)string對(duì)象到C_string的自動(dòng)類型轉(zhuǎn)換。

對(duì)于string類型的字符串，可以通過c_str()函數(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.

10. 交換兩個(gè)string對(duì)象的內(nèi)容

swap 成員函數(shù)可以交換兩個(gè) string 對(duì)象的內(nèi)容。例如：

string s1("West”), s2("East"); s1.swap(s2); // s1 = "East"，s2 = "West"

11. 將 string 對(duì)象作為流處理

使用流對(duì)象 istringstream 和 ostringstream，可以將 string 對(duì)象當(dāng)作一個(gè)流進(jìn)行輸入輸出。使用這兩個(gè)類需要包含頭文件 sstream。

示例程序如下：

#include <iostream> #include <sstream> #include <string> using namespace std; int main() {string src("Avatar 123 5.2 Titanic K");istringstream istrStream(src); //建立src到istrStream的聯(lián)系string s1, s2;int n; double d; char c;istrStream >> s1 >> n >> d >> s2 >> c; //把src的內(nèi)容當(dāng)做輸入流進(jìn)行讀取ostringstream ostrStream;ostrStream << s1 << endl << s2 << endl << n << endl << d << endl << c <<endl;cout << ostrStream.str();return 0; }

12. 用 STL 算法操作 string 對(duì)象

string 對(duì)象也可以看作一個(gè)順序容器，它支持隨機(jī)訪問迭代器，也有 begin 和 end 等成員函數(shù)。STL 中的許多算法也適用于 string 對(duì)象。

下面是用 STL 算法操作 string 對(duì)象的程序示例。

#include <iostream> #include <algorithm> #include <string> using namespace std; int main() {string s("afgcbed");string::iterator p = find(s.begin(), s.end(), 'c');if (p!= s.end())cout << p - s.begin() << endl; //輸出 3sort(s.begin(), s.end());cout << s << endl; //輸出 abcdefgnext_permutation(s.begin(), s.end());cout << s << endl; //輸出 abcdegfreturn 0; }

2. vector

向量（Vector）是一個(gè)封裝了動(dòng)態(tài)大小數(shù)組的順序容器（Sequence Container）。跟任意其它類型容器一樣，它能夠存放各種類型的對(duì)象。可以簡(jiǎn)單的認(rèn)為，向量是一個(gè)能夠存放任意類型的動(dòng)態(tài)數(shù)組。

1. vector迭代器

Vector維護(hù)一個(gè)線性空間，所以不論元素的型別如何，普通指針都可以作為vector的迭代器，因?yàn)関ector迭代器所需要的操作行為，如operaroe*, operator->, operator++, operator–, operator+, operator-, operator+=, operator-=, 普通指針天生具備。Vector支持隨機(jī)存取，而普通指針正有著這樣的能力。所以vector提供的是隨機(jī)訪問迭代器(Random Access Iterators).

根據(jù)上述描述，如果我們寫如下的代碼：

Vector<int>::iterator it1; Vector<Teacher>::iterator it2;

it1的型別其實(shí)就是int*,it2的型別其實(shí)就是Teacher*.

void test2() {vector<int> v;for (int i = 0; i < 10; i++) {v.push_back(i);cout << v.capacity() << endl;}int *start = &v[0];int *end = &v[v.size() - 1];for (; start <= end; start++) {cout << *start << endl;} }

2. 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ù)必小心。

3. vector常用api操作

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

vector<T> v; //采用模板實(shí)現(xiàn)類實(shí)現(xiàn)，默認(rèn)構(gòu)造函數(shù) vector(v.begin(), v.end());//將v[begin(), end())區(qū)間中的元素拷貝給本身。 vector(n, elem);//構(gòu)造函數(shù)將n個(gè)elem拷貝給本身。 vector(const vector &vec);//拷貝構(gòu)造函數(shù)。//例子 使用第二個(gè)構(gòu)造函數(shù) int arr[] = {2,3,4,1,9}; vector<int> v1(arr, arr + sizeof(arr) / sizeof(int)); // 使用第三個(gè)構(gòu)造函數(shù) vector<int> v2(10,6);

2. 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與本身的元素互換。vector<int> v;v.assign(10,6);v.swap(v2);

3. 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ù)留位置不初始化，元素不可訪問。

4. vector數(shù)據(jù)存取操作

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ù)元素

5. 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();//刪除容器中所有元素

4. vector案例

1. 使用swap，收縮內(nèi)存空間

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> usingnamespace std;int main(){vector<int> v;for(int i =0; i <100000;i ++){v.push_back(i);}cout <<"capacity:"<< v.capacity()<< endl;cout <<"size:"<< v.size()<< endl;//此時(shí) 通過resize改變?nèi)萜鞔笮?/span>v.resize(10);cout <<"capacity:"<< v.capacity()<< endl;cout <<"size:"<< v.size()<< endl;//容量沒有改變vector<int>(v).swap(v);cout <<"capacity:"<< v.capacity()<< endl;cout <<"size:"<< v.size()<< endl;system("pause");return EXIT_SUCCESS; }

2. reserve 預(yù)留空間

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> usingnamespace std;int main(){vector<int> v;//預(yù)先開辟空間v.reserve(100000);int* pStart =NULL;int count =0;for(int i =0; i <100000;i ++){v.push_back(i);if(pStart !=&v[0]){pStart =&v[0];count++;}}cout <<"count:"<< count << endl;system("pause");return EXIT_SUCCESS; }

3. deque

Vector容器是單向開口的連續(xù)內(nèi)存空間，deque則是一種雙向開口的連續(xù)線性空間。所謂的雙向開口，意思是可以在頭尾兩端分別做元素的插入和刪除操作，當(dāng)然，vector容器也可以在頭尾兩端插入元素，但是在其頭部操作效率奇差，無法被接受。

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 Iterator，但是它的迭代器并不是普通的指針，其復(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.

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

Deque容器是連續(xù)的空間，至少邏輯上看來如此，連續(xù)現(xiàn)行空間總是令我們聯(lián)想到array和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ǔ)空間的主體。

2. deque常用api操作

1. deque構(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ù)。

2. deque賦值操作

assign(beg, end);//將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。 assign(n, elem);//將n個(gè)elem拷貝賦值給本身。 deque&operator=(const deque &deq); //重載等號(hào)操作符 swap(deq);// 將deq與本身的元素互換

3. deque大小操作

deque.size();//返回容器中元素的個(gè)數(shù) deque.empty();//判斷容器是否為空 deque.resize(num);//重新指定容器的長(zhǎng)度為num,若容器變長(zhǎng)，則以默認(rèn)值填充新位置。如果容器變短，則末尾超出容器長(zhǎng)度的元素被刪除。 deque.resize(num, elem); //重新指定容器的長(zhǎng)度為num,若容器變長(zhǎng)，則以elem值填充新位置,如果容器變短，則末尾超出容器長(zhǎng)度的元素被刪除。

4. deque雙端插入和刪除操作

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

5. deque雙端插入和刪除操作

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

6. deque插入操作

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ù)，無返回值。

7. deque刪除操作

clear();//移除容器的所有數(shù)據(jù) erase(beg,end);//刪除[beg,end)區(qū)間的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置。 erase(pos);//刪除pos位置的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置。

4. stack容器

1. stack容器基本概念

stack是一種先進(jìn)后出(First In Last Out,FILO)的數(shù)據(jù)結(jié)構(gòu)，它只有一個(gè)出口，形式如圖所示。stack容器允許新增元素，移除元素，取得棧頂元素，但是除了最頂端外，沒有任何其他方法可以存取stack的其他元素。換言之，stack不允許有遍歷行為。

有元素推入棧的操作稱為:push，將元素推出stack的操作稱為pop.

2. stack沒有迭代器

stack所有元素的進(jìn)出都必須符合”先進(jìn)后出”的條件，只有stack頂端的元素，才有機(jī)會(huì)被外界取用。Stack不提供遍歷功能，也不提供迭代器。

3. stack常用API

1. stack構(gòu)造函數(shù)

stack<T> stkT;//stack采用模板類實(shí)現(xiàn)， stack對(duì)象的默認(rèn)構(gòu)造形式： stack(const stack &stk);//拷貝構(gòu)造函數(shù)

2. stack賦值操作

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

3. stack數(shù)據(jù)存取操作

push(elem);//向棧頂添加元素 pop();//從棧頂移除第一個(gè)元素 top();//返回棧頂元素

4. stack大小操作

empty();//判斷堆棧是否為空 size();//返回堆棧的大小

5. queue

1. queue容器基本概念

queue是一種先進(jìn)先出(First In First Out,FIFO)的數(shù)據(jù)結(jié)構(gòu)，它有兩個(gè)出口，queue容器允許從一端新增元素，從另一端移除元素。

2. queue沒有迭代器

Queue所有元素的進(jìn)出都必須符合”先進(jìn)先出”的條件，只有queue的頂端元素，才有機(jī)會(huì)被外界取用。Queue不提供遍歷功能，也不提供迭代器。

3. queue常用API

1. queue構(gòu)造函數(shù)

queue<T> queT;//queue采用模板類實(shí)現(xiàn)，queue對(duì)象的默認(rèn)構(gòu)造形式： queue(const queue &que);//拷貝構(gòu)造函數(shù)

2. queue存取、插入和刪除操作

push(elem);//往隊(duì)尾添加元素 pop();//從隊(duì)頭移除第一個(gè)元素 back();//返回最后一個(gè)元素 front();//返回第一個(gè)元素

3. queue賦值操作

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

4. queue大小操作

empty();//判斷隊(duì)列是否為空 size();//返回隊(duì)列的大小

6. list容器

1. list容器基本概念

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。

相較于vector的連續(xù)線性空間，list就顯得負(fù)責(zé)許多，它的好處是每次插入或者刪除一個(gè)元素，就是配置或者釋放一個(gè)元素的空間。因此，list對(duì)于空間的運(yùn)用有絕對(duì)的精準(zhǔn)，一點(diǎn)也不浪費(fèi)。而且，對(duì)于任何位置的元素插入或元素的移除，list永遠(yuǎn)是常數(shù)時(shí)間。

List和vector是兩個(gè)最常被使用的容器。

List容器是一個(gè)雙向鏈表。

list采用動(dòng)態(tài)存儲(chǔ)分配，不會(huì)造成內(nèi)存浪費(fèi)和溢出

鏈表執(zhí)行插入和刪除操作十分方便，修改指針即可，不需要移動(dòng)大量元素

鏈表靈活，但是空間和時(shí)間額外耗費(fèi)較大

2. list容器的迭代器

List容器不能像vector一樣以普通指針作為迭代器，因?yàn)槠涔?jié)點(diǎn)不能保證在同一塊連續(xù)的內(nèi)存空間上。List迭代器必須有能力指向list的節(jié)點(diǎn)，并有能力進(jìn)行正確的遞增、遞減、取值、成員存取操作。所謂”list正確的遞增，遞減、取值、成員取用”是指，遞增時(shí)指向下一個(gè)節(jié)點(diǎn)，遞減時(shí)指向上一個(gè)節(jié)點(diǎn)，取值時(shí)取的是節(jié)點(diǎn)的數(shù)據(jù)值，成員取用時(shí)取的是節(jié)點(diǎn)的成員。

由于list是一個(gè)雙向鏈表，迭代器必須能夠具備前移、后移的能力，所以list容器提供的是Bidirectional Iterators.
List有一個(gè)重要的性質(zhì)，插入操作和刪除操作都不會(huì)造成原有l(wèi)ist迭代器的失效。這在vector是不成立的，因?yàn)関ector的插入操作可能造成記憶體重新配置，導(dǎo)致原有的迭代器全部失效，甚至List元素的刪除，也只有被刪除的那個(gè)元素的迭代器失效，其他迭代器不受任何影響。

3. list容器的數(shù)據(jù)結(jié)構(gòu)

list容器不僅是一個(gè)雙向鏈表，而且還是一個(gè)循環(huán)的雙向鏈表。

4. list常用api

1. list構(gòu)造函數(shù)

list<T> lstT;//list采用采用模板類實(shí)現(xiàn),對(duì)象的默認(rèn)構(gòu)造形式： list(beg,end);//構(gòu)造函數(shù)將[beg, end)區(qū)間中的元素拷貝給本身。 list(n,elem);//構(gòu)造函數(shù)將n個(gè)elem拷貝給本身。 list(const list &lst);//拷貝構(gòu)造函數(shù)。

2. list數(shù)據(jù)元素插入和刪除操作

push_back(elem);//在容器尾部加入一個(gè)元素 pop_back();//刪除容器中最后一個(gè)元素 push_front(elem);//在容器開頭插入一個(gè)元素 pop_front();//從容器開頭移除第一個(gè)元素 insert(pos,elem);//在pos位置插e(cuò)lem元素的拷貝，返回新數(shù)據(jù)的位置。 insert(pos,n,elem);//在pos位置插入n個(gè)elem數(shù)據(jù)，無返回值。 insert(pos,beg,end);//在pos位置插入[beg,end)區(qū)間的數(shù)據(jù)，無返回值。 clear();//移除容器的所有數(shù)據(jù) erase(beg,end);//刪除[beg,end)區(qū)間的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置。 erase(pos);//刪除pos位置的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置。 remove(elem);//刪除容器中所有與elem值匹配的元素。

3. list大小操作

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

4. list賦值操作

assign(beg, end);//將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。 assign(n, elem);//將n個(gè)elem拷貝賦值給本身。 list&operator=(const list &lst);//重載等號(hào)操作符 swap(lst);//將lst與本身的元素互換。

5. list數(shù)據(jù)的存取

front();//返回第一個(gè)元素。 back();//返回最后一個(gè)元素。

6. list反轉(zhuǎn)排序

reverse();//反轉(zhuǎn)鏈表，比如lst包含1,3,5元素，運(yùn)行此方法后，lst就包含5,3,1元素。 sort(); //list排序

7. set/multiset 容器

1. set/multiset容器基本概念

1. set容器基本概念

Set的特性是。所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)被排序。Set的元素不像map那樣可以同時(shí)擁有實(shí)值和鍵值，set的元素即是鍵值又是實(shí)值。Set不允許兩個(gè)元素有相同的鍵值。

因?yàn)閟et元素值就是其鍵值，關(guān)系到set元素的排序規(guī)則。如果任意改變set元素值，會(huì)嚴(yán)重破壞set組織。換句話說，set的iterator是一種const_iterator.

set擁有和list某些相同的性質(zhì)，當(dāng)對(duì)容器中的元素進(jìn)行插入操作或者刪除操作的時(shí)候，操作之前所有的迭代器，在操作完成之后依然有效，被刪除的那個(gè)元素的迭代器必然是一個(gè)例外。

2. multiset容器基本概念

multiset特性及用法和set完全相同，唯一的差別在于它允許鍵值重復(fù)。set和multiset的底層實(shí)現(xiàn)是紅黑樹，紅黑樹為平衡二叉樹的一種。

2. set常用API

1. set構(gòu)造函數(shù)

set<T> st;//set默認(rèn)構(gòu)造函數(shù)： mulitset<T> mst; //multiset默認(rèn)構(gòu)造函數(shù): set(const set &st);//拷貝構(gòu)造函數(shù)

2. set賦值操作

set&operator=(const set &st);//重載等號(hào)操作符 swap(st);//交換兩個(gè)集合容器

3. set大小操作

size();//返回容器中元素的數(shù)目 empty();//判斷容器是否為空

4. set插入和刪除操作

insert(elem);//在容器中插入元素。 clear();//清除所有元素 erase(pos);//刪除pos迭代器所指的元素，返回下一個(gè)元素的迭代器。 erase(beg, end);//刪除區(qū)間[beg,end)的所有元素 ，返回下一個(gè)元素的迭代器。 erase(elem);//刪除容器中值為elem的元素。

5. set查找操作

find(key);//查找鍵key是否存在,若存在，返回該鍵的元素的迭代器；若不存在，返回set.end(); count(key);//查找鍵key的元素個(gè)數(shù) lower_bound(keyElem);//返回第一個(gè)key>=keyElem元素的迭代器。 upper_bound(keyElem);//返回第一個(gè)key>keyElem元素的迭代器。 equal_range(keyElem);//返回容器中key與keyElem相等的上下限的兩個(gè)迭代器。

6. set的返回值和指定set排序規(guī)則

//插入操作返回值 void test01() {set<int> s;pair<set<int>::iterator, bool> ret = s.insert(10);if (ret.second) {cout << "插入成功:" << *ret.first << endl;} else {cout << "插入失敗:" << *ret.first << endl;}s.insert(20);ret = s.insert(10);if (ret.second) {cout << "插入成功:" << *ret.first << endl;} else {cout << "插入失敗:" << *ret.first << endl;}}struct MyCompare02 {bool operator()(int v1, int v2) {return v1 > v2;} };//set從大到小 void test02() {srand((unsigned int) time(NULL));//我們發(fā)現(xiàn)set容器的第二個(gè)模板參數(shù)可以設(shè)置排序規(guī)則，默認(rèn)規(guī)則是less<_Kty>set<int, MyCompare02> s;for (int i = 0; i < 10; i++) {s.insert(rand() % 100);}for (set<int, MyCompare02>::iterator it = s.begin(); it != s.end(); it++) {cout << *it << " ";}cout << endl; }//set容器中存放對(duì)象 class Person { public:Person(string name, int age) {this->mName = name;this->mAge = age;}public:string mName;int mAge; };struct MyCompare03 {bool operator()(const Person &p1, const Person &p2) {return p1.mAge > p2.mAge;} };void test03() {set<Person, MyCompare03> s;Person p1("aaa", 20);Person p2("bbb", 30);Person p3("ccc", 40);Person p4("ddd", 50);Person p5("ddd", 50);s.insert(p1);s.insert(p2);s.insert(p3);s.insert(p4);for (set<Person, MyCompare03>::iterator it = s.begin(); it != s.end(); it++) {cout << "Name:" << it->mName << " Age:" << it->mAge << endl;} }

8. map/multimap容器

1. map/multimap基本概念

Map的特性是，所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)排序。Map所有的元素都是pair,同時(shí)擁有實(shí)值和鍵值，pair的第一元素被視為鍵值，第二元素被視為實(shí)值，map不允許兩個(gè)元素有相同的鍵值。

因?yàn)閙ap的鍵值關(guān)系到map元素的排列規(guī)則，任意改變map鍵值將會(huì)嚴(yán)重破壞map組織。如果想要修改元素的實(shí)值，那么是可以的。

Map和list擁有相同的某些性質(zhì)，當(dāng)對(duì)它的容器元素進(jìn)行新增操作或者刪除操作時(shí)，操作之前的所有迭代器，在操作完成之后依然有效，當(dāng)然被刪除的那個(gè)元素的迭代器必然是個(gè)例外。

Multimap和map的操作類似，唯一區(qū)別multimap鍵值可重復(fù)。

Map和multimap都是以紅黑樹為底層實(shí)現(xiàn)機(jī)制。

2. map/multimap常用API

1. map構(gòu)造函數(shù)

map<T1, T2> mapTT;//map默認(rèn)構(gòu)造函數(shù): map(const map &mp);//拷貝構(gòu)造函數(shù)

2. map賦值操作

map&operator=(const map &mp);//重載等號(hào)操作符 swap(mp);//交換兩個(gè)集合容器

3. map大小操作

size();//返回容器中元素的數(shù)目 empty();//判斷容器是否為空

4. map插入數(shù)據(jù)元素操作

map.insert(...); //往容器插入元素，返回pair<iterator,bool> map<int, string> mapStu; // 第一種 通過pair的方式插入對(duì)象 mapStu.insert(pair<int, string>(3, "小張")); // 第二種 通過pair的方式插入對(duì)象 mapStu.inset(make_pair(-1, "校長(zhǎng)")); // 第三種 通過value_type的方式插入對(duì)象 mapStu.insert(map<int, string>::value_type(1, "小李")); // 第四種 通過數(shù)組的方式插入值 mapStu[3] = "小劉"; mapStu[5] = "小王";

5. map刪除操作

clear();//刪除所有元素 erase(pos);//刪除pos迭代器所指的元素，返回下一個(gè)元素的迭代器。 erase(beg,end);//刪除區(qū)間[beg,end)的所有元素 ，返回下一個(gè)元素的迭代器。 erase(keyElem);//刪除容器中key為keyElem的對(duì)組。

6. map查找操作

find(key);//查找鍵key是否存在,若存在，返回該鍵的元素的迭代器；/若不存在，返回map.end(); count(keyElem);//返回容器中key為keyElem的對(duì)組個(gè)數(shù)。對(duì)map來說，要么是0，要么是1。對(duì)multimap來說，值可能大于1。 lower_bound(keyElem);//返回第一個(gè)key>=keyElem元素的迭代器。 upper_bound(keyElem);//返回第一個(gè)key>keyElem元素的迭代器。 equal_range(keyElem);//返回容器中key與keyElem相等的上下限的兩個(gè)迭代器。

9. STL容器使用時(shí)機(jī)

STL容器所提供的都是值(value)寓意，而非引用(reference)寓意，也就是說當(dāng)我們給容器中插入元素的時(shí)候，容器內(nèi)部實(shí)施了拷貝動(dòng)作，將我們要插入的元素再另行拷貝一份放入到容器中，而不是將原數(shù)據(jù)元素直接放進(jìn)容器中，也就是說我們提供的元素必須能夠被拷貝。

vector的使用場(chǎng)景：比如軟件歷史操作記錄的存儲(chǔ)，我們經(jīng)常要查看歷史記錄，比如上一次的記錄，上上次的記錄，但卻不會(huì)去刪除記錄，因?yàn)橛涗浭鞘聦?shí)的描述。

deque的使用場(chǎng)景：比如排隊(duì)購(gòu)票系統(tǒng)，對(duì)排隊(duì)者的存儲(chǔ)可以采用deque，支持頭端的快速移除，尾端的快速添加。如果采用vector，則頭端移除時(shí)，會(huì)移動(dòng)大量的數(shù)據(jù)，速度慢。

vector與deque的比較：

vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的開始位置 卻是不固定的。

如果有大量釋放操作的話，vector花的時(shí)間更少，這跟二者的內(nèi)部實(shí)現(xiàn)有關(guān)。

deque支持頭部的快速插入與快速移除，這是deque的優(yōu)點(diǎn)。

list的使用場(chǎng)景：比如公交車乘客的存儲(chǔ)，隨時(shí)可能有乘客下車，支持頻繁的不確實(shí)位置元素的移除插入。

set的使用場(chǎng)景：比如對(duì)手機(jī)游戲的個(gè)人得分記錄的存儲(chǔ)，存儲(chǔ)要求從高分到低分的順序排列。

map的使用場(chǎng)景：比如按ID號(hào)存儲(chǔ)十萬個(gè)用戶，想要快速要通過ID查找對(duì)應(yīng)的用戶。二叉樹的查找效率，這時(shí)就體現(xiàn)出來了。如果是vector容器，最壞的情況下可能要遍歷完整個(gè)容器才能找到該用戶。

總結(jié)

以上是生活随笔為你收集整理的C/C++学习之路: STL的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。