跳到主要内容

C++ 序列容器

什么是序列容器?

序列容器是C++ STL(标准模板库)中的一类容器,它们以线性方式存储和组织元素。序列容器中的每个元素都有固定的位置,取决于插入的时间和地点,与元素的值无关。

备注

序列容器的主要特点是元素按照严格的线性顺序排列,可以通过位置访问。

主要的序列容器类型

C++标准库提供了几种不同的序列容器,每种都有其特定的用途和性能特点:

  1. vector - 动态数组
  2. deque - 双端队列
  3. list - 双向链表
  4. forward_list (C++11) - 单向链表
  5. array (C++11) - 静态数组

vector容器

基本概念

vector是最常用的序列容器,它实现了一个动态数组,可以在运行时改变大小。

特点

  • 支持快速随机访问 O(1)
  • 在末尾插入/删除元素效率高 O(1)(平摊复杂度)
  • 在中间或开头插入/删除元素效率低 O(n)
  • 当空间不足时,会重新分配更大的连续内存空间

基本用法

cpp
#include <iostream>
#include <vector>

int main() {
// 创建一个空的vector
std::vector<int> vec1;

// 创建一个包含5个元素的vector,每个元素初始化为0
std::vector<int> vec2(5, 0);

// 使用初始化列表(C++11)
std::vector<int> vec3 = {1, 2, 3, 4, 5};

// 添加元素
vec1.push_back(10);
vec1.push_back(20);

// 访问元素
std::cout << "第一个元素: " << vec1[0] << std::endl; // 输出: 10
std::cout << "第二个元素: " << vec1.at(1) << std::endl; // 输出: 20

// 获取大小
std::cout << "容器大小: " << vec1.size() << std::endl; // 输出: 2

// 遍历vector
for (const auto& element : vec3) {
std::cout << element << " ";
}
// 输出: 1 2 3 4 5

return 0;
}

常用成员函数

函数名描述
push_back()在末尾添加元素
pop_back()删除末尾元素
size()返回容器中的元素数量
empty()检查容器是否为空
at()返回指定位置的元素(带边界检查)
operator[]返回指定位置的元素(无边界检查)
front()返回第一个元素
back()返回最后一个元素
clear()清空容器
insert()在指定位置插入元素
erase()删除指定位置的元素
resize()调整容器大小
reserve()预分配容量,不改变size
capacity()返回容器当前分配的存储空间大小

deque容器

基本概念

deque(双端队列)是一个支持快速在两端进行插入和删除操作的序列容器。

特点

  • 支持随机访问 O(1)
  • 在两端插入/删除元素效率高 O(1)
  • 在中间插入/删除元素效率低 O(n)
  • 内存布局不连续,使用多个内存块链接

基本用法

cpp
#include <iostream>
#include <deque>

int main() {
// 创建一个空的deque
std::deque<int> dq1;

// 创建一个包含5个元素的deque,每个元素初始化为0
std::deque<int> dq2(5, 0);

// 使用初始化列表
std::deque<int> dq3 = {1, 2, 3, 4, 5};

// 在两端添加元素
dq1.push_back(10); // 在末尾添加
dq1.push_front(5); // 在开头添加

// 访问元素
std::cout << "第一个元素: " << dq1.front() << std::endl; // 输出: 5
std::cout << "最后一个元素: " << dq1.back() << std::endl; // 输出: 10

// 遍历deque
for (const auto& element : dq1) {
std::cout << element << " ";
}
// 输出: 5 10

return 0;
}

list容器

基本概念

list是一个双向链表,它允许在任何位置进行常数时间的插入和删除操作。

特点

  • 不支持随机访问(只能顺序访问)
  • 在任何位置插入/删除元素效率高 O(1)
  • 占用更多内存(需要存储前后指针)

基本用法

cpp
#include <iostream>
#include <list>

int main() {
// 创建一个空的list
std::list<int> lst1;

// 创建一个包含5个元素的list,每个元素初始化为0
std::list<int> lst2(5, 0);

// 使用初始化列表
std::list<int> lst3 = {1, 2, 3, 4, 5};

// 在两端添加元素
lst1.push_back(10);
lst1.push_front(5);

// 在特定位置插入元素
auto it = lst1.begin();
++it; // 移动到第二个位置
lst1.insert(it, 7);

// 遍历list
for (const auto& element : lst1) {
std::cout << element << " ";
}
// 输出: 5 7 10

return 0;
}

forward_list容器 (C++11)

基本概念

forward_list是一个单向链表,相比list更加节省内存,但只能向前遍历。

特点

  • 最小的内存开销
  • 不支持随机访问
  • 只能从前向后遍历
  • 不能获取size(没有size()方法)
  • 在任何位置插入/删除元素效率高

基本用法

cpp
#include <iostream>
#include <forward_list>

int main() {
// 创建一个空的forward_list
std::forward_list<int> flist1;

// 创建一个包含5个元素的forward_list,每个元素初始化为0
std::forward_list<int> flist2(5, 0);

// 使用初始化列表
std::forward_list<int> flist3 = {1, 2, 3, 4, 5};

// 在开头添加元素
flist1.push_front(10);
flist1.push_front(20);
flist1.push_front(30);

// 在特定位置后插入元素
auto it = flist1.begin(); // 指向第一个元素
flist1.insert_after(it, 25);

// 遍历forward_list
for (const auto& element : flist1) {
std::cout << element << " ";
}
// 输出: 30 25 20 10

return 0;
}

array容器 (C++11)

基本概念

array是一个固定大小的数组,它包装了一个C风格的数组,提供了STL容器的接口。

特点

  • 大小固定,不能动态改变
  • 支持快速随机访问 O(1)
  • 不会进行动态内存分配
  • 比vector更加高效(当大小固定时)

基本用法

cpp
#include <iostream>
#include <array>

int main() {
// 创建一个包含5个int元素的array
std::array<int, 5> arr1 = {1, 2, 3, 4, 5};

// 访问元素
std::cout << "第一个元素: " << arr1[0] << std::endl; // 输出: 1
std::cout << "第三个元素: " << arr1.at(2) << std::endl; // 输出: 3

// 获取大小
std::cout << "容器大小: " << arr1.size() << std::endl; // 输出: 5

// 遍历array
for (const auto& element : arr1) {
std::cout << element << " ";
}
// 输出: 1 2 3 4 5

// 使用fill方法填充所有元素
arr1.fill(10);

// 再次遍历
for (const auto& element : arr1) {
std::cout << element << " ";
}
// 输出: 10 10 10 10 10

return 0;
}

序列容器的性能比较

下表总结了各序列容器的性能特点:

容器随机访问开头插入/删除中间插入/删除末尾插入/删除内存使用
vectorO(1)O(n)O(n)O(1)*低(连续存储)
dequeO(1)O(1)*O(n)O(1)*中(分块存储)
listO(n)O(1)O(1)O(1)高(双向链表)
forward_listO(n)O(1)O(n)O(n)中(单向链表)
arrayO(1)不支持不支持不支持最低(固定大小)

*注:平摊复杂度,某些情况下可能会触发内存重新分配。

实际应用场景

vector 的应用

cpp
// 使用vector存储学生信息
#include <iostream>
#include <vector>
#include <string>

struct Student {
std::string name;
int id;
float gpa;

Student(const std::string& n, int i, float g) : name(n), id(i), gpa(g) {}
};

int main() {
std::vector<Student> students;

// 添加学生
students.push_back(Student("张三", 1001, 3.8));
students.push_back(Student("李四", 1002, 3.9));
students.push_back(Student("王五", 1003, 3.7));

// 查找并显示特定ID的学生
int searchId = 1002;
for (const auto& student : students) {
if (student.id == searchId) {
std::cout << "找到学生: " << student.name
<< ", GPA: " << student.gpa << std::endl;
break;
}
}

return 0;
}

deque 的应用

cpp
// 使用deque实现一个简单的任务队列
#include <iostream>
#include <deque>
#include <string>

int main() {
std::deque<std::string> taskQueue;

// 添加普通任务(从队尾)
taskQueue.push_back("发送邮件");
taskQueue.push_back("生成报表");

// 添加优先任务(从队首)
taskQueue.push_front("紧急修复Bug");

// 处理任务(总是从队首开始)
std::cout << "处理任务顺序:" << std::endl;
while (!taskQueue.empty()) {
std::cout << "- " << taskQueue.front() << std::endl;
taskQueue.pop_front();
}

return 0;
}

list 的应用

cpp
// 使用list实现一个播放列表,可以在任意位置插入/删除歌曲
#include <iostream>
#include <list>
#include <string>

int main() {
std::list<std::string> playlist;

// 添加歌曲
playlist.push_back("歌曲1");
playlist.push_back("歌曲2");
playlist.push_back("歌曲4");

// 在特定位置插入歌曲
auto it = playlist.begin();
std::advance(it, 2); // 移动到第三个位置
playlist.insert(it, "歌曲3");

// 显示播放列表
std::cout << "播放列表:" << std::endl;
int trackNum = 1;
for (const auto& song : playlist) {
std::cout << trackNum++ << ". " << song << std::endl;
}

// 删除一首歌曲
it = playlist.begin();
std::advance(it, 1); // 移动到第二个位置
playlist.erase(it);

// 显示更新后的播放列表
std::cout << "\n更新后的播放列表:" << std::endl;
trackNum = 1;
for (const auto& song : playlist) {
std::cout << trackNum++ << ". " << song << std::endl;
}

return 0;
}

选择合适的序列容器

在选择序列容器时,应考虑以下几点:

  1. 需要频繁随机访问元素?

    • 是 → 考虑 vectorarray
    • 否 → 考虑 listforward_list
  2. 需要在容器中间频繁插入/删除元素?

    • 是 → 考虑 list
    • 否 → 考虑 vectordeque
  3. 需要在容器两端频繁插入/删除元素?

    • 是 → 考虑 deque
    • 否 → 根据其他需求选择
  4. 内存使用是否关键?

    • 是 → 考虑 vector (连续存储) 或 forward_list (单链表)
    • 否 → 根据其他需求选择
  5. 容器大小是否固定?

    • 是 → 考虑 array
    • 否 → 考虑其他动态容器
提示

在实际应用中,除非有特殊需求,vector通常是首选的序列容器,因为它提供了良好的性能和便利的接口。

总结

序列容器是C++ STL的重要组成部分,它们提供了不同的存储和访问数据的方式:

  • vector: 动态数组,适合快速随机访问和末尾操作
  • deque: 双端队列,适合两端操作
  • list: 双向链表,适合任意位置的插入和删除
  • forward_list: 单向链表,占用更少内存但功能有限
  • array: 固定大小数组,提供STL接口的轻量级封装

了解不同序列容器的特点和用途,可以帮助你在编程中选择最合适的容器,提高程序的效率和可维护性。

练习与挑战

  1. 实现一个简单的文本编辑器,使用适当的序列容器存储文本行,支持在任意位置插入和删除行。

  2. 编写一个程序,比较在不同大小的数据集上,使用vectorlist进行中间位置插入操作的性能差异。

  3. 实现一个滑动窗口算法,使用deque存储窗口中的元素。

  4. 创建一个使用array的固定大小缓冲区,实现循环写入和读取操作。

  5. 使用forward_list实现一个简单的内存池,管理固定大小的内存块。

进一步学习资源

  • C++ 参考手册 - 容器
  • 《C++ Primer》第9章 顺序容器
  • 《Effective STL》by Scott Meyers
  • 《STL 源码剖析》by 侯捷