# ===== CodeLab: cpp-deque-list =====
# 以下代码片段按文章出现顺序拼接, 共 7 段

# ----- 片段 1 (cpp) -----
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3, 4, 5};
    // 头部插入:所有元素都要往后挪一位,O(n)
    v.insert(v.begin(), 0);
    // 中间插入:同样要搬移
    v.insert(v.begin() + 3, 99);
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";   // 0 1 2 99 3 4 5
    return 0;
}

# ----- 片段 2 (cpp) -----
#include <deque>
#include <iostream>

int main() {
    std::deque<int> d;
    d.push_back(30);    // 尾部
    d.push_front(20);   // 头部
    d.push_front(10);
    d.push_back(40);
    std::cout << "front=" << d.front() << ", back=" << d.back() << "\n";
    d.pop_front();      // 弹出头部
    d.pop_back();       // 弹出尾部
    for (int x : d) std::cout << x << " ";
    std::cout << "\n";   // 20 30
    return 0;
}

# ----- 片段 3 (cpp) -----
#include <algorithm>
#include <iostream>
#include <list>

int main() {
    std::list<int> lst{10, 20, 30, 40};
    // 找到 20 所在位置,在其前面插入 15
    auto it = std::find(lst.begin(), lst.end(), 20);
    lst.insert(it, 15);
    // 删除 30
    auto it2 = std::find(lst.begin(), lst.end(), 30);
    lst.erase(it2);
    for (int x : lst) std::cout << x << " ";
    std::cout << "\n";   // 10 15 20 40
    return 0;
}

# ----- 片段 4 (cpp) -----
#include <iostream>
#include <list>

int main() {
    std::list<int> nums{1, 2, 3, 4, 5, 6, 7, 8};
    // 一边遍历一边删除偶数:erase 返回下一个有效迭代器
    for (auto it = nums.begin(); it != nums.end();) {
        if (*it % 2 == 0) {
            it = nums.erase(it);
        } else {
            ++it;
        }
    }
    for (int x : nums) std::cout << x << " ";
    std::cout << "\n";   // 1 3 5 7
    return 0;
}

# ----- 片段 5 (cpp) -----
#include <iostream>
#include <list>

int main() {
    std::list<int> a{5, 1, 4};
    std::list<int> b{3, 2};
    a.sort();          // 链表自己的排序,不是 std::sort
    b.sort();
    a.merge(b);        // 把有序的 b 合并进有序的 a,b 变空
    a.unique();        // 去掉相邻重复的元素
    for (int x : a) std::cout << x << " ";
    std::cout << "\n"; // 1 2 3 4 5

    // splice:把 y 的节点整体搬到 x 头部,O(1) 完成
    std::list<int> x{100, 200}, y{1, 2, 3};
    x.splice(x.begin(), y);   // y 变空
    for (int v : x) std::cout << v << " ";
    std::cout << "\n";        // 1 2 3 100 200
    return 0;
}

# ----- 片段 6 (cpp) -----
#include <algorithm>
#include <forward_list>
#include <iostream>

int main() {
    std::forward_list<int> fl{3, 1, 4};
    fl.push_front(0);          // 单链表只能从头部插入
    // 在值为 1 的元素后面插入 2
    auto it = std::find(fl.begin(), fl.end(), 1);
    fl.insert_after(it, 2);
    fl.remove(3);              // 删除所有值为 3 的节点
    for (int x : fl) std::cout << x << " ";
    std::cout << "\n";         // 0 1 2 4
    return 0;
}

# ----- 片段 7 (cpp) -----
#include <deque>
#include <iostream>
#include <string>

int main() {
    std::deque<std::string> tasks;
    tasks.push_back("写代码");
    tasks.push_back("写测试");
    tasks.push_back("写文档");
    tasks.push_front("紧急修复");   // 新来的紧急任务插队到队头

    while (!tasks.empty()) {
        // 交替从两头取任务,模拟两个处理者
        std::string job;
        if (tasks.size() % 2 == 0) { job = tasks.front(); tasks.pop_front(); }
        else                       { job = tasks.back();  tasks.pop_back();  }
        std::cout << "处理: " << job << "\n";
    }
    return 0;
}