深度剖析C++STL：手持list利剑，破除编程重重难题（上）

🕗 发布于 2024-11-19 11:17 c++ 开发语言

前言：

C++ 标准模板库（STL）中的 list 容器是一个双向链表结构，它提供了高效的插入和删除操
作。与 vector 不同，list 中的元素不是连续存储的，因此可以在任何位置高效插入和删除元素，而无需移动其他元素。虽然它在随机访问方面不如 vector 高效，但在大量的插入和删除操作场景中具有不可替代的优势。

本文将通过详细的示例代码，从基础到进阶，逐步讲解如何使用 C++ 中的 list 容器，并探讨其特性与常用操作。

一. list容器简介

1.1 容器概述

C++ 提供了丰富的标准模板库 (STL)，其中包括顺序容器（如 vector、deque）和关联容器（如 map、set）。list 是一种链表结构的顺序容器，它的底层实现是双向链表。这使得 list 在插入和删除操作上比 vector 更加高效，但由于不支持随机访问，因此访问特定位置的元素时效率较低。

1.2 list的特点

双向链表：list 底层是一个双向链表，能够高效地进行插入和删除操作。
不支持随机访问：由于链表的结构特点，list 只能顺序访问，随机访问效率低下。
动态增长：list 不需要预留空间，它会根据需要动态分配内存。

代码示例如下：

#include <list>
#include <iostream>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};
    for (int val : lst) {
        cout << val << " ";
    }
    return 0;
}

二. list的构造方法

2.1 常见构造函数

C++ list 提供了多种构造函数，允许用户根据不同需求初始化链表。

2.2 具体文档链接

https://cplusplus.com/reference/list/list/list/

三. list迭代器的玩转使用

list 支持多种迭代器类型，允许我们遍历、访问和修改链表中的元素。迭代器可以看作指向 list 中节点的指针，遍历时可以用迭代器依次访问链表中的每一个节点。

3.1 常见迭代器相关接口类型

3.2 分别使用正向和反向迭代器进行遍历

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    // 使用正向迭代器遍历
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        cout << *it << " ";  // 输出: 1 2 3 4 5
    }
    cout << endl;

    // 使用反向迭代器遍历
    for (auto rit = lst.rbegin(); rit != lst.rend(); ++rit) {
        cout << *rit << " ";  // 输出: 5 4 3 2 1
    }
    cout << endl;

    return 0;
}

注意：反向迭代器的使用无需用rend到rbegin进行遍历，且遍历不会改变链表本身元素的顺序。

3.3 具体文档链接

https://cplusplus.com/reference/list/list/begin/

四. list的容积与大小操作

4.1 容积管理相关接口

list 提供了常用的容积管理接口，方便用户操作链表的大小和判断链表状态。

4.2 容积操作实例

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    cout << "Size: " << lst.size() << endl; // 输出当前元素个数
    cout << "Is empty: " << (lst.empty() ? "Yes" : "No") << endl; // 判断是否为空

    lst.resize(3); // 调整大小为3，保留前3个元素

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 2 3
    }

    return 0;
}

4.3 具体文档链接

C++ Reference: list size

五. list的元素访问，插入，修改与删除

5.1 访问操作与代码示例

list提供了两个方法直接访问头部和尾部的元素。

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    cout << "First element: " << lst.front() << endl; // 访问第一个元素
    cout << "Last element: " << lst.back() << endl;   // 访问最后一个元素

    return 0;
}

具体文档链接如下：

https://cplusplus.com/reference/list/list/front/

5.2 插入操作

list 容器提供了多种插入操作，包括在前部、尾部插入元素，或在指定位置插入。与 vector 不同的是，list 插入时不需要移动其他元素，只修改指针，因此插入效率非常高。

5.2.1 push_front()与push_back()使用示例

push_front() 和 push_back() 是将元素插入到链表前部和尾部的常用方法。由于 list 是双向链表，头部和尾部操作的效率都非常高，为 O(1)。

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3};

    // 在前部插入元素
    lst.push_front(0);

    // 在末尾插入元素
    lst.push_back(4);

    for (int val : lst) {
        cout << val << " ";  // 输出: 0 1 2 3 4
    }

    return 0;
}

5.2.2 insert()使用示例

`insert()` 用于在链表中指定位置插入元素。该方法需要提供一个迭代器指向要插入的位置。

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 3, 4};

    // 在第二个位置插入2
    auto it = lst.begin();
    ++it;
    lst.insert(it, 2);

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 2 3 4 
    }

    return 0;
}

5.3 插入时的相关问题

迭代器失效：在 list 中进行插入操作时，插入不会使已有迭代器失效，因为 list 是双向链表，插入时只修改指针，且返回值为最近插入元素的第一个的地址，

尾部插入效率：在链表尾部插入元素的效率始终为 O(1)，无需移动其他元素，这点不同于 vector。

插入到特定位置的效率：虽然 insert() 操作本身是 O(1)，但查找特定插入位置的时间复杂度是 O(n)，这取决于迭代器的获取方法。

具体文档链接

https://cplusplus.com/reference/list/list/insert/

5.4 删除操作

list 提供了多种删除元素的方式，包括从前部和尾部删除，删除指定位置的元素，以及一次性清空整个链表。

5.4.1 删除list中的首尾元素示例

pop_front() 和 pop_back() 用于删除 list 中的第一个或最后一个元素。与插入操作类似，这两种操作的时间复杂度都是 O(1)，不会影响其他元素的指针。

代码示例如下：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    // 删除第一个元素
    lst.pop_front();

    // 删除最后一个元素
    lst.pop_back();

    for (int val : lst) {
        cout << val << " ";  // 输出: 2 3 4
    }

    return 0;
}

5.4.2 删除list中指定位置的元素示例

erase() 用于删除指定位置的元素。它需要提供一个指向该位置的迭代器。

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    // 查找要删除的元素
    auto it = lst.begin();
    advance(it, 2);  // 移动到第三个元素

    // 删除第三个元素
    lst.erase(it);

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 2 4 5
    }

    return 0;
}

注意：erase会返回删除元素的下一个元素的迭代器。

5.5 list的一键清空

clear() 是一种非常彻底的清除操作，它会删除 list 中的所有元素。值得注意的是，clear() 仅会删除有效节点，不会删除链表的头节点（即 list 对象本身）。

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    // 清空 list
    lst.clear();

    cout << "Size after clear: " << lst.size() << endl;  // 输出: 0
    cout << "Is list empty? " << (lst.empty() ? "Yes" : "No") << endl;  // 输出: Yes

    return 0;
}

5.6 删除时的相关问题

迭代器失效：在 list 中，删除操作只会导致指向被删除元素的迭代器失效，其他迭代器不受影响。删除后如果需要继续使用迭代器，应该使用 erase() 的返回值，指向下一个有效元素。

clear() 是否删除头节点：clear() 不会删除 list 的头节点。调用 clear() 后，list 对象依然存在，只是里面的所有元素被删除，list 的结构保持完好。

具体文档链接：

https://cplusplus.com/reference/list/list/clear/

https://cplusplus.com/reference/list/list/erase/

https://cplusplus.com/reference/list/list/pop_back/

5.7 修改操作

通过迭代器或者 list 提供的访问接口，用户可以直接修改链表中的元素。由于 list 不支持随机访问，所以修改操作通常需要遍历元素。

5.7.1 修改list的首尾元素示例

通过 front() 和 back()，可以分别访问并修改 list 中的第一个和最后一个元素。修改操作的时间复杂度为 O(1)。

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    // 修改第一个元素
    lst.front() = 10;

    // 修改最后一个元素
    lst.back() = 20;

    for (int val : lst) {
        cout << val << " ";  // 输出: 10 2 3 4 20
    }

    return 0;
}

5.7.2 通过迭代器进行修改示例

由于 list 不支持随机访问，修改中间位置的元素需要通过迭代器遍历找到目标位置。

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    // 使用迭代器修改第三个元素
    auto it = lst.begin();
    advance(it, 2);  // 移动到第三个元素
    *it = 30;

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 2 30 4 5
    }

    return 0;
}

5.8 修改操作的常见问题

效率问题：由于 list 是链表结构，访问中间元素时无法像 vector 一样通过下标随机访问，而是必须通过迭代器进行遍历，时间复杂度为 O(n)。

advance() 函数用于将迭代器向前或向后移动指定的距离，这是 list 中最常用的访问与修改元素方式之一。由于 list 不能通过下标随机访问，迭代器的使用显得尤为重要，同时需要注意下标是从0开始。

避免无效访问：通过迭代器进行修改时，确保在修改过程中没有删除操作，否则迭代器可能失效，导致未定义行为。

六. list迭代器的失效问题

list 的底层实现为双向链表，因此与 vector 不同，list 的插入和删除操作不会导致整体迭代器失效。具体来说：

插入操作：不会导致现有迭代器失效。
删除操作：仅导致被删除元素的迭代器失效，其他迭代器不会受影响。

6.1 删除操作导致的迭代器失效

删除操作会使指向被删除元素的迭代器失效，如果在删除元素后继续使用失效的迭代器，将会导致程序的未定义行为。因此，在执行删除操作后，我们必须重新更新迭代器。

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    // 查找并删除元素3
    auto it = lst.begin();
    while (it != lst.end()) {
        if (*it == 3) {
            it = lst.erase(it);  // 删除元素并获取下一个有效迭代器
        } else {
            ++it;  // 继续遍历
        }
    }

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 2 4 5
    }

    return 0;
}

注意：上述为正确处理方式，下面我们来看一个迭代器失效错误处理的例子。

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    auto it = lst.begin();
    while (it != lst.end()) {
        if (*it == 3) {
            lst.erase(it);  // 删除元素，但未更新迭代器
            ++it;           // 错误：it 已经失效，导致直接跳过4这个元素
        } else {
            ++it;
        }
    }

    return 0;
}

且此时代码不一定会报错，但是输出却无法达到目标结果。

6.2 具体文档链接

https://cplusplus.com/reference/list/list/erase/

七. list的其他常用接口

7.1 splice()操作修改指向

splice() 是 list 特有的操作，它允许我们将一个 list 中的元素直接拼接到另一个 list 中，而不会重新分配内存或复制元素。该操作非常高效，因为它仅修改链表的指针。

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst1 = {1, 2, 3};
    list<int> lst2 = {4, 5, 6};

    // 将 lst2 的元素拼接到 lst1 的末尾
    lst1.splice(lst1.end(), lst2);

    for (int val : lst1) {
        cout << val << " ";  // 输出: 1 2 3 4 5 6
    }

    cout << "\nList 2 size: " << lst2.size() << endl; // 输出: 0 (lst2 已被清空)

    return 0;
}

splice() 可以高效地将一个链表中的元素移动到另一个链表中，它不会复制元素，也不会破坏链表的连续性。

具体文档链接：

https://cplusplus.com/reference/list/list/splice/

7.2 merge()操作合并有序链表

merge() 函数用于将两个已经排序好的 list 合并为一个有序的 list。它会自动按照升序或自定义的比较规则合并两个链表。

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst1 = {1, 3, 5};
    list<int> lst2 = {2, 4, 6};

    // 合并两个已排序的链表
    lst1.merge(lst2);

    for (int val : lst1) {
        cout << val << " ";  // 输出: 1 2 3 4 5 6
    }

    return 0;
}

merge() 会将两个有序链表合并成一个新的有序链表，并且不会对原链表进行元素的复制，只是对链表节点进行了重新连接。

具体文档链接：

https://cplusplus.com/reference/list/list/merge/

7.3 reverse()操作反转链表

reverse() 函数用于将 list 的顺序进行反转。该操作不会创建新的链表，而是直接修改现有链表的链接顺序。

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

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

    for (int val : lst) {
        cout << val << " ";  // 输出: 5 4 3 2 1
    }

    return 0;
}

7.4 swap()操作交换两个链表的内容

swap() 函数用于交换两个 list 容器的内容。这个操作非常高效，因为 list 只交换内部的指针和相关数据，而不会实际移动或复制元素。

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst1 = {1, 2, 3};
    list<int> lst2 = {4, 5, 6};

    // 交换两个 list
    lst1.swap(lst2);

    cout << "List 1: ";
    for (int val : lst1) {
        cout << val << " ";  // 输出: 4 5 6
    }

    cout << "\nList 2: ";
    for (int val : lst2) {
        cout << val << " ";  // 输出: 1 2 3
    }

    return 0;
}

7.5 remove()操作移除指定元素

remove() 函数用于从 list 中移除所有与指定值相等的元素。它会遍历整个链表，删除所有匹配的元素。

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 2, 5};

    // 移除值为2的所有元素
    lst.remove(2);

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 3 4 5
    }

    return 0;
}

7.6 remove_if()操作根据规则移除指定元素

remove_if() 函数根据给定的条件（谓词）移除链表中符合条件的所有元素。与 remove() 不同，它可以使用自定义的判断规则来删除元素。

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

// 判断条件：删除所有偶数
bool isEven(int n) {
    return n % 2 == 0;
}

int main() {
    list<int> lst = {1, 2, 3, 4, 5, 6};

    // 删除所有偶数元素
    lst.remove_if(isEven);

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 3 5
    }

    return 0;
}

7.7 `emplace()` 和 `emplace_back()` 操作进行直接构造

emplace() 和 emplace_back() 是 list 提供的构造元素的方法，它们允许我们直接在链表中构造元素，避免不必要的复制操作。相比 push_back()，emplace_back() 更加高效，尤其是在插入复杂对象时。

#include <iostream>
#include <list>
using namespace std;

struct Point {
    int x, y;
    Point(int a, int b) : x(a), y(b) {}
};

int main() {
    list<Point> points;

    // 在 list 中直接构造元素
    points.emplace_back(1, 2);  // 在末尾构造元素 (1, 2)
    points.emplace(points.begin(), 3, 4);  // 在起始位置构造元素 (3, 4)

    for (const auto& pt : points) {
        cout << "(" << pt.x << ", " << pt.y << ") ";  // 输出: (3, 4) (1, 2)
    }

    return 0;
}

具体文档链接：

https://cplusplus.com/reference/list/list/emplace/

八. list的排序与去重

8.1 set()操作排序

list 提供了 sort() 函数来对链表进行排序。由于 list 不支持随机访问，因此它使用的排序算法是稳定的归并排序，性能为 O(N log N)。

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {5, 2, 9, 1, 5, 6};

    // 对链表进行排序
    lst.sort();

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 2 5 5 6 9
    }

    return 0;
}

8.1.1 使用自定义函数(仿函数)进行排序

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

bool customCompare(int a, int b) {
    return a > b;  // 降序比较
}

int main() {
    list<int> lst = {5, 2, 9, 1, 5, 6};

    // 使用自定义比较函数进行降序排序
    lst.sort(customCompare);

    for (int val : lst) {
        cout << val << " ";  // 输出: 9 6 5 5 2 1
    }

    return 0;
}

8.2 unique()操作去重

unique() 函数用于去除链表中相邻的重复元素。它会比较相邻的两个元素，如果它们相等，则删除后一个元素。

具体代码示例如下：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 1, 2, 3, 3, 4, 5, 5};

    // 去除相邻的重复元素
    lst.unique();

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 2 3 4 5
    }

    return 0;
}

8.2.1 使用自定义函数(仿函数)进行去重

#include <iostream>
#include <list>
using namespace std;

bool customEqual(int a, int b) {
    return a % 2 == b % 2;  // 自定义规则：移除相邻的偶数/奇数
}

int main() {
    list<int> lst = {1, 3, 2, 4, 5, 6};

    // 使用自定义规则去重
    lst.unique(customEqual);

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 2 5
    }

    return 0;
}

小结：

本篇详细介绍了STL中list的相关接口，就其含义和使用给出了详细的具体示例，希望能对大家的学习产生帮助和收获，欢迎各位佬前来支持斧正！！！

原文地址：https://blog.csdn.net/2303_81060385/article/details/143457361

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：每日计划-1118
下一篇：掌控 Solidity：事件日志、继承和接口的深度解析

鸿蒙进阶篇-TextInput&TextArea和Checkbox
在鸿蒙开发中，TextInput 用于单行文本输入，TextArea 用于多行文本输入，Checkbox 则是用于多项选择的复选框组件。
阅读更多2024-11-21
MySQL45讲第二十六讲备库为什么会延迟好几个小时？——阅读总结
在MySQL数据库的主备架构中，备库延迟是一个需要重点关注的问题。它可能影响系统的可用性和数据的一致性，尤其是在主库压力较大时，备库延迟可能达到数小时甚至永远无法追上主库。今天，我们将深入探讨MySQ
阅读更多2024-11-21
快速简单的视频下载器——lux
在学习之余，发现了一个简单并且高效的视频下载器lux,能够帮你快速且高效的下载文件（不仅仅是视频可以），所以写了一篇博客分享lux的相关内容这个简单并且高效的视频下载器lux，一定会提高你的下载效率的
阅读更多2024-11-21
XGBOOST、LightGBM、CATBoost
本文介绍了三种 GBDT 的优化算法，可以根据实际情况进行选择。
阅读更多2024-11-21
【JAVA】Java基础—面向对象编程：常用API与数据结构—字符串、数组的使用
在Java编程中，字符串和数组是两个非常基础且重要的数据结构。它们在日常开发中无处不在，理解它们的使用及其背后的理论知识是成为一名合格Java开发者的必经之路。：可以将字符串比作一本书的章节。每个章节
阅读更多2024-11-21
Docker-Compose 快速部署安装 Nginx 或其他应用
测试部署的 Nginx 是否运行正常，可以在浏览器中访问 Nginx 所在的 IP 或端口，确保能够看到默认的 Nginx 页面。（如果你安装的是 Docker CE）。将下载的 Docker-Com
阅读更多2024-11-21
微信小程序申请getlocation权限
2、如果小程序没有导航功能。可以使用wx.openLocation写一个导航页面功能，以便进行权限申请。所以需要申请getlocation权限的开启。体验版没有申请开启不影响使用，但是上线提审必须申请
阅读更多2024-11-21
(RK3566驱动开发 - 2）.IIC驱动
【代码】(RK3566驱动开发 - 2）.IIC驱动。
阅读更多2024-11-21
04 搭建linux驱动开发环境
虽然 petalinux 功能很全面，但是其编译速度较慢，不适用于驱动调试阶段（因为驱动调试阶段会频繁修改驱动模块、内核、设备树等），因此本章将采用分步编译的方式来编译启动开发板所需要的各种镜像文件，
阅读更多2024-11-21
2025蓝桥杯（单片机）备赛--扩展外设之NE555的使用及定时器1的详细讲解（十）
超详细的定时器555讲解
阅读更多2024-11-21

深度剖析C++STL：手持list利剑，破除编程重重难题（上）

一. list容器简介

1.1 容器概述

1.2 list的特点

二. list的构造方法

2.1 常见构造函数

2.2 具体文档链接

三. list迭代器的玩转使用

3.1 常见迭代器相关接口类型

3.2 分别使用正向和反向迭代器进行遍历

3.3 具体文档链接

四. list的容积与大小操作

4.1 容积管理相关接口

4.2 容积操作实例

4.3 具体文档链接

五. list的元素访问，插入，修改与删除

5.1 访问操作与代码示例

5.2 插入操作

5.2.1 push_front()与push_back()使用示例

5.2.2 insert()使用示例

insert() 用于在链表中指定位置插入元素。该方法需要提供一个迭代器指向要插入的位置。

5.3 插入时的相关问题

5.4 删除操作

5.4.1 删除list中的首尾元素示例

5.4.2 删除list中指定位置的元素示例

5.5 list的一键清空

5.6 删除时的相关问题

5.7 修改操作

5.7.1 修改list的首尾元素示例

5.7.2 通过迭代器进行修改示例

5.8 修改操作的常见问题

六. list迭代器的失效问题

6.1 删除操作导致的迭代器失效

6.2 具体文档链接

七. list的其他常用接口

7.1 splice()操作修改指向

7.2 merge()操作合并有序链表

7.3 reverse()操作反转链表

7.4 swap()操作交换两个链表的内容

7.5 remove()操作移除指定元素

7.6 remove_if()操作根据规则移除指定元素

7.7 emplace() 和 emplace_back() 操作进行直接构造

八. list的排序与去重

8.1 set()操作排序

8.1.1 使用自定义函数(仿函数)进行排序

8.2 unique()操作去重

8.2.1 使用自定义函数(仿函数)进行去重

相关文章

`insert()` 用于在链表中指定位置插入元素。该方法需要提供一个迭代器指向要插入的位置。

7.7 `emplace()` 和 `emplace_back()` 操作进行直接构造