C / C++ / 系统课时
容器为什么有不同类型
容器为什么有不同类型
STL 没有设计一个能够包办所有场景的“万能容器”,因为随机访问、频繁插入、有序遍历和按键快速查找对底层结构的要求并不相同。选择容器的关键不是记住名称,而是先判断程序最频繁执行什么操作。
学习目标
- 区分顺序容器、关联容器和无序关联容器的核心特点
- 理解不同容器为何会有不同的时间复杂度和数据约束
- 能根据访问、插入、排序和按键查找需求选择容器类型
不同需求需要不同数据结构
如果数据主要按加入顺序保存,并且经常通过位置访问,连续存储通常很有优势。如果希望元素天然按键排序,就需要能够维护顺序的数据结构。如果只关心根据键尽快找到值,则可以用哈希结构换取平均常数时间的查找。
这些目标无法同时做到最优。例如 std::vector 的随机访问很快,但在中间插入元素通常需要移动后续数据;std::set 能自动维持有序和唯一性,却不能像数组一样通过下标直接访问。
三类容器解决的问题
| 类型 | 典型容器 | 主要特点 | 常见场景 |
|---|---|---|---|
| 顺序容器 | vector、deque、list |
主要按元素位置或插入顺序组织 | 保存列表、序列、队列式数据 |
| 关联容器 | set、map |
按键维护有序结构,典型查找复杂度为 | 需要有序遍历、范围查询或唯一键 |
| 无序关联容器 | unordered_set、unordered_map |
基于哈希组织,平均查找复杂度为 | 主要根据键快速查询,不要求有序 |
这里的复杂度描述的是典型操作,而不是整个容器只有一种复杂度。例如 vector 尾部追加通常是摊还 ,但在中间插入通常是 ;哈希容器平均查询为 ,最坏情况下仍可能退化到 。
用相同数据观察差异
下面分别使用 vector、set 和 unordered_map。程序刻意让三个容器承担不同任务:保留原始序列、维护唯一有序元素,以及按照名字查找分数。
cpp
#include <iostream>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
int main() {
std::vector<int> sequence{3, 1, 3, 2};
std::set<int> unique_sorted(sequence.begin(), sequence.end());
std::unordered_map<std::string, int> scores{
{"alice", 90},
{"bob", 85}
};
std::cout << "vector:";
for (int value : sequence) {
std::cout << ' ' << value;
}
std::cout << '\n';
// set 会去重,并按照键的顺序遍历。
std::cout << "set:";
for (int value : unique_sorted) {
std::cout << ' ' << value;
}
std::cout << '\n';
std::cout << "alice score: " << scores.at("alice") << '\n';
}预期输出:
text
vector: 3 1 3 2
set: 1 2 3
alice score: 90vector 保留了插入顺序和重复元素;set 自动去除了重复值并按升序遍历;unordered_map 则把字符串键映射到分数,适合通过键直接查询。
先看操作模式,再选容器
选择容器时,可以先问几个具体问题:是否需要通过下标频繁访问?是否必须保持键有序?是否要求键唯一?是否主要根据键查询?是否经常在序列中间插入或删除?这些问题比“哪个容器性能最好”更有意义。
容器选择本质上是在访问方式、插入删除成本、内存布局以及顺序要求之间做取舍。不存在对所有操作都最优的类型,正确做法是让最常见、最关键的操作匹配合适的数据结构。
按自己的节奏,确认真正理解。