【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

目录
相关文章
|
5月前
|
存储 缓存 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`),全面解析它们的特点、用法
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
|
5月前
|
算法 C++ 容器
模拟实现c++中的list模版
模拟实现c++中的list模版
|
5月前
|
存储 机器学习/深度学习 编译器
【C++终极篇】C++11:编程新纪元的神秘力量揭秘
【C++终极篇】C++11:编程新纪元的神秘力量揭秘
|
5月前
|
存储 算法 C++
深入浅出 C++ STL:解锁高效编程的秘密武器
C++ 标准模板库(STL)是现代 C++ 的核心部分之一,为开发者提供了丰富的预定义数据结构和算法,极大地提升了编程效率和代码的可读性。理解和掌握 STL 对于 C++ 开发者来说至关重要。以下是对 STL 的详细介绍,涵盖其基础知识、发展历史、核心组件、重要性和学习方法。
|
5月前
|
存储 安全 算法
深入理解C++模板编程:从基础到进阶
在C++编程中,模板是实现泛型编程的关键工具。模板使得代码能够适用于不同的数据类型,极大地提升了代码复用性、灵活性和可维护性。本文将深入探讨模板编程的基础知识,包括函数模板和类模板的定义、使用、以及它们的实例化和匹配规则。
|
7月前
|
编译器 C语言 C++
【c++丨STL】list模拟实现(附源码)
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构,相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口,然后详细讲解了节点、迭代器及容器的实现过程。 最终,通过这些步骤,我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现,并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣,建议先掌握相关基础知识后再阅读本文,以便更好地理解内容。
133 1
|
7月前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构,适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码,读者可以更好地理解如何使用这些接口。最后,作者总结了`list`的特点和适用场景,并预告了后续关于`list`模拟实现的文章。
200 7
|
7月前
|
存储 编译器 C++
C++ initializer_list&&类型推导
在 C++ 中,`initializer_list` 提供了一种方便的方式来初始化容器和传递参数,而右值引用则是实现高效资源管理和移动语义的关键特性。尽管在实际应用中 `initializer_list&&` 并不常见,但理解其类型推导和使用方式有助于深入掌握现代 C++ 的高级特性。
76 4
|
8月前
|
存储 安全 Java
Java多线程编程中的并发容器:深入解析与实战应用####
在本文中,我们将探讨Java多线程编程中的一个核心话题——并发容器。不同于传统单一线程环境下的数据结构,并发容器专为多线程场景设计,确保数据访问的线程安全性和高效性。我们将从基础概念出发,逐步深入到`java.util.concurrent`包下的核心并发容器实现,如`ConcurrentHashMap`、`CopyOnWriteArrayList`以及`BlockingQueue`等,通过实例代码演示其使用方法,并分析它们背后的设计原理与适用场景。无论你是Java并发编程的初学者还是希望深化理解的开发者,本文都将为你提供有价值的见解与实践指导。 --- ####
|
8月前
|
存储 设计模式 C++
【C++】优先级队列(容器适配器)
本文介绍了C++ STL中的线性容器及其适配器,包括栈、队列和优先队列的设计与实现。详细解析了`deque`的特点和存储结构,以及如何利用`deque`实现栈、队列和优先队列。通过自定义命名空间和类模板,展示了如何模拟实现这些容器适配器,重点讲解了优先队列的内部机制,如堆的构建与维护方法。
118 0