back_insert_iterator源码分析

gcc 4.1.2 版本的 back_insert_iterator

  // 24.4.2.2.1 back_insert_iterator
  /**
   *  @brief  Turns assignment into insertion.
   *
   *  These are output iterators, constructed from a container-of-T.
   *  Assigning a T to the iterator appends it to the container using
   *  push_back.
   *
   *  Tip:  Using the back_inserter function to create these iterators can
   *  save typing.
  */
  template<typename _Container>
    class back_insert_iterator
    : public iterator<output_iterator_tag, void, void, void, void>
    {
    protected:
      _Container* container;

    public:
      /// A nested typedef for the type of whatever container you used.
      typedef _Container          container_type;

      // 非常巧妙的使用 explicit 限制了初始化必须传入类型，这个以后再编写类似
      // 的专用类的时候，可以参考这样的实现
      // 构造函数传入必须是一个容器
      /// The only way to create this %iterator is with a container.
      explicit
      back_insert_iterator(_Container& __x) : container(&__x) { }

      /**
       *  @param  value  An instance of whatever type
       *                 container_type::const_reference is; presumably a
       *                 reference-to-const T for container<T>.
       *  @return  This %iterator, for chained operations.
       *
       *  This kind of %iterator doesn't really have a "position" in the
       *  container (you can think of the position as being permanently at
       *  the end, if you like).  Assigning a value to the %iterator will
       *  always append the value to the end of the container.
      */
      //将赋值运算符适配成 push_back， 返回值为 back_insert_iterator 迭代器适配器
      //传入容器必须要还有 push_back接口（常用容器都是有这个接口）
      back_insert_iterator&
      operator=(typename _Container::const_reference __value)
      {
    container->push_back(__value);
    return *this;
      }

      /// Simply returns *this.
      //空操作，保证迭代器接口的完备
      back_insert_iterator&
      operator*()
      { return *this; }

      /// Simply returns *this.  (This %iterator does not "move".)
      //空操作，保证迭代器接口的完备
      back_insert_iterator&
      operator++()
      { return *this; }

      /// Simply returns *this.  (This %iterator does not "move".)
      //空操作，保证迭代器接口的完备
      back_insert_iterator
      operator++(int)
      { return *this; }
    };

C++17

C++17采用了新的设计(尚无源码，看不出实现的区别)

应用

应用时候一般是使用 back_inserter
back_inserter 的实现源码如下:

  /**
   *  @param  x  A container of arbitrary type.
   *  @return  An instance of back_insert_iterator working on @p x.
   *
   *  This wrapper function helps in creating back_insert_iterator instances.
   *  Typing the name of the %iterator requires knowing the precise full
   *  type of the container, which can be tedious and impedes generic
   *  programming.  Using this function lets you take advantage of automatic
   *  template parameter deduction, making the compiler match the correct
   *  types for you.
  */
  //创建一个临时的 back_insert_iterator 对象，执行之后就返回.
  template<typename _Container>
    inline back_insert_iterator<_Container>
    back_inserter(_Container& __x)
    { return back_insert_iterator<_Container>(__x); }

#define private public
#define protected public

#include <stdio.h>
#include <string.h>
#include <fcntl.h>
#include <unistd.h>
#include <errno.h>
#include <iostream>  
#include <typeinfo>
#include <string>

using namespace std;

//打印内存 BEGIN
inline char hdigit(int n){return "0123456789abcdef"[n&0xf];};
#define LEN_LIMIT 32
#define SUBSTITUTE_CHAR '`'
int isValidPtr(const void*p, int len)
{
    if (!p) {
        return 0;
    }
    int ret = 1;
    int nullfd = open("/dev/random", O_WRONLY);
    if (write(nullfd, p, len) < 0) {
        ret = 0;
        /* Not OK */
    }
    close(nullfd);
    return ret;
}

static const char* dumpline(char*dest, int linelen, const char*src, const char*srcend)
{
    if(src>=srcend) {
        return 0;
    }
    int i;
    unsigned long s = (unsigned long)src;
    for(i=0; i<8; i++) {
        dest[i] = hdigit(s>>(28-i*4));
    }
    dest[8] = ' ';
    dest += 9;
    if (isValidPtr(src,linelen/4)) {
      for(i=0; i<linelen/4 ; i++) {
        if(src+i<srcend) {
            dest[i*3] = hdigit(src[i]>>4);
            dest[i*3+1] = hdigit(src[i]);
            //dest[i*3+2] = ((i+1+(unsigned long)src)&3)?' ':'|';
            dest[i*3+2] = ' ';
            dest[linelen/4*3+i] = src[i] >= ' ' && src[i] < 0x7f ? src[i] : SUBSTITUTE_CHAR;
        }else{
            dest[i*3] = dest[i*3+1] = dest[i*3+2] = dest[linelen/4*3+i] = '|';
        }
      }
    } else {
      strcpy(dest, "***cannot read***");
      i = linelen/4;
    }
    dest[linelen] = 0;
    return src+i;
}

void hexdump( const void *addr, unsigned len)
{
    int linelen=80;
    static char _buf[128];
    char*buf = _buf;//(char*)alloca(linelen+1); // alloca() causes the initialization to fail!!!!
    buf[linelen]=0;
    const char*start = (char*)addr;
    const char*cur = start;
    const char*end = start+len;
    while(!!(cur = dumpline(buf,linelen,cur,start+len)))
    {
        //write_log( filename, funcname, lineno, "%s",buf);
        printf("0x%s \n",buf);
    }
}
//打印内存 END 

void print_string_inner_type()
{
    //type 
    //string 里面用到的变量
    cout<<"typeid string::traits_type "<<typeid(string::traits_type).name()<<" sizeof:"<<sizeof(string::traits_type)<<endl;
    cout<<"typeid string::value_type "<<typeid(string::value_type).name()<<" sizeof:"<<sizeof(string::value_type)<<endl;
    cout<<"typeid string::allocator_type "<<typeid(string::allocator_type).name()<<" sizeof:"<<sizeof(string::allocator_type)<<endl;
    cout<<"typeid string::size_type "<<typeid(string::size_type).name()<<" sizeof:"<<sizeof(string::size_type)<<endl;
    cout<<"typeid string::difference_type "<<typeid(string::difference_type).name()<<" sizeof:"<<sizeof(string::difference_type)<<endl;
    cout<<"typeid string::reference "<<typeid(string::reference).name()<<" sizeof:"<<sizeof(string::reference)<<endl;
    cout<<"typeid string::const_iterator "<<typeid(string::const_iterator).name()<<" sizeof:"<<sizeof(string::const_iterator)<<endl;
    cout<<"typeid string::_Rep "<<typeid(string::_Rep).name()<<" sizeof:"<<sizeof(string::_Rep)<<endl;

    //variable
    string a("hello");
    string b(a);
    string::_Rep* st_rep;
    st_rep = a._M_rep();
    st_rep->_M_length;
    st_rep->_M_capacity;
    st_rep->_M_refcount;
    a._M_dataplus;
    a._M_dataplus._M_p;

    cout<<"a.c_str():"<<endl;
    hexdump(a.c_str(),a.length()+1);
    cout<<"_M_rep:"<<endl;
    hexdump(a._M_rep(),a.length()+sizeof(string::_Rep));

    printf("a._M_dataplus:%p\n",&a._M_dataplus);
    printf("a._M_dataplus._M_p:%p\n",a._M_dataplus._M_p);
    printf("a._M_rep():%p\n",st_rep);

    //b是通过a 拷贝构造生成,b指向的内存地址和a一样,不过 _M_refcount 的值会加一
    cout<<"b._M_rep:"<<endl;
    hexdump(b._M_rep(),b.length()+sizeof(string::_Rep));

    //b重新赋值，不在是a的引用，因此b指向地址和a不一样， a 的_M_refcount 会减一
    b="aaa";
    cout<<"After operator= a._M_rep:"<<endl;
    hexdump(a._M_rep(),a.length()+sizeof(string::_Rep));
    cout<<"After operator= b._M_rep:"<<endl;
    hexdump(b._M_rep(),b.length()+sizeof(string::_Rep));

    //未赋值的string对象，不会调用构造函数，会指向静态内存块的地址 string::_Rep::_S_empty_rep_storage
    string e,f;
    cout<<"string::_Rep::_S_empty_rep_storage[]:"<<endl;
    hexdump(string::_Rep::_S_empty_rep_storage,20);
    cout<<"e:"<<endl;
    hexdump(e._M_rep(),e.length()+sizeof(string::_Rep));
    cout<<"f:"<<endl;
    hexdump(f._M_rep(),f.length()+sizeof(string::_Rep));

    //static
    //string中用到的静态值
    cout<<"static string::_Rep::_S_max_size 0x"<<hex<<string::_Rep::_S_max_size<<" sizeof:"<<sizeof(string::_Rep::_S_max_size)<<endl;
    cout<<"static string::_Rep::_S_terminal 0x"<<hex<<string::_Rep::_S_terminal<<" sizeof:"<<sizeof(string::_Rep::_S_terminal)<<endl;
}

void test_nagetive_idx()
{
    //a[-1]
    char c[]={"abcdefgh"};
    char* d=&c[2];

    cout<<"c:"<<endl;
    hexdump(c,sizeof(c));

    printf("&d[-1]=%p,d[-1]=%c\n",&d[-1],d[-1]);
}

int main(int argc,char* argv[])
{
    print_string_inner_type();
    test_nagetive_idx();

    return 0;
}

chiyl@centos65 ~/Compile/test » make
g++ -g main.cpp -o test
chiyl@centos65 ~/Compile/test » ./test
typeid string::traits_type St11char_traitsIcE sizeof:1
typeid string::value_type c sizeof:1
typeid string::allocator_type SaIcE sizeof:1
typeid string::size_type m sizeof:8
typeid string::difference_type l sizeof:8
typeid string::reference c sizeof:1
typeid string::const_iterator N9__gnu_cxx17__normal_iteratorIPKcSsEE sizeof:8
typeid string::_Rep NSs4_RepE sizeof:24
a.c_str():
0x0220d028 68 65 6c 6c 6f 00 ||||||||||||||||||||||||||||||||||||||||||hello`||||||||||||||
_M_rep:
0x0220d010 05 00 00 00 00 00 00 00 05 00 00 00 00 00 00 00 01 00 00 00 ````````````````````
0x0220d024 00 00 00 00 68 65 6c 6c 6f |||||||||||||||||||||||||||||||||````hello|||||||||||
a._M_dataplus:0x7fff90869ae0
a._M_dataplus._M_p:0x220d028
a._M_rep():0x220d010
b._M_rep:
0x0220d010 05 00 00 00 00 00 00 00 05 00 00 00 00 00 00 00 01 00 00 00 ````````````````````
0x0220d024 00 00 00 00 68 65 6c 6c 6f |||||||||||||||||||||||||||||||||````hello|||||||||||
After operator= a._M_rep:
0x0220d010 05 00 00 00 00 00 00 00 05 00 00 00 00 00 00 00 00 00 00 00 ````````````````````
0x0220d024 00 00 00 00 68 65 6c 6c 6f |||||||||||||||||||||||||||||||||````hello|||||||||||
After operator= b._M_rep:
0x0220d040 03 00 00 00 00 00 00 00 03 00 00 00 00 00 00 00 00 00 00 00 ````````````````````
0x0220d054 00 00 00 00 61 61 61 |||||||||||||||||||||||||||||||||||||||````aaa|||||||||||||
string::_Rep::_S_empty_rep_storage[]:
0x00602be0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ````````````````````
e:
0x00602be0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ````````````````````
0x00602bf4 00 00 00 00 ||||||||||||||||||||||||||||||||||||||||||||||||````||||||||||||||||
f:
0x00602be0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ````````````````````
0x00602bf4 00 00 00 00 ||||||||||||||||||||||||||||||||||||||||||||||||````||||||||||||||||
static string::_Rep::_S_max_size 0x3ffffffffffffff9 sizeof:8
static string::_Rep::_S_terminal 0x sizeof:1
c:
0x90869af0 61 62 63 64 65 66 67 68 00 |||||||||||||||||||||||||||||||||abcdefgh`|||||||||||
&d[-1]=0x7fff90869af1,d[-1]=b

解决问题

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

文章目标

解决下面几个问题：
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-category、iterator_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_category 、value_type、difference_type、pointer、reference。这些特性在上面的 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