//边写边改 #ifndef __ZSL_LIST_H__#define __ZSL_LIST_H__#include 
     
      //for size_t,ptrdiff_t,initializer_listtemplate 
      
       struct node_base{    node_base *pre;    node_base *next;    T data;};template 
       
        class list_iterator{public:    using iterator              = list_iterator
        
         ;    using const_iterator        = list_iterator
         
          ;    using self                  = list_iterator
          
           ;public: using value_type = T; using pointer = Ptr; using reference = Ref; using list_type = node_base
           
            *; using size_type = size_t; using deference = ptrdiff_t; list_type node; list_iterator(){}; list_iterator(value_type x) : node(x) {} list_iterator(const self& x) : node(x.node) {} reference operator*() { return (*node).data; } pointer operator->() { return &(operator*()); } bool operator == (const self& x) { return x.node == node; } bool operator != (const self& x) { return x.node != node; } self& operator++(){ node = (list_type)((*node).next); return *this; } self operator++(int){ self tmp = *this; node = (list_type)((*node).next); return tmp; } self& operator--(){ node = (list_type)((*node).pre); return node; } self operator--(int){ self tmp = *this; node = (list_type)((*node).pre); return tmp; }};template 
            
             class list{private: using list_node = node_base
             
              ; using link_type = list_node*;public: using value_type = T; using size_type = size_t; using difference_type = ptrdiff_t; using reference = T&; using const_reference = const T&; using pointer = T*; using const_pointer = const T*; using iterator = list_iterator
              
               ; using const_iterator = list_iterator
               
                ; using reverse_iterator = list_iterator
                
                 ; using const_reverse_iterator = list_iterator
                 
                  ;private: link_type node;private: link_type get_node(){ return (link_type)malloc(8 + sizeof(T)); } void empty_initialize() { node = get_node(); node->pre = node; node->next = node; } link_type create_node(const T& x){ link_type n = get_node(); (*n).data = x; return n; } void destroy_node(link_type it){ it->data->~T(); put_node(it); } void put_node(link_type node){ free(node); }public: explicit list(){ empty_initialize(); } explicit list(size_type count, const T& value = T()){ empty_initialize(); insert(begin(), count, value); } explicit list(size_type count){ empty_initialize(); insert(begin(), count, T()); } list(const list
                  
                   & other){ empty_initialize(); insert(begin(), other.begin(), other.end()); } list(list
                   
                    && other) noexcept{ node = other.node; other.node = nullptr; } list(std::initializer_list
                    
                      init){ empty_initialize(); insert(begin(), init.begin(), init.end()); } ~list
                     
                      (){ clear(); put_node(node); } list
                      
                       & operator=(const list
                       
                        & other){ if(&other != this){ iterator first1 = begin(); iterator last1 = end(); const_iterator first2 = other.begin(); const_iterator last2 = other.end(); while(first1 != last1 && first2 != last2) *++first1 = *++first2; if(first2 == last2) erase(first1, last1); else insert(first1, first2, last2); } return *this; } list
                        
                         & operator=(list
                         
                          && other) noexcept{ if(&other != this){ clear(); destroy_node(node); node = other.node; other.node = nullptr; } } list
                          
                           & operator=(std::initializer_list
                           
                             ilist){ clear(); insert(begin(), ilist.begin(), ilist.end()); } void assign(size_type count, const T& value){ } template
                            
                              void assign(InputIt first, InputIt last); void assign(std::initializer_list
                             
                               ilist); iterator begin() { return (*node).next; } const_iterator cbegin() { return (*node).next; } iterator end() { return node; } const_iterator cend() { return node; } reverse_iterator rbegin() { return (*node).pre; } const_reverse_iterator crbegin(){ return (*node).pre; } reverse_iterator rend() { return (*node).next; } const_reverse_iterator crend() { return (*node).next; } reference front() { return *begin();} const_reference front() const { return *cbegin(); } reference back() { return *(--end()); } const_reference back() const { return *(--cend()); } bool empty() const { return node->next == node;} size_type size() const { size_type len = 0; iterator first = begin(), last = end(); while(first != end()){ ++len; ++first; } return len; } size_type max_size() const { return size_type(-1); } void clear(){ link_type cur = node->next; while(cur != node){ link_type tmp = cur; cur = cur->next; destroy_node(tmp); } node->next = node; node->pre = node; } iterator insert(iterator pos, const T& value){ return insert(static_cast
                              
                               (pos), value); } iterator insert(const_iterator pos, const T& value){ link_type p = create_node(value); p->next = pos.node; p->pre = (pos.node)->pre; (pos.node->pre)->next = p; pos.node->pre = p; return p; } void insert(iterator pos, size_type count, const T& value){ insert(static_cast
                               
                                (pos), count, value); } void insert(const_iterator pos, size_type count, const T& value){ while(--count){ insert(pos, value); } } template
                                
                                  void insert(iterator pos, InputIt first, InputIt last){ insert(static_cast
                                 
                                  (pos), first, last); } template
                                  
                                    void insert(const_iterator pos, InputIt first, InputIt last){ while(first != last){ insert(pos, *first); ++first; } } void insert(const_iterator pos, std::initializer_list
                                   
                                     ilist){ insert(pos, ilist.begin(), ilist.end()); } iterator erase(iterator pos){ return erase(static_cast
                                    
                                     (pos)); } iterator erase(const_iterator pos){ if(pos != end()){ link_type tmp = pos.node; pos.node = pos.node->next; pos.node->pre = tmp->pre; tmp->pre->next = pos.node; destroy_node(tmp); } return pos; } iterator erase(iterator first, iterator last){ return erase(static_cast
                                     
                                      (first), static_cast
                                      
                                       (last)); } iterator erase(const_iterator first, const_iterator last){ while(first != last){ erase(first); ++first; } return first; } void push_back(const T& value){ insert(--end(), value); } void push_back(T&& value){ } void pop_back(){ erase(--end()); } void push_front(const T& value){ insert(begin(), value); } void push_front(T&& value){ } void pop_front(){ erase(begin()); } void resize(size_type count, T value = T()){ iterator cur = begin(); while(--count && cur != end()){ *cur = value; ++begin(); } if(count != 0 && cur == end()) push_back(value); if(count == 0 && cur != end()) erase(++cur); } void resize(size_type count){ resize(count, T()); } void resize(size_type count, const value_type& value){ resize(count, const_cast
                                       
                                        (value)); } void swap(list& other){ std::swap(node, other.node); } void transfer(iterator pos, iterator first, iterator last){ if(pos != end()){ ((*last.node).pre).next = pos.node; ((*first.node).pre).next = last.node; ((*pos.node).pre).next = first.node; link_type tmp = (*pos.node).pre; (*pos.node).pre = (*last.node).pre; (*last.node).pre = (*first.node).pre; (*first.node).pre = tmp; } } //合并两个已排序链表 void merge(list& other){ link_type one = node->next; link_type two = other.node->next; while(one != node && two != node){ if(one->data < two->data){ one = one->next; } if(one->data >= two->data){ link_type tmp = two->next; one->pre->next = two; two->next = one; two->pre = one->pre; one->pre = two; two = tmp; } } other.node->next = node; other.node->pre = node; } void merge(list&& other); template 
                                        
                                          void merge(list& other, Compare comp); template 
                                         
                                           void merge(list&& other, Compare comp); void splice(const_iterator pos, list& other){ if(!other.empty()) transfer(pos, other.begin(), other.end()); } void splice(const_iterator pos, list&& other); void splice(const_iterator pos, list& other, const_iterator it){ //it和pos可能指向同一条链表的同一个位置 iterator tmp = it; ++tmp; if(pos == tmp || pos == it) return; transfer(pos, it, ++it); } void splice(const_iterator pos, list&& other, const_iterator it){ } void splice(const_iterator pos, list& other, const_iterator first, const_iterator last){ if(first != last) transfer(pos, first, last); } void splice(const_iterator pos, list&& other, const_iterator first, const_iterator last); void remove(const T& value){ iterator it = begin(); while(it != end()){ if(value == *it){ link_type tmp = (*it.node).pre; tmp->next = (*it.node).next; ((*it.node).next).pre = tmp; destroy_node(it); *it.node = tmp->next; } } } template 
                                          
                                            void remove_if(UnaryPredicate p); //链表翻转算法 //利用两个指针，每次和begin()进行transfer void reverse(){ if(node->next == node || node->next->next == node) return; iterator fast = begin(); ++fast; while(fast != end()){ iterator slow = fast; ++fast; transfer(begin(), slow, fast); } } void unique(){ if(!empty() && (++begin() != end())){ iterator slow = begin(); iterator fast = ++begin(); while(fast != end()){ if(*slow == *fast) remove(*fast); else ++fast, ++slow; } } } template 
                                           
                                             void unique(BinaryPredicate p); //采用快速排序 void sort(){ if(node->next == node || node->next->next == node) return; list
                                            
                                              carry; list
                                             
                                               counter[64]; int fill = 0; while(!empty()){ int i = 0; carry.splice(carry.begin(), *this, begin()); while(i < fill && !counter[i].empty()){ counter[i].merge(carry);//注意使用merge，merge是对两个已经排序的链表进行合并 carry.swap(counter[i++]);//注意i++ } carry.swap(counter[i]); if(i == fill) ++fill; } for(int i = 0; i < fill; ++i) counter[i].merge(counter[i - 1]);//注意merge方式 swap(counter[fill - 1]); } template 
                                              
                                                void sort(Compare comp);};template 
                                               
                                                bool operator==(const list
                                                
                                                 & lhs, const list
                                                 
                                                  & rhs){ auto l = lhs.begin(); auto r = rhs.begin(); while(l != lhs.end() && rhs != lhs.end()){ if(*l != *r) return false; } return (l == lhs.end()) || (r == rhs.end());}template 
                                                  
                                                   bool operator!=(const list
                                                   
                                                    & lhs, const list
                                                    
                                                     & rhs){ return !(lhs == rhs);}template 
                                                     
                                                      bool operator<(const list
                                                      
                                                       & lhs, const list
                                                       
                                                        & rhs){ auto l = lhs.begin(); auto r = rhs.begin(); while(l != lhs.end() && rhs != lhs.end()){ if(*l >= *r) return false; } return (l == lhs.end()) && (r != rhs.end());}template 
                                                        
                                                         bool operator<=(const list
                                                         
                                                          & lhs, const list
                                                          
                                                           & rhs){ return !(lhs > rhs);}template 
                                                           
                                                            bool operator>(const list
                                                            
                                                             & lhs, const list
                                                             
                                                              & rhs){ auto l = lhs.begin(); auto r = rhs.begin(); while(l != lhs.end() && rhs != lhs.end()){ if(*l <= *r) return false; } return (l != lhs.end()) && (r == rhs.end());}template 
                                                              
                                                               bool operator>=(const list
                                                               
                                                                & lhs, const list
                                                                
                                                                 & rhs){ return !(lhs < rhs);}#endif // !__ZSL_LIST_H__