STL實(shí)用技術(shù)專題
STL的從廣義上講分為三類： algorithm （算法）、container （容器）和iterator （迭代器），
STL詳細(xì)的說六大組件
– 容器（ Container ）
– 算法（ Algorithm ）
– 迭代器（ Iterator ）
– 仿函數(shù)（ Function object ）
– 適配器（ Adaptor）
– 空間配制器（ allocator ）
1. string
string 和char* 的比較：
string 是一個(gè)類, char* 是一個(gè)指向字符的指針。
string 封裝了char* ，管理這個(gè)字符串，是一個(gè)char* 型的容器。
string 不用考慮內(nèi)存釋放和越界。
string 封裝相關(guān)函數(shù)。
相關(guān)函數(shù)
const char *c_str() const; // 從string 取得const char* 的操作
string &operator+=(const string &s); // 把字符串s 連接到當(dāng)前字符串結(jié)尾
string &operator+=(const char *s); // 把字符串s 連接到當(dāng)前字符串結(jié)尾
int compare(const string &s) const; // 與字符串s 比較
int compare(const char *s) const; // 與字符串s 比較
string substr(int pos=0, int n=npos) const; // 返回由pos 開始的n 個(gè)字符組成的子字符串
find以及rfind函數(shù)。
replace函數(shù)
insert函數(shù)
erase函數(shù)
相關(guān)算法：
transform(s2.begin(), s2.end(), s2.begin(), toupper);
transform(s3.begin(), s3.end(), s3.begin(), tolower);
2. Vector
向量是表示可以改變大小的數(shù)組的序列容器。
就像數(shù)組一樣，向量使用連續(xù)的存儲(chǔ)位置作為元素，這意味著它們的元素也可以使用常量指向其元素的偏移來訪問，并且與數(shù)組一樣有效。但與數(shù)組不同，它們的大小可以動(dòng)態(tài)變化，其存儲(chǔ)由容器自動(dòng)處理。
在內(nèi)部，向量使用動(dòng)態(tài)分配的數(shù)組來存儲(chǔ)它們的元素。可能需要重新分配此數(shù)組，以便在插入新元素時(shí)增大大小，這意味著分配新數(shù)組并將所有元素移動(dòng)到該數(shù)組。就處理時(shí)間而言，這是相對(duì)昂貴的任務(wù)，因此，每次將元素添加到容器時(shí)，向量都不會(huì)重新分配。
相反，矢量容器可以分配一些額外的存儲(chǔ)空間以適應(yīng)可能的增長，因此容器的實(shí)際容量可能大于包含其元素所需的存儲(chǔ)容量（即，其大?。?。庫可以實(shí)現(xiàn)不同的增長策略以在內(nèi)存使用和重新分配之間取得平衡，但無論如何，重新分配只應(yīng)以對(duì)數(shù)增長的大小間隔發(fā)生，以便在向量末尾插入單個(gè)元素可以提供攤銷的常量時(shí)間復(fù)雜性（見push_back）。
因此，與數(shù)組相比，向量消耗更多內(nèi)存，以換取管理存儲(chǔ)和以有效方式動(dòng)態(tài)增長的能力。
與其他動(dòng)態(tài)序列容器（deques，lists和forward_lists）相比，向量非常有效地訪問其元素（就像數(shù)組一樣）并且相對(duì)有效地從其末尾添加或刪除元素。對(duì)于涉及在末尾以外的位置插入或刪除元素的操作，它們的性能比其他位置差，并且與列表和forward_lists相比具有更少的一致的迭代器和引用。
相關(guān)函數(shù)
vector.size(); // 返回容器中元素的個(gè)數(shù)
vector.capacity() // 分配的內(nèi)存大小
vector.empty(); // 判斷容器是否為空
3. deque
雙端隊(duì)列
deque（通常發(fā)音為“deck”）是雙端隊(duì)列的不規(guī)則首字母縮寫。雙端隊(duì)列是具有動(dòng)態(tài)大小的序列容器，可以在兩端（前端或后端）擴(kuò)展或收縮。
特定庫可以以不同方式實(shí)現(xiàn)deques，通常作為某種形式的動(dòng)態(tài)數(shù)組。但無論如何，它們?cè)试S通過隨機(jī)訪問迭代器直接訪問各個(gè)元素，并根據(jù)需要通過擴(kuò)展和收縮容器來自動(dòng)處理存儲(chǔ)。
因此，它們提供類似于vector的功能，但是在序列的開頭也有效地插入和刪除元素，而不僅僅是在其結(jié)尾。但是，與向量不同，deques不能保證將其所有元素存儲(chǔ)在連續(xù)的存儲(chǔ)位置：通過將指針偏移到另一個(gè)元素來訪問雙端隊(duì)列中的元素會(huì)導(dǎo)致未定義的行為。
vector和deque都提供了一個(gè)非常相似的接口，可以用于類似的目的，但內(nèi)部都以完全不同的方式工作：雖然矢量使用需要偶爾重新分配以生長的單個(gè)數(shù)組，但是deque的元素可以分散在不同的存儲(chǔ)塊，容器在內(nèi)部保存必要的信息，以便在恒定的時(shí)間內(nèi)通過統(tǒng)一的順序接口（通過迭代器）直接訪問其任何元素。因此，deques在內(nèi)部比矢量稍微復(fù)雜一些，但是這允許它們?cè)谀承┣闆r下更有效地生長，特別是在非常長的序列中，其中重新分配變得更加昂貴。
對(duì)于涉及在開頭或結(jié)尾以外的位置頻繁插入或刪除元素的操作，deques表現(xiàn)更差，并且與列表和轉(zhuǎn)發(fā)列表相比具有更少的一致的迭代器和引用。
相關(guān)函數(shù)
deque.push_back(elem); // 在容器尾部添加一個(gè)數(shù)據(jù)
deque.push_front(elem); // 在容器頭部插入一個(gè)數(shù)據(jù)
deque.pop_back(); // 刪除容器最后一個(gè)數(shù)據(jù)
deque.pop_front(); // 刪除容器第一個(gè)數(shù)據(jù)
deque.at(idx); // 返回索引idx 所指的數(shù)據(jù)，如果idx 越界，拋出out_of_range 。
deque[idx]; // 返回索引idx 所指的數(shù)據(jù)，如果idx 越界，不拋出異常，直接出錯(cuò)。
deque.front(); // 返回第一個(gè)數(shù)據(jù)。
deque.back(); // 返回最后一個(gè)數(shù)據(jù)
4. stack
stack 是簡(jiǎn)單地裝飾deque 容器而成為另外的一種容器。
LIFO堆棧
堆棧是一種容器適配器，專門設(shè)計(jì)用于在LIFO上下文中操作（后進(jìn)先出），其中元素僅從容器的一端插入和提取。
堆棧實(shí)現(xiàn)為容器適配器，它是使用特定容器類的封裝對(duì)象作為其底層容器的類，提供一組特定的成員函數(shù)來訪問其元素。 元素從特定容器的“后面”推出/彈出，該容器稱為堆棧頂部。
底層容器可以是任何標(biāo)準(zhǔn)容器類模板或一些其他專門設(shè)計(jì)的容器類。
相關(guān)函數(shù)
stack.push(elem); // 往棧頭添加元素
stack.pop(); // 從棧頭移除第一個(gè)元素
stack.empty(); // 判斷堆棧是否為空
stack.size(); // 返回堆棧的大小
5.1 queue
FIFO隊(duì)列
隊(duì)列是一種容器適配器，專門設(shè)計(jì)用于在FIFO上下文中操作（先進(jìn)先出），其中元素插入容器的一端并從另一端提取。
隊(duì)列實(shí)現(xiàn)為容器適配器，它是使用特定容器類的封裝對(duì)象作為其底層容器的類，提供一組特定的成員函數(shù)來訪問其元素。 元素被推入特定容器的“后面”并從其“前面”彈出。
底層容器可以是標(biāo)準(zhǔn)容器類模板之一或其他一些專門設(shè)計(jì)的容器類。
相關(guān)函數(shù)
queue.push(elem); // 往隊(duì)尾添加元素
queue.pop(); // 從隊(duì)頭移除第一個(gè)元素
queue.empty(); // 判斷隊(duì)列是否為空
queue.size(); // 返回隊(duì)列的大小
queue.back(); // 返回最后一個(gè)元素
queue.front(); // 返回第一個(gè)元素
5.2 priority_queue
優(yōu)先隊(duì)列
優(yōu)先級(jí)隊(duì)列是一種容器適配器，根據(jù)一些嚴(yán)格的弱排序標(biāo)準(zhǔn)，專門設(shè)計(jì)使其第一個(gè)元素始終是它包含的最大元素。
此容器類似于堆，其中可以隨時(shí)插入元素，并且只能檢索最大堆元素（優(yōu)先級(jí)隊(duì)列中頂部的元素）。
優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)為容器適配器，它是使用特定容器類的封裝對(duì)象作為其底層容器的類，提供一組特定的成員函數(shù)來訪問其元素。元素從特定容器的“后面”彈出，該容器稱為優(yōu)先級(jí)隊(duì)列的頂部。
底層容器可以是任何標(biāo)準(zhǔn)容器類模板或一些其他專門設(shè)計(jì)的容器類。容器應(yīng)通過隨機(jī)訪問迭代器訪問。
相關(guān)函數(shù)
priority_queue<int> p1; // 默認(rèn)是最大值優(yōu)先級(jí)隊(duì)列
//priority_queue<int, vector<int>, less<int>> p1; // 相當(dāng)于這樣寫
priority_queue<int, vector<int>, greater<int>> p2; // 最小值優(yōu)先級(jí)隊(duì)列
6. list
列表是序列容器，允許在序列中的任何位置進(jìn)行恒定時(shí)間插入和擦除操作，并在兩個(gè)方向上進(jìn)行迭代。
列表容器實(shí)現(xiàn)為雙向鏈表;雙向鏈表可以將它們包含的每個(gè)元素存儲(chǔ)在不同且不相關(guān)的存儲(chǔ)位置中。排序由內(nèi)部保留，鏈接到前面元素的鏈接的每個(gè)元素，以及到它后面的元素的鏈接。
它們與forward_list非常相似：主要區(qū)別在于forward_list對(duì)象是單鏈接列表，因此它們只能向前迭代，以換取更小和更高效。
與其他基本標(biāo)準(zhǔn)序列容器（數(shù)組，向量和雙端隊(duì)列）相比，列表在插入，提取和移動(dòng)已經(jīng)獲得迭代器的容器內(nèi)的任何位置中的元素時(shí)通常表現(xiàn)更好，因此也在使用密集型的算法中其中，就像排序算法一樣。
與其他序列容器相比，list和forward_lists的主要缺點(diǎn)是它們無法通過位置直接訪問元素;例如，要訪問列表中的第六個(gè)元素，必須從已知位置（如開頭或結(jié)尾）迭代到該位置，這將在這些位置之間的距離中采用線性時(shí)間。它們還消耗一些額外的內(nèi)存來保持與每個(gè)元素相關(guān)聯(lián)的鏈接信息（這可能是大型小元素列表的重要因素）。
相關(guān)函數(shù)
list.push_back(elem); // 在容器尾部加入一個(gè)元素
list.pop_back(); // 刪除容器中最后一個(gè)元素
list.push_front(elem); // 在容器開頭插入一個(gè)元素
list.pop_front(); // 從容器開頭移除第一個(gè)元素
7.1 set
集合是按特定順序存儲(chǔ)唯一元素的容器。
在集合中，元素的值也標(biāo)識(shí)它（值本身是類型T的鍵），并且每個(gè)值必須是唯一的。 集合中元素的值不能在容器中修改一次（元素總是const），但可以在容器中插入或刪除它們。
在內(nèi)部，集合中的元素總是按照其內(nèi)部比較對(duì)象（類型比較）指示的特定嚴(yán)格弱排序標(biāo)準(zhǔn)進(jìn)行排序。
set容器通常比unordered_set容器慢，以便通過鍵訪問單個(gè)元素，但它們?cè)试S根據(jù)子集的順序直接迭代子集。
集合通常實(shí)現(xiàn)為二叉搜索樹。
7.2 multiset
multiset是按特定順序存儲(chǔ)元素的容器，多個(gè)元素可以具有等效值。
在multiset中，元素的值也標(biāo)識(shí)它（值本身是T類型的鍵）。 多個(gè)集合中元素的值不能在容器中修改一次（元素總是const），但可以在容器中插入或刪除它們。
在內(nèi)部，多集合中的元素總是按照其內(nèi)部比較對(duì)象（類型比較）指示的特定嚴(yán)格弱排序標(biāo)準(zhǔn)進(jìn)行排序。
multiset容器通常比unordered_multiset容器慢，以便通過其鍵訪問單個(gè)元素，但它們?cè)试S根據(jù)子集的順序直接迭代子集。
multiset通常實(shí)現(xiàn)為二叉搜索樹。
8.1 map
map是關(guān)聯(lián)容器，它按照特定順序存儲(chǔ)由鍵值和映射值的組合形成的元素。
在映射中，鍵值通常用于排序和唯一標(biāo)識(shí)元素，而映射值存儲(chǔ)與此鍵關(guān)聯(lián)的內(nèi)容。鍵和映射值的類型可能不同，并在成員類型value_type中組合在一起，這是一種結(jié)合兩者的對(duì)類型：
typedef pair <const Key，T> value_type;
在內(nèi)部，map中的元素總是按照其內(nèi)部比較對(duì)象（類型比較）指示的特定嚴(yán)格弱排序標(biāo)準(zhǔn)按其鍵排序。
map容器通常比unordered_map容器慢，以便通過鍵訪問單個(gè)元素，但它們?cè)试S根據(jù)子集的順序直接迭代子集。
可以使用括號(hào)運(yùn)算符（（operator []）通過相應(yīng)的鍵直接訪問映射中的映射值。
map通常實(shí)現(xiàn)為二叉搜索樹。
8.2 multimap
Multimaps是關(guān)聯(lián)容器，用于存儲(chǔ)由鍵值和映射值的組合形成的元素，遵循特定順序，并且多個(gè)元素可以具有等效鍵。
在multimap中，鍵值通常用于排序和唯一標(biāo)識(shí)元素，而映射值存儲(chǔ)與此鍵關(guān)聯(lián)的內(nèi)容。 鍵和映射值的類型可能不同，并在成員類型value_type中組合在一起，這是一種結(jié)合兩者的對(duì)類型：
typedef pair <const Key，T> value_type;
在內(nèi)部，多圖中的元素總是按照其內(nèi)部比較對(duì)象（類型比較）指示的特定嚴(yán)格弱排序標(biāo)準(zhǔn)按其鍵排序。
multimap容器通常比unordered_multimap容器慢，以通過其鍵訪問單個(gè)元素，但它們?cè)试S根據(jù)子集的順序直接迭代子集。
multimap通常實(shí)現(xiàn)為二叉搜索樹。
以下是 C++11 新增的
9. array
數(shù)組是固定大小的序列容器：它們包含以嚴(yán)格線性序列排序的特定數(shù)量的元素。
在內(nèi)部，數(shù)組不保留除其包含的元素之外的任何數(shù)據(jù)（甚至不是它的大小，這是一個(gè)模板參數(shù)，在編譯時(shí)固定）。它在存儲(chǔ)大小方面與使用語言括號(hào)語法（[]）聲明的普通數(shù)組一樣高效。這個(gè)類只是為它添加了一層成員函數(shù)和全局函數(shù)，因此數(shù)組可以用作標(biāo)準(zhǔn)容器。
與其他標(biāo)準(zhǔn)容器不同，數(shù)組具有固定大小，并且不通過分配器管理其元素的分配：它們是封裝固定大小元素?cái)?shù)組的聚合類型。因此，它們不能動(dòng)態(tài)擴(kuò)展或收縮（參見可擴(kuò)展的類似容器的向量）。
零大小的數(shù)組是有效的，但不應(yīng)該取消引用它們（成員前面，后面和數(shù)據(jù)）。
與標(biāo)準(zhǔn)庫中的其他容器不同，交換兩個(gè)數(shù)組容器是一種線性操作，涉及單獨(dú)交換范圍中的所有元素，這通常是效率相當(dāng)?shù)偷牟僮?。另一方面，這允許兩個(gè)容器中的元素的迭代器保持其原始容器關(guān)聯(lián)。
數(shù)組容器的另一個(gè)獨(dú)特功能是它們可以被視為元組對(duì)象：<array>頭重載get函數(shù)以訪問數(shù)組的元素，就像它是一個(gè)元組一樣，以及專門的tuple_size和tuple_element類型。
10. forward_list
前向列表是序列容器，允許在序列中的任何位置進(jìn)行恒定時(shí)間插入和擦除操作。
forward_list實(shí)現(xiàn)為單鏈表;單個(gè)鏈接列表可以將它們包含的每個(gè)元素存儲(chǔ)在不同且不相關(guān)的存儲(chǔ)位置中。通過關(guān)聯(lián)到序列中下一個(gè)元素的鏈接的每個(gè)元素來保持排序。
forward_list容器和list容器之間的主要設(shè)計(jì)區(qū)別在于，第一個(gè)容器內(nèi)部僅保留指向下一個(gè)元素的鏈接，而后者每個(gè)元素保留兩個(gè)鏈接：一個(gè)指向下一個(gè)元素，一個(gè)指向前一個(gè)元素，從而有效在兩個(gè)方向上迭代，但每個(gè)元素消耗額外的存儲(chǔ)空間，并且插入和移除元素的時(shí)間略微增加。因此，forward_list對(duì)象比列表對(duì)象更有效，盡管它們只能向前迭代。
與其他基本標(biāo)準(zhǔn)序列容器（數(shù)組，向量和雙端隊(duì)列）相比，forward_list通常在容器內(nèi)的任何位置插入，提取和移動(dòng)元素時(shí)執(zhí)行得更好，因此也可以在大量使用這些元素的算法中執(zhí)行，例如排序算法。
與其他序列容器相比，forward_lists和list的主要缺點(diǎn)是它們無法通過位置直接訪問元素;例如，要訪問forward_list中的第六個(gè)元素，必須從開頭到該位置進(jìn)行迭代，這需要在它們之間的距離內(nèi)采用線性時(shí)間。它們還消耗一些額外的內(nèi)存來保持與每個(gè)元素相關(guān)聯(lián)的鏈接信息（這可能是大型小元素列表的重要因素）。
forward_list類模板的設(shè)計(jì)考慮了效率：通過設(shè)計(jì)，它與簡(jiǎn)單的手寫C風(fēng)格單鏈表一樣高效，實(shí)際上是唯一一個(gè)為了提高效率而故意缺乏大小成員函數(shù)的標(biāo)準(zhǔn)容器：由于其作為鏈接列表的性質(zhì)，具有持續(xù)時(shí)間的大小成員將要求它保持其大小的內(nèi)部計(jì)數(shù)器（如列表所示）。這將消耗一些額外的存儲(chǔ)空間，并使插入和移除操作的效率略低。要獲取forward_list對(duì)象的大小，可以使用距離算法及其開始和結(jié)束，這是一個(gè)需要線性時(shí)間的操作。
11.1 unordered_set
unordered_set是不按特定順序存儲(chǔ)唯一元素的容器，它允許根據(jù)單個(gè)元素的值快速檢索單個(gè)元素。
在unordered_set中，元素的值同時(shí)是其鍵，它唯一地標(biāo)識(shí)它。 鍵是不可變的，因此，unordered_set中的元素不能在容器中修改一次 - 但是可以插入和刪除它們。
在內(nèi)部，unordered_set中的元素不按任何特定順序排序，而是根據(jù)其哈希值組織到存儲(chǔ)桶中，以允許直接通過其值快速訪問各個(gè)元素（平均時(shí)間復(fù)雜度恒定）。
unordered_set容器比通過其鍵訪問單個(gè)元素的set容器更快，盡管它們通過其元素子集的范圍迭代通常效率較低。
容器中的迭代器至少是前向迭代器。
11.2 unordered_multiset
unordered_multiset是不按特定順序存儲(chǔ)元素的容器，允許基于其值快速檢索單個(gè)元素，非常類似于unordered_set容器，但允許不同元素具有等效值。
在unordered_multiset中，元素的值同時(shí)是其鍵，用于標(biāo)識(shí)它。鍵是不可變的，因此，unordered_multiset中的元素不能在容器中修改一次 - 但是可以插入和刪除它們。
在內(nèi)部，unordered_multiset中的元素沒有按任何特定方式排序，而是根據(jù)其哈希值組織到存儲(chǔ)桶中，以允許直接通過其值快速訪問各個(gè)元素（平均時(shí)間復(fù)雜度恒定）。
具有等效值的元素在同一個(gè)存儲(chǔ)桶中組合在一起，并且迭代器（請(qǐng)參閱equal_range）可以迭代所有這些元素。
容器中的迭代器至少是前向迭代器。
請(qǐng)注意，此容器未在其自己的標(biāo)頭中定義，但使用unordered_set共享標(biāo)頭<unordered_set>。
12.1 unordered_map
unordered_map是關(guān)聯(lián)容器，其存儲(chǔ)由鍵值和映射值的組合形成的元素，并且允許基于其鍵快速檢索各個(gè)元素。
在unordered_map中，鍵值通常用于唯一標(biāo)識(shí)元素，而映射值是具有與此鍵關(guān)聯(lián)的內(nèi)容的對(duì)象。鍵和映射值的類型可能不同。
在內(nèi)部，unordered_map中的元素沒有按照其鍵值或映射值以任何特定順序排序，而是根據(jù)其哈希值組織到桶中，以允許通過鍵值直接快速訪問各個(gè)元素（使用常量）平均時(shí)間復(fù)雜度）。
unordered_map容器比映射容器更快地通過其鍵訪問單個(gè)元素，盡管它們通過其元素子集的范圍迭代通常效率較低。
unordered_map實(shí)現(xiàn)直接訪問運(yùn)算符（operator []），允許使用其鍵值作為參數(shù)直接訪問映射值。
容器中的迭代器至少是前向迭代器。
12.2 unordered_multimap
unordered_multimap是關(guān)聯(lián)容器，它存儲(chǔ)由鍵值和映射值組合形成的元素，非常類似于unordered_map容器，但允許不同的元素具有等效鍵。
在unordered_multimap中，鍵值通常用于唯一標(biāo)識(shí)元素，而映射值是具有與此鍵關(guān)聯(lián)的內(nèi)容的對(duì)象。鍵和映射值的類型可能不同。
在內(nèi)部，unordered_multimap中的元素沒有按照其鍵值或映射值以任何特定順序排序，而是根據(jù)其哈希值組織到桶中，以允許通過其鍵值直接快速訪問各個(gè)元素（使用常量）平均時(shí)間復(fù)雜度）。
具有等效鍵的元素在同一個(gè)桶中組合在一起，并且迭代器（請(qǐng)參閱equal_range）可以遍歷所有這些元素。
容器中的迭代器至少是前向迭代器。
請(qǐng)注意，此容器未在其自己的標(biāo)頭中定義，但與unordered_map共享標(biāo)頭<unordered_map>。
