[数据结构与算法] STL容器—

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> STL容器——list -> 正文阅读

[数据结构与算法]STL容器——list

文章目录

前言：list是带头节点的双向循环链表，本文意在了解list的基本使用，并且模拟实现list。

1.list的基本框架

list是由一个一个的节点，形成的双向带头链表，所以必须实现节点这一结构。

    template<class T>
    struct ListNode
    {
        //节点的构造函数
        ListNode(const T& val = T())
            :_pNext(nullptr),
            _pPre(nullptr),
            _val(val)
        {
        }
       //指向前面节点的指针
        ListNode<T>* _pPre;
       //指向后面节点的指针
        ListNode<T>* _pNext;
       //节点的数据
        T _val;
    };

在这里插入图片描述
有了节点，再对节点进行链接，就形成了链表。链表中只需要有头节点就可以通过头节点找到其他的节点。

class list
 {
   typedef ListNode<T> Node;
   typedef Node* PNode;
 private:
   PNode _pHead;
 }

实现构造函数，只创造头节点，至于后面的节点插入就好了

        list()
        {
            _pHead = new Node;
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
        }

实现push_back()，插入数据

        void push_back(const T& val)
        {
             //创建新的节点
            PNode newnode = new Node(val);
            //保存尾节点
            PNode tail = _pHead->_pPre;
            //进行链接
            _pHead->_pPre = newnode;
            tail->_pNext = newnode;
            newnode->_pNext = _pHead;
            newnode->_pPre = tail;
        }

这就是最简易的list实现。

namespace ly
{   
    //list的节点
    template<class T>
    struct ListNode
    {   
        //节点的构造函数
        ListNode(const T& val = T())
            :_pNext(nullptr),
            _pPre(nullptr),
            _val(val)
        {
        }
       //指向前面节点的指针
        ListNode<T>* _pPre;
       //指向后面节点的指针
        ListNode<T>* _pNext;
       //节点的数据
        T _val;
    };
  template<class T>
  class list
 {
   typedef ListNode<T> Node;
   typedef Node* PNode;
 public:
     //构造函数
        list()
        {
            _pHead = new Node;
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
        }
     //插入节点
       void push_back(const T& val)
        {
             //创建新的节点
            PNode newnode = new Node(val);
            //保存尾节点
            PNode tail = _pHead->_pPre;
            //进行链接
            _pHead->_pPre = newnode;
            tail->_pNext = newnode;
            newnode->_pNext = _pHead;
            newnode->_pPre = tail;
        }
 private:
   PNode _pHead;
 }
 
 }

2.list的具体模拟实现

上述的list功能和STL中的list相差甚远，所以我们需要进一步的完善我们的list。

2.1 list的迭代器实现

vector和string的迭代器是封装的指针，因为它俩是顺序储存，物理地址挨着，所以迭代器的实现和操作都非常的简单。但是list的迭代器呢？它由于物理空间不连续，用指针，将链表串联起来，不支持随机访问。该如何实现它的迭代器呢？这个迭代器如何进行++，解引用等操作呢？
答案是：我们可以创建一个迭代器类，在类中实现迭代器的功能，我们可以重载运算符，对吧？

2.1.1 简易迭代器实现

实现一个简易的迭代器，完成++到下一个节点的功能，以及解引用。

template<class T>
class ListIterator
{
  typedef ListNode<T>* PNode;
  typedef ListIterator<T> Self;
  public:
  //迭代器
  PNode _pNode;
  //迭代器构造
        ListIterator(PNode pNode = nullptr)
            :_pNode(pNode)
        {
        }
  //迭代器++，--
       //前置++
       Self& operator++()
        {

            _pNode = _pNode->_pNext;
            return *this;
        }
       //后置++
        Self operator++(int)
        {
            Self tmp(*this);
            _pNode = _pNode->_pNext;
            return tmp;
        }

        Self& operator--()
        {
            _pNode = _pNode->_pPre;
            return *this;
        }
        
        Self operator--(int)
        {
            Self tmp(*this);
            _pNode = _pNode->_pPre;
            return tmp;
        }
  //迭代器解引用
        Ref operator*()
        {
            return _pNode->_val;
        }   
};

2.1.2 如何支持const版本的迭代器

但是上述的迭代器，如果想要支持const版本的，该如何实现呢？
可能有人说，这不难，我直接再写一个迭代器就好了，里面全换成支持const调用的版本就好了，这个方法可以，但是不要忘了模板参数这个东东。

template<class T，class Ref>
class ListIterator
{
  typedef ListNode<T>* PNode;
  typedef ListIterator<T,Ref> Self;
  public:
  //迭代器
  PNode _pNode;
  //迭代器构造
        ListIterator(PNode pNode = nullptr)
            :_pNode(pNode)
        {
        }
  //迭代器++，--
       //前置++
       Self& operator++()
        {

            _pNode = _pNode->_pNext;
            return *this;
        }
       //后置++
        Self operator++(int)
        {
            Self tmp(*this);
            _pNode = _pNode->_pNext;
            return tmp;
        }

        Self& operator--()
        {
            _pNode = _pNode->_pPre;
            return *this;
        }
        
        Self operator--(int)
        {
            Self tmp(*this);
            _pNode = _pNode->_pPre;
            return tmp;
        }
  //迭代器解引用
        Ref operator*()
        {
            return _pNode->_val;
        }   
};

昂这样就可以了？就改个模板参数？答案是：就是这样，改模板参数，具体使用时，直接对应推导即可。
比如：

        typedef ListIterator<T, T&> iterator;
        typedef ListIterator<T, const T&> const_iterator;

这样就已经，完成了两个版本。

2.1.3 完整的迭代器

迭代器也是支持 ->，同样也得支持const版本，所以再添加一个模板参数。总共就是三个参数，查看STL源码时，当然也是三个模板参数。

        typedef ListIterator<T, T&,T*> iterator;
        typedef ListIterator<T, const T&,const T*> const_iterator;

    template<class T, class Ref, class Ptr>
    class ListIterator
    {
        typedef ListNode<T>* PNode;

        typedef ListIterator<T, Ref, Ptr> Self;

    public:

        ListIterator(PNode pNode = nullptr)
            :_pNode(pNode)
        {
        }
        Ref operator*()
        {
            return _pNode->_val;
        }

        Ptr operator->()
        {
            return &_pNode->_val;
        }

        Self& operator++()
        {

            _pNode = _pNode->_pNext;
            return *this;
        }

        Self operator++(int)
        {
            Self tmp(*this);
            _pNode = _pNode->_pNext;
            return tmp;
        }

        Self& operator--()
        {
            _pNode = _pNode->_pPre;
            return *this;
        }

        Self operator--(int)
        {
            Self tmp(*this);
            _pNode = _pNode->_pPre;
            return tmp;
        }

        bool operator!=(const Self& it)
        {
            return _pNode != it._pNode;
        }

        bool operator==(const Self& it)
        {
            return _pNode == it._pNode;
        }
        PNode _pNode;
    };

关于以上对->重载，大家可能有疑惑？为什么返回的是一个T*，或者是一个const T*。
也就是说我们调用 iterator it->，返回的是一个指针，所以还得加一个->才能达到我们想要的结果，但是由于这样的可读性比较差，所以编译器做了优化，并不需要额外添加->。

2.2 list的构造函数

每个list都有一个哨兵位头节点，所以我们写一个创造头节点的函数

        void CreateHead()
        {
            _pHead = new Node();
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
        }

2.2.1 list构造函数

        //无参的构造，只创造头节点
        //这里直接复用CreatHead()也可以
        list()
        {
            _pHead = new Node;
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
        }
        //构造list含有n个节点且节点的val为value
        list(int n, const T& value = T())
        {   
            //创造头节点
            CreateHead();
            for (int i = 0; i < n; i++)
            {
                push_back(value);
            }
        }
        //根据迭代器的区间，初始化list
        template <class Iterator>
        list(Iterator first, Iterator last)
        {   
            CreateHead();
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

2.2.2 list的拷贝构造以及`=`的重载

       list(const list<T>& it)
        {
            CreateHead();
            list<T> tmp(it.begin(), it.end());
            std::swap(_pHead, tmp._pHead);
        }
        
        list<T>& operator=(list<T> it)
        {

            std::swap(_pHead, it._pHead);
            return *this;
        }

拷贝构造的话，直接创建一个临时的list tmp去拷贝 it 的所有节点值，再和this交换头节点就可以了。
赋值重载，用的传值传参，所以直接交换 it 的头节点即可。

2.2.3 迭代器功能实现

        typedef ListIterator<T, T&,T*> iterator;
        typedef ListIterator<T, const T&,const T*> const_iterator;
        iterator begin()
        {
            return iterator(_pHead->_pNext);
        }

        iterator end()
        {
            return iterator(_pHead);
        }

        const_iterator begin() const
        {
            return const_iterator(_pHead->_pNext);
        }

        const_iterator end() const
        {
            return const_iterator(_pHead);
        }

2.2.4 插入和删除操作



        // 在pos位置前插入值为val的节点

        iterator insert(iterator pos, const T& val)
        {
            PNode newnode = new Node(val);
            PNode cur = pos._pNode;
            PNode pre = cur->_pPre;

            cur->_pPre = newnode;
            newnode->_pNext = cur;
            pre->_pNext = newnode;
            newnode->_pPre = pre;

            return iterator(newnode);
        }

         删除pos位置的节点，返回该节点的下一个位置

        iterator erase(iterator pos)
        {
            PNode next = pos._pNode->_pNext;
            PNode pre = pos._pNode->_pPre;
            pre->_pNext = next;
            next->_pPre = pre;
            delete pos._pNode;
            return iterator(next);
        }
         全部复用上面的即可
        //尾插
         void push_back(const T& val)
        {
           /*PNode newnode = new Node(val);
            PNode tail = _pHead->_pPre;
            _pHead->_pPre = newnode;
            tail->_pNext = newnode;
            newnode->_pNext = _pHead;
            newnode->_pPre = tail;*/
           insert(end(), val);
        }
        //尾删
        void pop_back()
        {
            erase(end());
        }
        //头插
        void push_front(const T& val)
        {
            insert(begin(), val);
        }
        //头删
        void pop_front()
        {
            erase(begin());
        }

上面的所有功能都可以复用insert和erase，从这里直观的看出list的插入删除非常高效，只需要改变一下节点的指向关系，就能完成插入，删除，灰常强势。

2.2.5 析构函数

清理资源的话，我们希望实现两种：一种可以清除除了头节点的所有其它节点，另一种则是完成的释放list的所有节点。

       //不清除头节点
        void clear()
        { 
            iterator it = begin();
            while (it != end())
            {
                erase(it++);
            }
        }
        //析构函数
         void clear()
        { 
            iterator it = begin();
            while (it != end())
            {
                erase(it++);
            }
        }

2.2.6 其他功能

       size_t size() const
        {
            size_t i = 0;
            const_iterator it = begin();
            while (it != end())
            {
                i++;
                it++;
            }
            return i;
        }

        bool empty()const
        {
            return _pHead->_pNext == _pHead->_pPre;
        }
         T& front()
        {
            return * begin();
        }

        const T& front()const
        {
            return *begin();
        }

        T& back()
        {
            return *(--end());
        }

        const T& back()const
        {
            return *(--end());
        }
        
        void Print()
        {
            for (auto it : *this)
            {
                std::cout << it << ' ';
            }
            std::cout << std::endl;
        }

3. list模拟实现代码

#include<iostream>
namespace ly
{
    // List的节点类
    template<class T>
    struct ListNode
    {

        ListNode(const T& val = T())
            :_pNext(nullptr),
            _pPre(nullptr),
            _val(val)
        {
        }

        ListNode<T>* _pPre;

        ListNode<T>* _pNext;

        T _val;
    };
    //List的迭代器类
    template<class T, class Ref, class Ptr>
    class ListIterator
    {
        typedef ListNode<T>* PNode;

        typedef ListIterator<T, Ref, Ptr> Self;

    public:

        ListIterator(PNode pNode = nullptr)
            :_pNode(pNode)
        {
        }
        Ref operator*()
        {
            return _pNode->_val;
        }

        Ptr operator->()
        {
            return &_pNode->_val;
        }

        Self& operator++()
        {

            _pNode = _pNode->_pNext;
            return *this;
        }

        Self operator++(int)
        {
            Self tmp(*this);
            _pNode = _pNode->_pNext;
            return tmp;
        }

        Self& operator--()
        {
            _pNode = _pNode->_pPre;
            return *this;
        }

        Self operator--(int)
        {
            Self tmp(*this);
            _pNode = _pNode->_pPre;
            return tmp; 
        }

        bool operator!=(const Self& it)
        {
            return _pNode != it._pNode;
        }

        bool operator==(const Self& it)
        {
            return _pNode == it._pNode;
        }
        PNode _pNode;
    };



    //list类

    template<class T>
    class list
    {
        typedef ListNode<T> Node;
        typedef Node* PNode;
    public:
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T&> const_iterator;
    public:
        ///
        // List的构造
        list()
        {
            _pHead = new Node;
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
        }
        list(int n, const T& value = T())
        {
            CreateHead();
            for (int i = 0; i < n; i++)
            {
                push_back(value);
            }
        }
        template <class Iterator>
        list(Iterator first, Iterator last)
        {   
            CreateHead();
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }
        list(const list<T>& it)
        {
            CreateHead();
            list<T> tmp(it.begin(), it.end());
            std::swap(_pHead, tmp._pHead);
        }
        list<T>& operator=(list<T> it)
        {

            std::swap(_pHead, it._pHead);
            return *this;
        }
        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                erase(it++);
            }
        }
        ///
        // List Iterator

        iterator begin()
        {
            return iterator(_pHead->_pNext);
        }

        iterator end()
        {
            return iterator(_pHead);
        }

        const_iterator begin() const
        {
            return const_iterator(_pHead->_pNext);
        }

        const_iterator end() const
        {
            return const_iterator(_pHead);
        }
        /

         List Capacity
        size_t size() const
        {
            size_t i = 0;
            const_iterator it = begin();
            while (it != end())
            {
                i++;
                it++;
            }
            return i;
        }

        bool empty()const
        {
            return _pHead->_pNext == _pHead->_pPre;
        }

        //

         List Access
        T& front()
        {
            return * begin();
        }

        const T& front()const
        {
            return *begin();
        }

        T& back()
        {
            return *(--end());
        }

        const T& back()const
        {
            return *(--end());
        }


        

        // List Modify

        void push_back(const T& val)
        {
           /*PNode newnode = new Node(val);
            PNode tail = _pHead->_pPre;
            _pHead->_pPre = newnode;
            tail->_pNext = newnode;
            newnode->_pNext = _pHead;
            newnode->_pPre = tail;*/
           insert(end(), val);
        }

        void pop_back()
        {
            erase(end());
        }

        void push_front(const T& val)
        {
            insert(begin(), val);
        }

        void pop_front()
        {
            erase(begin());
        }

        // 在pos位置前插入值为val的节点

        iterator insert(iterator pos, const T& val)
        {
            PNode newnode = new Node(val);
            PNode cur = pos._pNode;
            PNode pre = cur->_pPre;

            cur->_pPre = newnode;
            newnode->_pNext = cur;
            pre->_pNext = newnode;
            newnode->_pPre = pre;

            return iterator(newnode);
        }

         删除pos位置的节点，返回该节点的下一个位置

        iterator erase(iterator pos)
        {
            PNode next = pos._pNode->_pNext;
            PNode pre = pos._pNode->_pPre;
            pre->_pNext = next;
            next->_pPre = pre;
            delete pos._pNode;
            return iterator(next);
        }
         
        void clear()
        { 
            iterator it = begin();
            while (it != end())
            {
                erase(it++);
            }
        }

        void swap(list<T>& it)
        {
            PNode tmp = it._pHead;
            it._pHead = _pHead;
            _pHead = tmp;

        }
        void Print()
        {
            for (auto it : *this)
            {
                std::cout << it << ' ';
            }
            std::cout << std::endl;
        }

    private:

        void CreateHead()
        {
            _pHead = new Node();
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
        }

        PNode _pHead;

    };

};