一、STL总览与六大组件：容器、算法、迭代器、仿函数、适配器、分配器的概念与关系

说实话，STL 这玩意儿，我刚开始学的时候也觉得头大。六个组件，名字还都挺唬人。但用久了你会发现，它其实就是一套精心设计的积木。你想想看，写代码最烦什么？重复造轮子。STL 就是帮你把最常用的数据结构和算法都封装好了，你直接拿来拼装就行。

我个人习惯把 STL 比作一个工厂流水线。容器是仓库，算法是加工机器，迭代器是传送带，仿函数是加工指令，适配器是转换接头，分配器是电力系统。嗯，这个比喻可能不太严谨，但能帮你快速理解它们各自是干嘛的。

1.1 六大组件，各司其职

咱们一个一个来看。先列个表，心里有个谱：

组件 英文 一句话解释
容器 Container 装数据的柜子。比如 vector、list、map
算法 Algorithm 处理数据的工序。比如排序、查找、拷贝
迭代器 Iterator 连接容器和算法的指针。像传送带一样逐个访问数据
仿函数 Functor 行为像函数的对象。用来定制算法的具体操作
适配器 Adapter 接口转换器。把一种组件包装成另一种样子
分配器 Allocator 内存管理员。负责给容器分配和释放内存

你看，每个组件都有自己明确的职责。它们之间怎么配合呢？我画了一张图，帮你理清关系：

STL 六大组件关系图 容器 vector, list, map... 分配器 内存管理 迭代器 智能指针，遍历 算法 sort, find, copy... 仿函数 less, greater... 适配器 stack, queue... 图例 提供内存 产生迭代器 操作数据 定制行为 包装接口

这张图你看懂了吗？核心就一句话：容器提供数据，迭代器遍历数据，算法处理数据，仿函数定制算法，适配器转换接口，分配器管理内存。它们各干各的，又紧密配合。

1.2 容器：数据的家

容器说白了就是用来存东西的。STL 里容器分三类：

  • 序列式容器：数据排成一排。vector 是动态数组，list 是双向链表，deque 是双端队列。我项目中用得最多的是 vector，因为它内存连续，随机访问快。
  • 关联式容器：数据按 key 组织。set 和 map 底层是红黑树，查找快。unordered_set 和 unordered_map 底层是哈希表，更快。
  • 容器适配器：stack、queue、priority_queue。它们底层其实是用其他容器实现的，只是把接口包装了一下。

重点：容器只负责存数据，不负责处理数据。处理数据是算法的事。容器和算法之间怎么通信？靠迭代器。

1.3 迭代器：算法和容器的桥梁

迭代器是什么？你可以把它理解成一个智能指针。它知道怎么在容器里移动，也知道怎么拿到当前指向的数据。

我举个例子。你想用 std::sort 给 vector 排序，但 sort 并不知道 vector 内部是怎么存数据的。没关系，你给它两个迭代器——begin 和 end，它就知道从哪开始、到哪结束。

std::vector<int> vec = {3, 1, 4, 1, 5};
std::sort(vec.begin(), vec.end());  // 迭代器作为桥梁

迭代器有五种类型，按能力从弱到强：

  • 输入迭代器：只能读，不能写。比如从 cin 读取数据。
  • 输出迭代器：只能写，不能读。比如写入 cout。
  • 前向迭代器：可以读写，但只能往前走。比如 forward_list 的迭代器。
  • 双向迭代器：可以往前走，也可以往后走。比如 list 的迭代器。
  • 随机访问迭代器：可以跳来跳去，支持 +n、-n。比如 vector 的迭代器。

你想想看，为什么算法要依赖迭代器？因为这样算法就不用关心容器长什么样了。只要容器能提供合适的迭代器，算法就能工作。这就是泛型编程的精髓。

1.4 算法：通用的处理逻辑

STL 提供了上百种算法，覆盖了排序、查找、拷贝、变换、数值计算等常见操作。它们都定义在 <algorithm> 和 <numeric> 头文件里。

我常用的几个：

  • std::sort：排序，底层是快速排序+插入排序的混合。
  • std::find：线性查找，返回迭代器。
  • std::copy：拷贝一段数据到另一个容器。
  • std::transform：对每个元素执行一个操作，生成新序列。

算法不直接操作容器，而是通过迭代器来操作。这意味着同一个算法可以用于不同的容器。比如 std::find 既可以在 vector 里找，也可以在 list 里找。

小技巧：如果你需要自定义排序规则，可以给 sort 传一个仿函数。比如按字符串长度排序：std::sort(vec.begin(), vec.end(), [](const string& a, const string& b) { return a.size() < b.size(); });

1.5 仿函数：可调用的对象

仿函数，也叫函数对象，就是重载了 operator() 的类。它的实例可以像函数一样被调用。

为什么要用仿函数而不是普通函数？因为仿函数可以携带状态。比如你想统计大于某个阈值的元素个数，普通函数做不到，但仿函数可以。

struct GreaterThan {
    int threshold;
    GreaterThan(int t) : threshold(t) {}
    bool operator()(int x) const { return x > threshold; }
};

std::vector<int> data = {1, 5, 3, 8, 2};
int count = std::count_if(data.begin(), data.end(), GreaterThan(4));
// count = 2 (5 和 8)

STL 预定义了一些仿函数，比如 std::less、std::greater、std::plus 等。它们通常和算法配合使用。

1.6 适配器：换个马甲继续用

适配器的作用是接口转换。它不改变底层实现，只是把一种接口包装成另一种接口。

STL 里有三类适配器：

  • 容器适配器：stack、queue、priority_queue。它们底层默认用 deque 或 vector 实现，但只暴露有限的接口。
  • 迭代器适配器：比如反向迭代器 rbegin()、rend()，它把正向迭代器包装成反向的。
  • 函数适配器：比如 std::bind、std::not1，用来调整仿函数的行为。

我记得有一次项目里需要用一个栈，但要求能动态调整大小。我直接用 std::stack<int>，底层是 deque，完全满足需求。适配器让我省了不少事。

1.7 分配器：幕后的内存管家

分配器是最容易被忽略的组件。它负责给容器分配和释放内存。默认的分配器 std::allocator 直接调用 new 和 delete。

但你可以自定义分配器。比如你想用内存池来减少碎片，或者你想跟踪内存使用情况，都可以写一个自己的分配器。

// 自定义分配器示例（简化版）
template<typename T>
struct MyAllocator {
    T* allocate(size_t n) {
        std::cout << "Allocating " << n << " elements\n";
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }
    void deallocate(T* p, size_t n) {
        std::cout << "Deallocating " << n << " elements\n";
        ::operator delete(p);
    }
};

std::vector<int, MyAllocator<int>> vec;  // 使用自定义分配器

注意：自定义分配器需要满足 STL 的分配器要求，包括 rebind、construct、destroy 等接口。写起来有点繁琐，但性能收益可能很大。我曾经在嵌入式项目里用内存池分配器，把动态内存分配的开销降到了接近零。

1.8 六大组件如何协同工作

咱们来捋一遍完整的流程。假设你要对一个 vector 排序，并且按降序排列：

  1. 容器：vector 存储数据。
  2. 分配器：vector 内部用分配器申请内存。
  3. 迭代器：vec.begin() 和 vec.end() 提供遍历接口。
  4. 仿函数：std::greater<int> 定义降序规则。
  5. 算法：std::sort 通过迭代器访问数据，用仿函数比较大小。
  6. 适配器：如果想把 vector 当栈用，可以用 std::stack 适配器包装。

你看，六个组件各司其职，又环环相扣。这就是 STL 的设计哲学——高内聚、低耦合。每个组件只关心自己的事，通过标准接口与其他组件协作。

我个人觉得，理解这六大组件的关系，是掌握 STL 的第一步。后面咱们会逐个深入，看看每个组件的源码实现。你会发现，STL 的代码写得真漂亮，每一行都有它的道理。

嗯，今天就先聊到这儿。记住这张关系图，后面学起来会轻松很多。

可可精品资料库

← 上一章 📖 返回目录 下一章 →