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

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

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

💬 欢迎讨论:学习过程中有问题吗?随时在评论区与我交流。你们的互动是我创作的动力!

👍 支持我:如果你觉得这篇文章对你有帮助,请点赞、收藏并分享给更多朋友吧!

🚀 一起成长:欢迎分享给更多对 C++ 感兴趣的小伙伴,让我们共同进步!

前言

C++ 标准模板库(STL)中的 list 容器是一个双向链表结构,它提供了高效的插入和删除操

作。与 vector 不同,list 中的元素不是连续存储的,因此可以在任何位置高效插入和删除元素,而无需移动其他元素。虽然它在随机访问方面不如 vector 高效,但在大量的插入和删除操作场景中具有不可替代的优势。

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

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

1.1 C++ STL 容器概述

C++ 提供了丰富的标准模板库 (STL),其中包括顺序容器(如 vectordeque)和关联容器(如 mapset)。

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 提供了多种构造函数,允许用户根据不同需求初始化链表。

构造函数 功能
list() 构造一个空的 list
list(size_type n, const T& val) 构造一个包含 n 个值为 val 的元素的 list
list(const list& x) 拷贝构造函数,构造与 x 相同的 list
list(InputIterator first, InputIterator last) 使用 [first, last) 区间内的元素构造 list
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 迭代器的使用

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

3.1 常见迭代器
迭代器类型 功能
begin() 返回指向链表第一个元素的迭代器
end() 返回指向链表末尾的迭代器
rbegin() 返回指向链表最后一个元素的反向迭代器
rend() 返回指向链表第一个元素之前的反向迭代器
cbegin() 返回常量迭代器,不能修改元素
cend() 返回常量迭代器,指向链表末尾
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 提供了常用的容量管理接口,方便用户操作链表的大小和判断链表状态。

方法名 功能描述
empty() 检测 list 是否为空
size() 返回 list 中元素的数量
max_size() 返回 list 可容纳的最大元素数
resize(n) 调整 list 的大小为 n
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 提供了几种常用的方法用于访问链表中的元素。

方法名 功能
front() 返回 list 的第一个元素
back() 返回 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 插入时不需要移动其他元素,只修改指针,因此插入效率非常高。
方法名 功能描述
push_front() list 的前部插入元素
push_back() list 的末尾插入元素
insert(position, val) 在指定位置插入元素
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 提供了多种删除元素的方式,包括从前部和尾部删除,删除指定位置的元素,以及一次性清空整个链表。

方法名 功能描述
pop_front() 删除 list 的第一个元素
pop_back() 删除 list 的最后一个元素
erase() 删除指定位置的元素
clear() 清空 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 中的所有元素。值得注意的是,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 的结构保持完好。
.2.5 相关文档

【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2:https://developer.aliyun.com/article/1617552?spm=a2c6h.13148508.setting.19.b8d84f0euVDBkf

目录
相关文章
|
1天前
|
存储 搜索推荐 C++
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器
21 2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
|
1天前
|
存储 算法 C++
C++ STL 初探:打开标准模板库的大门
C++ STL 初探:打开标准模板库的大门
35 9
|
1天前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
18 2
|
4月前
|
安全 Java
java线程之List集合并发安全问题及解决方案
java线程之List集合并发安全问题及解决方案
589 1
|
3月前
|
Java API Apache
怎么在在 Java 中对List进行分区
本文介绍了如何将列表拆分为给定大小的子列表。尽管标准Java集合API未直接支持此功能,但Guava和Apache Commons Collections提供了相关API。
|
3月前
|
运维 关系型数据库 Java
PolarDB产品使用问题之使用List或Range分区表时,Java代码是否需要进行改动
PolarDB产品使用合集涵盖了从创建与管理、数据管理、性能优化与诊断、安全与合规到生态与集成、运维与支持等全方位的功能和服务,旨在帮助企业轻松构建高可用、高性能且易于管理的数据库环境,满足不同业务场景的需求。用户可以通过阿里云控制台、API、SDK等方式便捷地使用这些功能,实现数据库的高效运维与持续优化。
|
3月前
|
存储 安全 Java
详解Java中集合的List接口实现的ArrayList方法 | Set接口实现的HashSet方法
详解Java中集合的List接口实现的ArrayList方法 | Set接口实现的HashSet方法
|
4月前
|
Java API
使用 Java 来实现两个 List 的差集操作
使用 Java 来实现两个 List 的差集操作
69 3
|
3月前
|
存储 Java 索引
Java List接口实现原理与性能评估
Java List接口实现原理与性能评估
|
3月前
|
存储 缓存 安全
Java List操作详解及常用方法
Java List操作详解及常用方法