【C++进阶】深入STL之list：高效双向链表的使用技巧-阿里云开发者社区

前言：双向链表是链表数据结构的一种重要变体，它允许我们在链表的任何位置进行高效的插入和删除操作，而无需像数组那样进行大量的数据移动。list容器正是基于这种数据结构实现的，它提供了丰富的成员函数和迭代器接口，让我们能够轻松地管理和操作链表元素

让我们一起走进STL中list容器的世界，探索其背后的奥秘吧！

因为前面我们学习string和vector，为list做足了铺垫，所以我们直接来看它的使用！

📒1. list的基本概念

list 是 C++ 标准模板库 (STL) 中的一个容器，它基于双向链表实现。双向链表是一种动态数据结构，由一系列节点组成，每个节点包含数据元素和两个指向其他节点的指针

在介绍list的使用之前，我们先来看看它的结构：

实际上：list就是一个带头双向链表

📕2. list的常用操作

🌈list的构造函数

构造函数（ (constructor)）	接口说明

list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list()	构造空的list
list (const list& x)	拷贝构造函数

list (InputIterator first, InputIterator last)

用[first, last)区间中的元素构造list

int main()
{
    list<int> lt1(10, 5); //构造的list中包含n个值为val的元素
    list<int> lt2; // 构造空的list
    list<int> lt3(lt1); // 拷贝构造函数
    list<int> lt4(lt1.begin(), lt1.end()); // 用迭代器区间中的元素构造list
    return 0;
}

🌞list iterator的使用

关于迭代器，我们都可以将迭代器暂时理解成一个指针，该指针指向list中的某个节点

函数声明	接口说明

begin +end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin +rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

迭代器打印列表：

int main()
{
    list<int> lt(10, 5);
  list<int>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout << *it << " ";
        it++;
    }
    return 0;
}

注意：

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

🌙list的常用函数

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false

size	返回list中有效节点的个数
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

这几个函数都比较简单，前面也都接触过，我们就不细讲

⭐list的增删查改

函数声明	接口说明

push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素

pop_back	删除list中最后一个元素
insert	在list pos 位置中插入值为val的元素
erase	删除list pos位置的元素

swap	交换两个list中的元素
clear	清空list中的有效元素

代码示例：

int main()
{
  list<int> lt1 = { 2,3,4,5 };
  lt1.push_back(6);
  lt1.push_front(1);

  // 将值为100的元素用insert插入lt1;
  lt1.insert(++lt1.begin(), 100);

  // 用erase删除lt1中的一个头部元素
  auto it1 = lt1.begin();
    it1 = lt1.erase(lt1.begin());
  // auto it1 = lt1.begin(); // 这里出现了迭代器失效
  while (it1 != lt1.end())
  {
    cout << *it1 << " ";
      it1++;
  }
      cout << endl;
  return 0;
}

在演示中，由于我们使用erase删除时，已经将该节点删除了，然后迭代器指向的该节点是一个无效的节点导致了迭代器失效！因此迭代器失效也存在list中

在这几个函数中，insert和erase当然又是最棘手的，但是它们的使用方法和vector其实是差不多的

当然除了插入删除，list中还有sort排序，swap交换和clear清除

代码示例：

int main()
{
  list<int> lt1 = { 1,4,3,2,5 };
  list<int> lt2 = { 6,9,8,7,0 };

  cout << "lt1: ";
  for (auto e : lt1)
  {
    cout << e << " ";
  }
  cout << endl;
  cout << "lt2: ";
  for (auto e : lt2)
  {
    cout << e << " ";
  }
  cout << endl;
  lt1.swap(lt2); // 交换两个容器里面的元素
  cout << "lt1(after swap): ";
  for (auto e : lt1)
  {
    cout << e << " ";
  }
  cout << endl;
  cout << "lt2(after swap): ";
  for (auto e : lt2)
  {
    cout << e << " ";
  }
  cout << endl;
  cout << "clear lt2";
  cout << endl;
  lt2.clear(); // 清除lt2中的元素
  cout << "lt1: ";
  for (auto e : lt1)
  {
    cout << e << " ";
  }
  cout << endl;

  cout << "lt2: ";
  for (auto e : lt2)
  {
    cout << e << " ";
  }
  cout << endl;

  lt1.sort(); // 将lt1中的元素排序
  cout << endl;
  cout << "after sort lt1: ";
  for (auto e : lt1)
  {
    cout << e << " ";
  }
  cout << endl;
  return 0;
}

注意：

list的clear()是将链表除头节点外全部清除

list的sort()在排序时，默认是进行升序排序

📜3. list迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响

void test_list()
{
  list<int> l= { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
  auto it = l.begin();
  while (it != l.end())
  {
  // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
    l.erase(it);
    ++it;
  }
}

解决迭代器失效的办法就是在遇到迭代器失效时，我们要对迭代器重新赋值

注意：erase返回的是被删除位置的下一个位置的迭代器!

void test_list()
{
  list<int> l= { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
  auto it = l.begin();
  while (it != l.end())
  {
    it = l.erase(it);
  }
}

📖4. 总结拓展

💧拓展：迭代器的性质类型

随机访问迭代器（Random Access Iterator）

支持快速访问容器中的任意元素。
支持迭代器之间的比较操作（如==、!=、<、<=、>、>=）。

双向迭代器（Bidirectional Iterator）

支持向前和向后遍历容器中的元素。

支持迭代器之间的相等和不等比较。

单向迭代器（Forward Iterator）

仅支持向前遍历容器中的元素。
支持迭代器之间的相等和不等比较。

迭代器类型	使用容器
单向迭代器	单链表，哈希表
双向迭代器	双链表，红黑树(map,set)
随机访问迭代器	vector，string，queue