C++_STL_vector_deque_stack详解
·
C++ STL 容器详解：vector、deque 与 stack 完全指南
关键词： C++ STL、标准模板库、vector 向量容器、deque 双端队列、stack 栈容器、序列式容器、容器适配器、动态数组、LIFO、C++ 数据结构
STL 标准模板库概述
STL 是 Standard Template Library（标准模板库）的简称，由惠普实验室（Hewlett-Packard Labs）开发的一系列软件的统称。它由 Alexander Stepanov、Meng Lee 和 David R. Musser 在惠普实验室工作期间共同设计开发。
从根本上说，STL 是一些**容器（Container）的集合，包含 list、vector、set、map 等；STL 同时也是算法（Algorithm）**和其他组件的集合。这里的"容器"和"算法"凝聚了世界上众多优秀开发者多年来的智慧结晶。
STL 的核心目标： 标准化组件，让开发者无需重复造轮子，直接复用现成的高质量组件。STL 是 C++ 标准库的一部分，无需额外安装任何库文件。
STL 版本众多，常见的有 HP STL、PJ STL、SGI STL 等。
在 C++ 标准中，STL 被组织为以下 13 个头文件：
| 头文件 | 功能领域 |
|---|---|
<algorithm> |
通用算法（排序、查找、遍历等） |
<deque> |
双端队列容器 |
<functional> |
函数对象与绑定器 |
<iterator> |
迭代器相关工具 |
<vector> |
向量（动态数组）容器 |
<list> |
双向链表容器 |
<map> |
关联容器（键值对映射） |
<memory> |
智能指针与内存管理 |
<numeric> |
数值算法 |
<queue> |
队列与优先级队列容器适配器 |
<set> |
集合容器 |
<stack> |
栈容器适配器 |
<utility> |
通用工具（pair、move 等） |
一、vector 向量容器
1.1 什么是 vector？
序列式容器 vector（向量）：连续存储的元素，定义在 <vector> 头文件中。
vector 容器是 STL 中最常用的容器之一，它和 array 容器非常类似，都可以看作是对 C++ 普通数组的升级版。
vector 与 array 的关键区别：
| 特性 | array |
vector |
|---|---|---|
| 数组类型 | 静态数组（容量固定） | 动态数组（容量可变） |
| 内存管理 | 手动管理 | 自动调整，无需人工干预 |
| 元素插入/删除 | 不支持 | 支持动态增减 |
vector 常被称为向量容器，该容器的核心性能特征如下：
- 尾部操作： 在尾部插入或删除元素，时间复杂度为 O(1)（常数时间）
- 头部/中部操作： 在头部或中部插入/删除元素，需要移动后续元素，时间复杂度为 O(n)（线性时间）
1.2 创建 vector 容器的多种方式
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 方式1：创建存储 double 类型的空 vector 容器
vector<double> v1;
// 方式2：创建 int 类型的 vector 容器，并初始化元素
vector<int> v2{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// 方式3：创建 vector 容器，指定元素个数为 50（默认值初始化）
vector<int> v3(50);
// 方式4：创建 vector 容器，拥有 10 个值为 'A' 的字符
vector<char> v4(10, 'A');
// 方式5：拷贝构造——将 v4 赋值给 v5
vector<char> v5(v4);
// 方式6：通过数组指针范围初始化
int a[] = { 10, 20, 30 };
vector<int> v6(a, a + 2); // v6 将保存 {10, 20}
// 方式7：通过另一个容器的迭代器范围初始化
vector<int> v7{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
vector<int> v8(begin(v7), begin(v7) + 3); // v8 将保存 {1, 2, 3}
return 0;
}
1.3 vector 容器基本操作示例
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 定义一个 vector 字符容器
vector<char> v1;
// 向容器尾部依次添加字符 "STLTEMPLATE"
v1.push_back('S');
v1.push_back('T');
v1.push_back('L');
v1.push_back('T');
v1.push_back('E');
v1.push_back('M');
v1.push_back('P');
v1.push_back('L');
v1.push_back('A');
v1.push_back('T');
v1.push_back('E');
// 输出容器 v1 的元素个数
cout << "元素个数为：" << v1.size() << endl;
// 遍历容器（使用迭代器）
cout << "\n输出 v1 容器中的元素:\n";
for (auto i = v1.begin(); i < v1.end(); i++) {
cout << " " << *i << " ";
}
/****************************************************************/
// 在头部位置插入数据元素
v1.insert(v1.begin(), 'V');
// 遍历容器
cout << "\n输出 v1 容器中的元素:\n";
for (auto i = v1.begin(); i < v1.end(); i++) {
cout << " " << *i << " ";
}
/****************************************************************/
// 在尾部位置插入数据元素
v1.insert(v1.end(), 'I');
// 遍历容器
cout << "\n输出 v1 容器中的元素:\n";
for (auto i = v1.begin(); i < v1.end(); i++) {
cout << " " << *i << " ";
}
cout << endl;
// 通过 at() 访问首元素（带边界检查）
cout << "输出 v1 容器首个元素为：" << v1.at(0) << endl;
return 0;
}
1.4 vector 成员函数速查
vector容器成员函数非常丰富，推荐直接查阅官方文档：
二、deque 双端队列容器
2.1 什么是 deque？
deque 是 double-ended queue（双端队列）的缩写，又称双端队列容器。
前面已经介绍过 vector 容器。deque 容器和 vector 容器有很多相似之处：
deque同样擅长在序列尾部添加或删除元素，时间复杂度为 O(1)deque同样不擅长在序列中部添加或删除元素deque也可以根据需要动态修改自身的容量和大小
deque 与 vector 的关键区别：
| 特性 | vector |
deque |
|---|---|---|
| 尾部操作（增/删） | O(1) | O(1) |
| 头部操作（增/删） | O(n) | O(1) |
| 中部操作（增/删） | O(n) | O(n) |
| 内存连续性 | 连续存储 | 不保证连续 |
| 动态调整容量 | ✅ | ✅ |
🎯 使用建议： 当需要向序列两端频繁添加或删除元素时，应首选
deque容器。
尤其重要的是，deque 容器中存储的元素不能保证所有元素都存储在连续的内存空间中，这是它与 vector 的重要区别之一。
2.2 创建 deque 容器
#include <iostream>
#include <deque>
using namespace std;
int main() {
// 方式1：创建空的 deque 容器，没有任何数据元素
deque<int> d1;
// 方式2：创建 deque 容器，指定 50 个元素（默认值初始化）
deque<int> d2(50);
// 方式3：创建具有 9 个元素的 deque 容器，且全部初始化为 888
deque<int> d3(9, 888);
// 方式4：容器之间直接赋值（拷贝构造）
deque<int> d4(10);
deque<int> d5(d4);
return 0;
}
2.3 deque 增删操作示例
#include <iostream>
#include <deque>
using namespace std;
int main() {
// 定义空的 deque 容器
deque<int> d1;
// 向容器尾部依次插入数字 1~10
d1.push_back(1);
d1.push_back(2);
d1.push_back(3);
d1.push_back(4);
d1.push_back(5);
d1.push_back(6);
d1.push_back(7);
d1.push_back(8);
d1.push_back(9);
d1.push_back(10);
// 输出 d1 的元素个数
cout << "输出 d1 容器元素的个数为：" << d1.size() << endl;
// 向 d1 容器尾部添加元素 888
d1.push_back(888);
cout << "输出 d1 容器元素的所有值：" << endl;
for (auto i = d1.begin(); i < d1.end(); i++) {
cout << " " << *i << " ";
}
cout << endl << endl;
// 删除容器头部的数据元素
d1.pop_front();
cout << "输出 d1 容器元素的所有值：" << endl;
for (auto i = d1.begin(); i < d1.end(); i++) {
cout << " " << *i << " ";
}
cout << endl << endl;
// 删除容器尾部的数据元素
d1.pop_back();
cout << "输出 d1 容器元素的所有值：" << endl;
for (auto i = d1.begin(); i < d1.end(); i++) {
cout << " " << *i << " ";
}
cout << endl << endl;
return 0;
}
2.4 deque 成员函数速查
deque容器成员函数非常丰富，推荐直接查阅官方文档：
三、stack 栈容器适配器
3.1 什么是容器适配器？什么是 stack？
容器适配器是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了不同风格的功能接口。之所以称为"适配器"，是因为它通过适配（包装）现有容器的接口来提供新的功能语义。
stack<T> 容器适配器中的数据以 LIFO（Last In, First Out，后进先出） 的方式组织，这与日常生活中的很多场景类似：
- 自助餐厅中堆叠的盘子（后放的先被取走）
- 箱子中堆叠的书本（最上面一本最先被拿到）
- 弹夹中的子弹（后压入的先射出）
stack 的核心限制： 只能访问栈顶（top）元素；只有在移除栈顶元素后，才能访问其下方的元素。
3.2 创建与使用 stack 容器
#include <iostream>
#include <stack>
#include <list>
using namespace std;
int main() {
// 创建一个 stack 容器适配器，底层使用 list 作为存储容器
list<int> LS{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };
stack<int, list<int>> mystack(LS);
// 查询 mystack 存储元素的个数
cout << "栈容器数据元素个数为：" << mystack.size() << endl;
// 输出栈容器数据元素的值（LIFO 顺序：从栈顶到栈底）
cout << "输出栈容器数据元素的值：" << endl;
while (!mystack.empty()) { // empty() 为空返回 true，否则返回 false
cout << mystack.top() << " "; // top()：访问栈顶元素
mystack.pop(); // pop()：弹出栈顶元素
}
return 0;
}
3.3 stack 成员函数速查
stack容器成员函数推荐直接查阅官方文档：
三容器对比总结
| 对比维度 | vector |
deque |
stack |
|---|---|---|---|
| 类型 | 序列式容器 | 序列式容器 | 容器适配器 |
| 数据结构 | 动态数组 | 双端队列 | LIFO 栈 |
| 内存布局 | 连续存储 | 分段连续（不保证整体连续） | 取决于底层容器 |
| 尾部插入 | O(1) | O(1) | O(1)（push） |
| 尾部删除 | O(1) | O(1) | O(1)（pop） |
| 头部插入 | O(n) | O(1) | 不可用 |
| 头部删除 | O(n) | O(1) | 不可用 |
| 随机访问 | O(1) | O(1) | 不可用 |
| 中间操作 | O(n) | O(n) | 不可用 |
| 头文件 | <vector> |
<deque> |
<stack> |
| 适用场景 | 频繁尾部操作 + 随机访问 | 频繁两端操作 | 后进先出场景 |
选择建议：
- 需要动态数组 + 随机访问 →
vector- 需要双端高效插入/删除 →
deque- 需要 LIFO 约束（如递归模拟、括号匹配、表达式求值） →
stack
更多推荐
6
0- 0
已为社区贡献11条内容
所有评论(0)