list_forward_list.cpp

// list_forward_list.cpp
// list 與 forward_list 的完整用法示範
// 編譯：g++ -std=c++17 -Wall -o list_forward_list list_forward_list.cpp

#include <iostream>
#include <list>
#include <forward_list>
#include <string>
#include <algorithm>

// 輔助函式：印出容器內容
template <typename Container>
void print_container(const std::string& label, const Container& c) {
    std::cout << label << " [";
    bool first = true;
    for (const auto& item : c) {
        if (!first) std::cout << ", ";
        std::cout << item;
        first = false;
    }
    std::cout << "]" << std::endl;
}

int main() {
    std::cout << "========================================" << std::endl;
    std::cout << "  list 與 forward_list 完整示範" << std::endl;
    std::cout << "========================================\n" << std::endl;

    // ========================================================
    // Part A: std::list（雙向鏈結串列）
    // ========================================================
    std::cout << "==================== std::list ====================" << std::endl;

    // --- 1. 建構與基本插入 ---
    std::cout << "\n--- 1. 建構與基本插入 ---" << std::endl;

    std::list<int> lst1 = {3, 1, 4, 1, 5, 9, 2, 6};
    print_container("初始", lst1);

    lst1.push_front(0);    // 頭端加入
    lst1.push_back(10);    // 尾端加入
    print_container("push_front(0), push_back(10)", lst1);

    // --- 2. insert — 在指定位置插入 ---
    std::cout << "\n--- 2. insert ---" << std::endl;

    auto it = lst1.begin();
    std::advance(it, 3);  // 移動到第 4 個位置
    lst1.insert(it, 99);
    print_container("在第4個位置插入99", lst1);

    lst1.insert(it, 3, 77);  // 插入 3 個 77
    print_container("插入3個77", lst1);

    // --- 3. erase — 刪除元素 ---
    std::cout << "\n--- 3. erase ---" << std::endl;

    auto it2 = lst1.begin();
    std::advance(it2, 2);
    lst1.erase(it2);
    print_container("刪除第3個元素", lst1);

    // 刪除範圍
    auto start = lst1.begin();
    auto end_it = lst1.begin();
    std::advance(end_it, 3);
    lst1.erase(start, end_it);
    print_container("刪除前3個元素", lst1);

    // --- 4. remove / remove_if — 按值或條件刪除 ---
    std::cout << "\n--- 4. remove / remove_if ---" << std::endl;

    std::list<int> lst2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    print_container("原始", lst2);

    lst2.remove(5);  // 移除值為 5 的元素
    print_container("remove(5)", lst2);

    lst2.remove_if([](int x) { return x % 2 == 0; });  // 移除偶數
    print_container("remove_if(偶數)", lst2);

    // --- 5. sort — 排序（list 有自己的 sort，不能用 std::sort）---
    std::cout << "\n--- 5. sort ---" << std::endl;

    std::list<int> lst3 = {5, 2, 8, 1, 9, 3, 7};
    print_container("排序前", lst3);

    lst3.sort();
    print_container("sort()(升序)", lst3);

    lst3.sort(std::greater<int>());
    print_container("sort(降序)", lst3);

    // --- 6. unique — 移除連續重複元素 ---
    std::cout << "\n--- 6. unique ---" << std::endl;

    std::list<int> lst4 = {1, 1, 2, 2, 2, 3, 3, 1, 1};
    print_container("unique 前", lst4);

    lst4.unique();  // 只移除「連續」重複
    print_container("unique 後", lst4);

    // 若要完全去重，需先排序
    std::list<int> lst5 = {3, 1, 2, 1, 3, 2, 1};
    lst5.sort();
    lst5.unique();
    print_container("sort + unique", lst5);

    // --- 7. merge — 合併兩個已排序的 list ---
    std::cout << "\n--- 7. merge ---" << std::endl;

    std::list<int> a = {1, 3, 5, 7};
    std::list<int> b = {2, 4, 6, 8};
    print_container("list a", a);
    print_container("list b", b);

    a.merge(b);  // b 的元素會移動到 a，b 變空
    print_container("merge 後 a", a);
    print_container("merge 後 b", b);

    // --- 8. splice — 將另一個 list 的元素搬移過來 ---
    std::cout << "\n--- 8. splice ---" << std::endl;

    std::list<int> src = {100, 200, 300};
    std::list<int> dst = {1, 2, 3};

    print_container("src", src);
    print_container("dst", dst);

    auto pos = dst.begin();
    std::advance(pos, 1);
    dst.splice(pos, src);  // 把 src 全部移到 dst 的第 2 個位置前

    print_container("splice 後 dst", dst);
    print_container("splice 後 src", src);

    // --- 9. reverse — 反轉 ---
    std::cout << "\n--- 9. reverse ---" << std::endl;

    std::list<int> lst6 = {1, 2, 3, 4, 5};
    print_container("反轉前", lst6);

    lst6.reverse();
    print_container("反轉後", lst6);

    // ========================================================
    // Part B: std::forward_list（單向鏈結串列）
    // ========================================================
    std::cout << "\n==================== std::forward_list ====================" << std::endl;

    // --- 1. 基本操作 ---
    std::cout << "\n--- 1. 基本操作 ---" << std::endl;

    std::forward_list<int> fl = {2, 4, 6};
    print_container("初始", fl);

    fl.push_front(0);  // 只有 push_front，沒有 push_back
    print_container("push_front(0)", fl);

    // --- 2. insert_after / erase_after ---
    std::cout << "\n--- 2. insert_after / erase_after ---" << std::endl;

    // forward_list 使用 insert_after 而非 insert
    auto fit = fl.begin();
    fl.insert_after(fit, 1);  // 在第一個元素後面插入 1
    print_container("insert_after(begin, 1)", fl);

    // before_begin() 可在最前面插入
    fl.insert_after(fl.before_begin(), -1);
    print_container("insert_after(before_begin, -1)", fl);

    // erase_after 刪除指定位置的下一個元素
    fl.erase_after(fl.begin());
    print_container("erase_after(begin)", fl);

    // --- 3. remove / remove_if ---
    std::cout << "\n--- 3. remove / remove_if ---" << std::endl;

    std::forward_list<int> fl2 = {1, 2, 3, 4, 5, 6, 7, 8};
    print_container("原始", fl2);

    fl2.remove(4);
    print_container("remove(4)", fl2);

    fl2.remove_if([](int x) { return x > 5; });
    print_container("remove_if(>5)", fl2);

    // --- 4. sort / unique / reverse / merge ---
    std::cout << "\n--- 4. sort / unique / reverse / merge ---" << std::endl;

    std::forward_list<int> fl3 = {5, 3, 1, 4, 1, 5, 9};
    fl3.sort();
    print_container("sort", fl3);

    fl3.unique();
    print_container("unique", fl3);

    fl3.reverse();
    print_container("reverse", fl3);

    // ========================================================
    // 比較總結
    // ========================================================
    std::cout << "\n==================== 比較總結 ====================" << std::endl;

    std::cout << "┌───────────────┬──────────┬──────────┬──────────────┐" << std::endl;
    std::cout << "│     特性      │  vector  │   list   │ forward_list │" << std::endl;
    std::cout << "├───────────────┼──────────┼──────────┼──────────────┤" << std::endl;
    std::cout << "│ 隨機存取      │   O(1)   │   O(n)   │     O(n)     │" << std::endl;
    std::cout << "│ 頭端增刪      │   O(n)   │   O(1)   │     O(1)     │" << std::endl;
    std::cout << "│ 尾端增刪      │ 攤銷O(1) │   O(1)   │     O(n)     │" << std::endl;
    std::cout << "│ 中間增刪      │   O(n)   │   O(1)   │     O(1)     │" << std::endl;
    std::cout << "│ 記憶體開銷    │   低     │   高     │     中       │" << std::endl;
    std::cout << "│ 快取友好      │   是     │   否     │     否       │" << std::endl;
    std::cout << "│ 有 size()     │   是     │   是     │     否       │" << std::endl;
    std::cout << "└───────────────┴──────────┴──────────┴──────────────┘" << std::endl;

    std::cout << "\n========================================" << std::endl;
    std::cout << "  list 與 forward_list 示範結束" << std::endl;
    std::cout << "========================================" << std::endl;

    return 0;
}