1 JJ::allocator——STL源碼解析

2 配置器std::alloc

2.1 二級配置器——__default_alloc_template

2.1.1 區塊大小和空閑鍊塊總數

2.1.2 union obj和free_list

2.1.3 從記憶體池擷取區塊放置free_list中

2.1.4 refill和chunk_alloc

2.1.5 allocate，deallocate，reallocate

3 全局函數construct，deconstruct

3.1 ：stl_alloc.h，stl_construct.h

3.1.1 stl_alloc.h——配置器

3.1.2 stl_construct.h——construct()和destroy()

3.2 construct和destroy

3.2.1 construct

3.2.2 destroy

4 全局函數uninitialized_copy，uninitialized_fill，uninitialized_fill_n

4.1 uninitialized_fill_n

4.2 uninitialized_fill

4.3 uninitialized_copy

allocator的必要接口

allocator	value_type
pointer
const_pointer
reference
const_reference
size_type
difference_type
rebind

allocator為什麼需要這些成員函數，可以試着從new和delete的角度來分析

（1）new配置設定堆空間，需要size，type兩個參數，即配置設定size大小的記憶體，類型為type。

（2）new配置設定完記憶體後，傳回指向配置設定空間的首位址

（3）delete回收new配置設定的空間

為什麼要實作這些必要的接口，除了從功能的角度，還可以從複用的角度來看。

标準就是為了複用，allocator是為上層容器提供服務的，是以它要穩定，一旦它不穩定，對于上層結構的沖擊是巨大的——就像網絡協定棧

穩定即意味着提供穩定不變的接口——不管内部實作是什麼，要接口符合标準就行

空間配置器——隻做空間配置設定和釋放工作，不做初始化對象工作。（單一職責）

1 JJ::allocator——STL源碼解析

#include <new>  //for placement new
/*
1、ptrdiff_t，與機器相關的資料類型，通常用來儲存兩個指針減法操作的結果，可正可負，是long int類型 
2、siz_t，用于指明數組長度，是unsigned樂星 
*/
#include <cstddef>  //for ptrdiff_t, size_t

#include <cstdlib>  //for exit()
#include <climits>  //for UINT_MAX
#include <iostream> //for cerr

using namespace std;

namespace JJ
{
template <typename T>
inline T* _allocate(ptrdiff_t size, T*){
    set_new_handler(0);  //當new配置設定空間失敗時，不做任何處理 
    T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));  //封裝了全局new操作符，而且使用operator() 
    if (tmp == 0){
        cerr << "out of memory" << endl;
        exit(1);
    }
    return tmp;
}

template <typename T>
inline void _deallocate(T* buffer){
    ::operator delete(buffer);  //使用operator()釋放空間 
}

template <class T1, class T2>
inline void _construct(T1* p, const T2& value){
/*
定位new運算符——在為對象配置設定記憶體時，可以指定記憶體的位置，括号中放置指定位置的指針 
*/
    new(p) T1(value);  //placement new. invoke ctor of T1——在p指向的記憶體空間，調用T1的構造函數，并使用T2類型參數作為構造參數 
}

template <class T>
inline void _destroy(T* ptr){
    ptr->~T();
}

template <class T>
class allocator{
public:

    /*
        這種定義方式似乎使得程式的可讀性變高了
		但是我在項目中曾經遇到一個BUG——比如，随着版本的疊代，value_type的本質變了，不再是T
		是以有的時候使用T本身可以帶來不必要的麻煩 
    */
    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;
    
    template <class U>
    struct rebind{
        typedef allocator<U> other;
    };
    
    pointer allocate(size_type n, const void* hint = 0){
        return _allocate((difference_type)n, (pointer)0);
    }
    
    void deallocate(pointer p, size_type n){
        _deallocate(p);
    }
    
    void construct(pointer p, const T& value){
        _construct(p, value);
    }
    
    void destroy(pointer p){
        _destroy(p);
    }
    
    pointer 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));
	} 
};

} 

#include <vector>
#include <algorithm>
using std::vector;
using namespace JJ;

int main(int argc, char** argv) {
    
    int array[5] = {1, 2, 3, 4, 5};
	unsigned int i;
	
	vector<int, JJ::allocator<int> > v(array, array + 5);
	for_each(v.begin(), v.end(), [](int i){ cout << i << endl;});
	return 0;
}

2 配置器std::alloc

雙層級配置器std::alloc，128bytes是門檻值

1、typedef __malloc_alloc_template<0> malloc_alloc; typdef malloc_alloc alloc;——第一級配置器

當要求的記憶體大于128bytes時，使用該配置器。

成員函數allocate調用malloc配置設定記憶體，傳回一個void *指針

成員函數deallocate調用free釋放記憶體，傳回void

2、typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;——第二級配置器

使用記憶體池，由free_lists管理16個節點，每個節點管理的區塊大小分别為——8，16，24，32，40，48，56，64，72，80，88，96，104，112，120，128bytes

每個節點管理着該節點對應的區塊大小的連結清單，如果需要配置設定的節點在128bytes範圍内，則找到最比對節點（不滿8的倍數，按照8的倍數配置設定），配置設定給用戶端。

SGI為alloc包裝了一個接口，使得其符合STL規範

template <class T, class Alloc>
class simple_alloc{
public:
    static T *allocate(size_t);
    static T *allocate(void);
    static void deallocate(T*, size_t);
    static void deallocate(T*);
};


//這種定義方式多用在容器中
typedef simple_alloc<T, alloc> data_allocator;

2.1 二級配置器——__default_alloc_template

源碼——128bytes為一個門限，大于128bytes就調用第一級配置器

#include <iostream>
#include <new.h>
using namespace std;

enum { __ALIGN = 8 };  //小型區塊的上調邊界 
enum { __MAX_BYTES = 128 };  //小型區塊上限 
enum { __NFREELISTS = __MAX_BYTES / __ALIGN };  //free-lists 個數 

template <bool threads, int inst>
class default_alloc_template{
private:
	static size_t ROUND_UP(size_t bytes){
		//~(__ALIGN - 1）= 11111000
		//與的過程中，把0~7的值全部消除，隻留下了8的倍數
		//而且 + (__ALIGN - 1)保證了傳回值必然 >= bytes 
		return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1));   
	}
private:
	union obj{
		union obj * free_list_link;  //在64位Windows系統gcc編譯器上，指針的大小為8位元組 
		char client_data[1];  //這裡的值是位址低位元組的值 
	};
private:
    //16個free-lists：8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128。
	//這個有點類似hash-table的buckets-nodes結構 
	//每個數組節點管理一個連結清單，同一連結清單上的節點區塊大小相等 
	//volatile告訴編譯器這是個“易變化”的變量，随時可能改變。
	//這樣編譯器就不會對它進行某些優化——比如不會從寄存器讀取資料，而是從變量位址讀取；
	//                                    比如不會調整指令順序以優化CPU指令流水線 
	static obj * volatile free_list[__NFREELISTS];  //一個數組，效率高 
	
	static size_t FREELIST_INDEX(size_t bytes){
		return ((bytes) + __ALIGN - 1) / __ALIGN - 1;  //傳回數組的索引——索引與請求的區塊的小是一一對象的 
	}
		
	
private: 
	//傳回一個大小為 n 的對象，并可能加入大小為 n 的其它區塊到 free-list 
	static void *refill(size_t n);
	//配置一大塊空間，可容納 nobjs 個大小為 "size" 的區塊
	//如果配置 nobjs 個區塊有所不便，nobjs 可能會降低
	static char *chunk_alloc(size_t size, int &nobjs);
	
	//Chunk allocation state
	static char *start_free;  //記憶體池起始位置。隻在chunk_alloc()中變化 
	static char *end_free;  //記憶體池結束為止。隻在chunk_alloc()中變化 
	static size_t heap_size; 
	
public:
	static void * allocate(size_t n);
	static void deallocate(void *p, size_t n);
	static void * reallocate(void *p, size_t old_sz, size_t new_sz);
}; 

//staitc data memeber的定義與初值設定
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;  //初值為0 

template <bool threads, int inst>
typename default_alloc_template<threads, inst>::obj * volatile 
default_alloc_template<threads, inst>::free_list[__NFREELISTS] = 
{
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};


// allocate的算法
//（1）首先判斷區塊大小，大于128bytes就調用第一級配置器，小于128bytes就檢查對應free-lists
//（2）小于128bytes——在free_list上尋找适當的區塊，傳回目前索引 
template <bool threads, int inst>
void * default_alloc_template<threads, inst>::allocate(size_t n)
{
    if (n > (size_t) __MAX_BYTES)
	{
		return malloc(n); //第一級配置器的allocate()内部直接使用malloc()配置設定 
	}	
	
	obj * volatile * my_free_list;
	obj * result;
	//尋找free_list中适當的區塊
	my_free_list = free_list + FREELIST_INDEX(n); //my_free_list為資料節點的位址 
	result = *my_free_list;  //解引用，擷取數組目前索引的元素 
	
	if (result == 0) { //如果目前索引管理的連結清單為空，則直接配置設定，不從連結清單取 
		void * r = refill(ROUND_UP(n));
		return r;
	}
	
	//指向管理的連結清單的首節點的下一個節點 
	*my_free_list = result->free_list_link;
	return (result);
} 

template <bool threads, int inst>
void default_alloc_template<threads, inst>::deallocate(void * p, size_t n)
{
	//大于128就調用第一級配置器
	if (n > (size_t) __MAX_BYTES){
		free(p);
		return;
	} 
	
	obj * q = (obj *)p;
	obj * volatile * my_free_list;
	//尋找對應的free list 
	my_free_list = free_list + FREELIST_INDEX(n);
	//調整free list，回收區塊
	q->free_list_link = *my_free_list;  //把待回收的區塊插入到目前空閑區塊的前面 
	*my_free_list = q;   //使得索引對應的值為首部指針 
}


//如果free_list沒有可用區塊，調用refill()，準備為free_list重新填充空間
//新的空間将取自記憶體池（經由chunk_alloc()）完成
//預設取得20個新節點（新區塊），但萬一記憶體池空間不足，獲得的節點數（區塊數）可能小于20
 
template <bool threads, int inst>
void * default_alloc_template<threads, inst>::refill(size_t n)  //假設 n 已經調節為 8 的倍數 
{
    int nobjs = 20;
    //調用chunk_alloc()，嘗試取得nobjs個區塊作為free_list的新節點
	//注意參數nobjs是pass by reference
	char * chunk = chunk_alloc(n, nobjs);  //chunk_alloc配置設定了一個塊。這個塊共有20個節點，每個節點大小為 n。
	
	obj * volatile * my_free_list;
	obj * result;
	obj * current_obj, *next_obj;
	int i;
	
	//如果隻獲得一個區塊，這個區塊就配置設定給調用者用，free_list無新節點
	if (1 == nobjs)
	    return (chunk);
	//否則準備調整free_list，納入新節點
	my_free_list = free_list + FREELIST_INDEX(n);
	
	//以下在 chunk 空間内建立 free_list
	result = (obj*)chunk;  //把塊的第一個節點傳回給用戶端，剩下的連結到free_list 
	//導引free_list指向新配置的空間（取自記憶體池）
	*my_free_list = next_obj = (obj *)(chunk + n);  //這裡它把請求的記憶體塊解釋為 union obj
	                                                //即該記憶體塊的前8個位元組存放的是union obj 
	                                                //這樣也就滿足了前面一個union既可以指向下一個union obj，又可以指向記憶體塊
													//因為通過數組下标，即可通路obj後續的空閑記憶體塊。 
	//将free_list的各節點串接起來
	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);
}

//記憶體池——memory pool
//chunk_alloc操作的對象時記憶體池，從記憶體池中取得所需記憶體
//如果記憶體池空間不足，則重新malloc記憶體
//如果malloc不到，則從free_list尋找空閑的區塊，賦給記憶體池，再對記憶體池chunk_alloc 
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){
		//記憶體池剩餘空間完全滿足需求量
		result = start_free;
		start_free += total_bytes;
		return (result); 
	} else if (bytes_left >= size){
	    //記憶體池剩餘空間不能完全滿足需求量，但足夠供應一個（含）以上的區塊
		nobjs = bytes_left / size;  //剩餘空間共有 nobjs 個區塊
		total_bytes = size * nobjs;
		result = start_free;
		start_free += total_bytes;  //把剩餘空間都配置設定到free_list上 
		return (result); 
	}else{
		//記憶體池剩餘空間連一個區塊的大小都無法提供，則擴充記憶體池，重新調用chunk_alloc 
		//配置設定所需空間的兩倍 
		size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);  //為什麼要向右移動4位或者說為什麼要除以8 
		//讓記憶體池的殘餘零頭插入到free_list對應位置上 
		if (bytes_left > 0)
		{
			obj * volatile * my_free_list = free_list + FREELIST_INDEX(bytes_left);  //這裡索引用的是bytes_left，而不是size 
			((obj *)start->free)->free_list_link = *my_free_list;  //使得新節點為索引所指連結清單的頭結點 
			*my_free_list = (obj *)start_free;  //指向插入新節點後的連結清單的頭結點 
		 } 
		 
		 //連結清單節點管理的連結清單為空才會調用refill，refill調用chunk_alloc配置設定大塊記憶體
		 //如果記憶體池中空間滿足需求，則配置設定出去，否則，把剩餘空間配置設定出去；
		 //如果記憶體池空間不足一個size，則重新malloc兩倍空間 
		 //配置heap空間，用來補充記憶體池
	    start_free = (char *)malloc(bytes_to_get);  //配置設定所需空間的兩倍 
	    if (0 == start_free){
	    	//malloc()失敗
			int i;
			obj * volatile * my_free_list, *p;
			//malloc()失敗，則從free_list上尋找可用空間（從大于size的區塊的索引開始尋找） 
			for (i = size; i <= __MAX_BYTES; i += __ALIGN){
				my_free_list = free_list + FREELIST_INDEX(i);  //周遊free_list，尋找比size更大的區塊 
				p = *my_free_list;
				if (0 != p)
				{
				   *my_free_list = p->free_list_link;
				   start_free = (char *)p;    //把連結清單中大于size且空閑的空間賦給記憶體池 
				   end_free = start_free + i;
				   return (chunk_alloc(size, nobjs));  //遞歸調用自己，修正nobjs 
				}
			} 
            //如果free_list上也沒有滿足需求的空閑區塊 
			end_free = 0;
			start_free = (char *)malloc(bytes_to_get);  //調用第一級配置器，借用out-of-memory機制 
		}
	
	heap_size += bytes_to_get;
	end_free = start_free + bytes_to_get;
	return (chunk_alloc(size, nobjs)); 
	} 
} 



int main(int argc, char** argv){
   
	
	return 0;
}

2.1.1 區塊大小和空閑鍊塊總數

enum { __ALIGN = 8 };  //小型區塊的上調邊界 
enum { __MAX_BYTES = 128 };  //小型區塊上限 
enum { __NFREELISTS = __MAX_BYTES / __ALIGN };  //free-lists 個數
           
為什麼是8？

從union obj的内部結構來看，在32位下，sizeof(obj) = 4；在64位下，sizeof(obj) = 8；是以，最小的區塊大小為8，且其他均為8的倍數。（個人認為是這樣的原因，畢竟底層實作中，資料結構和算法還是耦合在一起的）

2.1.2 union obj和free_list

union obj{
 		union obj * free_list_link;  //在64位Windows系統gcc編譯器上，指針的大小為8位元組 
		char client_data[1];  //這裡的值是位址低位元組的值 
	};

	static obj * volatile free_list[__NFREELISTS];  //一個數組，效率高 
	
	static size_t FREELIST_INDEX(size_t bytes){
		return ((bytes) + __ALIGN - 1) / __ALIGN - 1;  //傳回數組的索引——索引與請求的區塊的小是一一對象的 
	}
           
書中說：union obj，從第一字段來看，obj可被視為一個指針，指向相同形式的另一個obj；從第二個字段來看，obj可被視為一個指針，指向實際區塊。一物二用。（這樣可以避免為了維護連結清單所必須的指針而造成記憶體的一種浪費）

union obj，從定義來看，char[0-3/7]和obj *公用同一段存儲空間，char[0-3/7]所指空間已經被obj *的值所填充了，其本身并不能存儲資料，是以，隻看定義無法很快了解它的效果。需要結合實際應用。
char * chunk = chunk_alloc(n, nobjs);  //chunk_alloc配置設定了一個塊。這個塊共有20個節點，每個節點大小為 n。
	
	obj * volatile * my_free_list;
	obj * result;
	obj * current_obj, *next_obj;
	int i;
	
	//如果隻獲得一個區塊，這個區塊就配置設定給調用者用，free_list無新節點
	if (1 == nobjs)
	    return (chunk);
	//否則準備調整free_list，納入新節點
	my_free_list = free_list + FREELIST_INDEX(n);
	
	//以下在 chunk 空間内建立 free_list
	result = (obj*)chunk;  //把塊的第一個節點傳回給用戶端，剩下的連結到free_list 
	//導引free_list指向新配置的空間（取自記憶體池）
	*my_free_list = next_obj = (obj *)(chunk + n);
           
在refill中用到了union obj *，這裡就可以了解一物二用的原理了——當把一個大塊記憶體空間解釋為union obj時，隻有記憶體空間的前幾個位元組被占用，後面的記憶體仍然是空閑的。這也正對應書中所畫的圖——union obj在大塊記憶體的前面一小部分。

這樣就可以使用union obj中指針指向另一個區塊，而使用client_data來通路空閑區塊

2.1.3 從記憶體池擷取區塊放置free_list中

//傳回一個大小為 n 的對象，并可能加入大小為 n 的其它區塊到 free-list 
	static void *refill(size_t n);
	//配置一大塊空間，可容納 nobjs 個大小為 "size" 的區塊
	//如果配置 nobjs 個區塊有所不便，nobjs 可能會降低
	static char *chunk_alloc(size_t size, int &nobjs);
	
	//Chunk allocation state
	static char *start_free;  //記憶體池起始位置。隻在chunk_alloc()中變化 
	static char *end_free;  //記憶體池結束為止。隻在chunk_alloc()中變化 
	static size_t heap_size; 
           
static char *start_free; static char *end_free; 分别指向配置設定的記憶體塊的首部和尾部

refill調用chunk_alloc配置設定多個大塊記憶體，分出一個給用戶端，其他的放入free_list中

chunk_alloc從記憶體池中擷取一整塊記憶體，如果記憶體池沒有，則重新malloc到記憶體池——>如果malloc失敗則從free_list上請求大于size的空閑區塊——>如果free_list也沒有，則使用第一級配置器來配置設定記憶體（其有out-of-memory機制可以跑出異常或釋放出一些記憶體）。

2.1.4 refill和chunk_alloc

1、refill的算法

（1）調用chunk_alloc擷取大塊記憶體

（2）把第一塊記憶體傳回給用戶端

（3）剩下的記憶體插入到free_list成鍊

2、chunk_alloc算法

（1）chunk_alloc操作的對象時記憶體池，從記憶體池中取得所需記憶體

（2）如果記憶體池空間不足，則重新malloc記憶體

（3）如果malloc不到，則從free_list尋找空閑的區塊，賦給記憶體池，再對記憶體池chunk_alloc

（4）都不行，則調用第一級配置器的allocate配置設定記憶體，利用其out-of-memory機制解圍

2.1.5 allocate，deallocate，reallocate

當free_list中需求的區塊空間不足時，調用allocate，reallocate中會調用refill來擷取空間

1、allocate的算法

（1）首先判斷區塊大小，大于128bytes就調用第一級配置器，小于128bytes就檢查對應free-lists

（2）小于128bytes——在free_list上尋找适當的區塊，傳回目前索引

2、deallocate的算法

（1）大于128bytes則調用第一級配置器

（2）尋找目前回收的區塊大小對應的索引，把該區塊插入該索引管理的連結清單首部

3 全局函數construct，deconstruct

類有構造函數，有析構函數

當聲明了一個類對象，空間配置器為它配置設定空間，并調用類的構造函數把記憶體空間初始化

即記憶體空間的配置與釋放和對象内容的構造與析構是分開的。

3.1 <memory>：stl_alloc.h，stl_construct.h

配置器的std::alloc定義于<memory>中，内含兩個檔案

#include <stl_alloc.h> //負責記憶體空間的配置和釋放

#include <stl_constuct.h> //負責對象内容的構造與析構

3.1.1 stl_alloc.h——配置器

負責記憶體空間的配置與釋放

3.1.2 stl_construct.h——construct()和destroy()

construct()負責對象的構造

destroy()負責對象的析構

3.2 construct和destroy

3.2.1 construct

construct全局函數通過在配置設定了記憶體空間的p指針上，調用構造函數來構造對象。——使用placement new：new(p) T(value)
template <class T1, class T2>
inline void construct(T1* p, const T2& value){
    new (p) T2(value);
}
           

3.2.2 destroy

有兩種

1、通過指針調用析構函數

template <class T>
inline void destroy(T* pointer){
    pointer->~T();
}

2、判斷元素的數值型别是否有trivial destructor

（1）有，則destroy不做任何事

（2）無，則通過指針調用析構函數

template <class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last, T*)
{
    __destroy(first, last, value_type(first));
}

template <class ForwardIterator, class T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T*)
{
    typedef typename _type_traits<T>::has_trival_destructor trivial_destructor;
    __destroy_aux(first, last, trivial_destructor());
}


template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator first, ForwardIterator last, T*)
{
    for (; first < last; ++first)
        destroy(&*first);
}

4 全局函數uninitialized_copy，uninitialized_fill，uninitialized_fill_n

三個函數都具有“ commit or rollback ”語意——要麼構造出所有必要元素，要麼（當有任何一個copy constructor失敗時）不構造任何東西。

uninitialized_copy()

uninitialized_fill()

uninitialized_fill_n()

PS：

雖然這些函數不屬于配置器的範疇，但與對象初值設定有關。

對于容器的大規模元素初值設定很有幫助。對于效率的考慮也面面俱到——最差情況下調用construct()，最佳情況使用C标準memmove()直接進行記憶體資料移動。

4.1 uninitialized_fill_n

從first開始，使用x，初始化往後n個對象

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));
}

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_trait<T1>::is_POD_type is_POD;
    return __uninitialized_fill_n_aux(first, n, x, is_POD());
}


//POD型别
//調用高階函數fill_n實作——可能直接memcopy了
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>
inline ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first, 
                                            Size n, const T& x, __false_type){
    ForwardIterator cur = first;
    for (; n > 0; --n, ++cur)
        construct(&*cur, x);  //傳入指針，通過指針調用構造函數
    return cur;
}

1、首先萃取出疊代器first的value_type，然後判斷型别是否為POD型别

POD意指Plain Old Data，即标量型别或傳統的C struct。

POD型别必然擁有trivial ctor/dtor/copy/assignment函數，是以可以對POD型别采用最高效的初值填寫手法。

4.2 uninitialized_fill

用x，初始化從first到last的所有對象

形式與uninitialized_fill_n差不多

4.3 uninitialized_copy

把first到last的對象複制到result開始的容器中

template <class InputIterator, class ForwardIterator>
inline ForwardIterator uninitialized_copy(InputIterator first, InputIterator last,
                                          ForwardIterator result){
    return __uninitialized_fill_n(first, n, x, value_type(first));
}

template <class InputIterator, class ForwardIterator, class T>
inline ForwardIterator __uninitialized_copy(InputIterator first, InputIterator last,
                                            ForwardIterator reslut, T*){
    typedef typename __type_trait<T1>::is_POD_type is_POD;
    return __uninitialized_copy_aux(first, last, result, is_POD());
}

//POD型别
//調用高階函數fill_n實作——可能直接memcopy了
template <class InputIterator, class ForwardIterator>
inline ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,
                                            ForwardIterator reslut, __true_type){
    return copy(first, last, result);
}

//非POD型别
//采用安全的方法——調用構造函數
template <class InputIterator, class ForwardIterator>
inline ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,
                                            ForwardIterator reslut, __false_type){
    ForwardIterator cur = result;
    for (; n > 0; --n, ++cur)
        construct(&*cur, *first);  //傳入指針，通過指針調用構造函數
    return cur;
}

對于char*和wchar_t*兩種型别，可以采用最具效率的做法memmove（直接移動記憶體内容）來執行複制行為

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);
}

STL——allocator1 JJ::allocator——STL源碼解析2 配置器std::alloc3 全局函數construct，deconstruct4 全局函數uninitialized_copy，uninitialized_fill，uninitialized_fill_n

1 JJ::allocator——STL源碼解析

2 配置器std::alloc

2.1 二級配置器——__default_alloc_template

2.1.1 區塊大小和空閑鍊塊總數

2.1.2 union obj和free_list

2.1.3 從記憶體池擷取區塊放置free_list中

2.1.4 refill和chunk_alloc

2.1.5 allocate，deallocate，reallocate

3 全局函數construct，deconstruct

3.1 <memory>：stl_alloc.h，stl_construct.h

3.1.1 stl_alloc.h——配置器

3.1.2 stl_construct.h——construct()和destroy()

3.2 construct和destroy

3.2.1 construct

3.2.2 destroy

4 全局函數uninitialized_copy，uninitialized_fill，uninitialized_fill_n

4.1 uninitialized_fill_n

4.2 uninitialized_fill

4.3 uninitialized_copy

繼續閱讀

常用的C++11,14,17 新特性清單初始化

C++三大繼承構造函數的執行順序詳解

leetcode 61. Rotate List 旋轉連結清單

Visual studio 快捷鍵的檢視與修改以添加/取消注釋為例快捷鍵檢視快捷鍵修改

超好用的代碼格式化工具Astyle使用

C++之【操作符】彙總 &【不能被重載的運算符】小記

常用C++代碼——整理自己的通用代碼一、檔案讀寫二、類型轉換三、字元串操作四、效率計算（clock）五、錯誤六、定時器

C++:C/C++記憶體管理

C++ 連結清單list1 構造函數2 指派和交換3 大小操作4 插入和删除5 資料存取6 反轉和排序

A1011 World Cup Betting (20 分)

C++_01_資料類型

C++中的頭檔案”#include<algorithm>“

C/C++常用頭檔案及函數彙總【轉】

作為函數參數的指針作為函數參數的指針

Qt資料庫判斷本地是否已經建立/存在資料庫，SQLite