C++ STL list 容器迭代器失效導致段錯誤的正確刪除姿勢

問題代碼分析

list<int> Boy;
for (int i = 1; i <= 100; ++i) Boy.push_back(i);

list<int>::iterator it = Boy.begin();
int num = 1;
while (Boy.size() > 1) {
    if (num % 3 == 0) {
        Boy.remove(*it);  // ❌ 錯誤：remove 會使迭代器失效
    } else {
        ++it;
    }
    if (it == Boy.end()) it = Boy.begin();
    ++num;
}
cout << *it << endl;  // 段錯誤：it 已失效

核心問題：迭代器失效規則

錯誤原因詳解

1. Boy.remove(*it) 會刪除所有值等於 *it 的元素
2. 刪除後，it 指向的記憶體已被釋放，成為懸空迭代器
3. 後續 ++it、it == Boy.end()、*it 皆屬未定義行為 → 段錯誤
4. 邏輯錯誤：remove 刪除的是值而非位置，若有重複值會誤刪

正確解法：使用 erase 並接收返回值

list<int> Boy;
for (int i = 1; i <= 100; ++i) Boy.push_back(i);

auto it = Boy.begin();
int num = 1;
while (Boy.size() > 1) {
    if (num % 3 == 0) {
        // erase 返回下一個有效迭代器
        it = Boy.erase(it);
        // erase 後 it 已指向下一個，無需 ++it
    } else {
        ++it;
    }
    
    if (it == Boy.end()) {
        it = Boy.begin();
    }
    ++num;
}
cout << "最後剩下: " << *it << endl;  // 正確輸出

完整約瑟夫環問題實現

#include <iostream>
#include <list>
using namespace std;

int josephus(int n, int k) {
    list<int> people;
    for (int i = 1; i <= n; ++i) people.push_back(i);
    
    auto it = people.begin();
    int count = 1;
    
    while (people.size() > 1) {
        if (count % k == 0) {
            it = people.erase(it);  // 關鍵：接收返回值
            if (it == people.end()) it = people.begin();
        } else {
            ++it;
            if (it == people.end()) it = people.begin();
        }
        ++count;
    }
    return *people.begin();
}

int main() {
    cout << "100人每報3出列，最後是: " << josephus(100, 3) << endl;
    return 0;
}

進階：使用 C++20 std::erase_if (若支援)

// C++20 可用，但不適用於需保留迭代器位置的邏輯
// std::erase_if(Boy, [](int x){ return x % 3 == 0; }); 
// 此為批量刪除，不適用逐步報數邏輯

常見錯誤模式對比

除錯技巧

1. 編譯器警告：-Witerator-invalidated (GCC/Clang)
2. AddressSanitizer：-fsanitize=address 可檢測迭代器使用後釋放
3. MSVC 迭代器偵錯：Debug 模式下自動檢測失效迭代器存取

總結

C++ STL 容器刪除元素時，必須使用 erase 返回值更新迭代器。list 的優勢在於 erase 只會使被刪除元素的迭代器失效，其他迭代器保持有效，非常適合約瑟夫環等需頻繁刪除且保持遍歷位置的演算法。