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

引言

        在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具有以下特点：

1. 双向链表：std::list 中的每个元素都包含指向前一个元素和后一个元素的指针。这使得在链表的任意位置进行插入和删除操作非常快速（时间复杂度为O(1)），但访问随机元素的效率较低（时间复杂度为O(n)）。

2. 动态大小：std::list 可以根据需要动态增长或收缩，能够有效管理动态变化的数据集。

3. 不连续存储：与std::vector 不同，std::list 中的元素在内存中不必连续存储，这为插入和删除操作防止内存重排提供了便利。

4. 支持迭代器：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);  // 在链表头部插入 10mylist.push_front(20);  // 在链表头部插入 20，链表现在是 {20, 10}

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

     std::list<int> mylist;mylist.push_back(10);  // 在链表尾部插入 10mylist.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博客中，有兴趣的小伙伴可以跳转学习