C++ 序列容器
概述[编辑 | 编辑源代码]
C++标准模板库（STL）中的序列容器是一组线性数据结构，按照严格的线性顺序存储元素。与关联容器不同，序列容器中的元素位置取决于插入时间和位置，而非元素值本身。这些容器提供了对元素的顺序访问和高效插入/删除操作，是C++程序设计的核心组件之一。
序列容器的主要类型包括：
- - 动态数组
std::vector
- - 双端队列
std::deque
- - 双向链表
std::list
- - 单向链表（C++11引入）
std::forward_list
- - 固定大小数组（C++11引入）
std::array
容器特性比较[编辑 | 编辑源代码]
下表展示了各序列容器的关键特性：
| 容器名称 | 存储结构 | 随机访问 | 插入/删除效率 | 内存分配方式 | vector
|
动态数组 | 是（O(1)） | 尾部O(1)，其他O(n) | 连续内存 | deque
|
分块数组 | 是（O(1)） | 头尾O(1)，其他O(n) | 分段连续 | list
|
双向链表 | 否（O(n)） | 任意位置O(1) | 非连续 | forward_list
|
单向链表 | 否（O(n)） | 已知位置后O(1) | 非连续 | array
|
固定数组 | 是（O(1)） | 不支持 | 连续内存 |
|---|
详细容器说明[编辑 | 编辑源代码]
std::vector[编辑 | 编辑源代码]
动态数组，在堆上分配连续内存空间，支持快速随机访问。当容量不足时会自动重新分配内存（通常以2倍大小增长）。
基本操作示例[编辑 | 编辑源代码]
#include <vector>
#include <iostream>
int main() {
std::vector<int> nums = {1, 2, 3}; // 初始化
// 添加元素
nums.push_back(4); // 尾部插入
nums.insert(nums.begin(), 0); // 头部插入
// 访问元素
std::cout << "第一个元素: " << nums[0] << '\n';
std::cout << "最后一个元素: " << nums.back() << '\n';
// 遍历
for(int num : nums) {
std::cout << num << ' ';
}
return 0;
}
输出：
第一个元素: 0 最后一个元素: 4 0 1 2 3 4
= 内存管理[编辑 | 编辑源代码]
vector的内存增长可以通过以下公式描述：
std::deque[编辑 | 编辑源代码]
双端队列，由多个固定大小的数组块组成，支持在头部和尾部高效插入/删除。
示例代码[编辑 | 编辑源代码]
#include <deque>
#include <iostream>
int main() {
std::deque<std::string> lines;
// 双端操作
lines.push_back("World");
lines.push_front("Hello");
lines.push_back("!");
for(const auto& line : lines) {
std::cout << line << ' ';
}
return 0;
}
输出：
Hello World !
std::list 和 std::forward_list[编辑 | 编辑源代码]
链表结构，区别在于双向和单向链接。
链表操作示例[编辑 | 编辑源代码]
#include <list>
#include <algorithm>
int main() {
std::list<int> data = {2, 4, 6};
// 高效插入
data.insert(data.begin(), 0); // 头部插入
auto it = std::find(data.begin(), data.end(), 4);
data.insert(it, 3); // 在4前插入3
// 高效删除
data.remove(6); // 删除所有6
// 链表特有操作
data.sort(); // 排序
data.unique(); // 去重
return 0;
}
std::array[编辑 | 编辑源代码]
固定大小数组，包装了C风格数组，提供STL接口。
#include <array>
#include <iostream>
int main() {
std::array<int, 3> arr = {1, 2, 3};
// 安全访问
try {
std::cout << arr.at(4); // 抛出std::out_of_range
} catch(const std::exception& e) {
std::cerr << e.what();
}
// 编译时大小检查
static_assert(arr.size() == 3, "大小必须为3");
return 0;
}
性能考虑[编辑 | 编辑源代码]
- vector：最适合随机访问频繁、主要在尾部操作的场景
- deque：适合频繁在两端操作的场景
- list：适合频繁在任意位置插入删除的场景
- array：适合固定大小且需要STL接口的场景
实际应用案例[编辑 | 编辑源代码]
案例1：游戏实体管理[编辑 | 编辑源代码]
使用vector存储游戏中的动态实体：
class GameEntity {
// 实体属性和方法...
};
std::vector<GameEntity> entities;
// 每帧更新
void updateAllEntities() {
for(auto& entity : entities) {
entity.update();
}
// 移除失效实体（使用erase-remove惯用法）
entities.erase(
std::remove_if(entities.begin(), entities.end(),
[](const GameEntity& e) { return !e.isActive(); }),
entities.end());
}
案例2：文本编辑器撤销操作[编辑 | 编辑源代码]
使用deque实现有限撤销栈：
std::deque<EditorState> undoStack;
const size_t MAX_UNDO = 100;
void executeCommand(Command cmd) {
// 保存当前状态
undoStack.push_front(currentState);
// 执行命令
cmd.execute();
// 限制栈大小
if(undoStack.size() > MAX_UNDO) {
undoStack.pop_back();
}
}
高级主题[编辑 | 编辑源代码]
迭代器失效问题[编辑 | 编辑源代码]
不同容器在修改操作后迭代器的有效性不同：
- vector：插入/删除可能导致所有迭代器失效
- deque：中间插入/删除使所有迭代器失效，头尾操作只影响相关迭代器
- list：只有被删除元素的迭代器失效
自定义分配器[编辑 | 编辑源代码]
STL容器允许指定自定义内存分配器：
#include <memory>
#include <vector>
template<typename T>
class CustomAllocator {
// 实现分配器接口...
};
std::vector<int, CustomAllocator<int>> customVector;
最佳实践[编辑 | 编辑源代码]
1. 默认首选vector，除非有特定需求 2. 预分配vector空间（使用reserve()）减少重分配 3. 链表容器只在频繁中间插入时使用 4. 注意容器的异常安全性保证 5. C++17后考虑使用std::pmr命名空间中的多态分配器