一、什么是 STL

STL 是 C++ 标准库的核心组成部分，它封装了常见的数据结构（动态数组、链表、映射、集合等）和算法（排序、查找、叠加等），并且全部通过模板实现，与类型无关。你只需要关注“什么数据结构”和“什么算法”，而不是“什么类型”。

二、STL 的版本

STL 经历了多个版本的演变：

• HP 版本：Alexander Stepanov 在惠普实验室完成的原始版本，所有实现的始祖，开源
• P.J. 版本：被 Windows Visual C++ 采用，不能公开修改，可读性低
• RW 版本：被 C++ Builder 采用，不能公开修改
• SGI 版本：被 GCC/Linux 采用，开源、可移植性好、可读性高，是学习源码的主要参考

三、STL 的六大组件

STL 由六大组件构成，它们相互配合，构成了一个完整的生态：

1. 容器（Container）

容器用于存储数据，分为序列式容器（vector、list、deque、array）和关联式容器（set、map、multiset、multimap）。C++11 还增加了无序关联容器（unordered_set、unordered_map）。

示例 1：vector 和 list 的基本使用

#include <iostream>
#include <vector>
#include <list>

int main() {
    // vector：动态数组，强项是随机访问
    std::vector<int> vec = {1, 2, 3, 4, 5};
    vec.push_back(6);               // 尾部插入
    std::cout << "vec[2] = " << vec[2] << "\n";  // O(1) 随机访问

    // list：双向链表，强项是任意位置插入删除
    std::list<int> lst = {10, 20, 30};
    lst.push_front(0);              // 头部插入也是 O(1)
    lst.push_back(40);              // 尾部插入 O(1)

    std::cout << "list front: " << lst.front() << "\n";
    return 0;
}

2. 算法（Algorithm）

算法处理容器中的数据，如排序、查找、统计等。STL 提供了超过 100 种算法，全部以模板函数形式存在。

示例 2：常见 STL 算法

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

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3};

    // sort：排序（默认升序）
    std::sort(v.begin(), v.end());

    // 查找 8
    auto it = std::find(v.begin(), v.end(), 8);
    if (it != v.end())
        std::cout << "Found: " << *it << "\n";

    // accumulate：求和
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "Sum: " << sum << "\n";

    // 输出排序后的数组
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";
    return 0;
}

3. 迭代器（Iterator）

迭代器是容器和算法之间的纽带——它抽象了“指针”的概念，让算法可以通用地处理任意容器。在之前学习 C++ 入门时提到的 auto 关键字，最常见的使用场景就是简化迭代器类型的声明。

示例 3：三种常见迭代器用法

#include <iostream>
#include <vector>
#include <set>

int main() {
    std::vector<int> v = {10, 20, 30, 40};

    // 写法 1：显式声明迭代器（类型太长）
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        std::cout << *it << " ";
    std::cout << "\n";

    // 写法 2：使用 auto 简化（推荐）
    for (auto it = v.begin(); it != v.end(); ++it)
        std::cout << *it << " ";
    std::cout << "\n";

    // 写法 3：范围 for（最简洁）
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";

    // set 是自平衡二叉检索树，自动排序
    std::set<int> s = {3, 1, 4, 1, 5, 9};
    for (auto it = s.begin(); it != s.end(); ++it)
        std::cout << *it << " ";  // 输出: 1 3 4 5 9
    std::cout << "\n";
    return 0;
}

4. 仿函数（Functor）

仿函数是重载了 operator() 的类对象，可以像函数一样被调用。它常被用于自定义排序规则或算法的行为。

示例 4：仿函数自定义排序规则

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

// 仿函数：降序排序
struct Descending {
    bool operator()(int a, int b) const {
        return a > b;
    }
};

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9};

    // 使用仿函数指定排序规则
    std::sort(v.begin(), v.end(), Descending());

    for (int x : v) std::cout << x << " ";  // 9 8 5 2 1
    std::cout << "\n";

    // 也可以直接使用 STL 提供的仿函数
    std::sort(v.begin(), v.end(), std::greater<int>());
    return 0;
}

5. 适配器（Adapter）

适配器用于修改容器或仿函数的接口。stack 和 queue 就是常见的容器适配器——它们的底层由 deque 实现，但对外提供了不同的接口。

示例 5：容器适配器 stack 与 queue

#include <iostream>
#include <stack>
#include <queue>

int main() {
    // stack：后进先出，底层默认用 deque
    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 << "\n";

    // queue：先进先出
    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 << "\n";

    // priority_queue：优先级队列，默认大顶堆
    std::priority_queue<int> pq;
    pq.push(3); pq.push(1); pq.push(4);
    std::cout << "top = " << pq.top() << "\n";  // 4
    return 0;
}

6. 空间配置器（Allocator）

空间配置器负责容器的内存分配与释放。它抽象了“对象构造/析构”与“内存分配/释放”，让容器的实现与内存管理解耦。默认使用 allocator<T>，底层调用 operator new 和 operator delete。

总结

STL 是 C++ 语言中最伟大的作品之一，它将常见的数据结构和算法封装成通用、高效、类型无关的库。接下来的几篇博客，我们将逐一深入学习 vector、list、string 等常见容器的底层原理和实际使用技巧。