STL初步認識：介紹了【什麼是STL】，以及【STL庫里的常見容器】，也對【迭代器】進行了簡短的說明。 ...
目錄
命名空間
問題背景
設想，在一次的大規模程式中，你和幾位搭檔合作寫代碼。
由於所需的代碼量無比龐大，你們遇到了一個無法避免的問題——標識符命名高度重合，造成了代碼極度混亂。
如果要重新修改標識符的名稱，不僅耗時耗力，還會導致代碼的可讀性降低。
這種情況下，你會怎麼解決這個棘手的問題呢？
。。。。。。。。。。（手動暫停，讓我們來稍作思考）。。。。。。。。。。
這時候，團隊里的大神提議，將每個人的代碼中所用到的標識符，都放進各自的一個專屬空間里。
例：A、B、C 三人，雖然都用了標識符名稱 x，但是放入各自的空間後，就可以用 A 的 x、 B 的 x、 C 的 x 來區分這三個同名不同意義的 x。
經過嘗試和實行後，你們發現，問題果然迎刃而解了。
知識點
-
命名空間 = 名字空間 = 名稱空間 = namespace
- 是標識符的可見範圍/作用域
- 多個命名空間中可以定義同樣的標識符，但是不同命名空間內的標識符意義不同，且互不幹擾
- 最常見的命名空間是 std，包含了標準 C++ 庫的所有內容
-
使用方法：
-
定義命名空間
namespace A { int x; float y; } -
使用命名空間
-
直接使用
// 使用命名空間 A 里的標識符 x 和 y A::x = 3; A::y = 2.2; -
使用整個命名空間
using namespace A; // 直接聲明要使用的命名空間 // 由於已經聲明瞭使用命名空間 A，因此可以直接使用標識符 x = 3; y = 2.2; -
使用部分命名空間
using A::x; // 聲明要使用命名空間 A 的 x x = 3; // 由於提前聲明，因此可以直接使用 A::y; // 因為沒有聲明要用 y，所有要用 A::y
-
-
STL初步
簡介
我們最常用的命名空間是 std，因此在一開始學習代碼的時候就會用using namespace std。
在命名空間 std 里，有一個十分重要且實用的 C++ 軟體庫——STL。
- STL = Standard Template Library = 標準模板庫
- 包含組件：演算法、容器、函數、迭代器
- 關鍵理念：基於模板編寫，將 “要操作的數據” 和 “對數據執行的操作” 分離
- 命名空間：std
- 使用時需要用
std::name - 可以直接
using namespace std（但是在大型工程中不推薦使用）
- 使用時需要用
容器
容器是包含、放置數據的工具，可以分為：簡單容器、序列容器、關聯容器。
1. 簡單容器（simple container）
- 例子：pair、tuple
- 實際上，pair 和 tuple 也不能算是容器，只可以算是 STL 中基本的數據單位
A) pair
-
由兩個單獨數據組成（可以是同數據類型/不同數據類型）
-
常用於 map 中，也可以用於函數中兩個返回值的傳遞
-
代碼實現：
template <class T1, class T2> // 基於模板編寫 struct pair { T1 first; // 第一個成員變數 T2 second; // 第二個成員變數 } -
使用方法：
#include <utility> // pair 的頭文件 #include <string> // string 的頭文件 using namespace std; int main() { // 方法1：同時創建+初始化 pair <string, float> p1 ("Karry", 92.1); // 方法2：創建之後再賦值 pair <string, float> p2; p2.first = "Brenda"; p2.second = 22.1; // 方法3：使用函數 make_pair 創建+初始化 // 優勢：程式可以自動推導成員變數的類型 auto p3 = make_pair ("Roy", 11.8); return 0; } -
訪問方法：
// 因為 pair 只有兩個元素，只需要用 first 和 second 來訪問 cout << p1.first << " " << p2.second << endl; // 輸出結果為：Karry 22.1 -
對 pair 進行大小比較（先比較 first，再比較 second）
template<class T1, class T2> void compare(T1 a, T2 b) { if (a > b) cout << ">" << endl; else if (a < b) cout << "<" << endl; else if (a == b) cout << "=" << endl; } //（1） pair <string, int> x = make_pair (2, "Alice"); pair <string, int> y = make_pair (2, "Bob"); compare(x,y); // 輸出結果為：< //（2） pair <string, int> x = make_pair (2, "Alice"); pair <string, int> y = make_pair (1, "Bob"); compare(x,y); // 輸出結果為：> //（3） pair <string, int> x = make_pair (2, "Bob"); pair <string, int> y = make_pair (2, "Bob"); compare(x,y); // 輸出結果為：=
B) tuple
-
和 pair 類似，但是可以由 n 個數據組成
-
適用於有多個返回值的函數的返回值傳遞
-
使用方法：
#include <tuple> // tuple 的頭文件 #include <string> // string 的頭文件 using namespace std; int main() { // 方法1：同時創建+初始化（需要多少個數據就寫多少個） tuple <string, int, float> p1 ("Karry", 23, 92.1); // 方法2：使用函數 make_tuple 創建+初始化 auto p2 = make_tuple ("Brenda", 20, 22.1); // 方法3：結合函數 tie 和 make_tuple 進行賦值創建 // 沒有一個特定的 tuple 標識符，但是可以同時對個別數據進行操作 string name; int age; float marks; tie (name, age, marks) = make_tuple ("Roy", 22, 11.8); return 0; } -
訪問方法：
// 使用 get 函數，通過下標訪問 // 下標需要在編譯時確定，只能使用確定的數字，不能使用變數，否則會編譯錯誤 auto x = get <0> (p1); // p1[0] = "Karry" auto y = get <1> (p2); // p2[1] = 20 auto z = get <2> (p3); // p3[2] = 11.8 cout << x << " " << y << " " << z << endl; // 輸出結果為：Karry 20 11.8 -
對 tuple 進行大小比較的方式和 pair 類似 [點擊跳轉]
-
返回值類型為 tuple 時：
tuple <int, float> calc(int n) { return make_tuple(n + 2, n / 2.0); } // 方法1：用 tuple 來接收函數返回值 tuple <int, float> a; a = calc(3); cout << get<0>(a) << " " << get<1>(a) << endl; // 方法2：用 tie 函數來接收函數返回值 // 優勢：可以直接分開使用函數返回值 int num; float data; tie(num, data) = calc(3); cout << num << " " << data << endl; // 輸出結果皆為：5 1.5
2. 序列容器（sequence container）
-
例子：array、vector、deque、list、forward list
-
特點概覽：
長度 添加元素 刪除元素 訪問元素 array 固定 可以在任意位置 可以在任意位置 通過下標 vector 不固定 一般在尾部 一般在尾部 通過下標 deque 不固定 在頭部、尾部 在頭部、尾部 通過下標 list 不固定 可以在任意位置 可以在任意位置 雙向 forward list 不固定 可以在任意位置 可以在任意位置 只可以正向
A) vector
-
可以自動擴展容量的動態數組
- 容量（capacity）是可以存放的數據數量，大小（size）是現存放的數據數量
- 當 size 達到 capacity 時，會自動將 capacity 擴充一倍
-
使用方法：
#include <vector> // vector 的頭文件 using namespace std; // 創建：vector <容器中的數據類型> 容器名稱; vector <int> vec; -
常用函數：
vec.size(); // 返回 vector vec 中的元素數量 vec.clear(); // 清空數組 vec.push_back(1); // 把 1 添加進 vector vec vec.pop_back(); // 把最後一個元素刪除 vec.insert(vec.begin() + ind, 5); // 在下標為 ind 的位置添加元素 5，其餘元素往後挪 vec.erase(vec.begin() + ind); // 把下標為 ind 的數據刪除 -
遍歷方法：
// 方法1：使用下標 for (int ind = 0; ind < vec.size(); ++ind) { cout << vec[ind] << " "; } // 方法2：按照範圍 for (auto &x : vec) { cout << x << " "; } // 方法3：使用迭代器 // 為了方便，也可以使用 auto it; vector <int>::iterator it; for (it = vec.begin(); it != vec.end(); ++it) { cout << *it << " "; }
B) list
-
雙向鏈表容器
-
list 中的元素可以分散存儲在記憶體空間
優勢：在任意位置插入和刪除元素的時間複雜度 = O(1)，效率高，且迭代器不會失效
缺點：無法使用下標訪問元素，只能遍歷尋找
-
-
使用方法：
#include <list> // list 的頭文件 using namespace std; // 創建：list <存儲的數據類型> 標識符名稱; list <int> num; -
常用函數：
num.push_front(1); // 在頭部插入元素 1 num.push_back(1); // 在尾部添加元素 1 num.pop_front(); // 刪除第一個元素 num.pop_back(); // 刪除最後一個元素 num.insert(iter, 1); // 在 iter 指向的位置添加元素 1 num.erase(iter); // 刪除 iter 指向的位置的元素 find(num.begin(), num.end(), 1); // 返回元素 1 所在位置的迭代器
3. 關聯容器（associative container）
- 關聯性容器，實現了有序關聯數組
- 使用的數據結構是 “紅黑樹”（一種二叉平衡樹）
- 例子：set、map
A) set
-
set 是包含不重覆元素的無序集合
無序，指的是 set 內的元素不按照 “插入順序” 進行排列
-
內部的元素根據大小順序進行排列
-
使用方法：
#include <set> // map 的頭文件 using namespace std; set <int> s; -
常用函數：
s.insert(val); // 插入元素 val（不可以插入重覆的元素） s.find(val); // 返回 val 所在位置的迭代器 s.erase(s.find(val)); // 由於 set 無序且無法用下標訪問，需要遍歷尋找再進行刪除 s.count(val); // 統計 set 內有多少元素 val // 由於不允許出現重覆性的元素，因此返回值只有 0 和 1
B) map
-
將一個數據映射到另一個數據，每個元素都是一個 pair <Key, T>
map 中的每個 Key 不允許出現重覆
-
可以通過下標訪問，訪問時如果元素不存在，則會創建一個
-
使用方法：
#include <map> // map 的頭文件 #include <string> // string 的頭文件 using namespace std; int main() { map <string, int> m; // 添加的方法1 // 為 map 中添加 make_pair("Karry", 921) m["Karry"] = 921; // 添加的方法2 m.insert(make_pair("Brenda", 221)); return 0; } -
常用函數：
m.find(key); // 返回指向 key 的迭代器 m.count(key); // 返回 map 內 key 的數量 // 由於不允許出現重覆元素，因此返回值只有 0 或 1 m.erase(m.find(key)); // 刪除元素 key
迭代器
介紹
-
迭代器（iterator）類似指針，是一種用來遍歷元素的數據類型
優勢：不需要暴露訪問對象的內部表示就可以順序訪問對象的元素
-
以 vector 為例的使用方法：
// 定義迭代器 // 迭代器 iter 指向 int 類型的 vector vector <int>::iterator iter; x.begin(); // 返回 vector x 中第一個元素的迭代器 x.end(); // 返回 vector x 中最後一個元素之後的位置的迭代器 // begin 和 end 形成了左閉右開的區間 ++iter // 下一個位置的迭代器 --iter // 上一個位置的迭代器 iter += n // 從 iter 位置開始算，後面第 n 個位置的迭代器 iter -= n // 從 iter 位置開始算，前面第 n 個位置的迭代器 *iter // 解引用運算符，返回左值引用，返回 iter 指向的位置的數據 -
用迭代器來遍歷容器的方法可參考 vector 處的遍歷方法
失效
-
迭代器失效 = 迭代器不再指向原本應指向的元素
-
以 vector 為例，導致迭代器失效的情況：
-
添加元素
-
使用
insert插入元素在特定位置添加元素，其餘的元素會向後挪，由於原先記憶體空間存儲的元素改變，因此受影響的迭代器失效。
-
使用
push_back插入元素當 size 達到 capacity 時，vector 會額外申請一個 2*capacity 的記憶體空間，並將原有的數據移到新記憶體空間，因此所有的迭代器均失效。
-
-
刪除元素
-
使用
erase刪除元素刪除特定位置的元素後，其餘位置會向前挪，原先的記憶體空間存儲的元素改變，受影響的迭代器失效。例：
vector <int> vec = {1, 2, 3, 4, 5}; auto first = vec.begin(); // first 指向 1 auto second = vec.begin() + 1; // second 指向 2 auto third = vec.begin() + 2; // third 指向 3 auto itr = vec.erase(second); // 刪除了迭代器 second 指向的元素，vec = {1, 3, 4, 5} // first 指向 1，沒有改變 // second 和 third 失效 // itr 指向第二個位置的新元素 3
-
-
-
迭代器的失效和容器的數據結構有關，絕對安全的準則是：修改了容器內容後，不使用先前的迭代器
