C++：List的使用和模拟实现-阿里云开发者社区

创作不易，感谢三连！！

一、List的介绍

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

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

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

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

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

要注意的是，list开始就不支持下标访问了，所以要访问都要以迭代器为准

void Print(const list<int>& l)
{
  //迭代去区间遍历
  list<int>::const_iterator it = l.begin();
  while (it != l.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
  //范围for遍历
  for (auto e : l)
    cout << e << " ";
  cout << endl;
}

二、List的使用注意事项

博主觉得跟之前vector的基本上差不了多少，如果不会看文档用库里面的list的可以去看博主只管关于string和vector的使用。

C++：String类的使用-CSDN博客

C++：Vector的使用-CSDN博客

下面直接介绍List使用中的易错点

2.1 List的迭代器失效问题

我们之前学习vector的时候，知道了insert和erase都有可能存在迭代器失效的问题，那list会出现这种情况吗？？下面来进行分析

insert插入新节点的迭代器，因此insert不可能会出现失效的问题。

而earse必然会失效，因为该迭代器对应的节点被删除了。如果我们想继续用的话，就得利用返回值去更新迭代器，返回值是被删除元素的下一个位置的迭代器。

2.2 List中sort的效率测试

我们用一段代码来测试一下list中sort的性能

void test_op()
{
  srand((unsigned int)time(NULL));
  const int N = 1000000;
  vector<int> v;
  v.reserve(N);
  list<int> lt1;
  list<int> lt2;
  for (int i = 0; i < N; ++i)
  {
    int e = rand();
    lt1.push_back(e);
    lt2.push_back(e);
  }
  // 拷贝到vector排序，排完以后再拷贝回来
  int begin1 = clock();
  for (auto e : lt1)
  {
    v.push_back(e);
  }
  sort(v.begin(), v.end());
  size_t i = 0;
  for (auto& e : lt1)
  {
    e = v[i++];
  }
  int end1 = clock();
  //list调用自己的sort
  int begin2 = clock();
  lt2.sort();
  int end2 = clock();
  printf("vector sort:%d\n", end1 - begin1);
  printf("list sort:%d\n", end2 - begin2);
}

会发现哪怕我先拷贝到vector排完再拷贝回去效率都比list的sort效率高，所以list的sort实际中意义不是很大！！

三、模拟实现的注意事项

还是跟之前模拟实现一样，先看看SGI版本的源码，list本质上是带头双向链表

第一部分链表节点

第二部分迭代器

第三部分、链表

这里我们可以先实现链表节点结构体这里用sturct把权限放开。

//节点的封装
template<class T>
struct list_node
{
  list_node<T>* _prev;
  list_node<T>* _next;
  T _data;
  //节点的构造函数
  list_node(const T& val = T())
    :_prev(nullptr)
    , _next(nullptr)
    , _data(val)
  {}
};

然后封装一个链表，将头结点作为自己的成员变量封装起来

template<class T>
class list
{
  typedef list_node<T>  node;//typedef可以帮助我们简洁代码
  private:
    node* _head;
  };

下面开始进行我们的重中之重——迭代器

四、正向迭代器的实现

2.1 正向迭代器的封装

在学习Vector的时候，我们发现其实vector的迭代器就是一个原生指针，所以我们将他改了名字

这得益于vector空间连续的特点，所以对指针进行加和减再进行解引用可以访问到我们想要的元素，但是链表可以吗？

虽然看似我们好像用箭头连接起来了，但其实他们空间上是不连续的，那我们对一个节点指针进行加减，就很难说能不能找到下一个节点，更多的是找不到的情况

那我们思考一样，如果我们要搞一个迭代器，我们希望怎么去得到我们的数据呢？？我们希望我们解引用的时候，可以拿到他的data，希望++的时候，可以拿到他的next，--的时候，可以拿到他的prev。那我们怎么去改变原生操作符的行为呢？答案就是运算符重载！所以我们可以将迭代器单独封装成一个类去管理节点，改变运算符的行为！！

我们先进行实现，然后再慢慢分析

//封装迭代器
  template<class T, class Ref, class Ptr>//Ref用于引用是否const，Ptr用于指针是否const
  struct list_iterator
  {
    typedef list_node<T> node;
    typedef list_iterator<T, Ref, Ptr>  self;
    node* _node;
    //迭代器的构造函数
    list_iterator(node* n)//迭代器的构造
      :_node(n)
    {}
    //实现*
    Ref operator*() const
    {
      return _node->_data;
    }
    //实现->
    Ptr operator->() const
    {
      return &operator*();    //本来是两个->,为了增强可读性，我们封装了这个函数 比如当我们存储的结构体解引用后有多个成员，那么我们可以通过箭头的直线去找到对应我们想要的成员  
    }
    //前置++
    self& operator++()
    {
      _node = _node->_next;
      return *this;
    }
    //后置++
    self operator++(int)
    {
      self temp(*this);
      ++*this;
      return temp;
    }
    //前置--
    self& operator--()
    {
      _node = _node->_prev;
      return *this;
    }
    //后置--
    self operator--(int)
    {
      self temp(*this);
      --*this;
      return temp;
    }
    //！=
    bool operator!=(const self& s) const
    {
      return _node != s._node;
    }
    //==
    bool operator==(const self& s) const
    {
      return _node == s._node;
    }
  };

第一个模版参数是类型，第二个模版参数是引用，第三个模版参数是指针

Ref和Ptr是用来区分正常的迭代器和const修饰的迭代器，Ref是T&或者是const T&,这样可以在某些时候我们去限制data不能被修改。而Ptr是T*或者是const T*，重载箭头的作用是如果我们data存储的是一个自定义类型，这个时候如果直接解引用肯定是不行的，所以我们的箭头可以在解引用的时候先返回data的地址，然后我们就可以通过箭头去访问他不同的成员变量。

下面举个data存的是自定义类型的例子

2.2 迭代器的使用

template<class T>
class list
{
  typedef list_node<T>  node;//typedef可以帮助我们简洁代码
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);
  }
  private:
    node* _head;
  };

这边我们用到了匿名对象。

思考：这里的const迭代器为什么不能直接用const修饰普通迭代器？？

因为typedef碰到const的话，就不是简单的字符串替换实际上你以为的const T* ，在这里变成了T*const ，因为迭代器我们是希望他可以进行++和--的，而我们只是不希望他指向的内容给改变，所以我们的const要修饰的是指针的内容，而不是修饰指针。

五、list相关的成员函数

3.1 构造函数

1、默认构造函数

因为无论如何都要有哨兵节点，所以我们直接封装一个

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

所以可以这么写

//默认构造函数
  list()
  {
    empty_init();
  }

2、有参构造函数

//有参构造函数
list(size_t n, const T& val = T())
{
  empty_init();
  for (size_t i = n; i > 0; --i)
    push_back(val);
}

3、迭代器区间构造函数

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

4、拷贝构造的传统写法

传统方法就是一个个拷贝过去

//拷贝构造函数传统写法
list(const list<T>& lt)
{
  empty_init();
  for (auto e : lt)
    push_back(e);
}

5、拷贝构造的现代写法+swap

现代写法就是，我先创建一个临时对象让他利用被拷贝对象的迭代器构造出来，然后再交换，窃取革命成功，被利用完后的临时对象会在栈帧结束后被清除（典型的资本家思维）

//交换函数
  void swap(list<T>& temp)
  {
    std::swap(_head, temp._head);
  }
  //拷贝构造函数的现代写法
  list(const list<T>& lt)
  {
    empty_init();
    list<T> temp(lt.begin(), lt.end());//复用迭代器区间构造，让别人构造好了，我再窃取革命成果
    swap(temp);
  }

3.2 clear和析构函数

list不像vector一样，不能直接用头指针delete，因为空间不连续，所以要一个个节点去delete，所以在这之前，我们可以先实现clear，clear的作用是把链表清空，只剩一个头节点，然我们的析构函数再复用clear，然后再单独delete头节点就行了！！

//clear 只留一个头节点
  void clear()
  {
    iterator it = begin();
    while (it != end())
      it = erase(it);
  }
  //析构函数
  ~list()
  {
    clear();
    delete _head;
    _head = nullptr;
  }

3.3 赋值重载和assign

assign和=的本质上都是，先将原来的空间的内容给清空，换成的内容。只不过区别就是assign可以利用迭代器去控制被替换的范围，也可以自己去换成n个一样的元素。所以我们先实现assign，再实现=

1、assign直接替换

//assign(直接替换)
void assign(size_t n, const T& val)
{
  clear();
  for (size_t i = n; i > 0; --i)
    push_back(val);
}

2、assign迭代器区间替换

//assign(迭代器区间替换)
  template <class InputIterator>
  void assign(InputIterator first, InputIterator last)
  {
    clear();
    while (first != last)
    {
      push_back(*first);
      ++first;
    }
  }

3、assign直接替换重载（防止间接寻址）

思考：我们的本意是将lt2替换成5个2，我们发现我们调的竟然是迭代器区间构造的assign，为什么会这样呢？？？？？

因为重载类型会优先找最匹配的，assign的第一个版本的n是size_t类型，我们传的整数默认是int所以会发生强制类型转化，而第二个版本恰好可以变成两个int，所以他会走迭代器区间版本。所以此时有两个方案，第一个方案是我们要在第一个参数后面加u，但是这不符合我们的使用习惯，所以我们可以采用第二个方案，写个重载版本。

//assign重载版本  防止间接寻址
void assign(int n, const T& val)
{
  clear();
  for (size_t i = n; i > 0; --i)
    push_back(val);
}

4、赋值重载传统写法

直接复用assign

// 赋值重载的传统写法
  list<T>& operator=(const list<T>& lt)
  {
    assign(lt.begin(), lt.end());
    return *this;
  }

5、赋值重载的现代写法

list<T>& operator=(list<T> lt)
{
  swap(lt);//利用值传递拷贝的临时对象进行交换
  return *this;
}

3.4 修改相关函数（Modifiers）

1、empty、size

//size
size_t size() const
{
  size_t n = 0;
  for (auto e : *this)
    ++n;
  return n;
}
//empty
bool empty() const
{
  return node->next == node;
}

2、insert

我们先实现insert和erase，其他的就可以直接复用了

//insert
iterator insert(iterator pos, const T& val)
{
  node* cur = pos._node;//记录当前节点
  node* prev = cur->_prev;//记录前驱节点
  node* newnode = new node(val);//建立新节点
  //开始改变指向
  newnode->_next = cur;
  cur->_prev = newnode;
  prev->_next = newnode;
  newnode->_prev = prev;
  return iterator(newnode);
}

3、erase

//erase
iterator erase(iterator pos)
{
  assert(pos != end());//确保不是删除哨兵位置
  node* prev = pos._node->_prev;
  node* next = pos._node->_next;
  prev->_next = next;
  next->_prev = prev;
  delete pos._node;
  return iterator(next);//利用匿名对象返回
}

4、尾插尾删头插头删

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

5、resize

//resize  如果n小于当前容量的大小，则内容将减少到前n个元素 当n大于容器大小时，则在末尾插入任意容量的内容。
void resize(size_t n, const T& val = T())
{
  size_t sz = size();//记录当前的有效元素的个数
  while (n < sz)
  {
    pop_back();
    --sz;
  }
  while (n > sz)
  {
    push_back(val);
    ++sz;
  }
}

六、反向迭代器的实现

sgi版本下的反向迭代器，其实就是将构建一个反向迭代器的类将正向迭代器封装起来，这个时候正向迭代器的++就是反向迭代器的--

template<class iterator, class Ref, class Ptr>
struct list_reverse_iterator
{
  typedef list_reverse_iterator<iterator, Ref, Ptr> self;
  //用正向迭代器去构造反向迭代器
  list_reverse_iterator(iterator it)
    :_cur(it)
  {}
  //解引用
  Ref operator*() const
  {
    iterator temp = _cur;
    --temp;
    return *temp;
  }
  //实现->
  Ptr operator->() const
  {
    return &operator*();
  }
  //前置++
  self& operator++()
  {
    --_cur;
    return *this;
  }
  //后置++
  self operator++(int)
  {
    iterator temp(_cur);
    --*this;
    return temp;
  }
  //前置--
  self& operator--()
  {
    ++_cur;
    return *this;
  }
  //后置--
  self operator--(int)
  {
    iterator temp(_cur);
    ++*this;
    return temp;
  }
  //不等于
  bool operator!=(const self& s)
  {
    return _cur != s._cur;
  }
  //等于
  bool operator==(const self& s)
  {
    return _cur == s._cur;
  }
  iterator _cur;
};

思考：为什么解引用的是前一个位置的元素？？？

通过这个我们来看看vector下的反向迭代器代码：

复用性很高，和list的区别就是因为是随机迭代器，所以多了+和-的接口，第二个就是不需要->,所以其实模版也可少传一个

七、list模拟实现的全部代码

//c++喜欢ListNode驼峰法命名  为了和STL风格一致，我们也用小写
//但是STL版本和java喜欢小写带_  
namespace cyx
{
  //节点的封装
  template<class T>
  struct list_node
  {
    list_node<T>* _prev;
    list_node<T>* _next;
    T _data;
    //节点的构造函数
    list_node(const T& val = T())
      :_prev(nullptr)
      , _next(nullptr)
      , _data(val)
    {}
  };
  //封装迭代器
  template<class T, class Ref, class Ptr>//Ref用于
  struct list_iterator
  {
    typedef list_node<T> node;
    typedef list_iterator<T, Ref, Ptr>  self;
    node* _node;
    //迭代器的构造函数
    list_iterator(node* n)//迭代器的构造
      :_node(n)
    {}
    //实现*
    Ref operator*() const
    {
      return _node->_data;
    }
    //实现->
    Ptr operator->() const
    {
      return &operator*();    //本来是两个->,为了增强可读性，我们封装了这个函数 比如当我们存储的结构体解引用后有多个成员，那么我们可以通过箭头的直线去找到对应我们想要的成员  
    }
    //前置++
    self& operator++()
    {
      _node = _node->_next;
      return *this;
    }
    //后置++
    self operator++(int)
    {
      self temp(*this);
      ++*this;
      return temp;
    }
    //前置--
    self& operator--()
    {
      _node = _node->_prev;
      return *this;
    }
    //后置--
    self operator--(int)
    {
      self temp(*this);
      --*this;
      return temp;
    }
    //！=
    bool operator!=(const self& s) const
    {
      return _node != s._node;
    }
    //==
    bool operator==(const self& s) const
    {
      return _node == s._node;
    }
  };
  template<class iterator, class Ref, class Ptr>
  struct list_reverse_iterator
  {
    typedef list_reverse_iterator<iterator, Ref, Ptr> self;
    //用正向迭代器去构造反向迭代器
    list_reverse_iterator(iterator it)
      :_cur(it)
    {}
    //解引用
    Ref operator*() const
    {
      iterator temp = _cur;
      --temp;
      return *temp;
    }
    //实现->
    Ptr operator->() const
    {
      return &operator*();
    }
    //前置++
    self& operator++()
    {
      --_cur;
      return *this;
    }
    //后置++
    self operator++(int)
    {
      iterator temp(_cur);
      --*this;
      return temp;
    }
    //前置--
    self& operator--()
    {
      ++_cur;
      return *this;
    }
    //后置--
    self operator--(int)
    {
      iterator temp(_cur);
      ++*this;
      return temp;
    }
    //不等于
    bool operator!=(const self& s)
    {
      return _cur != s._cur;
    }
    //等于
    bool operator==(const self& s)
    {
      return _cur == s._cur;
    }
    iterator _cur;
  };
  template<class T>
  class list
  {
    typedef list_node<T>  node;//typedef可以帮助我们简洁代码
  public:
    //正向迭代器
    typedef list_iterator<T, T&, T*>   iterator;
    typedef list_iterator<T, const T&, const T*>   const_iterator;
        //typedef __list_const_iterator<T> const_iterator;不行
    //反向迭代器
    typedef list_reverse_iterator<iterator, T&, T*>    reverse_iterator;
    typedef list_reverse_iterator<iterator, const T&, const T*>  const_reverse_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);
    }
        //可读可写的反向迭代器
    reverse_iterator rbegin()
    {
      return reverse_iterator(end());
    }
    reverse_iterator rend()
    {
      return reverse_iterator(begin());
    }
    //可读不可写的反向迭代器
    const_reverse_iterator rbegin() const
    {
      return const_reverse_iterator(end());
    }
    const_reverse_iterator rend() const
    {
      return const_reverse_iterator(begin());
    }
    //默认构造函数
    list()
    {
      empty_init();
    }
    //有参构造函数
    list(size_t n, const T& val = T())
    {
        empty_init();
      for (size_t i = n; i > 0; --i)
        push_back(val);
    }
    //迭代器区间构造函数
    template <class InputIterator>
    list(InputIterator first, InputIterator last)
    {
         empty_init();
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    //拷贝构造函数传统写法
    /*list(const list<T>& lt)
    {
      empty_init();
      for (auto e : lt)
        push_back(e);
    }*/
    //交换函数
    void swap(list<T>& temp)
    {
      std::swap(_head, temp._head);
    }
    //拷贝构造函数的现代写法
    list(const list<T>& lt)
    {
      empty_init();
      list<T> temp(lt.begin(), lt.end());//复用迭代器区间构造，让别人构造好了，我再窃取革命成果
      swap(temp);
    }
    //assign(迭代器区间替换)
    template <class InputIterator>
    void assign(InputIterator first, InputIterator last)
    {
      clear();
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    //assign(直接替换)
    void assign(size_t n, const T& val)
    {
      clear();
      for (size_t i = n; i > 0; --i)
        push_back(val);
    }
    //assign重载版本  防止间接寻址
    void assign(int n, const T& val)
    {
      clear();
      for (size_t i = n; i > 0; --i)
        push_back(val);
    }
    // 赋值重载的传统写法
    list<T>& operator=(const list<T>& lt)
    {
      assign(lt.begin(), lt.end());
      return *this;
    }
    // 赋值重载的现代写法
    //list<T>& operator=(list<T> lt)
    //{
    //  swap(lt);//利用值传递拷贝的临时对象进行交换
    //  return *this;
    //}
    //析构函数
    ~list()
    {
      clear();
      delete _head;
      _head = nullptr;
    }
    //size
    size_t size() const
    {
      size_t n = 0;
      for (auto e : *this)
        ++n;
      return n;
    }
    //insert
    iterator insert(iterator pos, const T& val)
    {
      node* cur = pos._node;//记录当前节点
      node* prev = cur->_prev;//记录前驱节点
      node* newnode = new node(val);//建立新节点
      //开始改变指向
      newnode->_next = cur;
      cur->_prev = newnode;
      prev->_next = newnode;
      newnode->_prev = prev;
      return iterator(newnode);
    }
    //erase
    iterator erase(iterator pos)
    {
      assert(pos != end());//确保不是删除哨兵位置
      node* prev = pos._node->_prev;
      node* next = pos._node->_next;
      prev->_next = next;
      next->_prev = prev;
      delete pos._node;
      return iterator(next);//利用匿名对象返回
    }
    //pushback 尾插
    void push_back(const T& val)
    {
      insert(end(), val);
    }
    //pushfront 头插
    void push_front(const T& val)
    {
      insert(begin(), val);
    }
    //popback 尾删
    void pop_back()
    {
      erase(--end());
    }
    //popfront 头删
    void pop_front()
    {
      erase(begin());
    }
    //clear 只留一个头节点
    void clear()
    {
      iterator it = begin();
      while (it != end())
        it = erase(it);
    }
    //resize  如果n小于当前容量的大小，则内容将减少到前n个元素 当n大于容器大小时，则在末尾插入任意容量的内容。
    void resize(size_t n, const T& val = T())
    {
      size_t sz = size();//记录当前的有效元素的个数
      while (n < sz)
      {
        pop_back();
        --sz;
      }
      while (n > sz)
      {
        push_back(val);
        ++sz;
      }
    }
    //empty
    bool empty() const
    {
      return node->next == node;
    }
  private:
    node* _head;
    //用来初始化  类内部自己用，设私有
    void empty_init()
    {
      _head = new node;
      _head->_next = _head;
      _head->_prev = _head;
    }
  };

接口暂时就搞这些，如果后面有时间再写些比较复杂的接口，这一篇不太好理解，讲解不到位还请见谅

C++：List的使用和模拟实现

一、List的介绍

二、List的使用注意事项

2.1 List的迭代器失效问题

2.2 List中sort的效率测试

三、模拟实现的注意事项

四、正向迭代器的实现

2.1 正向迭代器的封装

2.2 迭代器的使用

五、list相关的成员函数

3.1 构造函数

1、默认构造函数

2、有参构造函数

3、迭代器区间构造函数

4、拷贝构造的传统写法

5、拷贝构造的现代写法+swap

3.2 clear和析构函数

3.3 赋值重载和assign

1、assign直接替换

2、assign迭代器区间替换

3、assign直接替换重载（防止间接寻址）

4、赋值重载传统写法

5、赋值重载的现代写法

3.4 修改相关函数（Modifiers）

1、empty、size

2、insert

3、erase

4、尾插尾删头插头删

5、resize

六、反向迭代器的实现

七、list模拟实现的全部代码

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

C++：List的使用和模拟实现

一、List的介绍

二、List的使用注意事项

2.1 List的迭代器失效问题

2.2 List中sort的效率测试

三、模拟实现的注意事项

四、正向迭代器的实现

2.1 正向迭代器的封装

2.2 迭代器的使用

五、list相关的成员函数

3.1 构造函数

1、默认构造函数

2、有参构造函数

3、迭代器区间构造函数

4、拷贝构造的传统写法

5、拷贝构造的现代写法+swap

3.2 clear和析构函数

3.3 赋值重载和assign

1、assign直接替换

2、assign迭代器区间替换

3、assign直接替换重载（防止间接寻址）

4、赋值重载传统写法

5、赋值重载的现代写法

3.4 修改相关函数（Modifiers）

1、empty、size

2、insert

3、erase

4、尾插尾删头插头删

5、resize

六、反向迭代器的实现

七、list模拟实现的全部代码

热门文章

最新文章

相关课程

相关电子书

相关实验场景