【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器2-阿里云开发者社区

【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器1:https://developer.aliyun.com/article/1617548

6.3 修改操作

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

方法名	功能描述
`front()`	返回 `list` 中第一个元素
`back()`	返回 `list` 中最后一个元素
迭代器	通过迭代器访问修改元素

6.3.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;
}

6.3.2 示例：通过迭代器修改 `list` 中的元素

由于 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;
}

6.3.3 修改操作的常见问题

效率问题：由于 list 是链表结构，访问中间元素时无法像 vector 一样通过下标随机访问，而是必须通过迭代器进行遍历，时间复杂度为 O(n)。
advance() 函数用于将迭代器向前或向后移动指定的距离，这是 list 中最常用的访问与修改元素方式之一。由于 list 不能通过下标随机访问，迭代器的使用显得尤为重要。

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

第七章：`list` 的迭代器失效问题

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

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

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

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

7.1.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;
}

在上面的代码中，erase() 函数会返回一个指向被删除元素之后的迭代器，因此我们使用该返回值继续遍历。这是一种常见的迭代器删除操作的最佳实践，可以避免迭代器失效问题。

7.1.2 错误示例：删除后不更新迭代器

#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 已经失效，导致未定义行为
        } else {
            ++it;
        }
    }

    return 0;
}

在这个错误的示例中，删除操作使 it 失效，但我们在下一个循环中继续使用了失效的 it，这会导致未定义行为，可能会引发程序崩溃。

7.1.3 相关文档

C++ Reference: list erase

第八章：`list` 常见的其他修改操作

8.1 `splice()` 操作

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

方法名	功能描述
`splice(position, x)`	将 `list x` 的所有元素插入到当前 `list` 中
`splice(position, x, it)`	将 `list x` 中的 `it` 指定的元素插入到当前 `list` 中

splice(position, x, first, last) 将 x 中 [first, last) 区间的元素插入当前 list

8.1.1 示例：使用 `splice()` 操作

#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() 可以高效地将一个链表中的元素移动到另一个链表中，它不会复制元素，也不会破坏链表的连续性。

8.1.2 相关文档

C++ Reference: list splice

8.2 `merge()` 操作

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

方法名	功能描述

`merge(list& x)`	将已排序的 `x` 合并到当前链表中
`merge(list& x, Compare comp)`	使用自定义比较函数 `comp` 合并 `x`

8.2.1 示例：使用 `merge()` 操作

#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() 会将两个有序链表合并成一个新的有序链表，并且不会对原链表进行元素的复制，只是对链表节点进行了重新连接。

8.2.2 相关文档

C++ Reference: list merge

第九章：`list` 的排序与去重

9.1 `sort()` 操作

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

方法名	功能描述
`sort()`	默认按照升序排序
`sort(Compare comp)`	使用自定义比较函数 `comp` 进行排序

9.1.1 示例：对 `list` 进行排序

#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;
}

9.1.2 使用自定义比较函数排序

#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;
}

9.2 `unique()` 操作

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

方法名	功能描述
`unique()`	移除相邻的重复元素
`unique(BinaryPredicate p)`	使用自定义的比较规则 `p` 移除相邻的元素

9.2.1 示例：使用 `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;
}

9.2.2 使用自定义规则去重

#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;
}

第十章：`list` 的其他操作

10.1 `reverse()` 操作

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

方法名	功能描述
`reverse()`	将 `list` 中的元素顺序反转

10.1.1 示例：反转 `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;
}

通过 reverse() 函数，原本顺序存储的元素将被反转，链表中的第一个元素变为最后一个，最后一个变为第一个。

10.1.2 相关文档

C++ Reference: list reverse

10.2 `swap()` 操作

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

方法名	功能描述
`swap(list& x)`	交换当前 `list` 与 `x` 中的元素

10.2.1 示例：交换两个 `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;
}

swap() 是一种非常高效的操作，尤其是在需要大量数据交换时，可以避免拷贝开销。

11.2.2 相关文档

C++ Reference: list swap

10.3 `remove()` 操作

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

方法名	功能描述
`remove(const T& val)`	删除所有与 `val` 相等的元素

10.3.1 示例：移除指定值的元素

#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;
}

remove() 函数会移除链表中所有等于指定值的元素。由于链表是双向的，这种操作不会导致大量的数据移动，只是修改指针指向。

10.3.2 相关文档

C++ Reference: list remove

10.4 `remove_if()` 操作

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

方法名	功能描述
`remove_if(UnaryPredicate p)`	移除所有满足谓词 `p` 条件的元素

10.4.1 示例：使用 `remove_if()` 删除符合条件的元素

#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;
}

在这个例子中，remove_if() 根据自定义的谓词函数 isEven() 删除了链表中所有的偶数元素。

10.4.2 相关文档

C++ Reference: list remove_if

10.5 `emplace()` 和 `emplace_back()` 操作

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

方法名功能描述

`emplace(position, args...)`	在指定位置直接构造元素
`emplace_back(args...)`	在链表末尾直接构造元素，避免复制构造开销

10.5.1 示例：使用 `emplace()` 和 `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;
}

emplace() 和 emplace_back() 提供了更灵活和高效的插入方式，尤其在处理复杂对象时可以减少额外的构造和复制操作。

10.5.2 相关文档

C++ Reference: list emplace

第十一章：`list` 的内存管理

11.1 `shrink_to_fit()` 操作

list 不像 vector 那样需要经常处理容量管理和扩容问题，因为它的底层实现是链表，元素的插入和删除并不会影响容器的容量分配。但 STL 容器通常提供 shrink_to_fit() 函数来缩减不必要的内存开销，而 list 没有此函数，因为链表结构本身并不涉及到多余的容量分配问题。

写在最后

本文详尽介绍了 C++ STL 中 list 容器的各类操作。我们从基本的构造、元素访问、容量管理，到迭代器、修改操作、排序与去重等高级功能，深入讲解了如何使用 list 实现高效的插入、删除和操作。同时我们也讨论了 list 特有的操作如 splice()、merge()、remove() 等。

在 C++ 中，list 作为双向链表，非常适合频繁插入和删除元素的场景，但它不支持随机访问，这与 vector 的应用场景有所不同。在实际开发中，可以根据需要选择合适的容器来优化性能和提高程序的可读性。

💬 欢迎讨论：如果你有任何问题或建议，请在评论区留言。

👍 支持一下：如果你觉得这篇文章对你有帮助，请点赞、收藏并分享！你们的支持是我持续创作的动力！

以上就是关于【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器2

6.3 修改操作

6.3.1 示例：修改 list 中的首尾元素

6.3.2 示例：通过迭代器修改 list 中的元素

6.3.3 修改操作的常见问题

第七章：list 的迭代器失效问题

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

7.1.1 示例：删除元素时正确的迭代器处理

7.1.2 错误示例：删除后不更新迭代器

7.1.3 相关文档

第八章：list 常见的其他修改操作

8.1 splice() 操作

8.1.1 示例：使用 splice() 操作

8.1.2 相关文档

8.2 merge() 操作

8.2.1 示例：使用 merge() 操作

8.2.2 相关文档

第九章：list 的排序与去重

9.1 sort() 操作

9.1.1 示例：对 list 进行排序

9.1.2 使用自定义比较函数排序

9.2 unique() 操作

9.2.1 示例：使用 unique() 去重

9.2.2 使用自定义规则去重

第十章：list 的其他操作

10.1 reverse() 操作

10.1.1 示例：反转 list 中的元素

10.1.2 相关文档

10.2 swap() 操作

10.2.1 示例：交换两个 list 的内容