【c++】list的特性及使用

目录

一、list的介绍

二、list的深度剖析与模拟实现

1、list图解

2、list增删查改模拟实现

三、list与vector的对比

一、list的介绍

? ? ? ? STL中的list指的是带头双向循环链表。list是可以在常数范围内任意位置进行插入和删除的序列式容器，并且可以前后双向迭代。list中每个元素的存储相互独立，通过每个节点中的指针指向其前一个元素和后一个元素。list因为每个节点的存储位置相互独立而是的插入和删除元素不需要移动其他元素让其效率更高，但是list也因此不能支持任意位置的随机访问，不能随机访问是它最大的缺陷。

二、list的深度剖析与模拟实现

1、list图解

? ? ? ? list的节点中有三个成员变量（哨兵位头节点除外），分别是：有效数据date、指向下一个节点的指针变量next、指向前一个节点的指针变量pre，哨兵位头节点不存储有效数据，只有两个指针变量。

2、list增删查改模拟实现

#pragma once
#include<iostream>
using namespace std;


namespace lbj
{
    // List的节点类
    template<class T>
    struct ListNode
    {
        ListNode(const T& val = T())
            :_val(val)
            ,_pPre(nullptr)
            ,_pNext(nullptr)
        {}
        ListNode<T>* _pPre;
        ListNode<T>* _pNext;
        T _val;
    };

    //List的迭代器类
    template<class T, class Ref, class Ptr> //Ref是T类型的引用；Ptr是指向T类型数据的指针
    class ListIterator
    {
        typedef ListNode<T> Node;
        typedef ListNode<T>* PNode;
        typedef ListIterator<T, Ref, Ptr> Self;
    public:
        
        ListIterator(PNode pNode = nullptr)
            :_pNode(pNode)
        {}
        ListIterator(const Self& l);
        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& l)
        {
            return(_pNode != l._pNode);
        }
        bool operator==(const Self& l)
        {
            return(_pNode == l._pNode);
        }
    private:
        PNode _pNode;
    };

    //list类
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
        typedef ListNode<T>* PNode;
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;
    public:

        // List Iterator
        iterator begin()
        {
            return _pHead->_pNext;
        }
        iterator end()
        {
            return _pHead;
        }
        const_iterator begin() const
        {
            return _pHead->_pNext;
        }
        const_iterator end() const
        {
            return _pHead;
        }


        // List Capacity
        size_t size()const;
        bool empty()const;


        // List Access
        T& front();
        const T& front()const;
        T& back();
        const T& back()const;


        // List Modify
        iterator insert(iterator pos, const T& val)// 在pos位置前插入值为val的节点,返回新插入元素的迭代器
        {
            PNode cur = pos._pNode;
            PNode pre = cur->_pPre;
            PNode NewNode = new Node(val);
            pre->_pNext = NewNode;
            NewNode->_pPre = pre;
            NewNode->_pNext = cur;
            cur->_pPre = NewNode;
            return iterator(NewNode);   //返回新插入元素的迭代器
        }
        iterator erase(iterator pos)// 删除pos位置的节点，返回该节点的下一个位置
        {
            PNode cur = pos;
            PNode pre = cur->_pPre;
            PNode next = cur->_pNext;
            pre->_pNext = next;
            next->_pPre = pre;
            delete cur;
            return iterator(next);  //返回该节点的下一个位置
        }
        void push_back(const T& val)    //{ insert(end(), val); }
        {
            //insert(end(), val);
            PNode tail = _pHead->_pPre;
            PNode NewNode = new Node(val);
            tail->_pNext = NewNode;
            NewNode->_pPre = tail;
            NewNode->_pNext = _pHead;
            _pHead->_pPre = NewNode;
        }
        void pop_back() 
        {
            erase(--end()); 
        }
        void push_front(const T& val) 
        { 
            insert(begin(), val); 
        }
        void pop_front() 
        { 
            erase(begin()); 
        }
        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }
        void swap(list<T>& l)
        {
            std::swap(_pHead, l._pHead);
        }

        // List的构造
        void empty_init()
        {
            _pHead = new Node;
            _pHead->_pPre = _pHead;
            _pHead->_pNext = _pHead;
        }
        list()
        {
            empty_init();
        }
        list(int n, const T& value = T());
        template <class Iterator>
        list(Iterator first, Iterator last);
        list(const list<T>& l)
        {
            empty_init();
            for (auto L_N : l)
            {
                push_back(L_N);
            }
        }
        list<T>& operator=(const list<T> l)
        {
            //if (this != &l)
            //{
            //    clear();
            //    for (auto L_N : l)
            //    {
            //        push_back(L_N);
            //    }
            //}

            swap(l);
            return *this;
        }
        ~list()
        {
            clear();
            delete _pHead;
            _pHead = nullptr;
        } 
    private:
        void CreateHead();
        PNode _pHead;
    };
};

三、list与vector的对比