引言

顺序容器（Sequence Containers）以线性序列的方式存储元素，支持高效的插入、删除、访问等操作。主要包括：

• vector（动态数组）

• deque（双端队列）

• list（双向链表）

• forward_list（单向链表）

• array（定长数组）

1 vector

底层结构与原理：

• vector采用动态数组实现，所有元素在内存中连续存储。

• 容器内部维护一个指向首元素的指针、容量（capacity）和当前元素个数（size）。

• 当插入元素导致容量不足时，vector会自动扩容，通常为原容量的2倍（实现相关，但大多指数增长）。

• 扩容时会重新分配更大的内存块，并将原有元素移动（move或copy）到新内存，再释放旧内存。

性能分析：

• 随机访问极快，O(1)。

• 尾部插入/删除为均摊O(1)；扩容时最坏O(n)。

• 头部/中间插入/删除为O(n)，因为需要移动大量元素。

适用场景：

• 需要高效随机访问，主要在尾部操作。

• 需要与C API进行内存连续的数据交互。

代码示例：

#include <vector>
#include <iostream>

// 功能：演示vector的常见操作
int main() {
  // 创建一个空的vector，类型为int
  std::vector<int> numbers;

  // 预分配空间，减少扩容次数，提高性能
  numbers.reserve(100);

  // 尾部插入元素，push_back操作均摊O(1)
  for (int i = 0; i < 10; ++i) {
    numbers.push_back(i);
  }

  // 随机访问：vector支持下标操作，时间复杂度O(1)
  std::cout << "第5个元素: " << numbers[4] << std::endl;

  // 遍历所有元素，采用范围for语句
  for (const int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl;

  // 删除最后一个元素，pop_back操作O(1)
  numbers.pop_back();

  return 0;
}

• push_back在尾部插入，效率高。

• reserve提前分配空间，避免频繁扩容。

• numbers[4]直接访问第5个元素，效率极高。

• pop_back直接移除末尾元素，无需移动其他数据。

2 deque

底层结构与原理：

• deque采用分段连续内存块（block）实现，每个块大小固定，由一个指针数组（map）管理。

• 插入/删除时可在头尾分配或释放块，无需整体移动元素。

• 支持随机访问，但实现比vector复杂，常数略大。

性能分析：

• 随机访问O(1)，但常数比vector大。

• 头尾插入/删除O(1)。

• 中间插入/删除O(n)。

适用场景：

• 需要高效的头尾插入/删除，如队列、滑动窗口等。

代码示例：

#include <deque>
#include <iostream>

// 功能：演示deque两端插入与删除
int main() {
  std::deque<int> dq;

  // 在尾部插入元素
  dq.push_back(1);

  // 在头部插入元素
  dq.push_front(2);

  // 输出所有元素，顺序为头到尾
  for (const int num : dq) {
    std::cout << num << " ";
  }
  std::cout << std::endl;  // 输出：2 1

  // 删除尾部元素
  dq.pop_back();

  // 删除头部元素
  dq.pop_front();

  // 此时deque为空
  std::cout << "容器大小: " << dq.size() << std::endl;

  return 0;
}

• push_front和push_back分别在头尾插入元素，效率高。

• pop_front和pop_back分别在头尾删除元素，效率同样高。

• 内部结构保证了两端操作的高效性。

3 list

底层结构与原理：

• list为双向链表，每个节点包含数据和前驱、后继指针。

• 插入/删除节点只需修改相邻节点指针，效率高。

• 节点在内存中不连续，支持高效的插入/删除，但不支持随机访问。

性能分析：

• 任意位置插入/删除（已知迭代器）：O(1)。

• 随机访问：O(n)，需顺序遍历。

适用场景：

• 需要频繁在中间插入/删除元素，且不关心随机访问。

• 实现如LRU缓存、链式数据处理等。

代码示例：

#include <list>
#include <iostream>

// 功能：演示list中间插入和删除
int main() {
  // 初始化list，包含3个元素
  std::list<int> lst = {1, 2, 3};

  // 获取第二个元素的迭代器
  auto it = lst.begin();
  ++it;  // 指向2

  // 在第二个元素前插入4
  lst.insert(it, 4);  // 结果：1 4 2 3

  // 遍历输出所有元素
  for (const int num : lst) {
    std::cout << num << " ";
  }
  std::cout << std::endl;

  // 删除刚插入的4
  --it;  // it现在指向4
  lst.erase(it);

  // 再次输出
  for (const int num : lst) {
    std::cout << num << " ";
  }
  std::cout << std::endl;  // 输出：1 2 3

  return 0;
}

• 通过迭代器可以在任意位置插入和删除，效率高。

• 插入和删除不会影响其他节点的存储位置。

4 forward_list

底层结构与原理：

• forward_list为单向链表，每个节点只包含数据和后继指针。

• 更节省内存，适合只需单向遍历的场景。

• 节点在内存中不连续，插入/删除需已知前驱节点。

性能分析：

• 插入/删除（已知前驱）：O(1)。

• 随机访问：O(n)。

适用场景：

• 内存敏感、仅需单向遍历的应用，如哈希表的拉链法实现。

代码示例：

#include <forward_list>
#include <iostream>

// 功能：演示forward_list头部操作
int main() {
  // 初始化forward_list，包含3个元素
  std::forward_list<int> fl = {1, 2, 3};

  // 在头部插入元素
  fl.push_front(0);  // 结果：0 1 2 3

  // 遍历输出
  for (const int num : fl) {
    std::cout << num << " ";
  }
  std::cout << std::endl;

  // 删除头部元素
  fl.pop_front();  // 结果：1 2 3

  // 再次输出
  for (const int num : fl) {
    std::cout << num << " ";
  }
  std::cout << std::endl;

  return 0;
}

• push_front和pop_front分别在头部插入和删除，效率高。

• 只能单向遍历，不支持随机访问。

5 array

底层结构与原理：

• array为封装的原生数组，内存连续，大小在编译期确定。

• 无法动态扩容，效率极高，支持所有STL算法。

性能分析：

• 所有操作O(1)。

适用场景：

• 数组大小已知且不变，追求极致性能和内存局部性。

代码示例：

#include <array>
#include <iostream>

// 功能：演示array的基本用法
int main() {
  // 创建一个长度为3的array
  std::array<int, 3> arr = {1, 2, 3};

  // 随机访问第二个元素
  std::cout << "第二个元素: " << arr[1] << std::endl;

  // 遍历所有元素
  for (const int num : arr) {
    std::cout << num << " ";
  }
  std::cout << std::endl;

  // array的大小在编译期确定，不支持插入/删除

  return 0;
}

• array的元素在内存中连续，支持高效随机访问。

• 不支持动态扩容和插入/删除操作。

6 性能对比

7 与原生实现及其他方法对比

• 原生数组：手动管理内存，容易越界，无自动扩容和丰富成员函数，易出错。

• 手写链表：灵活但实现复杂，维护成本高，容易内存泄漏。

• STL容器：自动管理内存，接口统一，异常安全。推荐优先使用。

示例对比：vector与原生数组

// 原生数组
int arr[100];
arr[0] = 1;  // 需要手动管理长度与边界，易出错

// vector
std::vector<int> vec;
vec.push_back(1);  // 自动扩容，安全

vector自动扩容、越界检查、异常安全、支持迭代器，推荐使用。

8 总结与建议

• vector：优先选择，适合大多数顺序存储需求，内存连续，效率高。

• deque：适合双端高效操作，内存分段，随机访问稍慢。

• list/forward_list：插入/删除频繁、元素量大时可选，但不支持高效随机访问。

• array：适合定长、性能敏感场景。

选择容器时应结合数据访问模式、操作频率、内存需求等因素综合考虑。