stl auto_ptr源码注释及若干问题笔记

解决问题

1.注释 stl auto_ptr 源码。
2.弄明白 auto_ptr_ref 实现机制和要解决的问题;
3.自己实现一个auto_ptr,并实现一个测试程序;

stl auto_ptr 源码注释

{
    /**
     *  A wrapper class to provide auto_ptr with reference semantics.
     *  For example, an auto_ptr can be assigned (or constructed from)
     *  the result of a function which returns an auto_ptr by value.
     *
     *  All the auto_ptr_ref stuff should happen behind the scenes.
     */
    //注释:当函数的返回值是 auto_ptr 时候,会造成一次传值转换。但是 auto_ptr构造
    //时候,需要将传入的auto_ptr进行release(),因此无法以传值方式进行构造,必须是引用
    //如: auto_ptr(auto_ptr& _a)。这就造成了函数返回值是传值时候会编译出错。
    //出错场景:
    //1. auto_ptr<int> p=new auto_ptr<int>(new int);
    //2. auto_ptr<int> func1();
    //   auto_ptr<int> p=func1();
    //
    //解决方案是利用返回时候进行的一次强行值转换进行。
    //1. return 时候,先强行将 auto_ptr 强行转换成 auto_ptr_ref;
    //2. auto_ptr 增加 auto_ptr(auto_ptr_ref _ref) 构造实现。
    //3. auto_ptr 增加一个操作符 operator = (auto_ptr_ref) 的实现。
    //4. 至此,实现了对返回值是 auto_ptr 的值的函数调用;
    template<typename _Tp1>
        struct auto_ptr_ref
        {
            _Tp1* _M_ptr;

            explicit
                auto_ptr_ref(_Tp1* __p): _M_ptr(__p) { }
        } _GLIBCXX_DEPRECATED;

    /**
     *  @brief  A simple smart pointer providing strict ownership semantics.
     *
     *  The Standard says:
     *  <pre>
     *  An @c auto_ptr owns the object it holds a pointer to.  Copying
     *  an @c auto_ptr copies the pointer and transfers ownership to the
     *  destination.  If more than one @c auto_ptr owns the same object
     *  at the same time the behavior of the program is undefined.
     *
     *  The uses of @c auto_ptr include providing temporary
     *  exception-safety for dynamically allocated memory, passing
     *  ownership of dynamically allocated memory to a function, and
     *  returning dynamically allocated memory from a function.  @c
     *  auto_ptr does not meet the CopyConstructible and Assignable
     *  requirements for Standard Library <a
     *  href="tables.html#65">container</a> elements and thus
     *  instantiating a Standard Library container with an @c auto_ptr
     *  results in undefined behavior.
     *  </pre>
     *  Quoted from [20.4.5]/3.
     *
     *  Good examples of what can and cannot be done with auto_ptr can
     *  be found in the libstdc++ testsuite.
     *
     *  _GLIBCXX_RESOLVE_LIB_DEFECTS
     *  127.  auto_ptr<> conversion issues
     *  These resolutions have all been incorporated.
     */
    template<typename _Tp>
        class auto_ptr
        {
            private:
                //保存指针的数据
                _Tp* _M_ptr;

            public:
                /// The pointed-to type.
                //也许是为了增加可读性
                //手册中规定了 auto_ptr::element_type 是类型别名
                typedef _Tp element_type;

                /**
                 *  @brief  An %auto_ptr is usually constructed from a raw pointer.
                 *  @param  __p  A pointer (defaults to NULL).
                 *
                 *  This object now @e owns the object pointed to by @a __p.
                 */
                //explicit 这个限制符让强行转换失效,类如: auto_ptr<int> = 0x10001; 
                //指针 0x10001 不再构造 auto_ptr(*p) 并调用 operator =;
                explicit
                    auto_ptr(element_type* __p = 0) throw() : _M_ptr(__p) { }

                /**
                 *  @brief  An %auto_ptr can be constructed from another %auto_ptr.
                 *  @param  __a  Another %auto_ptr of the same type.
                 *
                 *  This object now @e owns the object previously owned by @a __a,
                 *  which has given up ownership.
                 */
                //另一个相同类型的 auto_ptr 作为构造参数;
                auto_ptr(auto_ptr& __a) throw() : _M_ptr(__a.release()) { }

                /**
                 *  @brief  An %auto_ptr can be constructed from another %auto_ptr.
                 *  @param  __a  Another %auto_ptr of a different but related type.
                 *
                 *  A pointer-to-Tp1 must be convertible to a
                 *  pointer-to-Tp/element_type.
                 *
                 *  This object now @e owns the object previously owned by @a __a,
                 *  which has given up ownership.
                 */
                //另一个不同类型的 auto_ptr 作为构造参数;
                template<typename _Tp1>
                    auto_ptr(auto_ptr<_Tp1>& __a) throw() : _M_ptr(__a.release()) { }

                /**
                 *  @brief  %auto_ptr assignment operator.
                 *  @param  __a  Another %auto_ptr of the same type.
                 *
                 *  This object now @e owns the object previously owned by @a __a,
                 *  which has given up ownership.  The object that this one @e
                 *  used to own and track has been deleted.
                 */
                //相同类型的 auto_ptr 赋值
                //赋值的时候,先将右值 auto_ptr 保存的地址释放掉,
                //左值 auto_ptr 赋值,注意返回是自己的一个引用。
                auto_ptr&
                    operator=(auto_ptr& __a) throw()
                    {
                        reset(__a.release());
                        return *this;
                    }

                /**
                 *  @brief  %auto_ptr assignment operator.
                 *  @param  __a  Another %auto_ptr of a different but related type.
                 *
                 *  A pointer-to-Tp1 must be convertible to a pointer-to-Tp/element_type.
                 *
                 *  This object now @e owns the object previously owned by @a __a,
                 *  which has given up ownership.  The object that this one @e
                 *  used to own and track has been deleted.
                 */
                //不相同类型的 auto_ptr 赋值
                //赋值的时候,先将右值 auto_ptr 保存的地址释放掉,
                //左值 auto_ptr 赋值,注意返回是自己的一个引用。
                template<typename _Tp1>
                    auto_ptr&
                    operator=(auto_ptr<_Tp1>& __a) throw()
                    {
                        reset(__a.release());
                        return *this;
                    }

                /**
                 *  When the %auto_ptr goes out of scope, the object it owns is
                 *  deleted.  If it no longer owns anything (i.e., @c get() is
                 *  @c NULL), then this has no effect.
                 *
                 *  The C++ standard says there is supposed to be an empty throw
                 *  specification here, but omitting it is standard conforming.  Its
                 *  presence can be detected only if _Tp::~_Tp() throws, but this is
                 *  prohibited.  [17.4.3.6]/2
                 */
                //智能指针析构时候,释放自己拥有的申请的内存
                ~auto_ptr() { delete _M_ptr; }

                /**
                 *  @brief  Smart pointer dereferencing.
                 *
                 *  If this %auto_ptr no longer owns anything, then this
                 *  operation will crash.  (For a smart pointer, <em>no longer owns
                 *  anything</em> is the same as being a null pointer, and you know
                 *  what happens when you dereference one of those...)
                 */
                //智能指针提领返回类型的引用
                //注意,如果这里如果智能指针是空值,程序会挂。
                //这里的const是指不能修改指针,对于指针指向的对象,是可以修改的。
                element_type&
                    operator*() const throw() 
                    {
                        _GLIBCXX_DEBUG_ASSERT(_M_ptr != 0);
                        return *_M_ptr; 
                    }

                /**
                 *  @brief  Smart pointer dereferencing.
                 *
                 *  This returns the pointer itself, which the language then will
                 *  automatically cause to be dereferenced.
                 */
                //操作符 -> 会返回指针
                element_type*
                    operator->() const throw() 
                    {
                        _GLIBCXX_DEBUG_ASSERT(_M_ptr != 0);
                        return _M_ptr; 
                    }

                /**
                 *  @brief  Bypassing the smart pointer.
                 *  @return  The raw pointer being managed.
                 *
                 *  You can get a copy of the pointer that this object owns, for
                 *  situations such as passing to a function which only accepts
                 *  a raw pointer.
                 *
                 *  @note  This %auto_ptr still owns the memory.
                 */
                //返回原始指针,有一些函数可能使用原始指针,此时需要用到 get()
                element_type*
                    get() const throw() { return _M_ptr; }

                /**
                 *  @brief  Bypassing the smart pointer.
                 *  @return  The raw pointer being managed.
                 *
                 *  You can get a copy of the pointer that this object owns, for
                 *  situations such as passing to a function which only accepts
                 *  a raw pointer.
                 *
                 *  @note  This %auto_ptr no longer owns the memory.  When this object
                 *  goes out of scope, nothing will happen.
                 */
                //放弃掉对 _M_ptr 的访问权限
                element_type*
                    release() throw()
                    {
                        element_type* __tmp = _M_ptr;
                        _M_ptr = 0;
                        return __tmp;
                    }

                /**
                 *  @brief  Forcibly deletes the managed object.
                 *  @param  __p  A pointer (defaults to NULL).
                 *
                 *  This object now @e owns the object pointed to by @a __p.  The
                 *  previous object has been deleted.
                 */
                //使用指针 p 对 _M_ptr 进行赋值
                void reset(element_type* __p = 0) throw()
                    {
                        if (__p != _M_ptr)
                        {
                            delete _M_ptr;
                            _M_ptr = __p;
                        }
                    }

                /** 
                 *  @brief  Automatic conversions
                 *
                 *  These operations convert an %auto_ptr into and from an auto_ptr_ref
                 *  automatically as needed.  This allows constructs such as
                 *  @code
                 *    auto_ptr<Derived>  func_returning_auto_ptr(.....);
                 *    ...
                 *    auto_ptr<Base> ptr = func_returning_auto_ptr(.....);
                 *  @endcode
                 */
                //使用见 auto_ptr_ref 的设计方法
                //使用 auto_ptr_ref 构造 auto_ptr
                auto_ptr(auto_ptr_ref<element_type> __ref) throw()
                    : _M_ptr(__ref._M_ptr) { }

                //使用见 auto_ptr_ref 的设计方法
                //使用 auto_ptr_ref 复制
                auto_ptr&
                    operator=(auto_ptr_ref<element_type> __ref) throw()
                    {
                        if (__ref._M_ptr != this->get())
                        {
                            delete _M_ptr;
                            _M_ptr = __ref._M_ptr;
                        }
                        return *this;
                    }

                //使用见 auto_ptr_ref 的设计方法,
                //类型强行转换,将自己(auto_ptr)强行转成 auto_ptr_ref;
                //转换之后,自己不再拥有内存
                template<typename _Tp1>
                    operator auto_ptr_ref<_Tp1>() throw()
                    { return auto_ptr_ref<_Tp1>(this->release()); }

                //类型强行转换,将自己(auto_ptr)强行转成另一个类型的auto_ptr;
                //转换之后,自己不再拥有内存
                //这个在什么场景下调用? 有些费解。
                //TODO:解析这个函数应用场景
                template<typename _Tp1>
                    operator auto_ptr<_Tp1>() throw()
                    { return auto_ptr<_Tp1>(this->release()); }
        } _GLIBCXX_DEPRECATED;

    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 541. shared_ptr template assignment and void
    // 对空类型的  auto_ptr 偏特化,如果不做处理, auto_ptr<void> p4; 会出错
    template<>
        class auto_ptr<void>
        {
            public:
                //手册中规定了 auto_ptr::element_type 是类型别名
                typedef void element_type;
        } _GLIBCXX_DEPRECATED;

    //C++ 11 宏
#if __cplusplus >= 201103L
    template<_Lock_policy _Lp>
        template<typename _Tp>
        inline
        __shared_count<_Lp>::__shared_count(std::auto_ptr<_Tp>&& __r)
        : _M_pi(new _Sp_counted_ptr<_Tp*, _Lp>(__r.get()))
        { __r.release(); }

    template<typename _Tp, _Lock_policy _Lp>
        template<typename _Tp1>
        inline
        __shared_ptr<_Tp, _Lp>::__shared_ptr(std::auto_ptr<_Tp1>&& __r)
        : _M_ptr(__r.get()), _M_refcount()
        {
            __glibcxx_function_requires(_ConvertibleConcept<_Tp1*, _Tp*>)
                static_assert( sizeof(_Tp1) > 0, "incomplete type" );
            _Tp1* __tmp = __r.get();
            _M_refcount = __shared_count<_Lp>(std::move(__r));
            __enable_shared_from_this_helper(_M_refcount, __tmp, __tmp);
        }

    //C++ 新增 share_ptr
    //gcc.4.9.3/gcc-4.9.3/libstdc++-v3/include/bits/shared_ptr_base.h
    template<typename _Tp>
        template<typename _Tp1>
        inline
        shared_ptr<_Tp>::shared_ptr(std::auto_ptr<_Tp1>&& __r)
        : __shared_ptr<_Tp>(std::move(__r)) { }

    //C++ 新增 unique_ptr,关于 unique_ptr 在文件
    //gcc.4.9.3/gcc-4.9.3/libstdc++-v3/include/bits/unique_ptr.h
    template<typename _Tp, typename _Dp>
        template<typename _Up, typename>
        inline
        unique_ptr<_Tp, _Dp>::unique_ptr(auto_ptr<_Up>&& __u) noexcept
        : _M_t(__u.release(), deleter_type()) { }
#endif

    _GLIBCXX_END_NAMESPACE_VERSION
} // namespace

auto_ptr_ref 实现机制

auto_ptr_ref 是用来解决 auto_ptr::auto_ptr(const auto_ptr&);
类似这种场景:

auto_ptr function();
int main(){auto_ptr f=function();}

注意到,这个 function 的返回值是一个临时变量(这个匿名的变量会在这个语句结束之后自动释放(自动析构)。C++语法规定,临时变量传输必须是 const 引用或者传值.这样做是为了避免程序员修改一个即将被销毁的变量。

那如何根据 function 的返回值来生成一个 'f' 呢?答案是通过利用 auto_ptr_ref 类。 C++编译器通过以下两个过程达成目标。
1.将 auto_ptr 转成一个 auto_ptr_ref 对象, 这时候 auto_ptr 将自身的指向的内存传给 auto_ptr_ref.(注意,这一步我们是通过调用一个 no-const 强行转换函数临时生成).

  1. 将 auto_ptr_ref 转成 auto_ptr, 这时候的 auto_ptr 就是我们所需要的'f1',并获得 auto_ptr_ref 指向的内存。

这里面的返回值优化和函数中的const 参数调用重载另外说明

下面的 function1(),function2() 可以清楚的观察到这个过程。

#include <iostream>
using std::cout;
using std::endl;

class auto_ptr
{
    private:
        struct auto_ptr_ref { };

    public:
        auto_ptr() { cout << "auto_ptr::auto_ptr()\n"; }
        auto_ptr(auto_ptr&) { cout << "auto_ptr::auto_ptr(auto_ptr&)\n"; }
        operator auto_ptr_ref()
        { cout << "auto_ptr::operator auto_ptr_ref()\n"; }
        auto_ptr(auto_ptr_ref) { cout <<
            "auto_ptr::auto_ptr(auto_ptr_ref)\n"; }
        ~auto_ptr() { cout << "auto_ptr::~auto_ptr()\n"; }
};

auto_ptr function1();
auto_ptr function2();

int main()
{
    auto_ptr f1=function1(); // 调用 function function1() ,过程如下
    // 调用 "auto_ptr::auto_ptr(const auto_ptr&)", 没找到
    // 不能调用"auto_ptr::auto_ptr(auto_ptr&)",因为function1()的返回值是一个临时变量。
    // 编译器决定执行“两步转换”:
    // 1) 使用 "auto_ptr::operator auto_ptr_ref()"
    // 2) 使用 "auto_ptr::auto_ptr(auto_ptr_ref)" 构造出 'f1'
    // 此时,使用 "auto_ptr::~auto_ptr()" 析构销毁 'function1()' 的返回值

    cout << "after1\n";

    auto_ptr f2=function2(); //返回值步骤具体和function1()类似,但是里面还生成了一个匿名函数,因此会多一次 “两步转换”;
    cout << "after2\n";
} // 2 calls to "auto_ptr::~auto_ptr()" to destroy 'f1' and 'f2'

auto_ptr function1() //编译器**如果没执行返回值优化**,其调用如下所示
{
    auto_ptr a; // 调用"auto_ptr::auto_ptr()",生成变量 a
    return a; // 调用"auto_ptr::auto_ptr(auto_ptr&)" 生成临时变量返回。
} // 调用"auto_ptr::~auto_ptr()" 销毁变量 'a'

auto_ptr function2() 
{
    return auto_ptr(); //调用"auto_ptr::auto_ptr()"生成临时变量。
    //调用 "auto_ptr::auto_ptr(const auto_ptr&)",没找到
    //编译器质性“两步转换”,生成一个临时变量用于返回。
}
//调用"auto_ptr::~auto_ptr()" 销毁返回的临时变量。

lawrencechi@LawrencechideMacBook-Pro ~/temp/test » make                                                                                                                        127 ↵
g++ -g main.cpp -o test
main.cpp:14:58: warning: control reaches end of non-void function [-Wreturn-type]
        { cout << "auto_ptr::operator auto_ptr_ref()\n"; }
                                                         ^
1 warning generated.
lawrencechi@LawrencechideMacBook-Pro ~/temp/test » ./test
auto_ptr::auto_ptr()
auto_ptr::operator auto_ptr_ref()
auto_ptr::auto_ptr(auto_ptr_ref)
auto_ptr::~auto_ptr()
after1
auto_ptr::auto_ptr()
auto_ptr::operator auto_ptr_ref()
auto_ptr::auto_ptr(auto_ptr_ref)
auto_ptr::~auto_ptr()
auto_ptr::operator auto_ptr_ref()
auto_ptr::auto_ptr(auto_ptr_ref)
auto_ptr::~auto_ptr()
after2
auto_ptr::~auto_ptr()
auto_ptr::~auto_ptr()
lawrencechi@LawrencechideMacBook-Pro ~/temp/test »

自己实现 auto_ptr

1.考虑构造函数 auto_ptr(const auto_ptr&) 不能用,必须用 auto_ptr(auto_ptr&);
2.由于1,所以必须使用 auto_ptr_ref机制规避返回值为auto_ptr时候的问题;
3.必须要考虑特化版本 template<> auto_ptr;
4.赋值操作符,构造函数考虑类型转换问题,构造函数中的 explicit 限定符问题;

#include <iostream>
#include <string>
using std::cout;
using std::endl;
using std::string;

template<typename T>
struct auto_ptr_ref
{
    T* pointee;

    explicit
        auto_ptr_ref(T* p): pointee(p) {}
};

template <class T>
class my_auto_ptr
{
    public:
        explicit my_auto_ptr(T* p=NULL):pointee(p) {
            cout<<"my_auto_ptr(T* p=NULL)"<<pointee<<endl;
        }
        template <class U>
            my_auto_ptr(my_auto_ptr<U>& rhs):pointee(rhs.release()){
                cout<<"my_auto_ptr(my_auto_ptr<U>& rhs)"<<pointee<<endl;
            }
        ~my_auto_ptr()
        {
            cout<<"~my_auto_ptr():"<<pointee<<endl;
            if(pointee)
            {
                delete pointee;
                pointee=NULL;
            }
        }

        T* release()
        {
            T* tmp=this->pointee;

            this->pointee=NULL;
            return tmp;
        }

        template<class U>
        void reset(U* rp)
        {
            if(pointee!=rp)
            {
                delete this->pointee;
                pointee=rp;
            }
        }

        T& operator*()const{ return *pointee;}
        T* operator->()const{ return pointee;}
        T* get() const {return pointee;}

        template <class U>
            my_auto_ptr<T>& operator=(my_auto_ptr<U>& rhs)
            {
                reset(rhs.release());
                return *this;
            }

        my_auto_ptr& operator=(my_auto_ptr& rhs)
        {
            reset(rhs.release());
            return *this;
        }

        my_auto_ptr(auto_ptr_ref<T> __ref): pointee(__ref.pointee) {
            cout<<"my_auto_ptr(auto_ptr_ref<T> __ref)"<<endl;
        }

        my_auto_ptr&
            operator=(auto_ptr_ref<T> __ref)
            {
                cout<<"my_auto_ptr& operator=(auto_ptr_ref<T> __ref)"<<endl;

                if (__ref.pointee!= pointee)
                {
                    delete pointee;
                    pointee= __ref.pointee;
                }
                return *this;
            }

        template<typename _Tp1>
            operator auto_ptr_ref<_Tp1>() throw()
            { 
                cout<<"template<typename _Tp1> operator auto_ptr_ref<_Tp1>() throw()"<<endl;
                return auto_ptr_ref<_Tp1>(this->release());
            }

        template<typename _Tp1>
            operator my_auto_ptr<_Tp1>() throw()
            { 
                cout<<"template<typename _Tp1>operator my_auto_ptr<_Tp1>() throw()"<<endl;
                return my_auto_ptr<_Tp1>(this->release());
            }

    private:
        T* pointee;
};

template<> 
class my_auto_ptr<void>
{
    public:
        typedef void element_type;
};

//测试自动销毁
void func()
{
    cout<<"func"<<endl;
    my_auto_ptr<string> ps(new string("test"));
    cout << *ps <<endl;
    cout<< ps->size()<<endl;
}

//测试返回为 my_auto_ptr<int>
my_auto_ptr<int> func1()
{
    my_auto_ptr<int> a(new int);
    *a=12;

    return a;
}

int main()
{
    my_auto_ptr<int> p;
    my_auto_ptr<int> p2;
    my_auto_ptr<int> p3;
    my_auto_ptr<void> p4; //test void
    my_auto_ptr<void> p5;

    std::cout << "before new" <<std::endl;
    p = my_auto_ptr<int> (new int);
    std::cout << "after new" <<std::endl;

    std::cout << "before func" <<std::endl;
    func();
    std::cout << "after func" <<std::endl;

    std::cout << "before func2" <<std::endl;
    p2=func1(); 
    std::cout << "after func2" <<std::endl;

    *p = 11;
    p2 = p;
    std::cout << "p2 points to " << *p2 << '\n';

    p4=p5;

    return 0;
}

lawrencechi@LawrencechideMacBook-Pro ~/temp/test » g++ my_auto_ptr.cpp
lawrencechi@LawrencechideMacBook-Pro ~/temp/test » ./a.out
my_auto_ptr(T* p=NULL)0x0
my_auto_ptr(T* p=NULL)0x0
my_auto_ptr(T* p=NULL)0x0
before new
my_auto_ptr(T* p=NULL)0x7fdd6bd00000
template<typename _Tp1> operator auto_ptr_ref<_Tp1>() throw()
my_auto_ptr& operator=(auto_ptr_ref<T> __ref)
~my_auto_ptr():0x0
after new
before func
func
my_auto_ptr(T* p=NULL)0x7fdd6bd00010
test
4
~my_auto_ptr():0x7fdd6bd00010
after func
before func2
my_auto_ptr(T* p=NULL)0x7fdd6bd00030
template<typename _Tp1> operator auto_ptr_ref<_Tp1>() throw()
my_auto_ptr& operator=(auto_ptr_ref<T> __ref)
~my_auto_ptr():0x0
after func2
p2 points to 11
~my_auto_ptr():0x0
~my_auto_ptr():0x7fdd6bd00000
~my_auto_ptr():0x0

参考资料

http://cpptips.com/auto_ptr_ref


stl iterator 学习笔记

文章目标

解决下面几个问题:
1.什么是stl迭代器,每一种数据结构都需要自定义自己的迭代器,那么应该如何自定义符合stl规范的迭代器;
2.每一种数据结构都需要定义自己的迭代器,为什么指针不需要;
3.迭代器的具体实现细节

引入代码

stl里面的distance函数是用来计算两个迭代器之间的距离,他的声明原型如下:

/**
 *  @brief A generalization of pointer arithmetic.
 *  @param  first  An input iterator.
 *  @param  last  An input iterator.
 *  @return  The distance between them.
 *
 *  Returns @c n such that first + n == last.  This requires that @p last
 *  must be reachable from @p first.  Note that @c n may be negative.
 *
 *  For random access iterators, this uses their @c + and @c - operations
 *  and are constant time.  For other %iterator classes they are linear time.
*/
template<typename _InputIterator>
  inline typename iterator_traits<_InputIterator>::difference_type
  distance(_InputIterator __first, _InputIterator __last);
  {
    // concept requirements -- taken care of in __distance
    return std::__distance(__first, __last,
             std::__iterator_category(__first));
  }

但是,如下的代码却能够正常编译执行:

#include <stdio.h>
#include <iterator>

int main ()
{
    int pool[10]={0};
    int* pBegin=pool;
    int* pEnd=&pool[9];

    //difference_type distance(_InputIterator __first, _InputIterator __last)
    int diff=std::distance(pBegin,pEnd);

    printf("pBegin:%p,pEnd:%p,diff %d\n",pBegin,pEnd,diff);

    return 0;
}

/*
out put
chiyl@centos65 ~/Compile/test ±master⚡ » ./test
pBegin:0x7fff88f3faf0,pEnd:0x7fff88f3fb14,diff 9
*/

同样的,stl中的其他内建函数、算法都能够正常处理指针并得到正确的运行结果。
几个问题:
1.为什么内建函数 distance能够识别出 指针迭代器?
2.函数原型中的difference_type__iterator-categoryiterator_traits有什么作用?

迭代器定义

在源码中发现iterator的类型如下:

/**
 *  @brief  Common %iterator class.
 *
 *  This class does nothing but define nested typedefs.  %Iterator classes
 *  can inherit from this class to save some work.  The typedefs are then
 *  used in specializations and overloading.
 *
 *  In particular, there are no default implementations of requirements
 *  such as @c operator++ and the like.  (How could there be?)
*/
template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
         typename _Pointer = _Tp*, typename _Reference = _Tp&>
  struct iterator
  {
    /// One of the @link iterator_tags tag types@endlink.
    typedef _Category  iterator_category;
    /// The type "pointed to" by the iterator.
    typedef _Tp        value_type;
    /// Distance between iterators is represented as this type.
    typedef _Distance  difference_type;
    /// This type represents a pointer-to-value_type.
    typedef _Pointer   pointer;
    /// This type represents a reference-to-value_type.
    typedef _Reference reference;
  };

明显,如果想要定义一个迭代器,必须实现迭代器的5个特性,分别是 iterator_categoryvalue_typedifference_typepointerreference。这些特性在上面的 distance函数原型中可以看到。

iterator_category

iterator_category的值是5个类,定义成类是为了便于编译器在编译时候进行精确的算法匹配(如果定义成枚举类型就没有这个优点了)。

/**
 *  @defgroup iterator_tags Iterator Tags
 *  These are empty types, used to distinguish different iterators.  The
 *  distinction is not made by what they contain, but simply by what they
 *  are.  Different underlying algorithms can then be used based on the
 *  different operations supported by different iterator types.
*/
//@{ 
///  Marking input iterators.
struct input_iterator_tag { };

///  Marking output iterators.
struct output_iterator_tag { };

/// Forward iterators support a superset of input iterator operations.
struct forward_iterator_tag : public input_iterator_tag { };

/// Bidirectional iterators support a superset of forward iterator
/// operations.
struct bidirectional_iterator_tag : public forward_iterator_tag { };

/// Random-access iterators support a superset of bidirectional
/// iterator operations.
struct random_access_iterator_tag : public bidirectional_iterator_tag { };
//@}

对于新类型,例如vector,list,map,重新定义iterator是没有什么问题,对于引子中的指针,编译器是如何得知这5个类别? stl 加多了一个萃取层进行处理这种问题,这就是 iterator_traits的作用。

iterator_traits

算法需要查询iterator的特性时候,通过 iterator_traits查询,这样对于指针这一类自带类型就能够通过 特化定义他们的类型。
萃取的使用方法在distance的实现中就看到了。
iterator_traits对于指针的特化实现:

 template<typename _Tp>
   struct iterator_traits<_Tp*>
   {
     typedef random_access_iterator_tag iterator_category;
     typedef _Tp                         value_type;
     typedef ptrdiff_t                   difference_type;
     typedef _Tp*                        pointer;
     typedef _Tp&                        reference;
   };

自定义迭代器和萃取

根据上面的原理,自己实现一个迭代器和萃取层。

#include <stdio.h>
#include <typeinfo>

#define ptrdiff_t void*

template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
    typename _Pointer = _Tp*, typename _Reference = _Tp&>
    struct myiterator
{
    /// One of the @link iterator_tags tag types@endlink.
    typedef _Category  iterator_category;
    /// The type "pointed to" by the iterator.
    typedef _Tp        value_type;
    /// Distance between iterators is represented as this type.
    typedef _Distance  difference_type;
    /// This type represents a pointer-to-value_type.
    typedef _Pointer   pointer;
    /// This type represents a reference-to-value_type.
    typedef _Reference reference;
};

class CCateroy{};
class CCFoward{};
class CCRandom{};

template<typename _Iterator>
struct myiterator_traits
{
    typedef typename _Iterator::iterator_category iterator_category;
    typedef typename _Iterator::value_type        value_type;
    typedef typename _Iterator::difference_type   difference_type;
    typedef typename _Iterator::pointer           pointer;
    typedef typename _Iterator::reference         reference;
};

template<typename _Tp>
struct myiterator_traits<_Tp*>
{
    typedef CCRandom iterator_category;
    typedef _Tp                         value_type;
    typedef ptrdiff_t                   difference_type;
    typedef _Tp*                        pointer;
    typedef _Tp&                        reference;
};

template<typename _Tp>
void print_iterator_traits(_Tp t)
{
    typedef typename myiterator_traits<_Tp>::iterator_category iterator_category;
    typedef typename myiterator_traits<_Tp>::value_type value_type;
    typedef typename myiterator_traits<_Tp>::difference_type difference_type;
    typedef typename myiterator_traits<_Tp>::pointer pointer;
    typedef typename myiterator_traits<_Tp>::reference reference;

    printf("==========\n");
    printf("iteator : %s\n",typeid(_Tp).name());
    printf("sizeof(iteator): %lu\n",sizeof(_Tp));
    printf("iterator::category=%s\n",typeid(iterator_category).name());
    printf("iterator::value_type=%s\n",typeid(value_type).name());
    printf("iterator::difference_type=%s\n",typeid(difference_type).name());
    printf("iterator::pointer=%s\n",typeid(pointer).name());
    printf("iterator::reference=%s\n",typeid(reference).name());
}

int main ()
{
    int* pInt=NULL;
    double* pdou=NULL;
    CCateroy* pCC=NULL;
    int a=0;
    myiterator<CCateroy,int> iter;
    myiterator<CCFoward,int> foward_iter;

    printf("iterator::category=%s\n",typeid(myiterator_traits<int*>::iterator_category).name());
    print_iterator_traits(pInt);
    print_iterator_traits(pdou);
    print_iterator_traits(pCC);
    //print_iterator_traits(a);
    print_iterator_traits(iter);
    print_iterator_traits(foward_iter);

    return 0;
}

资料

c++手册中关于迭代器的描述:
http://www.cplusplus.com/reference/iterator/

gcc 4.9.3 中iterator 代码路径:

gcc-4.9.3/libstdc++-v3/include/std/iterator
gcc-4.9.3/libstdc++-v3/include/std/bits/c++config.h
gcc-4.9.3/libstdc++-v3/include/std/bits/stl_iterator_base_types.h
gcc-4.9.3/libstdc++-v3/include/std/bits/stl_iterator_base_funcs.h
gcc-4.9.3/libstdc++-v3/include/std/bits/stl_iterator.h
gcc-4.9.3/libstdc++-v3/include/std/ostream
gcc-4.9.3/libstdc++-v3/include/std/istream
gcc-4.9.3/libstdc++-v3/include/std/bits/stream_iterator.h
gcc-4.9.3/libstdc++-v3/include/std/bits/streambuf_iterator.h
gcc-4.9.3/libstdc++-v3/include/std/bits/range_access.h