标准模板库之容器-《C++标准库(第二版)》读书笔记
寫在前面：本文是閱讀《C++標準庫(第二版)》的讀書筆記。
文章目錄
- 6.1 STL組件（Component）
- 6.2 容器(Container)
- 6.2.1 序列式容器(Sequence container)
- vector
- Deque
- Array
- List
- 6.2.2 關(guān)聯(lián)式容器(Associative container）
- Set 和Multiset 實例
- Map和Multimap 實例
- 6.2.3 無序容器(Unordered container）
- unordered set/multiset 實例
- unordered map/multimap實例
6.1 STL組件（Component）
若干組件精心合作，構(gòu)筑起STL的基礎(chǔ)。 這些組件中最關(guān)鍵的是容器、迭代器和算法。
-
容器（Container），用來管理某類對象的集合。每一種容器都有其優(yōu)點和缺點，所以，為了應(yīng)付不同的需求，STL準備了不同的容器類型。容器可以是array或linked list，或者每個元素有一個特別的key。
-
迭代器（Iterator），用來在一個對象集合內(nèi)遍歷元素。這個對象集合或許是一個容器，或許是容器的一部分。迭代器的主要好處是，為所有各式各樣的容器提供了一組很小的共通接口。例如其中一個操作是行進至集合內(nèi)的下一個元素。至于如何做到當然取決于集合的內(nèi)部結(jié)構(gòu)。不論這個集合是array或tree或hash table，此一行進動作都能成功，因為每一種容器都提供了自己的迭代器，而這些迭代器了解容器的內(nèi)部結(jié)構(gòu)，知道該做些什么。
迭代器的接口和尋常的pointer差不多，調(diào)用operator++就累進，調(diào)用operator * 就訪問被指向的值。所以你可以把迭代器視為一種 smart pointer，能夠把“前進到下一元素”的意圖轉(zhuǎn)換為合適的操作。
-
算法（Algorithm），用來處理集合內(nèi)的元素。它們可以出于不同目的而查找、排序、修改、使用元素。通過迭代器的協(xié)助，我們只需要撰寫一次算法，就可以將它應(yīng)用到任意容器，因為所有容器的迭代器都提供一致的接口。
你還可以提供一些特殊的輔助函數(shù)供算法調(diào)用，從而獲取更佳的靈活性，這樣你就可以一方面運用標準算法，一方面配合自己特殊或復(fù)雜的需求。例如，你可以提供自己的查找準則（search criterion）或元素合并時的特殊操作。特別是C++11新引入了lambda，你得以輕松地指明在容器元素上進行任何種類的操作。
STL的基本觀念就是將數(shù)據(jù)和操作分離。數(shù)據(jù)由容器類加以管理，操作則由可定制的算法定義之。 迭代器在兩者之間充當粘合劑，使得任何算法都可以和任何容器交互作用。
STL的一個根本特性是，所有組件都可以針對任意類型運作。顧名思義，所謂的standard template library 意味著其內(nèi)的所有組件都是“可接受任意類型”的template，前提是這些類型必須能夠執(zhí)行必要的操作。因此STL成為了泛型編程概念下的一個出色范例。容器和算法被泛化為可適用于任意type和class。
6.2 容器(Container)
容器用來管理一大群元素。 為了適應(yīng)不同需求，STL提供了不同的容器。
總的來說，容器可分為三大類：
6.2.1 序列式容器(Sequence container)
STL內(nèi)部預(yù)先定義好了以下序列式容器：
- Array(其class 名為array)
- Vector
- Deque
- List(singly/doubly linked)
vector
vector將其元素放在一個dynamic array 中管理。 它允許隨機訪問，也就是說，你可以利用索引直接訪問任何一個元素。在array尾部附加元素或移除元素都很快速，但是在array內(nèi)部安插元素就比較費時。
以下例子針對整數(shù)類型定義了一個vector，插入6個元素，然后打印所有元素：
#include<iostream> #include<vector> using namespace std;int main(){vector<int> coll; //vector container for integer elements//append elements with values 1 to 6for(int i=1;i<=6;i++)coll.push_back(i);//print all elements followed by a spacefor(int i=0;i<coll.size();i++)cout<<coll[i]<<" ";cout<<endl; }Deque
所謂deque，是“double-ended queue”的縮寫。它是一個dynamic array，可以向兩端發(fā)展，因此不論在尾部或頭部安插元素都十分迅速。在中間部分安插元素則比較費時，因此必須移動其他元素。
以下例子聲明了一個元素為浮點數(shù)的deque，并在容器頭部安插1.1 到6.6 供6個元素，最后打印出來所有元素。
#include<iostream> #include<deque> using namespace std;int main(){deque<float> coll;//insert elements form 1.1 to 6.6 each at the frontfor(int i=1;i<=6;i++)coll.push_front(i*1.1); //insert at the front//print all elements followed by a spacefor(int i=0;i<coll.size();i++)cout<<coll[i]<<" ";cout<<endl; }本例中，下面這一行將deque的頭文件包含進來：
#include<deque>下面的聲明則是產(chǎn)生一個空的浮點數(shù)集合：
deque<float> coll;push_front()函數(shù)用來安插元素：
coll.push_front(i*1.1);push_front()會將元素安插在集合前端。注意，這種安插方式造成的結(jié)果是，元素排放次序于安插次序恰好相反，因為每個元素都安插在上一個元素的前面。程序輸出結(jié)果如下：
6.6 5.5 4.4 3.3 2.2 1.1你也可以使用成員函數(shù)push_back()在deque尾部附加元素。vector并未提供push_front()，因為其時間效率不佳（在vector頭部安插一個元素，需要先移動全部元素）。一般而言，STL容器只提供具備良好時間效率的成員函數(shù)，所謂“良好”通常意味著其復(fù)雜度為常數(shù)或者對數(shù)，以免程序員調(diào)用性能很差的函數(shù)。
Array
一個array對象是在某個固定大小的array（有時稱為一個static array 或C array）內(nèi)管理元素。因此，你不可以改變元素個數(shù)，只能改變元素值。 必須在建立時就指明其大小。 array允許隨機訪問，意思是可以直接訪問任何一個元素，只要指定相應(yīng)的索引。
下面定義了一個array，元素是string
#include<bits/stdc++.h> using namespace std;int main(){//array container of 5 string elementsarray<string,5> coll= {"hello", "world"};//print each element with its index on a linefor(int i=0; i<coll.size() ; i++)cout<< i<< ": "<< coll[i]<<endl; }一般array 的頭文件是
#include<array>以下聲明式會建立一個array，帶有5個類型為string 的元素：
array <string ,5> coll;默認情況是這些元素都被元素的default構(gòu)造函數(shù)初始化。這意味著，對基礎(chǔ)類型而言， 初值不明確。
然后本程序使用了一個初值列，這東西允許我們以一系列值將對象初始化與創(chuàng)建期。自C++11起這種初始化方法受到每一種容器的支持，所以當然我們可以在vector和deque中使用它。 既然如此，基礎(chǔ)類型用的是zero initialization，意味著基礎(chǔ)類型保證被初始化為0.
注意，元素個數(shù)是array類型的一部分。因此array <int ,5> 和 array<int, 10> 是兩個不同的類型，你不能對此兩者進行復(fù)制或比較。
List
C++11起，STL竟然提供了兩個不同的list容器：class list< > 和 class forward_list< > 。因此，list可能表示其中某個class，或者是個總體術(shù)語，代表上述兩個list class。 然后就某種程度而言， forward list 只不過是受到更多限制的list ， 現(xiàn)實中兩者的差異并不這么重要。 因此當我使用術(shù)語list ，通常我指的是class list< > ，它的能力往往超越class forward_list< > 。
list< > 由雙向鏈表(double linked list)實現(xiàn)而成。 這意味著list內(nèi)的每個元素都以一部分內(nèi)存指示其前導(dǎo)元素和后繼元素。
list不提供隨機訪問，因此如果你要訪問第10個元素，必須沿著鏈表依次走過前9個元素。不過，移動到下一個元素或著前一個元素的行為，可以在常量時間內(nèi)完成。 因此一般的元素訪問動作會發(fā)揮線性時間，因為平均距離和元素數(shù)量成正比。 這比vector 和deque提供的常量時間，效率差很多。
list的優(yōu)勢是：在任何位置上執(zhí)行安插或刪除動作都十分迅速，因為只需要改變鏈接就好。 這表示在list 中段處移動元素比在vector和deque快得多。
以下例子產(chǎn)生一個空list， 用以放置字符， 然后將‘a(chǎn)’ 到’z’的所有字符插入其中，利用循環(huán)每次打印并移除集合中的第一個元素，從而打印所有元素：
#include<bits/stdc++.h> using namespace std;int main(){list<char> coll;// list container for character elements//append elements from 'a' to 'z'for(char c='a';c<='z';c++)coll.push_back(c);//printfor(auto elem: coll){cout<< elem <<" ";}cout<<endl; }輸出結(jié)果
a b c d e f g h i j k l m n o p q r s t u v w x y zlist需要包含頭文件
#include<list>以下定義了一個“元素類型為字符”的list：
list<char> coll;為了打印所有元素，使用了一個基于范圍的for循環(huán)，這種循環(huán)自C++11開始提供，允許對每個元素執(zhí)行指定的語句。list并不提供作為“元素直接訪問”指用的操作符[ ] 。這是因為list并不提供隨機訪問，因此操作符 [ ] 會帶來低下的效率。
在此循環(huán)中，當前正在被處理的coll元素的類型被聲明為auto 。因此elem的類型被自動推導(dǎo)為char，因為coll是個char集合。另一種做法是明白聲明elem的類型：
for (char elem :coll){ }比如
list<int> ll;for(int i=0;i<4;i++)ll.push_back(i);for(int elem:ll)cout<< elem<<" ";cout<<endl;輸出結(jié)果是 0 1 2 3
注意，elem永遠是當前正被處理的元素的一個拷貝(copy)。雖然你可以改動它，但其影響只限于“針對此元素而調(diào)用的語句”，coll內(nèi)部并沒有任何東西被改變。 如果你想改動傳入的集合的元素，你必須將elem聲明為一個非常量的reference：
for(auto& elem : coll){... }就像函數(shù)的參數(shù)那樣，通常你應(yīng)該使用一個常量reference 以避免發(fā)生一次copy操作。因此下面的function template 輸出“被傳入的容器內(nèi)的所有元素”：
template<typename T>void printElements(const T& coll){for(const auto & elem: coll)cout<<elem<<endl; }在C++11之前，打印所有元素的另一做法（不使用迭代器）是逐一地“打印而后移除”第一元素，直到此list之中不再有任何元素：
#include<bits/stdc++.h> using namespace std;int main(){list<char> coll;for(char c='a';c<='z';c++)coll.push_back(c);//print//print and remove the first element while(!coll.empty()){cout<<coll.front()<<" ";coll.pop_front();} cout<<endl; }輸出結(jié)果：
a b c d e f g h i j k l m n o p q r s t u v w x y z成員函數(shù)empty()的返回值告訴我們?nèi)萜髦惺欠襁€有元素。只要這個函數(shù)返回false（也就是說，容器內(nèi)還有元素），循環(huán)就繼續(xù)進行：
while(! coll.emtpy() ){ ... }循環(huán)之內(nèi)，成員函數(shù)front()返回第一個元素：
cout<< coll.front()<<" ";pop_front()函數(shù)刪除第一個元素:
coll.pop_front();注意，pop_front()并不會返回被刪除的元素，所以你無法將上述兩個語句合二為一。
6.2.2 關(guān)聯(lián)式容器(Associative container）
關(guān)聯(lián)式容器依據(jù)特定的排序準則，自動為其元素排序。 元素可以是任何類型的value，也可以是key /value pair，其中key可以是任何類型，映射到一個相關(guān)value ，而value 也可以是任意類型。 排序準則以函數(shù)形式呈現(xiàn)，用來比較value，或比較key /value pair 中的key 。默認情況下所有容器都以操作符< 進行比較，不過你也可以提供自己的比較函數(shù)，定義出不同的排序準則。
通常關(guān)聯(lián)式容器由二叉樹實現(xiàn)出來。 在二叉樹中，每個元素（結(jié)點）都有一個父節(jié)點和兩個子結(jié)點。左子樹的所有元素都比自己小，右子樹的所有元素都比自己大。關(guān)聯(lián)式容器的差別主要在于元素的種類以及處理重復(fù)元素時的方式。
關(guān)聯(lián)式容器的主要優(yōu)點是：它能很快找出一個具有某特定value 的元素，因為它具備對數(shù)復(fù)雜度，而任何循環(huán)式容器的復(fù)雜度是線性。 因此，使用關(guān)聯(lián)式容器，面對1000個元素，平均而言只需要10此而不是500次比較動作。然后它的一個缺點是，你不能直接改動元素的 value，因為那會破壞元素的自動排序。
下面是STL定義的關(guān)聯(lián)式容器：
- set： 元素依據(jù)其value 自動排序，每個元素只能出現(xiàn)一次，不允許重復(fù)。
- multiset：和set的唯一區(qū)別是：元素可以重復(fù)。也就是multiset可包括多個“value相同”的元素。
- map：每個元素都是key/value pair,其中key 是排序準則的基準。 每個key只能出現(xiàn)一次，不允許重復(fù)。map可被視為一種關(guān)聯(lián)式數(shù)組(associative array)，也就是“索引可以為任意類型”的數(shù)組。
- multimap：和map的唯一區(qū)別是：元素可以重復(fù)，也就是multimap允許其元素擁有相同的key。multimap可被當作字典使用。
Set 和Multiset 實例
下面看一個例子，使用multiset：
#include<set> #include<string> #include<iostream>using namespace std;int main(){multiset<string> cities {"Braunschweig", "hanover", "Frankfurt", "New York","Chicago","Toronto" ,"Paris" ,"Frankfurt"};//printfor(const auto& elem: cities)cout<<elem<<" ";cout<<endl;//insert additional values:cities.insert({"London","Munich","Hanover","Braunschweig"});//printfor(const auto& elem: cities)cout<<elem<<" ";cout<<endl; }輸出結(jié)果
包含頭文件< set>后，可以聲明cities是個以string為元素的multiset：
multiset< string> cities聲明之后，若干字符串以初值列形式成為元素初值。容器內(nèi)部已經(jīng)排好序。
multiset允許元素重復(fù)，如果聲明成set，則不允許元素重復(fù)。
Map和Multimap 實例
下面的例子示范了如何使用map和multimap：
#include<map> #include<iostream> #include<string>using namespace std;int main(){multimap<int,string> coll; // container for int/string values//insertcoll={{5,"tagged"},{2,"a"},{1,"this"},{4,"of"},{6,"strings"},{1,"is"},{3,"multimap"}};//printfor(auto c:coll){cout<< c.second<<" ";}cout<<endl; }運行結(jié)果
this is a multimap of tagged strings
包含< map >之后， 我們聲明了一個map，其元素擁有一個int作為key和一個string作為value：
multimap<int,string> coll;6.2.3 無序容器(Unordered container）
在無序容器中，元素沒有明確的排列次序。 我們唯一關(guān)心的是，某個特定元素是否位于容器內(nèi)。無序容器常以hash table實現(xiàn)出來，內(nèi)部結(jié)構(gòu)是一個 由linked list組成的array。 通過某個hash函數(shù)的運算，確定元素落于這個array的位置。hash函數(shù)運算的目標是：讓每個元素的位置有助于用戶快速訪問任何一個元素，前提則是hash函數(shù)本身足夠快。 基本上就是 數(shù)組和鏈表的搭配。
無序容器的主要優(yōu)點是：當你打算查找一個帶某特定值的元素，其速度甚至可能快過關(guān)聯(lián)式容器。當你有一個良好的hash函數(shù)時， 查找速度為O(1)。 然后提供一個良好的hash函數(shù)并非易事，可能需要提供許多內(nèi)存作為bucket。
STL定義出下面這些無序容器：
unordered set/multiset 實例
下面是一個例子，使用unorder_multiset ，元素是string
#include<iostream> #include<string> #include<unordered_set> using namespace std;int main(){unordered_multiset<string > cities {"Braunschweig", "hanover", "Frankfurt", "New York","Chicago","Toronto" ,"Paris" ,"Frankfurt"};//printfor(const auto& c:cities)cout<<c<<" ";cout<<endl;//insertcities.insert({"Shanghai","Beijing","Chongqing","Rizhao"});//printfor(const auto& s:cities)cout<<s<<" ";cout<<endl;}輸出結(jié)果
Paris Toronto Chicago New York Frankfurt Frankfurt hanover Braunschweig Rizhao Chongqing Beijing Shanghai Frankfurt Frankfurt New York Braunschweig Chicago hanover Toronto Paris打印所有元素，出現(xiàn)的次序可能不同于程序中所給的次序，因為其次序是不明確的。
unordered map/multimap實例
需要包含
#include<unordered_map>unordered_multimap<int,string>coll;總結(jié)
以上是生活随笔為你收集整理的标准模板库之容器-《C++标准库(第二版)》读书笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Leetcode5635. 构建字典序最
- 下一篇： 《C和指针》读书笔记第三章数据