Trouvaille ~

Trouvaille ~

关注
发信
关注(28)粉丝(399)

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

文章目录

C++ list 容器详解：从入门到精通

前言

C++ 标准模板库（STL）中的 list 容器是一个双向链表结构，它提供了高效的插入和删除操
作。与 vector 不同，list 中的元素不是连续存储的，因此可以在任何位置高效插入和删除元素，而无需移动其他元素。

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

第一章：C++ list 容器简介

1.1 C++ STL 容器概述

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 常见构造函数
2.1.1 示例：不同构造方法
#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst1;                      // 空 list
    list<int> lst2(5, 100);              // 5个值为100的元素
    list<int> lst3(lst2);                // 拷贝构造
    list<int> lst4 = {1, 2, 3, 4, 5};    // 初始化列表

    for (int val : lst4) {
        cout << val << " ";              // 输出: 1 2 3 4 5
    }
    return 0;
}
2.1.2 相关文档

第三章：list 迭代器的使用

3.1 常见迭代器
3.1.1 示例：使用正向和反向迭代器遍历 list
#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;
}
3.1.2 相关文档

第四章：list 的容量与大小操作

4.1 容量管理接口

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

4.1.1 示例：容量操作
#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.1.2 相关文档

第五章：list 的元素访问

5.1 元素访问方法

list 提供了几种常用的方法用于访问链表中的元素。

5.1.1 示例：访问第一个与最后一个元素
#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;
}
5.1.2 相关文档

第六章：list 的插入、删除与修改

6.1 插入操作

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

6.1.1 示例：使用 push_back() 和 push_front() 插入元素

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;
}
6.1.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;
}
6.1.3 插入元素的常见问题
  • 迭代器失效：在 list 中进行插入操作时，插入不会使已有迭代器失效，因为 list 是双向链表，插入时只修改指针。
  • 尾部插入效率：在链表尾部插入元素的效率始终为 O(1)，无需移动其他元素，这点不同于 vector。
  • 插入到特定位置的效率：虽然 insert() 操作本身是 O(1)，但查找特定插入位置的时间复杂度是 O(n)，这取决于你如何获取迭代器。
6.1.4 相关文档
6.2 删除操作

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

6.2.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;
}
6.2.2 示例：删除指定位置的元素

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;
}
6.2.3 示例：清空 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;
}
6.2.4 删除操作的常见问题
  • 迭代器失效：在 list 中，删除操作只会导致指向被删除元素的迭代器失效，其他迭代器不受影响。删除后如果需要继续使用迭代器，应该使用 erase() 的返回值，指向下一个有效元素。
  • clear() 是否删除头节点：clear() 不会删除 list 的头节点。调用 clear() 后，list 对象依然存在，只是里面的所有元素被删除，list 的结构保持完好。
6.2.5 相关文档
6.3 修改操作
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 的迭代器失效问题

  • 插入操作：
  • 删除操作：
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;
}
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 相关文档

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

8.1 splice() 操作
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 相关文档
8.2 merge() 操作
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;
}

，并且不会对原链表进行元素的复制，只是对链表节点进行了重新连接。

8.2.2 相关文档

第九章：list 的排序与去重

9.1 sort() 操作
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() 操作
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() 操作
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 相关文档
10.2 swap() 操作
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 相关文档
10.3 remove() 操作
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 相关文档
10.4 remove_if() 操作
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 相关文档
10.5 emplace() 和 emplace_back() 操作
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 相关文档

第十一章：list 的内存管理

11.1 shrink_to_fit() 操作

写在最后

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

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

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

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

09-27 08:20
Powered by LMLPHP ©2024 Trouvaille ~ 0.007109