C++模板实战5： 迭代器与容器(一)

容器通过提供大致统一的迭代器界面供外界访问数据，而算法只作用于迭代器，从而摆脱对具体类型的依赖。

实例1： 带有迭代器的双向链表简易实现：

#include
  
   
#include
   
     _Pragma ("once") template
    
      class List; template
     
       class Iterator{ public: using value_type=typename N::value_type; using reference_type=typename N::reference_type; using const_reference_type=typename N::const_reference_type; using self_type=Iterator
      
       ; Iterator():pos(0){} Iterator(N* p):pos(p){} bool operator !=(self_type const& right) const{ return pos!=right.pos; } bool operator ==(self_type const& right) const{ return pos==right.pos; } self_type& operator++(){ if(pos){ pos=pos->next; } return *this; } reference_type operator*() throw(std::runtime_error){ if(pos) return pos->value; else throw (std::runtime_error("defreferenceing null iterator")); } private: N* pos; template
       
         friend class list; }; template
        
          class Node{ public: using value_type=T; using reference_type=T&; using const_reference_type=const T&; T value; Node* prev; Node* next; Node(T const& v,Node* p,Node* n) :value(v),prev(p),next(n){} }; template
         
           class List{ private: using node_type=Node
          
           ; node_type* head; public: using value_type=T; using iterator=Iterator
           
            ; List():head(nullptr){} ~List(){ while(head){ node_type* n=head; head=head->next; delete n; } } void push_front(T const& v){ head=new node_type(v,nullptr,head); if(head->next){ head->next->prev=head; } } void pop_front(T& v){ if(head){ node_type* temp=head; head=head->next; if(head) head->prev=nullptr; v=temp->value; delete temp; } } void insert(iterator it,T const& v){ node_type* n=it.pos; if(n){ node_type* new_node=new node_type(v,n,n->next); new_node->next->prev=new_node; n->next=new_node; } } void erase(iterator& it){ node_type* n=it.pos; ++it; if(n){ if(n->next) n->next->prev=n->prev; if(n->prev) n->prev->next=n->next; delete n; } } bool empty() const{ return head==nullptr; } iterator begin(){ return iterator(head); } iterator end(){ return iterator(); } }; int main(){ List
            
              myList; int x=10; myList.push_front(x); int y; myList.pop_front(y); std::cout<
             
              
 实例2：带有迭代器的简易set实现： 
              
 
              
 
              
#include
               
                
#include
                
                  using namespace std; _Pragma("once") template
                 
                   class Iterator{ private: const N* pos; public: using value_type=typename N::value_type; using const_reference_type=typename N::const_reference_type; using self_type=Iterator
                  
                   ; Iterator():pos(nullptr){} Iterator(const N* p):pos(p){} bool operator==(self_type const& right) const{ return pos==right.pos; } self_type& operator++(){ if(pos){ if(pos->right){ pos=pos->right; while(pos->left) pos=pos->left; } else{ while((pos->parent)&&(pos->parent->right==pos)) pos=pos->parent; pos=pos->parent; } } return *this; } const_reference_type operator*() const throw(std::runtime_error){ if(pos) return pos->value; else throw std::runtime_error("deferencing null iterator"); } }; template
                   
                     bool operator!=(Iterator
                    
                      const &left,Iterator
                     
                       const &right){ return !(left==right); } template
                      
                        class Node{ public: using value_type=T; using reference_type=T&; using const_reference_type=const T&; T value; Node* parent; Node* left; Node* right; Node(T const& v,Node* p,Node* l,Node* r) :value(v),parent(p),left(l),right(r){} ~Node(){ if(left) delete left; if(right) delete right; } }; template
                       
                         class Set{ private: using node_type=Node
                        
                         ; node_type* root; public: using value_type=T; using const_iterator=Iterator
                         
                          ; Set():root(nu