C++ : list类及其模拟实现

一、list的介绍和使用

list的介绍

list的使用

1.list的构造

构造函数

2.list iterator 的使用

3.list capacity

4.list element access

5.list modifiers

6.list的迭代器失效

二、list的模拟实现

要点

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

1.list的构造

构造函数

（1）是指传来一个空指针，构造空的list

（2）指构造n个值为val的list

（3）用[first，last)中的元素构造list

（4）用x链表拷贝构造

2.list iterator 的使用

迭代器可以理解成一个指针，因为它封装了底层的逻辑，像指针一样使用。该指针指向list中的某个节点。begin就是指向第一个节点（非哨兵），end，返回最后一个元素下一个位置（就是哨兵位）。rbegin返回end位置，rend，返回begin位置。

注意：

begin和end是正向迭代器，对迭代器++，迭代器向后移动

rbegin和rend是反向迭代器，对迭代器++,迭代器向前移动

3.list capacity

empty 检查list是否是空链表

size 返回list中有效节点个数

4.list element access

front 返回list中，第一个节点的值的引用

back返回list中，最后一个节点的值的引用

5.list modifiers

模拟实现的话，掌握红框中常用的就好。

push_front 在list首节点前插入值为val的节点

pop_front 删除list首节点

push_back 在list最后一个元素后插入值为val的节点

pop_back 删除list尾结点

insert 在pos位置插入一个值为val的节点

erase 删除pos位置的节点

swap 交换两个list中的元素

clear 清除list中的有效节点

6.list的迭代器失效

迭代器失效是指迭代器指向的节点无效，也就是该节点被删除了，用户不会再有该节点的访问权限。因为list的底层是带头双向循环链表，所以在list中进行插入时是不会导致list迭代器失效的，只有在删除时才会失效，并且失效的只有被删除节点的迭代器，其他节点的迭代器不会受到影响。

在逐个（调用erase函数时，参数）用后置++，不用前置++。表示删除以后，it又被重新赋值了。

二、list的模拟实现

要点

1.list要实现节点和链表还有迭代器三个部分，分别建立三个类模板。这是为了提高类的复用性。封装在自己的命名空间里。

2.单个节点的结构体是公有的开放的，因为要在其他类里经常调用。所以得开放。包含val，前指针和后指针，以及构造函数。

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

3.写迭代器的类时，迭代器指针也要设置为开放的，为了后面在list类中erase pos位置和insert pos位置可以访问。迭代器的类模板是这样的。

Ref 和Ptr分别是迭代器返回的引用类型和迭代器返回的指针类型。

如果写T& 和T*，会限制迭代器返回的类型，这样想要返回const T& 和const T* 也无法更改。而Ref可以使你在实例化的时候就可以选择返回类型是什么。

//List的迭代器类
template<class T, class Ref, class Ptr>
class ListIterator
{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;//加了Ref和Ptr后，代码的灵活性提高
public:                                 //体现在返回的时候和实例化的时候，我可以控制迭代器解引 //用后返回什么类型ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}Ref operator*(){return _pNode->_val;}Ptr operator->(){return &_pNode->_val;}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self ptmp(*this);_pNode = _pNode->_pNext;return ptmp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self& operator--(int){Self ptmp(*this);_pNode = _pNode->_pPre;return ptmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode == l._pNode;}
public:PNode _pNode;
};

list类模拟实现部分接口全部代码展示

#pragma once
#include<iostream>
#include <assert.h>
using namespace std;namespace ting
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()):_pPre(nullptr), _pNext(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;//加了Ref和Ptr后，代码的灵活性提高public:                                 //体现在返回的时候和实例化的时候，我可以控制迭代器解引用后返回什么类型ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}Ref operator*(){return _pNode->_val;}Ptr operator->(){return &_pNode->_val;}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self ptmp(*this);_pNode = _pNode->_pNext;return ptmp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self& operator--(int){Self ptmp(*this);_pNode = _pNode->_pPre;return ptmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode == l._pNode;}public: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(){//处理私设的变量CreateHead();}list(int n, const T& value = T()){CreateHead();while (n--){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);++first;}}list(const list<T>& l){CreateHead();list<T> tmp(l.begin(), l.end());swap(tmp);}list<T>& operator=(const list<T> l){swap(l);return *this;}~list(){clear();delete _pHead;_pHead = nullptr;}///// List Iteratoriterator begin(){return iterator(_pHead->_pNext);//因为_pNext不是迭代器类型，要走迭代器的拷贝构造}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(_pHead->_pNext);}const_iterator end() const{return const_iterator(_pHead);}///// List Capacitysize_t size()const{size_t n = 0;for (auto it = begin(); it != end(); ++it){++n;}return n;}bool empty()const{return _pHead->_pNext == _pHead;}// List AccessT& 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;}// List Modifyvoid 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){PNode newnode = new Node(val);newnode->_pNext = pos._pNode;newnode->_pPre = pos._pNode->_pPre;newnode->_pPre->_pNext = newnode;pos._pNode->_pPre = newnode;return iterator(newnode);}iterator erase(iterator pos){assert(pos != end());PNode nextNode = pos._pNode->_pNext;pos._pNode->_pPre->_pNext = pos._pNode->_pNext;pos._pNode->_pNext->_pPre = pos._pNode->_pPre;delete pos._pNode;return iterator(nextNode);}void clear(){while (!empty()){pop_back();}}void swap(list<T>& l){std::swap(_pHead, l._pHead);}private:void CreateHead(){_pHead = new Node();_pHead->_pPre = _pHead;_pHead->_pNext = _pHead;}PNode _pHead;};
};