STL标准模板库

STL（Standard Template Library）是C++标准库的重要组成部分，提供了容器、迭代器、算法和函数对象等组件。本章将详细介绍STL的使用方法。

容器概述

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <array>
using namespace std;

/*
 * STL容器分类：
 * 
 * 1. 序列容器（顺序容器）
 *    - vector：动态数组
 *    - deque：双端队列
 *    - list：双向链表
 *    - forward_list：单向链表
 *    - array：固定大小数组
 * 
 * 2. 关联容器
 *    - set/multiset：集合
 *    - map/multimap：映射
 *    - unordered_set/unordered_multiset：哈希集合
 *    - unordered_map/unordered_multimap：哈希映射
 * 
 * 3. 容器适配器
 *    - stack：栈
 *    - queue：队列
 *    - priority_queue：优先队列
 */

int main() {
    // ============ vector ============
    
    vector<int> vec = {1, 2, 3, 4, 5};
    
    // 添加元素
    vec.push_back(6);
    vec.emplace_back(7);  // C++11，更高效
    
    // 访问元素
    cout << "vec[0] = " << vec[0] << endl;
    cout << "vec.at(1) = " << vec.at(1) << endl;  // 带边界检查
    cout << "vec.front() = " << vec.front() << endl;
    cout << "vec.back() = " << vec.back() << endl;
    
    // 大小和容量
    cout << "size = " << vec.size() << endl;
    cout << "capacity = " << vec.capacity() << endl;
    
    // 遍历
    cout << "vector: ";
    for (int n : vec) {
        cout << n << " ";
    }
    cout << endl;
    
    
    // ============ list ============
    
    list<int> lst = {1, 2, 3, 4, 5};
    
    // 在头部和尾部添加
    lst.push_front(0);
    lst.push_back(6);
    
    // 插入
    auto it = lst.begin();
    advance(it, 2);  // 移动迭代器
    lst.insert(it, 100);
    
    cout << "list: ";
    for (int n : lst) {
        cout << n << " ";
    }
    cout << endl;
    
    
    // ============ deque ============
    
    deque<int> dq = {1, 2, 3};
    
    dq.push_front(0);
    dq.push_back(4);
    
    cout << "deque: ";
    for (int n : dq) {
        cout << n << " ";
    }
    cout << endl;
    
    
    // ============ array ============
    
    array<int, 5> arr = {1, 2, 3, 4, 5};
    
    cout << "array: ";
    for (int n : arr) {
        cout << n << " ";
    }
    cout << endl;
    
    cout << "array size = " << arr.size() << endl;
    
    return 0;
}

关联容器

#include <iostream>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
using namespace std;

int main() {
    // ============ set ============
    
    // 自动排序，不允许重复
    set<int> s = {5, 3, 1, 4, 2};
    
    s.insert(6);
    s.insert(3);  // 重复元素不会被插入
    
    cout << "set: ";
    for (int n : s) {
        cout << n << " ";
    }
    cout << endl;
    
    // 查找
    if (s.find(3) != s.end()) {
        cout << "找到 3" << endl;
    }
    
    // 统计
    cout << "count(3) = " << s.count(3) << endl;
    
    // multiset：允许重复
    multiset<int> ms = {1, 2, 2, 3, 3, 3};
    cout << "multiset count(3) = " << ms.count(3) << endl;
    
    
    // ============ map ============
    
    // 键值对，按键排序
    map<string, int> scores;
    
    // 插入
    scores["张三"] = 90;
    scores["李四"] = 85;
    scores.insert({"王五", 95});
    scores.emplace("赵六", 88);
    
    // 访问
    cout << "\n张三的分数: " << scores["张三"] << endl;
    
    // 遍历
    cout << "map内容:" << endl;
    for (const auto& pair : scores) {
        cout << "  " << pair.first << ": " << pair.second << endl;
    }
    
    // 查找
    auto it = scores.find("李四");
    if (it != scores.end()) {
        cout << "找到李四，分数: " << it->second << endl;
    }
    
    // multimap：允许重复键
    multimap<string, int> mm;
    mm.insert({"课程", 90});
    mm.insert({"课程", 85});
    cout << "multimap count(\"课程\") = " << mm.count("课程") << endl;
    
    
    // ============ unordered_set ============
    
    // 哈希实现，不排序，查找更快
    unordered_set<int> us = {5, 3, 1, 4, 2};
    
    us.insert(6);
    
    cout << "\nunordered_set: ";
    for (int n : us) {
        cout << n << " ";
    }
    cout << endl;
    
    // 平均O(1)查找
    if (us.find(3) != us.end()) {
        cout << "找到 3" << endl;
    }
    
    
    // ============ unordered_map ============
    
    unordered_map<string, int> um;
    
    um["apple"] = 1;
    um["banana"] = 2;
    um["orange"] = 3;
    
    cout << "\nunordered_map内容:" << endl;
    for (const auto& pair : um) {
        cout << "  " << pair.first << ": " << pair.second << endl;
    }
    
    return 0;
}

迭代器

#include <iostream>
#include <vector>
#include <list>
#include <iterator>
using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 4, 5};
    
    // ============ 迭代器类型 ============
    
    // 正向迭代器
    cout << "正向遍历: ";
    for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 反向迭代器
    cout << "反向遍历: ";
    for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        cout << *rit << " ";
    }
    cout << endl;
    
    // 常量迭代器
    cout << "常量迭代器: ";
    for (auto cit = vec.cbegin(); cit != vec.cend(); ++cit) {
        cout << *cit << " ";
        // *cit = 10;  // 错误：不能修改
    }
    cout << endl;
    
    // C++11：范围for循环
    cout << "范围for: ";
    for (int n : vec) {
        cout << n << " ";
    }
    cout << endl;
    
    
    // ============ 迭代器操作 ============
    
    auto it = vec.begin();
    
    // 前进
    advance(it, 2);  // it指向第3个元素
    cout << "\nadvance后: " << *it << endl;
    
    // 距离
    auto it2 = vec.end();
    cout << "distance: " << distance(vec.begin(), it2) << endl;
    
    // 下一个
    auto nextIt = next(it);
    cout << "next: " << *nextIt << endl;
    
    // 上一个
    auto prevIt = prev(it);
    cout << "prev: " << *prevIt << endl;
    
    
    // ============ 插入迭代器 ============
    
    vector<int> v1 = {1, 2, 3};
    vector<int> v2 = {4, 5, 6};
    
    // back_inserter：在末尾插入
    copy(v2.begin(), v2.end(), back_inserter(v1));
    
    cout << "\nback_inserter后: ";
    for (int n : v1) {
        cout << n << " ";
    }
    cout << endl;
    
    // front_inserter：在开头插入（适用于list、deque）
    list<int> lst = {1, 2, 3};
    list<int> lst2 = {4, 5, 6};
    copy(lst2.begin(), lst2.end(), front_inserter(lst));
    
    cout << "front_inserter后: ";
    for (int n : lst) {
        cout << n << " ";
    }
    cout << endl;
    
    // inserter：在指定位置插入
    vector<int> v3 = {1, 2, 5, 6};
    vector<int> v4 = {3, 4};
    auto insertIt = v3.begin() + 2;
    copy(v4.begin(), v4.end(), inserter(v3, insertIt));
    
    cout << "inserter后: ";
    for (int n : v3) {
        cout << n << " ";
    }
    cout << endl;
    
    
    // ============ 流迭代器 ============
    
    // 输出流迭代器
    cout << "\n流迭代器输出: ";
    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    
    return 0;
}

算法

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

int main() {
    vector<int> vec = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // ============ 排序算法 ============
    
    // sort：排序
    sort(vec.begin(), vec.end());
    cout << "升序: ";
    for (int n : vec) cout << n << " ";
    cout << endl;
    
    // 降序
    sort(vec.begin(), vec.end(), greater<int>());
    cout << "降序: ";
    for (int n : vec) cout << n << " ";
    cout << endl;
    
    // partial_sort：部分排序
    vector<int> v1 = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    partial_sort(v1.begin(), v1.begin() + 3, v1.end());
    cout << "部分排序(前3个): ";
    for (int n : v1) cout << n << " ";
    cout << endl;
    
    // stable_sort：稳定排序
    // nth_element：第n个元素
    
    // ============ 查找算法 ============
    
    vector<int> v2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // find：查找元素
    auto it = find(v2.begin(), v2.end(), 5);
    if (it != v2.end()) {
        cout << "\n找到5，位置: " << (it - v2.begin()) << endl;
    }
    
    // binary_search：二分查找（需要已排序）
    bool found = binary_search(v2.begin(), v2.end(), 5);
    cout << "binary_search(5): " << (found ? "找到" : "未找到") << endl;
    
    // lower_bound：第一个 >= 目标的位置
    auto lb = lower_bound(v2.begin(), v2.end(), 5);
    cout << "lower_bound(5): " << (lb - v2.begin()) << endl;
    
    // upper_bound：第一个 > 目标的位置
    auto ub = upper_bound(v2.begin(), v2.end(), 5);
    cout << "upper_bound(5): " << (ub - v2.begin()) << endl;
    
    // find_if：条件查找
    auto it2 = find_if(v2.begin(), v2.end(), [](int n) { return n > 5; });
    if (it2 != v2.end()) {
        cout << "第一个大于5的数: " << *it2 << endl;
    }
    
    // ============ 修改算法 ============
    
    vector<int> v3 = {1, 2, 3, 4, 5};
    vector<int> v4(5);
    
    // copy：复制
    copy(v3.begin(), v3.end(), v4.begin());
    
    // transform：变换
    transform(v3.begin(), v3.end(), v4.begin(), [](int n) { return n * 2; });
    cout << "\ntransform后: ";
    for (int n : v4) cout << n << " ";
    cout << endl;
    
    // fill：填充
    fill(v4.begin(), v4.end(), 0);
    
    // replace：替换
    vector<int> v5 = {1, 2, 3, 2, 4, 2, 5};
    replace(v5.begin(), v5.end(), 2, 10);
    cout << "replace后: ";
    for (int n : v5) cout << n << " ";
    cout << endl;
    
    // remove：移除（实际是移动，返回新逻辑末尾）
    v5.erase(remove(v5.begin(), v5.end(), 10), v5.end());
    cout << "remove后: ";
    for (int n : v5) cout << n << " ";
    cout << endl;
    
    // ============ 数值算法 ============
    
    vector<int> v6 = {1, 2, 3, 4, 5};
    
    // accumulate：累加
    int sum = accumulate(v6.begin(), v6.end(), 0);
    cout << "\n累加和: " << sum << endl;
    
    // 带操作的累加
    int product = accumulate(v6.begin(), v6.end(), 1, multiplies<int>());
    cout << "累乘积: " << product << endl;
    
    // adjacent_difference：相邻差
    // inner_product：内积
    // partial_sum：部分和
    
    // ============ 其他算法 ============
    
    // count：计数
    vector<int> v7 = {1, 2, 3, 2, 4, 2, 5};
    int cnt = count(v7.begin(), v7.end(), 2);
    cout << "\n2的个数: " << cnt << endl;
    
    // count_if：条件计数
    cnt = count_if(v7.begin(), v7.end(), [](int n) { return n > 2; });
    cout << "大于2的个数: " << cnt << endl;
    
    // min_element / max_element
    auto minIt = min_element(v7.begin(), v7.end());
    auto maxIt = max_element(v7.begin(), v7.end());
    cout << "最小值: " << *minIt << ", 最大值: " << *maxIt << endl;
    
    // reverse：反转
    reverse(v7.begin(), v7.end());
    cout << "反转后: ";
    for (int n : v7) cout << n << " ";
    cout << endl;
    
    // unique：去重（需要先排序）
    sort(v7.begin(), v7.end());
    v7.erase(unique(v7.begin(), v7.end()), v7.end());
    cout << "去重后: ";
    for (int n : v7) cout << n << " ";
    cout << endl;
    
    return 0;
}

本章小结

本章学习了：

• 序列容器：vector、list、deque、array
• 关联容器：set、map、unordered_set、unordered_map
• 迭代器：正向、反向、插入迭代器、流迭代器
• 算法：排序、查找、修改、数值算法

下一章，我们将学习异常处理，了解C++的错误处理机制。