第18章 标准模板库(STL)容器

想象一下你的衣柜：如果你把衣服一件件叠好摞起来，想拿最底下那件就得把上面的都搬开，这就像vector；如果你把衣服用衣架挂在横杆上，可以随意取下任何一件而不影响其他，这就像list。在C++中，STL容器就是用来存储和管理一组同类型数据的“智能衣柜”，它封装了底层数据结构，提供了统一、安全、高效的访问接口。

从第17章的模板基础出发，STL容器是模板最经典的应用。你不用再为整型数组、字符串数组分别写管理代码，一个vector<T>就能通吃。实际项目中，我见过太多人从零手写链表导致内存泄漏，而STL容器经过几十年工业级验证，性能稳定，直接拿来用是明智的选择。

容器家族图谱：序列 vs. 关联

选择哪个容器，首先看你的数据访问模式。STL容器主要分为两大阵营：序列容器（按插入顺序存储）和关联容器（按特定顺序快速查找）。

这张图揭示了容器的继承关系。序列容器关心“位置”，关联容器关心“钥匙”。下面这个表格帮你快速决策：

vector：你的主力“动态数组”

vector就像会自动扩容的数组。你声明时不用指定固定大小，它会根据需要动态增长。但这里有个关键细节：增长是有代价的。

// 基本使用
#include <vector>
#include <iostream>

int main() {
    // 1. 创建
    std::vector<int> scores; // 空vector
    std::vector<double> prices(100); // 100个0.0
    std::vector<std::string> names = {"Alice", "Bob"};

    // 2. 添加元素
    scores.push_back(95); // 尾部添加，最常用
    scores.insert(scores.begin(), 80); // 头部插入，性能差

    // 3. 访问元素
    int firstScore = scores[0]; // 不检查越界，速度快
    int secondScore = scores.at(1); // 检查越界，越界抛异常

    // 4. 容量管理
    std::cout << "大小: " << scores.size() << ", 容量: " << scores.capacity() << "\n";
    scores.reserve(1000); // 预分配空间，避免多次扩容

    return 0;
}

size()是当前元素个数，capacity()是实际分配的内存能容纳的元素个数。当size == capacity时再添加元素，vector会重新分配一块更大的内存（通常是翻倍），然后把所有元素搬过去。这个“搬家”操作会使所有迭代器、指针、引用失效。

map与set：高效的“查找表”

如果说vector是编号储物柜，那map就是带标签的储物柜。你通过唯一的“键”（key）来存取“值”（value）。set是map的简化版，只存储键，用于快速判断某个元素是否存在。

// map的核心操作
#include <map>
#include <string>

int main() {
    std::map<std::string, int> studentScores;

    // 插入数据的三种方式
    studentScores["1001"] = 95; // 如果"1001"不存在，会创建并赋值
    studentScores.insert({"1002", 88}); // C++11风格
    studentScores.emplace("1003", 92); // 直接构造，效率更高

    // 查找与访问
    auto it = studentScores.find("1001");
    if (it != studentScores.end()) {
        std::cout << "成绩: " << it->second << "\n"; // it->first是键，it->second是值
    }

    // 遍历（自动按键排序）
    for (const auto& pair : studentScores) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }

    return 0;
}

性能对比与实战选型

光看理论复杂度不够，我们看一组实测数据（在Intel i7-9700K上，处理100万个int元素）：

数据说明了一切：vector在顺序访问和内存效率上碾压其他容器。unordered_map查找最快，但迭代顺序不确定。实际开发中，我遵循这个决策流程：