AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【C++】一文带你走进list的模拟实现

2023-01-14 106
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【C++】一文带你走进list的模拟实现

一. list大框架

list_node节点


namespace ljj
{
  template<class T>
  class 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;
  public:
  list()
  {
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
  }
  private:
  Node* _head;
  };


为了测试，我们迅速实现一个尾插吧，忘记的话可以画图（我画的有点丑）

//尾插
  void push_back(const T& x)
  {
    Node* namespace ljj
{
  template<class T>
  class 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;
  public:
  list()
  {
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
  }
  private:
  Node* _head;
  };tail = _head->_prev;
    Node* newnode = new Node(x);
    //_head      tail     newnode
    tail->_next = newnode;
    newnode->_prev = tail;
    newnode->_next = _head;
    _head->_prev = newnode;
  }


二 .迭代器（狠重要）

🌍相比vector和string那些连续的物理空间，原生指针就是天生的迭代器，但对于list在空间上不连续的数据结构，解引用不能取到数据，++也不能到不了下一个节点


为此，对于链表的迭代器，我们用自定义类型对结点的指针进行封装，底层仍然是结点的指针。C++的自定义类型支持运算符重载，原本的运算符编程变成函数调用，这样就可以实现像内置类型一样使用运算符，这就是c++厉害的地方 up！


构造迭代器，仅需要一个节点就可以构造了


template<class T>
  struct __list_iterator
  {
  typedef ListNode<T> Node;
  typedef __list_iterator<T,Ref,Ptr> Self;
  Node* _node;//节点指针
  __list_iterator(Node* x)//提供一个节点构造
    : _node(x)
  {}
    };


迭代器的拷贝构造&赋值重载都不需要我们自己实现，因为我们要的就是浅拷贝，用编译器默认生成的即可


灵魂发问：迭代器需不需要析构函数，把节点释放掉？不要，释放节点归链表管，迭代器是借助结点指针来访问修改链表的，不属于迭代器管，好比人家借东西给你用，你却把人家东西故意弄丢了，很可笑


🌍iterator & const_iterator

我们在list中进行typedef，这样所有容器迭代器名字统一都是iterator

我们知道const迭代器和普通迭代器的唯一区别就是：普通迭代器返回的是T&，可读可写；const迭代器返回的是const T&，可读不可写。我们当然可以再继续封装一个类（此处不能重载，因为返回值不同），__const_list_iterator类，但是会造成代码冗余，看了源码我们发现：传入模板参数解决了这个问题，这也是迭代器的精华


0a2653c851af460fa595bd959398a8f1.png


🎨重载 *


*it 就是要取迭代器指向的数据，并且返回这个数据的引用，可以修改


//*it -> it.opeartor*()    可读可写
T& operator*()
{
  return _node->_data;
}


🎨重载 ->


如果T不是int等内置类型，而是自定义类型，我们访问其中的成员，需要重载->


struct pos
  {
  int _a1;
  int _a2;
  pos(int a1 = 0 , int a2 = 0)
    :_a1(a1)
    ,_a2(a2)
  {}
  };
  void test_list2()
  {
  int x = 10;
  int* p1 = &x;
  cout << *p1 << endl;
  pos aa;
  pos* p2 = &aa;
  p2->_a1;
  p2->_a2;//找结构体成员
  list<pos> lt;
  lt.push_back(pos(10, 20));
  lt.push_back(pos(20, 50));
  list<pos>::iterator it = lt.begin();
  while (it != lt.end())
  {
      //cout << *it << endl; // 错误示范，请勿模仿
            // 因为Date是自定义类型，需要重载<<来打印，但要就是不给你提供呢，下面这样是可以的,很别扭
    //cout << (*it)._a1 << ":" << (*it)._a2 << endl;
    cout << it->_a1 << ":" << it->_a2 << endl;
    ++it;
  }
  cout<< endl;
  }
}


迭代器it是去模仿指针的行为。在list中，如果节点中是int这样的内置类型，解引用(本质调用函数)访问数据即可；而像这里一个结构体的指针，我们固然可以(*it)拿到日期类对象.访问成员，但我们更希望能->访问成员，因此我们还需要重载->


//  ->    
    T* operator->()
  {
    return &(operator*());//调用了operator*() -> &(_node->data)
  }


这里本来应该是it->->_year，但是这样写运算符可读性太差了，所以编译器进行了优化，省略了一个->，对于cosnt对象，就是返回const指针，也就是添加了ptr参数的原因


0a2653c851af460fa595bd959398a8f1.png


🎨++ / – 和 == / !=

此处比较简单，直接上代码了


//  ++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;
  }


🌍反向迭代器(迭代器适配器)

反向迭代器就是对正向迭代器的封装，这样它可以是任意容器的反向迭代器。


二者的不同之处：++调的是正向迭代器的–；–调的是正向迭代器的++

源码中为了对称的设计，使正向迭代器&反向迭代器的开始和结束保持对称，解引用*取前一个位置（我的开始就是你的结束）

0a2653c851af460fa595bd959398a8f1.png

为啥要这样子对称设计呢？直接解引用当前位置（哨兵位）的值，可能是随机值，出错


对于vector的反向迭代器，如果是我们预想的那样(解引用取的是当前位置)，会有越界访问问题


2d65d23f6d4748949b924e4057485923.png


为了获取数据类型T，我们还需要增加两个类模板参数Ref、Ptr，同时也可以区分普通参数与const参数。源码中不带这两个参数，是通过迭代器萃取技术实现的（难难难）


namespace ljj
{
  //复用, 迭代器适配器  给list就出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++(int)
  {
    RIterator(tmp);
    --_cur;
    return tmp;
  }
  RIterator operator--()
  {
    ++_cur;
    return *this;
  }
  RIterator operator--(int)
  {
    RIterator(tmp);
    ++_cur;
    return tmp;
  }
  Ref operator*()
  {
    Iterator tmp = _cur;
    return *(--tmp);//解引用上一个位置
  }
  Ptr operator->()
  {
    //return _cur.operator->();
    return &(operator*());
  }
  bool operator!=(const RIterator& it)
  {
    return _cur != it._cur;
  }
  bool operator==(const RIterator& it)
  {
    return _cur == it._cur;
  }
  };
}


反向迭代器：迭代器适配器，可以适配支持符合的反向迭代器


0a2653c851af460fa595bd959398a8f1.png


三. 增删查改

⚡insert & erase

💦insert


插入的位置是pos的上一个

返回值是newnode位置的迭代器

list的insert会导致迭代器失效吗？我们知道vector中迭代器失效的原因：扩容导致的野指针；pos意义改变，显然这里都不符合，所以不会发生

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


💦erase


注意哨兵位的头结点不能删

返回值是删除位置的下一个数据的迭代器

erase后迭代器必定失效，节点都被干掉了，pos你说指向哪里？

//删除
  iterator erase(iterator pos)
  {
    assert(pos != ens());//哨兵位头结点不能删
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    //prev   cur   next
    prev->_next = next;
    next->_prev = prev;
    delete cur;
    return iterator(next);
  }


⚡push_back & push_front

注意插入位置


//尾插
  void push_back(const T& x)
  {
    insert(end(), x);
  }
  //头插
  void push_front(const T& x)
  {
    insert(begin(), x);
  }


⚡pop_back & pop_front

也是要注意删除的位置


//尾删
  void pop_back()
  {
    erase(--end());
  }
  //头删
  void pop_front()
  {
    erase(begin());
  }


四. list的默认成员函数

🌈构造


✨无参构造


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


✨迭代器区间构造


//迭代器区间构造
  template <class InputIterator>  
  list(InputIterator first, InputIterator last)
  {
  while (first != last)
  {
    push_back(*first);//前提是已经构造了头结点
    ++first;
  }
  }


所以我们干脆实现一个empty_init来初始化，


void empty_init()
  {
     //创建并初始化哨兵位的头结点
  _head = new Node;
  _head->_next = _head;
  _head->_prev = _head;
  }


注意必须给一个头，否则_head是一个随机值，换给tmp后出作用域调用析构函数，clear时获取begin()要解引用 _head-> _next会崩溃


🌈~析构 & clear


🌍claer

查阅文档发现库中还提供了一个clear的函数


注意要给给it ，因为erase后此结点失效，返回下一个节点的迭代器


//clear 不清理头结点
  void clear()
  {
  iterator it = begin();
  while (it != end())
  {
    it = erase(it);//注意要给给it ，因为erase后此结点失效，返回下一个节点的迭代器
  }
  }


🌍析构函数


因此析构可以直接复用clear，但头结点也要一并释放


//析构  全部都清理，生命周期到了
  ~list()
  {
  clear();
  delete _head;
  _head = nullptr;
  }


🌈拷贝构造


此处的浅拷贝会导致：


二者修改的都是同一个链表的数据

析构两次会崩溃的问题


所以我们要实现深拷贝—— ps:（this）的哨兵位不释放，已经换给lt2，tmp出作用域要释放


✅传统写法：利用范围for🍬尾插——


list(const list<T>& lt)
  {
   empty_init();
      for(auto& e : lt)
      {
        push_back(e);
      }
  }


✅现代写法：


//lt2(lt1)
  list(const list<T>& lt)
  {
  empty_init();
  list<T> tmp = (lt.begin(), lt.end());
  swap(tmp);
  }


也实现了swap函数


void swap(list<T>& x)//这里的不是list<T>也可以，因为在这个类里面
  {
  std::swap(_head, x._head);
  }


🌈赋值重载


✅传统写法：


//lt1 = lt3
    list<T>& operator=(const list<T>& lt)
    {
        if (this != &lt)
        {
            clear(); //清理lt1
            for (auto e : lt)
            {
                push_back(e);
            }
        }
        return *this;
    }


✅现代写法：（压榨思路）


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


🌈小细节


我们可以看见文档里面的list都没有加类型


在类的外面必须要有模板参数:list<T> , 类名不是类型，带模板参数才是类型

在类里面：可以用类名代表类型（真心不建议）


五. list & vector 区别和联系

【面试题】 list & vector的区别和联系


image.png


附源码

list.h
#pragma once
#include<iostream>
using namespace std;
namespace ljj
{
  template<class T>
  class list_node
  {
  public:
  friend class list<T>;
  T _data;
  list_node<T>* _next;
  list_node<T>* _prev;
  //构造
  list_node(const T& x = T())//全缺省 ~ 构造匿名对象
    :_data(x)
    ,_next(nullptr)
    ,_prev(nullptr)
  {}
  };
  //  typedef __list_iterator<T, T&, T*>
  //  typedef __list_iterator<T, cosnt T&, const T*>
  template<class T, class Ref, class Ptr>//模板参数泛型化
  struct __list_iterator
  {
  typedef list_node<T> Node;
  typedef __list_iterator<T,Ref,Ptr> iterator;
  typedef bidirectional_iterator_tag iterator_category;
  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  Node* _node;//节点指针
  __list_iterator(Node* node)//提供一个节点构造
    :_node(node)
  {}
  bool operator!=(const iterator& it) const
  {
    return _node != it._node;
  }
  bool operator==(const iterator& it) const
  {
    return _node == it._node;
  }
  //*it -> it.opeartor*()    可读可写
  //const T& operator*()    不能重载，因为返回值不同
  //T& operator*()
  Ref operator*()
  {
    return _node->_data;
  }
  //  ->    
  //T* operator->()
  Ptr 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;
  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);
  }
  //构造
  list()
  {
    //_head = new Node;
    //_head->_next = _head;
    //_head->_prev = _head;
    empty_init();
  }
  //拷贝构造
  //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(tmp);
    return *this;
  }
  void swap(list<T>& x)//这里的不是list<T>也可以，因为在这个类里面
  {
    std::swap(_head, x._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()
  {
    clear();
    delete _head;
    _head = nullptr;
  }
  //clear 不清理头结点
  void clear()
  {
    iterator it = begin();
    while (it != end())
    {
    it = erase(it);//注意要给给it ，因为erase后此结点失效，返回下一个节点的迭代器
    }
  }
  //尾插
  void push_back(const T& x)
  {
    //Node* tail = _head->_prev;
    //Node* newnode = new Node(x);
    _head      tail     newnode
    //tail->_next = newnode;
    //newnode->_prev = tail;
    //newnode->_next = _head;
    //_head->_prev = newnode;
    //复用insert
    insert(end(), x);
  }
  //头插
  void push_front(const T& x)
  {
    insert(begin(), x);
  }
  //插入
  iterator insert(iterator pos, const T& x)
  {
    Node* cur = pos._node;//迭代器是struct，就能访问其成员
    Node* prev = cur->_prev;
    Node* newnode = new Node(x);
    //prev   newnode   cur
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;
    return iterator(newnode);//构造迭代器返回
  }
  //尾删
  void pop_back()
  {
    erase(--end());
  }
  //头删
  void pop_front()
  {
    erase(begin());
  }
  //删除
  iterator erase(iterator pos)
  {
    assert(pos != end());//哨兵位头结点不能删
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    //prev   cur   next
    prev->_next = next;
    next->_prev = prev;
    delete cur;
    return iterator(next);
  }
  private:
  Node* _head;
  };
  void test_list1()
  {
  list<int> lt;
  lt.push_back(1);
  lt.push_back(2);
  lt.push_back(3);
  lt.push_back(4);
  lt.push_back(5);
  //只能迭代器遍历
  list<int>::iterator it = lt.begin();
  while (it != lt.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
  it = lt.begin();
  while (it != lt.end())
  {
    *it *= 2;
    ++it;
  }
  cout << endl;
  }
  struct pos
  {
  int _a1;
  int _a2;
  pos(int a1 = 0 , int a2 = 0)
    :_a1(a1)
    ,_a2(a2)
  {}
  };
  void test_list2()
  {
  int x = 10;
  int* p1 = &x;
  cout << *p1 << endl;
  pos aa;
  pos* p2 = &aa;
  p2->_a1;
  p2->_a2;//找结构体成员
  list<pos> lt;
  lt.push_back(pos(10, 20));
  lt.push_back(pos(20, 50));
  list<pos>::iterator it = lt.begin();
  while (it != lt.end())
  {
    //cout << (*it)._a1 << ":" << (*it)._a2 << endl;
    cout << it->_a1 << ":" << it->_a2 << endl;
    ++it;
  }
  cout<< endl;
  }
  void test_list3()
  {
  list<int> lt;
  lt.push_back(1);
  lt.push_back(2);
  lt.push_back(3);
  lt.push_back(4);
  lt.push_back(5);
  list<int> copy = lt;
  for (auto e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
  }
}
文章标签：
C++
容器
编译器
关键词：
C++ list
张小姐的猫
目录
相关文章
Hoshiᅟᅠ
|
1月前
|
存储 搜索推荐 C++
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器2
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器
Hoshiᅟᅠ
47 2
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器2
白子寰
|
21天前
|
存储 算法 C++
【C++打怪之路Lv10】-- list
【C++打怪之路Lv10】-- list
白子寰
14 1
Hoshiᅟᅠ
|
1月前
|
存储 C++ 容器
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器1
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器
Hoshiᅟᅠ
51 5
Hoshiᅟᅠ
|
1月前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱：从底层设计到高效应用的全景解析（附源码）
【C++篇】揭开 C++ STL list 容器的神秘面纱：从底层设计到高效应用的全景解析（附源码）
Hoshiᅟᅠ
49 2
是店小二呀
|
1月前
|
C++
【C++】C++ STL 探索：List使用与背后底层逻辑（三）
【C++】C++ STL 探索：List使用与背后底层逻辑
是店小二呀
56 2
是店小二呀
|
1月前
|
C++
【C++】C++ STL 探索：List使用与背后底层逻辑（二）
【C++】C++ STL 探索：List使用与背后底层逻辑
是店小二呀
25 2
是店小二呀
|
1月前
|
存储 编译器 C++
【C++】C++ STL 探索：List使用与背后底层逻辑（一）
【C++】C++ STL 探索：List使用与背后底层逻辑
是店小二呀
64 2
徐霞客320
|
1月前
|
存储 缓存 C++
C++番外篇——list与vector的比较
C++番外篇——list与vector的比较
徐霞客320
21 0
徐霞客320
|
1月前
|
C++
C++番外篇——list的实现
C++番外篇——list的实现
徐霞客320
19 0
徐霞客320
|
1月前
|
存储 C++ 容器
C++入门9——list的使用
C++入门9——list的使用
徐霞客320
18 0