C++初阶学习第十一弹——探索STL奥秘(六)——深度刨析list的用法和核心点

简介: C++初阶学习第十一弹——探索STL奥秘(六)——深度刨析list的用法和核心点

前言:

在前面,我们已经学习了STL中的string和vector,现在就来讲解STL中的最后一个部分——list的使用及其相关知识点,先说明一点,因为我们之前已经讲过了string和vector的接口函数等用法,list的这些用法与它们相差不大,所以我们讲解的重心就不再是如何使用list上,而是后面list的模拟实现和一些细节点


一、list的使用

1.1 list的简单接口函数

首先我们需要先明确list的底部实际上是类似一个带头双向链表的,结构如下图所示:

因此list非常便于插入和删除数据,下面我们就先来看一下list的一些重要的接口函数

初始化列表:

std::list<int> myList = {1, 2, 3, 4, 5};

通过迭代器访问元素:

std::list<int>::iterator it = myList.begin();
while (it != myList.end()) {
    std::cout << *it << std::endl;
    ++it;
}

在链表尾部插入元素:

myList.push_back(6);

在链表头部插入元素:

myList.push_front(0);

删除元素:

myList.remove(3); // 删除值为3的元素
myList.erase(it); // 删除迭代器指向的元素

排序链表:

myList.sort();

反转链表:

myList.reverse();

上面这些就是list经常使用的一些接口函数,没啥难度,有不理解的地方可以私信我或者到网上搜一下

1.2 list的注意事项

  • 迭代器失效: 在list进行插入和删除操作时,不仅操作的元素所在的迭代器会失效,所有指向链表的迭代器、指针和引用都会失效。因此,在进行操作后,需要重新获取有效的迭代器。(vector的使用也要注意这个问题)
  • 内存效率: list的内存效率相对较高,因为它不需要像数组那样连续分配内存,但是它的插入和删除操作的时间复杂度为O(1),这是因为链表的每个元素都需要存储指向前后节点的指针。
  • 没有容量概念: list没有容量(capacity)这个概念,它总是根据需要动态分配内存。
  • 元素唯一性: list中的元素是不重复的,如果尝试插入已经存在的元素,该元素将被覆盖。
  • 操作顺序: 由于list是双向链表,因此插入和删除操作会保持元素的相对顺序,即元素在链表中的位置不会改变。

使用list时,应该根据具体需求选择合适的操作,并注意迭代器的管理,以确保程序的正确性。

特别强调一下迭代器失效的问题,list的迭代器失效问题一般只有在删除元素的时候会出现,因为它插入数据的时候都是开辟的新空间,不同数据之间一般不是连接在一起的


二、list的模拟实现

list的模拟实现上与前面的vector和string也极为相似,这里我们主要想讲一下list的迭代器的模拟实现,首先我们要知道,因为我们期待迭代器能像指针那样发挥作用,所以它的模拟实现需要包含以下几点:


1. 指针可以解引用,迭代器的类中必须重载operator*()


2. 指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()


3. 指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)


至于operator--()/operator--(int)释放需要重载,根据具体的结构来抉择,双向链表可以向前 移动,所以需要重载,如果是forward_list就不需要重载--


4. 迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()

list迭代器也要分为两种:正向迭代器和反向迭代器

因为list正反向迭代器的应用都要实现,所以还是比较麻烦的,下面我们直接来看一下实现

#include <iostream>
using namespace std;
#include <assert.h>
namespace zda
{
  // List的节点类
  template<class T>
  struct ListNode
  {
    ListNode(const T& val = T())
      : _prev(nullptr)
      , _next(nullptr)
      , _val(val)
    {}
 
    ListNode<T>* _prev;
    ListNode<T>* _next;
    T _val;
  };
 
  //正向迭代器
  template<class T, class Ref, class Ptr>
  class ListIterator
  {
    typedef ListNode<T> Node;
    typedef ListIterator<T, Ref, Ptr> Self;
 
    // Ref 和 Ptr 类型需要重定义下,实现反向迭代器时需要用到
  public:
    typedef Ref Ref;
    typedef Ptr Ptr;
  public:
    //
    // 构造
    ListIterator(Node* node = nullptr)
      : _node(node)
    {}
 
    //
    // 具有指针类似行为
    Ref operator*()
    {
      return _node->_val;
    }
 
    Ptr operator->()
    {
      return &(operator*());
    }
 
    // 迭代器支持移动
    Self& operator++()
    {
      _node = _node->_next;
      return *this;
    }
 
    Self operator++(int)
    {
      Self temp(*this);
      _node = _node->_next;
      return temp;
    }
 
    Self& operator--()
    {
      _node = _node->_prev;
      return *this;
    }
 
    Self operator--(int)
    {
      Self temp(*this);
      _node = _node->_prev;
      return temp;
    }
 
    // 迭代器支持比较
    bool operator!=(const Self& l)const
    {
      return _node != l._node;
    }
 
    bool operator==(const Self& l)const
    {
      return _node != l._node;
    }
 
    Node* _node;
  };
 
  //反向迭代器
  template<class Iterator>
  class ReverseListIterator
  {
  public:
    typedef typename Iterator::Ref Ref;
    typedef typename Iterator::Ptr Ptr;
    typedef ReverseListIterator<Iterator> Self;
  public:
    // 构造
    ReverseListIterator(Iterator it)
      : _it(it)
    {}
 
    // 具有指针类似行为
    Ref operator*()
    {
      Iterator temp(_it);
      --temp;
      return *temp;
    }
 
    Ptr operator->()
    {
      return &(operator*());
    }
 
    // 迭代器支持移动
    Self& operator++()
    {
      --_it;
      return *this;
    }
 
    Self operator++(int)
    {
      Self temp(*this);
      --_it;
      return temp;
    }
 
    Self& operator--()
    {
      ++_it;
      return *this;
    }
 
    Self operator--(int)
    {
      Self temp(*this);
      ++_it;
      return temp;
    }
 
    // 迭代器支持比较
    bool operator!=(const Self& l)const
    {
      return _it != l._it;
    }
 
    bool operator==(const Self& l)const
    {
      return _it != l._it;
    }
 
    Iterator _it;
  };
}


三、list和vector的区别

1、任意位置插入删除时:list可以随意插入删除,但是vector任意位置的插入删除效率低,需要挪动元素,尤其是插入时有时候需要异地扩容,就需要开辟新空间,拷贝元素,释放旧空间,效率很低

2、访问元素时:vector支持随机访问,但是list不支持随机访问

3、迭代器的使用上:vector可以使用原生指针,但是list需要对原生指针进行封装

4、空间利用上:vector使用的是一个连续的空间,空间利用率高,而list使用的是零碎的空间,空间利用率低

四、总结

以上就是学习list的一些重点内容和基本操作,这些内容当然是不全的,剩下有很多内容需要自己再去学习一下,后期我也会有针对的再加一些内容进来

感谢大佬观看,创作不易,还请各位大佬一键三连!!!

相关文章
|
7天前
|
存储 Java C++
【c++】list详细讲解
【c++】list详细讲解
15 5
|
7天前
|
设计模式 算法 Java
【c++】STL之stack和queue详解
【c++】STL之stack和queue详解
10 1
|
7天前
|
Java C++ Python
【c++】list 模拟
【c++】list 模拟
8 1
|
15天前
|
存储 编译器 C语言
【C++】list模拟实现
本文档介绍了C++ STL中`list`容器的模拟实现,包括`ListNode`节点类、迭代器类和`list`类的详细设计。`ListNode`模板类存储数据并维护前后指针;`ListIterator`是一个复杂的模板类,提供解引用、自增/自减以及比较操作。`list`类包含了链表的各种操作,如插入、删除、访问元素等,并使用迭代器作为访问接口。实现中,迭代器不再是简单的指针,而是拥有完整功能的对象。此外,文档还提到了迭代器的实现对C++语法的特殊处理,使得`it-&gt;_val`的写法成为可能。文章通过分步骤展示`list`的各个组件的实现,帮助读者深入理解STL容器的内部工作原理。
|
15天前
|
算法 搜索推荐 C++
【C++】list的使用(下)
`C++` 中 `std::list` 的 `merge()`、`sort()` 和 `reverse()` 操作: - `merge(x)` 和 `merge(x, comp)`: 合并两个已排序的`list`,将`x`的元素按顺序插入当前`list`,`x`清空。比较可自定义。 - `sort()` 和 `sort(comp)`: 对`list`元素排序,保持等价元素相对顺序。内置排序基于稳定排序算法,速度较慢。 -reverse(): 反转`list`中元素的顺序。 这些操作不涉及元素构造/销毁,直接移动元素。注意,`sort()`不适合`std::list`,因链表结构不利于快速排序
|
15天前
|
C++ 容器
【C++】list的使用(下)
这篇博客探讨了C++ STL中`list`容器的几个关键操作,包括`splice()`、`remove()`、`remove_if()`和`unique()`。`splice()`允许高效地合并或移动`list`中的元素,无需构造或销毁。`remove()`根据值删除元素,而`remove_if()`则基于谓词移除元素。`unique()`则去除连续重复的元素,可选地使用自定义比较函数。每个操作都附带了代码示例以说明其用法。
|
15天前
|
编译器 C++ 容器
【C++】list的使用(上)
迭代器在STL中统一了访问接口,如`list`的`begin()`和`end()`。示例展示了如何使用正向和反向迭代器遍历`list`。注意`list`的迭代器不支持加减操作,只能用`++`和`--`。容器的`empty()`和`size()`用于检查状态和获取元素数。`front()`和`back()`访问首尾元素,`assign()`重载函数用于替换内容,`push_*/pop_*`管理两端元素,`insert()`插入元素,`erase()`删除元素,`resize()`调整大小,`clear()`清空容器。这些接口与`vector`和`string`类似,方便使用。
|
14天前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
24 0
|
15天前
|
存储 编译器 C语言
【C++】list的使用(上)
**C++ STL的list是一个基于双向循环链表的容器,支持常数时间内插入和删除,但不支持随机访问。默认构造函数、填充构造、迭代器范围构造和拷贝构造提供多种初始化方式。析构函数自动释放内存,赋值运算符重载用于内容替换。示例代码展示了构造和赋值操作。**
|
24天前
|
安全 Java
java线程之List集合并发安全问题及解决方案
java线程之List集合并发安全问题及解决方案
20 1