1. 模擬實現 list 一些常用接口

// list.h
#pragma once
#include <assert.h>
#include "Iterator.h"namespace room
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _data;list_node(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}};// 兩個迭代器 -- 合成一個模板template<class T, class Ref, class Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(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>//struct list_iterator//{//	typedef list_node<T> Node;//	Node* _node;//	list_iterator(Node* node)//		:_node(node)//	{}//	// 解引用運算符重載//	T& operator*()//	{//		return _node->_data;//	}//	T* operator->()//	{//		return &_node->_data;//	}//	//	// ++運算符重載//	list_iterator<T>& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	// !=運算符重載//	bool operator!=(const list_iterator<T>& it)//	{//		return _node != it._node;//	}//	bool operator==(const list_iterator<T>& it)//	{//		return _node == it._node;//	}//};//// 迭代器//template<class T>//struct list_const_iterator//{//	typedef list_node<T> Node;//	Node* _node;//	list_const_iterator(Node* node)//		:_node(node)//	{}//	// 解引用運算符重載//	const T& operator*()//	{//		return _node->_data;//	}//	const T* operator->()//	{//		return &_node->_data;//	}//	// ++運算符重載//	list_const_iterator<T>& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	// !=運算符重載//	bool operator!=(const list_const_iterator<T>& it)//	{//		return _node != it._node;//	}//	bool operator==(const list_const_iterator<T>& it)//	{//		return _node == it._node;//	}//};template<class T>class list{typedef list_node<T> Node;public:/*typedef Node* iterator;typedef list_iterator<T> iterator;typedef list_const_iterator<T> const_iterator;*/typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;// 第一種寫法//reverse_iterator rbegin()//{//	return reverse_iterator(--end());//}//reverse_iterator rend()//{//	return reverse_iterator(end());//}// 對稱reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}iterator begin(){//return iterator(_head->_next);iterator it(_head->_next);return it;}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){/*_head = new Node;_head->_prev = _head;_head->_next = _head;*/empty_init();}list(initializer_list<T> lt){empty_init();for (auto& e : lt){push_back(e);}}// lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}// lt1 = lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}size_t size() const{return _size;}void push_back(const T& x){/*Node* newnode = new Node(x);Node* tail = _head->_prev;newnode->_prev = tail;tail->_next = newnode;newnode->_next = _head;_head->_prev = newnode;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* nextNode = cur->_next;Node* prevNode = cur->_prev;prevNode->_next = nextNode;nextNode->_prev = prevNode;delete cur;--_size;return iterator(nextNode);}private:Node* _head;size_t _size;};
}

2. list 的反向迭代器

? ? ? ? 反向迭代器的 ++ 就是正向迭代器的 --，反向迭代器的 -- 就是正向迭代器的 ++。因此，反向迭代器的實現可以借助正向迭代器，即：反向迭代器內部可以包含一個正向迭代器，對正向迭代器的接口進行包裝即可。

// Iterator.h
// 所有容器的反向迭代器
// 迭代器適配器
#pragma oncetemplate<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
public:typedef ReverseIterator<Iterator, Ref, Ptr> Self;ReverseIterator(Iterator it): _it(it){}Ref operator*(){//return *_it;	// 第一種寫法Iterator tmp = _it;--tmp;return *tmp;}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s){return _it != s._it;}bool operator==(const Self& s){return _it == s._it;}private:Iterator _it;
};

3. list 與 vector 的對比

????????vector 與 list 都是STL中非常重要的序列式容器，由于兩個容器的底層結構不同，導致其特性以及應用場景不同，其主要不同如下：