STL顺序容器如何为？
摘要：STL基本概念 什么是STL STL（Standard Template Library，标准模板库）是惠普实验室开发的一系列软件组件统称，设计目标是提升代码重用性。 为建立数据结构和算法的统一标准，降低组件间耦合度，提升独立性、弹性和交互
STL基本概念
什么是STL
STL（Standard Template Library，标准模板库）是惠普实验室开发的一系列软件组件统称，设计目标是提升代码重用性。
为建立数据结构和算法的统一标准，降低组件间耦合度，提升独立性、弹性和交互操作性，STL应运而生。其核心优势是采用模板类/模板函数，相比传统函数库/类库提供了更强大的代码复用能力。
STL三大核心组件
STL从广义上分为三大核心组件，三者通过迭代器无缝衔接：
容器（Container）：封装特定数据结构，用于存储和管理数据（如数组、链表、队列）
算法（Algorithm）：用于操作容器中数据的函数（如排序、查找、遍历）
迭代器（Iterator）：连接容器和算法的桥梁，提供统一的方式访问容器元素
容器的概念
容器是实现特定算法的数据结构集合，具备以下特点：
可容纳任意类型数据（文件、进程、自定义类等）
提供统一操作接口（如赋值、清除、插入、删除）
屏蔽内部实现细节，用户无需关注容器逻辑，专注于数据处理
容器的分类
容器类型
核心特征
典型示例
内部结构
顺序容器
元素存储位置取决于存取顺序，与元素本身属性无关
array/vector、list、deque
数组、链表
关联容器
元素存储位置取决于元素本身属性（大小关系/键值对应）
set、map
平衡二叉树
无序关联容器
采用Hash结构，极致提升检索速度
unordered_set、unordered_map
哈希表
容器适配器
对顺序容器封装特定接口，转换为专用容器
stack（栈）、queue（队列）
基于vector/deque/list
迭代器
概念与作用
迭代器是广义指针，是高度抽象的容器元素指涉器，核心作用是让C++程序通过统一方式处理不同数据结构。
使用迭代器的优势
算法独立于容器内元素类型（模板特性）和容器本身类型（迭代器特性）
支持继承扩展，可构建输入/输出迭代器、正向/反向迭代器、随机访问迭代器等
屏蔽指涉对象细节，无需关心元素类型即可用指针语法操作
核心接口与区间特性
所有迭代器均提供 begin() 和 end() 接口：
begin()：指向容器第一个元素
end()：指向容器最后一个元素的下一个位置（半开半闭区间 [begin, end)）
迭代器类型说明
迭代器类型
特点
支持的容器
正向迭代器
从前往后遍历，支持 ++
所有容器
反向迭代器
从后往前遍历，支持 ++（实际移动方向相反），接口为 rbegin()/rend()
vector、list、deque等
常量迭代器
仅可读，不可修改元素，前缀为 c（如 crbegin()）
所有容器
随机访问迭代器
支持跳跃访问（+n/-n）、比较操作（</>）
vector、array、deque
双向迭代器
支持前后移动（++/--），不支持跳跃
list、forward_list（仅正向）
迭代器遍历示例（vector）
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
// 1. 数组下标遍历（仅支持随机访问容器）
for(int i=0; i<v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
// 2. 正向迭代器遍历
for(vector<int>::iterator it=v.begin(); it!=v.end(); it++) {
cout << *it << " ";
}
cout << endl;
// 3. 反向迭代器遍历
for(vector<int>::reverse_iterator it=v.rbegin(); it!=v.rend(); it++) {
cout << *it << " ";
}
cout << endl;
return 0;
}
顺序容器详解
顺序容器的核心特征：元素存储位置由存取顺序决定，支持在头部、尾部或中间位置进行元素操作。
数组容器
静态数组 array（C++11起）
核心特性
容量固定，初始化后大小不可修改（与C语言数组类似）
不自动退化为指针，支持容器化操作（如 swap()、size()）
需显式指定元素类型和容量
接口规范
#include <array>
template<typename T, size_t N> // T：元素类型，N：固定容量
struct array;
核心接口表格
接口名
功能描述
备注
at(size_t i)
返回下标i的元素
越界抛出 out_of_range 异常
operator[](i)
返回下标i的元素
越界行为未定义（效率更高）
front()
返回第一个元素
容器非空时使用
back()
返回最后一个元素
容器非空时使用
begin()/end()
返回正向迭代器（起始/末尾）
支持遍历
rbegin()/rend()
返回反向迭代器（起始/末尾）
从后往前遍历
crbegin()/crend()
返回常量反向迭代器
不可修改元素（const 特性）
size()/max_size()
返回元素个数
两者结果相同（容量固定）
swap(array& other)
交换两个数组元素
要求类型和容量完全一致
fill(const T& val)
用val填充整个数组
覆盖所有元素
empty()
判断容器是否为空
仅当容量N=0时返回true（关键！）
完整示例代码
#include <iostream>
#include <array>
using namespace std;
int main(int argc, char const *argv[]) {
// 1. 创建并初始化静态数组
array<int, 10> arr{1,2,3,4,5,6,7,8,9,10};
array<int, 10> arr1{11,22,33,44,55,66,77,88,99,0};
// 2. 获取数组大小
cout << "数组大小：" << arr.size() << endl;
cout << "最大容量：" << arr.max_size() << endl;
cout << "++++++++++++++++++++" << endl;
// 3. 下标访问（安全方式）
for (int i = 0; i < arr.size() ; i++) {
cout << arr.at(i) << " ";
}
cout << "\n++++++++++++++++++++" << endl;
// 4. 迭代器遍历
for (array<int,10>::iterator it = arr.begin(); it != arr.end(); it++) {
cout << *it << " ";
}
cout << "\n++++++++++++++++++++" << endl;
// 5. 获取首尾元素
cout << "第一个元素：" << arr.front() << endl;
cout << "最后一个元素：" << arr.back() << endl;
cout << "++++++++++++++++++++" << endl;
// 6. 交换两个数组
arr.swap(arr1);
cout << "交换后arr元素：";
for (auto it = arr.begin(); it != arr.end(); it++) {
cout << *it << " ";
}
cout << "\n++++++++++++++++++++" << endl;
// 7. 填充数组
arr.fill(666);
cout << "填充后反向遍历：";
for (auto it = arr.rbegin(); it != arr.rend(); it++) {
cout << *it << " ";
}
cout << "\n++++++++++++++++++++" << endl;
// 8. 空判断（关键示例）
array<int, 32> arr2; // 未初始化，但容量32≠0
if (arr2.empty()) {
cout << "数组为空.." << endl;
} else {
cout << "数组不为空.." << endl; // 实际输出此句
}
return 0;
}
注意事项
常量迭代器（如 crbegin()）返回的元素不可修改，否则编译报错
empty() 仅判断容量是否为0，而非元素是否初始化
不支持动态扩容，适合数据量固定的场景
动态数组 vector
核心特性
容量动态变化（按需扩容/收缩）
元素连续存储，支持随机访问（v[i]）
内存紧凑，尾部插入/删除效率高，中间插入/删除效率低（需移动元素）
接口规范
#include <vector>
template<typename T,
typename Allocator = std::allocator<T> // 分配器（默认提供）
> class vector;
核心接口表格
接口名
功能描述
备注
push_back(const T& val)
在尾部追加元素
触发扩容时可能导致迭代器失效
pop_back()
移除尾部元素
不触发扩容，效率高
capacity()
返回当前总容量（已分配内存可存储的元素数）
大于等于 size()
size()
返回当前元素个数
实际存储的元素数量
begin()/end()
返回正向迭代器
支持随机访问（it + n）
rbegin()/rend()
返回反向迭代器
从后往前遍历
swap(vector& other)
交换两个vector元素
类型需一致
clear()
清空所有元素
size() 变为0，但 capacity() 不变
reserve(size_t n)
预分配n个元素的内存
避免频繁扩容，提升性能
resize(size_t n)
调整元素个数为n
超出原size时补默认值，不足时截断
基础示例代码
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
vector<int> v; // 空vector，初始capacity=0
// 尾部插入元素
v.push_back(1);
v.push_back(2);
v.push_back(3);
cout << "元素个数：" << v.size() << endl; // 输出3
cout << "当前容量：" << v.capacity() << endl; // 输出4（不同编译器可能不同，通常翻倍扩容）
// 遍历元素（三种方式）
// 1. 下标遍历
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
// 2. 迭代器遍历
for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
cout << *it << " ";
}
cout << endl;
// 3. 范围for遍历（C++11起）
for (int val : v) {
cout << val << " ";
}
cout << endl;
// 交换vector
vector<int> w{4,5,6};
v.swap(w);
cout << "交换后v的元素：";
for (int val : v) {
cout << val << " ";
}
cout << endl;
return 0;
}
拓展：vector扩容机制
扩容逻辑：当 size() == capacity() 时，触发扩容，通常是翻倍扩容（如capacity从4→8→16...）
扩容过程：分配新内存 → 拷贝原元素到新内存 → 释放原内存
影响：扩容后原迭代器、指针、引用会失效（指向已释放内存）
优化方案：提前用 reserve(n) 预分配足够内存，避免频繁扩容
双端队列 deque
核心特性
双端操作：支持队头/队尾的插入、删除操作
支持随机访问（dq[i]），但内存布局非连续（效率低于vector）
无需扩容：采用分段内存存储，插入元素时按需分配新段
接口规范
#include <deque>
template<typename T,
typename Allocator = std::allocator<T>
> class deque;
核心接口表格
接口名
功能描述
备注
push_front(const T& val)
在队头插入元素
效率高（无需移动元素）
push_back(const T& val)
在队尾插入元素
效率高
pop_front()
移除队头元素
效率高
pop_back()
移除队尾元素
效率高
front()/back()
返回队头/队尾元素
容器非空时使用
operator[](size_t i)
返回下标i的元素
支持随机访问
at(size_t i)
返回下标i的元素
越界抛出 out_of_range 异常
erase(iterator it)
擦除指定位置元素
效率低于list（需移动分段内元素）
insert(iterator it, const T& val)
在指定位置插入元素
效率低于list
empty()
判断队列是否为空
size() == 0 时返回true
示例代码
#include <iostream>
#include <deque>
using namespace std;
int main(void) {
deque<int> dq;
// 双端插入
dq.push_front(1); // 队头：1
dq.push_back(2); // 队尾：2
dq.push_front(0); // 队头：0
dq.push_back(3); // 队尾：3
// 随机访问
cout << "下标1的元素：" << dq[1] << endl; // 输出1
cout << "下标2的元素：" << dq.at(2) << endl; // 输出2
// 遍历
cout << "队列元素：";
for (deque<int>::iterator it = dq.begin(); it != dq.end(); it++) {
cout << *it << " "; // 输出：0 1 2 3
}
cout << endl;
// 双端删除
dq.pop_front(); // 移除0
dq.pop_back(); // 移除3
cout << "删除后元素：";
for (int val : dq) {
cout << val << " "; // 输出：1 2
}
cout << endl;
return 0;
}
链表容器
单链表 forward_list（C++11起）
核心特性
单向链表，仅支持正向遍历（无反向迭代器）
内存非连续，中间插入/删除效率高（无需移动元素）
不支持随机访问，访问元素需从头遍历
相比list更节省内存（无需存储前驱指针）
接口规范
#include <forward_list>
template<typename T,
typename Allocator = std::allocator<T>
> class forward_list;
核心接口表格
接口名
功能描述
备注
push_front(const T& val)
在表头插入元素
效率O(1)
pop_front()
移除表头元素
效率O(1)
insert_after(iterator pos, const T& val)
在pos位置后插入元素
需先找到目标位置，效率O(n)
erase_after(iterator pos)
擦除pos位置后的元素
效率O(1)
sort()
升序排序
需重载 < 运算符（自定义类型）
unique()
移除相邻重复元素
保留一个，需元素可比较
begin()/end()
返回正向迭代器
无反向迭代器（rbegin()/rend()）
实例：存储自定义类并排序
#include <iostream>
#include <forward_list>
#include <string>
using namespace std;
// 排序关键字枚举
enum SortKey { NUM, SCORE, NAME_LENGTH };
class Student {
private:
int num; // 学号
string name; // 姓名
int score; // 分数
public:
static SortKey sortKey; // 静态成员：排序关键字（类共享）
// 构造函数
Student(int n, int s, string nm) : num(n), score(s), name(nm) {}
// 访问器
int getNum() const { return num; }
string getName() const { return name; }
int getScore() const { return score; }
// 重载 < 运算符（用于sort()）
bool operator<(const Student& other) const {
switch (sortKey) {
case NUM:
return this->num < other.num;
case SCORE:
return this->score < other.score;
case NAME_LENGTH:
return this->name.length() < other.name.length();
default:
return false;
}
}
};
// 静态成员类外初始化
SortKey Student::sortKey = NUM;
int main() {
// 创建单链表并初始化
forward_list<Student> fl = {
Student(1, 35, "Evenvv"),
Student(3, 22, "Jacyd"),
Student(5, 17, "Jackjjjjj"),
Student(2, 78, "TieZhu")
};
// 按姓名长度排序
Student::sortKey = NAME_LENGTH;
fl.sort();
// 遍历输出
cout << "按姓名长度排序结果：" << endl;
for (const auto& stu : fl) {
cout << "学号：" << stu.getNum()
<< " 姓名：" << stu.getName()
<< " 分数：" << stu.getScore() << endl;
}
return 0;
}
双链表 list
核心特性
双向链表，支持正向/反向遍历
内存非连续，任意位置插入/删除效率高（O(1)，仅需修改指针）
不支持随机访问，访问元素需遍历（效率O(n)）
相比forward_list功能更全，但内存开销更大（需存储前驱+后继指针）
接口规范
#include <list>
template<typename T,
typename Allocator = std::allocator<T>
> class list;
核心接口表格
接口名
功能描述
备注
push_front(const T& val)
在表头插入元素
效率O(1)
push_back(const T& val)
在表尾插入元素
效率O(1)
pop_front()
移除表头元素
效率O(1)
pop_back()
移除表尾元素
效率O(1)
insert(iterator pos, const T& val)
在pos位置插入元素
需先找到pos，效率O(n)，插入本身O(1)
erase(iterator pos)
擦除pos位置元素
效率O(1)
sort()
升序排序
自定义类型需重载 < 运算符
reverse()
反转链表
效率O(n)
unique()
移除相邻重复元素
需元素可比较
begin()/end()
正向迭代器（起始/末尾）
rbegin()/rend()
反向迭代器（起始/末尾）
支持反向遍历
示例代码
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> myList;
// 两端插入
myList.push_front(3);
myList.push_back(1);
myList.push_front(2);
myList.push_back(4);
// 遍历（正向）
cout << "正向遍历：";
for (list<int>::iterator it = myList.begin(); it != myList.end(); it++) {
cout << *it << " "; // 输出：2 3 1 4
}
cout << endl;
// 排序
myList.sort();
cout << "排序后：";
for (int val : myList) {
cout << val << " "; // 输出：1 2 3 4
}
cout << endl;
// 插入元素（在2后面插入5）
auto it = myList.begin();
++it; // 指向2
myList.insert(it, 5);
// 反向遍历
cout << "反向遍历（含插入元素）：";
for (list<int>::reverse_iterator rit = myList.rbegin(); rit != myList.rend(); rit++) {
cout << *rit << " "; // 输出：4 3 2 5 1
}
cout << endl;
return 0;
}
顺序容器特性对比
容器类型
存储结构
随机访问
头部操作效率
尾部操作效率
中间插入/删除效率
迭代器类型
适用场景
array
连续数组（固定）
支持（O(1)）
O(1)（仅访问）
O(1)（仅访问）
O(n)（需移动元素）
随机访问迭代器
数据量固定、需频繁随机访问
vector
连续数组（动态）
支持（O(1)）
O(n)（需移动）
O(1)（扩容时O(n)）
O(n)（需移动元素）
随机访问迭代器
数据量动态、频繁尾部操作/随机访问
deque
分段连续数组
支持（O(1)）
O(1)
O(1)
O(n)（分段内移动）
随机访问迭代器
需双端操作、偶尔随机访问
forward_list
单向链表
不支持（O(n)）
O(1)
O(n)（需遍历）
O(1)（找到位置后）
正向迭代器
内存紧张、仅需正向遍历/中间操作
list
双向链表
不支持（O(n)）
O(1)
O(1)
O(1)（找到位置后）
双向迭代器
频繁任意位置插入/删除、双向遍历
常见问题与拓展知识
迭代器失效问题
容器类型
可能导致迭代器失效的操作
避免方案
vector
1. push_back() 触发扩容；2. insert()/erase() 中间操作
1. 预分配 reserve()；2. 操作后重新获取迭代器
deque
1. 头部/尾部插入可能导致迭代器失效；2. 中间插入/删除
操作后重新获取迭代器
list/forward_list
仅被删除元素的迭代器失效
保存下一个迭代器再删除（如 it = list.erase(it)）
内存使用优化
vector：用 reserve(n) 预分配内存，避免频繁扩容；用 shrink_to_fit() 释放多余内存（C++11起）
list：避免存储大量小对象（内存开销大），可考虑用 vector 替代
array：适合栈上存储（无需动态内存分配），但容量固定需提前规划
自定义类型作为容器元素的要求
必须提供默认构造函数（vector/deque 扩容时需要）
若使用 sort()/unique() 等算法，需重载 < 运算符或提供比较函数
若涉及拷贝操作，需确保拷贝构造函数/赋值运算符正确实现（避免浅拷贝）
容器适配器与顺序容器的关系
容器适配器（stack/queue/priority_queue）是对顺序容器的封装：
stack：基于 deque（默认）/vector/list，仅支持尾部操作（LIFO）
queue：基于 deque（默认）/list，仅支持队尾插入、队头删除（FIFO）
priority_queue：基于 vector（默认）/deque，是优先级队列（堆结构）