移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——7.list(无习题）

C++ 中的

list

容器详细总结

1. 什么是

list

？

list文档

list

是 C++ 标准模板库 (STL) 中的一种容器类型，采用双向链表的数据结构来存储数据。双向链表意味着每个节点包含一个数据元素和两个指针，分别指向前一个和后一个节点。

list

适用于需要频繁进行插入和删除操作的场景，其效率比动态数组（如

vector

）更高，但不支持随机访问。与

vector

使用连续内存存储不同，

list

的节点在内存中并不连续存储。

1.1 双向链表简介

双向链表是一种链式存储结构，与单向链表相比，它多了一个指向前驱节点的指针。这样设计的优点是，可以从任意一个节点向前或向后遍历链表，操作更加灵活。每个节点包含三个部分：

• 数据部分：存储节点的数据元素。
• 前驱指针：指向前一个节点。
• 后继指针：指向后一个节点。

这种结构使得插入和删除节点的操作效率较高，因为只需修改相关节点的前驱和后继指针，而不需要移动其他节点的数据。

2.

list

的特点与优缺点

2.1

list

的特点

• 双向链表结构：list 使用双向链表来存储数据，因此插入和删除操作的时间复杂度为 O(1)。
• 不支持随机访问：list 的元素在内存中不是连续存储的，无法通过下标直接访问某个元素，需要通过迭代器来遍历，访问特定位置元素的时间复杂度为 O(n)。
• 动态大小：list 的大小可以根据需要动态调整，插入和删除元素不会像 vector 那样引发频繁的内存重新分配。
• 双向迭代器：list 提供双向迭代器，可以在链表中向前或向后遍历，灵活度较高。

2.2

list

的优点

• 插入和删除效率高：由于 list 的每个节点都包含前驱和后继指针，插入或删除一个节点时，只需要更新相邻节点的指针，因此插入和删除操作的时间复杂度为 O(1)。
• 动态增长：list 在进行插入和删除时，不需要担心内存容量的问题，因为每次操作都会动态分配或释放内存，大小灵活调整。
• 低内存拷贝开销：当插入或删除元素时，不需要像 vector 一样移动其他元素的数据，因此不会产生大量的内存拷贝开销。

2.3

list

的缺点

• 不支持随机访问：list 不能通过下标访问元素，访问特定位置的元素需要从头遍历到该位置，时间复杂度为 O(n)。对于需要频繁访问特定位置元素的场景，list 并不适合。
• 内存开销较大：list 中的每个节点除了存储数据外，还需要存储两个指针，这使得 list 的内存开销比 vector 大。此外，节点的动态分配也会引入额外的内存管理开销。
• 缓存不友好：由于 list 的节点在内存中是分散存储的，无法利用 CPU 缓存的局部性原理，因此在遍历大量数据时，性能不如连续存储的容器（如 vector）。

3.

list

的常用操作与函数

3.1 创建与初始化

创建和初始化

C++ 中的

list

容器可以通过多种方式创建和初始化，以下是一些常见的方式：

#include<list>intmain(){
    std::list<int> list1;// 创建空的 list
    std::list<int>list2(5);// 创建包含 5 个默认元素的 list，值为 0
    std::list<int>list3(5,10);// 创建包含 5 个值为 10 的元素的 list
    std::list<int> list4 ={1,2,3,4,5};// 使用列表初始化return0;}

3.2 增加元素

• **push_back(value)**：在 list 的末尾添加一个元素。

list1.push_back(10);// 在末尾添加 10

• **push_front(value)**：在 list 的头部添加一个元素。

list1.push_front(20);// 在头部添加 20

• **emplace_back(args...) 和 emplace_front(args...)**：分别在末尾或头部原地构造元素。与 push_back 和 push_front 相比，emplace 系列函数可以避免不必要的拷贝和移动。

list1.emplace_back(30);// 在末尾原地构造 30
list1.emplace_front(40);// 在头部原地构造 40

• **insert(iterator, value)**：在指定位置插入元素。

list1.insert(list1.begin(),50);// 在 list 的开头插入 50

3.3 删除元素

• **pop_back()**：删除 list 末尾的元素。

list1.pop_back();// 删除末尾元素

• **pop_front()**：删除 list 头部的元素。

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

• **erase(iterator)**：删除指定位置的元素。

list1.erase(list1.begin());// 删除第一个元素

• **clear()**：清空 list 中所有元素。

list1.clear();// 清空容器

3.4 访问元素

• 由于 list 不支持随机访问，因此无法使用下标直接访问元素。必须通过迭代器来遍历整个链表。

for(auto it = list1.begin(); it != list1.end();++it){
    std::cout <<*it <<" ";}

3.5 迭代器的使用

• begin(), **end()**：获取指向第一个元素和末尾后一个位置的迭代器。

for(auto it = list1.begin(); it != list1.end();++it){
    std::cout <<*it <<" ";}

• rbegin(), **rend()**：获取反向迭代器，从尾部向头部遍历。

for(auto rit = list1.rbegin(); rit != list1.rend();++rit){
    std::cout <<*rit <<" ";}

3.6 容量相关函数

• **size()**：获取当前元素的数量。
• **empty()**：判断 list 是否为空。

std::cout <<"Size: "<< list1.size()<<"\n";
std::cout <<"Is empty: "<< list1.empty()<<"\n";

4.

list

的内部机制与性能分析

4.1 双向链表结构

list

是由多个节点组成的双向链表，每个节点包含一个数据元素和两个指针，分别指向前一个节点和后一个节点。这种结构使得在链表中插入和删除元素的时间复杂度为 O(1)，而访问特定位置的元素需要从头遍历，时间复杂度为 O(n)。

4.2 内存分配与管理

由于

list

的节点在内存中是分散存储的，因此每次插入或删除节点时，

list

都会进行动态内存分配或释放。相比于

vector

的连续存储结构，这种方式避免了频繁的内存重新分配，但也带来了较高的内存管理开销。此外，由于每个节点还需要存储前驱和后继指针，因此

list

的内存占用比

vector

更大。

4.3 缓存性能

list

的节点在内存中是分散存储的，这意味着在访问链表元素时，无法充分利用 CPU 缓存的局部性原理。因此，对于需要遍历大量数据的场景，

list

的性能不如使用连续内存的

vector

。如果应用程序对缓存性能要求较高，建议使用

vector

之类的连续存储容器。

5.

list

的高级操作

5.1 合并与排序

• **merge(other_list)**：将另一个 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}

• **sort()**：对 list 中的元素进行排序。

list1.sort();// 对 list1 进行升序排序

• **reverse()**：将 list 中的元素顺序反转。

list1.reverse();// 反转 list1 中的元素

5.2 移除与唯一化

• **remove(value)**：移除 list 中所有等于指定值的元素。

list1.remove(3);// 移除所有值为 3 的元素

• **remove_if(predicate)**：根据给定的条件移除元素。

list1.remove_if([](int value){return value %2==0;});// 移除所有偶数元素

• **unique()**：移除连续的重复元素，使每个相同的元素只保留一个。

list1.unique();// 移除连续的重复元素

6.

list

与其他容器的对比

6.1 与

vector

的对比

• 存储结构：vector 使用连续内存存储，支持 O(1) 时间复杂度的随机访问；list 使用链表存储，不支持随机访问。
• 插入和删除操作：vector 在末尾插入和删除的效率较高，但在中间位置插入和删除需要移动大量元素，时间复杂度为 O(n)。list 的插入和删除操作在任何位置都是 O(1)。
• 内存使用：vector 的内存使用更加紧凑，而 list 由于存储了前驱和后继指针，内存占用更大。
• 遍历性能：vector 的连续内存使得遍历性能更好，能够更好地利用 CPU 缓存，而 list 的遍历性能相对较差。

6.2 与

deque

的对比

• 存储结构：deque（双端队列）由多个连续内存块组成，支持快速的头尾插入和删除操作，而 list 是链式存储。
• 访问性能：deque 支持常数时间的随机访问，而 list 只能通过迭代器顺序访问。
• 插入和删除操作：deque 在头尾的插入和删除效率高，但在中间位置插入和删除的性能不如 list，尤其是在需要频繁插入和删除的场景中，list 更加适合。

6.3 与

forward_list

的对比

• 链表类型：forward_list 是单向链表，只能向前遍历；list 是双向链表，支持向前和向后遍历。
• 内存开销：forward_list 的每个节点只包含一个指针（指向下一个节点），因此内存开销比 list 小。
• 操作灵活性：由于 list 是双向链表，插入和删除操作更加灵活，尤其是在需要从尾部进行操作时。forward_list 只适用于简单的单向遍历场景。

7. 使用建议

• 频繁插入和删除：如果应用程序中需要频繁地在容器的中间位置进行插入和删除操作，list 是一个很好的选择，因为其时间复杂度为 O(1)。
• 随机访问需求低：如果不需要频繁访问特定位置的元素，而只是顺序遍历或插入和删除，list 的链表结构可以很好地满足需求。
• 内存敏感场景：在需要节省内存的场景中，尽量避免使用 list，因为其节点内存开销较大。对于简单数据类型，使用 vector 或 deque 可能更加合适。

8. 示例代码

下面是一个完整的示例代码，展示了

list

的常用操作以及高级功能：

#include<iostream>#include<list>intmain(){// 创建 list 并初始化
    std::list<int> myList ={1,2,3,4,5};// 添加元素
    myList.push_back(6);// 在末尾添加元素
    myList.push_front(0);// 在头部添加元素// 遍历 list
    std::cout <<"Elements: ";for(int val : myList){
        std::cout << val <<" ";}
    std::cout << std::endl;// 删除元素
    myList.pop_back();// 删除末尾元素
    myList.pop_front();// 删除头部元素
    myList.erase(++myList.begin());// 删除第二个元素// 查看大小
    std::cout <<"Size: "<< myList.size()<< std::endl;// 清空 list
    myList.clear();
    std::cout <<"Size after clear: "<< myList.size()<< std::endl;// 合并两个有序 list
    std::list<int> list1 ={1,3,5};
    std::list<int> list2 ={2,4,6};
    list1.merge(list2);
    std::cout <<"Merged list: ";for(int val : list1){
        std::cout << val <<" ";}
    std::cout << std::endl;// 对 list 进行排序和反转
    list1.push_back(0);
    list1.sort();
    list1.reverse();
    std::cout <<"Reversed list: ";for(int val : list1){
        std::cout << val <<" ";}
    std::cout << std::endl;// 移除元素
    list1.remove(3);// 移除所有值为 3 的元素
    list1.remove_if([](int value){return value %2==0;});// 移除所有偶数元素
    std::cout <<"List after removal: ";for(int val : list1){
        std::cout << val <<" ";}
    std::cout << std::endl;return0;}

9. 总结

C++ 中的

list

容器是一种基于双向链表的数据结构，适合需要频繁插入和删除元素的场景。

list

提供了灵活的增删操作和双向迭代器，能够在常数时间内完成插入和删除操作。然而，由于其不支持随机访问且内存开销较大，因此在需要频繁访问特定位置或对内存使用敏感的场景中，

list

并不是最佳选择。对于不同的应用需求，合理选择合适的容器（如

vector

、

deque

等）能够显著提升程序的性能和资源利用率。