跳到主要内容

C++ STL 标准库

STL（Standard Template Library）是 C++ 标准库的重要组成部分，提供了丰富的容器、算法和迭代器。本章将详细介绍 STL 的核心组件。

STL 概述​

STL 包含以下主要组件：

┌─────────────────────────────────────────────────────────┐
│                    STL 组件                             │
├─────────────────────────────────────────────────────────┤
│  容器    │  数据存储结构，如 vector, map, set 等        │
│  算法    │  排序、查找、转换等操作                       │
│  迭代器  │  遍历容器的对象                              │
│  函数对象│  可调用对象（仿函数）                         │
│  适配器  │  容器、迭代器、函数适配器                     │
│  分配器  │  内存管理策略                                │
└─────────────────────────────────────────────────────────┘

顺序容器​

vector（动态数组）​

#include <vector>
#include <iostream>

int main() {
    // 创建
    std::vector<int> v1;              // 空向量
    std::vector<int> v2(5);           // 5个元素，值为0
    std::vector<int> v3(5, 10);       // 5个元素，值为10
    std::vector<int> v4 = {1, 2, 3};  // 初始化列表
    
    // 访问元素
    v4.push_back(4);                  // 末尾添加
    v4[0];                            // 下标访问（不检查边界）
    v4.at(0);                         // 下标访问（检查边界）
    v4.front();                       // 第一个元素
    v4.back();                        // 最后一个元素
    
    // 遍历
    for (int x : v4) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    // 大小操作
    v4.size();        // 元素个数
    v4.empty();       // 是否为空
    v4.capacity();    // 容量
    
    // 修改
    v4.pop_back();    // 删除末尾
    v4.insert(v4.begin() + 1, 99);  // 插入
    v4.erase(v4.begin() + 1);       // 删除
    
    return 0;
}

deque（双端队列）​

#include <deque>

int main() {
    std::deque<int> d;
    
    // 两端操作
    d.push_front(1);   // 头部插入
    d.push_back(2);     // 尾部插入
    d.pop_front();     // 头部删除
    d.pop_back();      // 尾部删除
    
    // 随机访问（与 vector 相同）
    d[0];
    d.at(1);
    
    return 0;
}

list（双向链表）​

#include <list>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    
    // 链表特有操作
    lst.push_front(0);     // 头部插入
    lst.push_back(6);      // 尾部插入
    
    // 在指定位置插入/删除
    auto it = lst.begin();
    ++it;  // 指向第二个元素
    lst.insert(it, 99);    // 在位置插入
    
    // 双向遍历
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    
    // splice：将另一个链表移动到当前位置
    std::list<int> other = {7, 8, 9};
    lst.splice(lst.begin(), other);  // other 的元素移动到 lst 开头
    
    return 0;
}

array（C++11）​

#include <array>

int main() {
    // 固定大小数组（栈上分配）
    std::array<int, 5> arr = {1, 2, 3, 4, 5};
    
    // 访问
    arr[0];           // 不检查边界
    arr.at(0);        // 检查边界
    arr.front();      // 第一个元素
    arr.back();       // 最后一个元素
    arr.data();       // 原始指针
    
    // 大小
    arr.size();       // 5
    arr.empty();      // false
    
    // 遍历
    for (int x : arr) {
        std::cout << x << " ";
    }
    
    // 支持迭代器
    std::sort(arr.begin(), arr.end());
    
    return 0;
}

关联容器​

set（集合）​

#include <set>

int main() {
    std::set<int> s = {5, 2, 8, 1, 9, 2};  // 自动去重、排序
    
    // 插入
    s.insert(3);
    s.insert({10, 11, 12});
    
    // 查找
    auto it = s.find(5);    // 找到返回迭代器
    if (it != s.end()) {
        std::cout << "Found: " << *it << std::endl;
    }
    
    // 检查存在
    if (s.count(3)) {
        std::cout << "3 exists" << std::endl;
    }
    
    // 删除
    s.erase(5);
    s.erase(s.begin());
    
    // 遍历（有序）
    for (int x : s) {
        std::cout << x << " ";
    }
    
    return 0;
}

multiset（多重集合）​

#include <multiset>

int main() {
    std::multiset<int> ms = {1, 2, 2, 3, 3, 3};
    
    // 允许重复
    ms.insert(2);
    ms.insert(2);
    
    // count: 某个值的个数
    std::cout << ms.count(2) << std::endl;  // 4
    
    // find: 返回第一个匹配的迭代器
    auto it = ms.find(2);
    
    // 删除：删除所有匹配的
    ms.erase(3);  // 删除所有值为 3 的元素
    
    return 0;
}

map（映射）​

#include <map>

int main() {
    std::map<std::string, int> ages;
    
    // 插入
    ages["Alice"] = 25;
    ages.insert({"Bob", 30});
    ages.insert(std::make_pair("Charlie", 35));
    
    // 访问
    std::cout << ages["Alice"] << std::endl;     // 25
    // ages["David"] 会创建一个新元素！使用 find 检查
    
    auto it = ages.find("Alice");
    if (it != ages.end()) {
        std::cout << it->first << ": " << it->second << std::endl;
    }
    
    // 遍历（按键排序）
    for (const auto& [name, age] : ages) {
        std::cout << name << " -> " << age << std::endl;
    }
    
    // 删除
    ages.erase("Bob");
    
    return 0;
}

multimap（多重映射）​

#include <multimap>

int main() {
    std::multimap<std::string, int> scores;
    
    // 允许一个键对应多个值
    scores.insert({"Alice", 90});
    scores.insert({"Alice", 95});
    scores.insert({"Bob", 88});
    
    // 查找
    auto range = scores.equal_range("Alice");
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }
    
    return 0;
}

unordered_set/map（C++11）​

#include <unordered_set>
#include <unordered_map>

int main() {
    // 无序容器：哈希表实现，查找 O(1)
    std::unordered_set<int> us = {3, 1, 4, 1, 5};
    
    std::unordered_map<std::string, int> um;
    um["one"] = 1;
    um["two"] = 2;
    
    // 遍历（无序）
    for (const auto& [key, value] : um) {
        std::cout << key << ": " << value << std::endl;
    }
    
    return 0;
}

容器适配器​

stack（栈）​

#include <stack>

int main() {
    std::stack<int> s;
    
    s.push(1);   // 入栈
    s.push(2);
    s.push(3);
    
    s.top();     // 查看栈顶
    s.pop();     // 出栈
    
    s.empty();   // 是否为空
    s.size();    // 大小
    
    return 0;
}

queue（队列）​

#include <queue>

int main() {
    std::queue<int> q;
    
    q.push(1);   // 入队
    q.push(2);
    q.push(3);
    
    q.front();   // 查看队首
    q.back();    // 查看队尾
    q.pop();     // 出队
    
    return 0;
}

priority_queue（优先队列）​

#include <queue>

int main() {
    // 大顶堆（默认）
    std::priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(5);
    // pq.top() 每次都是最大的
    
    // 小顶堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq2;
    
    // 自定义比较
    struct Node {
        int priority;
        std::string data;
    };
    
    struct cmp {
        bool operator()(const Node& a, const Node& b) const {
            return a.priority < b.priority;  // 大顶堆
        }
    };
    
    std::priority_queue<Node, std::vector<Node>, cmp> pq3;
    
    return 0;
}

算法​

排序算法​

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9};
    
    // sort: 排序（快速排序，平均 O(n log n)）
    std::sort(v.begin(), v.end());           // 升序
    std::sort(v.begin(), v.end(), 
               [](int a, int b) { return a > b; });  // 降序
    
    // stable_sort: 稳定排序
    std::stable_sort(v.begin(), v.end());
    
    // partial_sort: 部分排序
    std::partial_sort(v.begin(), v.begin() + 3, v.end());  // 前3个最小
    
    // nth_element: 找到第 n 小的元素
    std::nth_element(v.begin(), v.begin() + 2, v.end());  // 第3小的在正确位置
    
    // reverse: 反转
    std::reverse(v.begin(), v.end());
    
    // shuffle: 打乱顺序
    std::random_device rd;
    std::shuffle(v.begin(), v.end(), rd);
    
    return 0;
}

查找算法​

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // find: 查找第一个匹配的元素
    auto it = std::find(v.begin(), v.end(), 3);
    
    // find_if: 查找满足条件的元素
    it = std::find_if(v.begin(), v.end(), 
                      [](int x) { return x > 3; });
    
    // binary_search: 二分查找（需已排序）
    bool found = std::binary_search(v.begin(), v.end(), 3);
    
    // lower_bound: 第一个 >= value 的位置
    auto lb = std::lower_bound(v.begin(), v.end(), 3);
    
    // upper_bound: 第一个 > value 的位置
    auto ub = std::upper_bound(v.begin(), v.end(), 3);
    
    // equal_range: 返回 [lower, upper) 范围
    auto range = std::equal_range(v.begin(), v.end(), 3);
    
    return 0;
}

变换算法​

#include <algorithm>
#include <vector>
#include <iterator>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::vector<int> result(5);
    
    // transform: 对每个元素进行变换
    std::transform(v.begin(), v.end(), result.begin(),
                   [](int x) { return x * 2; });
    // result = {2, 4, 6, 8, 10}
    
    // copy: 复制
    std::copy(v.begin(), v.end(), result.begin());
    
    // remove: 删除满足条件的元素
    v.erase(std::remove_if(v.begin(), v.end(),
                           [](int x) { return x % 2 == 0; }),
            v.end());  // 删除偶数
    
    // replace: 替换
    std::replace(v.begin(), v.end(), 3, 30);
    
    // fill: 填充
    std::fill(v.begin(), v.end(), 0);
    
    // unique: 去除相邻重复元素
    v.erase(std::unique(v.begin(), v.end()), v.end());
    
    return 0;
}

数值算法​

#include <numeric>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // accumulate: 求和
    int sum = std::accumulate(v.begin(), v.end(), 0);
    
    // inner_product: 内积
    int inner = std::inner_product(v.begin(), v.end(), v.begin(), 0);
    
    // partial_sum: 前缀和
    std::vector<int> prefix(5);
    std::partial_sum(v.begin(), v.end(), prefix.begin());
    // prefix = {1, 3, 6, 10, 15}
    
    // iota: 生成递增序列
    std::vector<int> iota(5);
    std::iota(iota.begin(), iota.end(), 1);
    // iota = {1, 2, 3, 4, 5}
    
    return 0;
}

迭代器​

迭代器类型​

#include <vector>
#include <iterator>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // 前向迭代器
    auto it = v.begin();
    ++it;  // 可以递增
    
    // 双向迭代器（list, set, map）
    ++it;
    --it;
    
    // 随机访问迭代器（vector, deque）
    auto it2 = v.begin() + 3;
    it2 - v.begin();  // 3
    *(it2 + 1);      // 访问下个元素
    
    // 反向迭代器
    std::reverse_iterator<std::vector<int>::iterator> rit;
    for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    
    // 插入迭代器
    std::vector<int> dest;
    std::copy(v.begin(), v.end(), std::back_inserter(dest));
    
    return 0;
}

迭代器适配器​

#include <iterator>
#include <sstream>

int main() {
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {4, 5, 6};
    
    // 反向迭代器
    for (auto it = v1.rbegin(); it != v1.rend(); ++it) {
        std::cout << *it << " ";
    }
    
    // 流迭代器
    std::istringstream iss("1 2 3 4 5");
    std::vector<int> v;
    std::copy(std::istream_iterator<int>(iss),
              std::istream_iterator<int>(),
              std::back_inserter(v));
    
    // ostream 迭代器
    std::copy(v.begin(), v.end(),
              std::ostream_iterator<int>(std::cout, " "));
    
    // 移动迭代器（C++11）
    // std::move(v.begin(), v.end(), dest.begin());
    
    return 0;
}

函数对象​

lambda 表达式​

#include <algorithm>
#include <functional>

int main() {
    auto isEven = [](int x) { return x % 2 == 0; };
    
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // 查找
    auto it = std::find_if(v.begin(), v.end(), isEven);
    
    // 排序
    std::sort(v.begin(), v.end(), 
              [](int a, int b) { return a > b; });
    
    // 使用 std::greater
    std::sort(v.begin(), v.end(), std::greater<int>());
    
    return 0;
}

预定义函数对象​

#include <functional>
#include <algorithm>

int main() {
    // 算术函数对象
    std::plus<int> add;
    std::cout << add(3, 5) << std::endl;  // 8
    
    std::minus<int> sub;
    std::multiplies<int> mul;
    std::divides<int> div;
    std::modulus<int> mod;
    std::negate<int> neg;
    
    // 比较函数对象
    std::equal_to<int> eq;
    std::not_equal_to<int> ne;
    std::greater<int> gt;
    std::less<int> lt;
    std::greater_equal<int> ge;
    std::less_equal<int> le;
    
    // 逻辑函数对象
    std::logical_and<int> land;
    std::logical_or<int> lor;
    std::logical_not<int> lnot;
    
    // 使用 bind 绑定参数
    auto isGreaterThan5 = std::bind(std::greater<int>(), std::placeholders::_1, 5);
    std::cout << isGreaterThan5(10) << std::endl;  // true
    
    return 0;
}

练习​

  1. 使用 vector 实现一个学生成绩管理系统
  2. 使用 map 实现一个单词计数器
  3. 使用 algorithm 实现各种排序和查找
  4. 使用 lambda 实现一个事件处理系统

小结​

本章学习了：

  1. 顺序容器：vector、deque、list、array
  2. 关联容器：set、map、multiset、multimap、unordered_*
  3. 容器适配器：stack、queue、priority_queue
  4. 算法：排序、查找、变换、数值算法
  5. 迭代器：各种迭代器类型和使用
  6. 函数对象：lambda、预定义函数对象

下一步​

接下来让我们学习 C++ 智能指针，了解现代 C++ 的内存管理。