前排提醒： 由於 Microsoft Docs 全是機翻。所以本文表格是我人腦補翻+審校。 如果有紕漏、模糊及時評論反饋。 序列式容器 序列容器是指在邏輯上以線性排列方式存儲給定類型元素的容器。 這些容器和數組非常類似，都是在邏輯上連續的(但記憶體不一定是連續的)，與數組不同的是，容器可以非常方便的動 ...
前排提醒：
由於 Microsoft Docs 全是機翻。所以本文表格是我人腦補翻+審校。
如果有紕漏、模糊及時評論反饋。
序列式容器
序列容器是指在邏輯上以線性排列方式存儲給定類型元素的容器。
這些容器和數組非常類似，都是在邏輯上連續的(但記憶體不一定是連續的)，與數組不同的是，容器可以非常方便的動態管理，而不是固定元素大小。
std::vector
當你需要容器時，就找vector!
-- Bjarne Stroustrup
std::vector 差不多是C++當中最常用的容器，它是一個模版類。你可以將它視作傳統數組的動態功能增強版本，因此它的泛用性非常高。
當你以局部變數形式創建並初始化 vector 時，對象本身是存儲於棧記憶體當中，但是它所存儲的元素卻是在堆記憶體當中連續的一塊空間，因此 std::vector 對於隨機訪問效率會非常高。
vector 的存儲是自動管理的，按需擴張收縮。 vector 通常占用多於靜態數組的空間，因為要分配更多記憶體以管理將來的增長。 vector 所用的方式不在每次插入元素時，而只在額外記憶體耗盡時重分配。分配的記憶體總量可用 capacity() 函數查詢。額外記憶體可通過對 shrink_to_fit() 的調用返回給系統。 (C++11 起)
重分配通常是性能上有開銷的操作。若元素數量已知，則 reserve() 函數可用於消除重分配。
-- 《C++ Reference》
頭文件：
#include <vector>
構造語法：
// 空初始化 std::vector<Type> name; // 帶有預設集合 std::vector<Type> name{ value, value, ... }; // 預分配長度 std::vector<Type> name(num); // 預分配長度與預設值 std::vector<Type> name(num, value);
成員函數：
| 名稱 | 說明 |
|---|---|
assign |
清除當前vector並將指定的元素複製到該空vector。 |
at |
返回對vector中指定位置的元素的引用。 |
back |
返回對vector中最後一個元素的引用。 |
begin |
返回該vector中起始位置的迭代器。 |
capacity |
返回在不分配更多的記憶體的情況下vector可以包含的元素數。(當前記憶體空間) |
cbegin |
返回指向vector中起始位置的常量迭代器。(const修飾) |
cend |
返回末尾位置常量迭代器。(非末尾元素)(const修飾) |
crbegin |
返回一個指向vector中起始位置的常量反向迭代器。(const修飾) |
crend |
返回一個指向vector中末尾位置的常量反向迭代器。(const修飾) |
clear |
清除vector的所有元素。（但沒有回收記憶體） |
data |
返回指向vector中首個元素的指針。 |
emplace |
將元素原位插入到指定位置之前。 |
emplace_back |
將元素原位插入到指定位置之後。 |
empty |
檢查vector是否為空。 |
end |
返回指向vector末尾的迭代器。（非末尾元素） |
erase |
從指定位置刪除vector中的一個元素或一系列元素。 |
front |
返回回vector中第一個元素的引用。 |
get_allocator |
將對象返回到vector使用的 allocator 類。 |
insert |
將一個元素或多個元素插入到vector指定位置。 |
max_size |
返回vector的最大長度。 |
pop_back |
刪除vector末尾處的元素。 |
push_back |
在vector末尾處追加一個元素。 |
rbegin |
返回起始位置的反向迭代器。 |
rend |
返回末尾位置的反向迭代器。 |
reserve |
重新分配vector的最小存儲長度。 |
resize |
為vector指定新的大小。 |
shrink_to_fit |
釋放冗餘容量(記憶體)。 |
size |
返回vector中的元素數量。 |
swap |
交換兩個vector的元素。 |
運算符：
| 名稱 | 說明 |
|---|---|
operator[] |
返回對指定位置的vector元素的引用。 |
operator= |
用另一個vector的副本替換該向量中的元素。 |
最簡單示例：
int main() { std::vector<int> vec = { 0, 1, 2, 3, 4 }; for (auto &i : vec) { std::cout << i << std::endl; } vec.reserve(10); vec.push_back(5); vec.push_back(6); vec.push_back(7); vec.push_back(8); vec.push_back(9); vec.erase(vec.begin() + 2, vec.end() - 3); for (auto& i : vec) { std::cout << i << std::endl; } vec.clear(); std::vector<int>().swap(vec); return EXIT_SUCCESS; }
擴展閱讀：
【Example】C++ Vector 記憶體預分配的良好習慣
std::list
std::list 是一個模板類，即鏈表。它的特點是每個元素在邏輯上都以線性連續方式來存儲。
它的每個元素內部都有指向前元素及後元素的指針，每次插入與刪除都只需更改前後“鄰居”的指針，可以做到任何位置高效的插入與刪除。
但是，雖然在邏輯上是連續的，然而每個元素在記憶體當中並不是連續存儲的，因此 std::list 無法做到像 std::vector 那樣隨機讀寫。（它直接沒有 at 函數及 [] 重載）
此外 std::list 對異常的控制是，要麼操作成功，出現異常則不進行任何更改。
頭文件：
#include <list>
構造語法：
// 預設 std::list<Type> name; // 預分配長度 std::list<Type> name(num); // 預分配長度及預設值 std::list<Type> name(num, value); // 從 initlist 創建 std::list<Type> name(initlist); // 迭代器區間創建 std::list<Type> name(obj.begin(), obj.end());
成員函數：
| 名稱 | 說明 |
|---|---|
assign |
清空當前list並將指定的元素複製到當前空list。 |
back |
返回對list中最後一個元素的引用。 |
begin |
返回list中指向起始位置的迭代器。 |
cbegin |
返回list中起始的位置的常量迭代器。(const修飾) |
cend |
返回list中末尾的位置的常量迭代器。(const修飾) |
clear |
清空list。 |
crbegin |
返回list中起始的常量反向迭代器。(const修飾) |
crend |
返回list中末尾的常量反向迭代器。(const修飾) |
emplace |
將元素原位插入到指定位置。 |
emplace_back |
將元素原位插入到末尾位置。 |
emplace_front |
將元素原位插入到起始位置。 |
empty |
判斷list是否為空。 |
end |
返回list中指向末尾的迭代器。 |
erase |
從指定位置刪除list中的一個元素或一系列元素。 |
front |
返回對list中第一個元素的引用。 |
get_allocator |
返回用於構造list的 allocator 對象的一個副本。 |
insert |
將一個、幾個或一系列元素插入list中的指定位置。 |
max_size |
返回list的最大長度。 |
merge |
合併兩個已排序list，合併前必須升序或其他指定順序排序。 |
pop_back |
刪除最後元素。 |
pop_front |
刪除首個元素。 |
push_back |
從末尾追加元素。 |
push_front |
從起始追加元素。 |
rbegin |
返回起始位置的反向迭代器。 |
remove |
移除滿足條件的元素。 |
remove_if |
移除滿足謂詞條件的元素。 |
rend |
返回list中末尾的反向迭代器。 |
resize |
重新分配長度。 |
reverse |
反轉list中元素的順序。 |
size |
返回list中元素的數目。 |
sort |
按升序或指定其他順序排列list中的元素。 |
splice |
從另一個list中移動元素。 |
swap |
交換兩個list的元素。 |
unique |
刪除連續的重覆元素。 |
運算符：
| 名稱 | 說明 |
|---|---|
operator= |
用另一個list的副本替換當前list中的元素。 |
最簡單示例：
int main() { std::list<int> list(10, 0); list.emplace_front(1); list.emplace_front(2); list.emplace_back(6); list.emplace_back(7); for (auto& i : list) { std::cout << i << std::endl; } std::cout << "------" << std::endl; list.sort(); std::list<int> list_m{1, 2, 3, 4, 5}; list.merge(list_m); for (auto& i : list) { std::cout << i << std::endl; }return EXIT_SUCCESS; }
擴展閱讀：
std::forward_list 是單項鏈表，它的頭文件是：
#include <forward_list>
它的操作方式和 std::list 基本相同，但是，由於它是單向鏈表，所以它沒有反向迭代器。
也就意味著沒有 size() 函數，沒有 push_back()、pop_back()、emplace_back() 這些涉及反向操作的函數。
它的優勢是空間利用率比 std::list 更高，酌情使用。
它相對於 std::list 多了以下操作函數：
| 名稱 | 說明 |
| before_begin | 返回指向第一個元素之前的迭代器 |
| cbefore_begin | 返回指向第一個元素之前的常量迭代器 |
| insert_after | 在某個元素後插入新元素 |
| emplace_after | 在元素後原位構造元素 |
| erase_after | 擦除元素後的元素 |
std::deque
雙端隊列，是具有下標與邏輯相鄰順序的容器。它是 std::vector 與 std::list 相結合的方案，既可隨機訪問、也可高效雙端插入刪除。
std::vector 之所以隨機訪問效率高，是因為它在記憶體當中是連續的空間並且具有下標。
std::list 之所以插入刪除效率高，是因為它所進行插入與刪除操作時只需更改前後鄰居的鏈接節點指針。
先來看 std::vector 的記憶體邏輯：【Example】C++ Vector 記憶體預分配的良好習慣
std::vector 是始終保持每個元素在連續的一塊記憶體上，當 pushback 了新的元素後，如果冗餘記憶體空間不足，需要重新申請一塊新記憶體再將原有數據拷貝入新的記憶體塊並釋放舊記憶體塊。
而 std::deque 在面臨 pushback 了新元素且已有記憶體空間面臨不足情況時，則新申請一塊記憶體直接存入新數據，再對新舊記憶體塊進行鏈接。
因此，std::deque 本質是由多個連續記憶體塊組成，在一定程度上兼具了 std::vector 與 std::list 的優點，但卻無法單獨超越其中一者。
區塊，這很 Minecraft! /滑稽
-- ZhouFZ
除此之外，std::deque 還具有以下特點：
1，雙端都可以進行數據的增刪。
2，不支持記憶體預分配或其他控制手段，也不支持對容量進行手動修改。
3，deque 會釋放冗餘的記憶體區塊，時機取決於編譯器實現。
4，它的迭代器需要在不同記憶體區塊之間迭代，所以性能不如 std::vector 但優於 std::list 。
需要註意的問題：
迭代器非法化：指的是在 std::deque 邏輯上連續元素的頭尾與中間進行插入或刪除新的元素而導致的迭代器失效。
特別補充：迭代器失效情況也取決於編譯器實現，如果實際操作中存在任何可能原因而導致失效，請採取措施避免。
引發失效的情況：
| 操作 | 情況 |
| 在頭尾插入 | 可能導致迭代器失效(全部或部分)，但指針與引用仍然有效 |
| 在頭尾刪除 | 其他元素的迭代器不失效 |
| 中間插入或刪除操作 | 全部失效 |
具體原因：
std::deque 是一個同時管理著索引區塊與對應數據區塊的結構，它通過一個類似於 MAP 的 Key:Value 形式來記錄所擁有的記憶體區塊。
當出現頭尾插或者中間插操作時，如果當前所管理的數據記憶體區塊容量不足，而去開闢了新的數據記憶體區塊，自然索引就會增加。
如果存儲索引本身的區塊記憶體空間不足，就又要去開闢新的記憶體去存儲更改後的索引區塊，已有的迭代器自然就失效了，因為迭代器找不到自己所處數據區塊的原有索引在哪了。
（聽不懂沒事，多琢磨幾天。）
《C++ Reference》對迭代器非法化的補充
操作 被非法化 所有隻讀操作 決不 swap 、 std::swap 尾後迭代器可能被非法化（實現定義） shrink_to_fit 、 clear 、 insert 、 emplace 、
push_front 、 push_back 、 emplace_front 、 emplace_back始終 erase 若在起始擦除——僅被擦除元素
若在末尾擦除——僅被擦除元素和尾後迭代器
否則——非法化所有迭代器（包含尾後迭代器）。resize 若新大小小於舊者：僅被擦除元素和尾後迭代器
若新大小大於舊者：非法化所有迭代器
否則——不非法化任何迭代器。pop_front 僅有指向被擦除元素者 pop_back 僅有指向被擦除元素者和尾後迭代器 此節有仍少量不准確處，更多細節請查看涉及單獨成員函數的頁面
非法化註意
- 從 deque 任一端插入時， insert 和 emplace 不會非法化引用。
- push_front 、 push_back 、 emplace_front 和 emplace_back 不會非法化任何到 deque 元素的引用。
- 從 deque 任一端擦除時， erase 、 pop_front 和 pop_back 不會非法化到未擦除元素的引用。
- 以較小的大小調用 resize 不會非法化任何到未擦除元素的引用。
- 以較大的大小調用 resize 不會非法化任何到 deque 元素的引用。
回歸正題
頭文件：
#include <deque>
構造語法：
// 預設空 std::deque<Type> name; // 拷貝構造 std::deque<Type> name(dequeobj); // 預設分配長度及預設值 std::deque<Type> name(num, value); // 迭代器區間 std::deque<Type> name(obj.begin(), obj.end());
成員函數：
| 名稱 | 說明 |
|---|---|
assign |
清空當前deque並將指定的元素複製到當前空deque。 |
at |
返回對deque中指定位置的元素的引用。 |
back |
返回對deque中最後一個元素的引用。 |
begin |
返回指向起始的迭代器。 |
cbegin |
返回指向起始的常量迭代器。(const修飾) |
cend |
返回指向末尾的常量迭代器。(const修飾) |
clear |
清空 deque。 |
crbegin |
返回指向起始的逆向常量迭代器。(const修飾) |
crend |
返回指向末尾的逆向常量迭代器。(const修飾) |
emplace |
將元素原位插入到指定位置。 |
emplace_back |
將元素原位插入到末尾位置。 |
emplace_front |
將元素原位插入到起始位置。 |
empty |
檢查 deque 是否為空。 |
end |
返回指向末尾的迭代器。 |
erase |
從指定位置刪除一個或一系列元素。 |
front |
返回第一個元素的引用。 |
get_allocator |
返回用於構造 allocator 的 deque 對象的副本。 |
insert |
將一個、多個或一系列元素插入到指定位置。 |
max_size |
返回可容納的最大元素數。 |
pop_back |
刪除末尾處的元素。 |
pop_front |
刪除起始處的元素。 |
push_back |
插入元素到末尾位置。 |
push_front |
插入元素到起始位置。 |
rbegin |
返回指向起始的逆向迭代器。 |
rend |
返回指向末尾的逆向迭代器。 |
resize |
手動改變大小。 |
shrink_to_fit |
釋放未使用的記憶體。 |
size |
返回當前長度。（元素數量） |
swap |
交換兩個deque。 |
運算符：
| 名稱 | 說明 |
|---|---|
operator[] |
返回對指定位置的 deque 元素的引用。 |
operator= |
將 deque 的元素替換為另一個 deque 的副本。 |
最簡單示例：
(註意看對迭代器的操作)
int main() { std::deque<int> deque_d(10, 0); std::deque<int>::iterator it = deque_d.begin(); it = deque_d.insert(it, 1); it = deque_d.insert(it, 2); it = deque_d.insert(it, 3); it = deque_d.insert(it, 4); std::deque<int>::iterator itf = std::find(deque_d.begin(), deque_d.end(), 3); itf = deque_d.emplace(itf, 5); itf = deque_d.emplace(itf, 6); itf = deque_d.emplace(itf, 7); for (auto &i : deque_d) { std::cout << i << std::endl; } return EXIT_SUCCESS; }
std::array
標準庫數組，本質一個模板類，是一個固定長度的容器，不可擴容。在現代C++中，主張使用 std::array 替代傳統樣式的數組。
std::array 提供的功能也比 std::vector、std::list 更簡單。因為，它從設計上的目的，就是對傳統數組進行現代化改造。
具體體現在：
1，它擁有和傳統數組一樣的性能、可訪問性。
2，它具有傳統數組所沒有的容器優點：可獲取大小、隨機訪問迭代器、支持賦值等。
所以，當你需要固定大小的數組時，應首先考慮 std::array。
頭文件：
#include <array>
構造語法：
// 預設空
std::array<Type, SizeNum> name;
// 預設值情況下
std::array<Type, SizeNum> name{value, value...};
std::array<Type, SizeNum> name = {value, value...};
成員函數：
| 名稱 | 說明 |
|---|---|
array |
構造一個數組對象。 |
at |
訪問指定位置處的元素。 |
back |
訪問最後一個元素。 |
begin |
指定受控序列的開頭。 |
cbegin |
返回一個隨機訪問常量迭代器，它指向數組中的第一個元素。 |
cend |
返回一個隨機訪問常量迭代器，它指向剛超過數組末尾的位置。 |
crbegin |
返回一個指向反向數據中第一個元素的常量迭代器。 |
crend |
返回一個指向反向數組末尾的常量迭代器。 |
data |
獲取第一個元素的地址。 |
empty |
測試元素是否存在。 |
end |
指定受控序列的末尾。 |
fill |
將所有元素替換為指定值。 |
front |
訪問第一個元素。 |
max_size |
對元素數進行計數。 |
rbegin |
指定反向受控序列的開頭。 |
rend |
指定反向受控序列的末尾。 |
size |
對元素數進行計數。 |
swap |
交換兩個容器的內容。 |
運算符：
| 運算符 | 說明 |
|---|---|
array::operator= |
賦值替換數組。 |
array::operator[] |
訪問指定位置處的元素。 |
最簡單示例：
int main()
{
std::array<int, 5> arry = {5, 4, 3, 2, 1};
std::sort(arry.begin(), arry.end());
for (auto &i : arry)
{
std::cout << i << std::endl;
}
std::cout << "-------------" << std::endl;
arry[2] = 10;
for (auto& i : arry)
{
std::cout << i << std::endl;
}
std::cout << "-------------" << std::endl;
arry.fill(0);
for (auto& i : arry)
{
std::cout << i << std::endl;
}
return EXIT_SUCCESS;
}
關聯式容器
與序列式容器不同的是，關聯式容器是採用鍵值對的方式即 Key : Value 對應的方式來存儲數據。
STL 所內置的關聯式容器主要使用紅黑樹來實現，容器內會自動根據 Key 來自動升序排序。
此外還有基於哈希值的無序關聯式容器，請照貓畫虎使用即可。
| 名稱 | 頭文件 | 實現 | 鍵值對應 | 允許鍵重覆 | 鍵排序 |
| std::set | set | 紅黑樹 | Key = Value | No | 升序 |
| std::multiset | set | 紅黑樹 | Key = Value | Yes | 升序 |
| std::unordered_set | unordered_set | 哈希表 | Key = Value | No | 無 |
| std::unordered_multiset | unordered_set | 哈希表 | Key = Value | Yes | 無 |
| std::map | map | 紅黑樹 | Key : Value | No | 升序 |
| std::multimap | map | 紅黑樹 | Key : Value | Yes | 升序 |
| std::unordered_map | unordered_map | 哈希表 | Key : Value | No | 無 |
| std::unordered_multimap | unordered_map | 哈希表 | Key : Value | Yes | 無 |
紅黑樹與哈希表不同實現的關聯式容器區別：紅黑樹實現的關聯式容器遍歷性能更好，哈希表實現的關聯式容器基於鍵的隨機訪問性能更好。
請記下表格當中的頭文件，下文當中不再贅述。
Set
std::set 與 std::multiset 最顯著的特點就是鍵就是值，所以在 Set 當中的值不能直接修改，需要刪除舊值再重新建立新值 (即新建立鍵值，只是對於 set 來說值就是鍵而已)。
std::set 與 std::multiset 的區別是，std::set 不允許有重覆值，std::multiset 則允許。兩者同樣都會根據鍵值大小進行升序排序。
構造語法：
// 預設 std::set<Type> name; std::multiset<Type> sm1; // 迭代器區間 std::set<Type> name(obj.begin(), obj.end()); std::multiset<Type> name(obj.begin(), obj.end()); // initlist std::set<int> name{value, value, ...}; std::multiset<int> name{value, value, ...};
// 拷貝構造和移動構造略 // 自定義比較器(C++14) struct Point { double x, y; }; struct PointCmp { bool operator()(const Point& lhs, const Point& rhs) const { return std::hypot(lhs.x, lhs.y) < std::hypot(rhs.x, rhs.y); } }; std::set<Point, PointCmp> z = { {2, 5}, {3, 4}, {1, 1} };
成員函數：
| 名稱 | 說明 |
|---|---|
begin |
返回指向起始的迭代器。 |
cbegin |
返回指向起始的常量迭代器。(const修飾) |
cend |
返回指向末尾的常量迭代器。(const修飾) |
clear |
清除所有元素。 |
contains(c++20) |
檢查是否存在指定鍵。僅限C++20。 |
count |
返回匹配特定鍵的元素數量。 |
crbegin |
返回指向起始的常量逆向迭代器。(const修飾) |
crend |
返回指向末尾的常量逆向迭代器。(const修飾) |
emplace |
原位插入元素。 |
emplace_hint |
原位插入元素，且儘可能於 hint(迭代器) 前面位置。 |
empty |
檢查是否為空。 |
end |
返回指向末尾的迭代器。 |
equal_range |
返回一對錶示範圍區間的迭代器，為匹配特定鍵的元素範圍。 |
erase |
從指定位置移除一個元素或元素範圍，或者移除與指定鍵匹配的元素。 |
find |
尋找帶有特定鍵的元素，並返回它所處位置的迭代器。 |
get_allocator |
返回用於構造 allocator 的 set 對象的副本。 |
insert |
將一個元素或元素範圍插入到set。 |
key_comp |
返回set內用於比較排序對象(比較器)的副本。 |
<
  更多相關文章
一周排行
 所有分類
|