c++:list模拟实现

一、模拟实现list

要模拟实现list，必须要熟悉list的底层结构以及其接口的含义,大家可以看我关于list接口的博客c++:list-CSDN博客

1.1 list成员变量

list是一个双向带头链表，我们在定义成员变量时应该先定义出list单个的节点的类型。

1.1.1 list节点

    // List的节点类template<class T>struct ListNode{//默认构造    T()是一个匿名对象ListNode(const T& val = T()):_pPre(nullptr),_pNext(nullptr),_val(val){}ListNode<T>* _pPre;//指向上一个节点ListNode<T>* _pNext;//指向下一个节点T _val;             //节点的数据};

在c++中class 和struct 的主要区别就是struct 中的成员变量和成员函数的默认访问权限是public，而class中的成员变量和成员函数的默认访问权限是private,这里直接用struct更方便。

1.1.2 list的成员变量

class List{typedef ListNode<T> Node;typedef Node* PNode;private:PNode _pHead;size_t _size = 0;
}

这里我们把节点类型重命名为Node，又把节点的指针重命名为PNode。List的成员变量只有一个头节点的指针和节点的数量。（List底层是一个带头双向链表）

1.2 list的默认成员函数

1.2.1 默认构造

 public:///// List的构造//void CreateHead();//PNode _pHead;void CreateHead(){_pHead = new Node;_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;_size = 0;}list(){CreateHead();}

1.2.2 构造函数

1.2.2.1 list中包含n个值为val的元素

        list(int n, const T& value = T()){CreateHead();int i = n;while (i--){push_back(value);}}

1.2.2.2 用迭代器区间初始化list

        template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first!=last){push_back(*first);++first;}}

1.2.3 拷贝构造

list(const list<T>& lt){CreateHead();// 用l中的元素构造临时的temp,然后与当前对象交换list<T> temp(lt.begin(), lt.end());this->swap(temp);}void swap(list<T>& l){std::swap(l._pHead, _pHead);std::swap(l._size, _size);}

1.2.4 赋值运算符重载

        list<T>& operator=(list<T> lt){swap(lt);return *this;}void swap(list<T>& l){std::swap(l._pHead, _pHead);std::swap(l._size, _size);}

1.2.5 析构函数

        ~list(){clear();delete _pHead;_pHead = nullptr;}void clear(){iterator it = begin();while (it != end()){//不用++防止迭代器失效it=erase(it);}_size = 0;_pHead = nullptr;}

1.3 list capacity

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

1.4 list 迭代器

正反向迭代器和const版本，反向迭代器是依靠正向迭代器实现，迭代器是通过对节点的指针进行封装，通过代码实现你想要的结果。

1.4.1 正向迭代器

    template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;//typedef ListIterator<T, T&, T*> iterator;//typedef ListIterator<T, const T&, const T&> const_iterator;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& l){return l._pNode != _pNode;}bool operator==(const Self& l){return l._pNode == _pNode;}PNode _pNode;};

1.4.2 begin,cbegin,end,cend,rbegin,rend,crbegin,crend

        // List Iteratorpublic:typedef ListNode<T> Node;typedef Node* PNode;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;   typedef ListReverseIterator<iterator,T, T&, T*> reverse_iterator;typedef ListReverseIterator<iterator,T, const T&, const T*> const_reverse_iterator;iterator begin(){return _pHead->_pNext;}iterator end(){return _pHead;}const_iterator begin()const{return _pHead->_pNext;}const_iterator end()const{return _pHead;}// ListreverseIteratorreverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin()const{return reverse_iterator(end());}const_reverse_iterator rend()const{return reverse_iterator(begin());}

1.4.3 反向迭代器

template<class iterator, class T, class Ref, class Ptr>
struct ListReverseIterator
{
public:typedef ListReverseIterator<iterator,T, Ref, Ptr> Self;ListReverseIterator(iterator it):_it(it){}Ref operator*(){//解引用不影响迭代器iterator tmp = _it;return *--tmp;}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self operator++(int){Self tmp = _it--;return tmp;}Self& operator--(){++_it;return *this;}Self& operator--(int){Self tmp = --_it;return tmp;}bool operator!=(const Self& l){return _it!= l._it;}bool operator==(const Self& l){return _it == l._it;}private:iterator _it;
};

1.5 list Modify

这里的erase和insert要返回一个迭代器来防止迭代器失效的问题。

        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位置前插入值为val的节点iterator insert(iterator pos, const T& val){Node* newNode = new Node(val);Node* tmp = pos._pNode;Node* prev = tmp->_pPre;newNode->_pNext = tmp;tmp->_pPre = newNode;newNode->_pPre = prev;prev->_pNext = newNode;_size++;return pos;}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){Node* tmp = pos._pNode;Node* tail = tmp->_pNext;Node* prev = tmp->_pPre;delete tmp;tail->_pPre = prev;prev->_pNext = tail;_size--;return iterator(tail);}

1.6 list Access

        T& front(){return _pHead->_pNext->_val;}const T& front()const{return _pHead->_pNext->_val;}T& back(){return _pHead->_pPre->_val;}const T& back()const{return _pHead->_pPre->_val;}