当前位置: 首页 > news >正文

《C++》STL--list容器详解

在 C++ 标准模板库(STL)中,list 是一个非常重要的序列容器,它实现了双向链表的数据结构。与 vector 和 deque 不同,list 提供了高效的插入和删除操作,特别是在任意位置。本文将深入探讨 list 容器的特性、使用方法以及常见操作。

文章目录

  • 一、list 容器的基本特性
  • 二、list 的基本操作
    • 2.1 list的语法
    • 2.2 常用成员函数
    • 2.3 插入和删除操作
  • 三、list 的高级特性
    • 3.1 迭代器使用
    • 3.2 排序和去重
    • 3.3 合并和拼接
  • 四、list对比其它容器的优劣势
    • 4.1优势
    • 4.2劣势

一、list 容器的基本特性

list 是一个双向链表容器,它有下面5个特点:

  • 双向链表结构:每个元素都包含指向前驱和后继的指针。

  • 非连续内存:元素存储在任意内存位置,通过指针连接。

  • 高效的插入删除:在任意位置插入和删除元素的时间复杂度为 O(1)。

  • 不支持随机访问:不能像数组一样通过下标直接访问元素。

  • 迭代器稳定性:插入和删除操作不会使迭代器失效(除了被删除元素的迭代器)。

二、list 的基本操作

2.1 list的语法

  • 使用 list 前需要包含 头文件:
#include <iostream>
#include <list>
using namespace std;
  • 初始化一个空的 list
    list<int> lst1;
  • 初始化包含 5 个元素,每个元素值为 10
    list<int> lst2(5, 10);
  • 通过初始化列表初始化
    list<int> lst3 = {1, 2, 3, 4, 5};
  • 通过数组初始化
    int arr[] = {6, 7, 8, 9, 10};list<int> lst4(arr, arr + sizeof(arr)/sizeof(arr[0]));

2.2 常用成员函数

定义一个list作为示例,将为大家演示一些常用的成员函数及其使用方法。

list<int> myList = {1, 2, 3};
  • 在末尾添加元素
myList.push_back(4);  // 1,2,3,4
  • 在开头添加元素
myList.push_front(0); // 0,1,2,3,4
  • 获取第一个和最后一个元素
cout << "Front: " << myList.front() << endl; // 0
cout << "Back: " << myList.back() << endl;   // 4
  • 删除第一个和最后一个元素
myList.pop_front(); // 1,2,3,4
myList.pop_back();  // 1,2,3
  • 判断 list 是否为空
if (!myList.empty()) {cout << "List size: " << myList.size() << endl; // 3
}

2.3 插入和删除操作

list 的插入和删除操作非常高效,定义一个list作为示例:

list<int> nums = {10, 20, 30, 40};
  • 在指定位置前插入元素
auto it = nums.begin();
advance(it, 2); // 移动到第3个元素位置
nums.insert(it, 25); // 10,20,25,30,40
  • 删除指定位置的元素
it = nums.begin();
advance(it, 3);
nums.erase(it); // 10,20,25,40
  • 删除所有值为20的元素
nums.remove(20); // 10,25,40
  • 删除满足条件的元素
nums.remove_if([](int n){ return n > 30; }); // 10,25

三、list 的高级特性

3.1 迭代器使用

由于 list 不支持随机访问,遍历时必须使用迭代器。
我在这里定义一个string类型的list作为演示遍历时的操作。(其实主要还是迭代器遍历,但是范围for也可以。其实范围for内核本质就是迭代器啦)

list<string> names = {"Alice", "Bob", "Charlie"};
  • 使用迭代器遍历
for (auto it = names.begin(); it != names.end(); ++it) {cout << *it << " ";
}
cout << endl;
  • 使用范围for循环遍历
for (const auto& name : names) {cout << name << " ";
}
cout << endl;

3.2 排序和去重

list 中,库提供了专门的排序和去重成员函数,下面我创建一个int类型的list为大家一一演示其使用方法:

list<int> values = {3, 1, 4, 1, 5, 9, 2, 6};
  • 排序 (升序)
values.sort(); // 1,1,2,3,4,5,6,9
  • 降序排序
values.sort(greater<int>()); // 9,6,5,4,3,2,1,1
  • 去重 (必须先排序)
values.unique(); // 9,6,5,4,3,2,1
  • 自定义去重条件
values.unique([](int a, int b){ return abs(a-b) <= 1; });

3.3 合并和拼接

list 在合并和拼接提供了十分方便并且高效的库函数:

  • 定义两个list链表作为演示
list<int> list1 = {1, 3, 5};
list<int> list2 = {2, 4, 6};
  • 合并两个有序list (list2会被清空)
list1.merge(list2); // list1: 1,2,3,4,5,6; list2: 空list<int> list3 = {7, 8, 9};
  • 拼接list (将list3的元素移动到list1的指定位置)
auto pos = list1.begin();
advance(pos, 3);
list1.splice(pos, list3); // list1: 1,2,3,7,8,9,4,5,6

下次我们写算法题就可以不用像C语言那样那么麻烦了…(手动狗头)

四、list对比其它容器的优劣势

4.1优势

  • 适合频繁插入删除:当需要在序列中间频繁插入删除元素时,list 是最佳选择

  • 适合大元素对象:当元素对象很大时,list 可能比 vector 更高效,因为不需要重新分配和复制

  • 不需要随机访问:如果不需要通过下标快速访问元素

  • 迭代器稳定性高:需要保证插入删除操作不影响其他元素的迭代器

4.2劣势

    1. 内存开销大
      • list 作为链表结构,每个元素都需要额外的指针空间来存储前驱和后继节点的地址:
struct ListNode {T data;            // 存储的实际数据ListNode* prev;    // 指向前驱节点的指针ListNode* next;    // 指向后继节点的指针
};
    1. 缓存不友好
    • 链表节点分散在内存各处,无法利用空间局部性。

    • 遍历链表时几乎每次访问都会导致缓存缺失。

    • CPU 难以预测下一个节点的内存位置。

http://www.lryc.cn/news/607659.html

相关文章:

  • UnionApplication
  • 江协科技STM32 12-2 BKP备份寄存器RTC实时时钟
  • 【Shell脚本自动化编写——报警邮件,检查磁盘,web服务检测】
  • Windows安装虚拟机遇到内容解码失败
  • python-异常(笔记)
  • Java学习-运算符
  • Java:JWT 从原理到高频面试题解析
  • 【Linux】重生之从零开始学习运维之Mysql
  • Rust在CentOS 6上的移植
  • 2025.8.1
  • 1661. 每台机器的进程平均运行时间
  • 系统开机时自动执行指令
  • 基于python大数据的招聘数据可视化及推荐系统
  • 算法思想之 多源 BFS 问题
  • 【Node.js安装注意事项】-安装路径不能有空格
  • PNP机器人机器人学术年会展示灵巧手动作捕捉方案。
  • MySQL分析步
  • Android签名轮转
  • Conda install安装了一些库,如何撤销操作
  • 第13届蓝桥杯Python青少组中/高级组选拔赛(STEMA)2022年3月13日真题
  • 外卖“0元购”退场后,即时零售大战才刚开始
  • CORS模块:你的跨域快速通行证 [特殊字符]
  • 【C语言入门级教学】字符指针变量
  • Java 23 新特性解析与代码示例
  • 嵌入式学习日志————TIM输入捕获
  • EasyGBS的两种录像回看
  • 抢占先机,PostgreSQL 中级专家认证的职业跃迁
  • 学习:入门uniapp Vue3组合式API版本(17)
  • Linux文件系统:从内核到缓冲区的奥秘
  • 如何创建一个飞书应用获取自己的飞书AppID和AppSecret?