STL 标准库 - C / C++

01. STL 六大组件概览

STL（标准模板库）是 C++ 最强大的库，六大组件：容器（存数据）、算法（排序查找等）、迭代器（连接容器和算法的桥梁）、仿函数（函数对象）、适配器（改造接口）、分配器（内存管理）。最常用的就是容器加算法，用迭代器串联，vector<int> v; sort(v.begin(), v.end()); 一行搞定。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3};
    
    // 算法 + 迭代器
    std::sort(v.begin(), v.end());
    
    auto it = std::find(v.begin(), v.end(), 8);
    if (it != v.end()) std::cout << "找到了: " << *it << "\n";
    
    for (int n : v) std::cout << n << " ";
    // 1 2 3 5 8 9
    
    return 0;
}

STL 的核心思想是算法和容器解耦，通过迭代器这个中间层连接。

02. 序列容器：vector、list、deque

vector 是动态数组，末尾增删 O(1)，随机访问 O(1)，是默认选择。list 是双向链表，任意位置增删 O(1)，但不能随机访问。deque 是双端队列，头尾增删都是 O(1)，还能随机访问，实现上是一个分块的数组。大部分场景用 vector，需要频繁头部操作用 deque。

cpp

#include <vector>
#include <list>
#include <deque>

int main() {
    // vector: 默认选择
    std::vector<int> v = {1, 2, 3};
    v.push_back(4);
    v.pop_back();
    int third = v[2]; // 随机访问
    
    // list: 频繁中间插入
    std::list<int> lst = {1, 2, 3};
    lst.push_front(0);
    lst.push_back(4);
    auto it = lst.begin();
    ++it;
    lst.insert(it, 99);
    
    // deque: 两头操作
    std::deque<int> dq;
    dq.push_back(1);
    dq.push_front(0);
    dq.pop_front();
    
    return 0;
}

03. 关联容器：set、map

set 存唯一键，自动排序（默认升序），底层是红黑树。map 存键值对，按 key 排序，key 必须唯一。unordered_set 和 unordered_map 是基于哈希表的，无序但 O(1) 平均查找。需要排序用 set/map，追求速度用 unordered_map。multiset/multimap 允许重复键。

cpp

#include <set>
#include <map>
#include <unordered_map>

int main() {
    // set: 自动排序去重
    std::set<int> s = {3, 1, 4, 1, 5};
    // s 里是 {1, 3, 4, 5}
    s.insert(2);
    if (s.count(3)) std::cout << "存在\n";
    
    // map: 键值对
    std::map<std::string, int> scores;
    scores["小明"] = 95;
    scores["小红"] = 88;
    
    for (auto& [name, score] : scores) {
        std::cout << name << ": " << score << "\n";
    }
    
    // unordered_map: 哈希表，快但无序
    std::unordered_map<std::string, int> hash;
    hash["apple"] = 3;
    hash["banana"] = 5;
    
    return 0;
}

如果不能确定用 map 还是 unordered_map，默认用 map，需要性能优化时再切 unordered_map。

04. 常用算法

STL 算法有上百个，最常用的：sort 排序、find 查找、binary_search 二分查找、count 计数、reverse 翻转、unique 去重、min_element/max_element 找极值、accumulate 求和、for_each 遍历执行操作。lambda 表达式让算法更灵活，一个 lambda 替代一个专门写的函数。

cpp

#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // 排序和去重
    std::sort(v.begin(), v.end());
    auto last = std::unique(v.begin(), v.end());
    v.erase(last, v.end());
    
    // 查找
    auto it = std::find(v.begin(), v.end(), 4);
    bool has5 = std::binary_search(v.begin(), v.end(), 5);
    
    // 计数
    int ones = std::count(v.begin(), v.end(), 1);
    
    // 累加
    int sum = std::accumulate(v.begin(), v.end(), 0);
    
    // lambda + for_each
    std::for_each(v.begin(), v.end(), [](int n) {
        std::cout << n * 2 << " ";
    });
    
    return 0;
}

binary_search 要求容器已排序，所以通常先 sort 再二分查找。

05. 智能指针和容器配合

C++11 引入智能指针后，在容器里存指针不再是噩梦。存 shared_ptr<T> 到 vector 里，最后一个引用消失时自动释放。unique_ptr<T> 独占所有权，只能移动不能拷贝。容器存指针的另一种方式是存值，用 vector<T> 而不是 vector<T*>，RAII 帮你自动管理。

cpp

#include <memory>
#include <vector>
#include <iostream>

class Animal {
public:
    virtual void speak() = 0;
    virtual ~Animal() = default;
};

class Dog : public Animal {
public:
    void speak() override { std::cout << "汪汪\n"; }
};

int main() {
    // vector 存 shared_ptr
    std::vector<std::shared_ptr<Animal>> animals;
    animals.push_back(std::make_shared<Dog>());
    animals.push_back(std::make_shared<Dog>());
    
    for (auto& a : animals) a->speak();
    
    // vector 存 unique_ptr
    std::vector<std::unique_ptr<Animal>> uanimals;
    uanimals.push_back(std::make_unique<Dog>());
    
    // 离开作用域自动释放所有指针，不用手动 delete
    return 0;
}

C++11 之后尽量用智能指针替代裸指针，容器里存 shared_ptr/unique_ptr 而不是 new 出来的指针。

知识测验

第 1/4 题正确 0

STL 中连接容器和算法的桥梁是什么？

现代 C++