关于顺序容器的个人在学习与理解

2024年5月22日 · 阅读需 12 分钟

文章详细介绍了五种常用的序列式容器：array、vector、deque、forward_list和list。每种容器的核心特点、复杂度分析以及代码示例均清晰明了。

前言

学过数据结构的同学们应该知道动态数组，双向链表，模拟栈，队列等基础数据结构的原理。比如我们在学习时，老师就要求我们使用数组，结构体等，实现模拟的循环队列双向链表等复杂的数据结构。对于这种可能需要重复劳动的“体力活”，C++标准模板库（STL）对这些进行了封装，提供了一系列强大且灵活的容器，可大概分类为这三类：

序列式容器
关联式容器
无序（关联式）容器

从名字可以看出：前者存在一个顺序，就像数组链表一样。后两者侧重于对应，类似哈希表。本文将介绍序列式容器，也可说顺序型容器；

本文章侧重于容器的理解与核心，不涉及具体使用，如需具体使用方法，请访问:

具体用法Vector、List 更多请访问官网

核心

总览

序列式容器常用的共有5种：

数组(array)：定长的顺序表，C 风格数组的简单包装。
向量(vector)：后端可高效增加元素的顺序表。
双端队列(deque)：双端都可高效增加元素的顺序表。
单向列表(forward_list)：只能沿一个方向遍历的链表。
列表(list)：可以沿双向遍历的链表。

学过数据结构的应该清楚，前三者都是本质数组，后两者为链表。没学过也不用担心，只要你知道什么是数组，什么是链表就够了，我们一个一个来介绍：

数组(array)

array本质就是一个数组，没什么可以说的：

特点：

固定大小
支持随机访问
不支持动态大小调整

复杂度分析：

访问：常数时间复杂度O(1)
尾部插入和删除：如允许，线性时间复杂度O(n)
中间插入和删除：如允许，线性时间复杂度O(n)

代码示例：

int main() {
    std::array<int, 5> arr = {1, 2, 3, 4, 5};
    arr[2] = 10; // 随机访问

    for (const auto& elem : arr) 
    {
        std::cout << elem << " ";
    }
    return 0;
}

向量(vector)

vector是动态数组，能够自动调整其大小。它的本质依然是数组。

数组(array)的不足在于，我定义了一个10个元素的数组，那么我想插入第11个元素，很显然不允许。那我应该怎么做，答案很粗暴简单，我开一个11元素的数组，把原来数组拷贝过来，插入第11个元素，把数组的头指针移过来，不就搞定了？ 对的，这就是动态数组的扩容机制，当然，大家也应该看到了，扩容操作是一个并不高效的操作，在实际运行时，往往都是倍增起步，即10个元素满了，有新的插入需求时直接倍增，扩充为20或更大的数组。

特点：

动态大小调整
支持随机访问
允许插入和删除操作，在末尾时时间复杂度为O(1)

复杂度分析：

访问：常数时间复杂度O(1) 尾部插入和删除：均摊常数时间复杂度O(1) 其他插入和删除：线性时间复杂度O(n)

代码示例：

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    vec.push_back(6); // 在末尾插入元素
    vec[2] = 10;      // 随机访问

    for (const auto& elem : vec) 
    {
        std::cout << elem << " ";
    }
    return 0;
}

可以看出，vector相比array，最大的改善就是允许直接插入删除，不在需要担心容量问题，是一个相当优秀的上位替代。
注意，Vector是常用的库,为重点，详细用法请参考:具体用法Vector、List

双端队列(deque)

vector解决了一个问题，即直接从尾部插入删除元素，但是如果需要频繁更改头部元素呢？和数组一样，如果需要在头部增删一个数据，那么需要将后面所有元素都进行移动，如果频繁的插入删除，效率会很低。回顾一下vector，vector之所以可以在尾部快速增删，本质是因为尾部并没有满，所谓的增删本质上是将尾部的空数据替换成要变更的数据。这个尾部实际上存在，只是被我们屏蔽了。既然尾部可以这样操作，那首部可不可以呢？当然可以，定义10个元素的数组，然后在前面额外分配10个空间，后面额外分配10个空间，然后封装起来，当我们访问a[0]的时候，本质上是*a(10+0)。对的，这就是双端队列的核心思想。当然，实际上的双端队列是分段存储的，实现要比vector复杂的多，但是正如前面这个例子，核心并不难。

特点：

双端高效插入和删除
支持随机访问
动态大小调整

复杂度分析：

访问：常数时间复杂度O(1)
两端插入和删除：常数时间复杂度O(1)
中间插入和删除：线性时间复杂度O(n)

代码示例：

int main() {
    std::deque<int> deq = {1, 2, 3, 4, 5};
    deq.push_front(0); // 在前端插入元素
    deq.push_back(6);  // 在末尾插入元素

    for (const auto& elem : deq) {
        std::cout << elem << " ";
    }
    return 0;
}

实际使用中，需要根据实际需要进行选择，并无明显的优劣之分。

单向列表(forward_list)

单向列表就是一个普通的单向链表，每一个元素保存当前元素的内容和下一个元素的地址。

特点：

只能沿一个方向遍历
高效的头部插入和删除

复杂度分析：

访问：线性时间复杂度O(n)
头部插入和删除：常数时间复杂度O(1)
其他插入和删除：线性时间复杂度O(n)

关于增删复杂度，这里认为没有相关引用，即首先查询，然后增删。关于其他情况，假如向单向列表ABC中，在B后插入元素D；如果已经有要插入位置上一个元素B的引用，则为O(1)。如果已经有要插入位置下一个元素C的引用，我们无法得到B的位置，则依然需要先查询到B，才可以进行插入。总之，具体情况需要进行分析。

代码示例：

int main() {
    std::forward_list<int> flist = {1, 2, 3, 4, 5};
    flist.push_front(0); // 在头部插入元素

    for (const auto& elem : flist) {
        std::cout << elem << " ";
    }
    return 0;
}

列表(list)

list是双向链表，可以沿双向遍历。每个元素保存当前元素的内容，上一个和下一个元素的地址。

特点：

高效的插入和删除操作
支持双向遍历
动态大小调整

复杂度分析：

访问：线性时间复杂度O(n) 首部和尾部插入和删除：常数时间复杂度O(n) 其他位置插入和删除：常数时间复杂度O(n)

同前面单向列表，这里假设不知道插入位置相关的引用，故需要先遍历链表查询位置。

代码示例：

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    lst.push_back(6);   // 在末尾插入元素
    lst.push_front(0);  // 在前端插入元素

    for (const auto& elem : lst) {
        std::cout << elem << " ";
    }
    return 0;
}

总结与理解

简单总结一下各个顺序容器：

array：适用于大小固定且需要随机访问的场景，但不支持动态调整大小。
vector：适用于需要动态调整大小且尾部插入和删除操作频繁的场景，是大多数情况下的首选容器。
deque：适用于需要双端高效插入和删除操作的场景，结合了数组和链表的优点。
forward_list：适用于需要高效头部插入和删除且不需要双向遍历的场景，内存占用较低。
list：适用于需要双向遍历和高效插入删除操作的场景，提供了最大的灵活性。

顺序容器是C++ STL中最常用的容器之一，也是算法比赛，项目开发中常用的数据结构，熟练使用可以大大提升编程的灵活性。尽管有些地方认为STL是模版编程，将它归为高级特性，但事实就是，灵活使用STL是一个重要的基本功。

前言

核心

总览​

数组(array)​

向量(vector)​

双端队列(deque)​

单向列表(forward_list)​

列表(list)​

总结与理解

总览

数组(array)

向量(vector)

双端队列(deque)

单向列表(forward_list)

列表(list)