STL之空间配置器详细讲解

秒速五厘米 2022-05-30 23:24 169阅读 0赞

[需要搞清楚空间配置器之前必须分清楚C++中各种内存分配和释放的区别？][C]

大型开源项目一般喜欢加上一个自己喜欢的内存池，哈哈 ，貌似可以解决一些内存碎片的功能，但是不知道效果大不大。到目前为止，我知道libevent里面没有使用内存池但是自己可以实现一个，给它使用；**Nignx里面自己实现了内存池**。

[可以先看看自己如何实现一个内存池功能][Link 1]

SGI含有两个空间配置器类，`std::allocator`内存分配类符合标准，但是仅仅是对`operator new`和`operator delete`简单封装一下而已；其次是SGI特殊的内存分配器`std::alloc`,其中实现采用了内存池，对于分配大量小容量的对象，可以大大减少内存碎片。下面我们将详细分析这两个内存分配功能如何实现，学习大神在最重要的内存分配方面是如何完成的。

# std::allocator #

template <class T>
    inline T* allocate(ptrdiff_t size, T*) {
       //size代表T的个数
        set_new_handler(0);
        T* tmp = (T*)(::operator new((size_t)(size * sizeof(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);
    }

模板内联内存释放函数，直接调用全局的`operator delete`释放对应的内存。

//allocator模板类，T代表分配的类型
    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 difference_type;
    
        pointer allocate(size_type n) 
        { 
            return ::allocate((difference_type)n, (pointer)0);
        }
    
        void deallocate(pointer p)
        { 
            ::deallocate(p); 
        }
    
        pointer address(reference x) 
        { 
            return (pointer)&x; 
        }
    
        const_pointer const_address(const_reference x) 
        { 
            return (const_pointer)&x; 
        }
        size_type init_page_size() 
        { 
            return max(size_type(1), size_type(4096/sizeof(T))); 
        }
        size_type max_size() const 
        { 
            return max(size_type(1), size_type(UINT_MAX/sizeof(T))); 
        }
    };

分配内存的简单封装类，实现功能超级简单，就是分配内存和释放内存。这里因为没有设计所谓的内存池所以当大量分配小内存块时候增大了极大可能产生内存碎片的过程，可能导致后期内存使用速度减慢的。

# std::alloc #

众所周知，对于一个类对象内存的分配，包括了内存空间分配和对象的构造两步；类对象内存的的释放，包括了对象的析构和内存空间的释放。为此STL将两阶段分开了，写到了不同的头文件中，实现起来也没有那么复杂。其中`stl_alloc.h`对应内存空间的分配和释放，`stl_construct.h`对应对象的构造和析构而已。实现起来超级简单。下面先简单讲解对象的构造和析构头文件。

## 1、stl\_construct.h 对应对象的构造和析构 ##

#include <new.h>//欲使用placement new。
    
    //版本1
    template <class T1, class T2>
    inline void construct(T1* p, const T2& value) {
      new (p) T1(value);
      //在分配好的内存中，重新构建对象，p指向分配好的内存，然后重新创建T1，通过T2初始化。
      //并调用T1::T1(value)构造函数
    }
    template <class T>
    inline void destroy(T* pointer) {
        pointer->~T();
    }//直接调用对象里面的析构函数而已
    
    //版本2，接受迭代器进行析构范围对象
    template <class ForwardIterator>
    inline void destroy(ForwardIterator first, ForwardIterator last) {
      __destroy(first, last, value_type(first));
    }
    //接受迭代器，根据萃取出元素的不同类型，找出destory的最佳措施。
    //value_type(first)原型为在`stl_iterator.h`，可以获取迭代器指向值的类型，依据类型选择不同的析构函数，后面有详细讲解，很容易理解，一定要耐心看下去，绝对不复杂，很合理。
    
    template <class ForwardIterator, class T>
    inline void __destroy(ForwardIterator first, ForwardIterator last, T*) {
      typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
      __destroy_aux(first, last, trivial_destructor());
    }
    //萃取对象中是否含有有用的析构函数，依据此参数重载，然后调用不同的析构函数has_trivial_destructor，
    
    //这是没有无用的析构函数，也就是析构函数有用，
    template <class ForwardIterator>
    inline void
    __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
       //循环中调用每一个的析构函数
      for ( ; first < last; ++first)
        destroy(&*first);//通过析构函数释放
    }
    
    //这是有无用的析构函数，也就是析构函数没有用，例如原始指针指向对象，那么析构函数不做事
    template <class ForwardIterator> 
    inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}//析构函数没作用，不做什么
    
    //迭代器为char*和wchar_t的特化版本
    inline void destroy(char*, char*) {}
    inline void destroy(wchar_t*, wchar_t*) {}

这个头文件实现很简单，首先因为需要在已经分配的内存上面构造对应的对象，所以需要使用`placement new`，因此必须首先包含`<new.h>`，上面注释以及解释清楚了所实现的功能。下面用个框图解释。  
![这里写图片描述][70]  
STL规定配置器必须拥有`construct()`和`destroy()`这两个成员函数。`construct()`接收指针p和一个初值value用于在指针的位置构造对象。`destroy()`有两个版本，第一个接收一个指针，直接调用析构函数即可。第二个接收first和last两个迭代器准备将\[first , last)范围内对象全部析构，然后通过`value_type`找出对象是否含有无用的析构函数，若无用，那么析构函数直接退出，否则调用第一个版本的函数。

## 2、stl\_alloc.h 内存空间的分配和释放 ##

内部使用malloc在堆中申请内存，其中制造了一个内存池，可以减少小型区块过多而造成的内存碎片问题。

### 1、内存分配第一级部分 ###

一级内存分配直接使用malloc和freee分配及释放内存。相关的代码实现起来也很简单。

/*******************第一级内存配置器模板***********************/
    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)
        {
            void *result = malloc(n);//malloc搞起来
            if (0 == result) result = oom_malloc(n);//分配失败，使用传进来的函数
            return result;
        }
    
        static void deallocate(void *p, size_t /* n */)
        {
            free(p);//直接使用free释放空间
        }
    
        static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
        {
            void * result = realloc(p, new_sz);//realloc搞起来，扩大或缩小原分配内存空间。
            if (0 == result) result = oom_realloc(p, new_sz);
            return result;
        }
        /* 参数：void (*f)() 返回：void (*f)() 所以合起来，这个函数看起来比较复杂，set_new_handler的标准实现形式。 */
        static void (* set_malloc_handler(void (*f)() ) )()//回调函数，将自己的函数传进来,传进函数指针，返回函数指针，所以看起来比较复杂
        {
            void (* old)() = __malloc_alloc_oom_handler;
            __malloc_alloc_oom_handler = f;
            return(old);
        }
    
    };

上面代码是第一级内存分配器，其实就是简单的封装了一下malloc和free。但是**代码部分必须注意，首先成员全部是静态的，那么也就说明可以直接通过类调用成员函数而无需定义对象。**要点：`oom_malloc和oom_realloc`是指针函数，用来处理堆内存不足的情况。`__malloc_alloc_oom_handler`是函数指针，相当于回调函数，用户可以通过类成员函数`set_malloc_handler`设定此函数指针，当在内存分配不足的时候，此函数将被调用。

static void (* set_malloc_handler(void (*f)() ) )()//回调函数，将自己的函数传进来,传进函数指针，返回函数指针，所以看起来比较复杂
        {
            void (* old)() = __malloc_alloc_oom_handler;
            __malloc_alloc_oom_handler = f;
            return(old);
        }

这个成员函数貌似很复杂，其实我们可以用typedef简化形式。

typedef void(* Hander)();
    Hander set_malloc_handler(Hander f)//简化版本
        {
            Hander older = __malloc_alloc_oom_handler;
            __malloc_alloc_oom_handler = f;
            return(old);
        }

下面看看各个静态成员的定义：

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(n);//再次尝试分配内存。
            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);
        }
    }

在`oom_malloc`中当`malloc`失败的时候，也就堆中内存不足时候，通过此函数来榨取内存，首先会调用用户注册的回调函数`__malloc_alloc_oom_handler()`看是否可以释放处对应的内存，然后继续尝试`malloc`。在`oom_realloc`中过程完全一样，不用赘述。

最后一句代码最关键，将模板实例，定义了一个类，在后面第二级分配器里面用到`malloc_alloc`类。

typedef __malloc_alloc_template<0> malloc_alloc;//定义第一级分配器类

### 2、内存分配第二级内存池部分 ###

STL规定所申请的内存块大小小于128字节时，那么就使用内存池。**内存池实际上就是内部维护了16个自由链表，预先已经分配好了，当需要从内存池中取内存时候，直接从对应链表取出即可；当释放内存到内存池时候，直接将内存插入链表即可。**每个链表中节点分别占用8、16、24、32、40、48、52、64、72、80、88、96、104、112、120、128字节。于是内存池的布局如同下图一样，相当的优雅、简单、美丽、大方。  
![这里写图片描述][70 1]  
当然每个链表的节点个数会根据实际使用进行动态调整，当某个链表节点个数不够，那么STL会再次从堆中申请，然后插入对应的链表中。下面从代码的角度仔细分析，STL是如何维护一个内存池的以及内存池节点个数是如何变化的。

enum {
       __ALIGN = 8};//8字节对齐
        enum {
       __MAX_BYTES = 128};//上限
        enum {
       __NFREELISTS = __MAX_BYTES/__ALIGN};//free_list数目
                                //为什么需要用枚举，在效率编程c++里面说的很清楚
      static size_t ROUND_UP(size_t bytes) {
            return ( ( (bytes) + __ALIGN-1) & ~(__ALIGN - 1) );
      }//将bytes上调至8的倍数

首先定义枚举常量。也就说小于128字节的区域块都是进行8字节对齐的，例如对象只需要4字节，那么进行8字节对齐后，依旧给其分配8字节空间，虽然浪费了4字节空间，但是这样在内存池的管理上提供了很大的方便。`ROUND_UP`用于返回8的倍数字节。

union obj {
       //free_list节点构造
            union obj * free_list_link;
            char client_data[1];    /* The client sees this. */
      };

这里定义了链表节点的信息。为什么定义为联合体了，这完全是为了节约内存，实际上，节点中并不需要存放用户自定义的数据，仅仅需要存放下个节点的地址即可。并且这个节点仅仅占用4字节，也就是说加入分配了一个8字节的节点，那么仅仅只有前4字节存储了下一个节点的信息，后面4字节并没有使用。  
![这里写图片描述][70 2]

static obj * __VOLATILE free_list[__NFREELISTS]; //16个free_lists，指针数组，free_list是一个指针指向的数据类型也是指针
      static  size_t FREELIST_INDEX(size_t bytes) {
            return (((bytes) + __ALIGN-1)/__ALIGN - 1);
      }//依据bytes得到对应的链表。

这里首先声明16个指针数组，然后定义获取数组索引的函数，相当简单。这里对应的变量和结构都分析完了，然后可以分析具体的操作函数了。  
前面定义第一级分配器对应的分配大于128字节的内存，在前面已经详细分析了过程。  
以下仔细分析第二级内存池模板：

template <bool threads, int inst>
    class __default_alloc_template {
    private:
        enum {__ALIGN = 8};//8字节对齐
        enum {__MAX_BYTES = 128};//上限
        enum {__NFREELISTS = __MAX_BYTES/__ALIGN};//free_list数目
    
      static size_t ROUND_UP(size_t bytes) {
            return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
      }//将bytes上调至8的倍数
    __PRIVATE:
      union obj {
       //free_list节点构造
            union obj * free_list_link;
            char client_data[1];    /* The client sees this. */
      };
    private:
    
        static obj * __VOLATILE free_list[__NFREELISTS]; //16个free_lists，指针数组，free_list是一个指针指向的数据类型也是指针
      static  size_t FREELIST_INDEX(size_t bytes) {
            return (((bytes) + __ALIGN-1)/__ALIGN - 1);
      }//根据区块大小，决定使用第几个free_list。
    
      static void *refill(size_t n);
      static char *chunk_alloc(size_t size, int &nobjs);//配置一大块空间，可容纳n个objs的大小的size区块
    
      static char *start_free;//内存池起始
      static char *end_free;//内存池结束
      static size_t heap_size;//堆大小
    
    public:
      static void * allocate(size_t n)
      {
        obj * __VOLATILE * my_free_list;
        obj * __RESTRICT result;
    
        if (n > (size_t) __MAX_BYTES) {
       //大于128字节，调用第一级配置器
            return(malloc_alloc::allocate(n));
        }
        my_free_list = free_list + FREELIST_INDEX(n);//寻找16个free list中适当的一个
    
        result = *my_free_list;//取出链表首节点
        if (result == 0) {
       //如果对应链表为空，准备重新增加链表节点
            void *r = refill(ROUND_UP(n));
            return r;
        }
        *my_free_list = result -> free_list_link;//free_list[n]中更改为下一个节点地址
        return (result);//将第一个节点地址返回给外部使用
      };
    
     //释放内存，
      static void deallocate(void *p, size_t n)
      {
        obj *q = (obj *)p;
        obj * __VOLATILE * my_free_list;
    
        if (n > (size_t) __MAX_BYTES) {
            malloc_alloc::deallocate(p, n);
            return;
        }
        my_free_list = free_list + FREELIST_INDEX(n);//寻找对应freelist
        q -> free_list_link = *my_free_list;//调整freelist，回收区块
        *my_free_list = q;
      }
    
      static void * reallocate(void *p, size_t old_sz, size_t new_sz);//声明成员函数
    
    };

这是内存池模板部分，这里声明以及定义了关键的操作函数，注意这里成员全部都是静态的，也就是可以直接通过类访问成员函数。使得后期更加方便，当然内存池也必须是静态的，因为内存池肯定是一个单例模式，整个程序运行应该仅仅只有一个内存池。下面看看关键函数的定义：

//从堆中分配对应的内存，这里讲内存榨干操作处理，具体实现细节暂时不分析。
    template <bool threads, int inst>
    char*
    __default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs)
    {
        char * result;
        size_t total_bytes = size * nobjs;
        size_t bytes_left = end_free - start_free;//内存池剩余空间
    
        if (bytes_left >= total_bytes) {
       //内存池可以存储所有obj
            result = start_free;
            start_free += total_bytes;//更新，以便下次配置
            return(result);
        } else if (bytes_left >= size) {
       //内存池可以存储部分obj
            nobjs = bytes_left/size;//可存储obj的个数
            total_bytes = size * nobjs;//可存储的总字节
            result = start_free;//
            start_free += total_bytes;//
            return(result);
        } else {                        //内存池不够存储一个obj
            size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
    
            if (bytes_left > 0) {
                // 尝试让内存池中残余零头还有利用价值
                //首先寻找适当的free list
                obj * __VOLATILE * my_free_list =
                            free_list + FREELIST_INDEX(bytes_left);
                //调整freelist，将内存池中的残余空间编入
                ((obj *)start_free) -> free_list_link = *my_free_list;
                *my_free_list = (obj *)start_free;
            }
            //配置heap空间，增加内存池
            start_free = (char *)malloc(bytes_to_get);
            if (0 == start_free) {
       //heap空间不足，malloc失败
                int i;
                obj * __VOLATILE * my_free_list, *p;
                // Try to make do with what we have. That can't
                // hurt. We do not try smaller requests, since that tends
                // to result in disaster on multi-process machines.
                for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
                    my_free_list = free_list + FREELIST_INDEX(i);
                    p = *my_free_list;
                    if (0 != p) {
                        *my_free_list = p -> free_list_link;
                        start_free = (char *)p;
                        end_free = start_free + i;
                        return(chunk_alloc(size, nobjs));
                        // Any leftover piece will eventually make it to the
                        // right free list.
                    }
                }
            end_free = 0;   //如果出现意外，到处都没有内存可用了
                start_free = (char *)malloc_alloc::allocate(bytes_to_get);
                // This should either throw an
                // exception or remedy the situation. Thus we assume it
                // succeeded.
            }
            heap_size += bytes_to_get;
            end_free = start_free + bytes_to_get;
            return(chunk_alloc(size, nobjs));
        }
    }
    
    //模板中成员的定义，用于重新给链表分配空间
    template <bool threads, int inst>
    void* __default_alloc_template<threads, inst>::refill(size_t n)
    {
        int nobjs = 20;//默认每个链表含有20个节点
        char * chunk = chunk_alloc(n, nobjs);
        obj * __VOLATILE * my_free_list;
        obj * result;
        obj * current_obj, * next_obj;
        int i;
    
        if (1 == nobjs) return(chunk);
        my_free_list = free_list + FREELIST_INDEX(n);
    
        /* 将分配的内存连接成链表 */
          result = (obj *)chunk;
          *my_free_list = next_obj = (obj *)(chunk + n);
          for (i = 1; ; i++) {
            current_obj = next_obj;
            next_obj = (obj *)((char *)next_obj + n);
            if (nobjs - 1 == i) {
       //注意这里少了一个，因为第一个用于返回
                current_obj -> free_list_link = 0;
                break;
            } else {
                current_obj -> free_list_link = next_obj;
            }
          }
        return(result);//返回首节点
    }
    
    //重新分配内存
    template <bool threads, int inst>
    void*
    __default_alloc_template<threads, inst>::reallocate(void *p,
                                                        size_t old_sz,
                                                        size_t new_sz)
    {
        void * result;
        size_t copy_sz;
    
        if (old_sz > (size_t) __MAX_BYTES && new_sz > (size_t) __MAX_BYTES) {
            return(realloc(p, new_sz));
        }
        if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return(p);
        result = allocate(new_sz);
        copy_sz = new_sz > old_sz? old_sz : new_sz;
        memcpy(result, p, copy_sz);
        deallocate(p, old_sz);
        return(result);
    }
    
    //以下是静态数据成员的定义和初值设定
    template <bool threads, int inst>
    char *__default_alloc_template<threads, inst>::start_free = 0;//其实部分
    
    template <bool threads, int inst>
    char *__default_alloc_template<threads, inst>::end_free = 0;//空闲尾部
    
    template <bool threads, int inst>
    size_t __default_alloc_template<threads, inst>::heap_size = 0;//堆空间初始为空
    
    template <bool threads, int inst>
    __default_alloc_template<threads, inst> ::free_list[
    ] = {
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };//链表全部初始化为空

上述过程函数不详细讲解，就是内存池元素个数增加或者减少的过程。当分配内存大于128字节调用第一级内存，当小于128字节时候则8字节对齐后选择对应的链表分配内存。

最后通过上述模版定义了一个类

typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;

alloc是二级内存分配器的类。

下面这个模板必须十分注意，包装接口，以满足STL标准定义：

//将内存接口包装，以满足STL标准接口
    template<class T, class Alloc>
    class simple_alloc { public: static T *allocate(size_t n) { return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); } static T *allocate(void) { return (T*) Alloc::allocate(sizeof (T)); } static void deallocate(T *p, size_t n) { if (0 != n) Alloc::deallocate(p, n * sizeof (T)); } static void deallocate(T *p) { Alloc::deallocate(p, sizeof (T)); } };

当容器里面需要使用内存分配的时候，可以通过上述模板定义对象。例如vector里面这样用的。

template <class T, class Alloc = alloc>
    class vector {
                ......
                typedef simple_alloc<value_type, Alloc> data_allocator;
                .....................
    }

默认分配器是alloc，也就是内存池分配。后期就可以通过data\_allocator直接调用alloc类里面的函数，进行内存分配了。至此内存分配系统讲解完毕。

# 内存操作全局函数 #

这几个函数都是全局定义的，作用于未初始化空间上。在容器里面大量被使用。

## 1、uninitialized\_copy ##

将迭代器\[first , last)范围内的内容拷贝到result指定的区域。如果first是char *或wchar* 那么直接使用memmove拷贝即可，如果first不是上述类型，则通过辨别是否是POD类型来选择构造函数或者copy拷贝。

`uninitialized_copy`使我们能够将内存的配置和对象的构造行为分离。

/////////////////////////////copy的三个重载版本//////////////////
    template <class InputIterator, class OutputIterator>
    inline OutputIterator copy(InputIterator first, InputIterator last,
                               OutputIterator result)
    {
      return __copy_dispatch<InputIterator,OutputIterator>()(first, last, result);
    }
    
    inline char* copy(const char* first, const char* last, char* result) {
      memmove(result, first, last - first);
      return result + (last - first);
    }
    
    inline wchar_t* copy(const wchar_t* first, const wchar_t* last,
                         wchar_t* result) {
      memmove(result, first, sizeof(wchar_t) * (last - first));
      return result + (last - first);
    }
    
    
    
    /////////////__uninitialized_copy_aux的2个重载版本//////////////////
    template <class InputIterator, class ForwardIterator>
    inline ForwardIterator 
    __uninitialized_copy_aux(InputIterator first, InputIterator last,
                             ForwardIterator result,
                             __true_type) {
      return copy(first, last, result);
    }
    template <class InputIterator, class ForwardIterator>
    ForwardIterator 
    __uninitialized_copy_aux(InputIterator first, InputIterator last,
                             ForwardIterator result,
                             __false_type) {
      ForwardIterator cur = result;
      __STL_TRY {
        for ( ; first != last; ++first, ++cur)
          construct(&*cur, *first);
        return cur;
      }
      __STL_UNWIND(destroy(result, cur));
    }
    
    
    /////////////__uninitialized_copy内部调用/////////////////
    template <class InputIterator, class ForwardIterator, class T>
    inline ForwardIterator
    __uninitialized_copy(InputIterator first, InputIterator last,
                         ForwardIterator result, T*) {
      typedef typename __type_traits<T>::is_POD_type is_POD;
      return __uninitialized_copy_aux(first, last, result, is_POD());
    }
    
    
    ///////////////////uninitialized_copy三个重载版本////////////////////////
    template <class InputIterator, class ForwardIterator>
    inline ForwardIterator
      uninitialized_copy(InputIterator first, InputIterator last,
                         ForwardIterator result) {
      return __uninitialized_copy(first, last, result, value_type(result));
    }
    
    inline char* uninitialized_copy(const char* first, const char* last,
                                    char* result) {
      memmove(result, first, last - first);
      return result + (last - first);
    }
    
    inline wchar_t* uninitialized_copy(const wchar_t* first, const wchar_t* last,
                                       wchar_t* result) {
      memmove(result, first, sizeof(wchar_t) * (last - first));
      return result + (last - first);
    }

![这里写图片描述][70 3]  
上图就是函数调用关系示意图，相当的简单，清楚，清晰，明了。

## 2、uninitialized\_fill ##

将\[first , last)迭代器指定范围的内存，通过x初始化。过程同上面差不多，这里不细说。

template <class ForwardIterator, class T>
    inline void
    __uninitialized_fill_aux(ForwardIterator first, ForwardIterator last, 
                             const T& x, __true_type)
    {
      fill(first, last, x);
    }
    
    template <class ForwardIterator, class T>
    void
    __uninitialized_fill_aux(ForwardIterator first, ForwardIterator last, 
                             const T& x, __false_type)
    {
      ForwardIterator cur = first;
      __STL_TRY {
        for ( ; cur != last; ++cur)
          construct(&*cur, x);
      }
      __STL_UNWIND(destroy(first, cur));
    }
    template <class ForwardIterator, class T, class T1>
    inline void __uninitialized_fill(ForwardIterator first, ForwardIterator last, 
                                     const T& x, T1*) {
      typedef typename __type_traits<T1>::is_POD_type is_POD;
      __uninitialized_fill_aux(first, last, x, is_POD());
    
    }
    template <class ForwardIterator, class T>
    inline void uninitialized_fill(ForwardIterator first, ForwardIterator last, 
                                   const T& x) {
      __uninitialized_fill(first, last, x, value_type(first));
    }

## 3、uninitialized\_fill\_n ##

将\[first , first+n)范围内的每一个迭代器都设定为x，总共设定了n个，当时pod类型，则直接拷贝x到指定的迭代器，但是不是pod类型，那么在每一个迭代器上以x为初值进行构造。

template <class OutputIterator, class Size, class T>
    OutputIterator fill_n(OutputIterator first, Size n, const T& value) {
      for ( ; n > 0; --n, ++first)
        *first = value;
      return first;
    }//直接赋值将对应的字节给到对应的位置上。
    
    
    __uninitialized_fill_n_aux两个重载函数，依据is_POD？而重载
    template <class ForwardIterator, class Size, class T>
    inline ForwardIterator
    __uninitialized_fill_n_aux(ForwardIterator first, Size n,
                               const T& x, __true_type) {
      return fill_n(first, n, x);
    }//是POD，则可以直接按照字节拷贝
    
    template <class ForwardIterator, class Size, class T>
    ForwardIterator
    __uninitialized_fill_n_aux(ForwardIterator first, Size n,
                               const T& x, __false_type) {
      ForwardIterator cur = first;
      __STL_TRY {
        for ( ; n > 0; --n, ++cur)
          construct(&*cur, x);
        return cur;
      }
      __STL_UNWIND(destroy(first, cur));
    }//不是POD，则必须调用全局构造函数构造。
    
    //__uninitialized_fill_n根据value_type调用相应的__uninitialized_fill_n_aux
    template <class ForwardIterator, class Size, class T, class T1>
    inline ForwardIterator __uninitialized_fill_n(ForwardIterator first, Size n,
                                                  const T& x, T1*) {
      typedef typename __type_traits<T1>::is_POD_type is_POD;
      return __uninitialized_fill_n_aux(first, n, x, is_POD());
    
    }
    
    
    template <class ForwardIterator, class Size, class T>
    inline ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n,
                                                const T& x) {
      return __uninitialized_fill_n(first, n, x, value_type(first));
    }

![这里写图片描述][70 4]  
上述是`uninitialized_fill_n`对应的简单函数调用关系，重点在于理解POD类型。POD意思就是Plain Old Data，也就是标量类型以及传统的C struct类型。POD类型必须含有无用的构造函数、析构函数、拷贝构造、赋值运算符函数。因此堆POD类型可以直接进行字节拷贝初始化，而非POD类型采用最安全的做法，也就是通过对应的构造函数初始化。

[C]: http://blog.csdn.net/u010710458/article/details/79057683
[Link 1]: http://blog.csdn.net/u010710458/article/details/79234706
[70]: /images/20220531/8a566e958f4d44b48f5876a0c36e37f8.png
[70 1]: /images/20220531/ad73cd2fba274b969e44473ff97fe213.png
[70 2]: /images/20220531/5d7f20a3de45465cb6d5160088315bf7.png
[70 3]: /images/20220531/65428d3ec54b4873b1f0895a8ca126e2.png
[70 4]: /images/20220531/7b6faf8709814be680a01dfe873afcc2.png