STL 學習系列之三：list 容器完整操作實戰 (插入、刪除、排序、搜尋、分割)

list 特性回顧

• 雙向鏈結串列，記憶體不連續
• 支援雙向迭代器，不支援隨機存取
• 任意位置插入/刪除 O(1) (已有迭代器)，不使其他迭代器失效
• 適合頻繁中間增刪、大型物件避免搬移

完整範例程式 (VC6/VC7/現代編譯器通用)

#include 
#include 
#include 
#include 
#include 

using namespace std;

// 列印函數物件
struct PrintString {
    void operator()(const string& s) const { cout << s << '\n'; }
};

// 判斷是否為 "Bufeng" 開頭
struct IsBufeng {
    bool operator()(const string& s) const {
        return s.substr(0, 6) == "Bufeng";
    }
};

int main() {
    list aiStudents, target;
    list::iterator it;

    // 1. 插入操作
    aiStudents.push_back("BufengZhang");
    aiStudents.push_back("YangZhang");
    aiStudents.push_back("KunHuang");
    aiStudents.push_front("ChengLuo");
    aiStudents.push_front("YonghuoYang");
    aiStudents.push_front("XiaoyuanCui");
    aiStudents.insert(aiStudents.end(), "KefeiGong"); // 等同 push_back

    target.push_back("BufengZhang");
    target.push_back("YangZhang");

    // 2. 狀態檢查
    if (aiStudents.empty())
        cout << "空容器\n";
    else
        cout << "成員數: " << aiStudents.size() << '\n';

    // 3. 遍歷：手動迭代器
    cout << "--- 手動迭代 ---\n";
    for (it = aiStudents.begin(); it != aiStudents.end(); ++it)
        cout << *it << '\n';

    // 4. 遍歷：std::for_each
    cout << "--- for_each ---\n";
    for_each(aiStudents.begin(), aiStudents.end(), PrintString());

    // 5. 計數：count / count_if
    int cnt = count(aiStudents.begin(), aiStudents.end(), "BufengZhang");
    cout << "精確匹配 BufengZhang: " << cnt << '\n';

    cnt = count_if(aiStudents.begin(), aiStudents.end(), IsBufeng());
    cout << "前綴 Bufeng: " << cnt << '\n';

    // 6. 搜尋：find / find_if
    it = find(aiStudents.begin(), aiStudents.end(), "BufengZhang");
    cout << (it != aiStudents.end() ? "find: 找到" : "find: 未找到") << '\n';

    it = find_if(aiStudents.begin(), aiStudents.end(), IsBufeng());
    cout << (it != aiStudents.end() ? "find_if: 找到" : "find_if: 未找到") << '\n';

    // 7. 子序列搜尋：search
    it = search(aiStudents.begin(), aiStudents.end(),
                target.begin(), target.end());
    cout << (it != aiStudents.end() ? "search: 找到序列" : "search: 未找到序列") << '\n';

    // 8. 排序：list::sort (專用 merge sort)
    aiStudents.sort();
    cout << "--- 排序後 ---\n";
    for_each(aiStudents.begin(), aiStudents.end(), PrintString());

    // 9. 刪除：pop_front/back, erase, remove (成員)
    aiStudents.pop_front();
    aiStudents.pop_back();
    aiStudents.erase(aiStudents.begin());
    aiStudents.remove("XiaoyuanCui"); // 刪除所有匹配
    cout << "--- 成員刪除後 ---\n";
    for_each(aiStudents.begin(), aiStudents.end(), PrintString());

    // 10. 通用演算法 remove (不改變容器大小)
    it = remove(aiStudents.begin(), aiStudents.end(), "YangZhang");
    cout << "--- remove 後 (邏輯區間) ---\n";
    for_each(aiStudents.begin(), it, PrintString());
    // 實際縮減容器需配合 erase
    aiStudents.erase(it, aiStudents.end());

    return 0;
}

關鍵操作對照表

進階技巧：splice 與 stable_partition 實作命令列參數解析

// 將 flags (-xxx) 移至前端，保持檔名相對順序
list cmd = {"-w", "linux", "-o", "is", "great"};
list flags, files;

auto isFlag = [](const string& s){ return s[0]=='-'; };
auto it = stable_partition(cmd.begin(), cmd.end(), isFlag);
// cmd 變為: -w, -o, linux, is, great

flags.splice(flags.end(), cmd, cmd.begin(), it); // 移動 flags
files.splice(files.end(), cmd);                 // 剩餘為 files

總結

std::list 以節點轉移 (splice)、穩定排序 (sort)、不失效迭代器等特性，在頻繁重組序列、大型物件管理、需保持插入順序的多級排序等場景具備獨特優勢。掌握成員函數與通用演算法的配合 (特別是 remove-erase 慣用語、splice 零拷貝移動)，能發揮 list 最大效能。