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

C++——list的使用及其模拟实现

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

list


本章思维导图

注：本章思维导图对应的 .png和 .xmind文件都以同步至 资源，可免费查阅

list也是C++标准模板库中的一大容器，事实上，他就是我们在数据结构中学的带头循环双向链表

接下来，让我们来学习它的基本使用以及模拟实现：

1. 基本使用

1.1 list对象的定义

template < class T, class Alloc = allocator<T> > class list;
  • 作为标准模板库中的容器，list同样也是一个类模板
  • 如果要定义一个list对象，就需要指定其存储的数据类型T。例如：list<int>

1.2 增（插入数据）

list作为带头循环双向链表，其支持头插（push_front）、尾插(push_back)、在pos位置之前插入（insert）等添加数据的操作

void push_back (const value_type& val);
void push_front (const value_type& val);
iterator insert (iterator position, const value_type& val);

接下来做简单的演示：

#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<int> lt;
  //尾插
  for (int i = 0; i < 3; i++) lt.push_back(i);
  for (auto& e : lt)  cout << e << " ";
  cout << endl;
  //头插
  for (int i = 3; i < 6; i++) lt.push_front(i);
  for (auto& e : lt)  cout << e << " ";
  cout << endl;
  //在`pos`前插入
  lt.insert(lt.end(), 99);
  for (auto& e : lt)  cout << e << " ";
  cout << endl;
  return 0;
}

output:

0 1 2
5 4 3 0 1 2
5 4 3 0 1 2 99

1.3 删（删除数据）

和添加数据一样，list删除数据同样也支持**头删（pop_front）、尾删（pop_back）、删除pos位置的节点（erase）**等删除操作

void pop_front();
void pop_back();
iterator erase (iterator position);

接下来做简单的演示：

#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<int> lt;
  for (int i = 0; i < 5; i++) lt.push_back(i + 1);
  //尾删
  lt.pop_back();
  for (auto& e : lt)  cout << e << " ";
  cout << endl;
  //头删
  lt.pop_front();
  for (auto& e : lt)  cout << e << " ";
  cout << endl;
  //删除`pos`处的节点
  lt.erase(lt.begin());
  for (auto& e : lt)  cout << e << " ";
  cout << endl;
  return 0;
}

output:

1 2 3 4
2 3 4
3 4

1.4 遍历访问

不同于string和vector，list并不支持[]访问。list只有两种访问方式：

  • 迭代器访问
  • 范围for
  • 实际上，范围for使用的同样也是迭代器
  • 关于list的迭代器后面会做详细说明，这里仅做使用展示

接下来做简单的演示：

#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<int> lt;
  for (int i = 0; i < 5; i++) lt.push_back(i + 1);
    //迭代器访问
  list<int>::iterator it = lt.begin();
  while (it != lt.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
  //范围for
  for (auto& e : lt)  cout << e << " ";
  cout << endl;
  return 0;
}

2. 模拟实现

不同于string、vector这种连续的结构，对于存储空间不连续的list而言，其模拟实现就要复杂了许多

接下来进行逐步分析：

2.1 节点类ListNode

  • list是带头循环双向链表，其每个节点都存储着：前一个节点和后一个节点的指针以及存储的数据。
  • 因此，我们需要创建一个ListNode类来存储对应的信息
template<class T>
struct ListNode
{
  ListNode<T>* _next;
  ListNode<T>* _prev;
  T          _data;
    //构造函数
  ListNode(const T& value = T())
    : _next(nullptr)
    , _prev(nullptr)
    , _data(value)
  {}
};

注：

  • 不要忘记在C++中**struct不是结构体而是一个类**，只是其默认的访问限定符为public。因此它也需要构造函数
  • ListNOde是一个类模板，所以ListNode不是类名，而是模板名；ListNode<T>才是类名

2.2 封装ListNode类，实现list基本功能

实现好了ListNOde类后，我们就可以将其封装进list类中，利用list对其进行管理：

template<class T>
class list
{
    typedef ListNode<T> Node;
public:
    //构造
    list()
    {
        _head = new Node;
        _head->_next = _head;
        _head->_prev = _head;
    }
    //尾插
    void push_back(const T& value = T())
    {
        Node* newNode = new Node(value);
        Node* tail = _head->_prev;
        tail->_next = newNode;
        newNode->_prev = tail;
        newNode->_next = _head;
        _head->_prev = newNode;
    }
    //尾删
    void pop_back()
    {
        assert(begin() != end());
        Node* tail = _head->_prev;
        Node* newTail = tail->_prev;
        _head->_prev = newTail;
        newTail->_next = _head;
        delete tail;
    }
    //头插
    void push_front(const T& value = T())
    {
        Node* cur = _head->_next;
        Node* newNode = new Node(value);
        _head->_next = newNode;
        newNode->_prev = _head;
        newNode->_next = cur;
        cur->_prev = newNode;
    }
    //头删
    void pop_front()
    {
        assert(begin() != end());
        Node* cur = _head->_next;
        cur->_next->_prev = _head;
        _head->_next = cur->_next;
        delete cur;
    }
    //交换两个list
    void swap(list<T>& it)
    {
        std::swap(_head, it._head);
    }
private:
    Node* _head;
};

注：部分需要用到迭代器的功能放到后面实现

2.3 实现迭代器iterator

让我们再来回顾一下C++迭代器的概念：

迭代器是一个设计模式，它允许你遍历一个容器（如数组、列表、向量等）的所有元素，而无需知道容器的底层表示方式

也就是说，迭代器为我们提供了一个统一的方式来遍历容器。例如我们++一个迭代器就可以指向其后一个元素，--一个迭代器就可以指向前一个元素，而不要管这个容器具体是什么。

  • 迭代器的底层实际上都是指针
  • 对于string、vector这种连续的物理空间，他们的迭代器很好实现，就是原生指针
  • 但是对于list这种物理空间并不连续的存储结构，一个节点的指针++后并不能指向它后面的指针，因此就不能使用原生指针来实现其迭代器了。

因此，为了让屏蔽节点的指针++后不能指向它后面的指针 这一缺陷，我们就需要对ListNode类进行封装，使其++和- - 等操作符合迭代器的规范。而对其封装的类，就是我们的迭代器__List_iterator

template<class T>
struct __list_iterator
{
    typedef ListNode<T> Node;
    typedef __list_iterator<T> self;
    Node* _node;
    __list_iterator(Node* node)
        : _node(node)
        {}
    //++it
    self& operator++ ()
    {
        _node = _node->_next;
        return *this;
    }
    //it++
    self operator++ (int)
    {
        self temp(_node);
        _node = _node->_next;
        return temp;
    }
    //--it
    self& operator-- ()
    {
        _node = _node->_prev;
        return *this;
    }
    //it--
    self operator-- (int)
    {
        self temp(_node);
        _node = _node->_prev;
        return temp;
    }
    T& operator* ()
    {
        return _node->_data;
    }
    T* operator-> ()
    {
        return &_node->_data;
    }
    bool operator!= (const self& value)
    {
        return _node != value._node;
    }
    bool operator == (const self& value)
    {
        return _node == value._node;
    }
};

2.3.1 实现const迭代器const_iterator

要实现一个const迭代器，最容易想到的方法，当然就是复制一份普通的迭代器__list_iterator对象，再对operator*()和operator->()的返回值做简单的修改就行了：

template<class T>
struct __list_const_iterator
{
    typedef ListNode<T> Node;
    typedef __list_const_iterator<T> self;
    Node* _node;
    __list_const_iterator(Node* node)
        : _node(node)
        {}
    //++it
    self& operator++ ()
    {
        _node = _node->_next;
        return *this;
    }
    //it++
    self operator++ (int)
    {
        self temp(_node);
        _node = _node->_next;
        return temp;
    }
    //--it
    self& operator-- ()
    {
        _node = _node->_prev;
        return *this;
    }
    //it--
    self operator-- (int)
    {
        self temp(_node);
        _node = _node->_prev;
        return temp;
    }
    const T& operator* ()
    {
        return _node->_data;
    }
    const T* operator-> ()
    {
        return &_node->_data;
    }
    bool operator!= (const self& value)
    {
        return _node != value._node;
    }
    bool operator == (const self& value)
    {
        return _node == value._node;
    }
};

但是，这样的做法无疑会添加大量冗余的代码，显然不是最恰当的。因此最初编写标准模板库的大佬们就想出了这样的办法——添加类模板参数。也就是说，我们可以将__list_iterator类模板写成这样：

template<class T, class Referance, class Ptr>
struct __list_iterator
{}
  • T就是list存储的数据类型
  • Referance就是operator*()的返回值，如果是非const对象，就传入T&；如果是const对象，就传入const T&
  • Ptr就是operator->()的返回值，如果是非const对象，就传入T*；如果是const对象，就传入const T*

这样，我们就可以将普通迭代器和const迭代器整合为一个迭代器__list_iterator：

template<class T, class Referance, class Ptr>
struct __list_iterator
{
    typedef ListNode<T> Node;
    typedef __list_iterator<T, Referance, Ptr> self;
    Node* _node;
    __list_iterator(Node* node)
        : _node(node)
        {}
    //++it
    self& operator++ ()
    {
        _node = _node->_next;
        return *this;
    }
    //it++
    self operator++ (int)
    {
        self temp(_node);
        _node = _node->_next;
        return temp;
    }
    //--it
    self& operator-- ()
    {
        _node = _node->_prev;
        return *this;
    }
    //it--
    self operator-- (int)
    {
        self temp(_node);
        _node = _node->_prev;
        return temp;
    }
    Referance operator* ()
    {
        return _node->_data;
    }
    Ptr operator-> ()
    {
        return &_node->_data;
    }
    bool operator!= (const self& value)
    {
        return _node != value._node;
    }
    bool operator == (const self& value)
    {
        return _node == value._node;
    }
};

2.3.2 实现反向迭代器reverse_iterator

需要注意：

为了实现对称性，C++规定：

  • 反向迭代器的开头rbegin()实际上是正向迭代器的结束end()；反向迭代器的结束rend()即为正向迭代器的开始begin()
  • 当对一个反向迭代器进行*操作时，并不会对当前的位置进行*操作，而是会对当前位置的之前一个位置进行*操作

和const迭代器，一样写出反向迭代器最简单的方式同样是复制一下普通迭代器类，再修改一下代码逻辑即可。这里不再做展示。

但很显然，这种方法同样也不是最好的。

最初编写标准模板库的大佬们在写反向迭代器的代码时会思考这样的问题：

是否可以写这样一份代码，可以将所有的正向迭代器都转化为对应的反向迭代器呢？

事实上，他们确实是这样做的：

  • 可以新建一个头文件reverse_iterator，其包含一个反向迭代器类Reverse_iterator，其实现了关于反向迭代器的各种操作。
  • 为了做到可以 将所有的正向迭代器转化为其对应的反向迭代器 ，其各种操作并不需要我们手动实现，而是需要复用正向迭代器的方法

我们可以先来看看其具体的实现：

template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
  Reverse_iterator(const Iterator& it)
    : _it(it)
  {}
  typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
  Self& operator++ ()
  {
    --_it;
    return *this;
  }
  Self& operator-- ()
  {
    ++_it;
    return *this;
  }
  Self operator++ (int)
  {
    Self tmp = _it;
    --_it;
    return tmp;
  }
  Self operator-- (int)
  {
    Self tmp = _it;
    ++_it;
    return tmp;
  }
  //注意，*运算不是对当前位置
  //而是对当前位置的前一个位置进行运算
  Ref operator* ()
  {
    Iterator tmp = --_it;
    ++_it;
    return *tmp;
  }
  Ptr operator-> ()
  {
    return &(operator*());
  }
  bool operator!= (const Self& it)
  {
    return _it != it._it;
  }
  bool operator== (const Self& it)
  {
    return _it == it._it;
  }
  Iterator _it;
};
  • Iterator即为对应正向迭代器
  • 这里通过对Iterator的封装，利用Iterator的方法来间接实现其反向迭代器的操作，从而就可以实现用同一份代码就可以将所有的正向迭代器都转换为其对应的反向迭代器

3. list容器模拟实现代码

reverse_list.h

template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
  Reverse_iterator(const Iterator& it)
    : _it(it)
  {}
  typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
  Self& operator++ ()
  {
    --_it;
    return *this;
  }
  Self& operator-- ()
  {
    ++_it;
    return *this;
  }
  Self operator++ (int)
  {
    Self tmp = _it;
    --_it;
    return tmp;
  }
  Self operator-- (int)
  {
    Self tmp = _it;
    ++_it;
    return tmp;
  }
  Ref operator* ()
  {
    Iterator tmp = --_it;
    ++_it;
    return *tmp;
  }
  Ptr operator-> ()
  {
    return &(operator*());
  }
  bool operator!= (const Self& it)
  {
    return _it != it._it;
  }
  bool operator== (const Self& it)
  {
    return _it == it._it;
  }
  Iterator _it;
};

list.h

#pragma once
#include <iostream>
#include <list>
#include <assert.h>
#include "reverse_iterator.h"
using namespace std;
namespace TEST
{
  template<class T>
  struct ListNode
  {
    ListNode<T>* _next;
    ListNode<T>* _prev;
    T          _data;
    ListNode(const T& value = T())
      : _next(nullptr)
      , _prev(nullptr)
      , _data(value)
    {}
  };
    //正向迭代器
  template<class T, class Referance, class Ptr>
  struct __list_iterator
  {
    typedef ListNode<T> Node;
    typedef __list_iterator<T, Referance, Ptr> self;
    Node* _node;
    __list_iterator(Node* node)
      : _node(node)
    {}
    //++it
    self& operator++ ()
    {
      _node = _node->_next;
      return *this;
    }
    //it++
    self operator++ (int)
    {
      self temp(_node);
      _node = _node->_next;
      return temp;
    }
    //--it
    self& operator-- ()
    {
      _node = _node->_prev;
      return *this;
    }
    //it--
    self operator-- (int)
    {
      self temp(_node);
      _node = _node->_prev;
      return temp;
    }
    Referance operator* ()
    {
      return _node->_data;
    }
    Ptr operator-> ()
    {
      return &_node->_data;
    }
    bool operator!= (const self& value)
    {
      return _node != value._node;
    }
    bool operator == (const self& value)
    {
      return _node == value._node;
    }
  };
  template<class T>
  class list
  {
    typedef ListNode<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<const_iterator, const T&, const T*> const_reverse_iterator;
    list()
    {
      _head = new Node;
      _head->_next = _head;
      _head->_prev = _head;
    }
    list(list<T>& it)
    {
      _head = new Node;
      _head->_next = _head;
      _head->_prev = _head;
      for (const auto e : it)
      {
        push_back(e);
      }
    }
    list<T>& operator= (list<T> it)
    {
      swap(it);
      return *this;
    }
    void push_back(const T& value = T())
    {
      insert(end(), value);
    }
    void pop_back()
    {
      erase(--end());
    }
    void push_front(const T& value = T())
        {
      insert(begin(), value);
    }
    void pop_front()
    {
      erase(begin());
    }
    iterator erase(iterator pos)
    {
      assert(begin() != end());
      Node* curNode = pos._node;
      Node* prevNode = curNode->_prev;
      Node* nextNode = curNode->_next;
      nextNode->_prev = prevNode;
      prevNode->_next = nextNode;
      delete curNode;
      return nextNode;
    }
    iterator insert(iterator pos, const T& value = T())
    {
      Node* newNode = new Node(value);
      Node* prevNode = pos._node->_prev;
      Node* curNode = pos._node;
      //prevNode newNode curNode;
      prevNode->_next = newNode;
      newNode->_prev = prevNode;
      newNode->_next = curNode;
      curNode->_prev = newNode;
      return newNode;
    }
    void swap(list<T>& it)
    {
      std::swap(_head, it._head);
    }
    void clear()
    {
      iterator it = begin();
      while (it != end())
      {
        it = erase(it);
      }
    }
    iterator begin()
    {
      return _head->_next;
    }
    const_iterator begin() const
    {
      return _head->_next;
    }
    iterator end()
    {
      return _head;
    }
    const_iterator end() const
    {
      return _head;
    }
    reverse_iterator rbegin()
    {
      return end();
    }
    const_reverse_iterator rbegin() const
    {
      return end();
    }
    reverse_iterator rend() 
    {
      return begin();
    }
    const_reverse_iterator rend() const
    {
      return begin();
    }
    ~list()
    {
      clear();
      delete _head;
      _head = nullptr;
    }
  private:
    Node* _head;
  };
}

本篇完

如果错误敬请指正

文章标签：
C++
容器
存储
设计模式
关键词：
C++ list
阿里云Forward
目录
相关文章
半截诗
|
1月前
|
存储 搜索推荐 C++
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器2
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器
半截诗
51 2
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器2
白子寰
|
1月前
|
存储 算法 C++
【C++打怪之路Lv10】-- list
【C++打怪之路Lv10】-- list
白子寰
21 1
半截诗
|
1月前
|
存储 C++ 容器
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器1
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器
半截诗
54 5
半截诗
|
1月前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱：从底层设计到高效应用的全景解析（附源码）
【C++篇】揭开 C++ STL list 容器的神秘面纱：从底层设计到高效应用的全景解析（附源码）
半截诗
56 2
是店小二呀
|
1月前
|
C++
【C++】C++ STL 探索：List使用与背后底层逻辑（三）
【C++】C++ STL 探索：List使用与背后底层逻辑
是店小二呀
59 2
是店小二呀
|
1月前
|
C++
【C++】C++ STL 探索：List使用与背后底层逻辑（二）
【C++】C++ STL 探索：List使用与背后底层逻辑
是店小二呀
27 2
是店小二呀
|
1月前
|
存储 编译器 C++
【C++】C++ STL 探索：List使用与背后底层逻辑（一）
【C++】C++ STL 探索：List使用与背后底层逻辑
是店小二呀
68 2
徐霞客320
|
1月前
|
存储 缓存 C++
C++番外篇——list与vector的比较
C++番外篇——list与vector的比较
徐霞客320
22 0
徐霞客320
|
1月前
|
C++
C++番外篇——list的实现
C++番外篇——list的实现
徐霞客320
19 0
徐霞客320
|
1月前
|
存储 C++ 容器
C++入门9——list的使用
C++入门9——list的使用
徐霞客320
19 0

热门文章

最新文章

  • 1
    【C++ 常见的异步机制】探索现代异步编程：从 ASIO 到协程的底层机制解析
  • 2
    C++11中的tuple应用：让函数返回多个值
  • 3
    C++第1周项目2——日期结构体
  • 4
    C++中消息自动派发之一 About JSON
  • 5
    读书笔记 effective c++ Item 53 关注编译器发出的警告
  • 6
    《Effective C++》item25：考虑写出一个不抛异常的swap函数
  • 7
    Visual C++ 时尚编程百例002(MFC窗口)
  • 8
    【编程练习】收集的一些c++代码片，算法排序，读文件，写日志，快速求积分等等
  • 9
    C/C++中#define的探究
  • 10
    2013级C++第1周(春)项目——枚举类型与结构体初步
  • 1
    Python中的列表（List）和元组（Tuple）是两种重要的数据结构
    56
  • 2
    stack=s+stack#TypeError: can only concatenate str (not “list“) to str
    36
  • 3
    DOM 节点列表长度（Node List Length）
    31
  • 4
    【Python】已解决：IndexError: list index out of range
    393
  • 5
    Java List接口实现原理与性能评估
    77
  • 6
    【Python】已解决：TypeError: descriptor ‘index‘ for ‘list‘ objects doesn‘t apply to a ‘str‘ object
    126
  • 7
    DOM 节点列表长度（Node List Length）
    22
  • 8
    DOM 节点列表长度（Node List Length）
    31
  • 9
    若依修改，配置了一个接口路径出现了，如何放通接口{ “msg“: “请求访问：/code/list，认证失败，无法访问系统资源“, “code“: 401}
    1044
  • 10
    Redis09-----List类型，有序，元素可以重复，插入和删除快，查询速度一般，一般保存一些有顺序的数据，如朋友圈点赞列表，评论列表等，LPUSH user 1 2 3可以一个一个推
    72

    • 相关课程

    更多
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce

    • 相关实验场景

    更多
  • 零基础入门Serverless：TodoList应用创建
    • 下一篇
    无影云桌面