探索C++的工具箱：双向链表容器类list（1）

🕗 发布于 2024-10-20 05:47 c++ 链表 list

引言

在C++中，std::list 是一个标准库提供的容器类，属于C++ STL（标准模板库）。std::list 是一种独特而强大的容器，它使用双向链表结构来管理元素。无论是在处理动态数据集合，还是在需要频繁进行插入和删除操作时，std::list 都展现了无与伦比的灵活性和效率。与其他线性数据结构如数组和向量相比，std::list 让开发者能够在不影响整体性能的情况下，轻松地在数据集中间添加或移除元素。

在这篇博客中，会以介绍与string类和vector类中相通的函数为主，在下一篇博客，探索C++的工具箱：双向链表容器类list（2）-CSDN博客中，会以介绍string类和vector类中没有的、list新引入的内容为主。

1. list 简介

C++ 的 std::list 是一个双向链表（doubly linked list）的实现，与 vector 不同，list 提供 O(1) 的插入和删除操作，但不支持随机访问。使用时需要包含头文件<list>。

如果将“list”比喻为一个“购物清单”，而“list中的元素”就相当于“购物清单上的每一项商品”。

在这个比喻中：

- 整个购物清单（list）是一个容器，帮助我们整理和管理购物的内容。

- 每一项商品（list中的元素）则是清单中具体要购买的内容。

就像我们可以在购物清单上添加、删除或修改商品，列表中的元素也可以随时增删改。

std::list具有以下特点：

双向链表：std::list 中的每个元素都包含指向前一个元素和后一个元素的指针。这使得在链表的任意位置进行插入和删除操作非常快速（时间复杂度为O(1)），但访问随机元素的效率较低（时间复杂度为O(n)）。
动态大小：std::list 可以根据需要动态增长或收缩，能够有效管理动态变化的数据集。
不连续存储：与std::vector 不同，std::list 中的元素在内存中不必连续存储，这为插入和删除操作防止内存重排提供了便利。
支持迭代器：std::list 支持常规和反向迭代器，可以方便地遍历链表元素。

2.list的构造

基本语法：


default (1)
explicit list (const allocator_type& alloc = allocator_type());
fill (2)
explicit list (size_type n);
         list (size_type n, const value_type& val,
                const allocator_type& alloc = allocator_type());
range (3)
template <class InputIterator>
  list (InputIterator first, InputIterator last,
         const allocator_type& alloc = allocator_type());
copy (4)
list (const list& x);
list (const list& x, const allocator_type& alloc);

move (5)
list (list&& x);
list (list&& x, const allocator_type& alloc);

initializer list (6)
list (initializer_list<value_type> il,
       const allocator_type& alloc = allocator_type());

explicit 关键字用于构造函数，目的是为了防止类型转换（隐式转换）。如果一个构造函数被声明为 explicit，那么它只能通过显式的方式来调用，而不能用作隐式类型转换。

以下是构造和使用 std::list 的几种常见方法（默认使用std）：

（1）默认构造函数
创建一个空的 std::list，可以使用以下代码：

list<int> myList;

（2）填充构造函数

explicit list (size_type n);
         list (size_type n, const value_type& val,
                const allocator_type& alloc = allocator_type());

上面的构造方法用来创建一个包含n个元素的list，并且元素会被初始化为默认值，在int类型中默认值是0。

下面的构造方法用来创建一个又n个元素且值会被初始化value的list

    list<int> myList(5);  // 创建一个包含5个元素的 list 

    list<int> myList(5, 100);  // 创建一个包含5个100的 list

（3）迭代器范围构造函数

template <class InputIterator>
  list (InputIterator first, InputIterator last,
         const allocator_type& alloc = allocator_type());

#include <iostream>  
#include <list>  
#include <vector>  

int main() {  
    vector<int> vec = {1, 2, 3, 4, 5};  
    list<int> myList(vec.begin(), vec.end());  // 使用范围构造函数  

    return 0;  
}

（4）复制构造函数

list (const list& x);
list (const list& x, const allocator_type& alloc);

第二个构造函数允许自定义分配器。

#include <iostream>  
#include <list>  

int main() {  

    list<int> original = {1, 2, 3, 4, 5};  
    list<int> copiedList(original);  // 使用复制构造函数

    return 0;  
}

（5）移动构造函数

list (list&& x);
list (list&& x, const allocator_type& alloc);

同上，可以自定义分配器。移动构造函数是在 C++11 中引入的，它用于高效地构造对象，将资源（如动态分配的内存）从一个对象“转移”到另一个对象，而不是进行复制。这种方式能够提高性能，尤其是在处理管理资源的对象时（例如，标准库容器、字符串等）。

#include <iostream>  
#include <list>  

int main() {  
    std::list<int> original = {1, 2, 3, 4, 5};  
    std::list<int> movedList(std::move(original));  // 使用移动构造函数  
 
    return 0;  
}

（6）初始化列表构造函数

list (initializer_list<value_type> il,
       const allocator_type& alloc = allocator_type());


    list<int> myList = {1, 2, 3, 4, 5};  // 使用初始化列表构造函数

（7）赋值运算符重载构造函数

copy (1)
list& operator= (const list& x);

move (2)
list& operator= (list&& x);

initializer list (3)
list& operator= (initializer_list<value_type> il);//与初始化列表结合

#include <iostream>  
#include <list>  

int main() {  
    // 创建两个 list  
    std::list<int> list1 = {1, 2, 3, 4, 5};  // 初始化 list1  
    std::list<int> list2;   // 创建空 list2  

    // 使用赋值运算符将 list1 的内容复制到 list2  
    list2 = list1;  // 执行 copy assignment  

    return 0;  
}

list容器的迭代器以及空间有关函数等与string类和vector类的使用相似，在此不再赘述，不了解的小伙伴可以去看以下博客：

C++深入学习string类成员函数（1）：默认与迭代_std::string初始化函数-CSDN博客

探索C++的存储箱：动态数组容器类vector-CSDN博客

3.list的修饰函数

3.1 emplace

`emplace` 允许在容器中直接构造对象，而不是先构造对象再进行拷贝或移动。这样可以避免不必要的性能开销。
- emplace_front(): 在链表头部直接构造元素。
- emplace_back(): 在链表尾部直接构造元素。
- emplace(): 在指定位置直接构造元素。

1. emplace_front()
在链表的开头直接构造元素：

std::list<std::string> mylist;
mylist.emplace_front("Hello");
mylist.emplace_front(5, 'A');  // 直接构造一个字符串 "AAAAA"

2. emplace_back()
在链表的末尾直接构造元素：

mylist.emplace_back("World");
mylist.emplace_back(4, 'B');  // 直接构造字符串 "BBBB"

3.emplace()
在链表的指定位置直接构造元素：

auto it = mylist.begin();
mylist.emplace(it, "Inserted");  // 在开头插入字符串 "Inserted"

emplace 与 push 系列的区别
- push_front() / push_back(): 需要先创建一个对象，然后再将其拷贝或移动到容器中。
- emplace_front() / emplace_back(): 直接在容器中的位置构造对象，省去了拷贝或移动的过程，适合构造复杂对象时提高效率。

使用场景
当你需要直接在容器中构造元素，并且想避免额外的临时对象构造和销毁时，`emplace` 系列函数非常有用，尤其是在需要构造复杂对象或容器时，性能优势明显。

3.2 assign

`std::list` 的 `assign()` 函数用于替换链表中的元素。它提供了三种重载方式来支持不同的输入类型。以下是每种 `assign()` 函数的具体说明：

range (1)
template <class InputIterator>
  void assign (InputIterator first, InputIterator last);

fill (2)
void assign (size_type n, const value_type& val);

initializer list (3)
void assign (initializer_list<value_type> il);

1.范围构造函数
- 功能：将链表中的元素替换为 `[first, last)` 范围内的元素。此函数使用两个迭代器来指定范围，可以从另一个容器或范围中拷贝元素。

  std::list<int> mylist;
  std::vector<int> vec = {1, 2, 3, 4, 5};
  mylist.assign(vec.begin(), vec.end());  // 复制 vector 中的所有元素到 list

2.填充构造函数
- 功能：将链表中的元素替换为 `n` 个值为 `val` 的元素。此函数将链表填充为 `n` 个相同的元素。

  std::list<int> mylist;
  mylist.assign(5, 100);  // 用 5 个值为 100 的元素填充 list

3.初始化列表构造函数
- 功能：将链表中的元素替换为初始化列表 `il` 中的元素。此函数允许使用 C++11 引入的初始化列表语法进行赋值。

  std::list<int> mylist;
  mylist.assign({1, 2, 3, 4, 5});  // 通过初始化列表填充 list

4.assign() 函数的使用场景

- 范围赋值（Range Assign）：适用于从另一个容器或范围内复制数据，例如从 `vector` 或 `array` 中将某个范围的元素赋值到 `list` 中。
- 填充赋值（Fill Assign）：适合需要将链表中的所有元素设置为相同的值时使用，例如初始化某个固定大小的列表。
- 初始化列表赋值（Initializer List Assign）：简化了使用固定值集合初始化 `list` 的过程，尤其是在初始化时可以快速赋值。

3.3 push与pop

在 C++ std::list 中，push 和 pop，分别用于向链表中添加元素和移除元素。它们有两种常用的形式：操作链表头部和尾部的元素。

（1）push 系列

1. push_front()
- 功能：在链表头部插入一个元素。

     std::list<int> mylist;
     mylist.push_front(10);  // 在链表头部插入 10
     mylist.push_front(20);  // 在链表头部插入 20，链表现在是 {20, 10}

2. push_back()
- 功能：在链表尾部插入一个元素。

     std::list<int> mylist;
     mylist.push_back(10);  // 在链表尾部插入 10
     mylist.push_back(20);  // 在链表尾部插入 20，链表现在是 {10, 20}

（2）pop 系列

1. pop_front()
- 功能：移除链表头部的元素。

- 注意：此操作不返回被移除的元素。如果链表为空，调用此函数会导致未定义行为。

     std::list<int> mylist = {10, 20, 30};
     mylist.pop_front();  // 移除头部的 10，链表现在是 {20, 30}

2. pop_back()
- 功能：移除链表尾部的元素。
- 注意：与 `pop_front()` 一样，此操作不返回被移除的元素，链表为空时调用会导致未定义行为。

     std::list<int> mylist = {10, 20, 30};
     mylist.pop_back();  // 移除尾部的 30，链表现在是 {10, 20}

3.4 其它函数

- insert()：在链表的指定位置插入元素或范围内的多个元素。
- swap()：交换两个链表的内容。
- erase()：删除链表中的某个元素或一段范围内的元素。
- resize()：调整链表大小，可能会插入或删除元素。
- clear()：清空链表，删除所有元素。

1. insert()

- 功能：在指定位置插入一个或多个元素。
- 重载形式：

single element (1)
iterator insert (const_iterator position, const value_type& val);
fill (2)
iterator insert (const_iterator position, size_type n, const value_type& val);
range (3)
template <class InputIterator>
iterator insert (const_iterator position, InputIterator first, InputIterator last);

1. 插入单个元素：
在 `position` 迭代器处插入 `val`，返回指向新插入元素的迭代器。
2. 插入多个相同值的元素：
在 `position` 处插入 `n` 个 `val`。

3. 插入范围内的元素：
将 `[first, last)` 范围内的元素插入到 `position` 处。

2. swap()

- 功能：交换两个 `list` 容器的内容。

  std::list<int> list1 = {1, 2, 3};
  std::list<int> list2 = {4, 5, 6};
  list1.swap(list2);  // list1 变为 {4, 5, 6}，list2 变为 {1, 2, 3}

3. erase()

- 功能：删除指定位置的元素或指定范围内的元素。
- 重载形式：

iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);

1. 删除单个元素：
删除 `position` 处的元素，返回指向被删除元素后面的元素迭代器。

2. 删除范围内的元素：
删除 `[first, last)` 范围内的所有元素，返回指向删除范围后第一个元素的迭代器。

4. resize()

- 功能：调整链表的大小。如果新大小比当前小，删除多余的元素；如果新大小比当前大，则插入默认值的元素或指定值的元素。
- 用法：

void resize (size_type n);
void resize (size_type n, const value_type& val);

1. 仅调整大小：
调整链表大小为 `n`，如果新大小比当前大，则插入默认值的元素。

2. 调整大小并指定新元素的值：
调整链表大小为 `n`，并用 `val` 填充新插入的元素。

  std::list<int> mylist = {1, 2, 3};
  mylist.resize(5, 100);  // 调整大小为 5，列表变为 {1, 2, 3, 100, 100}
  mylist.resize(2);       // 缩小大小为 2，列表变为 {1, 2}

5. clear()

- 功能：清空链表，删除所有元素，链表大小变为 0，但不改变链表的容量。

  std::list<int> mylist = {1, 2, 3, 4};
  mylist.clear();  // 清空列表，列表现在为空

通过本篇文章，我们详细了解了 C++ `list` 容器的基本操作与应用场景。`list` 提供了双向链表的灵活性，能够高效地进行插入、删除等操作，尤其在需要频繁修改容器中的元素时表现优异。然而，正如我们所讨论的，它在随机访问性能上不如其他顺序容器（如 `vector`），因此在选择容器时，应根据实际需求权衡各个方面。

本篇博客就到此为止了，与vector、string容器不同、list新引入的内容都在探索C++的工具箱：双向链表容器类list（2）-CSDN博客中，有兴趣的小伙伴可以跳转学习

原文地址：https://blog.csdn.net/wangchen_0/article/details/143078562

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Hbase 几种scan方式
下一篇：矩阵系统哪家好～矩阵短视频运营～怎么矩阵OEM

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20