STL 容器

本课属于 Coddy C++ 学习旅程的“面向对象编程”单元。第 71 课，共 104 课。

STL 容器是用于存储和组织对象集合的模板类。每种容器类型都针对不同的访问模式和操作进行了优化。为你的需求选择合适的容器，可以显著影响程序的性能。

序列容器会按特定顺序保存元素：

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // 动态数组，支持快速随机访问
vec.push_back(4);                   // 添加到末尾：均摊 O(1)
int x = vec[2];                     // 通过索引访问：O(1)

std::list<int> lst = {1, 2, 3};    // 双向链表
lst.push_front(0);                  // 添加到开头：O(1)
lst.push_back(4);                   // 添加到末尾：O(1)

关联容器会按排序顺序存储元素，以便快速查找：

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // 不重复且已排序的元素：{1, 3, 4}
s.insert(2);                        // 插入：O(log n)
bool found = s.count(3);            // 检查是否存在：O(log n)

std::map<std::string, int> ages;   // 键值对，按键排序
ages["Alice"] = 25;                 // 插入或更新：O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // 访问：O(log n)

无序容器使用哈希表，平均查找速度更快：

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // 插入：平均 O(1)
scores["player2"] = 200;
std::cout << scores["player1"];    // 访问：平均 O(1)

需要快速随机访问时使用 vector，需要频繁在中间插入时使用 list，需要有序数据时使用 map/set，查找速度至关重要且不需要考虑顺序时使用 unordered_map。

挑战

简单

让我们构建一个学生成绩管理系统，演示不同的 STL 容器如何各司其职。你将使用多种容器类型来高效地组织学生数据，并为每项任务选择合适的容器。

你将创建两个文件来组织代码：

GradeManager.h：定义一个使用多种 STL 容器管理学生信息的 GradeManager 类。
你的类应使用：
- 一个 std::vector<std::string>，按照添加顺序存储学生姓名
- 一个 std::map<std::string, int>，将每位学生的姓名与其成绩关联起来
- 一个 std::set<int>，跟踪所有已分配且不重复的成绩
实现以下方法：
- addStudent(const std::string& name, int grade)：将一名学生及其成绩添加到全部三个容器中
- getGrade(const std::string& name)：使用 map 返回指定学生姓名对应的成绩
- printRoster()：按照添加顺序（从 vector 中）打印所有学生姓名，每个姓名单独占一行
- printGrades()：按字母顺序打印所有学生及其成绩（map 会自动处理排序），每行的格式为 name: grade
- printUniqueGrades()：按升序打印所有不重复的成绩（set 会处理排序），成绩之间用空格分隔，并在末尾换行
main.cpp：读取输入，并演示每种容器类型如何发挥不同作用。
读取 6 项输入（每项单独占一行）：
1. 第一位学生的姓名
2. 第一位学生的成绩（整数）
3. 第二位学生的姓名
4. 第二位学生的成绩（整数）
5. 第三位学生的姓名
6. 第三位学生的成绩（整数）
创建一个 GradeManager，并添加全部三位学生。然后演示不同容器的行为：
1. 打印 Roster (insertion order):，然后调用 printRoster()
2. 打印 Grades (alphabetical):，然后调用 printGrades()
3. 打印 Unique grades:，然后调用 printUniqueGrades()
4. 查找第二位学生的成绩，并打印 <name>'s grade: <grade>

例如，输入 Charlie、85、Alice、90、Bob、85 时：

Roster (insertion order):
Charlie
Alice
Bob
Grades (alphabetical):
Alice: 90
Bob: 85
Charlie: 85
Unique grades:
85 90 
Alice's grade: 90

注意，vector 会保留插入顺序（Charlie、Alice、Bob），map 会按键自动排序（Alice、Bob、Charlie），而 set 只存储按顺序排列的不重复值（85 只出现一次，而不是两次）。每种容器类型都擅长处理不同的任务！

亲手试试

#include <iostream>
#include <string>
#include "GradeManager.h"

using namespace std;

int main() {
    // 读取三名学生的输入
    string name1, name2, name3;
    int grade1, grade2, grade3;
    
    cin >> name1;
    cin >> grade1;
    cin >> name2;
    cin >> grade2;
    cin >> name3;
    cin >> grade3;
    
    // TODO: 创建一个 GradeManager 对象
    
    // TODO: 将三名学生都添加到 GradeManager 中
    
    // TODO: 打印 "Roster (insertion order):" 并调用 printRoster()
    
    // TODO: 打印 "Grades (alphabetical):" 并调用 printGrades()
    
    // TODO: 打印 "Unique grades:" 并调用 printUniqueGrades()
    
    // TODO: 查询第二名学生的成绩，并打印 "<name>'s grade: <grade>"
    
    return 0;
}

自我测试

这节课包含一个小测验。开始学习即可作答，并记录你的进度。

面向对象编程中的所有课

自己练习： C++ 在线编译器