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(nullptr){}
        ~Set(){
            if(root)
                delete root;
        }
        bool insert(T const& v){
            node_type** n=&root;
            node_type* p=nullptr;
            while(*n){
                if(v==(*n)->value)
                    return false;
                else{
                    p=*n;
                    n=v<(*n)->value?&((*n)->left):&((*n)->right);
                }
            }
            *n=new node_type(v,p,nullptr,nullptr);
            return true;
        }
        bool has(T const& v){
            node_type* n=root;
            while(n){
                if(v==n->value)
                    return true;
                n=vvalue?n->left:n->right;
            }
            return false;
        }
        bool empty() const{
            return root==nullptr;
        }
        const_iterator begin(){
            node_type* n=root;
            while(n->left) n=n->left;
            return const_iterator(n);
        }
        const_iterator end() const{
            return const_iterator();
        }
};
int main(){
    Set mySet;
    int x=10;
    mySet.insert(x);
    cout<