algorithms_basic.cpp

// Ch14 — 基本 STL 演算法示範
// 編譯：g++ -std=c++17 -Wall -o algorithms_basic algorithms_basic.cpp

#include <iostream>
#include <vector>
#include <algorithm>  // sort, find, find_if, count, count_if, for_each, etc.
#include <numeric>    // accumulate
#include <string>
#include <iomanip>    // setw

// 輔助函式：印出分隔線
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. sort — 排序
    // ========================================================
    section("1. sort 排序");

    std::vector<int> scores = {78, 92, 65, 88, 95, 72, 85};
    printVec("排序前：", scores);

    // 預設升序排列
    std::sort(scores.begin(), scores.end());
    printVec("升序排列：", scores);

    // 使用 std::greater 進行降序排列
    std::sort(scores.begin(), scores.end(), std::greater<int>());
    printVec("降序排列：", scores);

    // 使用 lambda 自訂排序（按個位數排序）
    std::sort(scores.begin(), scores.end(), [](int a, int b) {
        return (a % 10) < (b % 10);
    });
    printVec("按個位數排序：", scores);

    // ========================================================
    // 2. stable_sort — 穩定排序
    // ========================================================
    section("2. stable_sort 穩定排序");

    // 用結構來示範穩定排序的意義
    struct Student {
        std::string name;
        int score;
    };

    std::vector<Student> students = {
        {"Alice", 90}, {"Bob", 85}, {"Charlie", 90},
        {"Diana", 85}, {"Eve", 92}
    };

    // stable_sort 保證分數相同時，保持原始順序
    std::stable_sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            return a.score > b.score;  // 依分數降序
        });

    std::cout << "穩定排序結果（分數相同者保持原始順序）：\n";
    for (const auto& s : students) {
        std::cout << "  " << std::setw(8) << s.name << "：" << s.score << " 分\n";
    }

    // ========================================================
    // 3. find / find_if — 搜尋
    // ========================================================
    section("3. find / find_if 搜尋");

    std::vector<int> data = {15, 42, 8, 23, 67, 31, 4, 56};
    printVec("資料：", data);

    // find：找指定值
    auto it = std::find(data.begin(), data.end(), 23);
    if (it != data.end()) {
        std::cout << "找到 23，位置索引：" << (it - data.begin()) << "\n";
    }

    // 找不到的情況
    auto it2 = std::find(data.begin(), data.end(), 99);
    if (it2 == data.end()) {
        std::cout << "找不到 99\n";
    }

    // find_if：找第一個滿足條件的元素
    auto it3 = std::find_if(data.begin(), data.end(),
        [](int x) { return x > 50; });
    if (it3 != data.end()) {
        std::cout << "第一個 > 50 的元素：" << *it3 << "\n";
    }

    // find_if_not：找第一個不滿足條件的元素
    auto it4 = std::find_if_not(data.begin(), data.end(),
        [](int x) { return x < 30; });
    if (it4 != data.end()) {
        std::cout << "第一個 >= 30 的元素：" << *it4 << "\n";
    }

    // ========================================================
    // 4. count / count_if — 計數
    // ========================================================
    section("4. count / count_if 計數");

    std::vector<int> nums = {1, 3, 5, 3, 7, 3, 9, 2, 4, 6, 3};
    printVec("資料：", nums);

    // count：計算特定值出現的次數
    int count3 = std::count(nums.begin(), nums.end(), 3);
    std::cout << "數字 3 出現 " << count3 << " 次\n";

    // count_if：計算滿足條件的元素個數
    int evenCount = std::count_if(nums.begin(), nums.end(),
        [](int x) { return x % 2 == 0; });
    std::cout << "偶數有 " << evenCount << " 個\n";

    int oddCount = std::count_if(nums.begin(), nums.end(),
        [](int x) { return x % 2 != 0; });
    std::cout << "奇數有 " << oddCount << " 個\n";

    // ========================================================
    // 5. for_each — 對每個元素執行操作
    // ========================================================
    section("5. for_each 遍歷操作");

    std::vector<double> prices = {29.99, 15.50, 42.00, 8.75, 33.25};

    // 印出所有價格（加上貨幣符號）
    std::cout << "商品價格：";
    std::for_each(prices.begin(), prices.end(), [](double p) {
        std::cout << "$" << std::fixed << std::setprecision(2) << p << " ";
    });
    std::cout << "\n";

    // 對每個價格打八折
    std::for_each(prices.begin(), prices.end(), [](double& p) {
        p *= 0.8;
    });
    std::cout << "八折後：  ";
    std::for_each(prices.begin(), prices.end(), [](double p) {
        std::cout << "$" << std::fixed << std::setprecision(2) << p << " ";
    });
    std::cout << "\n";

    // ========================================================
    // 6. accumulate — 累加 / 累積運算
    // ========================================================
    section("6. accumulate 累加");

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

    // 求總和（初始值 = 0）
    int sum = std::accumulate(values.begin(), values.end(), 0);
    std::cout << "總和：" << sum << "\n";

    // 求乘積（提供自訂二元運算）
    long long product = std::accumulate(values.begin(), values.end(), 1LL,
        [](long long acc, int val) { return acc * val; });
    std::cout << "乘積：" << product << "\n";

    // 字串連接
    std::vector<std::string> words = {"C++", "是", "一門", "強大的", "語言"};
    std::string sentence = std::accumulate(words.begin(), words.end(), std::string(""),
        [](const std::string& acc, const std::string& word) {
            return acc.empty() ? word : acc + " " + word;
        });
    std::cout << "字串連接：" << sentence << "\n";

    // 求平均值
    double avg = static_cast<double>(
        std::accumulate(values.begin(), values.end(), 0)) / values.size();
    std::cout << "平均值：" << avg << "\n";

    // ========================================================
    // 7. min_element / max_element — 最小值 / 最大值
    // ========================================================
    section("7. min_element / max_element");

    std::vector<int> temps = {22, 18, 35, 28, 15, 31, 20};
    printVec("一週氣溫：", temps);

    auto minIt = std::min_element(temps.begin(), temps.end());
    auto maxIt = std::max_element(temps.begin(), temps.end());

    std::cout << "最低溫：" << *minIt
              << "（第 " << (minIt - temps.begin() + 1) << " 天）\n";
    std::cout << "最高溫：" << *maxIt
              << "（第 " << (maxIt - temps.begin() + 1) << " 天）\n";

    // 也可以使用 minmax_element 同時找最小和最大
    auto [minP, maxP] = std::minmax_element(temps.begin(), temps.end());
    std::cout << "minmax_element → 最低：" << *minP << "，最高：" << *maxP << "\n";

    // 自訂比較：找最接近 25 度的一天
    auto closest = std::min_element(temps.begin(), temps.end(),
        [](int a, int b) {
            return std::abs(a - 25) < std::abs(b - 25);
        });
    std::cout << "最接近 25°C 的氣溫：" << *closest << "\n";

    // ========================================================
    // 8. binary_search / lower_bound / upper_bound
    // ========================================================
    section("8. binary_search（需要已排序的資料）");

    std::vector<int> sorted = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    printVec("已排序資料：", sorted);

    // binary_search：回傳是否存在
    bool found23 = std::binary_search(sorted.begin(), sorted.end(), 23);
    bool found25 = std::binary_search(sorted.begin(), sorted.end(), 25);
    std::cout << "搜尋 23：" << (found23 ? "找到" : "未找到") << "\n";
    std::cout << "搜尋 25：" << (found25 ? "找到" : "未找到") << "\n";

    // lower_bound：第一個 >= 目標值的位置
    auto lb = std::lower_bound(sorted.begin(), sorted.end(), 16);
    std::cout << "lower_bound(16)：值 = " << *lb
              << "，索引 = " << (lb - sorted.begin()) << "\n";

    // 搜尋不存在的值
    auto lb2 = std::lower_bound(sorted.begin(), sorted.end(), 20);
    std::cout << "lower_bound(20)：值 = " << *lb2
              << "（第一個 >= 20 的元素），索引 = " << (lb2 - sorted.begin()) << "\n";

    // upper_bound：第一個 > 目標值的位置
    auto ub = std::upper_bound(sorted.begin(), sorted.end(), 16);
    std::cout << "upper_bound(16)：值 = " << *ub
              << "（第一個 > 16 的元素），索引 = " << (ub - sorted.begin()) << "\n";

    // 使用 lower_bound + upper_bound 找出等值範圍
    std::vector<int> repeated = {1, 2, 2, 2, 3, 4, 4, 5};
    printVec("含重複資料：", repeated);
    auto range_begin = std::lower_bound(repeated.begin(), repeated.end(), 2);
    auto range_end = std::upper_bound(repeated.begin(), repeated.end(), 2);
    std::cout << "數字 2 的範圍：索引 ["
              << (range_begin - repeated.begin()) << ", "
              << (range_end - repeated.begin()) << ")，共 "
              << std::distance(range_begin, range_end) << " 個\n";

    // ========================================================
    // 9. 綜合範例：學生成績統計
    // ========================================================
    section("9. 綜合範例：學生成績統計");

    std::vector<int> grades = {78, 92, 65, 88, 55, 73, 95, 42, 81, 70};
    printVec("全班成績：", grades);

    int total = std::accumulate(grades.begin(), grades.end(), 0);
    double average = static_cast<double>(total) / grades.size();
    auto [worstIt, bestIt] = std::minmax_element(grades.begin(), grades.end());
    int passCount = std::count_if(grades.begin(), grades.end(),
        [](int g) { return g >= 60; });
    int failCount = std::count_if(grades.begin(), grades.end(),
        [](int g) { return g < 60; });

    std::cout << "全班人數：" << grades.size() << "\n";
    std::cout << "總分：" << total << "\n";
    std::cout << "平均：" << std::fixed << std::setprecision(1) << average << "\n";
    std::cout << "最高分：" << *bestIt << "\n";
    std::cout << "最低分：" << *worstIt << "\n";
    std::cout << "及格人數：" << passCount << "\n";
    std::cout << "不及格人數：" << failCount << "\n";

    // 排序後找中位數
    std::sort(grades.begin(), grades.end());
    double median;
    size_t n = grades.size();
    if (n % 2 == 0) {
        median = (grades[n/2 - 1] + grades[n/2]) / 2.0;
    } else {
        median = grades[n/2];
    }
    std::cout << "中位數：" << median << "\n";

    return 0;
}