Course: 斯坦福大学: C++标准库编程 | C++ Standard Library Programming

🎮 CS106L Lecture 3.1 — Sequence Containers

🏛 课程：Stanford CS106L — Standard C++ Programming Language

📍 主题：序列容器（Sequence Containers）

🎯 目标：理解 STL 容器体系结构、vector 与 deque 的工作机制、性能特征与使用场景。

🧭 课程定位

容器（Container）是 STL 的第一大支柱。

所有容器都体现了 “Generic Programming（泛型编程）” 的核心思想：

算法与数据结构的分离（Separation of Algorithms and Data Structures）

C++ 通过模板让算法与容器互相独立、却又完美协作。

本讲主要聚焦于「序列容器」，即具有顺序性的数据集合。

🏷 关键词速记

STL｜标准模板库

Container｜容器

Sequence｜序列

vector｜动态数组

deque｜双端队列

iterator｜迭代器

push_back / at()｜插入与安全访问

🎮 30 秒课程摘要

“容器是 C++ 世界中存放数据的房间。

你既可以用 vector 住在公寓，也可以用 deque 住在双门仓库。

不同的容器，不同的代价。”

📚 核心内容讲解

🧩 1️⃣ STL 的诞生与哲学

STL 的核心设计师 Alexander Stepanov（贝尔实验室）提出理念：

“Algorithms + Containers + Iterators = Generic Programming.”

STL 的三大核心组件：

1. 容器（Containers） — 存储数据
2. 迭代器（Iterators） — 访问数据
3. 算法（Algorithms） — 操作数据

📦 通用示例：

std::vector<int> v = {3, 1, 4, 1, 5};
std::sort(v.begin(), v.end());
for (int n : v)
    std::cout << n << " ";

算法与容器解耦：sort 不依赖容器类型，只要支持随机访问即可。

🧩 2️⃣ 容器的定义与分类

C++ STL 容器分为三大类：

本讲聚焦：Sequence Containers（序列容器）

🧩 3️⃣ std::vector — 动态数组

最常用的序列容器。

底层实现： 连续内存块 + 自动扩容。

📦 基本用法

std::vector<int> v;
v.push_back(10);
v.push_back(20);
std::cout << v[0] << " " << v.at(1);

📦 越界风险：

std::vector<int> v = {1, 2, 3};
std::cout << v[5];     // 未定义行为！
std::cout << v.at(5);  // 抛出 std::out_of_range 异常

口诀： “生产用 at()，竞赛用 []。”

📦 容量与扩容机制

vector 会自动分配更大内存（通常翻倍增长），并移动旧元素。

v.reserve(1000);  // 预分配，避免频繁重分配

capacity() ≠ size()：前者是分配的空间，后者是实际元素数。

🧩 4️⃣ std::deque — 双端队列

deque（Double-ended Queue）支持在前后两端插入删除。

📦 用法

std::deque<int> dq;
dq.push_back(1);
dq.push_front(0);
std::cout << dq.front() << " " << dq.back();

底层原理：

• 非连续内存块（分段存储）
• 内部维护一组指针块（blocks）
• 允许高效前后插入（O(1) amortized）

⚔️ vector vs deque 性能对比

📦 性能实验示例：

const int N = 1e6;
std::vector<int> v;
for (int i=0; i<N; ++i) v.push_back(i);

std::deque<int> d;
for (int i=0; i<N; ++i) d.push_back(i);

结论：

• vector 写入速度略快（缓存友好）
• deque 插入前端更高效
• deque 更适合需要前后弹入的队列结构

🧩 5️⃣ STL 的设计哲学：信任与责任

“C++ 信任你能控制一切，也信任你能承担后果。”

例子：

std::vector<int> v = {1, 2, 3};
std::cout << v[100];  // ❌ 不检查，程序可能崩溃

C++ 没有强制保护机制，而是提供：

• 安全接口：at()
• 高效接口：[]

你可以决定用哪一个，这就是 C++ 的自由与责任。

🧠 STL 精神总结

📜 教师原话：

“STL 并不假设你会犯错，但它给你犯错的自由。”

🧠 记忆口诀

“容器分三门，序列打先锋；

vector 连续快，deque 双端行；

push_back 常用，at() 保命名。”

🧪 实践练习

✅ 练习 1：容器性能对比

写程序测试 vector 与 deque 的插入时间。

✅ 练习 2：安全访问函数

用 try...catch 捕获 v.at(5) 的越界异常。

✅ 练习 3：模拟任务队列

用 deque 实现一个任务系统，支持 push_front() 添加高优先级任务。

🪄 创作与工程建议

• 在游戏引擎或实时系统中，首选 vector（CPU cache 友好）。
• 需频繁前插的队列结构 → 用 deque。
• 若需稳定迭代器 → 考虑 list 或 deque。
• 生产环境务必使用 .at() 或 std::span。
• 预分配容量可显著提高性能（reserve()）。

✅ 小结表

“选容器，就像选工具：

锤子打钉子，螺丝得用螺丝刀。”