编辑“︁C++ 序列容器”︁

{{DISPLAYTITLE:C++序列容器}}

== 概述 ==
'''C++标准模板库（STL）中的序列容器'''是一组线性数据结构，按照严格的线性顺序存储元素。与关联容器不同，序列容器中的元素位置取决于插入时间和位置，而非元素值本身。这些容器提供了对元素的顺序访问和高效插入/删除操作，是C++程序设计的核心组件之一。

序列容器的主要类型包括：
* {{code|std::vector}} - 动态数组
* {{code|std::deque}} - 双端队列
* {{code|std::list}} - 双向链表
* {{code|std::forward_list}} - 单向链表（C++11引入）
* {{code|std::array}} - 固定大小数组（C++11引入）

== 容器特性比较 ==
下表展示了各序列容器的关键特性：

{| class="wikitable"
! 容器名称
! 存储结构
! 随机访问
! 插入/删除效率
! 内存分配方式

| {{code|vector}}
| 动态数组
| 是（O(1)）
| 尾部O(1)，其他O(n)
| 连续内存

| {{code|deque}}
| 分块数组
| 是（O(1)）
| 头尾O(1)，其他O(n)
| 分段连续

| {{code|list}}
| 双向链表
| 否（O(n)）
| 任意位置O(1)
| 非连续

| {{code|forward_list}}
| 单向链表
| 否（O(n)）
| 已知位置后O(1)
| 非连续

| {{code|array}}
| 固定数组
| 是（O(1)）
| 不支持
| 连续内存
|}

== 详细容器说明 ==

=== std::vector ===
'''动态数组'''，在堆上分配连续内存空间，支持快速随机访问。当容量不足时会自动重新分配内存（通常以2倍大小增长）。

==== 基本操作示例 ====
<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>

输出：
<pre>
第一个元素: 0
最后一个元素: 4
0 1 2 3 4 
</pre>

==== 内存管理 ===
vector的内存增长可以通过以下公式描述：
<math>
capacity_{new} = max(2 \times capacity_{current}, size_{required})
</math>

=== std::deque ===
'''双端队列'''，由多个固定大小的数组块组成，支持在头部和尾部高效插入/删除。

<mermaid>
graph LR
    A[块1] --> B[块2] --> C[块3]
    A -->|前端| Front
    C -->|后端| Back
</mermaid>

==== 示例代码 ====
<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>

输出：
<pre>
Hello World ! 
</pre>

=== std::list 和 std::forward_list ===
链表结构，区别在于双向和单向链接。

==== 链表操作示例 ====
<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>

=== std::array ===
'''固定大小数组'''，包装了C风格数组，提供STL接口。

<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>

== 性能考虑 ==
* '''vector'''：最适合随机访问频繁、主要在尾部操作的场景
* '''deque'''：适合频繁在两端操作的场景
* '''list'''：适合频繁在任意位置插入删除的场景
* '''array'''：适合固定大小且需要STL接口的场景

== 实际应用案例 ==
=== 案例1：游戏实体管理 ===
使用vector存储游戏中的动态实体：

<syntaxhighlight lang="cpp">
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());
}
</syntaxhighlight>

=== 案例2：文本编辑器撤销操作 ===
使用deque实现有限撤销栈：

<syntaxhighlight lang="cpp">
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();
    }
}
</syntaxhighlight>

== 高级主题 ==
=== 迭代器失效问题 ===
不同容器在修改操作后迭代器的有效性不同：

* '''vector'''：插入/删除可能导致所有迭代器失效
* '''deque'''：中间插入/删除使所有迭代器失效，头尾操作只影响相关迭代器
* '''list'''：只有被删除元素的迭代器失效

=== 自定义分配器 ===
STL容器允许指定自定义内存分配器：

<syntaxhighlight lang="cpp">
#include <memory>
#include <vector>

template<typename T>
class CustomAllocator {
    // 实现分配器接口...
};

std::vector<int, CustomAllocator<int>> customVector;
</syntaxhighlight>

== 最佳实践 ==
1. 默认首选vector，除非有特定需求
2. 预分配vector空间（使用reserve()）减少重分配
3. 链表容器只在频繁中间插入时使用
4. 注意容器的异常安全性保证
5. C++17后考虑使用std::pmr命名空间中的多态分配器

== 参见 ==
* [[C++迭代器]]
* [[C++算法库]]
* [[C++容器适配器]]

[[Category:编程语言]]
[[Category:C++]]
[[Category:C++stl 容器]]