C++ Primer 第 10 章算法與迭代器習題完整解答與代碼詳解

前言

《C++ Primer》第 10 章重點講解泛型算法、迭代器、Lambda 表達式、綁定器與函數對象。本文提供全部習題（10.1~10.42）的完整可編譯參考代碼，並對關鍵算法（count、accumulate、equal、fill_n、copy、unique_copy、partition、sort、stable_sort、bind、lambda、流迭代器、反向迭代器等）進行逐行註釋與原理解析，幫助讀者掌握 STL 算法實戰技巧。

一、習題代碼彙總（核心片段）

10.1-10.2：count 算法統計元素出現次數

// 10.1: vector + count
vector vi; int val;
while (cin >> val) vi.push_back(val);
cout << "Count: " << count(vi.begin(), vi.end(), val) << endl;

// 10.2: list + count
list ls; string word;
while (cin >> word) ls.push_back(word);
cout << "Count: " << count(ls.begin(), ls.end(), word) << endl;

10.3-10.4：accumulate 求和（注意初值類型決定推導類型）

// 10.3: int 累加
cout << accumulate(vi.begin(), vi.end(), 0) << endl; // 初值 0 → int

// 10.4: double 累加
cout << accumulate(vd.begin(), vd.end(), 0.0) << endl; // 初值 0.0 → double

10.5：equal 比較序列（含 C 風格字符串陷阱）

char* p[] = {"Hello", "World", "!"};
char* q[] = {strdup(p[0]), strdup(p[1]), strdup(p[2])}; // 深拷貝
char* r[] = {p[0], p[1], p[2]}; // 淺拷貝，同一地址
cout << equal(begin(p), end(p), q) << endl; // 1 (內容相同)
cout << equal(begin(p), end(p), r) << endl; // 1 (地址相同)

10.6-10.8：fill_n、back_inserter 填充容器

// 10.6: fill_n 將 vector 全部置 0
fill_n(vi.begin(), vi.size(), 0);

// 10.7: copy list 到 vector (back_inserter 自動擴容)
copy(lst.begin(), lst.end(), back_inserter(vec));

// 10.8: fill_n + back_inserter 構造指定大小 vector
vector vec;
fill_n(back_inserter(vec), 10, 0); // vec 變為 10 個 0

10.9-10.11：sort、unique、erase 去重 + stable_sort 保持相對順序

void elimDups(vector& words) {
    sort(words.begin(), words.end()); // 排序
    auto end_unique = unique(words.begin(), words.end()); // 相鄰重複後移
    words.erase(end_unique, words.end()); // 真正刪除
}

bool isShorter(const string& a, const string& b) {
    return a.size() < b.size();
}

// 10.11: 先去重，再按長度穩定排序（相同長度保持字典序）
elimDups(words);
stable_sort(words.begin(), words.end(), isShorter);

10.13：partition 分區（將滿足條件元素移至前部）

bool five_or_more(const string& s) { return s.size() >= 5; }
auto it = partition(words.begin(), words.end(), five_or_more);
// [begin, it) 為長度>=5 的單詞，順序不保證

10.14-10.15：Lambda 表達式基礎與捕獲

// 10.14: 簡單 lambda
auto sum = [](int a, int b) { return a + b; };
cout << sum(1, 1) << endl;

// 10.15: 值捕獲
void add(int a) {
    auto sum = [a](int b) { return a + b; }; // 捕獲 a 副本
    cout << sum(1) << endl;
}

10.21：mutable Lambda 修改捕獲變量

int i = 5;
auto f = [i]() mutable -> bool {
    if (i > 0) { i--; return false; }
    return true;
};
// 每次調用 f() 修改副本 i，不影響外部 i

10.22-10.25：bind 綁定器與佔位符

using namespace std::placeholders;

// 10.22: bind 綁定參數順序
bool check_size(const string& s, string::size_type sz) {
    return s.size() >= sz;
}
auto bc = count_if(words.begin(), words.end(), bind(check_size, _1, 6));
// _1 佔位第一個參數(詞)，6 綁定第二個參數

// 10.24: 尋找第一個長度 >= 字符串長度的數字
auto p = find_if(vc.begin(), vc.end(), bind(check_size, s, _1));
// s 為 string，_1 為 vector 元素

10.25-10.27：綜合實戰：去重 + 分區 + 輸出

void biggies(vector& words, vector::size_type sz) {
    elimDups(words); // 去重
    auto wc = partition(words.begin(), words.end(), bind(check_size, _1, sz));
    auto count = wc - words.begin();
    cout << count << " words of length " << sz << " or longer" << endl;
    for_each(words.begin(), wc, [](const string& s){ cout << s << " "; });
    cout << endl;
}

10.27-10.28：unique_copy + 三種插入器

// 10.27: inserter (指定位置插入)
unique_copy(vi.begin(), vi.end(), inserter(li, li.begin()));

// 10.28: back_inserter / front_inserter / inserter 對比
unique_copy(vi.begin(), vi.end(), back_inserter(li1));  // 尾部插入，順序同 vi
unique_copy(vi.begin(), vi.end(), front_inserter(li2)); // 頭部插入，順序反轉
unique_copy(vi.begin(), vi.end(), inserter(li3, li3.begin())); // 指定位置

10.29-10.31：流迭代器 (istream_iterator/ostream_iterator)

// 10.29: 從文件讀單詞到 vector
istream_iterator in(inFile), eof;
vector words(in, eof); // 範圍構造

// 10.30: 從 cin 讀 int，排序，輸出到 cout
istream_iterator in(cin), eof;
vector vi(in, eof);
sort(vi.begin(), vi.end());
copy(vi.begin(), vi.end(), ostream_iterator(cout, " "));

// 10.31: 去重輸出
unique_copy(vi.begin(), vi.end(), ostream_iterator(cout, " "));

10.32-10.33：Sales_data 實戰 + accumulate 分組統計

// 10.32: 按 ISBN 分組累加
sort(vs.begin(), vs.end(), compareIsbn);
auto l = vs.begin();
while (l != vs.end()) {
    auto r = find_if(l+1, vs.end(), [l](const Sales_data& s){ return s.isbn() != l->isbn(); });
    cout << accumulate(l+1, r, *l) << endl; // 累加同 ISBN 記錄
    l = r;
}

// 10.33: 奇偶分離寫入不同文件
ostream_iterator out1(oddFile, " "), out2(evenFile, "\n");
while (in != eof) {
    if (*in & 1) *out1++ = *in;
    else *out2++ = *in;
    ++in;
}

10.34-10.35：反向迭代器遍歷

// 10.34: 反向迭代器 (crbegin/crend)
for (auto r = vi.crbegin(); r != vi.crend(); ++r) cout << *r << " ";

// 10.35: 普通迭代器逆向 (cend 遞減)
for (auto r = vi.cend(); r != vi.cbegin(); ) cout << *--r << " ";

10.36-10.37：find 反向查找最後一個 0 + copy 反向範圍

// 10.36: 反向迭代器找最後一個 0
auto rz = find(li.rbegin(), li.rend(), 0);
int pos = distance(li.begin(), rz.base()); // base() 轉正向迭代器，指向 0 後一個

// 10.37: 複製 vi[3..7] 逆序到 list (注意反向迭代器範圍)
copy(vi.rbegin() + 2, vi.rbegin() + 7, back_inserter(li)); // vi[7] 到 vi[3]

二、核心知識點總結

1. 算法分類與選擇

類別	代表算法	特點
非修改序列	find, count, equal, search, all_of	只讀，不改變元素
修改序列	copy, fill, transform, replace, remove	改變元素值/位置
排序相關	sort, stable_sort, partial_sort, nth_element	需隨機訪問迭代器
二分查找	binary_search, lower_bound, equal_range	要求有序序列
集合操作	set_union, set_intersection, set_difference	有序範圍
堆操作	make_heap, push_heap, pop_heap, sort_heap	堆結構
極值	min_element, max_element, minmax_element	返回迭代器

2. 迭代器分類與算法要求

輸入迭代器  → 只讀單向
輸出迭代器  → 只寫單向
前向迭代器  → 讀寫單向 (forward_list)
雙向迭代器  → 讀寫雙向 (list, map, set)
隨機訪問迭代器 → 讀寫隨機 (vector, deque, array, string)

算法要求最低迭代器類別：如 sort 需隨機訪問，reverse 需雙向，find 只需輸入。

3. Lambda 核心語法

[捕獲列表] (參數列表) mutable(可選) -> 返回類型(可選) { 函數體 }
```
捕獲模式：
- `[=]` 值捕獲所有
- `[&]` 引用捕獲所有
- `[x, &y]` 混合捕獲
- `mutable` 允許修改值捕獲的變量

4. bind 佔位符 _1, _2... 對應調用時參數位置

返回可調用對象，可綁定任意參數、調整順序、固定部分參數。

三、常見錯誤避雷

1. accumulate 初值類型決定計算類型：0 為 int，0.0 為 double。
2. unique 只移動重複元素到末尾，**不改變容器大小**，必須配合 erase。
3. partition 不保證相對順序，需穩定分區用 stable_partition。
4. bind 參數按值捕獲，需引用用 std::ref/std::cref。
5. 反向迭代器 base() 返回的正向迭代器指向**下一個**元素，轉換時需注意偏移。
6. 流迭代器構造 vector 時：vector(istream_iterator(in), istream_iterator())。