【C++进阶】深入STL之list:高效双向链表的使用技巧

简介: 【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中

在这几个函数中,inserterase当然又是最棘手的,但是它们的使用方法和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

随机访问迭代器支持++,--,-,+操作,
双向迭代器能支持++,--
单向迭代器只支持++

这些迭代器是向上兼容的,随机访问迭代器是特殊的单向迭代器



🔥总结

通过本篇文章,我们一同探索了C++标准模板库(STL)中list容器的奥秘。list以其基于双向链表的特性,为我们提供了在序列容器中进行高效插入和删除操作的强大工具。我们深入了解了list的基本操作、迭代器使用、内存管理以及与其他STL容器的比较,使得我们能够在编程中更加灵活地应用它。

每个工具都有其适用的场景和局限性。在选择使用list容器时,我们需要根据具体需求权衡其优点和缺点。例如,list的随机访问性能较差,不适合需要频繁访问特定元素位置的场景。此时,我们可以考虑使用vector或deque等随机访问容器。

学习STL中的list容器不仅是为了掌握其使用技巧,更是为了培养我们解决问题的思维方式和编程能力。希望本篇文章能够为您在C++编程道路上的探索提供一些帮助和启示。让我们一起继续深入学习STL和其他C++编程技术,不断提升自己的编程水平!

谢谢大家支持本篇到这里就结束了,祝大家天天开心!

目录
相关文章
|
10天前
|
设计模式 算法 Java
【c++】STL之stack和queue详解
【c++】STL之stack和queue详解
10 1
|
17天前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
26 0
|
19天前
|
存储 算法 数据处理
【C++】STL简介
**STL是C++标准库的关键部分,源于Alexander Stepanov的泛型编程研究。它提供了数据结构(如vector、list)和算法,是高效、通用的软件框架。STL始于惠普,后由SGI发展,现已成为C++1998标准的一部分并不断进化。它包括容器、迭代器、算法、仿函数、配接器和分配器六大组件,带来高效性、通用性和可扩展性,但也存在性能开销和学习难度。学习STL涉及理解底层数据结构、用法、实现和实践。推荐[cplusplus.com](https://cplusplus.com)作为学习资源。**
|
19天前
|
存储 算法 程序员
C++基础知识(八:STL标准库(Vectors和list))
C++ STL (Standard Template Library标准模板库) 是通用类模板和算法的集合,它提供给程序员一些标准的数据结构的实现如 queues(队列), lists(链表), 和 stacks(栈)等. STL容器的提供是为了让开发者可以更高效率的去开发,同时我们应该也需要知道他们的底层实现,这样在出现错误的时候我们才知道一些原因,才可以更好的去解决问题。
|
19天前
|
算法 前端开发 C++
C++基础知识(八:STL标准库 deque )
deque在C++的STL(Standard Template Library)中是一个非常强大的容器,它的全称是“Double-Ended Queue”,即双端队列。deque结合了数组和链表的优点,提供了在两端进行高效插入和删除操作的能力,同时保持了随机访问的特性。
|
19天前
|
存储 C++ 索引
C++基础知识(八:STL标准库 Map和multimap )
C++ 标准模板库(STL)中的 map 容器是一种非常有用的关联容器,用于存储键值对(key-value pairs)。在 map 中,每个元素都由一个键和一个值组成,其中键是唯一的,而值则可以重复。
|
10天前
|
设计模式 安全 编译器
【C++11】特殊类设计
【C++11】特殊类设计
29 10
|
15天前
|
C++
C++友元函数和友元类的使用
C++中的友元(friend)是一种机制,允许类或函数访问其他类的私有成员,以实现数据共享或特殊功能。友元分为两类:类友元和函数友元。类友元允许一个类访问另一个类的私有数据,而函数友元是非成员函数,可以直接访问类的私有成员。虽然提供了便利,但友元破坏了封装性,应谨慎使用。
43 9
|
10天前
|
存储 编译器 C语言
【C++基础 】类和对象(上)
【C++基础 】类和对象(上)
|
19天前
|
编译器 C++
【C++】string类的使用④(字符串操作String operations )
这篇博客探讨了C++ STL中`std::string`的几个关键操作,如`c_str()`和`data()`,它们分别返回指向字符串的const char*指针,前者保证以&#39;\0&#39;结尾,后者不保证。`get_allocator()`返回内存分配器,通常不直接使用。`copy()`函数用于将字符串部分复制到字符数组,不添加&#39;\0&#39;。`find()`和`rfind()`用于向前和向后搜索子串或字符。`npos`是string类中的一个常量,表示找不到匹配项时的返回值。博客通过实例展示了这些函数的用法。