STL浅析——迭代器是一种智能指针(smart pointer)

　　迭代器（iterators）是一种抽象的设计概念，23种设计模式中迭代器模式定义为：提供一种方法，使之能够依次巡访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。

　　在STL的实际运用中，迭代器扮演着重要的角色，STL的中心思想在于：将数据和算法分开，彼此独立设计，最后以一贴胶合剂将它们撮合到一起。容器和算法的泛型化，从技术角度看并不困难，C++的class templates 和 function templates 可分别达到目标，如何设计两者之间的胶合剂，才是最大的难题。

　　迭代器是一种行为类似指针的对象，而指针的各种行为中最常见的便是内容提领（dereference）和成员访问（number access），因此迭代器最重要的编程是对 operator* 和 operator-> 进行重载，在C++标准库中，有个 auto_prt ，这是一个用来包装原生指针的对象，auto_ptr 在 memory 源码中，以下是该指针的源代码：

　　

#ifndef __SGI_STL_MEMORY
#define __SGI_STL_MEMORY

__STL_BEGIN_NAMESPACE

#if defined(__SGI_STL_USE_AUTO_PTR_CONVERSIONS) && 
    defined(__STL_MEMBER_TEMPLATES)

template<class _Tp1> struct auto_ptr_ref {
  _Tp1* _M_ptr;
  auto_ptr_ref(_Tp1* __p) : _M_ptr(__p) {}
};

#endif

template <class _Tp> class auto_ptr {
private:
  _Tp* _M_ptr;   //封装普通指针

public:
  typedef _Tp element_type;
  //explicit 构造函数的explicit关键词有效阻止从一个“裸”指针隐式转换成auto_ptr类型。
  explicit auto_ptr(_Tp* __p = 0) __STL_NOTHROW : _M_ptr(__p) {}
  auto_ptr(auto_ptr& __a) __STL_NOTHROW : _M_ptr(__a.release()) {}

//:_M_ptr(__a.release())表示__a释放自己对对象的掌控权，然后把掌控权丢给另外一个auto_ptr(实际上是_M_ptr夺取掌控权)
#ifdef __STL_MEMBER_TEMPLATES
  template <class _Tp1> auto_ptr(auto_ptr<_Tp1>& __a) __STL_NOTHROW
    : _M_ptr(__a.release()) {}
#endif /* __STL_MEMBER_TEMPLATES */


//取消_M_ptr对现有对象的掌控，改成掌控新的auto_ptr对象a
  auto_ptr& operator=(auto_ptr& __a) __STL_NOTHROW {
    if (&__a != this) {
      delete _M_ptr;
      _M_ptr = __a.release();
    }
    return *this;
  }

#ifdef __STL_MEMBER_TEMPLATES
  template <class _Tp1>
  auto_ptr& operator=(auto_ptr<_Tp1>& __a) __STL_NOTHROW {
    if (__a.get() != this->get()) {
      delete _M_ptr;
      _M_ptr = __a.release();
    }
    return *this;
  }
#endif /* __STL_MEMBER_TEMPLATES */


  ~auto_ptr() { delete _M_ptr; }

  _Tp& operator*() const __STL_NOTHROW {
    return *_M_ptr;
  }
  _Tp* operator->() const __STL_NOTHROW {
    return _M_ptr;
  }
  _Tp* get() const __STL_NOTHROW {
    return _M_ptr;
  }
  _Tp* release() __STL_NOTHROW {
    _Tp* __tmp = _M_ptr;
    _M_ptr = 0;
    return __tmp;
  }
  void reset(_Tp* __p = 0) __STL_NOTHROW {
    if (__p != _M_ptr) {
      delete _M_ptr;
      _M_ptr = __p;
    }
  }

#if defined(__SGI_STL_USE_AUTO_PTR_CONVERSIONS) && 
    defined(__STL_MEMBER_TEMPLATES)

public:
  auto_ptr(auto_ptr_ref<_Tp> __ref) __STL_NOTHROW
    : _M_ptr(__ref._M_ptr) {}

  auto_ptr& operator=(auto_ptr_ref<_Tp> __ref) __STL_NOTHROW {
    if (__ref._M_ptr != this->get()) {
      delete _M_ptr;
      _M_ptr = __ref._M_ptr;
    }
    return *this;
  }

  template <class _Tp1> operator auto_ptr_ref<_Tp1>() __STL_NOTHROW 
    { return auto_ptr_ref<_Tp1>(this->release()); }
  template <class _Tp1> operator auto_ptr<_Tp1>() __STL_NOTHROW
    { return auto_ptr<_Tp1>(this->release()); }

#endif /* auto ptr conversions && member templates */
};

__STL_END_NAMESPACE

#endif /* __SGI_STL_MEMORY */

　　有了上方的迭代器，可以为下方链表设计一个迭代器：

#include <iostream>
using namespace std;
template<class T>
//节点类
class ListItem
{
public:
    ListItem(T value):_value(value), _next(NULL){}
    T value()
    {
        return _value;
    }
    void setNext(ListItem<T> *newNode)
    {
        _next = newNode;
    }
    ListItem* getNext()
    {
        return _next;
    }
private:
    T _value;
    ListItem* _next;
};
//单链表类
template<class T>
class List
{
public:
    //...
    List():_size(0)
    {
        _front = _end = NULL;
    }
    void insert_front(T value)
    {
        ListItem<T> *newNode = new ListItem<T>(value);
        if(_size == 0)
        {
            _end = _front = newNode;
        }
        else
        {
            newNode -> setNext(_front);
            _front = newNode;
        }
        _size++;
    }
    void insert_end(T value)
    {
        ListItem<T> *newNode = new ListItem<T>(value);
        if(_size == 0)
        {
            _end = _front = newNode;
        }
        else
        {
            _end -> setNext(newNode);
            _end = _end -> getNext();
        }
        _size++;
    }
    
    void display()
    {
        ListItem<T>* temp = _front;
        while(temp != _end -> getNext())
        {
            printf("%d ", temp -> value());
            temp = temp -> getNext(); 
        }
        printf("
");
    }
    void getSize()
    {
        printf("%d
", _size);
    }
    ListItem<T>*front()
    {
        return _front;
    }
    ListItem<T>*back()
    {
        return _end;
    }
private:
    ListItem<T>* _end;
    ListItem<T>* _front;
    long _size;
};
//迭代器类
template<class Item>
struct ListIter
{
    Item* ptr;
    
    ListIter(Item* p = 0):ptr(p) {}
    
    Item& operator* () const {return *ptr;}
    Item* operator -> () const {return ptr;}
    
    ListIter& operator++()
    {
        ptr = ptr -> getNext();
        return *this;
    }
    
    ListIter operator++(int)
    {
        ListIter tmp = *this;
        ++*this;
        return tmp;
    }
    
    bool operator==(const ListIter& i)const
    {
        return ptr == i.ptr;
    }
    bool operator!=(const ListIter& i)const
    {
        return ptr != i.ptr;
    }
};

ListIter<ListItem<int> > find(ListIter<ListItem<int> > &begin, ListIter<ListItem<int> > &end, int value)
{
    ListIter<ListItem<int> > first = begin;
    ListIter<ListItem<int> > last = end;
    while( first != last -> getNext())
    {
        if(first -> value() != value)
        {
            first++;
        }
        else
        {
            return first;
        }
        
    }
    return end -> getNext();
}

　　并且加上测试程序：

int main()
{
    List<int> m_ListItor;
    for(int i = 0; i < 6; i++)
    {
        m_ListItor.insert_front(i);
        m_ListItor.insert_end(i + 2);
    }
    m_ListItor.display();        //5 4 3 2 1 0 2 3 4 5 6 7
    
    ListIter<ListItem<int> > begin(m_ListItor.front());
    ListIter<ListItem<int> > end(m_ListItor.back());
    ListIter<ListItem<int> > iter;
    
    iter = find(begin, end, 3);
    if(iter == end -> getNext())
    {
        printf("%s", "not found");
    }
    else
    {
        printf("%d
", iter -> value());
    }
    
    
    iter = find(begin, end, 8);
    if(iter == end -> getNext())
    {
        printf("%s", "not found");
    }
    else
    {
        printf("%d", iter -> value());
    }
    return 0;
}

　　输出结果：

　　　　　　　　　　

　　以上可以看出，为了完成一个针对List而设计的迭代器，我们必须暴露太多有关于 List 实现细节，在 main 函数中制作 begin() 和 end() 两个迭代器，我们暴露了 ListItem，在 ListIter class 中为了达成operator++，我们暴露了 ListItem 的操作函数 getNext()，如果不是为了迭代器，ListItem 是要完全隐藏起来不曝光的。换句话说只有对 ListItem 的实现细节特别了解，才能设计出迭代器，既然这无法避免，干脆把迭代器的设计工作交给 List 的设计者，如此一来，所有实现细节反而不被使用者发现，这也是为什么 STL 的每一种容器都有自己专属的迭代器的原因。