你不能不知道的記憶體配置設定，從全局概覽STL的allocator空間配置器

一、空間配置器allocator介紹

allocator是隐藏在STL元件（容器vector、map等）背後的，用來配置設定記憶體，這樣STL容器才能有空間存放元素
為什麼不說 allocator是記憶體配置器而說它是空間配置器呢？因為，空間不一定是記憶體，空間也可以是磁盤或其他輔助儲存媒體。是的，你可以寫一個 allocator，直接向硬碟取空間

二、空間配置器的标準接口

allocator的使用文法可以參見文章：javascript:void(0)

三、設計自己的allocator

#include <iostream>
#include <new>
#include <cstdlib>
#include <cstddef>
#include <climits>
#include <vector>

using namespace std;

namespace JJ
{
	//申請size個類型為T的位址空間
	template<class T>
	inline T* __allocate(ptrdiff_t size, T*)
	{
		std::set_new_handler(0);//設定記憶體配置設定出錯處理函數，詳情見文章： 
		T *tmp = (T*)(::operator new((size_t)(size*sizeof(T))));

		//如果配置設定失敗
		if (tmp == 0) {
			std::cerr << "out of memory" << std::endl;
			exit(1);
		}
		//配置設定成功傳回配置設定的首位址
		return tmp;
	}

	//釋放buffer所指的位址
	template<class T>
	inline void __deallocate(T* buffer)
	{
		::operator delete(buffer);
	}

	//使用placement new來在p所指的位址中構造一個類型為T1的對象，對象的值為value
	template<class T1, class T2>
	inline void __construct(T1* p, const T2& value)
	{
		new(p) T1(value);
	}

	//對ptr所指的對象執行析構函數
	template<class T>
	inline void __destory(T* ptr)
	{
		ptr->~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;  //兩個指針之間的距離大小

		template<class U>
		struct rebind {
			typedef allocator<U> other;
		};

		//配置設定n個大小為T的位址空間（參數2為類型T）
		pointer allocate(size_type n, const void* hint = 0) {
			return _allocate((difference_type)n, (pointer)0);
		}

		//從p所指的位址開始，釋放n個類型為T的對象
		void deallocate(pointer p, size_type n) { __deallocate(p); }

		/*p為自身T*類型的指針，指向一塊記憶體，這個記憶體是先前配置設定過且未釋放的
		value為傳遞給類型為T的構造函數，用來對p所指的記憶體中構造一個對象，placement new*/
		void construct(pointer p, const T& value) {
			__construct(p, value);
		}

		//對p所指的對象執行析構函數
		void destory(pointer p) { __destory(p); }

		//傳回x的位址
		pointer address(reference x) { return (pointer)&x; }

		//傳回x的位址（const類型）
		const_pointer const_address(const_reference x) { return (const_pointer)&x; }

		//傳回系統中可以配置設定類型為T的對象的最大量
		size_type max_size()const {
			return size_type(UINT_MAX / sizeof(T));
		}
	};
}

測試1：我們知道标準庫中的vector在初始化時，可以在模闆2處指定空間配置器用來替代預設的空間配置器。下面我們将自己設計的allocator用于标準庫的vector

int main()
{
	int ia[5] = { 0,1,2,3,4 };
	unsigned int i;
	//vector<int, std::allocator<int>> iv(ia, ia + 5);
	
	vector<int, JJ::allocator<int>> iv(ia, ia + 5);
	for (i = 0; i < iv.size(); i++) {
		cout << iv[i] << ' ';
		cout << endl;
	}
	return 0;
}

下面在Linux與Windows下分别測試，發現出錯，原因：

标準庫STL所實作的容器底層十分複雜，我們自己設計的allocator無法滿足标準庫的使用，是以報錯是正常的

測試2：

int main()
{
	int ia[5] = { 0,1,2,3,4 };
	unsigned int i;
	vector<int, std::allocator<int>> iv(ia, ia + 5);
	
	//vector<int, JJ::allocator<int>> iv(ia, ia + 5);
	for (i = 0; i < iv.size(); i++) {
		cout << iv[i] << ' ';
		cout << endl;
	}
	return 0;
}

下面我們使用标準庫的allocator空間配置器，在Linux可以運作成功，因為标準庫的allocator空間配置器實作更加複雜（下面的一系列文章，我們将對标準庫的allocator空間配置器進行剖析）

四、SGI STL版本的allocator源碼

SGI STL定義了一個符合部分标準的allocator配置器，但是SGI并為使用過，也不建議使用，主要因為效率不佳，其隻是把C++的::operator new和::operator delete做一層簡單地封裝而已
下面是SGI STL版本的allocator的源碼，位于defalloc.h頭檔案中（這個版本的allocator不是我們研究的對象，我們研究的對象是下面會介紹的标準STL allocator配置器）

#ifndef DEFALLOC_H
#define DEFALLOC_H

#include <new.h>
#include <stddef.h>
#include <stdlib.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 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))); 
    }
};

class allocator<void> {
public:
    typedef void* pointer;
};



#endif

五、STL标準版本的allocator版本

上面介紹的SGI STL版本的allocator隻是基層記憶體配置/釋放行為（也就是::operator new和::operator delete）的一層薄薄的封裝，并為考慮到任何效率上的強化
STL标準定義的allocator定義在<memory>頭檔案中

一個小案例

為了更友善了解STL标準定義的allocator，我們使用下面的一個C++記憶體配置和釋放操作來引出我們的話題
class Foo{...};

Foo* pf=new Foo; //配置記憶體，然後構造對象
delete pf;  //将對象析構，然後釋放記憶體           
new操作符：

1.先調用::operator new配置記憶體

2.然後調用Foo::Foo()構造對象

delete操作符：

1.先調用Foo:~Foo()将對象析構

2.再調用::operator delete釋放記憶體

allocator的實作

與上面介紹的案例相似，STL标準實作的allocator也是将allocator分為幾步來實作：

1.記憶體配置操作由alloc::allocate()負責

2.記憶體釋放操作由alloc::deallocate()負責

3.對象構造操作由::construct()負責

4.對象析構操作由::destroy()負責

<memory>頭檔案包含以下頭檔案：

#include <stl_alloc.h>：定義了::construct()、::destroy()

#include <stl_construct.h>：定義了alloc::allocate()、alloc::deallocate()等

#include <stl_uninitiallized.h>：定義了一些記憶體處理工具函數

由于allocator的實作比較複雜，本文不會介紹标準STL allocator的實作，而是将實作步驟按順序分為以下幾篇文章來介紹：
- 構造和析構工具construct()、destroy()的介紹：javascript:void(0)
- 空間的配置設定與釋放alloc::allocate()、alloc::deallocate()的介紹：javascript:void(0)
- 記憶體處理工具uninitialized_copy()、uninitialized_fill()、uninitialized_fill_n()：javascript:void(0)

我是小董，V公衆點選"筆記白嫖"解鎖更多【C++ STL源碼剖析】資料内容。

你不能不知道的記憶體配置設定，從全局概覽STL的allocator空間配置器

一個小案例

allocator的實作

繼續閱讀

HDU 5344 MZL's xor

UVA 590 Always on the run

FZU 1978 Repair the brackets

UVA 10344- 23 out of 5

ZOJ 3935 2016

POJ 2115 C Looooops

HDU 5381 The sum of gcd

ZOJ 1104 Leaps Tall Buildings

ZOJ 3700 Ever Dream

HDU 2821 Pusher

ZOJ 1199 Point of Intersection

UVA 1401 Remember the Word

UVA 620 Cellular Structure

ZOJ 2748 Free Kick

CSU 1567 Reverse Rot

UVA 519 Puzzle (II)