C++ 序列容器

概述

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

序列容器的主要类型包括：

• std::vector
  

  - 动态数组

• std::deque
  

  - 双端队列

• std::list
  

  - 双向链表

• std::forward_list
  

  - 单向链表（C++11引入）

• std::array
  

  - 固定大小数组（C++11引入）

容器特性比较

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

容器名称	存储结构	随机访问	插入/删除效率	内存分配方式	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的内存增长可以通过以下公式描述： $capacit{y}_{new}=max(2\times capacit{y}_{current},siz{e}_{required})$

std::deque

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

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

示例代码

#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命名空间中的多态分配器

参见

• C++迭代器
• C++算法库
• C++容器适配器