【C++】list介绍以及模拟实现（超级详细）-阿里云开发者社区

前言

string vector的是存储是基于物理空间上连续的，而list是作为线性的链式结构，是值得学习的。

`list`介绍

std::list是C++标准模板库（STL）中的一个容器适配器，它内部实现为双向链表结构。
这种设计使得std::list能够在常数时间内进行任意位置的插入和删除操作，这是其相对于其他序列容器如std::vector的显著优点。
std::list不支持随机访问，即无法直接通过索引来访问容器中的元素，这通常需要从头部或尾部开始迭代到目标位置.

标准库容器 `std::list` 与 `std::vector` 的优缺点

std::list: 作为一个双向链表，std::list 在插入和删除操作上具有优势，因为这些操作只涉及到改变相邻节点的指针，而不需要移动其他元素。此外，std::list 不需要预分配额外的内存，可以更好地处理动态内存分配，减少内存碎片.

std::vector: 作为一个动态数组，std::vector 提供了高效的随机访问能力，可以通过下标直接访问任意位置的元素，其访问效率为 O(1). 此外，std::vector 通常具有较高的空间利用率和缓存友好性，因为其元素在内存中是连续存储的.

缺点

std::list: 由于非连续的内存存储，std::list 在访问元素时效率较低，因为可能需要从头开始遍历链表。此外，每个节点都需要存储额外的指针信息，这增加了内存开销.

	vector	list
底层结构	动态顺序表，一段连续空间	带头结点的双向循环链表
随机访问	支持随机访问，访问某个元素效率O(1)	不支持随机访问，访问某个元素效率O(N)

插入
删除

任意位置插入和删除效率低，需要搬移元素，
时间复杂度为O(N)，插入时有可能需要增容，
增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低

任意位置插入和删除效率高，不需要搬移元
素，时间复杂度为 O(1)

插入
删除

底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高

底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低

迭代器

原生态指针

对原生态指针(节点指针)进行封装

迭代器
失效

在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效

插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响

用
场景

需要高效存储，支持随机访问，不关心插入删除效率

大量插入和删除操作，不关心随机访问

`list`的基本操作

构造函数

【C++】vector介绍以及模拟实现	接口说明
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list()	构造空的list

list (const list& x)	拷贝构造函数
list (InputIterator ﬁrst, InputIterator last)	用[ﬁrst, last)区间中的元素构造list

`list iterator`

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

函数声明	接口说明
begin + end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器

rbegin + rend

返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置

`list capcacity`

函数声明	接口说明

empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

`list modify`

函数声明	接口说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素

push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素
insert	在list position 位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

`list`模拟实现

存贮结构（双向带头循环）

定义一个类（C语言：结构体）存储数据，作为指向下一个上一个的节点

namespace MyList
{
    //LIst节点
  template<class T>
  struct _list_node
  {
    _list_node<T>* _next;
    _list_node<T>* _prev;
    T _val;

    _list_node(const T& val = T())
      : _next(nullptr)
      , _prev(nullptr)
      , _val(val)
    {}
  };
}

`iterator`

迭代器有两种实现方式，具体应根据容器底层数据结构实现：

原生态指针，比如：vector string
将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：

1. 指针可以解引用，迭代器的类中必须重载operator*()

2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载 oprator->()

3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)

4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()

`iterator`结构

三个模板参数

第一个模板参数控制类型
第二个模板参数控制返回值类型const 非const
第三个模板参数控制返回的list类的类型const 非const

Node* _node;需要定义一个指针，指向list节点

template<class T,class Ref,class ptr>
    struct _list_iterator
    {
        typedef _list_node<T> Node;
        typedef _list_iterator<T, Ref,ptr> self;

        Node* _node;
    };

`operator!=` `operator ==`

//重载operator!=
bool operator!=(const self& it)const 
{
    return _node != it._node;
}
//重载operator==
bool operator==(const self& it)const
{
    return _node == it._node;
}

`operator++`

//重载operator++(前置)
self& operator++()
{
    _node = _node->_next;

    return *this;
}
//重载operator++(后置)
self& operator++(int)
{
    self tmp(*this);

    _node = _node->_next;

    return tmp;
}

`operator--`

//重载operator--(前置)
self& operator--()
{
    _node = _node->_prev;

    return *this;
}
//重载operator--(后置)
self& operator--(int)
{
    self tmp(*this);

    _node = _node->_prev;

    return tmp;
}

operator* operator->

//重载operator*
Ref& operator* ()
{
    return _node->_val;
}
//重载operator->
ptr operator->()
{
    return _node->_val;
}

`list`数据结构

构造函数

list的初始化

双向带带头循环

_head

//空list初始化
void empty_init()
{
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;

    _size = 0;
}

节点初始化

默认构造函数
默认构造函数
用迭代器初始化
拷贝构造函数
赋值运算符重载
赋值运算符重载

//默认构造函数
list()
{
    empty_init();
}
//默认构造函数
list(int n, const T& val = T())
{
    empty_init();

    while (n--)
    {
        push_back(val);
    }

}
//用迭代器初始化
template <class Iterator>
    list(Iterator first, Iterator last)
{
    empty_init();

    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}
//拷贝构造函数
list(const list<T>& lt)
{
    empty_init();

    for (auto e : lt)
    {
        push_back(e);
    }
}
//赋值运算符重载
list<T> operator=(list<T> lt)
{
    swap(lt);

    return *this;
}
//赋值运算符重载
~list()
{
    clear();

    delete _head;
}

迭代器

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

`list modify`

insert

在pos位置插入节点，同数据结构是一样的，在这里面不过多赘述（可以参考）

//insert
iterator insert(iterator pos, const T& x)
{
    Node* newcode = new Node(x);
    Node* cur = pos._node;
    Node* prev = cur->_prev;

    prev->_next = newcode;
    newcode->_prev = prev;
    newcode->_next = cur;
    cur->_prev = newcode;

    ++_size;

    return pos;
}

erase

删除迫使位置的节点，同样（可以参考）

//erase
iterator erase(iterator pos)
{
    assert(pos._node != _head);

    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;

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

    delete cur;

    --_size;

    return next;
}

头插、头删、尾插、尾删

可以复用insert ersae STL标准模板库也是进行复用

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

`list operator`

交换

void swap(list<T> lt)
{
    std::swap(_head, lt._head);
    std::swap(_size, lt._size);

}

clear

析构函数也是利用了clear

//删除
void clear()
{
    iterator it = begin();

    while (it != end())
    {
        it = erase(it);
        ++it;
    }

}

源码

#pragma once
#include <iostream>
#include <assert.h>

namespace MyList
{
  //节点
  template<class T>
  struct _list_node
  {
    _list_node<T>* _next;
    _list_node<T>* _prev;
    T _val;

    _list_node(const T& val = T())
      : _next(nullptr)
      , _prev(nullptr)
      , _val(val)
    {}
  };
  //迭代器
  template<class T,class Ref,class ptr>
  struct _list_iterator
  {
    typedef _list_node<T> Node;
    typedef _list_iterator<T, Ref,ptr> self;
    
    Node* _node;

    _list_iterator (Node* node)
      :_node(node)
    {}
    //重载operator*
    Ref& operator* ()
    {
      return _node->_val;
    }
    //重载operator->
    ptr operator->()
    {
      return _node->_val;
    }
    //重载operator++(前置)
    self& operator++()
    {
      _node = _node->_next;

      return *this;
    }
    //重载operator++(后置)
    self& operator++(int)
    {
      self tmp(*this);

      _node = _node->_next;

      return tmp;
    }
    //重载operator--(前置)
    self& operator--()
    {
      _node = _node->_prev;

      return *this;
    }
    //重载operator--(后置)
    self& operator--(int)
    {
      self tmp(*this);

      _node = _node->_prev;

      return tmp;
    }


    //重载operator!=
    bool operator!=(const self& it)const 
    {
      return _node != it._node;
    }
    //重载operator==
    bool operator==(const self& it)const
    {
      return _node == it._node;
    }

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

    //空list初始化
    void empty_init()
    {
      _head = new Node;
      _head->_next = _head;
      _head->_prev = _head;

      _size = 0;
    }
    //用n个val初始化
    list(int n, const T& val = T())
    {
      empty_init();

      while (n--)
      {
        push_back(val);
      }

    }
    //用迭代器初始化
    template <class Iterator>
    list(Iterator first, Iterator last)
    {
      empty_init();

      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }

    //默认构造函数
    list()
    {
      empty_init();
    }
    //拷贝构造函数
    list(const list<T>& lt)
    {
      empty_init();

      for (auto e : lt)
      {
        push_back(e);
      }
    }


    //赋值运算符重载
    list<T> operator=(list<T> lt)
    {
      swap(lt);

      return *this;
    }

    //析构函数
    ~list()
    {
      clear();

      delete _head;
    }
    //删除
    void clear()
    {
      iterator it = begin();

      while (it != end())
      {
        it = erase(it);
        ++it;
      }

    }


    //迭代器
    iterator begin()
    {
      return _head->_next;
    }
    iterator end()
    {
      return _head;
    }
    const_iterator begin()const
    {
      return _head->_next;
    }
    const_iterator end()const
    {
      return _head;
    }

    //void push_back(const T& x)
    //{
    //  Node* newcode = new Node(x);
    //  Node* tail = _head->_prev;

    //  tail->_next = newcode;
    //  newcode->_next = _head;

    //  newcode->_prev = tail;
    //  _head->_prev = newcode;

    //  ++_size;
    //}
    
    // 头插
    void push_front(const T& x)
    {
      insert(begin(), x);
    }
    //头删
    void pop_front()
    {
      erase(begin());
    }
    //尾插
    void push_back(const T& x)
    {
      insert(begin());
    }
    //尾删
    void pop_back()
    {
      erase(--end());
    }
    //insert
    iterator insert(iterator pos, const T& x)
    {
      assert(pos._node != _head);

      Node* newcode = new Node(x);
      Node* cur = pos._node;
      Node* prev = cur->_prev;

      prev->_next = newcode;
      newcode->_prev = prev;
      newcode->_next = cur;
      cur->_prev = newcode;

      ++_size;

      return pos;
    }
    //erase
    iterator erase(iterator pos)
    {
      assert(pos._node != _head);

      Node* cur = pos._node;
      Node* prev = cur->_prev;
      Node* next = cur->_next;

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

      delete cur;

      --_size;

      return next;
    }
    //大小
    size_t size()const
    {
      return _size;
    }
    //交换
    void swap(list<T> lt)
    {
      std::swap(_head, lt._head);
      std::swap(_size, lt._size);

    }

  private:
    Node* _head;
    size_t _size;
  };

}

【C++】list介绍以及模拟实现（超级详细）

前言

`list`介绍

标准库容器 `std::list` 与 `std::vector` 的优缺点

缺点

`list`的基本操作

构造函数

`list iterator`

`list capcacity`

`list modify`

`list`模拟实现

存贮结构（双向带头循环）

`iterator`

`iterator`结构

`operator!=` `operator ==`

`operator++`

`operator--`

`list`数据结构

构造函数

list的初始化

节点初始化

迭代器

`list modify`

insert

erase

头插、头删、尾插、尾删

`list operator`

交换

clear

源码

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C++】list介绍以及模拟实现（超级详细）

前言

list介绍

标准库容器 std::list 与 std::vector 的优缺点

缺点

list的基本操作

构造函数

list iterator

list capcacity

list modify

list模拟实现

存贮结构（双向带头循环）

iterator

iterator结构

operator!= operator ==

operator++

operator--

list数据结构

构造函数

list的初始化

节点初始化

迭代器

list modify

insert

erase

头插、头删、尾插、尾删

list operator

交换

clear

源码

热门文章

最新文章

相关课程

相关电子书

`list`介绍

标准库容器 `std::list` 与 `std::vector` 的优缺点

`list`的基本操作

`list iterator`

`list capcacity`

`list modify`

`list`模拟实现

`iterator`

`iterator`结构

`operator!=` `operator ==`

`operator++`

`operator--`

`list`数据结构

`list modify`

`list operator`