list简单模拟实现

由于前面已经模拟实现了vector，所以这里关于一些函数实现就不会讲的过于细致。

成员变量

template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}
};template<class T>
class list
{typedef ListNode<T> Node;
public:list(){_head = new Node;_head->_next = _head->_prev = _head;_size = 0;}size_t size()const{return _size;}
private:Node* _head;size_t _size;
};

迭代器（重点）

我们想要迭代器能实现以下的功能：

void test_1()
{list<int>lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << ' ';++it;}cout << endl;
}

实际上迭代器模拟的是指针的功能，然而链表的指针++并不会得到下一个元素的指针。但我们却希望迭代器++能得到下一个元素的迭代器。

那么我们是不是需要对++进行一个修改，也就是运算符重载。

再仔细想想，重载后的运算符是对这一个类生效的，但我们只需要对迭代器生效。那是不是意味着我们的迭代器需要是一个独立的类：

ListIterator

template<class T>
struct ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;//内置类型指针ListIterator(Node* node):_node(node){}
}

注意不需要析构函数，实际上我们的迭代器就是原数组结点指针的一个类，怎么可以用过一次后就析构掉呢？

运算符重载

前置++：

Self& operator++()//前置++
{_node = _node->_next;return *this;
}

后置++：

Self operator++(int)//后置++
{Self tmp(*this);//浅拷贝_node = _node->_next;return tmp; 
}

值得注意的是，前后++的重载函数名都是operator++，那么如何区分他们呢？

C++语法规定：后置++的函数参数里面需要有一个int。

此外，我这的tmp是一个浅拷贝，这样做有没有问题呢？
我们需要的是指针，那么对于指针自然应该采用浅拷贝。
事实上，我们一般有一个规律：如果类需要重载析构函数，那么一般就要深拷贝，反之一般就需要浅拷贝。

剩余运算符：

Self& operator*()
{return _node->_data;
}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;
}

begin、end

注意到我们的begin是返回首元素迭代器，而end是返回最后一个元素的下一个位置的迭代器：

typedef ListIterator<T> iterator;
iterator begin() 
{return _head->_next;
}iterator end()
{return iterator(_head);
}

注意到，begin这里我返回的是_head->_next，因为单参数会隐式类型转换：自动调用单参数的构造函数，也就是等价于iterator(_head->_next).

插入、删除

insert

void insert(iterator pos, const T& val)
{Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;
}

erase

iterator erase(iterator pos)//返回iterator防止迭代器失效
{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 push_back(const T& x)
{insert(end(), x);
}void push_front(const T& x)
{insert(begin(), x);
}void pop_back()
{erase(end()--);//没有重载-1，所以要用--
}void pop_front()
{erase(begin());
}

尾删这里需要注意一定要是end()–，而不能是end()-1.理由很简单，因为我们没有重载-。

operator->

对于非内置类型如下：

struct A
{int _a1;int _a2;A(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}
};void test_2()
{list<A>lt;A aa1(1, 1);lt.push_back(aa1);lt.push_back(aa1);lt.push_back(A(2, 2));lt.push_back({ 3,3 });lt.push_back({ 4,4 });list<A>::iterator it = lt.begin();while (it != lt.end()){cout << *it << ' ';//不支持流插入++it;}}

不难发现cout << *it << ’ ';这里会报错，因为自定义类型没有重载<<。
因此我们需要改写为：

cout << (*it)._a1 << ' ' << (*it)._a2 << endl;

不难发现这有些许繁琐，正常来说对于类指针功能我们更希望用->这个操作符，也就是：

cout << it->_a1 << ' ' << it->_a2 << endl;

那就需要重载->：

Self* operator->()
{return &_node->_data;
}

这时候就有人发出疑问了，怎么返回值是一个指针，那要调用_a1，不应该是it->->_a1吗？
没错，这是原生写法，但是我们C++语法给他优化掉了，现在it->_a1等价于it.operator->()->_a1

const_iterator

const_iterator为什么不是const iterator?
这个问题其实前面学习类的时候已经解答过了，事实上我们的const_iterator是不能改变迭代器呢，还是不能改变迭代器指向的元素的值呢？
事实上const_iterator也是可以++的，否则怎么遍历数组元素。
那也就是说const_iterator只是不能改变指向的元素的值，而不是不能改变迭代器本身。

经过上述分析我们得知，我们只需要对*和->重载的返回值作出修改即可：

const T& operator*()
{return _node->_data;
}const T* operator->()
{return &_node->_data;
}

但是，只有返回值不同是无法重载函数的！！
那么我们是不是需要再多写一个const_iterator类呢？
可以，但有更好的方法。
注意到我们只有这两个函数不同，并且只有返回值不同，那是不是可以写一个模板将返回值不同分成不同的类呢？

template<class T,class Ref,class Ptr>
struct ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}}
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;const_iterator begin() const
{return _head->_next;
}const_iterator end() const
{return _head;
}

这样我们就省去了CV再写一个类的功夫。

拷贝构造

一样是复用push_back

void empty_init()
{_head = new Node;_head->_next = _head->_prev = _head;_size = 0;
}
list(const T& lt)// 复用push_back来深拷贝
{empty_init();for (auto& e : lt){push_back(e);}
}

operator=

一样是复用拷贝构造：

void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}list<T>& operator=(list<T> lt)//传值传参
{swap(lt);return *this;
}

析构函数

同样复用erase

void clear()//没清除头结点
{iterator it = begin();while (it != end()){it = erase(it);}}~list()
{clear();delete _head;_head = nullptr;}

完整代码

template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}
};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){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}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;}};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;iterator begin() //const{return iterator(_head->_next);}iterator end(){return iterator(_head);}//const_iterator而不是const iterator，因为是指向内容不能被修改，而非迭代器本身不能被修改。如果是const iterator就不能it++const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_next = _head->_prev = _head;_size = 0;}list(){empty_init();}list(const T& lt)// 复用push_back来深拷贝{empty_init();for (auto& e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt)//传值传参{swap(lt);return *this;}void clear()//没清除头结点{iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}//void push_back(const T& x)//{//	Node* newnode = new Node(x);//	Node* tail = _head->_prev;//	tail->_next = newnode;//	newnode->_prev = tail;//	newnode->_next = _head;//	_head->_prev = newnode;//}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(end()--);//没有重载-1，所以要用--}void pop_front(){erase(begin());}void insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;}iterator erase(iterator pos)//返回iterator防止迭代器失效{Node* cur = pos->_node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}size_t size()const{return _size;}bool empty()const{return _size == 0;}private:Node* _head;size_t _size;
};