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

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

2024-01-30 70
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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
目录
相关文章
ephemerals__
|
21小时前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构，适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码，读者可以更好地理解如何使用这些接口。最后，作者总结了`list`的特点和适用场景，并预告了后续关于`list`模拟实现的文章。
ephemerals__
18 7
蓝易云
|
9天前
|
存储 编译器 C++
C++ initializer_list&&类型推导
在 C++ 中，`initializer_list` 提供了一种方便的方式来初始化容器和传递参数，而右值引用则是实现高效资源管理和移动语义的关键特性。尽管在实际应用中 `initializer_list&&` 并不常见，但理解其类型推导和使用方式有助于深入掌握现代 C++ 的高级特性。
蓝易云
15 4
半截诗
|
2月前
|
存储 搜索推荐 C++
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器2
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器
半截诗
55 2
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器2
白子寰
|
2月前
|
存储 算法 C++
【C++打怪之路Lv10】-- list
【C++打怪之路Lv10】-- list
白子寰
22 1
半截诗
|
2月前
|
存储 C++ 容器
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器1
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器
半截诗
57 5
半截诗
|
2月前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱：从底层设计到高效应用的全景解析（附源码）
【C++篇】揭开 C++ STL list 容器的神秘面纱：从底层设计到高效应用的全景解析（附源码）
半截诗
60 2
是店小二呀
|
2月前
|
C++
【C++】C++ STL 探索：List使用与背后底层逻辑（三）
【C++】C++ STL 探索：List使用与背后底层逻辑
是店小二呀
63 2
是店小二呀
|
2月前
|
C++
【C++】C++ STL 探索：List使用与背后底层逻辑（二）
【C++】C++ STL 探索：List使用与背后底层逻辑
是店小二呀
29 2
是店小二呀
|
2月前
|
存储 编译器 C++
【C++】C++ STL 探索：List使用与背后底层逻辑（一）
【C++】C++ STL 探索：List使用与背后底层逻辑
是店小二呀
75 2
徐霞客320
|
2月前
|
存储 缓存 C++
C++番外篇——list与vector的比较
C++番外篇——list与vector的比较
徐霞客320
24 0

热门文章

最新文章

  • 1
    读书笔记 effective c++ Item 53 关注编译器发出的警告
  • 2
    2013级C++第1周(春)项目——枚举类型与结构体初步
  • 3
    c++模板类
  • 4
    C++第17周项目2——用指针玩字符串（1）连接
  • 5
    C++ Exercises（九）
  • 6
    Mac上写C++
  • 7
    C++ 连接数据库的入口和获取列数、数据
  • 8
    C++之虚函数
  • 9
    Qt实用技巧：Qt中添加对C++11标准的支持（两种方式）
  • 10
    C++ sting字符串函数详解
  • 1
    DataWorks操作报错合集之在使用函数holiday_date遇到报错： “Perhaps you forgot to add it to using list when create funciton.，是什么原因
    49
  • 2
    Python中的列表（List）和元组（Tuple）是两种重要的数据结构
    60
  • 3
    stack=s+stack#TypeError: can only concatenate str (not “list“) to str
    41
  • 4
    DOM 节点列表长度（Node List Length）
    33
  • 5
    【Python】已解决：IndexError: list index out of range
    473
  • 6
    Java List接口实现原理与性能评估
    84
  • 7
    【Python】已解决：TypeError: descriptor ‘index‘ for ‘list‘ objects doesn‘t apply to a ‘str‘ object
    145
  • 8
    DOM 节点列表长度（Node List Length）
    24
  • 9
    DOM 节点列表长度（Node List Length）
    31
  • 10
    若依修改，配置了一个接口路径出现了，如何放通接口{ “msg“: “请求访问：/code/list，认证失败，无法访问系统资源“, “code“: 401}
    1240

    • 相关课程

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

    • 相关电子书

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

    • 相关实验场景

    更多
  • 零基础入门Serverless：TodoList应用创建
    • 下一篇
    阿里云对象存储OSS收费标准：存储、流量和请求等多个计费项详解