C++ list 与 vector 用法解析

C++ list 与 vector 简介

在 C++ 编程中，list 和 vector 都是标准模板库（STL）中极为重要的容器类。它们为程序员提供了方便且高效的数据存储和管理方式，但两者在实现原理、性能特点以及适用场景上有着显著的差异。

vector 是一种顺序容器，它以连续的内存空间来存储元素。这就好比是在一片连续的土地上建造房屋，每个房屋都紧密相连。这种连续存储的特性使得 vector 能够像数组一样通过下标快速访问元素，因为其内存地址是连续递增的。例如，若 vector 存储了一系列整数，访问第 n 个整数时，计算机可以根据起始地址和每个整数的大小，直接计算出第 n 个整数的内存地址并快速获取其值。

而 list 则是一种双向链表容器。链表中的每个节点就像是一个个独立的房间，每个房间都有两个门，一个指向前一个房间（前驱节点），另一个指向后一个房间（后继节点）。这种结构使得 list 在插入和删除元素时非常高效，因为只需调整相关节点的指针指向，而不需要像 vector 那样移动大量元素。但由于链表的节点在内存中并非连续存储，所以 list 不支持通过下标直接访问元素，要访问某个元素，必须从链表的头节点或尾节点开始，顺着指针逐个遍历。

vector 的用法

定义与初始化

vector 的定义方式多种多样。最基本的形式是定义一个空的 vector，例如：

#include <vector>
std::vector<int> myVector;

这里定义了一个名为 myVector 的 vector，它可以存储 int 类型的数据，初始时不包含任何元素。

也可以在定义时指定初始大小，例如：

std::vector<int> myVector(5);

此时 myVector 被初始化为包含 5 个 int 类型的元素，这些元素默认值为 0（对于 int 类型）。

如果希望初始化时给元素赋予特定的值，可以使用如下方式：

std::vector<int> myVector = {1, 2, 3, 4, 5};

或者

std::vector<int> myVector({1, 2, 3, 4, 5});

还可以通过拷贝构造函数来初始化 vector，例如：

std::vector<int> sourceVector = {1, 2, 3};
std::vector<int> targetVector(sourceVector);

元素访问

vector 支持通过下标运算符 [] 来访问元素，就像访问数组元素一样。例如：

std::vector<int> myVector = {10, 20, 30};
std::cout << "The first element is: " << myVector[0] << std::endl;

这里通过 myVector[0] 访问到了 vector 中的第一个元素。

除了 [] 运算符，vector 还提供了 at() 成员函数来访问元素。at() 函数与 [] 运算符的主要区别在于，at() 会进行边界检查，如果访问的下标越界，会抛出 std::out_of_range 异常，而 [] 运算符在越界时行为未定义，可能导致程序崩溃。例如：

try {
    std::vector<int> myVector = {10, 20, 30};
    std::cout << "The fourth element is: " << myVector.at(3) << std::endl;
} catch (const std::out_of_range& e) {
    std::cerr << "Out of range exception: " << e.what() << std::endl;
}

元素插入与删除

在 vector 的末尾添加元素可以使用 push_back() 函数。例如：

std::vector<int> myVector = {1, 2, 3};
myVector.push_back(4);

此时 myVector 变为 {1, 2, 3, 4}。

若要在 vector 的指定位置插入元素，可以使用 insert() 函数。insert() 函数的第一个参数是插入位置的迭代器，第二个参数是要插入的元素。例如，在 vector 的第二个位置插入元素 10：

std::vector<int> myVector = {1, 2, 3};
auto it = myVector.begin() + 1;
myVector.insert(it, 10);

这里使用 myVector.begin() 获取 vector 的起始迭代器，然后通过 +1 移动到第二个位置，最后调用 insert() 函数插入元素 10。此时 myVector 变为 {1, 10, 2, 3}。

删除 vector 末尾的元素可以使用 pop_back() 函数。例如：

std::vector<int> myVector = {1, 2, 3};
myVector.pop_back();

此时 myVector 变为 {1, 2}。

要删除 vector 中指定位置的元素，可以使用 erase() 函数。例如，删除 vector 的第二个元素：

std::vector<int> myVector = {1, 2, 3};
auto it = myVector.begin() + 1;
myVector.erase(it);

此时 myVector 变为 {1, 3}。

常用成员函数

size() 函数用于获取 vector 中当前元素的数量。例如：

std::vector<int> myVector = {1, 2, 3};
std::cout << "The size of myVector is: " << myVector.size() << std::endl;

capacity() 函数返回 vector 当前分配的内存能够容纳的元素数量。vector 的容量通常大于或等于其当前大小，当 vector 的大小超过容量时，会重新分配内存，这是一个相对耗时的操作。例如：

std::vector<int> myVector = {1, 2, 3};
std::cout << "The capacity of myVector is: " << myVector.capacity() << std::endl;

resize() 函数可以改变 vector 的大小。如果新的大小大于当前大小，会在末尾添加默认值的元素；如果新的大小小于当前大小，会删除末尾多余的元素。例如：

std::vector<int> myVector = {1, 2, 3};
myVector.resize(5);

此时 myVector 变为 {1, 2, 3, 0, 0}。

clear() 函数用于清空 vector 中的所有元素，使其大小变为 0，但容量不变。例如：

std::vector<int> myVector = {1, 2, 3};
myVector.clear();

此时 myVector 为空，但如果再次添加元素，可能不需要重新分配内存（如果添加的元素数量不超过当前容量）。

list 的用法

定义与初始化

与 vector 类似，list 也有多种定义和初始化方式。定义一个空的 list 如下：

#include <list>
std::list<int> myList;

定义一个包含特定数量元素的 list，例如：

std::list<int> myList(5);

这里 myList 初始化为包含 5 个 int 类型的元素，默认值为 0（对于 int 类型）。

通过初始化列表初始化 list：

std::list<int> myList = {1, 2, 3, 4, 5};

或者

std::list<int> myList({1, 2, 3, 4, 5});

通过拷贝构造函数初始化 list：

std::list<int> sourceList = {1, 2, 3};
std::list<int> targetList(sourceList);

元素访问

由于 list 是链表结构，不支持通过下标访问元素。若要访问 list 中的元素，需要使用迭代器。例如，遍历 list 并输出所有元素：

std::list<int> myList = {1, 2, 3};
for (auto it = myList.begin(); it != myList.end(); ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

这里使用 myList.begin() 获取 list 的起始迭代器，myList.end() 获取末尾迭代器（指向最后一个元素的下一个位置），通过迭代器逐个访问并输出元素。

元素插入与删除

在 list 的开头插入元素可以使用 push_front() 函数。例如：

std::list<int> myList = {2, 3};
myList.push_front(1);

此时 myList 变为 {1, 2, 3}。

在 list 的末尾插入元素可以使用 push_back() 函数，与 vector 类似。例如：

std::list<int> myList = {1, 2};
myList.push_back(3);

此时 myList 变为 {1, 2, 3}。

在 list 的指定位置插入元素可以使用 insert() 函数。insert() 函数的第一个参数是插入位置的迭代器，后续参数是要插入的元素。例如，在 list 的第二个位置插入元素 10：

std::list<int> myList = {1, 2, 3};
auto it = myList.begin();
std::advance(it, 1);
myList.insert(it, 10);

这里通过 std::advance() 函数将迭代器 it 移动到第二个位置，然后调用 insert() 函数插入元素 10。此时 myList 变为 {1, 10, 2, 3}。

删除 list 开头的元素可以使用 pop_front() 函数。例如：

std::list<int> myList = {1, 2, 3};
myList.pop_front();

此时 myList 变为 {2, 3}。

删除 list 末尾的元素可以使用 pop_back() 函数。例如：

std::list<int> myList = {1, 2, 3};
myList.pop_back();

此时 myList 变为 {1, 2}。

要删除 list 中指定位置的元素，可以使用 erase() 函数。例如，删除 list 的第二个元素：

std::list<int> myList = {1, 2, 3};
auto it = myList.begin();
std::advance(it, 1);
myList.erase(it);

此时 myList 变为 {1, 3}。

常用成员函数

size() 函数用于获取 list 中当前元素的数量，与 vector 的 size() 函数功能类似。例如：

std::list<int> myList = {1, 2, 3};
std::cout << "The size of myList is: " << myList.size() << std::endl;

empty() 函数用于判断 list 是否为空，返回一个布尔值。例如：

std::list<int> myList;
if (myList.empty()) {
    std::cout << "The list is empty." << std::endl;
}

merge() 函数用于将一个已排序的 list 合并到当前 list 中，合并后的 list 也是已排序的。例如：

std::list<int> list1 = {1, 3, 5};
std::list<int> list2 = {2, 4, 6};
list1.merge(list2);

此时 list1 变为 {1, 2, 3, 4, 5, 6}，list2 变为空。

sort() 函数用于对 list 中的元素进行排序。例如：

std::list<int> myList = {3, 1, 2};
myList.sort();

此时 myList 变为 {1, 2, 3}。

性能比较

访问性能

vector 在访问元素方面具有显著优势。由于其元素在内存中连续存储，通过下标访问元素的时间复杂度为 O(1)，这意味着无论 vector 中有多少元素，访问特定位置元素的时间几乎是恒定的。例如，在一个包含百万个元素的 vector 中访问第 50 万个元素，计算机可以瞬间定位到该元素的内存地址并获取其值。

而 list 由于是链表结构，不支持直接通过下标访问元素。若要访问某个元素，必须从链表的头节点或尾节点开始，顺着指针逐个遍历，时间复杂度为 O(n)，其中 n 是链表中从起始节点到目标节点的元素个数。在一个长链表中，访问中间位置的元素可能需要遍历大量节点，花费较多时间。

插入与删除性能

在插入和删除操作上，list 表现出色。当在 list 中插入或删除元素时，只需调整相关节点的指针，时间复杂度为 O(1)。例如，在链表的开头插入一个新节点，只需创建新节点，将其指针指向原头节点，并更新头节点指针，这个过程与链表的长度无关。

vector 在插入和删除操作上相对复杂。在 vector 的末尾插入（push_back()）或删除（pop_back()）元素的时间复杂度通常为 O(1)，因为这只涉及到对最后一个元素的操作，不需要移动其他元素。但如果在 vector 的中间位置插入或删除元素，由于需要移动大量后续元素来保持内存的连续性，时间复杂度为 O(n)，其中 n 是需要移动的元素个数。例如，在一个包含百万个元素的 vector 中间插入一个元素，可能需要移动几十万甚至更多的元素，这是非常耗时的。

内存管理性能

vector 的内存管理方式相对简单。它预先分配一定的内存空间，当元素数量超过当前容量时，会重新分配更大的内存空间，并将原有的元素复制到新的内存空间中，这个过程称为内存重分配。内存重分配是一个相对耗时的操作，因为涉及到大量数据的复制。但由于 vector 元素连续存储，在内存利用效率上较高，缓存命中率也较高，对于大规模数据的处理可能更有优势。

list 的内存管理则更为灵活。每个节点单独分配内存，不需要连续的大块内存。这使得 list 在内存分配上更加容易，不会出现像 vector 那样因内存不足而需要重分配的情况。但由于每个节点除了存储数据外，还需要额外存储指向前驱和后继节点的指针，因此在内存占用上相对较大。

适用场景分析

vector 的适用场景

频繁随机访问：如果程序需要频繁地通过下标访问容器中的元素，例如实现一个数组式的查找表，vector 是最佳选择。比如在一个学生成绩管理系统中，要根据学生的编号快速查询其成绩，使用 vector 存储成绩数据可以快速定位到相应的成绩。
数据量相对稳定且内存连续需求高：当数据量在程序运行过程中变化不大，并且对内存连续性有要求时，vector 更为合适。例如在图形处理中，需要存储大量连续的像素点数据，vector 可以保证数据在内存中的连续性，提高缓存命中率，从而提升图形处理的效率。
简单的数据存储与遍历：对于一些简单的数据存储需求，并且遍历方式为顺序遍历，vector 既方便又高效。例如存储一个班级学生的年龄信息，顺序遍历输出每个学生的年龄，vector 可以很好地满足这种需求。

list 的适用场景

频繁插入和删除操作：如果程序中需要频繁地在容器的任意位置插入或删除元素，list 是更好的选择。例如在一个实时消息队列中，消息不断地在队列头部或尾部插入和删除，list 可以高效地处理这些操作，不会因大量元素移动而导致性能瓶颈。
数据量动态变化大：当数据量在程序运行过程中会有较大的动态变化，并且不希望因内存重分配而带来性能开销时，list 更为合适。例如在一个网络爬虫程序中，随着网页的不断抓取，需要存储的链接数量可能会不断变化，list 可以灵活地适应这种变化，不需要担心内存重分配的问题。
需要高效合并与排序：由于 list 提供了 merge() 和 sort() 等高效的成员函数，对于需要对数据进行合并和排序的场景，list 可以发挥其优势。例如在一个音乐播放列表管理程序中，需要将不同的播放列表合并并排序，list 可以方便地实现这些功能。

通过对 C++ 中 list 和 vector 的用法、性能以及适用场景的详细解析，程序员可以根据具体的需求选择最合适的容器，从而编写出高效、稳定的程序。在实际应用中，深入理解这两种容器的特性，合理运用它们，对于提升程序的性能和质量至关重要。