您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

C++ Primer 第 9 章習題完整解答：序列容器與泛型演算法

編輯：關於C++

第 9 章核心考點回顧

本章聚焦序列容器（vector、deque、list、forward_list、array、string）的操作介面、迭代器分類、容量管理、以及泛型演算法應用。

習題精選解析

練習 9.1：容器選擇決策

場景	推薦容器	理由
(a) 固定數量單詞，按字典序插入	`list`	頻繁中間插入，`list` O(1) 插入不失效迭代器；`vector`/`deque` 中間插入 O(n)
(b) 未知數量單詞，尾部插入、頭部刪除	`deque` 或 `list`	雙端高頻操作，`deque` 另支援隨機存取
(c) 讀取整數、排序、輸出	`vector`	整數體積小、排序需隨機存取、`vector` 記憶體連續緩存友好

練習 9.3：迭代器範圍約束

begin 和 end 必須指向同一容器
end 為尾後位置（最後元素之後）
對 begin 反覆遞增必能到達 end（end 不在 begin 之前）

練習 9.4-9.5：泛型查找函數

// 回傳 bool 版本
template <typename Iterator, typename T>
bool find_val(Iterator begin, Iterator end, const T& val) {
    for (; begin != end; ++begin)
        if (*begin == val) return true;
    return false;
}

// 回傳迭代器版本（STL 風格）
template <typename Iterator, typename T>
Iterator find_val(Iterator begin, Iterator end, const T& val) {
    for (; begin != end; ++begin)
        if (*begin == val) return begin;
    return end;  // 未找到回傳 end
}

練習 9.6：list 迭代器比較錯誤

// 錯誤：list 迭代器不支援 < 運算子
while (iter1 < iter2)  // 編譯錯誤

// 正確：使用 !=
while (iter1 != iter2)

list 迭代器為雙向迭代器，僅支援 ++、--、==、!=。

練習 9.9-9.10：`begin`/`cbegin` 與型別推導

vector<int> v1;
const vector<int> v2;

auto it1 = v1.begin();      // vector<int>::iterator
auto it2 = v2.begin();      // vector<int>::const_iterator
auto it3 = v1.cbegin();     // vector<int>::const_iterator (C++11)
auto it4 = v2.cbegin();     // vector<int>::const_iterator

cbegin/cend 保證回傳 const_iterator，配合 auto 明確語義；begin 依物件常數性重載。

練習 9.11-9.12：vector 建構方式

vector<int> v1;                    // 空
vector<int> v2(v1);                // 拷貝建構
vector<int> v3 = {1,2,3,4,5};      // 列表初始化 (C++11)
vector<int> v4(v3.begin()+1, v3.end()-1); // 範圍建構 {2,3,4}
vector<int> v5(10);                // 10 個 0
vector<int> v6(10, 42);            // 10 個 42

範圍建構不要求容器型別相同，僅需元素型別可轉換；拷貝建構要求型別完全一致。

練習 9.13：`list<int>` 初始化 `vector<double>`

list<int> ilist = {1, 2, 3, 4};
vector<double> dvec(ilist.begin(), ilist.end()); // 隱式 int→double 轉換
vector<double> dvec2(ivec.begin(), ivec.end());  // 同理

練習 9.14：`char*` 到 `string` 的容器轉換

list<const char*> clist = {"Hello", "World", "C++"};
vector<string> svec(clist.begin(), clist.end()); // 隱式轉換建構 string

練習 9.21-9.22：`insert` 迭代器失效陷阱

// vector 插入導致迭代器失效
vector<int> iv = {1,1,1,1,1};
auto iter = iv.begin();
auto mid = iv.begin() + iv.size()/2;

// 錯誤：迴圈中未遞增 iter，且 insert 使 iter 失效
while (iter != mid) 
    if (*iter == 1) iv.insert(iter, 2);

// 正確：使用 insert 回傳值更新迭代器，手動控制索引
size_t org_size = iv.size();
for (size_t i = 0, idx = 0; idx <= org_size/2; ++idx) {
    if (iv[idx] == 1) {
        iv.insert(iv.begin() + idx, 2);
        ++idx; // 跳過新插入元素
    }
}

練習 9.25-9.26：`erase` 範圍刪除與單元素刪除

// 刪除偶數 (vector)
auto it = vec.begin();
while (it != vec.end()) {
    if (*it % 2 == 0) it = vec.erase(it); // erase 回傳下一個有效迭代器
    else ++it;
}

// 刪除奇數 (list)
auto it = lst.begin();
while (it != lst.end()) {
    if (*it % 2 != 0) it = lst.erase(it);
    else ++it;
}

練習 9.27：`forward_list` 刪除奇數

forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin();
auto curr = flst.begin();

while (curr != flst.end()) {
    if (*curr & 1) 
        curr = flst.erase_after(prev); // 單向鏈表需追蹤前驅
    else {
        prev = curr;
        ++curr;
    }
}

練習 9.31：`list`/`forward_list` 不支援迭代器算術

// 鏈表迭代器無 operator+，需用 advance 或迴圈
auto it = lst.begin();
advance(it, n);  // 
for (int i = 0; i < n && it != lst.end(); ++i, ++it) {}

練習 9.34-9.35：`capacity` vs `size`

size()：當前元素數量
capacity()：已分配記憶體可容納元素數
capacity() >= size() 恆成立
list/array 無 capacity：鏈表動態分配節點，陣列固定大小

練習 9.39-9.40：`reserve` 與 `resize` 互動

vector<string> svec;
svec.reserve(1024);           // 預分配 1024 個 string 空間
// 讀入 256 個單詞...
svec.resize(svec.size() + svec.size()/2); // 擴充 128 個空 string

// 容量變化：
// 256 個單詞 → capacity 仍 1024，resize 後 size=384
// 512 個單詞 → capacity 仍 1024，resize 後 size=768
// 1000 個單詞 → capacity 擴充至 2048，resize 後 size=1500
// 1048 個單詞 → capacity 2048，resize 後 size=1572

練習 9.43-9.44：字串替換演算法

// 迭代器版本
void replace_str(string& s, const string& oldVal, const string& newVal) {
    for (auto it = s.begin(); it <= s.end() - oldVal.size(); ) {
        if (equal(it, it + oldVal.size(), oldVal.begin())) {
            it = s.erase(it, it + oldVal.size());
            it = s.insert(it, newVal.begin(), newVal.end());
            advance(it, newVal.size());
        } else ++it;
    }
}

// 下標版本（更簡潔高效）
void replace_str(string& s, const string& oldVal, const string& newVal) {
    for (size_t pos = 0; (pos = s.find(oldVal, pos)) != string::npos; pos += newVal.size())
        s.replace(pos, oldVal.size(), newVal);
}

練習 9.47：`find_first_of` / `find_first_not_of`

string s = "ab2c3d7R4E6";
string digits = "0123456789";
string letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

cout << "數字位置: ";
for (size_t pos = 0; (pos = s.find_first_of(digits, pos)) != string::npos; ++pos)
    cout << pos << '(' << s[pos] << ") ";

cout << "\n字母位置: ";
for (size_t pos = 0; (pos = s.find_first_of(letters, pos)) != string::npos; ++pos)
    cout << pos << '(' << s[pos] << ") ";

練習 9.49：最長無伸展字母單詞


// 無上伸展 (bdfhkl) 和下伸展 (gpqy) 的字母：aceimnorsuvwxz
string longest;
string word;
while (cin >> word) {
    if (word.find_first_of("bdfghklpqty") == string::npos) { // 含伸展字母跳過
        if (word.size() > longest.size()) longest = word;
    }
}
cout << "最長單詞: " << longest << endl;