双向链表实现的list

文章目录

• 手写list
• AC代码（没那么漂亮的版本）
• 修改后list
• • 分析函数及其作用
  • 写的时候出现的重大问题
  • • 1、代码逻辑问题
    • 2、代码理解问题
    • 3、请写好返回值
    • 4、充分理解`new和malloc和T()`、`delete和free和~T()`

手写list

要求如下：

给的algorithm如下：

#ifndef SJTU_ALGORITHM_HPP
#define SJTU_ALGORITHM_HPP

#include 

namespace sjtu{

template<typename T>
void sort(T *begin, T *end, std::function<bool(const T&, const T&)> cmp){
    int len = end - begin;
    if (len <= 1) return ;
    T *i = begin, *j = end - 1;
    T pivot = *(begin + (len + 1) / 2 - 1);
    while (j - i >= 0){
        while (cmp(*i, pivot)) i++;
        while (cmp(pivot, *j)) j--;
        if (j - i >= 0){
            std::swap(*i, *j);
            i++, j--;
        }
    }
    if (j - begin > 0) sort(begin, i, cmp);
    if (end - i > 1) sort(i, end, cmp);
}

template<class T>
T *upper_bound(const T *begin, const T *end, const T &num){//第一个大于num的值 ，不存在就返回end 
    int l = -1, r = end - begin;
    while (l + 1 < r){
        int mid = (l + r) >> 1;
        if (num < *(begin + mid)) r = mid; else l = mid;
    }
    return const_cast<T *>(begin + r);
}

template<class T>
T *lower_bound(const T *begin, const T *end, const T &num){//第一个大于等于num的值，不存在返回end 
    int l = -1, r = end - begin;
    while (l + 1 < r){
        int mid = (l + r) >> 1;
        if (num <= *(begin + mid)) r = mid; else l = mid;
    }
    return const_cast<T *>(begin + r);
}

};

#endif //SJTU_ALGORITHM_HPP

AC代码（没那么漂亮的版本）

#ifndef SJTU_LIST_HPP
#define SJTU_LIST_HPP

#include "exceptions.hpp"
#include "algorithm.hpp"

#include 
#include 
namespace sjtu {
/**
 * a data container like std::list
 * allocate random memory addresses for data and they are doubly-linked in a list.
 */
template<typename T>
class list {
	protected:
	    class node {
		    public: // add data members and constructors & destructor
		    	node *prev,*next;
		    	T *data;
		    	node(){
		    		data = NULL;
					prev = NULL;
					next = NULL;
				}
		    	node(const T &x,node *p = NULL,node *n = NULL){ 
		    		data = new T(x);
		    		prev = p;
		    		next = n;
		    		if(prev) prev->next = this;
		    		if(next) next->prev = this;
				}
				~node(){
					prev = next = NULL;
					if(data)  {
						delete data;//是这样写吗…难道是说 如果用data.~T()仅仅析构了T，没有释放data的空间！！！ 
				    }
					data = NULL;
				}
	    };
	
	protected:// add data members for linked list as protected members
		node *head,*tail;
		int len;
	    node *insert(node *pos, node *cur) {//在pos之前，插入一个node cur
			 cur->prev = pos->prev;
			 cur->next = pos;
			 pos->prev->next = cur;//有head和tail结点就不会担心有NULL的情况存在了吧 
			 pos->prev = cur;//48 49行不能交换，否则pos->prev改变了 
			 len++;
			 return cur;//你不return的话……怎么得到地址呢…… 为什么你不return 每次都忘记return 
		}
	     // remove node pos from list (no need to delete the node) ，return the removed node pos
		 //不删除 啊！！ 那怎样不内存泄漏呢 哦，原来是使用函数之后再删除空间 
	     // 这里erase不删除，是为了方便后面的函数使用，可以从一个list转移到另一个list 
	    node *erase(node *pos) {
			pos->prev->next = pos->next;
			pos->next->prev = pos->prev;
			len--;
			return pos; 
		}
	
	public:
	    class const_iterator;
	    class iterator {
	    	friend class const_iterator;
	    	friend class list;
		    private://TODO add data members
		    	const list *listname;
		    	node *posi;
		    public:
				iterator(const list *name,node *pos){
		    		listname = name;
		    		posi = pos;
				}
		        iterator operator++(int) {//iter++
		        	if(posi->next == NULL) throw invalid_iterator(); 
					iterator tmp(listname,posi);
					posi = posi->next;
					return tmp;
				}
		        
		        iterator & operator++() {// ++iter
		    	    if(posi->next == NULL) throw invalid_iterator(); 
					posi = posi->next;
					return *this;
				}
		        iterator operator--(int) {// iter--
		        	if(posi->prev->prev == NULL) throw invalid_iterator(); 
					iterator tmp(listname,posi);
					posi = posi->prev;
					return tmp;
				}
		        iterator & operator--() {// --iter
		        	if(posi->prev->prev == NULL) throw invalid_iterator(); 
					posi = posi->prev;
					return *this;
				}
		        // TODO *it
		        // remember to throw if iterator is invalid
		        T & operator *() const {
		        	if(posi==NULL || posi==listname->head || posi==listname->tail)
						throw invalid_iterator();
					return *(posi->data);
				}
		        T * operator ->() const noexcept {
					if(posi==NULL || posi==listname->head || posi==listname->tail)
						throw invalid_iterator();
					return posi->data ;
				}
		        // a operator to check whether two iterators are same (pointing to the same memory).
		        bool operator==(const iterator &rhs) const {
					if(listname != rhs.listname ) return false;
					if(posi != rhs.posi ) return false;
					return true;
				}
		        bool operator==(const const_iterator &rhs) const {
					if(listname != rhs.listname ) return false;
					if(posi != rhs.posi ) return false;
					return true;
				}
		        // some other operator for iterator.
		        bool operator!=(const iterator &rhs) const {
					return !(*this == rhs);
				}
		        bool operator!=(const const_iterator &rhs) const {
					return !(*this == rhs);
				}
	    };
	    
	    class const_iterator { // should be able to construct from an iterator.!!!!!
	    	friend class iterator;
	    	friend class list;
			private:
		    	const list *listname;
		    	node *posi;
		    public:
				const_iterator(const list *name,node *pos){
		    		listname = name;
		    		posi = pos;
				}
				const_iterator(const iterator &x){//private or public?
					listname = x.listname;
					posi = x.posi;
				}
		        const_iterator operator++(int) {//iter++
		        	if(posi->next == NULL) throw invalid_iterator(); 
					//在循环里只用到了i++……要求i++可以到tail，而i--不能到head…… 
					//是因为可以在tail前插入而不可以在head前插入吗
					const_iterator tmp(listname,posi);
					posi = posi->next;
					return tmp;
				}
		        const_iterator & operator++() {// ++iter
		        	if(posi->next == NULL) throw invalid_iterator(); 
					posi = posi->next;
					return *this;
				}
		        const_iterator operator--(int) {// iter--
		        	if(posi->prev->prev == NULL) throw invalid_iterator(); 
					iterator tmp(listname,posi);
					posi = posi->prev;
					return tmp;
				} 
		        const_iterator & operator--() {// --iter
		        	if(posi->prev->prev == NULL) throw invalid_iterator(); 
					posi = posi->prev;
					return *this;
				}
				T & operator *() const {
					if(posi==NULL || posi==listname->head || posi==listname->tail) {
						throw invalid_iterator();	
					}
					return *(posi->data);
				}
		        T * operator ->() const noexcept {
		        	if(posi==NULL || posi==listname->head || posi==listname->tail)
						throw invalid_iterator();
					return posi->data ;
				}
		        // a operator to check whether two iterators are same (pointing to the same memory).
		        bool operator==(const iterator &rhs) const {
					if(listname != rhs.listname ) return false;
					if(posi != rhs.posi ) return false;
					return true;
				}
		        bool operator==(const const_iterator &rhs) const {
					if(listname != rhs.listname ) return false;
					if(posi != rhs.posi ) return false;
					return true;
				}
		        // some other operator for iterator.
		        bool operator!=(const iterator &rhs) const {
					return !(*this == rhs);
				}
		        bool operator!=(const const_iterator &rhs) const {
					return !(*this == rhs);
				}
	    };
	    
	    list() {
			head = new node;
			tail = new node;
			head->prev = NULL; 
			tail->prev = NULL;
			head->next = tail;
			tail->prev = head;
			len = 0;
		}
	    list(const list &other) {
			head = new node;
			tail = head;
			len = other.len;
			node *p = other.head ;
			for(int i=1;i<=len;i++){
				p = p->next;
				node *tmp = new node(*(p->data),tail,NULL);//value,prev!!!和insert不一样,next
				tail = tmp;
			}
			node *taill = tail;
			tail = new node;
			tail->prev = taill;
			taill->next = tail;
		}
	    virtual ~list() { // TODO Destructor
	    	node *p = head, *q;
			while(p){
				q = p;
				p = p->next;
				delete q;
			}
			head = tail = NULL;
			len = 0;
		}
	    // TODO Assignment operator
	    list &operator=(const list &other) {
			if(this == &other) return *this;
			clear(); //留了head和tail 
			node *taill = head;
			len = other.len;
			node *p = other.head ;
			for(int i=1;i<=len;i++){
				p = p->next;
				node *tmp = new node(*(p->data),taill,NULL);
				taill = tmp;
			}
			tail->prev = taill;
			taill->next = tail;
			return *this;//!!!!!!!!!!每次都不写return *this 
		}
	    // access the first / last element
	    // throw container_is_empty when the container is empty.
	    const T & front() const {
			if(len==0) throw container_is_empty();
			return *(head->next->data);
		}
	    const T & back() const {
			if(len==0) throw container_is_empty();
			return *(tail->prev->data);
		}
	    // returns an iterator to the beginning.
	    iterator begin() {
			iterator tmp(this,head->next);//其实不知道是head还是真实的第一个值，由于左闭右开，猜测是第一个值 
			return tmp;
		}
	    const_iterator cbegin() const {
			const_iterator tmp(this,head->next);
			return tmp;
		}
	    // returns an iterator to the end.
	    iterator end() {
			iterator tmp(this,tail);//现确定end是tail指针 
			return tmp;
		}
	    const_iterator cend() const {
			const_iterator tmp(this,tail);
			return tmp;
		}
	    // checks whether the container is empty.
	    virtual bool empty() const {
			return (len==0);
		}
	    // returns the number of elements
	    virtual size_t size() const {
			size_t siz = len;
			return siz;
		}
	    // clears the contents
	    virtual void clear() {//删不删tail和head …… 别删…… 
			node *p = head->next, *q;
			while(p!=tail){
				q = p;
				p = p->next;
				delete q;//要删掉结点 ，因为是clear 
			}
			head->next = tail;
			tail->prev = head;
			len = 0;
		}
	    // insert value before pos (pos may be the end() iterator)
	     // return an iterator pointing to the inserted value
	     // throw if the iterator is invalid
	    virtual iterator insert(iterator pos, const T &value) {
	    	if((!pos.posi)||(!pos.listname)||(pos.listname!=this)) 
				throw invalid_iterator();
	    	node *cur = new node(value); 
			node *tmp = insert(pos.posi,cur);
			iterator ans(this,tmp);
			return ans;
		}
	    // remove the element at pos (the end() iterator is invalid)
	     //returns an iterator pointing to the following element, if pos pointing to the last element, end() will be returned.
	     // throw if the container is empty, the iterator is invalid
	    virtual iterator erase(iterator pos) {
			if(len==0) throw container_is_empty();
			iterator ans(this,pos.posi->next);
			node *tmp = erase(pos.posi); 
			delete tmp;//删 
			return ans;
		}
	    //adds an element to the end
	    void push_back(const T &value) {
			node *cur = new node(value);//value是const类型的变量，所以构造函数加const 
			insert(tail,cur);
		}
	    // removes the last element
	     // throw when the container is empty.
	    void pop_back() {
			if(len==0) throw container_is_empty();
			node *tmp = erase(tail->prev);
			delete tmp;//这里是要删掉的……
		}
	    // inserts an element to the beginning.
	    void push_front(const T &value) {
			node *cur = new node(value);
			insert(head->next,cur);	
		}
	    //removes the first element.
	     // throw when the container is empty.
	    void pop_front() {
	    	if(len==0) throw container_is_empty();
			node *tmp = erase(head->next);
			delete tmp;
		}
	    // sort the values in ascending order with operator< of T
	    void sort() {//是谁准备传个iterator进sjtu::sort里面去，我不说 重载符号也太麻烦了吧…… 
	    	iterator it = begin();//现在体现出来begin和end前闭后开的好处，写起来方便一点 
	    	T *a = (T*) malloc (sizeof(T)*len);
	    	int cnt = 0;
	    	while(it!=end()){
	    		new(a+cnt)T(*(it.posi->data));
				cnt++;
	    		it++;
			}
			sjtu::sort<T>(a,a+len,[](const T &x,const T &y){return x<y ;});
			it = begin();
			cnt = 0;
			while(it!=end()){
	    		if(it.posi->data) it.posi->data->~T();//不能写*(it.posi->data).~T();
				new(it.posi->data)T(a[cnt]);
	    		cnt++;
	    		it++;
			}
			for(int i=0;i<cnt;i++){
				a[i].~T();
			}
			free(a);
		}
	    /* merge two sorted lists into one (both in ascending order)
	     * compare with operator< of T
	     * container other becomes empty after the operation
	     * for equivalent elements in the two lists, the elements from *this shall always precede the elements from other
	     * the order of equivalent elements of *this and other does not change.
	     * no elements are copied or moved
	     */
	    void merge(list &other) {//写的很难看……虽然可能会让复杂度降一点，但也太难看了，明明用insert和erase就很好看 
			node *p = head->next,*q = other.head->next;
			while(p != tail && q!=other.tail){
				while(p!=tail && (*(p->data) < *(q->data) || *(p->data) == *(q->data)))//短路，防止调用这个data空指针 
					p = p->next;
				node *tmp = q;
				while(q!=other.tail && (p->data!=NULL) && *(q->data) < *(p->data)) {//两个短路 
					q = q->next;	
				}
				p->prev->next = tmp;
				tmp->prev = p->prev;
				q->prev->next = p;
				p->prev = q->prev;
			}
			if(q!=other.tail) {
				p->prev->next = q;
				q->prev = p->prev;
				other.tail->prev->next = tail;
				tail->prev = other.tail->next; 
			}
			other.head->next = other.tail;
			other.tail->prev = other.head;
			len += other.len;
			other.len = 0;
			
		}
	    // reverse the order of the elements
	    // no elements are copied or moved
	    void reverse() {
	    	if(len == 0) return ;
	    	node *p = head, *q;
			while(p!=NULL){ //到了tail 仍然需要reverse！！！！ 
				q = p->prev;
				p->prev = p->next;
				p->next = q;
				p = p->prev;
			}
			q = tail;
			tail = head;
			head = q;
		}
	    /**
	     * remove all consecutive duplicate elements from the container
	     * only the first element in each group of equal elements is left
	     * use operator== of T to compare the elements.
	     */
	    void unique() {
			node *p = head->next;
			while(p!=tail){
				node *q;
				node *tmp = p;
				p = p->next;
				q = p; 
				while(p!=tail) {
					p = p->next;
					if(!(*q->data == *tmp->data)) break;
					len--;
					delete q;
					q = p;
				}//first different one
				tmp->next = q;
				q->prev = tmp;
				p = q;
			}
		}
	};
}

#endif //SJTU_LIST_HPP

修改后list

#ifndef SJTU_LIST_HPP
#define SJTU_LIST_HPP

#include "exceptions.hpp"
#include "algorithm.hpp"

#include 
#include 
namespace sjtu {
/**
 * a data container like std::list
 * allocate random memory addresses for data and they are doubly-linked in a list.
 */
template<typename T>
class list {
	protected:
	    class node {
		    public: // add data members and constructors & destructor
		    	node *prev,*next;
		    	T *data;
		    	node(){
		    		data = NULL;
					prev = NULL;
					next = NULL;
				}
		    	node(const T &x,node *p = NULL,node *n = NULL){ 
		    		data = new T(x);
		    		prev = p;
		    		next = n;
		    		if(prev) prev->next = this;
		    		if(next) next->prev = this;
				}
				~node(){
					prev = next = NULL;
					if(data)  {
						delete data;//是这样写吗…难道是说 如果用data.~T()仅仅析构了T，没有释放data的空间！！！ 
				    }
					data = NULL;
				}
	    };
	
	protected:// add data members for linked list as protected members
		node *head,*tail;
		int len;
	    node *insert(node *pos, node *cur) {//在pos之前，插入一个node cur
			 cur->prev = pos->prev;
			 cur->next = pos;
			 pos->prev->next = cur;//有head和tail结点就不会担心有NULL的情况存在了吧 
			 pos->prev = cur;//48 49行不能交换，否则pos->prev改变了 
			 len++;
			 return cur;//你不return的话……怎么得到地址呢…… 为什么你不return 每次都忘记return 
		}
	     // remove node pos from list (no need to delete the node) ，return the removed node pos
		 //不删除 啊！！ 那怎样不内存泄漏呢 哦，原来是使用函数之后再删除空间 
	     // 这里erase不删除，是为了方便后面的函数使用，可以从一个list转移到另一个list 
	    node *erase(node *pos) {
			pos->prev->next = pos->next;
			pos->next->prev = pos->prev;
			len--;
			return pos; 
		}
	
	public:
	    class const_iterator;
	    class iterator {
	    	friend class const_iterator;
	    	friend class list;
		    private://TODO add data members
		    	const list *listname;
		    	node *posi;
		    public:
				iterator(const list *name,node *pos){
		    		listname = name;
		    		posi = pos;
				}
		        iterator operator++(int) {//iter++
		        	if(posi->next == NULL) throw invalid_iterator(); 
					iterator tmp(listname,posi);
					posi = posi->next;
					return tmp;
				}
		        
		        iterator & operator++() {// ++iter
		    	    if(posi->next == NULL) throw invalid_iterator(); 
					posi = posi->next;
					return *this;
				}
		        iterator operator--(int) {// iter--
		        	if(posi->prev->prev == NULL) throw invalid_iterator(); 
					iterator tmp(listname,posi);
					posi = posi->prev;
					return tmp;
				}
		        iterator & operator--() {// --iter
		        	if(posi->prev->prev == NULL) throw invalid_iterator(); 
					posi = posi->prev;
					return *this;
				}
		        // TODO *it
		        // remember to throw if iterator is invalid
		        T & operator *() const {
		        	if(posi==NULL || posi==listname->head || posi==listname->tail)
						throw invalid_iterator();
					return *(posi->data);
				}
		        T * operator ->() const noexcept {
					if(posi==NULL || posi==listname->head || posi==listname->tail)
						throw invalid_iterator();
					return posi->data ;
				}
		        // a operator to check whether two iterators are same (pointing to the same memory).
		        bool operator==(const iterator &rhs) const {
					if(listname != rhs.listname ) return false;
					if(posi != rhs.posi ) return false;
					return true;
				}
		        bool operator==(const const_iterator &rhs) const {
					if(listname != rhs.listname ) return false;
					if(posi != rhs.posi ) return false;
					return true;
				}
		        // some other operator for iterator.
		        bool operator!=(const iterator &rhs) const {
					return !(*this == rhs);
				}
		        bool operator!=(const const_iterator &rhs) const {
					return !(*this == rhs);
				}
	    };
	    
	    class const_iterator { // should be able to construct from an iterator.!!!!!
	    	friend class iterator;
	    	friend class list;
			private:
		    	const list *listname;
		    	node *posi;
		    public:
				const_iterator(const list *name,node *pos){
		    		listname = name;
		    		posi = pos;
				}
				const_iterator(const iterator &x){//private or public?
					listname = x.listname;
					posi = x.posi;
				}
		        const_iterator operator++(int) {//iter++
		        	if(posi->next == NULL) throw invalid_iterator(); 
					//在循环里只用到了i++……要求i++可以到tail，而i--不能到head…… 
					//是因为可以在tail前插入而不可以在head前插入吗
					const_iterator tmp(listname,posi);
					posi = posi->next;
					return tmp;
				}
		        const_iterator & operator++() {// ++iter
		        	if(posi->next == NULL) throw invalid_iterator(); 
					posi = posi->next;
					return *this;
				}
		        const_iterator operator--(int) {// iter--
		        	if(posi->prev->prev == NULL) throw invalid_iterator(); 
					iterator tmp(listname,posi);
					posi = posi->prev;
					return tmp;
				} 
		        const_iterator & operator--() {// --iter
		        	if(posi->prev->prev == NULL) throw invalid_iterator(); 
					posi = posi->prev;
					return *this;
				}
				T & operator *() const {
					if(posi==NULL || posi==listname->head || posi==listname->tail) {
						throw invalid_iterator();	
					}
					return *(posi->data);
				}
		        T * operator ->() const noexcept {
		        	if(posi==NULL || posi==listname->head || posi==listname->tail)
						throw invalid_iterator();
					return posi->data ;
				}
		        // a operator to check whether two iterators are same (pointing to the same memory).
		        bool operator==(const iterator &rhs) const {
					if(listname != rhs.listname ) return false;
					if(posi != rhs.posi ) return false;
					return true;
				}
		        bool operator==(const const_iterator &rhs) const {
					if(listname != rhs.listname ) return false;
					if(posi != rhs.posi ) return false;
					return true;
				}
		        // some other operator for iterator.
		        bool operator!=(const iterator &rhs) const {
					return !(*this == rhs);
				}
		        bool operator!=(const const_iterator &rhs) const {
					return !(*this == rhs);
				}
	    };
	    
	    list() {
			head = new node;
			tail = new node;
			head->next = tail;
			tail->prev = head;
			len = 0;
		}
	    list(const list &other) {
			head = new node;
			tail = head;
			len = other.len;
			node *p = other.head ;
			for(int i=1;i<=len;i++){
				p = p->next;
				node *tmp = new node(*(p->data),tail,NULL);//value,prev!!!和insert不一样,next
				tail = tmp;
			}
			node *taill = tail;
			tail = new node;
			tail->prev = taill;
			taill->next = tail;
		}
	    virtual ~list() { // TODO Destructor
	    	node *p = head, *q;
			while(p){
				q = p;
				p = p->next;
				delete q;
			}
			head = tail = NULL;
			len = 0;
		}
	    // TODO Assignment operator
	    list &operator=(const list &other) {
			if(this == &other) return *this;
			clear(); //留了head和tail 
			node *taill = head;
			len = other.len;
			node *p = other.head ;
			for(int i=1;i<=len;i++){
				p = p->next;
				node *tmp = new node(*(p->data),taill,NULL);
				taill = tmp;
			}
			tail->prev = taill;
			taill->next = tail;
			return *this;//!!!!!!!!!!每次都不写return *this 
		}
	    // access the first / last element
	    // throw container_is_empty when the container is empty.
	    const T & front() const {
			if(len==0) throw container_is_empty();
			return *(head->next->data);
		}
	    const T & back() const {
			if(len==0) throw container_is_empty();
			return *(tail->prev->data);
		}
	    // returns an iterator to the beginning.
	    iterator begin() {
			iterator tmp(this,head->next);//其实不知道是head还是真实的第一个值，由于左闭右开，猜测是第一个值 
			return tmp;
		}
	    const_iterator cbegin() const {
			const_iterator tmp(this,head->next);
			return tmp;
		}
	    // returns an iterator to the end.
	    iterator end() {
			iterator tmp(this,tail);//现确定end是tail指针 
			return tmp;
		}
	    const_iterator cend() const {
			const_iterator tmp(this,tail);
			return tmp;
		}
	    // checks whether the container is empty.
	    virtual bool empty() const {
			return (len==0);
		}
	    // returns the number of elements
	    virtual size_t size() const {
			size_t siz = len;
			return siz;
		}
	    // clears the contents
	    virtual void clear() {//删不删tail和head …… 别删…… 
			node *p = head->next, *q;
			while(p!=tail){
				q = p;
				p = p->next;
				delete q;//要删掉结点 ，因为是clear 
			}
			head->next = tail;
			tail->prev = head;
			len = 0;
		}
	    // insert value before pos (pos may be the end() iterator)
	     // return an iterator pointing to the inserted value
	     // throw if the iterator is invalid
	    virtual iterator insert(iterator pos, const T &value) {
	    	if((!pos.posi)||(!pos.listname)||(pos.listname!=this)) 
				throw invalid_iterator();
	    	node *cur = new node(value); 
			node *tmp = insert(pos.posi,cur);
			iterator ans(this,tmp);
			return ans;
		}
	    // remove the element at pos (the end() iterator is invalid)
	     //returns an iterator pointing to the following element, if pos pointing to the last element, end() will be returned.
	     // throw if the container is empty, the iterator is invalid
	    virtual iterator erase(iterator pos) {
			if(len==0) throw container_is_empty();
			iterator ans(this,pos.posi->next);
			node *tmp = erase(pos.posi); 
			delete tmp;//要删的 
			return ans;
		}
	    //adds an element to the end
	    void push_back(const T &value) {
			node *cur = new node(value);//value是const类型的变量，所以构造函数加const 
			insert(tail,cur);
		}
	    // removes the last element
	     // throw when the container is empty.
	    void pop_back() {
			if(len==0) throw container_is_empty();
			node *tmp = erase(tail->prev);
			delete tmp;//这里是要删掉的……
		}
	    // inserts an element to the beginning.
	    void push_front(const T &value) {
			node *cur = new node(value);
			insert(head->next,cur);	
		}
	    //removes the first element.
	     // throw when the container is empty.
	    void pop_front() {
	    	if(len==0) throw container_is_empty();
			node *tmp = erase(head->next);
			delete tmp;
		}
	    // sort the values in ascending order with operator< of T
	    void sort() {//是谁准备传个iterator进sjtu::sort里面去，我不说 重载符号也太麻烦了吧…… 
	    	iterator it = begin();//现在体现出来begin和end前闭后开的好处，写起来方便一点 
	    	T *a = (T*) malloc (sizeof(T)*len);
	    	int cnt = 0;
	    	while(it!=end()){
	    		new(a+cnt)T(*(it.posi->data));
				cnt++;
	    		it++;
			}
			sjtu::sort<T>(a,a+len,[](const T &x,const T &y){return x<y ;});
			it = begin();
			cnt = 0;
			while(it!=end()){
	    		if(it.posi->data) it.posi->data->~T();//不能写*(it.posi->data).~T();
				new(it.posi->data)T(a[cnt]);
	    		cnt++;
	    		it++;
			}
			for(int i=0;i<cnt;i++){
				a[i].~T();
			}
			free(a);
		}
	    /* merge two sorted lists into one (both in ascending order)
	     * compare with operator< of T
	     * container other becomes empty after the operation
	     * for equivalent elements in the two lists, the elements from *this shall always precede the elements from other
	     * the order of equivalent elements of *this and other does not change.
	     * no elements are copied or moved
	     */
	    void merge(list &other) {//用insert和erase就很好看 
			node *p = head->next,*q = other.head->next;
			while(p != tail && q!=other.tail){
				if(q!=other.tail && *q->data < *p->data){
					node *tmp = other.erase(q);//在other里面删除！ 
					q = tmp->next;
					insert(p,tmp);
				}
				else p = p->next;
			}
			if(q!=other.tail){
				node *tmp = other.erase(q);//在other里面删除！ 
				q = tmp->next;
				insert(p,tmp);
			}
			other.len = 0;
			len += other.len; 
			
		}
	    // reverse the order of the elements , no elements are copied or moved
	    void reverse() {
	    	if(len == 0) return ;
	    	node *p = head, *q;
			while(p!=NULL){ //到了tail 仍然需要reverse！！！！ 
				q = p->prev;
				p->prev = p->next;
				p->next = q;
				p = p->prev;
			}
			q = tail;
			tail = head;
			head = q;
		}
	    /**
	     * remove all consecutive duplicate elements from the container
	     * only the first element in each group of equal elements is left
	     */
	    void unique() {
			node *p = head->next;
			while(p!=tail){
				node *q;
				node *tmp = p;
				p = p->next;
				q = p; 
				while(p!=tail) {
					p = p->next;
					if(!(*q->data == *tmp->data)) break;
					len--;
					delete q;
					q = p;
				}//first different one
				tmp->next = q;
				q->prev = tmp;
				p = q;
			}
		}
	};
}

#endif //SJTU_LIST_HPP

分析函数及其作用

• insert 和 erase （传node *进去的）：仅仅是把结点连到链里面或者从链里面拆下来，不删除
• front 和 back 返回头和尾巴的元素值（T类型）
• begin 和 end 返回头指针和尾指针的迭代器，头是第一个实际结点（head->next），尾是最后一个实际节点的下一个（tail）
• clear 是清空内存，保留头尾结点
• 传迭代器的insert和erase是真的要在链里面某个位置添加或者删除结点，里面可以使用上面写的insert 和 erase，注意这里erase是要删掉的！删掉的方式呢，可以是用前面的erase返回一个指针指向这个拆下来的结点，再delete掉。
  

  
  

• sort是一个排序函数，排好后升序，algorithm里面给的sort是一个只能用于连续空间的函数（否则你就写好几个重载符号的函数，对迭代器的+-*/重载），中间使用的cmp函数是lambda函数。
  

  
  

  所以重新开个动态数组，然后再sort，再赋值回去啦……

• merge函数一开始是纯手写的，没用别的函数，想着可以少改几次指针，就写成了第一份代码里面那个样子，非常的冗长还喜欢出错；后来明白了可以用最前面定义的insert 和 erase （传node *进去的），这两个函数非常适合挪动结点（不是数据的移动，只是指针指的方向变换一下），虽然可能指针 *** 作多了点但是看上去赏心悦目还好写！！（也没那么好写，因为我第一次忘记可能第一个while完了还有other里面的结点没挪进去；第二次忘记修改other的len；第三次忘记修改本身的len，要加一个other.len）
• reverse是反转，也不好写（主要是水平太差的问题，因为我总是掉这掉那，忘记写tail的反转）
• unique是去掉连续重复的元素，只保留第一个，我的方法写的时候指针 *** 作逻辑有问题，盯了一个晚上没发现问题，还不如手动搞个样例测试一下来的快，下次要么搞个样例测试一下要么就学断点调试（助教让我学可是我……我努力学……）后来改掉了，还是有问题（xs），别的同学还是用了insert 和 erase （传node *进去的）那两个函数，写起来很好懂but也不太好写（别问，问就是我太菜了）

写的时候出现的重大问题 1、代码逻辑问题

我真的很容易出逻辑问题……不管是指针的 *** 作顺序还是 *** 作方法，都会出问题……当时想的时候真的没有想清楚……以后思考问题要注意！！

2、代码理解问题

呃呃呃呃这个没办法……不知道什么时候删结点什么时候不删，也不知道什么时候用对应的函数（名字一样的函数太多了），还不知道什么时候用node *什么时候用迭代器，而且也不知道front、back、begin、end都要返回个什么……后来研究了很久才看懂……真的是一点一点磨，就像vector里面是一定要用0-base的

3、请写好返回值

为什么你的非void函数总是不喜欢写返回值？？？？？？？？下次先看清楚好吗？？首先是老熟人的operator assignment ，然后是node *的insert函数，你的心不会痛吗……

4、充分理解new和malloc和T()、delete和free和~T()

情况是这样的：new = malloc + T(); delete = ~T() + free;
在第一版提交代码里，我的~node()里面只写了 ~T()没写free，也就是说只析构了T类型的变量，没释放空间，当然会leak……