#include <new.h>
#include <stddef.h>
#include <limits.h>
#include <iostream.h>
#include <algobase.h>

template <class T>
inline T* allocate(ptrdiff_t size,T*)
{
    //设置新句柄

    set_new_handler(0);
    T* tmp=(T*)(::operator new((size_t)(size* sizeof(T))));
    if(tmp==0)
    {
        cerr<<"out of memory"<<endl;
        exit(1);
    }
    return tmp;
}
template <class T>
inline void_deallocate(T* buffer)
{
    ::operator delete(buffer);
}
template <class T1,class T2>
inline void _construct(T1* p,const T2& value)
{
    new(p) T1(value);
}
inline void _destroy(T* ptr)
{
    ptr->~T();
}


//allocator类的基本实现

template <class T>
class allocator
{
public:
    typedef T  value_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T&      reference;
    typedef const T& const_reference;
    typedef size_t size_type;
    typedef ptrdiff_t size_type;
    //连接 allocator和U

    template <class U>
    struct rebind
    {
        typedef allocator<U> other;
    };
    //获取左值指针

    pointer allocate(size_type n,const void* hint=0)
    {
        //分配内存并初始化为0

        return _allocate((difference_type)n,(pointer)0);
    }
    void deallocate(pointer p,size_type n){_deallocate(p);}

    void address(reference x){return (pointer)&x;}

    const_pointer const_address(const_reference x)
    {
        return (const_pointer)&x;
    }
    size_type max_size() const
    {
        return size_type(UINT_MAX/sizeof(T));
    }


};

#ifndef _STL_CONSTRUCT_H
#define _STL_CONSTRUCT_H 1

#include <new>
#include <bits/move.h>
#include <ext/alloc_traits.h>

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  /**
   * Constructs an object in existing memory by invoking an allocated
   * object's constructor with an initializer.
   */
//c++11 新添加Construct函数 

#if __cplusplus >= 201103L
  template<typename _T1, typename... _Args>
    inline void
    _Construct(_T1* __p, _Args&&... __args)
    { ::new(static_cast<void*>(__p)) _T1(std::forward<_Args>(__args)...); }
#else
  template<typename _T1, typename _T2>
    inline void
    _Construct(_T1* __p, const _T2& __value)
    {
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 402. wrong new expression in [some_]allocator::construct
      ::new(static_cast<void*>(__p)) _T1(__value);
    }
#endif

  /**
   * Destroy the object pointed to by a pointer type.
   */
    //接受指针，并直接调用指针类的析构函数

  template<typename _Tp>
    inline void
    _Destroy(_Tp* __pointer)
    { __pointer->~_Tp(); }
//模板函数

  template<bool>
    struct _Destroy_aux
    {
      template<typename _ForwardIterator>
        static void
        __destroy(_ForwardIterator __first, _ForwardIterator __last)
    {
      for (; __first != __last; ++__first)
        std::_Destroy(std::__addressof(*__first));
    }
    };
//特例化函数判断对象是否含有默认构造函数，如果是则什么也不做，这样可以提高效率

  template<>
    struct _Destroy_aux<true>
    {
      template<typename _ForwardIterator>
        static void
        __destroy(_ForwardIterator, _ForwardIterator) { }
    };

  /**
   * Destroy a range of objects.  If the value_type of the object has
   * a trivial destructor, the compiler should optimize all of this
   * away, otherwise the objects' destructors must be invoked.
   */

    //销毁一系列对象。如果对象的value_type是一个默认的析构函数，编译器应该优化所有这些，否则必须调用对象的析构函数。

  template<typename _ForwardIterator>
    inline void
    _Destroy(_ForwardIterator __first, _ForwardIterator __last)
    {
        //迭代器别名

      typedef typename iterator_traits<_ForwardIterator>::value_type
                       _Value_type;

      std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
    __destroy(__first, __last);
    }

  /**
   * Destroy a range of objects using the supplied allocator.  For
   * nondefault allocators we do not optimize away invocation of 
   * destroy() even if _Tp has a trivial destructor.
   */
    //使用支持的allocator销毁一系列对象，如果没有非默认的allocators不会进行销毁函数的初始化，即便，对象含有默认构造函数

  template<typename _ForwardIterator, typename _Allocator>
    void
    _Destroy(_ForwardIterator __first, _ForwardIterator __last,
         _Allocator& __alloc)
    {
      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
      for (; __first != __last; ++__first)
    __traits::destroy(__alloc, std::__addressof(*__first));
    }

  template<typename _ForwardIterator, typename _Tp>
    inline void
    _Destroy(_ForwardIterator __first, _ForwardIterator __last,
         allocator<_Tp>&)
    {
      _Destroy(__first, __last);
    }

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
#endif

//一级适配器

template <int inst>

class __malloc_alloc_template
{
private:
    //函数指针，所代表的函数将用来处理内存不足的情况
    //oom: out of memory

    static void *oom_malloc(size_t);
    static void *oom_realloc(void*,size_t);
    static void (*__malloc_alloc_oom_handler)();

public:
    static void *allocate(size_t n)
    {
        //一级配置器必须使用malloc()

        void *result=malloc(n);
        //当无法满足需求时，改用oom_malloc()

        if(0==result) result=oom_malloc(n);
        return result;
    }
    static void deallocate(void *p,size_t)
    {
        //第一级配置器直接使用free()

        free(p);
    }
    //输入旧size和新size

    static void* reallocate(void *p,size_t,size_t new_sz)
    {
        void* result=realloc(p,new_sz);
        if(0==result) result=oom_realloc(p,new_sz);
        return result; 
    }
    //指定自己的out-of-memory handler
    
    static void (* set_malloc_handler(void(*f)()))()
    {
        //获取函数指针

        void (* old)()=__malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler=f;
        return(old); 
    }


};
//下面是用户提供的malloc_alloc函数

template <int inst>
void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)()=0;

template <int inst>
void *__malloc_alloc_template<inst>::oom_malloc(size_t n)
{
    //获取内存分配句柄函数指针

    void (*my_malloc_handler)();
    void *result;
    for(;;)
    {
        //指针指向分配函数

        my_malloc_handler=__malloc_alloc_oom_handler;
        //分配失败抛出异常

        if(0==my_malloc_handler){__THROW_BAD_ALLOC;}
        //调用处理例程，企图释放内存

        (*my_malloc_handler)();
        //再次尝试分配内存

        result=malloc();
        if(result) return(result);
    }
}
//内存调用分配不成功时，进行二次调用

template <int inst>
void * __malloc_alloc_template<inst>::oom_realloc(void *p,size_t n)
{
    void (*my_malloc_handler)();
    void *result;
    for(;;)
    {
        my_malloc_handler=__malloc_alloc_oom_handler;
        if(0==my_malloc_handler){__THROW_BAD_ALLOC;}
        //尝试调用处理例程

        (*my_malloc_handler)();
        //尝试分配内存

        result=realloc(p,n);
        if(result) return(result);
    }
}
//注意,以下参数直接将inst指定为0

typedef __malloc_alloc_template<0> malloc_alloc;

union obj{
    union obj* free_list_link;
    char client_data[1];
}

template<class T>
class auto_ptr
{
public:
    explicit auto_ptr(T *p=0):pointer(p){}
    template<class U>
    auto_ptr(auto_ptr<U>& rhs):pointee(rhs.release()){}
    ~auto_ptr(){delete pointee;}
    template<class U>
    auto_ptr<T>& operator=(auto_ptr<U>& rhs)
    {
        if(this!=&rhs) reset(rhs.release());
        return *this;
    }
    T& operator*() const {return *pointee;}
    T* operator->() const {return pointee;}
    T* get() const {return pointee;}  
private:
    T *pointee;
}

template <class Item>
struct LisIter
 {
     Item* ptr;
     ListIter(Item* p=0):ptr(p){}
     //关键操作

     Item& operator*() const {return *ptr;}
     Item* operator->() const {return ptr;}
     ListIter& operator++()
     {
        ptr=ptr->next();
        return *this;
     } 
     ListIter operator++(int)
     {
        ListIter tmp=*this;
        ++*this;
        retrun tmp;
     }
     bool operator==(const ListIter& i) const
     {
        return ptr!=i.ptr;
     }
 }; 

template <class T>
struct MyIter
{
    //内嵌类型声明

    typedef T value_type;
    T* ptr;
    MyIter(T* p=0):ptr(p){}
    T& operator*() const {return *ptr;} 
}

template <class I>
typename I::value_type func(I ite){return *ite;}

MyIter<int> ite(new int(8));
cout<<func(ite);

template <
      class Category,
      class T,
      class Distance=ptrdiff_t,
      class Pointer=T*,
      class Reference=T&
          >
struct iterator
{
  typedef Category iterator_category;
  typedef T value_type;
  typedef Distance difference_type;
  typedef Pointer pointer;
  typedef Reference reference;
  
};

//使用

std::iterator<std::forward_iterator_tag,Item> 

//源自 <stl_iterator.h>

struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag:public input_iterator_tag{};
struct bidirectional_iterator_tag:public forward_iterator_tag{};
struct random_access_iterator_tag:public bidirectional_iterator_tag{};
//迭代器封装类

template <
      class Category,
      class T,
      class Distance=ptrdiff_t,
      class Pointer=T*,
      class Reference=T&
          >
struct iterator
{
  typedef Category iterator_category;
  typedef T value_type;
  typedef Distance difference_type;
  typedef Pointer pointer;
  typedef Reference reference;
  
};
//traits

template <class Iterator>
struct iterator_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;
}
//为原生指针而设计的traits偏特化版

template <class T>
struct iteraror_traits<T*>
{
    typedef random_access_iterator_tag iterator_category;
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef T& reference;
};
...