Learning Objectives
- 用 vector 儲存數量會變動的資料，說明 size 與 capacity 的差別，以及容量不夠時的重新配置
- 分辨 [] 與 at()：哪一個會檢查範圍
- 用 list 在前後與中間插入元素，說明它和 vector 在記憶體配置上的不同
- 用 map 依鍵儲存與查詢資料，說明 [] 找不到鍵時會新增，find 與 count 只查詢
- 用迭代器 begin、end 指定範圍，搭配 sort、find、count、accumulate 等演算法
為什麼要用標準模板庫
內建陣列的大小在宣告時就固定了：int scores[30]; 最多只能放 30 個，班上來了第 31 位同學就放不下；
想在中間插入一筆、刪除一筆，也要自己寫迴圈搬移元素。這些事情幾乎每個程式都會遇到，所以 C++ 標準函式庫已經寫好了一整套工具，
稱為標準模板庫（Standard Template Library，STL）。它由三部分組成：
| 部分 | 做什麼 | 本課會用到的 |
|---|---|---|
| 容器（container） | 存放一群資料 | vector、list、map |
| 迭代器（iterator） | 指出容器裡的某個位置，用來走訪 | begin()、end() |
| 演算法（algorithm） | 對「一段範圍」做事 | sort、find、count、accumulate |
容器的名字後面要用角括號寫出元素型別，例如 vector<int>、map<string, int>：它們都是類別模板，第 18 課會說明模板怎麼寫。
STL 由 Alexander Stepanov 和 Meng Lee 提出，1994 年被 C++ 標準委員會接受，寫進標準草案，之後成為 C++ 標準函式庫的一部分。
本課的動畫會把容器真正放資料的地方畫在堆積（heap）區：vector 是一整塊連續的緩衝區（含還沒使用的容量），
list 和 map 則是一個一個分開的節點。三者的差別，看圖最清楚。
vector：size、capacity 與重新配置
v 本身在堆疊上，元素放在堆積上的緩衝區。每次 push_back 後注意兩件事：size 是已經放了幾個元素，capacity 是緩衝區總共放得下幾個（虛線框的空格是還沒使用的空位）。容量用完時，vector 會配置一塊更大的新緩衝區、把舊元素搬過去，緩衝區的位址也跟著改變。
vector 的記憶體
vector 的元素在記憶體裡連續排列，和陣列一樣，所以 v[i] 可以直接算出位址，存取很快。
它能變大的祕密是：緩衝區通常比實際需要的大一些。容量用完時，push_back 會：
- 配置一塊更大的新緩衝區
- 把舊元素搬過去
- 釋放舊緩衝區
動畫裡容量是 1、2、4、8 地翻倍，這是 g++ 的標準函式庫的做法；C++ 標準只要求 push_back 平均起來夠快，沒有規定成長的倍數，
其他編譯器可能不同。如果事先知道大約要放多少個，可以先 reserve(n)，省掉中途的搬移。
| 寫法 | 意思 |
|---|---|
vector<int> v; |
空的 vector |
vector<int> v(5); |
5 個元素，都是 0 |
vector<int> v(3, 7); |
3 個元素，都是 7 |
vector<int> v = {3, 8, 5}; |
用初始值列表 |
v[i] |
第 i 個元素，不檢查範圍，越界是未定義行為 |
v.at(i) |
第 i 個元素，越界時丟出 std::out_of_range 例外 |
v.front()、v.back() |
第一個、最後一個元素 |
v.push_back(x)、v.pop_back() |
在尾端加入、移除 |
重新配置之後，指向舊緩衝區的指標、參考與迭代器都失效了：它們還記得舊位址，但那塊記憶體已經還給系統。
走訪、insert、erase 與迭代器
第 12、13 行在中間插入、在開頭刪除，注意後面的元素整批往後或往前移，因為 vector 要維持連續。第 15 行的 it 是迭代器：動畫顯示它指向哪一格，++it 往下一格移動，走到 end()（最後一個元素的下一格）就停止。
想一想：vector
下面的程式會印出什麼？
vector<int> v = {1, 2, 3};
v.push_back(4);
v.erase(v.begin() + 1);
cout << v.size() << " " << v[1];
下面的程式執行後會怎樣？（v 一開始的 capacity 是 3）
vector<int> v = {1, 2, 3};
int* p = &v[0];
v.push_back(4);
cout << *p;
list：雙向鏈結串列
list 的每個元素放在一個獨立配置的節點裡，節點除了資料，還記著前一個和後一個節點的位址，像一串用繩子連起來的珠子。
因為不需要連續，在任何位置插入或刪除，只要改前後節點的連結，其他元素都不用搬；代價是不能用索引：
list 沒有 []，要找第 5 個元素，只能從頭一個一個走過去。
| 操作 | vector |
list |
|---|---|---|
用索引存取 [i] |
可以，很快 | 不支援 |
| 在尾端加入 | push_back |
push_back |
| 在開頭加入 | 用 insert，所有元素要往後搬 |
push_front，不用搬 |
| 在中間插入、刪除 | 後面的元素都要搬 | 只改前後的連結 |
| 記憶體 | 一整塊連續 | 每個元素一個節點，另外存兩個指標 |
大多數情況先選 vector；只有在中間插入、刪除很頻繁，而且不需要用索引時，才考慮 list。
list 的節點
每次加入元素，堆積上就多一個節點，箭頭表示節點之間前後的連結。push_front 把新節點接在最前面，insert(it, "Bob") 插在 it 指的節點前面，原有節點的位址都不變。
map：依鍵查詢
map<K, V> 儲存「鍵（key）→ 值（value）」的配對，例如商品名稱對庫存數量。每個鍵只會出現一次，
而且 map 會自動依鍵排序（字串依字典順序、數字由小到大），所以走訪時一定是排好的順序。
| 寫法 | 意思 |
|---|---|
m[k] = v; |
設定 k 的值；k 不存在就新增 |
m[k] |
讀取 k 的值；k 不存在時會新增一筆，值是預設值（int 是 0） |
m.count(k) |
k 存在回傳 1，不存在回傳 0，不會新增 |
m.find(k) |
回傳指向該筆的迭代器；找不到回傳 m.end()，不會新增 |
m.erase(k) |
刪除 k |
map 的元素型別是 pair<const K, V>，鍵叫 first、值叫 second。走訪時可以用 C++17 的結構化繫結（structured binding）
一次拆成兩個名字：for (const auto& [name, qty] : m)。
只想「查查看有沒有」時，用 count 或 find，不要用 []，否則會不小心多出一筆資料。
map 的排序、[] 與 find
依序加入 pear、apple、kiwi，但動畫裡的節點一直依鍵的字母順序排列。第 13 行只是想讀 grape 的值，注意它執行完之後 map 多了一個節點。
迭代器與演算法
迭代器的用法很像指標：*it 取得元素、++it 前進一格、it1 != it2 比較位置。
每個容器都有 begin()（第一個元素）和 end()（最後一個元素的下一個位置，不能取值）。
[begin, end) 這種「包含開頭、不含結尾」的範圍，是 STL 的共同語言。
<algorithm> 和 <numeric> 裡的函式都接收一段範圍，所以同一個 find 可以用在 vector、list 或陣列上：
| 函式 | 標頭檔 | 做什麼 |
|---|---|---|
sort(b, e) |
<algorithm> |
由小到大排序（需要能隨機存取，list 要用自己的 names.sort()） |
sort(b, e, cmp) |
<algorithm> |
依 cmp 規定的順序排序 |
find(b, e, x) |
<algorithm> |
回傳第一個等於 x 的位置，找不到回傳 e |
count(b, e, x) |
<algorithm> |
等於 x 的元素有幾個 |
accumulate(b, e, init) |
<numeric> |
從 init 開始，把每個元素加上去 |
accumulate 的結果型別和 init 相同：加總 double 時要寫 0.0，寫成 0 會每一步都轉成整數。
sort、find、count 與 accumulate
第 13 行的 it 是 find 回傳的迭代器，it - scores.begin() 算出它是第幾個元素。第 20 行把一個 lambda（寫在現場的小函式）交給 sort 當比較規則：a > b 時 a 排前面，所以變成由大到小；動畫會顯示 sort 呼叫它比較的過程。
想一想：list、map 與演算法
下面的程式會印出什麼？
map<string, int> m;
m["b"] = 2;
m["a"] = 1;
if (m["c"] == 0) cout << "zero ";
cout << m.size() << " " << m.begin()->first;
下面的程式會印出什麼？
vector<double> v = {1.5, 2.5};
cout << accumulate(v.begin(), v.end(), 0);
一個待辦清單程式，常常要在清單中間插入或刪除項目，而且只會從頭到尾依序走訪，從不用索引。哪個容器最合適？
動手寫：統計投票
votes 裡是每一票投的飲料。請用 map<string, int> 統計每種飲料的票數，依名稱順序印出「名稱: 票數」，最後印出票數最多的飲料。
重點回顧
- STL 由容器、迭代器、演算法組成；容器名稱後面用角括號寫元素型別，例如
vector<int> vector的元素連續排列在堆積上的緩衝區：size 是元素個數、capacity 是緩衝區大小；容量用完會重新配置，舊的指標、參考、迭代器隨之失效v[i]不檢查範圍，v.at(i)越界時丟出std::out_of_rangelist每個元素一個節點，前後插入刪除不用搬移元素，但不能用索引map依鍵自動排序；[]找不到鍵會新增一筆，只想查詢時用count或findbegin()到end()是「包含開頭、不含結尾」的範圍；sort、find、count、accumulate都用這種範圍工作