【C++】手搓 list 容器

简介: 本文我们实现了STL库中重要的list 的模拟实现,其中最重要莫过于迭代器的封装类的书写,这是前所未有的操作(对于我来说,我是第一次使用这种结构)。通过list 的模拟实现也帮我们巩固了类与对象的知识,也强化了指针操作的思路。欢迎大家讨论分析。

送给大家一句话:

若结局非你所愿,就在尘埃落定前奋力一搏。—— 《夏目友人帐》

手搓 list 容器

1 前言

List是C++标准模板库(STL)中的一个成员,其本质为带头双向循环链表。不同于连续的、紧密排列的数组容器Vector,List容器的内部是由双向链表构成的,使得它在插入和删除操作上,就如同行云流水一般顺畅,不需移动其它元素。

1.1 底层结构

List容器的底层结构,是一个经典的带头双向循环链表。每个节点包含:

  1. 数据
  2. 指向前一个节点的指针
  3. 指向后一个节点的指针。

这种结构赋予了List灵动的特性:它能够轻松地在任意位置增加或移除元素,而这种操作几乎是与容器大小无关的,体现了时间复杂度上的优势。但这种优势的代价是,与数组相比,List在访问元素时的速度会较慢,因为它需要从头开始遍历。这也决定了list的更适合频繁插入的动态数据。

来看STL源码中的节点结构:

template <class T>
struct __list_node {
  typedef void* void_pointer;
  void_pointer next;
  void_pointer prev;
  T data;
};

1.2 使用场景

List最适合的场景是那些需要频繁进行插入和删除操作的场合。

例如,如果你正在管理一个动态变化的列表,如任务调度、人员排队等场景,List的特性将大放异彩。但是如果你的应用场景更多地需要随机访问元素,那么向量(Vector)或者数组可能是更佳的选择。因为List的顺序访问性能相比之下会显得有些力不从心。

  • 所以如果需要频繁随机的访问数据,那么选择vector容器
  • 如果需要频繁插入删除数据,那么选择list容器
  • 排序不要选择list !!!其删除节点的过程就决定了其速度不会太快。

1.3 功能简介

功能简介我们可以参考STL官方库 :list文档介绍

  1. 插入与删除:List的插入和删除操作非常高效,它可以在任意位置快速地添加或移除元素,而不需要像连续内存容器那样进行大量元素的移动。
  2. 多种构造:类都应该包含多种构造函数
  3. 支持迭代器:迭代器是C++重要的特性,我们写的list 也一定要支持迭代器。

2 框架搭建

现在我们开始实现list 容器,首先先要思考一下框架结构:

  1. 首先我们需要一个节点结构体(类似源码中的节点)
  2. 其次我们的list 类要带一个头结点,让我们更方便进行插入删除操作

基本就是这样,现在我们开始手搓

2.1 节点类

// 节点 结构体
template<class T>
struct ListNode
{
  ListNode* _next;
  ListNode* _prev;
  T _data;

  ListNode(T x = T()) :
    _next(nullptr),
    _prev(nullptr),
    _data(x)
  {}
  //ListNode(T x = T()) 
  //{
  //  _next = nullptr;
  //  _prev = nullptr;
  //  _data = x;
  //} 
  ~ListNode()
  {
    _next = nullptr;
    _prev = nullptr;
  }
};

这里使用模版来适配更多的情景,然后基本的数据,前后指针都很简单。在编写一个构造函数,==构造函数使用初始化列表,并不是必须使用。析构函数避免野指针出现,将指针赋值为nullptr就可以了。

2.2 list 类

我们先进行简单的框架书写,构造函数需要创建一个头结点,因为我们要创建双向循环链表,所以头尾都要指向头结点本身。 _size赋初值。

template<class T>
class list
{
public:
  //设置适配的节点
  typedef ListNode<T> Node;
  //空初始化
  void empty_init()
  {
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
    _size = 0;
  }
  //构造函数
  list() :
  _head(nullptr)
  {
    empty_init();
  }
private:
  Node* _head;
  size_t _size;
};

接下来我们来逐步完成功能书写,由于我们还没有进行迭代器的书写

2.3 迭代器类

我们思考一下这里能不能使用原生指针来完成迭代器的操作(++ == != --)当然是不能的,因为链表的物理地址并不是连续的,对原生指针的++或–操作是没有意义的,所以我们需要自行编写迭代器类,对原生指针进行封装,来满足我们特殊的++和–操作。

  //这里的模板可以再次升级  先简单写一下
  template<class T>
  class ListIterator 
  {
  public:
    //重命名方便书写
    typedef ListNode<T> Node;
    typedef ListIterator<T> Self;
    Node* _node;
    ListIterator(Node* x ):
      _node(x)
    {}
    //操作符重载 前置++ 与 后置++的区别是参数是否带(int)
    //++t
    Self operator++()
    {
      _node = _node->_next;
      return *this;
    }
    //t++
    Self operator++(int)
    {
      Self tmp(*this);//浅拷贝即可
      _node = _node->_next;
      return tmp;
    }
    //--t
    Self operator--()
    {
      _node = _node->_prev;
      return *this;
    }
    //t--
    Self operator--(int)
    {
      Self tmp(*this);//浅拷贝即可
      _node = _node->_prev;
      return tmp;
    }
    //判断是否相等 比较指针地址是否相同即可
    bool operator!=(const Self& it)
    {
      return _node != it._node;
    }
    //判断是否相等 比较指针地址是否相同即可
    bool operator==(const Self& it)
    {
      return _node == it._node;
    }
    // 解引用操作 *it 返回节点数据的引用 可以进行修改
    T& operator*()
    {
      return  _node->_data;
    }
    //因为指针才能使用-> 所以->要返回地址(指针)    
    T* operator->()//编译器会进行省略->
    {
      return &_node->_data;
    }
  };

这样迭代器类就大致写好了,那么一般我们的迭代器应该还要支持const,不然我们传入一个不可修改的链表(const list l),就会反生报错,那么我们还要书写一份const版的迭代器。如果进行编写,那么是不是会有大部分与刚才我们书写的迭代器重复(++ -- == != 都是一样的),只有operator*()和operator->()返回值不一致:

  • 因为是常迭代器,使用场景是对const list l进行操作,那么节点数据不可改变,所以不影响++ -- == != 这些操作,受影响的是operator*()和operator->()返回值(该情况下链表本身是只读的,又因为不能将权限进行扩大,所以返回值应该也是只读的(const))。
  • 那这样就发现了不同常迭代器应该为 const T& operator*() 和 const T* operator->() ,所以有没有一种办法可以简单解决呢,当然有了,我们设置一个新模版(带有三个参数),创建的时候就传入对应参数

我们将模版修改为这样,

//reference 引用  pointer 指针
template<class T , class Ref ,class Ptr>

对应返回值也改变:

Ref operator*()
  {
    return  _node->_data;
  }
  Ptr operator->()
  {
    return &_node->_data;
  }

那么类实例化的时候传入对应参数就好了:

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;

这样就实现了迭代器的创建,是不是就非常简洁了呢

3 功能实现

3.1 begin() 与 end()

使用迭代器即可,注意end()是头结点,因为遍历过程中,全部遍历后会回到头结点,所以直接判断是

否为头结点就能控制结束位置。

//普通迭代器
typedef ListIterator<T, T&, T*> iterator;
//常迭代器
typedef ListIterator<T, const T&, const T*> const_iterator;

iterator begin() { return _head->_next; }
iterator end() { return _head; }

const_iterator begin() const { return _head->_next; }
const_iterator end() const { return _head; }

3.2 插入操作

插入操作我们很熟悉,步骤是创建一个新节点,然后通过改变指针指向来完成插入操作:

来看尾插操作,

void push_back(const T& x = T())
{
  //创建新节点
  Node* node = new Node(x);
  //找尾
  Node* tail = _head->_prev;
  //进行插入
  node->_next = _head;
  node->_prev = tail;
  
  tail->_next = node;
  _head->_prev = node;
  //别忘记大小++
  _size++;
}

任意位置插入,操作思路依然是对前后节点与新节点的指针指向进行操作,来完成插入。

void insert(iterator pos = begin(), T x = T())
{
  //创建新节点
  Node* node = new Node(x);
  //前节点 后节点
  Node* prev = pos._node->_prev;
  Node* next = pos._node;
  //处理新节点
  node->_prev = prev;
  node->_next = next;
  //出现前后节点
  prev->_next = node;
  next->_prev = node;
  //别忘记大小++
  _size++;
}   

头插,直接干脆调用insert就可以了

void push_front(const T& x = T())
{
  insert(begin(), x);
}

3.3 删除操作

删除操作,同样是使用指针操作,来达到删除的效果。注意要对删除的节点进行释放空间操作(delete),不然会发生内存泄漏!!!

尾删
void pop_back()
{
  Node* tail = _head->_prev;
  Node* prev = tail->_prev;

  prev->_next = _head;
  _head->_prev = prev;

  delete tail;
  _size--;
}
//头删
void pop_front()
{
  Node* head = _head->_next;
  Node* next = head->_next;

  _head->_next = next;
  next->_prev = _head;

  delete head;
  _size--;
}
//任意位置删除
iterator erase(iterator pos)
{
  Node* cur = pos._node;
  Node* prev = cur->_prev;
  Node* next = cur->_next;

  prev->_next = next;
  next->_prev = prev;
  delete cur;

  _size--;
  return iterator(next);
}

需要注意的是,任意位置删除因为使用了迭代器,删除后会造成迭代器失效,所以需要更新迭代器,返回被删除节点的下一个节点的迭代器即可。

3.4 拷贝构造

拷贝构造直接将数据一个一个插入到该链表中即可:

list(const list<T>& l)
{
  empty_init();
  iterator it = l.begin();
  while (it != l.end())
  {
    push_back(*it);
    it++;
  }
}

这样十分方便快捷!!!

3.5 析构函数

void clear()
{
  //依次释放
  iterator it = begin();
  while (it != end())
  {
    
    it = erase(it);
  }
}
~list()
{
  clear();
  //需要单独释放头结点空间
  delete _head;
  _head = nullptr;
}

3.6 其他函数

返回大小:

size_t size() const { return _size; }

判断是否为空:

bool empty()
{
  return _size == 0;
}

清空数据:

void clear()
{
  iterator it = begin();
  while (it != end())
  {
    it = erase(it);
  }
}

4 总结

本文我们实现了STL库中重要的list 的模拟实现,其中最重要莫过于迭代器的封装类的书写,这是前所未有的操作(对于我来说,我是第一次使用这种结构)。通过list 的模拟实现也帮我们巩固了类与对象的知识,也强化了指针操作的思路。欢迎大家讨论分析。

Thanks♪(・ω・)ノ谢谢阅读!!!

下一篇文章见!!!

相关文章
|
2天前
|
存储 算法 C++
C++一分钟之-容器概览:vector, list, deque
【6月更文挑战第21天】STL中的`vector`是动态数组,适合随机访问,但插入删除非末尾元素较慢;`list`是双向链表,插入删除快但随机访问效率低;`deque`结合两者优点,支持快速双端操作。选择容器要考虑操作频率、内存占用和性能需求。注意预分配容量以减少`vector`的内存重分配,使用迭代器而非索引操作`list`,并利用`deque`的两端优势。理解容器内部机制和应用场景是优化C++程序的关键。
18 5
|
6天前
|
算法 前端开发 Linux
【常用技巧】C++ STL容器操作:6种常用场景算法
STL在Linux C++中使用的非常普遍,掌握并合适的使用各种容器至关重要!
33 10
|
2天前
|
存储 算法 NoSQL
C++一分钟之-map与set容器详解
【6月更文挑战第21天】C++ STL的`map`和`set`是基于红黑树的关联容器,提供有序存储和高效查找。`map`存储键值对,键唯一,值可重复;`set`仅存储唯一键。两者操作时间复杂度为O(log n)。常见问题包括键的唯一性和迭代器稳定性。自定义比较函数可用于定制排序规则,内存管理需注意适时释放。理解和善用这些工具能提升代码效率。
10 3
|
11天前
|
存储 C++
C++的list-map链表与映射表
这篇教程介绍了C++中`list`链表和`map`映射表的基本使用。`list`链表可通过`push_front()`、`push_back()`、`pop_front()`和`pop_back()`进行元素的添加和删除,使用迭代器遍历并支持在任意位置插入或删除元素。`map`是一个键值对的集合,元素自动按键值排序,可使用下标操作符或`insert()`函数插入元素,通过迭代器遍历并修改键值对,同时提供`count()`方法统计键值出现次数。教程中包含多个示例代码以帮助理解和学习。
14 2
|
17天前
|
存储 C++
C++初阶学习第十一弹——探索STL奥秘(六)——深度刨析list的用法和核心点
C++初阶学习第十一弹——探索STL奥秘(六)——深度刨析list的用法和核心点
22 7
|
16天前
|
存储 人工智能 C++
map容器在C++中的具体用法以及相关注意点
map容器在C++中的具体用法以及相关注意点
16 1
|
23天前
|
存储 C++ 索引
C++标准库容器的使用
C++标准库容器的使用
21 1
|
8天前
|
存储 缓存 编译器
【C++进阶】深入STL之list:模拟实现深入理解List与迭代器
【C++进阶】深入STL之list:模拟实现深入理解List与迭代器
10 0
|
8天前
|
C++ 容器
【C++进阶】深入STL之list:高效双向链表的使用技巧
【C++进阶】深入STL之list:高效双向链表的使用技巧
13 0
|
9天前
|
C++ 容器
【C++语言】String 类关键函数实现,手搓一个简单字符串类!
【C++语言】String 类关键函数实现,手搓一个简单字符串类!

热门文章

最新文章