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

简介: C++:List的使用和模拟实现

                                                       创作不易,感谢三连!!

一、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;
    }
  };

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

相关文章
|
2天前
|
C++ 容器
|
4天前
|
调度 C++ 容器
【C++】手搓 list 容器
本文我们实现了STL库中重要的list 的模拟实现,其中最重要莫过于迭代器的封装类的书写,这是前所未有的操作(对于我来说,我是第一次使用这种结构)。通过list 的模拟实现也帮我们巩固了类与对象的知识,也强化了指针操作的思路。欢迎大家讨论分析。
13 1
|
4天前
|
存储 编译器 C++
【C++/STL】list(常见接口、模拟实现、反向迭代器、)
【C++/STL】list(常见接口、模拟实现、反向迭代器、)
5 0
|
4天前
|
存储 缓存 编译器
【C++进阶(五)】STL大法--list模拟实现以及list和vector的对比
【C++进阶(五)】STL大法--list模拟实现以及list和vector的对比
|
4天前
|
算法 C++ 容器
【C++进阶(四)】STL大法--list深度剖析&list迭代器问题探讨
【C++进阶(四)】STL大法--list深度剖析&list迭代器问题探讨
|
4天前
|
C++
c++的学习之路:16、list(3)
c++的学习之路:16、list(3)
13 0
|
4天前
|
C++
c++的学习之路:15、list(2)
c++的学习之路:15、list(2)
14 0
|
4天前
|
存储 C++ 容器
c++的学习之路:14、list(1)
c++的学习之路:14、list(1)
19 0
|
4天前
|
编译器 C++ 容器
【C++初阶】STL详解(八)List的模拟实现
【C++初阶】STL详解(八)List的模拟实现
39 0
|
4天前
|
存储 C++ 容器
【C++初阶】STL详解(五)List的介绍与使用
【C++初阶】STL详解(五)List的介绍与使用
33 0