list的模拟实现

简介: list的模拟实现



一、list类

1、 list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。

2、 list的底层是带头双向循环链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。

3、 list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。

4、 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。

链表结点定义:

template<class T>
struct list_node
{
  T _data;
  list_node<T>* _next;
  list_node<T>* _prev;
  list_node(const T& x = T())
    :_data(x)
    ,_next(nullptr)
    ,_prev(nullptr)
  {}
};

链表的定义:

template<class T>
class list
{
  typedef list_node<T> Node;
private:
  Node* _head;//哨兵位头节点
};

二、迭代器

1、说明

迭代器的价值在于封装底层的实现,不暴露底层的实现细节,又提供统一的访问方式,这样几乎所有的容器都可以用相似的方法来访问。对于vector和string类而言,物理空间是连续的,通过++或者--,我们就可以访问一个位置的前一个位置或者后一个位置,所以我们可以用原生的指针来实现迭代器。

但是对于list而言,它的空间是不连续的,我们无法直接通过++或者--来直接访问一个位置的前一个位置或者后一个位置,所以使用指针来实现list的迭代器是不可能的了。我们需要进行一些特殊处理。怎么处理呢?

C++作为一种优秀的编程语言,它的一个非常牛逼的功能之一就是可以对运算符进行重载和三大特性之一的封装,使其有特殊的功能,来帮助我们满足一些特殊的需求。list 无法直接通过++或者--来直接访问一个位置的前一个位置或者后一个位置,那么我们可以通过运算符重载来帮助我们来找到一个结点的前一个位置或者下一个位置。

2、迭代器模板实现

template<class T, class Ref, class Ptr>
struct _list_iterator
{
  typedef list_node<T> Node;
  typedef _list_iterator<T, Ref, Ptr> iterator;
  Node* _node;
  _list_iterator(Node* node)
    :_node(node)
  {}
  bool operator!=(const iterator& it)const
  {
    return _node != it._node;
  }
  //const T& operator*()
  // T& operator*()
  //通过模板参数来控制是const还是非const
  Ref operator*()
  {
    return _node->_data;
  }
  //T* operator->()
  Ptr operator->()  //p->_data  p.operator->()   
  {
    return &(operator*());
  }
  //++it
  iterator& operator++()
  {
    _node = _node->_next;
    return *this;
  }
  //it++
  iterator operator++(int)
  {
    iterator tmp(*this);
    _node = _node->_next;
    return tmp;
  }
  //--it
  iterator& operator--()
  {
    _node = _node->_prev;
    return *this;
  }
  //it--
  iterator operator--(int)
  {
    iterator tmp(*this);
    _node = _node->_prev;
    return tmp;
  }
};

3、迭代器实现

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
  return iterator(_head->_next);
}
iterator end()
{
  return iterator(_head);
}
const_iterator begin()const
{
  return const_iterator(_head->_next);
}
const_iterator end()const
{
  return const_iterator(_head);
}

实现了迭代器后我们就可以直接使用范围for了。

那么为什么需要重载 -> 呢?请看下图:

从上图我们可以看出如果只重载了 * 的话,我们解引用只能拿到Pos(自定义类型),而不能拿到Pos里的数据, 所以我们就可以重载一下 -> 来帮助我们直接访问 _a1 和 _a2。

第二个重载函数的调用结果是  &(_node->_data) ,括号里面我们取到了 Pos,然后取到Pos的地址,这样我们就可以通过 -> 来访问 _a1 和 _a2,即:it->->_a1。但是为了可读性,编译器将它简化为了 it->_a1来使用。

说明:前面的 it-> 是重载的运算符部分,返回的是T*,而我们知道指针可以使用 -> 符号来访问成员,因此就可以直接访问 _a1 和 _a2。


三、增删查改

1、insert

iterator insert(iterator pos, const T& x)
{
  Node* newnode = new Node(x);
  Node* cur = pos._node;
  Node* prev = cur->_prev;
  prev->_next = newnode;
  newnode->_prev = prev;
  newnode->_next = cur;
  cur->_prev = newnode;
  return iterator(newnode);//返回新插入位置的迭代器
}

2、erase

iterator erase(iterator pos)//返回删除位置下一个位置的迭代器
{
  assert(pos != end());
  Node* cur = pos._node;
  Node* prev = cur->_prev;
  Node* next = cur->_next;
  prev->_next = next;
  next->_prev = prev;
  delete cur;
  return iterator(next);
}

3、push_back

void push_back(const T& x)
{
  /*Node* tail = _head->_prev;
  Node* newnode = new Node(x);
  tail->_next = newnode;
  newnode->_prev = tail;
  newnode->_next = _head;
  _head->_prev = newnode;*/
  insert(end(), x);
}

4、push_front

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

5、pop_back

void pop_back()
{
  erase(--end());
}

6、pop_front

void pop_front()
{
  erase(begin());
}

7、clear

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

四、list的各种构造函数和析构函数

1、构造函数

我们可以用empty_init()来封装初始化,方便复用。

void empty_init()
{
  _head = new Node;
  _head->_next = _head;
  _head->_prev = _head;
}
list()
{
  empty_init();
}

2、区间构造

template<class InputIterator>
    //区间构造
list(InputIterator first, InputIterator last)
{
  empty_init();
  while (first != last)
  {
    push_back(*first);
    ++first;
  }
}

3、拷贝构造函数

void swap(list<T>& x)
{
  std::swap(_head, x._head);
}
//拷贝构造函数 lt2(lt1)
list(const list<T>& lt)
{
  empty_init();
  list<T> tmp(lt.begin(), lt.end());
  swap(tmp);
}

4、 赋值重载

//  lt1 = lt3
list<T>& operator=(list<T> lt)
{
  swap(lt);
  return *this;
}

5、析构函数

~list()
{
  clear();
  delete _head;
  _head = nullptr;
}

五、反向迭代器

在lis的STL的源码中,我们发现还提供了一种十分好的遍历方式,那就是反向遍历。对于vector和string,我们可以直接通过下标的++或者--来反向遍历,而在list中,我们则需要进行一些特殊的处理。

通过前面例子知道,反向迭代器的++就是正向迭代器的 - -,反向迭代器的 - - 就是正向迭代器的++,因此反向迭代器的实现可以借助正向迭代器,即:反向迭代器内部可以包含一个正向迭代器,对正向迭代器的接口进行包装即可。

template<class Iterator, class Ref, class Ptr>
  struct _reverse_iterator
  {
    Iterator _cur;
    typedef _reverse_iterator<Iterator, Ref, Ptr> RIterator;
    _reverse_iterator(Iterator it)
      :_cur(it)
    {}
    RIterator operator++()
    {
      --_cur;
      return *this;
    }
    RIterator operator--()
    {
      ++_cur;
      return *this;
    }
    Ref operator*()
    {
      //return *_cur;
      auto tmp = _cur;
      --tmp;
      return *tmp;
    }
    Ptr operator->()
    {
      //return &(*_cur);
      return &(operator*());
    }
    bool operator!=(const RIterator& it)
    {
      return _cur != it._cur;
    }
  };

六、总代码

namespace zdl
{
  template<class T>
  struct list_node
  {
    T _data;
    list_node<T>* _next;
    list_node<T>* _prev;
    list_node(const T& x = T())
      :_data(x)
      ,_next(nullptr)
      ,_prev(nullptr)
    {}
  };
  //迭代器模板
  template<class T, class Ref, class Ptr>
  struct _list_iterator
  {
    typedef list_node<T> Node;
    typedef _list_iterator<T, Ref, Ptr> iterator;
    Node* _node;
    _list_iterator(Node* node)
      :_node(node)
    {}
    bool operator!=(const iterator& it)const
    {
      return _node != it._node;
    }
    //const T& operator*()
    // T& operator*()
    //通过模板参数来控制是const还是非const
    Ref operator*()
    {
      return _node->_data;
    }
    //T* operator->()
    Ptr operator->()  //p->_data  p.operator->()   
    {
      return &(operator*());
    }
    //++it
    iterator& operator++()
    {
      _node = _node->_next;
      return *this;
    }
    //it++
    iterator operator++(int)
    {
      iterator tmp(*this);
      _node = _node->_next;
      return tmp;
    }
    //--it
    iterator& operator--()
    {
      _node = _node->_prev;
      return *this;
    }
    //it--
    iterator operator--(int)
    {
      iterator tmp(*this);
      _node = _node->_prev;
      return tmp;
    }
  };
  template<class T>
  class list
  {
    typedef list_node<T> Node;
  public:
    typedef _list_iterator<T, T&, T*> iterator;
    typedef _list_iterator<T, const T&, const T*> const_iterator;
    typedef _reverse_iterator<iterator, T&, T*> reverse_iterator;
    typedef _reverse_iterator<iterator, const T&, const T*> const_reverse_iterator;
    iterator begin()
    {
      return iterator(_head->_next);
    }
    iterator end()
    {
      return iterator(_head);
    }
    reverse_iterator rbegin()
    {
      return reverse_iterator(end());
    }
    reverse_iterator rend()
    {
      return reverse_iterator(begin());
    }
    const_iterator begin()const
    {
      return const_iterator(_head->_next);
    }
    const_iterator end()const
    {
      return const_iterator(_head);
    }
    void empty_init()
    {
      _head = new Node;
      _head->_next = _head;
      _head->_prev = _head;
    }
    template<class InputIterator>
    //区间构造
    list(InputIterator first, InputIterator last)
    {
      empty_init();
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    list()
    {
      empty_init();
    }
    void swap(list<T>& x)
    {
      std::swap(_head, x._head);
    }
    //拷贝构造函数 lt2(lt1)
    list(const list<T>& lt)
    {
      empty_init();
      list<T> tmp(lt.begin(), lt.end());
      swap(tmp);
    }
    //  lt1 = lt3
    list<T>& operator=(list<T> lt)
    {
      swap(lt);
      return *this;
    }
    ~list()
    {
      clear();
      delete _head;
      _head = nullptr;
    }
    void clear()
    {
      iterator it = begin();
      while (it != end())
      {
        it = erase(it);
      }
    }
    void push_back(const T& x)
    {
      /*Node* tail = _head->_prev;
      Node* newnode = new Node(x);
      tail->_next = newnode;
      newnode->_prev = tail;
      newnode->_next = _head;
      _head->_prev = newnode;*/
      insert(end(), x);
    }
    void push_front(const T& x)
    {
      insert(begin(), x);
    }
    iterator insert(iterator pos, const T& x)
    {
      Node* newnode = new Node(x);
      Node* cur = pos._node;
      Node* prev = cur->_prev;
      prev->_next = newnode;
      newnode->_prev = prev;
      newnode->_next = cur;
      cur->_prev = newnode;
      return iterator(newnode);//返回新插入位置的迭代器
    }
    iterator erase(iterator pos)//返回删除位置下一个位置的迭代器
    {
      assert(pos != end());
      Node* cur = pos._node;
      Node* prev = cur->_prev;
      Node* next = cur->_next;
      prev->_next = next;
      next->_prev = prev;
      delete cur;
      return iterator(next);
    }
    void pop_back()
    {
      erase(--end());
    }
    void pop_front()
    {
      erase(begin());
    }
  private:
    Node* _head;//哨兵位头节点
};
dbln
+关注
目录
打赏
0
0
0
0
1
分享
相关文章
DingTalk「开发者说」酷应用沉浸式容器开发指南
在移动端是半屏效果,可以达到轻交互,不打断当前对话的效果,所以比较适合酷应用的沉浸式交互场景。沉浸容器(在桌面端被称之为侧边栏)在桌面端也需要遵循一些规范标准,如侧边栏标题、侧边栏关闭、自定义内容区、操作按钮、二级页面按钮等。
1564 0
DingTalk「开发者说」酷应用沉浸式容器开发指南
阿里云服务器地域和可用区之间是什么关系?地域和可用区的区别与选择参考
不管是选择阿里云的国内云服务器还是国外云服务器,都有多个地域及可用区选择,目前国内地域有北京、青岛、甚至等13个地域可选,国外地域有韩国、新加坡、悉尼等15个地域可选,每个地域又有多个可用区可选,那么阿里云服务器地域和可用区之间是什么关系?作为用户的我们又改如何选择呢?本文介绍阿里云地域和可用区的概念、选择指导、两者的关系以及阿里云支持的地域和可用区列表。
910 0
阿里云服务器地域和可用区之间是什么关系?地域和可用区的区别与选择参考
如何利用AI技术提升软件开发效率
【10月更文挑战第9天】如何利用AI技术提升软件开发效率
622 2
gpio_direction_output 和 gpio_set_value之间的关系
gpio_direction_output 和 gpio_set_value之间的关系
837 0
梦入丹青境,变换由心生
**阿里通义的“丹青-千变万换”是图像处理技术,让用户轻松替换图片内容,如人脸、衣物和背景。该技术基于深度学习,能精确分离图像元素,实现自然的图像修改。用户通过简单步骤即可实现创意变换:选择图片、标记保留对象、输入生成参数,然后运行。此工具适用于广告、个性化媒体内容创建,帮助设计师高效工作,促进个性化营销。[Learn More](https://modelscope.cn/studios/iic/ReplaceAnything)**
【深入探究Qt内部架构】QObject、事件循环与Q_OBJECT宏的协同作用(二)
【深入探究Qt内部架构】QObject、事件循环与Q_OBJECT宏的协同作用
478 0
【AI 初识】描述数据预处理在 AI 中的重要性
【5月更文挑战第2天】【AI 初识】描述数据预处理在 AI 中的重要性
Linux 内存管理与 Swap 空间扩展实践
该文介绍了Linux系统中`free`命令的使用,解析了其输出信息,包括物理内存(总内存、已用、空闲、缓存)和交换空间(总大小、使用和空闲)。Linux优先使用物理内存作缓存,当内存紧张时使用Swap空间。文章还提供了扩展Swap空间的步骤,并强调适度Swap使用对性能的影响,建议合理平衡物理内存和Swap的比例。
打开xshell无法定位程序输入点。。。。。。。。。。于动态链接库nssock2.dll上解决方法(参考)
打开xshell无法定位程序输入点。。。。。。。。。。于动态链接库nssock2.dll上解决方法(参考)
1063 0
大白话-设计RocketMQ延迟消息
RocketMQ的延迟消息使用上非常便捷,但是不支持任意时间的延迟,这一点对于有强迫症的朋友来说就比较难受,但是搞明白为什么这么设计后,就自然释怀了。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问