C++學習-入門到精通【13】標準庫的容器和迭代器

---

---

一、標準模板庫簡介

STL(Standard Template Library)定義了強大的、基于模板的、可復用的組件，實現了許多通用的數據結構及處理這些數據結構的算法。

容器、迭代器和算法

本章中將介紹STL，并且將討論它的三個關鍵組件——容器（container，流行的模板數據結構）、迭代器（iterator）和算法（algorithm）。STL容器是能存放幾乎所有類型的數據的數據結構。

各容器中共同的成員函數

每個STL容器都有相關的成員函數，這些成員函數的一個子集在所有的STL容器中都有定義。

迭代器

STL迭代器和指針有著類似的屬性，它們用于操作STL容器中的元素。事實上，標準的數組中的指針也可以作為STL容器來使用，只要把標準的指針當作迭代器。

算法

STL算法是執行這些通用數據操作的函數模板，例如，搜索、排序和比較元素等等。它們中的大部分使用迭代器來訪問容器中的元素。每個算法對于和它一起使用的迭代器類型都有一些最小的要求，所以一個容器所支持的迭代器類型決定了這個容器是否可以用于一個特定的算法。

迭代器封裝了訪問容器元素的機制，這種封裝使得許多STL算法能夠應用于多種容器，而無須注意容器的底層實現細節。

自定義模板化數據結構

除了使用標準庫提供的模板，我們還可以建立我們自己的自定義模板化數據結構，包括鏈表、隊列、堆棧和樹。在這些模板的實現中我們會大量使用指針，基于指針的代碼是復雜的，且編譯器并不會對指針使用出現的錯誤進行提示。

所以在我們自定義的模板化數據結構中我們也可以復用STL容器、迭代器及算法來實現一般的數據表示和操作。

1.容器簡介

STL的容器可以分為4種類型：序列容器（sequence container）、有序關聯容器（ordered associative container）、無序關聯容器（unordered associative container）和容器適配器（container adapter）。

標準庫容器類	描述
序列容器
array	固定大小，直接訪問任意元素
deque	從前部或后部進行快速插入和刪除操作，直接訪問任意元素
forward_list	單鏈表，在任意位置快速插入或刪除操作，直接訪問任意元素
list	雙向鏈表，在任意位置進行快速插入和刪除操作
vector	從后部進行快速插入和刪除操作，直接訪問任意元素
有序關聯容器
set	快速查找，無重復元素
multiset	快速查找，可有重復元素
map	一對一映射，無重復元素，基于鍵快速查找
multimap	一對一映射，可胡重復元素，基于鍵快速查找
無序關聯容器
unordered_set	快速查找，無重復元素
unordered_multiset	快速查找，可有重復元素
unordered_map	一對一映射，無重復元素，基于鍵快速查找
unordered_multimap	一對一映射，可胡重復元素，基于鍵快速查找
容器適配器
stack	后進先出（LIFO）
queue	先進先出（FIFO）
priority_queue	優先級最高的元素先出

2.STL容器總覽

序列容器描述了線性的數據結構，例如，數組、向量和鏈表。
關聯容器描述非線性的容器，它們通常可以快速鎖定其中的元素。這種容器可以存儲值的集合或者鍵-值對。C++11中，關聯容器中的鍵是不可變的（無法修改）。

序列容器和關聯容器一起被稱為首類容器。

棧和隊列都是在序列容器的基礎上增加約束條件得到的，因此STL把stack和queue作為容器適配器來實現，這樣就可以使程序以一種約束方式來處理線性容器。類型string支持的功能跟線性容器一樣，但是它只能用來存儲字符數據。

3.近容器

除此之外，有一些其他的容器種類被稱為“近容器”：C類型的基于指針的數組，用于維護標志位的bitset，以及用于進行高速向量運算的valarray。

這些類型被稱為“近容器”，是因為它們展現出的功能與首類容器類似，但是不支持所有的首類容器的功能。

4.STL容器的通用函數

所有的STL容器提供了相近的功能。很多通用的的操作例如成員函數size，可用于所有的容器。下圖中顯示了所有標準庫容器中通用的函數。

注意，priority_queue沒有提供重載的運算符 <、<=、>、>=、==和!=；無序關聯容器沒有提供重載運算符<、<=、>、>= ；forward_list沒有提供成員函數rbegin、rend、crbegin和crend。

我們在使用一個容器之前應該學習容器提供的功能。

STL容器的通用函數	描述
默認構造函數	對容器進行默認初始化的構造函數。通常每種容器都有幾種構造函數，以提供不同的容器初始化方法
拷貝構造函數	將容器初始化為同類型已有容器的副本的構造函數
轉移構造函數	C++11中的新內容，將一個已經存在容器中的元素轉移到同類型的新容器中。轉移構造函數避免了復制作為參數傳入容器的每個元素的開銷
析構函數	在容器不需要時執行處理工作
empty	容器中沒有元素返回true，否則返回false
insert	在容器中插入一個元素
size	返回當前容器中的元素個數
copy operator =	把一個容器賦值給另一個
move operator =	移動賦值運算符（C++11中的新內容），將元素從一個容器移動到另一個容器，避免了復制作為參數傳入容器的每個元素的開銷
operator <	若第一個容器小于第二個容器，返回true，否則返回false
operator <=	若第一個容器小于或等于第二個容器，返回true，否則返回false
operator >	若第一個容器大于第二個容器，返回true，否則返回false
operator >=	若第一個容器大于或等于第二個容器，返回true，否則返回false
operator ==	若第一個容器等于第二個容器，返回true，否則返回false
operator !=	若第一個容器不等于第二個容器，返回true，否則返回false
swap	交換兩個容器中的元素。在C++11中有個新的非成員函數swap，該函數使用移動操作而不是使用復制操作來交換它的兩個參數中的元素值，該函數只適用于首類容器
max_size	返回一個容器中能容納的最大元素個數
begin	該函數有兩個版本，返回引用容器中第一個元素的iterator或const_iterator
end	該函數有兩個版本，返回引用容器末端之后位置（容器中最后一個元素后面的一個元素，容器外部）的iterator或const_iterator
cbegin(c++11)	返回引用容器第一個元素的const_iterator
cend(c++11)	返回引用容器末尾元素之后位置的const_iterator
rbegin	該函數有兩個版本，返回引用容器末端位置的reverse_iterator或const_reverse_iterator
rend	該函數有兩個版本，返回引用容器第一個元素之前位置的reverse_iterator或const_reverse_iterator
crbegin(C++11)	返回引用容器末端位置的const_reverse_iterator
crend(C++11)	返回引用容器第一個元素之前位置的const_reverse_iterator
erase	刪除容器中的一個或多個元素
clear	刪除容器中所有元素

5.首類容器的通用typedef

下圖中顯示了首類容器中通用的typedef，這些typedef在基于模板的變量、函數參數以及返回值的聲明中使用。

typedef	描述
allocator_type	用來分配容器內存的對象的類型（不包含在類模板array中）
value_type	容器中存儲元素的類型
reference	對容器中存儲的元素類型的引用
const_reference	對容器中存儲元素類型的常量引用。這種引用只能用于讀取容器中的元素及執行const操作
pointer	指向容器中存儲元素類型的指針
const_pointer	指向容器中存儲元素類型的常量指針，這種指針只能用于讀取容器中的元素及執行const操作
iterator	指向容器中元素類型的迭代器
const_iterator	指向容器中元素類型的常量迭代器，只能用于讀取元素及執行const操作
reverse_iterator	指向容器中存儲元素類型的反向迭代器，用于反向遍歷容器
const_reverse_iterator	指向容器中存儲元素類型的常量反向迭代器，用于反向讀取元素及執行const操作
difference_type	兩個引用相同容器的迭代器之差的類型（list和關聯容器中沒有定義）
size_type	用于計算容器中的項目數及索引序列容器的類型（list不能進行索引）

6.對容器元素的要求

在使用STL容器之前，首先要確定作為元素的類型可以支持的功能的最小集合。當把一個元素插入到容器中時便生成了這個元素的一個副本。因此，該元素應該支持拷貝構造函數及賦值操作。

有序關聯容器和很多算法要求元素可以相互比較，因此，這些容器中的元素類型應該提供==運算符和<運算符。

在C++11中，對象可以被移動到容器中作為元素，所以對象類型需要實現轉移構造函數和移動賦值運算符。關于移動的內容會在后續章節中介紹。

二、迭代器簡介

迭代器有許多方面與指針類似，它也是用于指向首類容器中的元素。它提供了一種訪問容器中元素的方法，而不需要了解容器內部的結構。

迭代器存有它們指向的特定容器的狀態信息，即迭代器對每種類型的容器都有一種實現。但有些迭代器的操作在容器間是統一。例如，*運算符間接引用一個迭代器，這樣就可以使用它所指向的元素。++運算符使得迭代器指向容器中的下一個元素（和數組中指針遞增后指向下一個元素類似）。

STL首類容器中提供了begin和end函數，函數begin返回一個指向容器中第一個元素的迭代器，函數end返回一個指向容器中最后一個元素再后面一個元素的迭代器（容器外，常用于判斷是否到達了容器的結束位置）。

如果迭代器i指向一個特定元素，那么++i表示迭代器i指向下一個元素。*i指代的是i指向的元素。

從end函數中返回的迭代器只在相等或不等的比較中使用，來判斷迭代器i是否到達了容器的末端。

使用一個iterator對象來指向一個可以修改的容器元素，使用一個const_iterator對象來指向一個不可修改的容器元素。

1.使用istream_iterator輸入，使用ostream_iterator輸出

我們以序列（也稱排列）的形式使用迭代器。這些序列可以在容器中，也可以是輸入序列或是輸出序列。

下面程序中演示了使用istream_iterator從標準輸入（用于輸入程序的數據序列）輸入，使用ostream_iterator從標準輸出（用于輸出程序的數據序列）輸出。

#include <iostream>
#include <iterator>
using namespace std;int main()
{cout << "Enter two integers: ";// 創建一個istream_iterator類型的迭代器從cin中讀取int類型的數據istream_iterator<int> inputInt(cin);int number1 = *inputInt;++inputInt;int number2 = *inputInt;ostream_iterator<int> outputInt(cout);cout << "The sum is: ";*outputInt = number1 + number2;cout << endl;
}

運行結果：

在這個程序中，我們使用了istream_iterator對象來從標準輸入流cin中接收輸入的int數值，這里需要注意，標準輸入流具有動態的、單向的特點（數據只能讀取一次），所以如果在當前輸入流中已經有數據的情況下，初始化一個istream_iterator對象來接收數據，它會直接讀取流中的第一個數據，并且保存一份該數據的副本到對象中的value_type類型的數據成員中。
（這是指向輸入流的迭代器與普通迭代器的本質區別，指向普通容器的迭代器，內部通常就是一個指向容器元素的指針，復制迭代器只是復制指針，不會復制元素。而由于輸入流的特點，指向輸入流的迭代器必須將當前讀取的值緩存起來。）

輸出流迭代器與指向普通容器的迭代器一樣，也不緩存值，它只是將賦值操作轉換成了輸出操作。在上面的程序中就是將*outputInt = number1 + number2;這個賦值操作等效成了cout << number1 + number2;。且這個迭代器的內容也不可以作為右值（畢竟你不能從輸出流中獲取什么數據吧）。同樣的該迭代器的自增操作也是沒有效果的。

2.迭代器類型和迭代器類型的層次

下圖給出了STL中迭代器的類型，每種類型都提供了一些特定的功能。

類型	描述
隨機訪問迭代器（random access）	在雙向迭代器基礎上增加了直接訪問容器中任意元素的功能，即可以向前或向后跳轉任意個元素
雙向迭代器（bidirectional）	在前向迭代器基礎上增加了向后移動的功能。支持多遍掃描算法
前向迭代器（forward）	綜合輸入和輸出迭代器的功能，并能保持它們在容器中的位置（作為狀態信息），可以使用同一個迭代器兩次遍歷一個容器（稱為多遍掃描算法）
輸出迭代器（output）	用于將元素寫入容器。輸出迭代器每次只能向前移動一個元素。輸出迭代器只支持一遍掃描算法，不能使用相同的輸出迭代器兩次遍歷一個序列容器
輸入迭代器（input）	用于從容器中讀取元素。輸入迭代器每次只能向前移動一個元素。輸入迭代器只支持一遍掃描算法，不能使用相同的輸入迭代器兩次遍歷一個序列容器

從上圖我們可以看出這些迭代器是有層次劃分的，從層次的底部到頂部，每種迭代器都支持其下層迭代器所具有的所有功能。下面是這些迭代器的層次圖。注意，這并非繼承。

3.容器對迭代器的支持

每種容器所支持的迭代器類型決定了這種容器是否可以在指定的STL算法中使用。支持隨機訪問迭代器的容器可用于所有的STL算法（除了那些需要改變容器大小的算法，這樣的算法無法在數組和array對象中使用）。指向數組的指針可以代替迭代器用于幾乎所有的STL算法中，包括那些要求隨機訪問迭代器的算法。下圖展示了每種STL容器所支持的迭代器類型。

容器	支持的迭代器類型
序列容器（首類容器）
vector	隨機訪問迭代器
array	隨機訪問迭代器
deque	隨機訪問迭代器
list	雙向迭代器
forward_list	前向迭代器
有序的關聯容器（首類容器）
set	雙向迭代器
multiset	雙向迭代器
map	雙向迭代器
multimap	雙向迭代器
無序的關聯容器（首類容器）
unordered_set	雙向迭代器
unordered_multiset	雙向迭代器
unordered_map	雙向迭代器
unordered_multimap	雙向迭代器
容器適配器
stack	不支持迭代器
queue	不支持迭代器
priority_queue	不支持迭代器

4.預定義的迭代器typedef

下圖中展示了STL容器的類定義中出現的幾種預定義的迭代器typedef。并不是每一種typedef都出現在每個容器中。我們使用常量版本的迭代器來訪問只讀容器或是不應被修改的非只讀容器，使用反向迭代器來以相反的方向訪問容器。

為迭代器類預先定義的typedef	++的方向	讀寫能力
iterator	向前	讀/寫
const_iterator	向前	讀
reverse_iterator	向后	讀/寫
const_reverse_iterator	向后	讀

5.迭代器的操作

下圖展示了每種迭代器上的操作，除了給出的對于所有迭代器都有的運算符，迭代器還必須提供默認構造函數、拷貝構造函數和拷貝賦值操作符。

前向迭代器支持++和所有的輸入和輸出迭代器的功能。
雙向迭代器支持--操作和所有前向迭代器的功能。
隨機訪問迭代器支持所有在表中給出的操作。

迭代器操作	描述
適用所有迭代器的操作
++p	前置自增迭代器
p++	后置自增迭代器
p = p1	將一個迭代器賦值給另一個迭代器
輸入迭代器
*p	間接引用一個迭代器
p->m	使用迭代器讀取元素m
p == p1	比較兩個迭代器是否相等
p != p1	比較兩個迭代器是否不相等
**輸出迭代器
*p	間接引用一個迭代器
p = p1	把一個迭代器賦值給另一個
前向迭代器	前向迭代器提供了輸入和輸出迭代器所有的功能
雙向迭代器
--p	前置自減迭代器
p--	后置自減迭代器
隨機訪問迭代器
p += i	迭代器 p 前進 i 個位置
p -= i	迭代器 p 后退 i 個位置
p + i 或 i + p	在迭代器 p 的位置上前進 i 個位置
p - i	在迭代器 p 的位置上后退 i 個位置
p - p1	表達式的值是一個整數，代表同一個容器中兩個元素之間的距離（與指針 - 指針類似）
p[i]	返回與迭代器p的位置相距 i 的元素，等價于 *(p + i)
p < p1	若迭代器 p 小于 p1（即容器中 p 在 p1 之前）則返回true，否則返回false
p <= p1	若迭代器 p 小于或等于 p1（即容器中 p 在 p1 前或兩者位置相同）則返回true，否則返回false
p > p1	若迭代器 p 大于 p1（即容器中 p 在 p1 之后）則返回true，否則返回false
p >= p1	若迭代器 p 大于或等于 p1（即容器中 p 在 p1 后或兩者位置相同）則返回true，否則返回false

三、算法簡介

STL提供了可以用于多種容器的算法，其中很多算法都是常用的。插入、刪除、搜索、排序及其他一些對部分或全部序列容器和關聯適用的算法。

四、序列容器

C++標準模板庫中提供了五種序列容器：array、vector、deque、list和forward_list。序列容器中的元素都是按照插入的順序進行排序的。

其中array、vector和deque的類模板都是基于數組的；
list和forward_list的類模板實現了一個鏈表數據結構。

提示

• 在vector的尾部進行插入操作是高效的。vector只是簡單地變長來適應新加入的元素。但是在vector的中間插入或刪除元素是低效的，即在插入和刪除的位置之后的整個部分都需要移動，因為vector的元素在內存中占用的是連續空間，和C/C++的原生數組一樣。
• 需要經常在容器兩端進行插入和刪除操作的應用程序通常使用deque而不是vector。盡管可以在vector和deque的前后兩端插入和刪除元素，但是deque類在前端進行插入刪除操作時比vector效率更高。
• 需要經常在容器的中部或者兩端進行插入刪除操作的應用程序通常使用list，因為它可以高效地在數據結構的任意位置執行插入和刪除操作

1.vector

vector類模板提供一種占用連續內存空間的數據結構。這使得它可以高效、直接地通過下標運算符[]訪問vector的任一元素（具有隨機存取性）。它與array類模板類似，通常在容器中的數據數量不確定時使用vector類模板。當一個vector的內存空間耗盡時，它會分配一個更大的連續空間，把原先位置的數據復制或移動過來，再把原空間釋放。

vector支持隨機訪問迭代器。

使用vector和迭代器

下面的程序中說明了類模板vector的幾個函數，這些函數的大部分都存在于首類容器中。使用類模板vectro必須包含頭文件<vector>。

#include <iostream>
#include <vector>
using namespace std;// 創建一個函數模板
template <typename T> void printVector(const vector <T> &integers2);int main()
{const size_t SIZE = 6;int values[SIZE] { 1, 2, 3, 4, 5, 6 };vector <int> integers;cout << "The initial size of integers is " << integers.size()<< "\nThe initial capacity of integers is " << integers.capacity();// 往容器中添加一個元素，vector、deque和list都適用integers.push_back(2);integers.push_back(3);integers.push_back(4);cout << "\nThe size of integers is " << integers.size()<< "\nThe capacity of integers is " << integers.capacity();cout << "\n\nOutput build-in array using pointer notation: ";// 使用begin和end函數，獲取內置數組的開始和結束元素后一個元素的位置的指針// 標準庫對于數組提供了特化，begin和end函數獲得的是指針，并非迭代器for (const int* ptr = begin(values); ptr != end(values); ++ptr){cout << *ptr << ' ';}cout << "\nOutput vector using iterator notation: ";printVector(integers);cout << "\nReversed contents of vector integers: ";for (auto reverseIterator = integers.crbegin();reverseIterator != integers.crend(); ++reverseIterator){cout << *reverseIterator << ' ';}cout << endl;
}template <typename T>
void printVector(const vector <T> &integers2)
{for (auto constIterator = integers2.cbegin();constIterator != integers2.cend(); ++constIterator){cout << *constIterator << ' ';}
}

運行結果：

現在來對上面的代碼進行分析：
首先聲明了一個函數模板用于輸出不同元素類型的vector對象。
聲明了一個大小為6的內置數組values；聲明了一個元素類型為int的vector對象integers；

調用vector類模板中定義的成員函數size和capacity，用于輸出容器當前元素的個數以及當前容量。其中size函數除了forward_list不可用之外，其他容器都可以使用。而capacity只對vector和deque有效。

隨后調用成員函數push_back（除了array和forward_list的其他序列容器均可用）往容器中末端插入元素。如果在一個已滿的vector中插入元素，這個vector就會增加它的容量，某些STL實現使得它的容量加倍。除了array和vector之外的序列容器還提供push_front函數。（vector雖然也可以在容器起始位置進行插入，但是在插入之后，需要將所有其他元素往后移動一位，開銷較在末端插入更大，所以不提供在頭部插入的函數，如果要在容器頭部進行頻繁的數據插入刪除，應該使用其他容器，而非vector）。

當vector需要更多空間時，在原大小上加倍可能會比較浪費。例如，一個已滿的有1000000個元素的vector，在插入一個元素后大小調整為2000000，其中999999個元素的位置是未使用的。程序員可以使用resize函數來更好地控制空間的使用。

在修改vector之后，再次使用size和capacity函數來顯示vector對象當前的元素個數以及容量。我們可以對上述代碼進行些許修改：

	integers.push_back(2);cout << "\nThe size of integers is " << integers.size()<< "\nThe capacity of integers is " << integers.capacity();integers.push_back(3);cout << "\nThe size of integers is " << integers.size()<< "\nThe capacity of integers is " << integers.capacity();integers.push_back(4);cout << "\nThe size of integers is " << integers.size()<< "\nThe capacity of integers is " << integers.capacity();

運行結果：

從結果上來看，當前程序使用vector類模板中，是一個元素一個元素的增加容量。

vector的增長

vector在調整大小以容納更多元素（較為耗時的操作）時所采用的方式在C++標準文檔中并沒有指定。不同庫的實現方法可能不相同，依賴于編譯器使用的vector版本。一些庫實現者最初就分配一個較大的空間，如果vector只存儲少量的元素，那么這樣的大容量就會浪費不少空間，但是如果某個程序在vector中添加很多元素時，它又可以不那么頻繁的重新分配空間，減少了分配空間帶來的額外開銷，提高的效率。

在往vector對象中插入元素之后，又使用指針和指針算法來輸出一個數組的內容。在這里使用了begin和end來獲取數組的起始指針和末尾元素后一個元素的位置指針。注意，這兩個函數對內置數組進行了特化，返回的并不是迭代器。

最后調用函數，通過迭代器來輸出一個vector對象的內容。crbegin即const_reverse_iterator，它返回的是一個反向的常量迭代器。

C++11：shrink_to_fit
在C++11中，可以使用函數shrink_to_fit讓vector或deque容器將額外的內存返回給系統。

vector的元素操作函數

#include <iostream>
#include <array>
#include <vector>
#include <iterator>
#include <stdexcept>
#include <algorithm>
using namespace std;int main()
{const size_t SIZE = 6;array<int, SIZE>values { 1, 2, 3, 4, 5, 6 };vector<int>integers(values.cbegin(), values.cend()); // 使用重載的構造函數來初始化一個vector對象// 聲明一個輸出流迭代器ostream_iterator<int> output(cout, " "); // 以一個空格符作為兩個輸出之間的間隔cout << "Vector integers contains: ";copy(integers.cbegin(), integers.cend(), output);cout << "\nFirst element of integers: " << integers.front()<< "\nLast element of integers: " << integers.back();integers[0] = 7; // 將容器中第一個元素賦值為7integers.at(2) = 10; // 將下標為2的元素賦值為10integers.insert(integers.cbegin() + 1, 22); // 在第二個元素的前面插入一個元素22cout << "\n\nContents of vector integers after changes: ";copy(integers.cbegin(), integers.cend(), output);// 試圖訪問一個容器外的元素try{integers.at(17) = 777;}catch(out_of_range& ex){cerr << "\n\nException: " << ex.what() << endl;}// 擦除第一個元素integers.erase(integers.cbegin());cout << "\n\nVector integers after erasing first element: ";copy(integers.cbegin(), integers.cend(), output);// 擦除剩余元素integers.erase(integers.cbegin(), integers.cend());cout << "\n\nAfter erasing all elements, vector integers "<< (integers.empty() ? "is" : "is not") << " empty.";// 將array對象中的元素插入到vector對象中integers.insert(integers.cbegin(), values.cbegin(), values.cend());cout << "\n\nContents of vector integers before clear: ";copy(integers.cbegin(), integers.cend(), output);// 清空vector對象；clear函數會調用erase函數來清空容器integers.clear();cout << "\nAfter clear, vector integers: "<< (integers.empty() ? "is" : "is not") << " empty" << endl;
}

運行結果：

上面代碼中聲明了一個istream_iterator的對象來用于實現一個類型安全的輸出機制，它只輸出int類型或者相容類型的值。這個與我們之前使用過的有點不一樣，這里使用的該對象的構造函數有兩個參數，第一個依舊表示輸出流，第二個參數是一個字符串，指定了輸出值之間的分隔符（之前聲明的對象其實分隔符也是一個空格，空格就是默認實參）。

copy算法

上面代碼中還使用標準庫中的算法copy（在頭文件<algorithm>中定義）把vector容器中的全部內容復制到目標域（此處為由output指向的輸出流）。

算法copy復制了容器中第一個迭代器參數指定的元素一直到（但不包括）第二個迭代器參數指定的元素之間的所有元素。這兩個迭代器必須符合輸入迭代器的要求，必須要能通過它們從容器中讀取數據。并且這兩個迭代器應該指定同一片區域（同一個容器中）。這些元素被復制到輸出迭代器（通過這個迭代器可以存儲或輸出一個值）指定的位置，它是copy算法的第三個參數。

vector的成員函數front和back

front和back這兩個函數（大部分序列函數都有它們的定義）分別確定vector中的第一個和最后一個元素。注意函數front和begin之間的區別，其中函數front返回vector中第一個元素的引用，而函數begin返回一個指向vector中第一個元素的隨機訪問迭代器。函數back和end也是類似的。back返回的一個元素的引用，end返回的是一個迭代器。

vector必須是非空的，否則front和back的結果是未定義的。

訪問vector元素

我們可以使用重載的下標運算符[]，返回指定位置元素的一個引用或常量值的引用（這取決于容器是否為常量）。
也可以使用成員函數at執行相同的操作，不過成員函數版本有邊界檢查。函數at首先檢查參數提供的值是否在vector的范圍內，若不是，at會拋出out_of_range類型的異常。

下面是一些STL異常類型：

STL異常類型	描述
out_of_range	表示下標超出范圍
invalid_argument	表示傳遞給函數的參數無效
length_error	表示試圖創建過長的容器、字符串等
bad_alloc	表示試圖使用new（或分配器）分配內存時，因可用的內存不夠而導致操作失敗

vector的insert成員函數

大多數序列容器（除了固定大小的array和用insert_list替代insert的forward_list）都有多個重載的insert成員函數。該函數的第一個參數指向元素插入位置的前面。且有多個重載版本，上面的程序中使用了兩個不同的版本，第一種是有兩個參數，第二個參數是要插入的元素；第二種有三個參數，后兩個參數表示另一個容器中的一組值。

vector的成員函數erase

成員函數erase可以用于所有的首類容器（除了固定大小的array和用erase_after代替的forward_list）。

注意，在刪除范圍內的元素時，第二個迭代器指向的元素不會被刪除。

通常情況下，erase將會刪除容器中的指定對象，但是當要刪除的元素中含有指向動態分配的對象的指針時，并不會刪除這個對象。因為這樣會造成內存泄漏。如果元素是unique_ptr，則這個unique_ptr會被刪除，其指向的動態分配的內存也會被刪除。如果元素是shared_ptr，則對應的動態分配的對象引用數減1，直到引用數為0時，動態分配的內存才會被刪除。

vector的成員函數clear

在程序的最后調用成員函數clear來清空vector。這個函數會調用erase函數來清空vector，所以并不會將vector所占的內存返回給系統（vector是動態分配內存的容器）。

所以我們在對上面的代碼進行修改，在每次調用erase函數之后，顯示當前容器的元素個數與容量。

2.list

序列容器list可以在容器的任意位置進行插入和刪除操作。如果大部分插入和刪除操作發生在容器的兩端，那么就應該使用deque來替換。

list類模板實現了一個雙向鏈表，list容器中的每個節點都有指向前一個元素和后一個元素的指針。這使得list類模板支持雙向迭代器，允許容器順序或逆序遍歷。所以任何要求輸入、輸出、前向和雙向迭代器的算法均可以使用該類模板的對象。

C++11：容器forword_list
C++11新增序列容器forward_list通過單鏈表實現，即每個節點中只含有指向下一個節點元素的指針。這使得該類模板支持前向迭代器，允許順序遍歷。任何要求輸入、輸出和前向迭代器的算法均可以使用該類模板的對象。

1.list的成員函數

除了之前介紹的STL容器的通用成員函數和序列容器中的通用成員函數，list類模板還提供了9個特別的成員函數：

• splice

• push_front
  

• pop_front：list類、forward_list類和deque類特有的函數。

• remove

• remove_if

• unique

• merger
  

• reverse

• sort

其中forward_list和deque也支持push_front和pop_front，它們也會操作容器起始位置的元素。

示例代碼：

#include <iostream>
#include <array>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;// 建立一個函數模板用于輸出list容器的值
template <class T> void printList(const list <T> &listRef);int main()
{const size_t SIZE = 4;array <int, SIZE> ints { 2, 6, 4, 8 };list <int> values;list <int> otherValues;values.push_front(1);values.push_front(2);values.push_back(4);values.push_back(3);cout << "values contains: ";printList(values); // 輸出list對象values中的值values.sort(); // 因為values中的值為int類型，可以使用關系運算符進行比較cout << "\nvalues after sorting contains: ";printList(values);// 將一個容器中的元素插入到另一個容器中otherValues.insert(otherValues.cbegin(), ints.cbegin(), ints.cend());cout << "\nAfter insert, otherValues contains: ";printList(otherValues);// 將otherValues對象中的元素全部移動到values對象的尾部values.splice(values.cend(), otherValues);cout << "\nAfter splice, values contains: ";printList(values);cout << "\nAfter splice, otherValues contains: ";printList(otherValues);// 對values對象進行排序values.sort();cout << "\nAfter sort, values contains: ";printList(values);// 將ints對象中的內容插入otherValues對象中otherValues.insert(otherValues.cbegin(), ints.cbegin(), ints.cend());cout << "\nAfter insert, otherValues contains: ";printList(otherValues);otherValues.sort();cout << "\nAfter sort, otherValues contains: ";printList(otherValues);// 合并兩個已排序的list對象，將參數合并到調用的對象中values.merge(otherValues);cout << "\nAfter merge: \n\tvalues contains: ";printList(values);cout << "\n\totherValues contains: ";printList(otherValues);// 移除values的第一個元素和最后一個元素values.pop_front();values.pop_back();cout << "\nAfter pop_front and pop_back: \n\tvalues contains: ";printList(values);// 調用unique函數，移除容器中的重復元素values.unique();cout << "\nAfter unique, values contains: ";printList(values);// 調用swap函數交換values對象和otherValues對象中的元素values.swap(otherValues);cout << "\nAfter swap: \n\tvalues contains: ";printList(values);cout << "\n\totherValues contains: ";printList(otherValues);// 重寫values中的元素values.assign(otherValues.cbegin(), otherValues.cend());cout << "\nAfter assign, values contains: ";printList(values);// 再次將兩個對象合并values.merge(otherValues);cout << "\nAfter merge, values contains: ";printList(values);// 刪除values中等于4的元素values.remove(4);cout << "\nAfter remove(4), values contains: ";printList(values);cout << endl;
}template <class T>
void printList(const list<T>& listRef)
{// 判斷list容器是否為空if (listRef.empty()){cout << "List is empty.";}else{ostream_iterator<T> output(cout, " ");copy(listRef.cbegin(), listRef.cend(), output);}
}

運行結果：

上面的代碼還使用了list的成員函數，swap和assgin：

3.deque

deque類有vector和list的多種優點。deque是“double-ended queue”的縮寫。deque類的實現提供了有效的索引訪問（下標訪問），可以讀取或修改它的元素，與vector類似。deque還提供了在它的首部和尾部進行高效插入和刪除操作的功能，這與list類似（list不僅在首部和尾部有高效的插入刪除操作，在其中部也有）。

deque類支持隨機訪問迭代器，所以deque支持所有STL算法。deque最常用的功能是實現一個隊列（FIFO）。

deque增加的空間可以按照內存塊的形式分配在deque的兩端，這些內存塊通常使用一個指向它們的指針數組來記錄。由于deque中內存分布的不連續性，deque的迭代器必須比那些vector或數組的迭代器更加智能。

提示

• 通常deque的開銷比vector略高；
• deque對在其中間插入、刪除元素進行了優化以減少元素的復制，所以在進行這類操作時比vector更高效，但是還是不如list；

#include <iostream>
#include <deque>
#include <iterator>
#include <algorithm>
using namespace std;int main()
{deque<double> values;ostream_iterator<double> output(cout, " ");values.push_front(2.2);values.push_front(3.5);values.push_back(1.1);cout << "values contains: ";for (size_t i = 0; i < values.size(); ++i){cout << values[i] << ' ';}values.pop_front();cout << "\nAfter pop_front, values contains: ";copy(values.cbegin(), values.cend(), output);values[1] = 5.4;cout << "\nAfter values[1] = 5.4, values contains: ";copy(values.cbegin(), values.cend(), output);cout << endl;
}

運行結果：

deque類提供了和vector相同的基本操作，但如list一樣，增加了成員函數push_front和pop_front，分別在deque的首部插入和刪除元素。

五、關聯容器

STL的關聯容器可以通過關鍵字（被稱為搜索關鍵字）來直接存取元素。有4種關聯容器：

• multiset
• set
• multimap
• map

每種關聯容器都按已排序的方式保存著所有的關鍵字。
還有4種對應的無序關聯容器，分別是：

• unordered_multiset
• unordered_set
• unordered_multimap
• unordered_map

它們提供與有序關聯容器相似的大部分功能。有序與無序關聯容器的主要區別在于關鍵字的存儲是否是按序的。

但是這里與序列容器的按照插入的次序進行排序不同，關聯容器中的排序是按照鍵的排序規則進行排序的。

multiset和set類提供了控制數值集合的操作，其中元素的值就是關鍵字。multiset和set最大的區別就是multiset中允許出現重復的關鍵字，而set中不允許。

multimap和map類提供了處理與關鍵字相關聯的值的功能。multimap與map的主要區別在于multimap允許存在與數值相關的重復關鍵字，而map只允許存放與數值有關的唯一關鍵字。

除了一般容器的成員函數之外，所有的關聯容器還提供一些其他的成員函數，包括，find、lower_bound、upper_bound和count。

1.multiset

有序關聯容器multiset可以快速存取關鍵字，并允許出現重復的關鍵字。元素的順序的是由一個比較函數對象決定的。例如，在一個整數multiset中，使用比較函數對象less<int>來排列關鍵字可以使元素按照遞增的順序排列。

所有關聯容器中關鍵字的數據類型必須支持比較函數對象中指定的比較操作：使用less<T>的關鍵字就必須支持<運算符。若在關聯容器中使用的是自定義的數據類型，那么這些類型必須提供相應的比較操作。

multiset支持雙向迭代器。

示例代碼：

#include <iostream>
#include <array>
#include <set>
#include <algorithm>
#include <iterator>
using namespace std;int main()
{const size_t SIZE = 10;array <int, SIZE> a { 7, 22, 9, 1, 18, 30, 100, 22, 85, 13 };multiset<int, less<int>> intMultiset; // 創建一個multiset對象ostream_iterator<int> output(cout, " ");// 輸出容器中關鍵字為15的元素個數cout << "There are currently " << intMultiset.count(15)<< " values of 15 in the multiset\n";// 往容器中插入兩個關鍵字為15的元素intMultiset.insert(15);intMultiset.insert(15);cout << "After inserts, there are " << intMultiset.count(15)<< " values of 15 in the multiset\n\n";// 在容器中查找關鍵字為15的元素，并返回一個指向它的迭代器auto result = intMultiset.find(15);if (result != intMultiset.end()){cout << "Found value 15\n";}result = intMultiset.find(20);if (result == intMultiset.end()){cout << "Did not found value 20\n";}// 將array對象中的元素插入到intMultiset對象中intMultiset.insert(a.cbegin(), a.cend());cout << "\nAfter insert, intMultiset contains:\n";copy(intMultiset.cbegin(), intMultiset.cend(), output);// 顯示第一個不小于22的元素cout << "\n\nLower bound of 22: "<<  *(intMultiset.lower_bound(22));// 顯示第一個超過22的元素cout << "\nUpper bound of 22: " << *(intMultiset.upper_bound(22));// 返回一對迭代器auto p = intMultiset.equal_range(22);cout << "\n\nequal_range of 22: " << "\n\tLower bound: "<< *(p.first) << "\n\tUpper bound: " << *(p.second);cout << endl;
}

運行結果：

創建一個multiset

該類模板可以只指定容器中元素的類型，該類的默認排序是按照less<key>，也就是升序。

上面程序中調用了multiset的成員函數count、insert、find、lower_bound、upper_bound和equal_range。它們的函數原型如下：

其中equal_range函數返回的是一個std::pair類型的對象，該類原型如下：

2.set

關聯容器set用于快速存取和檢索唯一的關鍵字。除了必須有唯一的關鍵字之外，set和multiset的實現相同。如果試圖往一個set容器中插入重復的關鍵字，那么就會忽略重復的值。

set支持雙向迭代器，與multiset相同。

#include <iostream>
#include <set>
#include <array>
#include <iterator>
#include <algorithm>
using namespace std;int main()
{const size_t SIZE = 5;array<double, SIZE> a { 2.1, 4.2, 9.5, 2.1, 3.7 };set<double, greater<double>> doubleSet(a.begin(), a.end()); // 降序ostream_iterator<double> output(cout, " ");cout << "doubleSet contains: ";copy(doubleSet.begin(), doubleSet.end(), output);// 往容器中插入元素13.8，返回一對值，第一個值為一個指向插入值的迭代器，第二個值為一個bool值（表明插入是否成功）auto p = doubleSet.insert(13.8);cout << "\n\n" << *(p.first)<< (p.second ? " was": " was not") << " inserted";cout << "\ndoubleSet contains: ";copy(doubleSet.cbegin(), doubleSet.cend(), output);p = doubleSet.insert(9.5);cout << "\n\n" << *(p.first)<< (p.second ? " was" : " was not") << " inserted";cout << "\ndoubleSet contains: ";copy(doubleSet.cbegin(), doubleSet.cend(), output);cout << endl;
}

運行結果：

set類模板中的insert函數

3.multimap

關聯容器multimap用于快速存取關鍵字和相關值（通常稱為關鍵字-值對）。multimap和map的元素都是關鍵字-值對，并不是單一的值。在往這兩個容器中插入時使用的是一個包含了關鍵字和值的pair對象，前面已經使用過了。相同的，容器中元素的排序仍是由一個比較函數對象來決定。例如，less<int>用來比較關鍵字類型為int類型的對象。

在multimap中，關鍵字是可以重復的，所以多個值可以和同一個關鍵字對應。通常稱這種關系為一對多關系。例如，一個老師有多個學生，一個學生可以學習多門課程。

multimap使用雙向迭代器。

#include <iostream>
#include <array>
#include <map>
#include <iterator>
#include <algorithm>
using namespace std;int main() 
{// 創建一個multimap對象multimap<int, double, less<int>> pairs;cout << "There are currently " << pairs.count(15)<< " pairs with key 15 in the multimap\n";// 往容器中插入兩個pair對象// 使用utility頭文件中的非成員函數來創建鍵值對pairs.insert(make_pair(15, 2.7));pairs.insert(make_pair(15, 99.3));cout << "After inserts, there are " << pairs.count(15)<< " pairs with key 15 in the multimap\n";pairs.insert(make_pair(30, 111.11));pairs.insert(make_pair(10, 22.22));pairs.insert(make_pair(25, 33.333));pairs.insert(make_pair(20, 9.345));pairs.insert(make_pair(5, 77.54));cout << "\nMultimap pairs contains: \nKey\tValues\n";for (auto mapItem : pairs){cout << mapItem.first << '\t' << mapItem.second << '\n';}cout << endl;
}

運行結果：

multimap的成員函數insert

上面程序使用了成員函數insert來插入一個元素，元素的類型為一個pair對象，該對象使用頭文件<utility>中的非成員函數make_pair來創建。
在C++11中除了使用非成員函數來創建一個pair對象之外，還可以使用列表的初始化方法來創建。例如：pairs.insert({15, 2.7});與程序中使用的語句等價。

C++11：使用列表初始化關鍵字-值對

在創建一個multimap對象時，也可以使用列表初始化器來對該對象進行初始化。例如：
multimap<int, double, less<int>> pairs { { 10, 22.222 }, { 20, 9.345 }, { 5, 77.54} };

4.map

關聯容器map用于快速存取唯一的關鍵字和關聯的值。在map中關鍵字是不能重復的，所以一個關鍵字只能和一個值進行關聯（一對一映射）。例如，學號是一個唯一的用來描述學生的關鍵字。

使用map可以從一個指定的關鍵字快速得到相關的值。所以map通常又被稱為關聯數組。在map的下標運算符[]中使用關鍵字可以鎖定與那個關鍵字相關的值。

在map的任意位置都可以進行插入和刪除操作。

map支持雙向迭代器。

示例代碼：

#include <iostream>
#include <map>
using namespace std;int main()
{map<int, double, less<int>> pairs;pairs.insert({ 15, 2.7 });pairs.insert({ 30, 111.11 });pairs.insert({ 5, 1010.1 });pairs.insert({ 10, 22.72 });pairs.insert({ 25, 345.67 });pairs.insert({ 5, 2.7 }); // 關鍵字相同，被忽略pairs.insert({ 20, 9.234 });pairs.insert({ 35, 2.7 });cout << "pairs contains: \nKey\tValue\n";for (auto mapItem : pairs){cout << mapItem.first << '\t' << mapItem.second << '\n';}// 使用下標運算符修改一個元素的值pairs[25] = 9999.99;// 使用下標運算符插入一個元素pairs[40] = 11.11;cout << "\nAfter subscript operations, pairs contains:\nKey\tValue\n";for (auto mapItem : pairs){cout << mapItem.first << '\t' << mapItem.second << '\n';}cout << endl;
}

運行結果：

從結果中可以看出，map容器中不能出現重復的關鍵字，但是不同關鍵字對應的值可以相同。

六、容器適配器

STL提供三種容器適配器：

• stack
• queue
• prioriy_queue

適配器并非首類容器，因為它們不提供真正的用于存儲元素的數據結構實現，而且它們也不支持迭代器。

適配器的好處在于程序員可以選擇合適的底層數據結構，這三種適配器類都支持成員函數push和pop，通過它們可以在適配器數據結構中插入和刪除元素。

1.stack

stack類（在頭文件<stack>中定義）可以在底層數據結構的一端插入和刪除元素（LIFO）。stack可以使用任意一種序列容器（vector，list或deque）來實現（不使用array來實現的原因是array對象的長度不可變）。默認的stack實現使用的是deque。

stack的操作包括把元素插入到stack頂端的push（實現是調用底層容器的push_back函數），從stack頂端刪除元素的pop（實現是調用底層容器的pop_back函數），獲得頂端元素引用的top（實現是調用底層容器的back函數），確定stack是否為空的empty（實現是調用底層容器的empty函數），以及獲得stack內元素個數的size（實現是調用底層容器的size函數）。

下面的代碼中展示了使用三種不同的底層數據結構來創建stack對象。

#include <iostream>
#include <stack>
#include <vector>
#include <list>
#include <deque> // 可以不包含，因為stack默認使用的就是deque
using namespace std;// 創建兩個函數模板
// 用于壓棧
template<class T> void pushElements(T &stackRef);
// 用于出棧
template<class T> void popElements(T& stackRef);int main()
{// 底層數據結構使用deque對象stack<int> intDequeStack;// 底層數據結構使用vector對象stack<int, vector<int> > intVectorStack;// 底層數據結構作用list對象stack<int, list<int> > intListStack;// 向這三個Stack的對象中壓入0-9這10個數字cout << "Pushing onto intDequeStack: ";pushElements(intDequeStack);cout << "\nPushing onto intVectorStack: ";pushElements(intVectorStack);cout << "\nPushing onto intListStack: ";pushElements(intListStack);cout << "\n\n";// 向這三個Stack的對象中壓入0-9這10個數字cout << "Poping onto intDequeStack: ";popElements(intDequeStack);cout << "\nPoping onto intVectorStack: ";popElements(intVectorStack);cout << "\nPoping onto intListStack: ";popElements(intListStack);cout << "\n\n";
}template <class T> 
void pushElements(T& stackRef)
{for (int i = 0; i < 10; i++){stackRef.push(i);cout << stackRef.top() << ' ';}
}template <class T>
void popElements(T& stackRef)
{while(!stackRef.empty()){cout << stackRef.top() << ' ';stackRef.pop();}
}

運行結果：

注意，push和pop函數都不返回任何值。stack類模擬中只有top函數可以返回元素。

2.queue

隊列queue，顧名思義該適配器的行為是先進先出（FIFO）。

queue可以使用STL的list或deque容器實現，不使用array的原因同樣是因為它的容量是固定的，而不使用vector的原因是在vector的首部插入刪除元素會移動后續所有元素，開銷過大。

默認情況下，queue也使用deque來實現。queue的通用操作包括，將元素插入到隊列尾的push（底層使用push_back函數實現）、將首部元素刪除的pop（底層使用pop_front函數實現）、獲得隊列首部的元素front（底層使用front函數實現）、獲得隊列尾部元素的back（底層使用back函數實現）、確定隊列是否為空的empty（底層使用empty函數實現）和獲得隊列中元素個數的size（底層使用size函數實現）。

示例代碼：

#include <iostream>
#include <deque>
#include <list>
#include <queue>
using namespace std;int main()
{// 默認使用deque容器來作為queue實現的底層數據結構queue<double> dequeValues;// 指定list作為queue實現的底層數據結構queue<double, list<double> > listValues;// 往隊列中插入元素dequeValues.push(3.2);dequeValues.push(4.8);dequeValues.push(9.9);listValues.push(5.5);listValues.push(3.4);listValues.push(6.6);cout << "Poping from dequeValues: ";while (!dequeValues.empty()){cout << dequeValues.front() << ' ';dequeValues.pop();}cout << "\n\nPoping from listValues: ";while (!listValues.empty()){cout << listValues.front() << ' ';listValues.pop();}cout << endl;
}

運行結果：

3.priority_queue

priority_queue類（在<queue>頭文件中定義）提供了在底層數據結構按序插入元素及在底層數據結構首部刪除元素的功能。該類可以使用deque和vector來實現。默認情況下使用vector作為底層數據結構。

當把元素插入到priority_queue中時，它們按照優先順序排序。如此以來，高優先級的元素（由對象創建時使用比較函數對象來決定）將是priority_queue中最先刪除的。這通常使用堆排序技術來實現。默認的比較函數對象是less<T>，程序員也可以自己提供比較函數。

priority_queue的通常操作在該對象的適當位置插入元素的push（使用底層數據結構的push_back函數，再使用heapsort算法重新排序實現）、刪除最高優先級元素的pop（使用底層數據結構的pop_front函數實現）、獲得對象中頂端元素的引用的top（使用底層數據結構的front函數實現）、確定是否為空的empty（使用底層數據結構中的empty函數實現）和獲得對象中元素個數的size（使用底層數據結構的size函數實現）。

示例代碼：

#include <iostream>
#include <queue>
using namespace std;int main()
{// 默認使用vector容器，使用less<T>作為比較函數對象priority_queue<double> priorities;priorities.push(1.1);priorities.push(3.4);priorities.push(5.5);cout << "Poping from priorities: ";while (!priorities.empty()){cout << priorities.top() << ' ';priorities.pop();}cout << endl;
}

運行結果：

七、bitset類

bitset類使創建和操作位集合更加容易，這在描述一些標志位的集合時特別有用。bitset在編譯時就確定了大小。

使用示例：

// 創建了一個有3個位長度的bitset對象b
bitset<3> b; // 調用默認的構造函數，將所有位全部初始化為 0(off)
// 將第bitNumber位的值設為 1(on)，次序從1開始（與下標從0開始不同）
b.set(bitNumber);
// 或者將整個對象的值全部設為 on
b.set();
// 將整個對象的值全部設為 off
b.reset(); // 也可以指定將第幾個位設為 off
// 將指定位置的位反轉
b.flip(bitNumber);
// 或全部反轉
b.flip();// 返回一個指定位的引用
b[bitNumber];
// 還可以使用函數來實現這個操作，且使用函數會進行邊界檢查
// 在沒有越界的情況下，指定位為 on 返回true，否則返回false
// 如果越界拋出一個 out_of_range 類型的異常
b.test(bitNumber); // 返回對象b中有多少位
b.size();
// 返回對象b中有多少位被設為 on
b.count();// 檢測所有位，全部被設為 on 返回true，否則返回false
b.all();
// 檢測所有位，如果有一個為 on 返回true，否則返回false
b.any();
// 檢測所有位，如果沒有一個為 on 返回true，否則返回false
b.none();// 可以使用關系運算符 == 和 != 比較兩個類對象是否相等
b1 == b2; // 兩個對象中所有位都一一相等時，返回true，否則返回false
b1 != b2; // 兩個對象中有一個位不相等時，返回true，否則返回false// 任何位運算符賦值運算符都可以用來操作 bitset 的對象
// 比如，&=, |=, ^=
b1 &= b2; // 在 b1 和 b2 之間逐位執行 邏輯與 操作，并將返回值保存在 b1 中。// 移位運算符當然也可以使用
// 將對象 b 中的位右移 n 位
b >> n;// 將對象 b 轉換成其他形式
b.to_string(); // 將 b 轉換成一個字符串，例如，對象 b 中的位為 10101， 使用該函數就可以得到 "10101" 這個字符串
b.to_ulong(); // 將 b 轉換成一個 ulong 類型的值

八、總結

本章中學習了標準模板庫（STL），并討論了它的三個主要組成部分：容器、算法和迭代器。至于為什么要有STL呢？這是因為，在C++中我們最主要的思想就是面向對象編程，實現泛型編程，通過模板實現，使得同一套代碼可以適用于不同的數據類型。舉個例子，編程比作造汽車，使用了STL模板庫，我們就不需要再自己造輪子，而是直接拿來使用即可，這大大的提高編程的效率。且使用迭代器來訪問容器，對容器中的元素進行操作，不需要像指針一樣那么復雜容易出錯。

對于容器可以分為三個部分：首類容器(可分為序列容器、關聯容器）、容器適配器和近容器。

近容器，本質是非標準庫容器，提供類似容器的接口，它們基于C風格的指針或進行了簡單封裝。bitset就是一個近容器；

序列容器，包括array（靜態數組）、vector（動態數組）、list（雙向鏈表）、deque（雙向隊列）和forward_list（單鏈表）。這類容器用于描述線性的數據結構。

關聯容器，包括有序關聯容器和無序關聯容器，其中有序的關聯容器有set、multiset、map和multimap這些容器基本都是由紅黑樹來實現；而無序的關聯容器有unordered_set、unordered_multiset、unordered_map和unordered_multimap這些容器基本都是由哈希桶來實現；

容器適配器，這部分是因為本身沒有具體的實現，而是通過組合已有容器的功能來實現。包括stack（棧）、queue（隊列）和priority_queue（具有優先級的隊列）。

對于迭代器，我們可以將其簡單的理解成指針，但是它們本身是一個模板類的對象，封裝了對容器中元素進行操作的函數。根據層次可以分為隨機訪問迭代器、雙向迭代器、前向迭代器、輸入迭代器和輸出迭代器（后兩個迭代器并列）。其中只有array、vector和deque支持隨機訪問迭代器，只有stack、queue和priority_queue不支持迭代器，其余的容器全部都支持雙向迭代器。

而算法則是STL提供的一些常用功能的實現。會在下一章詳細介紹。