vector_deque.cpp

// vector_deque.cpp
// vector 與 deque 的完整用法示範
// 編譯：g++ -std=c++17 -Wall -o vector_deque vector_deque.cpp

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <string>

// 輔助函式：印出容器內容
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 << "  vector 與 deque 完整示範" << std::endl;
    std::cout << "========================================\n" << std::endl;

    // ========================================================
    // Part A: std::vector
    // ========================================================
    std::cout << "==================== vector ====================" << std::endl;

    // --- 1. 各種建構方式 ---
    std::cout << "\n--- 1. 建構方式 ---" << std::endl;

    std::vector<int> v1;                     // 空向量
    std::vector<int> v2(5);                  // 5 個元素，預設值 0
    std::vector<int> v3(5, 42);              // 5 個元素，值為 42
    std::vector<int> v4 = {1, 2, 3, 4, 5};  // 初始化串列
    std::vector<int> v5(v4.begin(), v4.begin() + 3);  // 從迭代器範圍

    print_container("v1 (空)",      v1);
    print_container("v2 (5個0)",    v2);
    print_container("v3 (5個42)",   v3);
    print_container("v4 (1~5)",     v4);
    print_container("v5 (前3個)",   v5);

    // --- 2. 新增元素 ---
    std::cout << "\n--- 2. 新增元素 ---" << std::endl;

    std::vector<std::string> names;
    names.push_back("Alice");       // 複製加入
    names.push_back("Bob");
    names.emplace_back("Charlie");  // 原地建構，避免不必要的複製
    print_container("push_back/emplace_back", names);

    names.insert(names.begin() + 1, "David");  // 在索引 1 插入
    print_container("insert 'David' at [1]", names);

    names.insert(names.end(), {"Eve", "Frank"});  // 尾端插入多個
    print_container("insert 多個到尾端", names);

    // --- 3. size、capacity、reserve ---
    std::cout << "\n--- 3. size / capacity / reserve ---" << std::endl;

    std::vector<int> sv;
    std::cout << "初始 — size: " << sv.size()
              << ", capacity: " << sv.capacity() << std::endl;

    for (int i = 0; i < 10; ++i) {
        sv.push_back(i);
        std::cout << "  push_back(" << i << ") → size: " << sv.size()
                  << ", capacity: " << sv.capacity() << std::endl;
    }

    sv.reserve(100);  // 預先配置空間
    std::cout << "reserve(100) → size: " << sv.size()
              << ", capacity: " << sv.capacity() << std::endl;

    sv.shrink_to_fit();  // 釋放多餘空間
    std::cout << "shrink_to_fit() → size: " << sv.size()
              << ", capacity: " << sv.capacity() << std::endl;

    // --- 4. 存取元素 ---
    std::cout << "\n--- 4. 存取元素 ---" << std::endl;

    std::vector<int> data = {10, 20, 30, 40, 50};
    std::cout << "data[0]     = " << data[0] << std::endl;
    std::cout << "data.at(2)  = " << data.at(2) << std::endl;
    std::cout << "data.front()= " << data.front() << std::endl;
    std::cout << "data.back() = " << data.back() << std::endl;

    // at() 有邊界檢查
    try {
        data.at(100);
    } catch (const std::out_of_range& e) {
        std::cout << "at(100) 例外: " << e.what() << std::endl;
    }

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

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

    del.pop_back();
    print_container("pop_back()", del);

    del.erase(del.begin() + 2);  // 刪除索引 2
    print_container("erase([2])", del);

    del.erase(del.begin(), del.begin() + 2);  // 刪除前兩個
    print_container("erase 前兩個", del);

    // 使用 erase-remove 慣用法刪除所有偶數
    std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    print_container("刪除偶數前", nums);
    nums.erase(
        std::remove_if(nums.begin(), nums.end(),
                       [](int x) { return x % 2 == 0; }),
        nums.end()
    );
    print_container("刪除偶數後", nums);

    // --- 6. 遍歷方式 ---
    std::cout << "\n--- 6. 遍歷方式 ---" << std::endl;

    std::vector<int> iter_demo = {10, 20, 30, 40, 50};

    // 方式 1：範圍 for
    std::cout << "範圍 for:    ";
    for (int val : iter_demo) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // 方式 2：索引
    std::cout << "索引:        ";
    for (std::size_t i = 0; i < iter_demo.size(); ++i) {
        std::cout << iter_demo[i] << " ";
    }
    std::cout << std::endl;

    // 方式 3：迭代器
    std::cout << "迭代器:      ";
    for (auto it = iter_demo.begin(); it != iter_demo.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 方式 4：反向迭代器
    std::cout << "反向迭代器:  ";
    for (auto rit = iter_demo.rbegin(); rit != iter_demo.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;

    // --- 7. clear ---
    std::cout << "\n--- 7. clear ---" << std::endl;

    std::vector<int> clr = {1, 2, 3};
    std::cout << "clear 前 — size: " << clr.size()
              << ", capacity: " << clr.capacity() << std::endl;
    clr.clear();
    std::cout << "clear 後 — size: " << clr.size()
              << ", capacity: " << clr.capacity()
              << " (容量不變)" << std::endl;

    // --- 8. 二維 vector ---
    std::cout << "\n--- 8. 二維 vector ---" << std::endl;

    // 3x4 矩陣，初始值為 0
    std::vector<std::vector<int>> matrix(3, std::vector<int>(4, 0));

    // 填入值
    int counter = 1;
    for (auto& row : matrix) {
        for (auto& cell : row) {
            cell = counter++;
        }
    }

    // 印出矩陣
    std::cout << "3x4 矩陣:" << std::endl;
    for (const auto& row : matrix) {
        std::cout << "  ";
        for (int cell : row) {
            std::cout << cell << "\t";
        }
        std::cout << std::endl;
    }

    // ========================================================
    // Part B: std::deque
    // ========================================================
    std::cout << "\n==================== deque ====================" << std::endl;

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

    std::deque<int> dq = {3, 4, 5};
    print_container("初始", dq);

    dq.push_front(2);   // 頭端加入
    dq.push_front(1);
    print_container("push_front(2, 1)", dq);

    dq.push_back(6);    // 尾端加入
    dq.push_back(7);
    print_container("push_back(6, 7)", dq);

    dq.pop_front();     // 移除頭端
    print_container("pop_front()", dq);

    dq.pop_back();      // 移除尾端
    print_container("pop_back()", dq);

    // --- 2. 隨機存取 ---
    std::cout << "\n--- 2. deque 隨機存取 ---" << std::endl;

    std::cout << "dq[0]     = " << dq[0] << std::endl;
    std::cout << "dq.at(2)  = " << dq.at(2) << std::endl;
    std::cout << "dq.front()= " << dq.front() << std::endl;
    std::cout << "dq.back() = " << dq.back() << std::endl;

    // --- 3. vector vs deque 比較 ---
    std::cout << "\n--- 3. vector vs deque 比較 ---" << std::endl;

    std::cout << "┌──────────────┬──────────┬──────────┐" << std::endl;
    std::cout << "│     操作     │  vector  │  deque   │" << std::endl;
    std::cout << "├──────────────┼──────────┼──────────┤" << std::endl;
    std::cout << "│ 隨機存取     │   O(1)   │   O(1)   │" << std::endl;
    std::cout << "│ 尾端增刪     │ 攤銷O(1) │   O(1)   │" << std::endl;
    std::cout << "│ 頭端增刪     │   O(n)   │   O(1)   │" << std::endl;
    std::cout << "│ 中間增刪     │   O(n)   │   O(n)   │" << std::endl;
    std::cout << "│ 連續記憶體   │    是    │    否    │" << std::endl;
    std::cout << "└──────────────┴──────────┴──────────┘" << std::endl;

    std::cout << "\n========================================" << std::endl;
    std::cout << "  vector 與 deque 示範結束" << std::endl;
    std::cout << "========================================" << std::endl;

    return 0;
}