***上一篇是對STL空間配置器的入門級了解，在這一篇中，我将讨論更加深入的SGI STL空間擴充卡的内容。在下一節中，我将根據自己的了解，結合STL标準接口，實作一個符合STL标準的具有次級配置能力的簡單空間配置器，将剪掉一切不需要的代碼，在加上我自己的了解，實作一個更容易閱讀與了解的空間配置器。
在開始進入正題之前，我先來談談為什麼要花這麼長的時間在看空間配置器的部分，而且對于學習如何使用STL來說，根本就不需要知道有空間擴充卡的存在，因為我們在實際程式設計中是不需要與空間配置器打交道的。那我想說，如果僅僅是為了學習如何使用STL去程式設計，那大可不必去閱讀他的源代碼，隻需要記住每個函數的功能和用法，然後就可以解決問題。但那不是學會STL，那是學會用STL。這是最為容易做到的事情，我相信隻要有點程式設計語言基礎的人，給上一個小時就完全可以用STL的各種組建來做事情了。***
但是這遠遠不夠，學習STL的核心在于了解他的設計原理，明白了原理，才能更好的去用STL，比如，如果你不知道STL容器之間的差別，那我相信大多數人在哪都會用一個容器vector，這個容器已然成了“通用容器”，确實，對于一般性問題，vector足夠強大去承擔各種場景，但是，你想想，如果隻需要vector就能把事情做好，那為什麼STL還有list呢？為什麼還有queue呢？那map呢？思考從這裡開始，但是對于本節來講，這些思考到這裡結束。
我們現在來讨論SGI STL的空間配置器，這是STL能正常、合理、高效工作的基礎和動力，他讓使用STL的各個元件變得更加容易，有了空間配置器，我們就不需要自己去管理記憶體，當然也不需要自己去處理記憶體不足的問題。既然是STL的基礎，那麼就要打好這個基礎，STL從這裡開始，我想，最後還是會回到這裡。
STL空間配置器有一套标準接口，這對我們很重要，因為如果我們想要自己寫一套屬于自己的STL版本，那就應該努力符合STL标準。SGI當然也有一個符合STL标準的空間配置器，但是在源代碼的開始，SGI就奉勸大家不要輕易使用這個版本的空間配置器，留着它隻是為了相容STL标準，是以，很明顯這個檔案不會被SGI STL用到，但是我們還是來看看它吧，也乘機了解了解STL标準的空間配置器張什麼樣子。
//為了相容STL标準而寫的這個檔案，實際上SGI STL并沒有使用這個檔案作為他的空間配置器
//下面這個類提供标準STL申請對象函數allocate
template <class T>
inline T* allocate(ptrdiff_t size, T*) {
set_new_handler(); //應該還記得new-handler機制吧（out-of-memory）
T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
if (tmp == ) {
cerr << "out of memory" << endl;
exit();
}
return tmp; //傳回一個對象指針
}
//空間配置器析構函數
template <class T>
inline void deallocate(T* buffer) {
::operator delete(buffer);
}
//标準SGI架構配置器
template <class T>
class allocator {
public:
//一組别名定義，不明真相的我以為這很沒有必要，可以直接将T改名為Type就ok啦
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;
//配置n個空的對象
pointer allocate(size_type n) {
return ::allocate((difference_type)n, (pointer));
}
//釋放
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(), size_type(/sizeof(T)));
}
size_type max_size() const {
return max(size_type(), size_type(UINT_MAX/sizeof(T)));
}
};
//ok，在你的需要配置的地方，使用這個就可以了
class allocator<void> {
public:
typedef void* pointer;
};
看了上面的代碼，我們應該知道了标準STL空間配置器應該含有哪些接口了吧？我将在下一節中實作一個标準空間配置器。
SGI真正使用的配置器的設計非常巧妙，它實作了一級配置器和次級配置器，兩級配置器互相配合，高效的為STL各種組建提供動力。我們已經在上一節中介紹了兩級配置器的原理，還介紹了它們是如何協調工作的，是以在這裡我也不會再次花費篇幅來講這兩級配置器，但是，我想講講記憶體管理。
當我們聽到記憶體管理的時候，一般會想到作業系統，核心，MMU這些東西，确實，在我們的應用中，特别是在C++語言中，我們自己管理記憶體較為簡單，new和delete配合使用即可，但即便如此，也免不了一些記憶體洩漏的BUG，作為一個高效安全的c++标準庫，STL用空間擴充卡将STL的組建的記憶體管理得井然有序，不需要我們自己花費精力去管理。那什麼是記憶體管理呢？本質是什麼呢？我以為，記憶體管理其實就是管理位址空間，記憶體的申請與釋放相當于對某一位址空間的上标記與解标記，上标記則表明已經被配置設定，用不用是程式做的事情，反正這段位址上了标記就是表明不能被再次配置設定了。有人可能會說我不是在說廢話嗎？記憶體不就是位址嗎？其實，我必不反對将記憶體說成位址空間，因為我就是那麼去了解記憶體的，進一步，對于32位的位址線，最大記憶體是2^32=4Gb，是以從記憶體是怎麼得到的來看，确實，記憶體就是位址空間，能提供的位址空間越大，那能管理的記憶體就越多，64位的位址線能管理的記憶體肯定大于32位的。
但是，記憶體不是位址，我隻能說這麼多！
對于STL裡面的空間擴充卡，它使用了malloc和free函數來實作記憶體的配置設定與回收，沒有使用我們熟悉的c++裡面的new和delete，很明顯，malloc和free的效率高于new和delete，但有可能對于程式員來說，new和delete更為熟悉和安全。
SGI STL空間擴充卡用到了一種稱為“記憶體池”的技術，這是一種較為進階的記憶體管理技術，在實作上，可以首先向作業系統申請一塊較大的記憶體空間，然後以後的每次記憶體操作都使用記憶體池接口，這樣就可以實作用記憶體池來管理程式中的記憶體操作，如果設計合理，使用記憶體池可以提高代碼的效率，還能有效減少記憶體碎片化問題，比直接使用malloc和free好很多。
在下一節中，我将實作一個通用的記憶體池，在這之前，還是先看看SGI空間配置器的記憶體池是如何設計的吧。（在我自己實作的空間配置器裡面，我将使用記憶體池技術，是以到時候再一次詳談）。
最後，我們來看看SGI STL的空間配置器的檔案組織模式。
下面是在檔案memory裡面發現的頭檔案：
#include <stl_algobase.h>
#include <stl_alloc.h> //負責記憶體空間的配置與釋放，裡面有一二級配置器
#include <stl_construct.h> //負責對象内容的構造與析構
#include <stl_tempbuf.h>
#include <stl_uninitialized.h> //全局函數，輔助
#include <stl_raw_storage_iter.h>
是以，我們主要關注三個檔案，一個是stl_alloc.h，這是SGI使用的空間配置器的檔案，stl_construst.h檔案裡面定義了construct和destory函數用來操作對象，stl_uninitialized.h檔案則包含兩個主要的全局記憶體操作函數,複制和填充記憶體。
因為目前還在配置器階段，是以我們将使用SGI的這些函數來為我們工作，等時機成熟，我們将改寫這些函數。
好啦，下面我們就要開始真正的寫一個自己的配置器了，主要内容依然參照SGI STL的空間配置器，但是去掉了一切進階的功能（比如線程支援），這些支援将在最後加上。
/*
* CopyRight (c) 2016
* HuJian in nankai edu.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
* Time :2016/4/5 in nankai edu
*/
#ifndef _HJ_STL_ALLOC_H_
#define _HJ_STL_ALLOC_H_
#include<cstdio>
#include<climits>
#include<iostream>
#include<cstddef>
//if out of memory,just exit after print the info.
#define _THROW_BAD_ALLOC cerr<<"out of memory"<<endl; exit(1);
//this is the new-handler handler,using when oom
void(*_malloc_alloc_oom_handler_hjstl)() = ;
//this is the first class of mmu in hjstl,this class will work
//if the second dispatch the job to it.
template<int inst>
class _malloc_alloc_first{
private:
static void* oom_malloc(size_t); //this function use to malloc and has the new-handler
static void* oom_remalloc(void*, size_t);//re-malloc
public:
//this function is the first allocator of hjstl
static void* allocate(size_t size)
{
void* result = malloc(size);
//check and dispatch it to oom_malloc if oom
if ( == result) result = oom_malloc(size);
return result;
}
//re-malloc,same as malloc
static void* remallocate(void* old, size_t/*old mem size*/, size_t new_size)
{
void* result = realloc(old, new_size);
if ( == result) result = oom_remalloc(old, new_size);
return result;
}
//de-allocate
static void deallocate(void* mem, size_t size)
{
//we not use the memory pool,so just use free
//but we will use the memory pool to manage the memory of
//hjstl later
free(mem);
}
//we can use this function to set the new handler
static void(*set_malloc_handler(void(*handler)()))()
{
//get the old oom handler,and we will return it to process
void(*old)() = _malloc_alloc_oom_handler_hjstl;
//set the new handler
_malloc_alloc_oom_handler_hjstl = handler;
return (old);
}
};//end of malloc alloc first
///---impelment the first allocate of hjstl
template<int inst>
void* _malloc_alloc_first<inst>::oom_malloc(size_t size)
{
//this is the oom handler,this function will use this function when
//out of memory
void(*my_malloc_handler)();
void* result;
for (;;){//i will loop to test till i get the memory
my_malloc_handler = _malloc_alloc_oom_handler_hjstl;
if ( == my_malloc_handler) { _THROW_BAD_ALLOC; }
//else,the handler defined,i can use it,run this handler
(*my_malloc_handler)();
result = malloc(size);
if (result) return result;//succeed!!!
}
}
//same as malloc
template<int inst>
void* _malloc_alloc_first<inst>::oom_remalloc(void* old, size_t size)
{
void (* my_handler)();
void* result;
for (;;){
my_handler = _malloc_alloc_oom_handler_hjstl;
if ( == myhandler) { _THROW_BAD_ALLOC; }
(*my_handler)();
result = realloc(old, size);
if (result) return result;
}
}
//ok,i need to define a first allocate,and if the second
//allocate can not do it,let me try!
typedef _malloc_alloc_first<> malloc_alloc_first_hjstl;
//we do this,because we need to let the HJSTL standard with STL
template<class Type,class HJALLOC>
class STD_STL_Alloc{
public:
static Type* allocate(size_t size){
return == n ? : (Type*)HJALLOC::allocate(size*sizeof(Type));
}
static Type* allocate(){
return (Type*)HJALLOC::allocate(sizeof(Type));
}
static void deallocate(Type* mem,size_t size){
if (size != ){
HJALLOC::deallocate(mem,size*sizeof(Type));
}
}
static void deallocate(Type* mem){
HJALLOC::deallocator(mem,sizeof(mem));
}
};
//ok,start to write the second allocator
//and some auxiliary variable neeed to define here
#define _ALIGN 8 //the min mem block
#define _MAX_BYTES 128 //the max mem block
#define _NFREELISTS _MAX_BYTES/_ALIGN //this is the num of free list
template<int inst>//no thread supposed
class _malloc_alloc_second{
private:
//round up a size
static size_t HJSTL_ROUND_UP(size_t bytes){
//ok,i use the SGI STL's round up method,it nice
return (((bytes)+_ALIGN - ) & ~(_ALIGN - ));
}
//this function will find the free list's position in the array actually
static size_t HJSTL_FREELIST_INDEX(size_t bytes){
//i just copy the sgi stl's code here.
return (((bytes)+_ALIGN - ) / _ALIGN - );
}
//this is the free list's node strcture
//this is a usion.just copy the sgi stl's
union free_list_node{
free_list_node* free_list_link;//store the next free list
char data[];//if assigned,this is the user's data
};
//this is the array of free lists
static free_list_node* free_list[_NFREELISTS];
//return an object of size n,and this function will re-fill the
//free list,update the free list array .
static void* refill(size_t size);
//memory pool,and allocate a chunk for nobjs of size 'size'
//if the memory of pool is not so enough,this function will
//return the real num of nobjs
static char* chunk_alloc(size_t size, int &nobjs);
//this is a sample memory pool
static char* pool_free_start;
static char* pool_free_end;
static size_t heap_size;
//the second allocate
static void* allocate(size_t size)
{
free_list_node* my_free_list;
free_list_node* result;
//dispatch the job,if the ask memory bigger _MAX_BYTES,use
//the first allocate,else use the second allocate
if (size > (size_t)_MAX_BYTES){
return (malloc_alloc_first_hjstl::allocate(size));
}
//else ,use the second allocate to do this job
//find the aim-free list
my_free_list = free_list + HJSTL_FREELIST_INDEX(size);
//now,the result is the header pointer of this list
result = *my_free_list;
if ( == result){//shirt,this list is empty,i will call refill to help me
void* r = refill(HJSTL_ROUND_UP(size));
return r;
}
//else,this free list is not empty,just use the header pointer
//and change the free list.
*my_free_list = result->free_list_link;
return result;
}
//the second deallocate
static void deallocate(void* mem, size_t size)
{
free_list_node* my_free_list;
free_list_node* new_header_pointer = (free_list_node*)mem;
//dispatch the job
if (size > (size_t)_MAX_BYTES){
malloc_alloc_first_hjstl::deallocate(mem, size);
return;
}
//else,solve it.
//first of all,i will find the free list's position
my_free_list = free_list + HJSTL_FREELIST_INDEX(size);
//change the list
new_header_pointer->free_list_link = my_free_list;
*my_free_list = new_header_pointer;
return;
}
//this is the second reallocate
static void* reallocate(void* old, size_t old_size, size_t new_size);
};//end of second allocator
//heihei,this is the default alloc,we will use this alloc in our project
typedef _malloc_alloc_second<> hjstl_alloc;
#endif //end of _HJ_STL_ALLOC_H_
上面是今天寫的代碼，很多内容複制了SGI的寫法，因為過于經典，在效率面前就不露三腳貓功夫了，下一節将接着實作refill函數和記憶體池函數，最後所有的記憶體操作除了不能使用之外都會使用我自己寫的一個記憶體池管理單元，我将單獨學習與記錄記憶體池部分。
——今天好傻，壓力很大，大三不好玩—
胡建，南開，2016
![C++數組引用C++數組引用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)