algorithms_advanced.cpp

// Ch14 — 進階 STL 演算法示範
// 編譯：g++ -std=c++17 -Wall -o algorithms_advanced algorithms_advanced.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>     // iota
#include <string>
#include <iterator>    // back_inserter, ostream_iterator
#include <cctype>      // toupper

// 輔助函式：印出分隔線
void section(const std::string& title) {
    std::cout << "\n===== " << title << " =====\n";
}

// 輔助函式：印出 vector 內容
template<typename T>
void printVec(const std::string& label, const std::vector<T>& v) {
    std::cout << label;
    for (const auto& x : v) std::cout << x << " ";
    std::cout << "\n";
}

int main() {
    // ========================================================
    // 1. transform — 轉換
    // ========================================================
    section("1. transform 轉換");

    // 一元 transform：每個元素平方
    std::vector<int> nums = {1, 2, 3, 4, 5};
    std::vector<int> squares(nums.size());
    std::transform(nums.begin(), nums.end(), squares.begin(),
        [](int x) { return x * x; });
    printVec("原始：", nums);
    printVec("平方：", squares);

    // 二元 transform：兩個 vector 對應元素相加
    std::vector<int> a = {10, 20, 30, 40};
    std::vector<int> b = {1, 2, 3, 4};
    std::vector<int> sum(a.size());
    std::transform(a.begin(), a.end(), b.begin(), sum.begin(),
        [](int x, int y) { return x + y; });
    printVec("a：", a);
    printVec("b：", b);
    printVec("a + b：", sum);

    // 字串轉大寫
    std::string text = "hello, c++ world!";
    std::string upper;
    std::transform(text.begin(), text.end(), std::back_inserter(upper),
        [](char c) { return std::toupper(static_cast<unsigned char>(c)); });
    std::cout << "原始字串：" << text << "\n";
    std::cout << "轉大寫：" << upper << "\n";

    // ========================================================
    // 2. copy / copy_if — 複製
    // ========================================================
    section("2. copy / copy_if 複製");

    std::vector<int> src = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // copy_if：只複製偶數
    std::vector<int> evens;
    std::copy_if(src.begin(), src.end(), std::back_inserter(evens),
        [](int x) { return x % 2 == 0; });
    printVec("原始：", src);
    printVec("偶數：", evens);

    // copy_if：複製大於 5 的元素
    std::vector<int> gt5;
    std::copy_if(src.begin(), src.end(), std::back_inserter(gt5),
        [](int x) { return x > 5; });
    printVec("大於 5：", gt5);

    // 使用 ostream_iterator 直接輸出
    std::cout << "使用 ostream_iterator 輸出：";
    std::copy(src.begin(), src.end(),
        std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    // ========================================================
    // 3. remove_if + erase — erase-remove 慣用法
    // ========================================================
    section("3. erase-remove 慣用法");

    std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    printVec("原始：", data);

    // 移除所有 3 的倍數
    // remove_if 會將不需移除的元素移到前面，回傳新的邏輯結尾
    auto newEnd = std::remove_if(data.begin(), data.end(),
        [](int x) { return x % 3 == 0; });

    std::cout << "remove_if 後（erase 前），vector 仍包含 "
              << data.size() << " 個元素：";
    for (const auto& x : data) std::cout << x << " ";
    std::cout << "\n";

    // erase 才真正縮小 vector
    data.erase(newEnd, data.end());
    printVec("erase 後：", data);

    // 一行完成 erase-remove
    std::vector<int> data2 = {10, 25, 30, 45, 50, 65, 70};
    printVec("原始：", data2);
    data2.erase(
        std::remove_if(data2.begin(), data2.end(),
            [](int x) { return x < 40; }),
        data2.end());
    printVec("移除 < 40 後：", data2);

    // 移除特定值
    std::vector<int> data3 = {1, 2, 3, 2, 4, 2, 5};
    printVec("原始：", data3);
    data3.erase(std::remove(data3.begin(), data3.end(), 2), data3.end());
    printVec("移除所有 2：", data3);

    // ========================================================
    // 4. unique — 移除相鄰重複
    // ========================================================
    section("4. unique 去重");

    // 必須先排序才能正確去重
    std::vector<int> dup = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    printVec("原始：", dup);

    std::sort(dup.begin(), dup.end());
    printVec("排序後：", dup);

    dup.erase(std::unique(dup.begin(), dup.end()), dup.end());
    printVec("去重後：", dup);

    // 自訂相等條件：相差不超過 1 視為重複
    std::vector<int> close = {1, 2, 2, 3, 5, 5, 6, 8, 8, 9};
    printVec("原始：", close);
    close.erase(
        std::unique(close.begin(), close.end(),
            [](int a, int b) { return std::abs(a - b) <= 1; }),
        close.end());
    printVec("相差 ≤ 1 去重後：", close);

    // ========================================================
    // 5. reverse — 反轉
    // ========================================================
    section("5. reverse 反轉");

    std::vector<int> rev = {1, 2, 3, 4, 5};
    printVec("原始：", rev);
    std::reverse(rev.begin(), rev.end());
    printVec("反轉：", rev);

    // 部分反轉
    std::vector<int> partial = {1, 2, 3, 4, 5, 6, 7};
    printVec("原始：", partial);
    std::reverse(partial.begin() + 2, partial.begin() + 5);
    printVec("反轉 [2,5) 位置：", partial);

    // ========================================================
    // 6. rotate — 旋轉
    // ========================================================
    section("6. rotate 旋轉");

    std::vector<int> rot = {1, 2, 3, 4, 5, 6, 7};
    printVec("原始：", rot);

    // 將 begin+3 變成新的第一個元素
    std::rotate(rot.begin(), rot.begin() + 3, rot.end());
    printVec("左旋 3 位：", rot);

    // 右旋 2 位 = 左旋 (size - 2) 位
    std::rotate(rot.begin(), rot.end() - 2, rot.end());
    printVec("右旋 2 位：", rot);

    // ========================================================
    // 7. partition — 分區
    // ========================================================
    section("7. partition 分區");

    std::vector<int> part = {8, 3, 5, 1, 9, 2, 7, 4, 6};
    printVec("原始：", part);

    // 將偶數移到前面，奇數移到後面
    auto pivot = std::partition(part.begin(), part.end(),
        [](int x) { return x % 2 == 0; });
    printVec("partition 後（偶數在前）：", part);
    std::cout << "分界位置索引：" << (pivot - part.begin()) << "\n";

    // stable_partition 保持相對順序
    std::vector<int> part2 = {8, 3, 5, 1, 9, 2, 7, 4, 6};
    std::stable_partition(part2.begin(), part2.end(),
        [](int x) { return x % 2 == 0; });
    printVec("stable_partition 後：", part2);

    // ========================================================
    // 8. merge — 合併已排序序列
    // ========================================================
    section("8. merge 合併");

    std::vector<int> s1 = {1, 3, 5, 7, 9};
    std::vector<int> s2 = {2, 4, 6, 8, 10};
    std::vector<int> merged;
    printVec("序列 1：", s1);
    printVec("序列 2：", s2);

    std::merge(s1.begin(), s1.end(), s2.begin(), s2.end(),
        std::back_inserter(merged));
    printVec("合併後：", merged);

    // ========================================================
    // 9. set_union / set_intersection — 集合運算
    // ========================================================
    section("9. 集合運算（需已排序）");

    std::vector<int> setA = {1, 2, 3, 4, 5};
    std::vector<int> setB = {3, 4, 5, 6, 7};
    printVec("集合 A：", setA);
    printVec("集合 B：", setB);

    // 聯集
    std::vector<int> unionResult;
    std::set_union(setA.begin(), setA.end(), setB.begin(), setB.end(),
        std::back_inserter(unionResult));
    printVec("A ∪ B：", unionResult);

    // 交集
    std::vector<int> interResult;
    std::set_intersection(setA.begin(), setA.end(), setB.begin(), setB.end(),
        std::back_inserter(interResult));
    printVec("A ∩ B：", interResult);

    // 差集
    std::vector<int> diffResult;
    std::set_difference(setA.begin(), setA.end(), setB.begin(), setB.end(),
        std::back_inserter(diffResult));
    printVec("A - B：", diffResult);

    // 對稱差集
    std::vector<int> symDiff;
    std::set_symmetric_difference(setA.begin(), setA.end(),
        setB.begin(), setB.end(), std::back_inserter(symDiff));
    printVec("A △ B：", symDiff);

    // ========================================================
    // 10. next_permutation — 排列
    // ========================================================
    section("10. next_permutation 全排列");

    std::vector<int> perm = {1, 2, 3};
    printVec("初始排列：", perm);

    std::cout << "所有排列：\n";
    // 先排序確保從最小排列開始
    std::sort(perm.begin(), perm.end());
    int count = 0;
    do {
        std::cout << "  ";
        for (int x : perm) std::cout << x << " ";
        std::cout << "\n";
        ++count;
    } while (std::next_permutation(perm.begin(), perm.end()));
    std::cout << "共 " << count << " 種排列\n";

    // ========================================================
    // 11. 綜合範例：文字處理管線
    // ========================================================
    section("11. 綜合範例：文字處理管線");

    std::vector<std::string> words = {
        "Hello", "world", "hello", "C++", "World",
        "programming", "HELLO", "c++", "fun"
    };

    std::cout << "原始單字：";
    for (const auto& w : words) std::cout << w << " ";
    std::cout << "\n";

    // 步驟 1：全部轉小寫
    std::vector<std::string> lower_words(words.size());
    std::transform(words.begin(), words.end(), lower_words.begin(),
        [](std::string s) {
            std::transform(s.begin(), s.end(), s.begin(),
                [](unsigned char c) { return std::tolower(c); });
            return s;
        });

    // 步驟 2：排序
    std::sort(lower_words.begin(), lower_words.end());

    // 步驟 3：去重
    lower_words.erase(
        std::unique(lower_words.begin(), lower_words.end()),
        lower_words.end());

    // 步驟 4：移除長度 < 4 的單字
    lower_words.erase(
        std::remove_if(lower_words.begin(), lower_words.end(),
            [](const std::string& s) { return s.size() < 4; }),
        lower_words.end());

    std::cout << "處理後（小寫、去重、排序、篩選長度≥4）：";
    for (const auto& w : lower_words) std::cout << w << " ";
    std::cout << "\n";

    return 0;
}