C / C++ / 系统课时

容器为什么有不同类型

容器为什么有不同类型

STL 没有设计一个能够包办所有场景的“万能容器”,因为随机访问、频繁插入、有序遍历和按键快速查找对底层结构的要求并不相同。选择容器的关键不是记住名称,而是先判断程序最频繁执行什么操作。

学习目标

  • 区分顺序容器、关联容器和无序关联容器的核心特点
  • 理解不同容器为何会有不同的时间复杂度和数据约束
  • 能根据访问、插入、排序和按键查找需求选择容器类型

不同需求需要不同数据结构

如果数据主要按加入顺序保存,并且经常通过位置访问,连续存储通常很有优势。如果希望元素天然按键排序,就需要能够维护顺序的数据结构。如果只关心根据键尽快找到值,则可以用哈希结构换取平均常数时间的查找。

这些目标无法同时做到最优。例如 std::vector 的随机访问很快,但在中间插入元素通常需要移动后续数据;std::set 能自动维持有序和唯一性,却不能像数组一样通过下标直接访问。

三类容器解决的问题

类型 典型容器 主要特点 常见场景
顺序容器 vector、deque、list 主要按元素位置或插入顺序组织 保存列表、序列、队列式数据
关联容器 set、map 按键维护有序结构,典型查找复杂度为 O(log⁡n)O(\log n) 需要有序遍历、范围查询或唯一键
无序关联容器 unordered_set、unordered_map 基于哈希组织,平均查找复杂度为 O(1)O(1) 主要根据键快速查询,不要求有序

这里的复杂度描述的是典型操作,而不是整个容器只有一种复杂度。例如 vector 尾部追加通常是摊还 O(1)O(1),但在中间插入通常是 O(n)O(n);哈希容器平均查询为 O(1)O(1),最坏情况下仍可能退化到 O(n)O(n)。

用相同数据观察差异

下面分别使用 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: 90

vector 保留了插入顺序和重复元素;set 自动去除了重复值并按升序遍历;unordered_map 则把字符串键映射到分数,适合通过键直接查询。

先看操作模式,再选容器

选择容器时,可以先问几个具体问题:是否需要通过下标频繁访问?是否必须保持键有序?是否要求键唯一?是否主要根据键查询?是否经常在序列中间插入或删除?这些问题比“哪个容器性能最好”更有意义。

容器选择本质上是在访问方式、插入删除成本、内存布局以及顺序要求之间做取舍。不存在对所有操作都最优的类型,正确做法是让最常见、最关键的操作匹配合适的数据结构。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

容器为什么有不同类型

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通