C++ List的模拟实现

时间:2024-07-08 09:48:04

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的使用:

下面是list的常见接口

#include<iostream>

using namespace std;
 
namespace mylist
{
    // List的节点类
    template<class T>

    struct ListNode
    {
        ListNode<T>* _next;
        ListNode<T>* _prev;
        T _val;

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

    };

     //List的迭代器类
    template<class T, class Ref, class Ptr>
    struct ListIterator
    {
        typedef ListNode<T> Node;
        typedef ListIterator<T, Ref, Ptr> Self;
        
        Node* _node;
        
        ListIterator(Node* node)
            :_node(node)
        {}
 
        ListIterator(const Self& it)
            :_node(it._node)
        {}
        
        Ref operator*();
        Ptr operator->();
        Self& operator++();
        Self operator++(int);
        Self& operator--();
        Self operator--(int);
        
        bool operator!=(const Self& it);
        bool operator==(const Self& it);  
    };

    //list类
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
    public:
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T&> const_iterator;
    public:
         //创造头节点
        void empty_init()//CreateHead;

        // List的构造
        list();

        //int 不能用size_t,否则会撞
        //类型不一致,会调用上面的模板迭代区间
         //list(int n, const T& value = T())
        //{
        //    empty_init();
        //    while (n)
        //    {
        //        push_back(value);
        //        n--;
        //    }
        //}
        
        //迭代器区间构造
        template <class Iterator>
        list(Iterator first, Iterator last);

         //拷贝构造
        list(const list<T>& lt);

        list<T>& operator=(const list<T> lt);

        ~list();
        
        // List Iterator
        iterator begin();
        iterator end();
        // const迭代器,需要是迭代器不能修改,还是迭代器指向的内容?
        // 迭代器指向的内容不能修改!const iterator不是我们需要const迭代器

        const_iterator begin() const;
        const_iterator end() const;
        
         // List Capacity
        size_t size()const;
        bool empty()const;

        // 在pos位置前插入值为val的节点
        void insert(iterator pos, const T& val);
        
        void push_back(const T& val);    
        void pop_back();
        void push_front(const T& val);
        void pop_front();

        任意位置插入多个数据
        //void insert(iterator pos, int n, const T& val)
        //{
        //    iterator it = pos;
        //    while (n)
        //    {
        //        it = insert(it, val);
        //        n--;
        //    }
        //}

        iterator erase(iterator pos);
        
        删除迭代器区间的数据
        //iterator erase(iterator first, iterator last)
        //{
        //    iterator it = first;
        //    while (if != last)
        //    {
        //        it = erase(it)
        //    }
        //    return last++;
        //}

        void clear();
        void swap(list<T>& lt);
private:
        Node* _head;
        size_t _size;
    };

}

List的节点类

    // List的节点类
    template<class T>

    struct ListNode
    {
        ListNode<T>* _next;
        ListNode<T>* _prev;
        T _val;

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

    };

List的迭代器类

        Ref operator*()
        {
            return _node->_val;
        }

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

        Self& operator++()
        {
            _node = _node->_next;
            return *this;
        }
        Self operator++(int)
        {
            Self tmp(*this);
            _node = _node->_next;
            return tmp;
        }

        Self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        Self operator--(int)
        {
            Self tmp(*this);
            _node = _node->_prev;
            return tmp;

        }

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

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

List类

        //创造头节点
        void empty_init()//CreateHead
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;

            _size = 0;
        }

        // List的构造
        list()
        {
            empty_init();
        }

        //迭代器区间构造
        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=(const list<T> lt)
        {
            swap(lt);
            return *this;
        }

        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }

        // List Iterator
        iterator begin()
        {
            return iterator(_head->_next);
        }

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

        // const迭代器,需要是迭代器不能修改,还是迭代器指向的内容?
        // 迭代器指向的内容不能修改!const iterator不是我们需要const迭代器

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

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

        // List Capacity
        size_t size()const
        {
            return _size;
        }

        bool empty()const
        {
            return _size == 0;
        }

        // 在pos位置前插入值为val的节点
        void insert(iterator pos, const T& val)
        {
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode = new Node(val);

            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = cur;
            cur->_prev = newnode;
            _size++;
        }

        // List Modify
        void push_back(const T& val)
        {
            insert(end(), val);
        }

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

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

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

        // 删除pos位置的节点,返回该节点的下一个位置
        iterator erase(iterator pos)
        {
             Node* cur = pos._node;
            Node* prev = cur->_prev;
                        Node* next = cur->_next;
            
            prev->_next = next;
            next->_prev = prev;
            delete cur;
            _size--;

            return iterator(next);
        }

        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }

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