【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

目录
相关文章
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
428 2
|
10月前
|
缓存 算法 程序员
C++STL底层原理:探秘标准模板库的内部机制
🌟蒋星熠Jaxonic带你深入STL底层:从容器内存管理到红黑树、哈希表,剖析迭代器、算法与分配器核心机制,揭秘C++标准库的高效设计哲学与性能优化实践。
C++STL底层原理:探秘标准模板库的内部机制
|
存储 算法 C++
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现,内部元素按键自动升序排列,存储键值对,支持通过键访问或修改值;而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能,并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别,强调了`map`在处理键值关系时的优势。
867 73
|
存储 缓存 C++
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
C++ 标准模板库(STL)提供了一组功能强大的容器类,用于存储和操作数据集合。不同的容器具有独特的特性和应用场景,因此选择合适的容器对于程序的性能和代码的可读性至关重要。对于刚接触 C++ 的开发者来说,了解这些容器的基础知识以及它们的特点是迈向高效编程的重要一步。本文将详细介绍 C++ 常用的容器,包括序列容器(`std::vector`、`std::array`、`std::list`、`std::deque`)、关联容器(`std::set`、`std::map`)和无序容器(`std::unordered_set`、`std::unordered_map`),全面解析它们的特点、用法
1058 1
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
|
存储 算法 C++
【c++丨STL】set/multiset的使用
本文深入解析了STL中的`set`和`multiset`容器,二者均为关联式容器,底层基于红黑树实现。`set`支持唯一性元素存储并自动排序,适用于高效查找场景;`multiset`允许重复元素。两者均具备O(logN)的插入、删除与查找复杂度。文章详细介绍了构造函数、迭代器、容量接口、增删操作(如`insert`、`erase`)、查找统计(如`find`、`count`)及`multiset`特有的区间操作(如`lower_bound`、`upper_bound`、`equal_range`)。最后预告了`map`容器的学习,其作为键值对存储的关联式容器,同样基于红黑树,具有高效操作特性。
759 3
|
存储 算法 C++
【c++丨STL】priority_queue(优先级队列)的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`(优先级队列)。`priority_queue`根据严格的弱排序标准设计,确保其第一个元素始终是最大元素。它底层使用堆结构实现,支持大堆和小堆,默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`,通过仿函数控制堆的类型,并调用封装容器的接口实现功能。最后,感谢大家的支持与关注。
1019 1
|
Kubernetes Docker Python
Docker 与 Kubernetes 容器化部署核心技术及企业级应用实践全方案解析
本文详解Docker与Kubernetes容器化技术,涵盖概念原理、环境搭建、镜像构建、应用部署及监控扩展,助你掌握企业级容器化方案,提升应用开发与运维效率。
1430 108

热门文章

最新文章