迭代器是連接容器與演算法的橋樑。STL 演算法透過迭代器操作資料，讓你無需了解容器的內部實作，就能對資料進行排序、搜尋、轉換等操作。學會「用演算法表達意圖」而非「手寫迴圈」，是寫出現代、正確、高效 C++ 的關鍵一步。
學習目標
讀完本章，你應該能夠：
- 說明六種迭代器類別（input/output/forward/bidirectional/random-access/contiguous）的能力差異，並指出哪些容器提供哪種迭代器
- 正確使用
begin/end、cbegin/cend、rbegin/rend取得迭代器，並用advance/next/prev/distance操作迭代器 - 理解「半開區間
[begin, end)」的設計哲學，並解釋為什麼end()不可解引用 - 熟練使用非修改型演算法：
find、find_if、count、all_of、any_of、none_of、for_each、search - 熟練使用修改型演算法：
copy、transform、fill、generate、replace，並掌握 erase-remove 慣用法 - 掌握排序家族：
sort、stable_sort、partial_sort、nth_element，以及它們的複雜度取捨 - 掌握二分搜尋家族（需先排序）：
binary_search、lower_bound、upper_bound、equal_range - 使用
<numeric>的數值演算法：accumulate、inner_product、iota、reduce - 使用集合運算與
min_element/max_element/minmax_element - 理解「優先使用標準演算法而非手寫迴圈」的理由（C++ Core Guidelines），並認識 C++17 的執行策略（parallel algorithms）
一、為什麼要用演算法，而不是手寫迴圈？（WHY）
許多初學者習慣對任何資料處理都寫一個 for 迴圈。但 C++ Core Guidelines 明確建議：
Core Guidelines P.3 / SL.1：「Prefer standard-library algorithms to hand-written loops.」
原因有四：
| 理由 | 說明 |
|---|---|
| 表達意圖 | std::sort(v.begin(), v.end()) 一眼就知道在排序；手寫的迴圈要讀完才知道。 |
| 減少錯誤 | 手寫迴圈常見的差一錯誤（off-by-one）、迭代器失效、邊界條件，標準演算法已替你處理好。 |
| 效能 | 標準庫實作經過高度最佳化（甚至會用 SIMD、特化），且容易被編譯器內聯。 |
| 可平行化 | C++17 起許多演算法支援執行策略，加一個參數就能平行執行（見第十一節）。 |
對照一下「找出第一個大於 50 的元素」：
// 手寫迴圈：容易寫錯邊界、忘記 break、回傳值不明確
int idx = -1;
for (size_t i = 0; i < v.size(); ++i) {
if (v[i] > 50) { idx = static_cast<int>(i); break; }
}
// 標準演算法：意圖清晰、無邊界錯誤
auto it = std::find_if(v.begin(), v.end(), [](int x){ return x > 50; });
本章後面會反覆呼應這個原則：先想「有沒有現成演算法」，再考慮手寫迴圈。
二、迭代器類別（Iterator Categories）
迭代器是「廣義指標」——它抽象了「指向序列中某個位置」的概念。STL 依能力把迭代器分成幾類，能力由弱到強。C++17 起正式區分出 contiguous iterator（連續迭代器），共六類。
2.1 能力總表
| 類別 | 能力 | 新增支援的操作 | 典型來源 |
|---|---|---|---|
| Input（輸入） | 單次走訪、唯讀、只能前進 | *it（讀）、++it、==/!= |
istream_iterator |
| Output（輸出） | 單次走訪、唯寫、只能前進 | *it = v（寫）、++it |
ostream_iterator、back_inserter |
| Forward（前向） | 可多次走訪、可讀寫、只能前進 | 可重複讀同一位置 | forward_list、unordered_* |
| Bidirectional（雙向） | 可前進可後退 | --it |
list、set、map |
| Random Access（隨機存取） | 可任意跳轉 | it + n、it[n]、it1 - it2、</> |
deque |
| Contiguous（連續，C++17） | 元素在記憶體中連續 | &*(it+n) == &*it + n |
vector、array、string、原生陣列 |
2.2 能力階層圖
Input ──┐
├──► Forward ──► Bidirectional ──► RandomAccess ──► Contiguous
Output ─┘
（弱） （強）
每個較強的類別都「繼承」較弱類別的所有能力。例如 Random Access Iterator 一定也能做 Bidirectional 能做的一切。Contiguous 是 Random Access 的加強版，額外保證「位址連續」，因此可以安全地取出底層指標傳給 C API。
2.3 哪個容器提供哪種迭代器？（重要對照表）
| 容器 | 迭代器類別 | 支援 it + n？ |
支援 --it？ |
|---|---|---|---|
array、vector、string |
Contiguous（隨機存取＋連續） | ✅ | ✅ |
deque |
Random Access（但非連續！） | ✅ | ✅ |
list |
Bidirectional | ❌ | ✅ |
set/map/multiset/multimap |
Bidirectional | ❌ | ✅ |
forward_list |
Forward | ❌ | ❌ |
unordered_set/unordered_map |
Forward | ❌ | ❌ |
stack/queue/priority_queue |
無（容器配接器，不提供迭代器） | — | — |
常考重點：
deque是 Random Access 但不是 Contiguous——它由多塊記憶體拼成，&v[0] + n不保證等於&v[n]。vector才是連續的。
迭代器類別直接決定「哪些演算法能用」。例如 std::sort 要求 Random Access，所以 std::list 不能用 std::sort，必須改用成員函式 list::sort()。
三、半開區間 [begin, end) 的設計哲學
STL 所有範圍都用「半開區間」：包含 begin，不包含 end。end() 指向「最後一個元素的再下一個位置」（past-the-end），是一個哨兵（sentinel），不可解引用。
索引: 0 1 2 3 4
┌────┬────┬────┬────┬────┐
v = │ 10 │ 20 │ 30 │ 40 │ 50 │
└────┴────┴────┴────┴────┘
▲ ▲
begin() end() ← 指向「最後一個之後」，不可 *end()
為什麼這樣設計？
- 空範圍很自然：當
begin == end時就代表空序列，不需特例。 - 長度 =
end - begin：直接相減即得元素數量（隨機存取迭代器）。 - 迴圈條件統一：
for (it = begin; it != end; ++it)，永遠用!=即可。 - 「找不到」有自然的回傳值：搜尋演算法找不到時回傳
end()，呼叫端統一檢查if (it != v.end())。
auto it = std::find(v.begin(), v.end(), 99);
if (it == v.end()) {
std::cout << "找不到\n"; // 99 不存在
}
// 注意：絕對不要寫 *it 或 *v.end()——未定義行為！
四、取得與操作迭代器
4.1 各種 begin/end
#include <vector>
std::vector<int> v = {10, 20, 30, 40, 50};
auto it = v.begin(); // 可讀寫，指向第一個元素
auto end = v.end(); // past-the-end 哨兵
auto cit = v.cbegin(); // const 迭代器（唯讀），即使 v 非 const
auto rit = v.rbegin(); // 反向迭代器，指向「最後一個元素」
auto rend = v.rend(); // 反向的尾端，指向「第一個元素之前」
auto crit = v.crbegin(); // const 反向迭代器
| 函式 | 方向 | 可否修改元素 | 起點 |
|---|---|---|---|
begin() / end() |
正向 | ✅ | 第一個 → 尾後 |
cbegin() / cend() |
正向 | ❌（唯讀） | 第一個 → 尾後 |
rbegin() / rend() |
反向 | ✅ | 最後一個 → 首前 |
crbegin() / crend() |
反向 | ❌（唯讀） | 最後一個 → 首前 |
最佳實踐（Core Guidelines ES.55 精神）：不需要修改元素時用
cbegin/cend，把「唯讀」意圖寫進程式碼，編譯器也能多一層保護。C++11 起也可用非成員的std::begin(c)／std::cbegin(c)，對原生陣列同樣有效。
4.2 迭代器輔助函式（<iterator>）
#include <iterator>
std::vector<int> v = {10, 20, 30, 40, 50};
auto it = v.begin();
std::advance(it, 3); // 就地前進 3 步 → 指向 v[3] = 40
auto nx = std::next(it); // 回傳 it 的下一個（it 本身不變）→ 50
auto pv = std::prev(it); // 回傳 it 的上一個 → 30
auto d = std::distance(v.begin(), it); // 兩迭代器間距離 = 3
| 函式 | 作用 | 會修改參數嗎？ |
|---|---|---|
advance(it, n) |
將 it 前進（或後退）n 步 |
✅ 就地修改 |
next(it, n=1) |
回傳前進 n 步後的新迭代器 | ❌ |
prev(it, n=1) |
回傳後退 n 步後的新迭代器 | ❌ |
distance(a, b) |
計算 a 到 b 的距離 | ❌ |
為什麼需要這些函式？ 因為
list、set的迭代器不支援it + n。advance/distance對任何迭代器都能用：遇到隨機存取迭代器是 O(1)，遇到雙向迭代器則退化為 O(n) 逐步移動。寫泛型程式時用它們才安全。
4.3 插入迭代器（Insert Iterators）
當演算法要「寫入」一個容器，但你不確定容器夠不夠大時，用插入迭代器自動擴充：
#include <iterator>
std::vector<int> src = {1, 2, 3};
std::vector<int> dst;
std::copy(src.begin(), src.end(), std::back_inserter(dst)); // 自動 push_back
std::list<int> lst;
std::copy(src.begin(), src.end(), std::front_inserter(lst)); // 自動 push_front
| 插入迭代器 | 底層呼叫 | 適用容器 |
|---|---|---|
back_inserter(c) |
c.push_back() |
vector、deque、list、string |
front_inserter(c) |
c.push_front() |
deque、list、forward_list（vector 不支援） |
inserter(c, pos) |
c.insert(pos, ...) |
幾乎所有容器 |
五、非修改型演算法（Non-modifying）
這類演算法只「讀」資料，不改變序列內容。標頭檔皆為 <algorithm>。
5.1 find / find_if / find_if_not
std::vector<int> v = {10, 20, 30, 40, 50};
auto it = std::find(v.begin(), v.end(), 30); // 找值
auto it2 = std::find_if(v.begin(), v.end(), [](int x){ return x > 25; }); // 找符合條件
auto it3 = std::find_if_not(v.begin(), v.end(), [](int x){ return x < 25; }); // 找第一個不符合
if (it != v.end()) std::cout << "找到：" << *it << "\n"; // 找到：30
5.2 count / count_if
std::vector<int> v = {1, 2, 3, 2, 4, 2, 5};
int n = std::count(v.begin(), v.end(), 2); // 3
int m = std::count_if(v.begin(), v.end(), [](int x){ return x % 2 == 0; }); // 4
5.3 all_of / any_of / none_of（C++11）
這三個謂詞檢查器讓條件判斷一目了然，是取代手寫旗標迴圈的利器：
std::vector<int> v = {2, 4, 6, 8};
bool allEven = std::all_of (v.begin(), v.end(), [](int x){ return x % 2 == 0; }); // true
bool anyOdd = std::any_of (v.begin(), v.end(), [](int x){ return x % 2 != 0; }); // false
bool noneNeg = std::none_of(v.begin(), v.end(), [](int x){ return x < 0; }); // true
| 演算法 | 回傳 true 的條件 | 空範圍時 |
|---|---|---|
all_of |
全部元素都滿足 | true（vacuous truth） |
any_of |
至少一個滿足 | false |
none_of |
沒有任何元素滿足 | true |
5.4 for_each
對範圍內每個元素執行動作（常用於「副作用」，如輸出或就地修改）：
std::vector<int> v = {1, 2, 3};
std::for_each(v.begin(), v.end(), [](int x){ std::cout << x << " "; }); // 1 2 3
std::for_each(v.begin(), v.end(), [](int& x){ x *= 10; }); // 就地修改
純粹遍歷輸出時，range-based for（
for (int x : v)）通常更易讀；for_each的優勢在於能直接傳入既有的可呼叫物件，或只處理子範圍。
5.5 search / equal / mismatch
std::vector<int> haystack = {1, 2, 3, 4, 5, 6};
std::vector<int> needle = {3, 4, 5};
// search：找子序列第一次出現的位置
auto it = std::search(haystack.begin(), haystack.end(), needle.begin(), needle.end());
if (it != haystack.end())
std::cout << "子序列起始索引：" << std::distance(haystack.begin(), it) << "\n"; // 2
// equal：兩範圍是否逐元素相等
bool same = std::equal(needle.begin(), needle.end(), haystack.begin() + 2); // true
六、修改型演算法（Modifying）
這類演算法會改變目標序列。
6.1 copy / copy_if / copy_n
std::vector<int> src = {1, 2, 3, 4, 5, 6};
std::vector<int> dst;
std::copy(src.begin(), src.end(), std::back_inserter(dst));
std::vector<int> evens;
std::copy_if(src.begin(), src.end(), std::back_inserter(evens),
[](int x){ return x % 2 == 0; }); // {2, 4, 6}
6.2 transform（最重要的「映射」演算法）
std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int> out(v.size());
// 一元：每個元素乘 2
std::transform(v.begin(), v.end(), out.begin(), [](int x){ return x * 2; });
// out = {2, 4, 6, 8, 10}
// 二元：兩序列對應元素相加
std::vector<int> a = {1, 2, 3}, b = {10, 20, 30}, c(3);
std::transform(a.begin(), a.end(), b.begin(), c.begin(),
[](int x, int y){ return x + y; });
// c = {11, 22, 33}
transform與for_each的差別：transform產生「新值寫入輸出範圍」（函數式的 map），for_each著重「副作用」。要轉換資料就用transform。
6.3 fill / fill_n / generate / iota
#include <numeric> // iota
std::vector<int> v(5);
std::fill(v.begin(), v.end(), 7); // {7,7,7,7,7}
int n = 0;
std::generate(v.begin(), v.end(), [&n](){ return n++; }); // {0,1,2,3,4}（用產生器函式）
std::iota(v.begin(), v.end(), 1); // {1,2,3,4,5}（遞增填充，<numeric>）
| 演算法 | 用途 |
|---|---|
fill / fill_n |
填入同一個固定值 |
generate / generate_n |
每格呼叫產生器函式取值 |
iota（<numeric>） |
從起始值開始遞增填入（1,2,3,...） |
6.4 replace / replace_if
std::vector<int> v = {1, 2, 3, 2, 5};
std::replace(v.begin(), v.end(), 2, 99); // {1,99,3,99,5}
std::replace_if(v.begin(), v.end(), [](int x){ return x > 50; }, 0); // {1,0,3,0,5}
6.5 ⭐ erase-remove 慣用法（必須掌握）
這是 STL 最重要、也最容易誤用的慣用法。關鍵認知：
std::remove/remove_if不會真正刪除元素！ 它們只是把「要保留的元素」往前搬，然後回傳一個「新邏輯結尾」迭代器。容器的大小完全沒變，尾端殘留著未定義的舊值。
原始: v = [1, 2, 3, 2, 4, 2, 5] 移除所有 2
┌ remove 把保留元素往前搬
搬移後: v = [1, 3, 4, 5, ?, ?, ?]
▲
new_end（remove 的回傳值）
真正刪除: v.erase(new_end, v.end()); → v = [1, 3, 4, 5]
所以必須搭配容器的 erase 才能真正縮小：
std::vector<int> v = {1, 2, 3, 2, 4, 2, 5};
v.erase(std::remove(v.begin(), v.end(), 2), v.end()); // 移除所有 2 → {1,3,4,5}
v.erase(std::remove_if(v.begin(), v.end(),
[](int x){ return x % 2 != 0; }), v.end()); // 移除所有奇數
C++20 補充：標準庫新增了自由函式
std::erase(v, value)與std::erase_if(v, pred)，一行搞定。但在 C++17 中，erase-remove 慣用法仍是標準做法。
6.6 unique（去除「相鄰」重複）
std::vector<int> v = {1, 1, 2, 3, 3, 3, 4, 5, 5};
v.erase(std::unique(v.begin(), v.end()), v.end()); // {1,2,3,4,5}
陷阱：
unique只移除相鄰重複。若要全域去重，必須先sort再unique。
七、排序家族
7.1 四種排序比較
| 演算法 | 作用 | 複雜度 | 穩定？ | 何時用 |
|---|---|---|---|---|
sort |
全部排好序 | O(N log N) | ❌ | 預設首選 |
stable_sort |
全部排序，保留相等元素相對順序 | O(N log²N)（記憶體足夠時 O(N log N)） | ✅ | 需要穩定性（如多鍵排序） |
partial_sort |
只把前 k 個最小排到前面 | O(N log k) | ❌ | 只要前幾名 |
nth_element |
把第 n 個元素放到排序後的位置，左小右大 | 平均 O(N) | ❌ | 找中位數／第 k 小 |
std::vector<int> v = {5, 2, 8, 1, 9, 3, 7};
std::sort(v.begin(), v.end()); // 升序
std::sort(v.begin(), v.end(), std::greater<>()); // 降序
// partial_sort：只要最小的 3 個排好（其餘順序不定）
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// nth_element：把「排序後會在索引 3 的元素」放到位置 3
std::nth_element(v.begin(), v.begin() + 3, v.end());
std::cout << "第 4 小的值：" << v[3] << "\n";
效能洞察：要找「最小的 3 個」，用
partial_sort比「sort完整排序再取前 3」快得多；只要「中位數」用nth_element（平均線性時間）更划算。選對演算法 = 免費的效能。
7.2 嚴格弱序（Strict Weak Ordering）
自訂比較函式必須滿足嚴格弱序，否則 sort 行為未定義（可能崩潰）：
comp(a, a)必須為false（非自反）- 若
comp(a, b)為 true，則comp(b, a)必須為 false（非對稱） - 可遞移
// ✅ 正確：用 < 不用 <=
std::sort(v.begin(), v.end(), [](int a, int b){ return a < b; });
// ❌ 錯誤：用 <= 違反非自反性，UB！
// std::sort(v.begin(), v.end(), [](int a, int b){ return a <= b; });
八、二分搜尋家族（前提：序列已排序）
對已排序範圍做 O(log N) 搜尋。若未排序，結果未定義。
std::vector<int> v = {1, 3, 5, 5, 5, 7, 9}; // 已排序
bool found = std::binary_search(v.begin(), v.end(), 5); // true：存不存在
auto lb = std::lower_bound(v.begin(), v.end(), 5); // 第一個 >= 5 → 指向索引 2
auto ub = std::upper_bound(v.begin(), v.end(), 5); // 第一個 > 5 → 指向索引 5
auto [b, e] = std::equal_range(v.begin(), v.end(), 5); // 等於 [lb, ub)
std::cout << "5 出現次數：" << std::distance(b, e) << "\n"; // 3
| 演算法 | 回傳 |
|---|---|
binary_search |
bool：目標是否存在 |
lower_bound |
第一個「不小於（≥）」目標的位置 |
upper_bound |
第一個「大於（>）」目標的位置 |
equal_range |
pair{lower_bound, upper_bound}，即所有等值元素的範圍 |
v = [1, 3, 5, 5, 5, 7, 9] 搜尋 5
索引: 0 1 2 3 4 5 6
▲ ▲
lower_bound upper_bound
(索引 2) (索引 5)
└─── equal_range = 3 個 5 ───┘
常見錯誤：對
std::set/std::map不要用std::lower_bound（會退化成 O(n)）。它們提供成員函式s.lower_bound(x)，利用樹結構達到 O(log n)。
九、數值演算法（<numeric>）
記住：這些在
<numeric>，不是<algorithm>！
9.1 accumulate
#include <numeric>
std::vector<int> v = {1, 2, 3, 4, 5};
int sum = std::accumulate(v.begin(), v.end(), 0); // 15
int prod = std::accumulate(v.begin(), v.end(), 1,
[](int a, int b){ return a * b; }); // 120
型別陷阱：初始值的型別決定累加型別。
std::accumulate(d.begin(), d.end(), 0)對vector<double>會用 int 累加（小數被截斷）！要寫0.0。
9.2 inner_product（內積／加權和）
std::vector<int> a = {1, 2, 3}, b = {4, 5, 6};
int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0); // 1*4+2*5+3*6 = 32
9.3 iota（遞增填充）
std::vector<int> v(5);
std::iota(v.begin(), v.end(), 10); // {10, 11, 12, 13, 14}
9.4 reduce（C++17，可平行版的 accumulate）
#include <numeric>
std::vector<int> v = {1, 2, 3, 4, 5};
int s = std::reduce(v.begin(), v.end()); // 15（與 accumulate 類似）
reduce與accumulate的關鍵差異：reduce不保證運算順序，因此可平行化（搭配執行策略），但要求運算可結合、可交換。對於浮點加法這種非嚴格結合的運算，結果可能與accumulate有微小差異。另有transform_reduce（先轉換再歸約）。
十、集合運算與極值
10.1 集合運算（需先排序）
std::vector<int> A = {1, 2, 3, 4, 5}, B = {3, 4, 5, 6, 7}, out;
std::set_union (A.begin(),A.end(), B.begin(),B.end(), std::back_inserter(out)); // 聯集 {1..7}
out.clear();
std::set_intersection(A.begin(),A.end(), B.begin(),B.end(), std::back_inserter(out)); // 交集 {3,4,5}
out.clear();
std::set_difference (A.begin(),A.end(), B.begin(),B.end(), std::back_inserter(out)); // 差集 {1,2}
也有 set_symmetric_difference（對稱差集）、merge（合併兩已排序序列）。
10.2 min/max 家族
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2};
auto mn = std::min_element(v.begin(), v.end()); // 指向 1
auto mx = std::max_element(v.begin(), v.end()); // 指向 9
auto [lo, hi] = std::minmax_element(v.begin(), v.end()); // 一次取得兩者
std::cout << "最小 " << *mn << "，最大 " << *mx << "\n";
// 注意區分：min_element 作用於「範圍」，min 作用於「兩個值」
int bigger = std::max(10, 20); // 20
十一、執行策略：平行演算法（C++17 簡介）
C++17 為許多演算法加入「執行策略」參數（標頭 <execution>），只要加一個參數就能要求平行執行：
#include <execution>
#include <algorithm>
std::vector<int> v(1'000'000);
// 序列（預設）
std::sort(v.begin(), v.end());
// 平行
std::sort(std::execution::par, v.begin(), v.end());
// 平行 + 向量化
std::sort(std::execution::par_unseq, v.begin(), v.end());
| 策略 | 意義 |
|---|---|
seq |
序列執行（與不加參數相同） |
par |
可多執行緒平行 |
par_unseq |
可平行 + 向量化（不保證執行緒邊界） |
注意：(1) 需要支援的標準庫實作（部分平台需連結 TBB，如 GCC 的
-ltbb）。(2) 傳給平行演算法的可呼叫物件必須是執行緒安全的，且不可拋例外（否則std::terminate）。本章僅作概念介紹，實務使用前請確認你的編譯環境。
最佳實踐（C++ Core Guidelines）
- 優先用演算法取代手寫迴圈（P.3、SL.1）：意圖清晰、減少錯誤、易最佳化。
- 唯讀就用
cbegin/cend：把不修改的意圖寫進型別（ES.55 精神）。 - 寫泛型程式時用
std::advance/std::distance/std::next，而非it + n，才能相容非隨機存取迭代器。 - 比較函式必須是嚴格弱序：用
<而非<=。 - 善用
nth_element、partial_sort：不要為了「找前幾名／中位數」而完整排序。 - 去重前先排序：
sort+unique+erase。 - 刪除元素用 erase-remove 慣用法（C++20 可用
std::erase/erase_if）。 accumulate注意初始值型別：浮點要用0.0、大數要用0LL。- 對關聯容器用成員版的
lower_bound，不要用通用演算法版。 - 明確指定要不要穩定性：需要時才付出
stable_sort的代價。
常見錯誤與陷阱
- 忘記
#include <numeric>：accumulate、inner_product、iota、reduce都在這裡，不在<algorithm>。 - 對未排序資料用
binary_search/lower_bound：結果未定義，必先排序。 remove不刪除元素：必須搭配erase，否則容器大小不變、尾端是垃圾值。unique只去相鄰重複：未先排序則非相鄰的重複留下來。- 迭代器失效：
vector的push_back/insert/erase可能使既有迭代器、指標、參考全部失效；操作後別再用舊迭代器。 std::sort用在list：list是雙向迭代器，不支援sort；用成員函式lst.sort()。- 解引用
end()：*v.end()是未定義行為；end()是哨兵不是元素。 - 比較函式違反嚴格弱序：用
<=會讓sortUB（可能崩潰或無窮迴圈）。 accumulate初始值型別錯誤：accumulate(v.begin(), v.end(), 0)對vector<double>會截斷成整數。min_element與min混淆：前者吃「範圍」回傳迭代器，後者吃「兩個值」回傳值。transform輸出空間不足：若直接寫到既有vector，要先resize，或改用back_inserter。deque當成連續記憶體：deque是隨機存取但非連續，不能&dq[0]當陣列指標傳給 C API。
重點整理
| 概念 | 要點 |
|---|---|
| 迭代器類別 | Input/Output/Forward/Bidirectional/RandomAccess/Contiguous，能力遞增 |
| 容器對應 | vector/array/string 連續；deque 隨機存取非連續；list/set/map 雙向；forward_list/unordered_* 前向 |
| 半開區間 | [begin, end)，end() 是哨兵不可解引用；找不到回傳 end() |
| 取得迭代器 | begin/end、cbegin/cend（唯讀）、rbegin/rend（反向） |
| 迭代器操作 | advance（就地）、next/prev（回傳新值）、distance |
| 非修改型 | find/find_if、count/count_if、all_of/any_of/none_of、for_each、search |
| 修改型 | copy/copy_if、transform、fill/generate/iota、replace、erase-remove、unique |
| 排序 | sort（不穩定）、stable_sort（穩定）、partial_sort（前 k）、nth_element（第 n） |
| 二分搜尋 | binary_search/lower_bound/upper_bound/equal_range（需先排序） |
| 數值 | accumulate/inner_product/iota/reduce（在 <numeric>） |
| 集合與極值 | set_union/intersection/difference、min/max/minmax_element |
| 平行（C++17） | std::execution::par 等執行策略 |
| 核心原則 | 優先用演算法表達意圖，而非手寫迴圈（Core Guidelines） |
練習題
每題附難度與提示。建議先自己動手，再對照
對應範例程式。所有程式須能以g++ -std=c++17 -Wall編譯。
練習 1（基礎）：統計分析
讀入一組整數（或用固定陣列），計算總和、平均值、最大值、最小值。要求使用 std::accumulate、std::min_element、std::max_element（不要手寫迴圈算這些）。
- 提示：平均值記得把總和轉成
double再除以size()；最值用*minIt解引用取得。
練習 2（基礎）：條件統計三連發
給定一組分數，用 std::all_of、std::any_of、std::none_of 分別回答：「是否全部及格（≥60）？」「是否有人滿分（100）？」「是否沒有人不及格？」，並用 std::count_if 算出及格人數。
- 提示：三個演算法都接受
(begin, end, 謂詞)，謂詞用 lambda 寫即可。
練習 3（中級）：篩選 + 轉換管線
有一個學生分數的 std::vector<int>。先用 std::copy_if 篩選出及格（≥60）的分數到新 vector，再用 std::transform 把每個分數轉成等級字串（A: ≥90、B: ≥80、C: ≥70、D: ≥60）。最後輸出等級序列。
- 提示：
copy_if搭配std::back_inserter；transform的輸出可寫到一個vector<std::string>（先resize或用back_inserter）。
練習 4（中級）：去重排序
讀入一組字串（含重複），輸出「去除重複後、按字典序排列」的結果。要求使用 std::sort + std::unique + erase。
- 提示：先
sort才能讓重複元素相鄰，unique才有效；unique回傳新邏輯結尾，要再erase(it, end())。
練習 5（中級）：第 k 小與中位數
給定一組整數，分別用 std::nth_element 找出「第 k 小的值」與「中位數」，並比較它與「完整 sort 後取索引」結果是否一致。
- 提示：
nth_element(begin, begin + k, end)後，v[k]就是第 k+1 小的值；偶數個元素的中位數是中間兩數平均。
練習 6（挑戰）：自訂多鍵排序
定義 struct Student { std::string name; int score; int age; };。先按分數降序，分數相同者按姓名字典序升序，再相同者按年齡升序。請用 std::sort 加單一比較 lambda 完成（思考：這裡需要 stable_sort 嗎？為什麼）。
- 提示：比較 lambda 內依序比較：
if (a.score != b.score) return a.score > b.score; if (a.name != b.name) return a.name < b.name; return a.age < b.age;。因為所有鍵都在比較函式裡決定了順序，所以用sort即可，不必stable_sort。
練習 7（挑戰）：值域查詢
給定一個已排序的整數 vector 與多個查詢區間 [lo, hi]，用 std::lower_bound 與 std::upper_bound 在 O(log N) 時間內回答「區間內有多少個元素」。
- 提示：答案 =
std::distance(lower_bound(begin,end,lo), upper_bound(begin,end,hi))。
對應範例程式
| 檔案 | 說明 |
|---|---|
| iterators.cpp | 迭代器類別、begin/end/cbegin/rbegin、advance/next/prev/distance、插入迭代器 |
| algorithms_basic.cpp | sort/stable_sort、find/find_if、count/count_if、for_each、accumulate、min/max_element、binary_search/lower_bound/upper_bound |
| algorithms_advanced.cpp | transform、copy_if、erase-remove、unique、reverse、rotate、partition、merge、集合運算、next_permutation |