容器体系结构

容器体系结构

STL 容器的整体分类

C++ STL 中的容器可以分为三大类：

容器类型	代表容器	简介
序列容器	vector, deque, list, array, forward_list	元素按插入顺序排列
有序关联容器	set, map, multiset, multimap	自动排序、基于平衡树
无序关联容器	unordered_map, unordered_set 等	基于哈希表实现，元素无序
容器适配器	stack, queue, priority_queue	基于已有容器封装出特定接口（限制行为）

序列容器（Sequence Containers）

代表容器：

• vector：动态数组，支持随机访问，尾部操作高效。
• deque：双端队列，两端插入删除都快。
• list：双向链表，适合频繁插入删除。
• forward_list：单向链表，更节省内存。
• array：固定大小的栈上数组。

特点：

• 元素按顺序排列，插入顺序决定位置。
• 一般支持：插入、删除、遍历、大小、比较。
• 接口统一，如 begin(), end(), push_back() 等。

容器适配器（Container Adapters）

容器适配器本质上是对已有序列容器的封装，提供特定功能的接口限制。

代表容器：

容器名称	底层通常使用	功能描述
stack	deque	后进先出（LIFO）
queue	deque	先进先出（FIFO）
priority_queue	vector	堆结构（大顶堆默认）

你无法遍历适配器中的元素，它只提供有限的接口如 push(), pop(), top() 等。

适配器本质：容器适配器是对底层容器功能的“裁剪与限制”，通过隐藏部分接口，模拟特定的数据结构行为。

对比

对比项	序列容器	容器适配器
定义	原生 STL 容器类型	基于已有容器封装的接口层
行为控制	支持插入、遍历、任意访问等	限制功能，如只能进/出栈顶
底层结构	自己实现内存与结构	借用其他容器（默认 deque/vector）
可遍历性	是	否
自由度	高	限制多
使用场景	灵活通用数据结构	模拟特定结构：栈、队列、堆

常见问题

1. stack 是如何实现的？能用 list 实现吗？
   • 默认是 deque，也可以换成 vector、list 作为底层容器（需满足接口要求）。
2. queue 和 deque 有啥区别？
   • queue 不能从前面插；deque 支持双向插入删除。
3. priority_queue 和 make_heap 有啥关系？
   • 它内部使用 make_heap、push_heap、pop_heap 实现堆行为。
4. 为什么适配器不能遍历？
   • 因为它刻意隐藏了底层容器的迭代器，防止用户破坏其行为模型（如先进先出、后进先出）。