C++ 标准模板库（STL）入门基础

1. 容器（Containers）

1.1 序列容器

vector - 动态数组

#include <vector>
#include <iostream>

void vector_example() {
    // 创建和初始化
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2(5, 10); // 5个元素，每个都是10
    std::vector<int> v3(v1);    // 拷贝构造
    
    // 元素访问
    std::cout << "v1[0]: " << v1[0] << std::endl;        // 不检查边界
    std::cout << "v1.at(1): " << v1.at(1) << std::endl;  // 检查边界，越界抛出异常
    std::cout << "front: " << v1.front() << std::endl;   // 第一个元素
    std::cout << "back: " << v1.back() << std::endl;     // 最后一个元素
    
    // 容量操作
    std::cout << "size: " << v1.size() << std::endl;
    std::cout << "capacity: " << v1.capacity() << std::endl;
    std::cout << "empty: " << v1.empty() << std::endl;
    
    // 修改操作
    v1.push_back(6);           // 末尾添加
    v1.pop_back();             // 删除末尾
    v1.insert(v1.begin() + 2, 99);  // 在位置2插入99
    v1.erase(v1.begin() + 1);        // 删除位置1的元素
    v1.clear();                // 清空
    
    // 遍历
    for (size_t i = 0; i < v1.size(); ++i) {
        std::cout << v1[i] << " ";
    }
    std::cout << std::endl;
    
    for (auto it = v1.begin(); it != v1.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    for (int val : v1) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
}

list - 双向链表

#include <list>

void list_example() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    
    // 前后插入
    lst.push_front(0);
    lst.push_back(6);
    lst.pop_front();
    lst.pop_back();
    
    // 插入和删除
    auto it = lst.begin();
    std::advance(it, 2);  // 移动迭代器到位置2
    lst.insert(it, 99);
    lst.erase(it);
    
    // 特殊操作
    lst.sort();                    // 排序
    lst.unique();                  // 去重
    lst.reverse();                 // 反转
    
    // 合并链表
    std::list<int> lst2 = {7, 8, 9};
    lst.merge(lst2);               // 合并后lst2为空
    
    // 遍历
    for (int val : lst) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
}

deque - 双端队列

#include <deque>

void deque_example() {
    std::deque<int> dq = {1, 2, 3, 4, 5};
    
    // 两端操作
    dq.push_front(0);
    dq.push_back(6);
    dq.pop_front();
    dq.pop_back();
    
    // 随机访问
    std::cout << "dq[2]: " << dq[2] << std::endl;
    std::cout << "dq.at(3): " << dq.at(3) << std::endl;
}

array - 固定大小数组（C++11）

#include <array>

void array_example() {
    std::array<int, 5> arr = {1, 2, 3, 4, 5};
    
    // 与普通数组类似，但更安全
    std::cout << "size: " << arr.size() << std::endl;
    std::cout << "front: " << arr.front() << std::endl;
    std::cout << "back: " << arr.back() << std::endl;
    
    // 填充
    arr.fill(10);  // 所有元素变为10
}

1.2 关联容器

set - 有序集合（不重复）

#include <set>

void set_example() {
    std::set<int> s = {5, 2, 8, 1, 9};
    
    // 插入
    s.insert(3);
    s.insert(5);  // 重复，不会插入
    
    // 查找
    auto it = s.find(3);
    if (it != s.end()) {
        std::cout << "Found: " << *it << std::endl;
    }
    
    // 计数（对于set，只能是0或1）
    std::cout << "Count of 5: " << s.count(5) << std::endl;
    
    // 删除
    s.erase(2);
    
    // 遍历（自动排序）
    for (int val : s) {
        std::cout << val << " ";  // 输出：1 3 5 8 9
    }
    std::cout << std::endl;
    
    // 范围查找
    auto lower = s.lower_bound(3);  // 第一个 >= 3 的元素
    auto upper = s.upper_bound(7);  // 第一个 > 7 的元素
}

map - 有序键值对

#include <map>
#include <string>

void map_example() {
    std::map<std::string, int> scores;
    
    // 插入
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores.insert({"Charlie", 92});
    
    // 访问
    std::cout << "Alice's score: " << scores["Alice"] << std::endl;
    
    // 检查存在
    if (scores.find("David") == scores.end()) {
        std::cout << "David not found" << std::endl;
    }
    
    // 遍历
    for (const auto& pair : scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    // 删除
    scores.erase("Bob");
}

unordered_set 和 unordered_map - 哈希容器（C++11）

#include <unordered_set>
#include <unordered_map>

void unordered_example() {
    // unordered_set
    std::unordered_set<int> us = {3, 1, 4, 1, 5, 9};
    
    // unordered_map
    std::unordered_map<std::string, int> um;
    um["one"] = 1;
    um["two"] = 2;
    
    // 哈希特定操作
    std::cout << "Bucket count: " << um.bucket_count() << std::endl;
    std::cout << "Load factor: " << um.load_factor() << std::endl;
}

1.3 容器适配器

stack - 栈

#include <stack>

void stack_example() {
    std::stack<int> st;
    
    st.push(1);
    st.push(2);
    st.push(3);
    
    while (!st.empty()) {
        std::cout << st.top() << " ";  // 输出：3 2 1
        st.pop();
    }
    std::cout << std::endl;
}

queue - 队列

#include <queue>

void queue_example() {
    std::queue<int> q;
    
    q.push(1);
    q.push(2);
    q.push(3);
    
    while (!q.empty()) {
        std::cout << q.front() << " ";  // 输出：1 2 3
        q.pop();
    }
    std::cout << std::endl;
}

priority_queue - 优先队列

#include <queue>
#include <vector>

void priority_queue_example() {
    // 最大堆（默认）
    std::priority_queue<int> pq1;
    
    // 最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq2;
    
    pq1.push(3);
    pq1.push(1);
    pq1.push(4);
    
    while (!pq1.empty()) {
        std::cout << pq1.top() << " ";  // 输出：4 3 1
        pq1.pop();
    }
    std::cout << std::endl;
}

2. 迭代器（Iterators）

2.1 迭代器类型

#include <vector>
#include <list>

void iterator_example() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 正向迭代器
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 反向迭代器
    for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        std::cout << *rit << " ";  // 输出：5 4 3 2 1
    }
    std::cout << std::endl;
    
    // 常量迭代器（只读）
    for (auto cit = vec.cbegin(); cit != vec.cend(); ++cit) {
        // *cit = 10;  // 错误，不能修改
        std::cout << *cit << " ";
    }
    std::cout << std::endl;
}

2.2 迭代器操作

#include <iterator>

void iterator_operations() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    auto it = vec.begin();
    
    // 移动迭代器
    std::advance(it, 3);        // 移动3个位置
    auto dist = std::distance(vec.begin(), it);  // 计算距离
    
    // 下一个和前一个位置
    auto next_it = std::next(it, 2);    // it后面第2个
    auto prev_it = std::prev(it, 1);    // it前面第1个
}

3. 算法（Algorithms）

3.1 非修改序列操作

遍历和查找

#include <algorithm>
#include <vector>

void non_modifying_algorithms() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 3, 2, 1};
    
    // 查找
    auto it1 = std::find(vec.begin(), vec.end(), 3);
    auto it2 = std::find_if(vec.begin(), vec.end(), [](int x) {
        return x > 3;
    });
    
    // 计数
    int count3 = std::count(vec.begin(), vec.end(), 3);
    int count_gt2 = std::count_if(vec.begin(), vec.end(), [](int x) {
        return x > 2;
    });
    
    // 遍历执行操作
    std::for_each(vec.begin(), vec.end(), [](int& x) {
        std::cout << x << " ";
    });
    std::cout << std::endl;
    
    // 检查条件
    bool all_even = std::all_of(vec.begin(), vec.end(), [](int x) {
        return x % 2 == 0;
    });
    bool any_even = std::any_of(vec.begin(), vec.end(), [](int x) {
        return x % 2 == 0;
    });
    bool none_negative = std::none_of(vec.begin(), vec.end(), [](int x) {
        return x < 0;
    });
}

3.2 修改序列操作

复制和变换

void modifying_algorithms() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    std::vector<int> dst(5);
    
    // 复制
    std::copy(src.begin(), src.end(), dst.begin());
    
    // 条件复制
    std::vector<int> even_nums;
    std::copy_if(src.begin(), src.end(), std::back_inserter(even_nums),
                 [](int x) { return x % 2 == 0; });
    
    // 变换
    std::vector<int> squared;
    std::transform(src.begin(), src.end(), std::back_inserter(squared),
                   [](int x) { return x * x; });
    
    // 替换
    std::replace(src.begin(), src.end(), 3, 30);
    std::replace_if(src.begin(), src.end(),
                    [](int x) { return x < 3; }, 0);
    
    // 填充
    std::fill(src.begin(), src.end(), 10);
    std::fill_n(src.begin(), 3, 5);  // 前3个元素填充为5
}

删除和去重

void remove_algorithms() {
    std::vector<int> vec = {1, 2, 3, 2, 4, 2, 5};
    
    // 移除值为2的元素（实际是移动到末尾）
    auto new_end = std::remove(vec.begin(), vec.end(), 2);
    vec.erase(new_end, vec.end());  // 真正删除
    
    // 条件移除
    new_end = std::remove_if(vec.begin(), vec.end(),
                             [](int x) { return x % 2 == 0; });
    vec.erase(new_end, vec.end());
    
    // 去重（需要先排序）
    std::vector<int> vec2 = {1, 2, 2, 3, 3, 3, 4};
    std::sort(vec2.begin(), vec2.end());
    auto last = std::unique(vec2.begin(), vec2.end());
    vec2.erase(last, vec2.end());
}

3.3 排序和搜索

排序算法

#include <algorithm>

void sorting_algorithms() {
    std::vector<int> vec = {5, 2, 8, 1, 9, 3};
    
    // 排序
    std::sort(vec.begin(), vec.end());                    // 升序
    std::sort(vec.begin(), vec.end(), std::greater<int>()); // 降序
    
    // 部分排序
    std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
    
    // 第n大元素
    std::nth_element(vec.begin(), vec.begin() + 2, vec.end());
    
    // 堆操作
    std::make_heap(vec.begin(), vec.end());
    std::pop_heap(vec.begin(), vec.end());
    vec.pop_back();
    vec.push_back(10);
    std::push_heap(vec.begin(), vec.end());
}

搜索算法

void searching_algorithms() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // 二分查找（必须有序）
    bool found = std::binary_search(vec.begin(), vec.end(), 5);
    
    // 边界查找
    auto lower = std::lower_bound(vec.begin(), vec.end(), 5);  // 第一个 >= 5
    auto upper = std::upper_bound(vec.begin(), vec.end(), 5);  // 第一个 > 5
    
    // 相等范围
    auto range = std::equal_range(vec.begin(), vec.end(), 5);
}

3.4 数值算法

#include <numeric>

void numeric_algorithms() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 累加
    int sum = std::accumulate(vec.begin(), vec.end(), 0);
    int product = std::accumulate(vec.begin(), vec.end(), 1, 
                                  std::multiplies<int>());
    
    // 内积
    std::vector<int> vec2 = {2, 2, 2, 2, 2};
    int inner_prod = std::inner_product(vec.begin(), vec.end(), vec2.begin(), 0);
    
    // 部分和
    std::vector<int> partial_sums(vec.size());
    std::partial_sum(vec.begin(), vec.end(), partial_sums.begin());
    
    // 相邻差
    std::vector<int> adjacent_diffs(vec.size());
    std::adjacent_difference(vec.begin(), vec.end(), adjacent_diffs.begin());
}

4. 函数对象（Function Objects）

4.1 内置函数对象

#include <functional>
#include <algorithm>

void function_objects() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 算术运算
    std::plus<int> add;
    std::multiplies<int> multiply;
    
    // 关系运算
    std::greater<int> gt;
    std::less_equal<int> le;
    
    // 逻辑运算
    std::logical_and<bool> land;
    std::logical_not<bool> lnot;
    
    // 使用函数对象
    std::sort(vec.begin(), vec.end(), std::greater<int>());
    
    // 使用bind（C++11）
    auto add5 = std::bind(std::plus<int>(), std::placeholders::_1, 5);
    std::vector<int> result;
    std::transform(vec.begin(), vec.end(), std::back_inserter(result), add5);
}

5. 实用工具

5.1 pair 和 tuple

#include <utility>
#include <tuple>

void utility_examples() {
    // pair
    std::pair<int, std::string> p1(1, "Alice");
    auto p2 = std::make_pair(2, "Bob");
    
    // tuple（C++11）
    std::tuple<int, std::string, double> t1(1, "Alice", 95.5);
    auto t2 = std::make_tuple(2, "Bob", 87.5);
    
    // 访问tuple
    std::cout << std::get<0>(t1) << std::endl;
    std::cout << std::get<1>(t1) << std::endl;
}

5.2 智能指针（C++11）

#include <memory>

void smart_pointers() {
    // unique_ptr - 独占所有权
    std::unique_ptr<int> ptr1 = std::make_unique<int>(10);
    // auto ptr2 = ptr1;  // 错误，不能复制
    
    // shared_ptr - 共享所有权
    std::shared_ptr<int> shared1 = std::make_shared<int>(20);
    auto shared2 = shared1;  // 引用计数+1
    
    // weak_ptr - 弱引用，不增加引用计数
    std::weak_ptr<int> weak = shared1;
    
    if (auto locked = weak.lock()) {  // 尝试获取shared_ptr
        std::cout << *locked << std::endl;
    }
}

6. 综合示例

6.1 学生成绩管理系统

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

struct Student {
    std::string name;
    int score;
    
    Student(const std::string& n, int s) : name(n), score(s) {}
    
    // 用于排序
    bool operator<(const Student& other) const {
        return score > other.score;  // 按分数降序
    }
};

void student_management() {
    std::vector<Student> students = {
        {"Alice", 85}, {"Bob", 92}, {"Charlie", 78},
        {"David", 95}, {"Eve", 88}
    };
    
    // 按分数排序
    std::sort(students.begin(), students.end());
    
    // 查找90分以上的学生
    auto it = std::find_if(students.begin(), students.end(),
                           [](const Student& s) { return s.score >= 90; });
    
    // 计算平均分
    double avg = std::accumulate(students.begin(), students.end(), 0.0,
                                [](double sum, const Student& s) {
                                    return sum + s.score;
                                }) / students.size();
    
    // 输出结果
    std::cout << "Ranking:" << std::endl;
    for (const auto& student : students) {
        std::cout << student.name << ": " << student.score << std::endl;
    }
    
    std::cout << "Average: " << avg << std::endl;
}