*1267365213* C++ STLのアロケーター(allocator)とか調べたり

2010/08/07
最終報告をこちらに
http://d.hatena.ne.jp/Dycoon/20100807

2010/07/11
Visual Studio 2008 でのReleaseモードでの実行に問題があることに気がつきました。
以下に現在わかっていることを書きました。
http://d.hatena.ne.jp/Dycoon/20100711


メモリーのAllocationについて理解しておくことで、
以下のような効用があるのではないかと考えています。
- メモリーの少ない環境でのメモリー確保失敗によるアプリケーションの停止の予防
- メモリーがハードウェア的に分割されている環境での効率のよい処理の記述

C++ではメモリーの確保などをカスタムに記述することも可能なので、
いろいろ実験して挙動を確認してみるのがよいかと思い、
STLでのアロケーターの使い方を含めていろいろ実験してみました。
また、ライブラリを設計する上で、アロケーターの扱いで
全体のコードの書き方が影響を受けるため、
（あとから、対応しようと思うと結構困ったことになったりすると思われます）
このあたりをよく理解する必要はあると考えています。

ActionScriptとかrubyとかガベージコレクションをおこなう言語では
アロケーションの処理自体を書くことはないと思いますがが、
一般的なアロケーターやコンテナがどんな動作をするか
考えておくとどのような記述をするのがよいかなど見えることもあるかと思います。
（配列の長さをできるだけ動的に変えないとか）

実験用のソースコード
http://www.rmake.net/dycoon/files/stlallocator/STLAllocatorSample20100228.zip
(Visual Studio 2008, Cygwinのg++-4で動作確認)

====

** メモリーアロケーションクラス（STL非依存部分）

アロケーターを記述するヘッダーファイルの先頭部分は次のようにしました。

>|cpp|

#pragma once

#include <stdlib.h>
#include <new>
#include <limits>
#include <string.h>
#include <iomanip>

#define DYCV_TMP_MAX max
#undef max

#define DYCV_TMP_MIN min
#undef min

||<

maxとminはlimitsのものとぶつかるためこのような処理をしています。
ヘッダーファイルの最後で次のようにして戻しています。

>|cpp|

#define max DYCV_TMP_MAX
#define min DYCV_TMP_MIN

||<

STL用のメモリー管理クラスの内部実装を記述するために
STLに依存しないメモリー管理クラスの抽象クラスを作りました。

>|cpp|
class TDAllocatorBase
{
public:

	TDAllocatorBase() {}
	virtual ~TDAllocatorBase() {}

	virtual void * Allocate(size_t size) = 0;

	virtual void Deallocate(void * p) = 0;
	
};

||<

これを実装して、TDAllocatorBaseを継承したクラスを
STLのアロケーターから操作します。

newなどで確保したメモリー領域をアライメントするための関数を用意しました。

>|cpp|

inline void * AlignedPointer(void * _p, size_t alsz)
{
	unsigned char * cp;
	unsigned char * alcp;
	void * ppt;

	cp = (unsigned char *)_p;
	alcp = (unsigned char *)(((size_t)(cp + alsz + sizeof(void *) - 1) / alsz) * alsz);
	ppt = (void *)(alcp - sizeof(void *));

	*(void * *)ppt = _p;

	return (void *)alcp;
}

inline void * UnAlignedPointer(void * _p)
{
	unsigned char * cp;
	void * ppt;
	cp = (unsigned char *)_p;

	cp = cp - sizeof(void *);
	ppt = *(void * *)cp;

	return ppt;
}

||<


new, deleteを使って、メモリー管理をおこなうクラスです。
カスタム実装のメモリー管理をおこないたいときと
デフォルトの処理を簡単に切り替えるようにします。

>|cpp|

// new delete allocator

class TDAllocatorNew : public TDAllocatorBase
{
private:
	size_t alignment;
	size_t count;

public:

	TDAllocatorNew() : alignment(128), count(0) {}
	TDAllocatorNew(size_t _alignment) : alignment(_alignment), count(0) {}
	virtual ~TDAllocatorNew() {}

	void SetAlignment(size_t alignment);
	size_t GetAlignment();

	virtual void * Allocate(size_t size);
	virtual void Deallocate(void * p);

	bool IsEmpty();

};


||<

実装部分は以下のとおりです。
>|cpp|

// new delete allocator

void TDAllocatorNew::SetAlignment(size_t alignment)
{
	this->alignment = alignment;
}

size_t TDAllocatorNew::GetAlignment()
{
	return alignment;
}

void * TDAllocatorNew::Allocate(size_t size)
{
	unsigned char * tp;

	tp = new unsigned char[size + alignment + sizeof(void *)];

	count++;

	return AlignedPointer((void *)tp, alignment);
}

void TDAllocatorNew::Deallocate(void * p)
{
	p = UnAlignedPointer(p);
	delete [] (unsigned char *)p;

	count--;
}

bool TDAllocatorNew::IsEmpty()
{
	if(count == 0)
	{
		return true;
	}

	return false;
}

||<

newとdeleteをラッピングしています。
あと、このアロケーターを通して何回メモリーが確保されたかどうかも
保存しています。

つぎに、Fit系のアルゴリズムでメモリーを確保するLinked Listによるアロケーターを
用意しました。

>|cpp|

// linked list allocator

struct TDAllocatorFitChunk;
typedef TDAllocatorFitChunk * PDAllocatorFitChunk;

struct TDAllocatorFitChunk
{
	PDAllocatorFitChunk next;
	PDAllocatorFitChunk prev;
	unsigned char * allocatedStart;
	unsigned char * freedStart;
	unsigned char * cunkEnd;
	size_t allocatedSize;

	void Init();

	void Remove();
	void InsertNext(PDAllocatorFitChunk nxt);
};

static const unsigned int DycNextFit = 0;
static const unsigned int DycFirstFit = 1;

class TDAllocatorFit : public TDAllocatorBase
{
private:
	size_t alignment;
	unsigned int fitType;
	bool antiFragmentation;
	size_t totalUsedSize;
	size_t totalAllocatedSize;

	unsigned char * memoryStart;
	unsigned char * memoryEnd;
	PDAllocatorFitChunk currentChunk;
	

	void MemInit();

public:

	TDAllocatorFit() : alignment(128), fitType(DycNextFit), antiFragmentation(true),
		memoryStart(NULL), memoryEnd(NULL) 
	{
		
	}

	TDAllocatorFit(size_t _alignment, unsigned int _fitType, bool _antiFragmentation,
			void * _memoryStart, void * _memoryEnd) : 
		alignment(_alignment), fitType(_fitType), antiFragmentation(_antiFragmentation),
		memoryStart((unsigned char *)_memoryStart), memoryEnd((unsigned char *)_memoryEnd) 
	{
		MemInit();
	}

	TDAllocatorFit(const TDAllocatorFit & a) : alignment(a.alignment), fitType(a.fitType), antiFragmentation(a.antiFragmentation),
		memoryStart(a.memoryStart), memoryEnd(a.memoryEnd) 
	{
		MemInit();
	}

	virtual ~TDAllocatorFit();

	void * GetMemoryStart();
	void * GetMemoryEnd();

	virtual void * Allocate(size_t size);
	virtual void Deallocate(void * p);

	size_t GetTotalUsedSize();
	size_t GetTotalAllocatedSize();

	size_t GetHeaderSize();

	bool IsEmpty();

};

||<

実装部分は以下のとおりです。

>|cpp|

// linked list allocator

void TDAllocatorFitChunk::Init()
{
	next = this;
	prev = this;
}

void TDAllocatorFitChunk::Remove()
{
	next->prev = prev;
	prev->next = next;
	next = this;
	prev = this;
}

void TDAllocatorFitChunk::InsertNext(PDAllocatorFitChunk nxt)
{
	nxt->next->prev = nxt->prev;
	nxt->prev->next = nxt->next;

	nxt->prev = this;
	nxt->next = next;
	next->prev = nxt;
	next = nxt;
}


TDAllocatorFit::~TDAllocatorFit()
{
	
}

void TDAllocatorFit::MemInit()
{
	PDAllocatorFitChunk top = (PDAllocatorFitChunk)memoryStart;
	currentChunk = top;

	top->Init();
	top->allocatedStart = memoryStart;
	top->freedStart = memoryStart + sizeof(TDAllocatorFitChunk);
	top->cunkEnd = memoryEnd;

	totalUsedSize = sizeof(TDAllocatorFitChunk);
	totalAllocatedSize = 0;
}

void * TDAllocatorFit::GetMemoryStart()
{
	return (void *)memoryStart;
}

void * TDAllocatorFit::GetMemoryEnd()
{
	return (void *)memoryEnd;
}

void * TDAllocatorFit::Allocate(size_t size)
{

	size_t sz;
	ptrdiff_t frsz;
	sz = size + GetHeaderSize();

	if(antiFragmentation)
	{
		size_t i;

		i = 1;
		while(size > i)
		{
			i = i << 1;
		}

		sz = i + GetHeaderSize();
	}

	PDAllocatorFitChunk top = currentChunk;

	if(fitType == DycNextFit)
	{
		top = currentChunk;
	}
	else if(fitType == DycFirstFit)
	{
		currentChunk = (PDAllocatorFitChunk)memoryStart;
		top = (PDAllocatorFitChunk)memoryStart;
	}

	while(top)
	{
		frsz = (ptrdiff_t)top->cunkEnd - (ptrdiff_t)top->freedStart;
		if(frsz > (ptrdiff_t)sz)
		{
			break;
		}
	
		top = top->next;
		if(top == currentChunk)
		{
			throw std::bad_alloc();
			return NULL;
		}
	}

	currentChunk = top;

	unsigned char * _p;
	PDAllocatorFitChunk nxt;

	_p = top->freedStart;

	::memset(top->freedStart, 0xac, sz);

	nxt = (PDAllocatorFitChunk)top->freedStart;
	nxt->Init();
	nxt->allocatedStart = top->freedStart;
	nxt->freedStart = nxt->allocatedStart + sz;
	nxt->cunkEnd = top->cunkEnd;
	nxt->allocatedSize = size;
	top->cunkEnd = nxt->allocatedStart;

	top->InsertNext(nxt);

	//
	unsigned char * cp;
	unsigned char * alcp;
	void * ppt;

	cp = (unsigned char *)_p;
	alcp = (unsigned char *)(((size_t)(cp + GetHeaderSize() - 1) / alignment) * alignment);
	ppt = (void *)(alcp - sizeof(void *));

	*(void **)ppt = (void *)_p;

	totalUsedSize += sz;
	totalAllocatedSize += size;

	return (void *)alcp;
}

void TDAllocatorFit::Deallocate(void * p)
{
	unsigned char * cp;
	cp = (unsigned char *)p;

	if((size_t)p < (size_t)memoryStart || (size_t)memoryEnd <= (size_t)p)
	{
		throw std::bad_exception();
	}

	cp = cp - sizeof(void *);
	
	PDAllocatorFitChunk top = (PDAllocatorFitChunk)*(void * *)cp;
	PDAllocatorFitChunk prev = top->prev;
	
	if((size_t)top <= (size_t)prev)
	{
		throw std::bad_exception();
	}

	prev->cunkEnd = top->cunkEnd;

	if((size_t)prev < (size_t)currentChunk)
	{
		currentChunk = prev;
	}

	top->Remove();

	totalUsedSize -= (size_t)top->freedStart - (size_t)top->allocatedStart;
	totalAllocatedSize -= top->allocatedSize;

	::memset(top, 0xed, (size_t)top->freedStart - (size_t)top->allocatedStart);
}

size_t TDAllocatorFit::GetTotalUsedSize()
{
	return totalUsedSize;
}

size_t TDAllocatorFit::GetTotalAllocatedSize()
{
	return totalAllocatedSize;
}

size_t TDAllocatorFit::GetHeaderSize()
{
	return alignment + sizeof(TDAllocatorFitChunk) + sizeof(void *);
}

bool TDAllocatorFit::IsEmpty()
{
	PDAllocatorFitChunk top = (PDAllocatorFitChunk)memoryStart;

	if(top->next == top)
	{
		return true;
	}

	return false;
}


||<

TDAllocatorFitChunkは確保されたメモリーの区間と、
まだ使用されていないメモリーの区間を保存する
構造体です。
TDAllocatorFitに、管理する対象のメモリー領域を与え、
そこからメモリーを確保します。
メモリーを確保する方法としては、Next FitとFirst Fitを
使うことができます。

Next Fitでは、メモリーを確保するときに、空いているメモリーを
前に確保したところから探します。
このアロケーターでは、開放がおこなわれた場合は
次に空いているメモリーを探し始める場所を一番手前で解放がおこなわれたところとしています。

First Fitでは、メモリーを確保するときに、空いているメモリーを
先頭から探しています。

使い方は以下のような感じです。

>|cpp|
#include "TDSTLAllocatorSample.h"

#include <iostream>
#include <vector>
#include <list>

class TDClass1
{
	int a;

public:

	TDClass1()
	{
		*gf << "TDClass1 Constructor " << (void*)this << std::endl;
	}

	~TDClass1()
	{
		*gf << "TDClass1 Destructor " << (void*)this << std::endl;
	}

	TDClass1(const TDClass1 & src) : a(src.a)
	{
		*gf << "TDClass1 Copy Constructor " << (void*)this << std::endl;
	}

	void SetA(int a)
	{
		this->a = a;
	}

	int GetA()
	{
		return a;
	}

};

void PrintAllMemory(unsigned char * d, size_t dsz)
{
	(*gf) << "memory dump" << std::endl;
	size_t i, isz;

	isz = dsz;
	for(i = 0; i < isz ; i++)
	{
		(*gf) << std::hex << std::setw(2) << std::setfill('0') << (int)d[i];
		if(i % 64 == 63)
		{
			(*gf) << std::endl;
		}
	}

	(*gf) << std::dec;
	(*gf) << std::endl;
	(*gf) << std::endl;

}

void PrintFitAllocatorUsedMap(TDAllocatorFit & a)
{
	(*gf) << "used memory map" << std::endl;

	char map[512];
	size_t i, isz;

	size_t sz;
	size_t ed;
	//size_t scale;
	void * start = a.GetMemoryStart();

	sz = (size_t)a.GetMemoryEnd() - (size_t)start;
	//scale = sz * sizeof(map);

	PDAllocatorFitChunk top;
	PDAllocatorFitChunk c;

	::memset(map, '0', sizeof(map));

	top = (PDAllocatorFitChunk)start;
	c = top;

	while(top)
	{
		size_t st;

		st = ((size_t)c->allocatedStart - (size_t)start) * sizeof(map) / sz;
		ed = ((size_t)c->freedStart - (size_t)start) * sizeof(map) / sz;

		::memset(&map[st], '1', ed - st + 1);
	
		c = c->next;
		if(c == top)
		{
			break;
		}
	}


	isz = sizeof(map);
	for(i = 0 ; i < isz ; i++)
	{
		(*gf) << map[i];
		if(i % 64 == 63)
		{
			(*gf) << std::endl;
		}
	}

	(*gf) << std::endl;
	(*gf) << std::endl;
}

void PrintFitAllocatorInfo(TDAllocatorFit & a)
{
	(*gf) << "Total Used Memory = " << a.GetTotalUsedSize() << std::endl;
	(*gf) << "Total Allocated Memory = " << a.GetTotalAllocatedSize() << std::endl;
	(*gf) << std::endl;
}

template<class TDContainer> void PrintClass1Container(TDContainer & v0)
{
	typename TDContainer::iterator i;
	typename TDContainer::iterator ied;

	ied = v0.end();
	for(i = v0.begin() ; i != ied ; i++)
	{
		(*gf) << "i->a = " << i->GetA() << " -> " << &*i << std::endl;
	}
	(*gf) << std::endl;
}

//
void STLAllocatorSample1_PlacementNew()
{
	std::cout << "STLAllocatorSample1_HowToUse" << std::endl;

	std::ofstream f("STLAllocatorSample1_PlacementNew.txt");

	gf = &f;

	//
	unsigned char d[256];
	::memset(d, 0xed, sizeof(d));
	TDAllocatorFit a(16, DycNextFit, false, d, d + sizeof(d));

	(*gf) << "MemoryStart = " << a.GetMemoryStart() << std::endl;
	(*gf) << "MemoryEnd = " << a.GetMemoryEnd() << std::endl;
	(*gf) << std::endl;

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);


	//
	TDClass1 * c0;

	c0 = (TDClass1 *)a.Allocate(sizeof(TDClass1));
	new(c0) TDClass1();

	c0->SetA(15);
	(*gf) << "c0->a = " << c0->GetA() << std::endl;
	(*gf) << std::endl;

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

	c0->~TDClass1();
	a.Deallocate((void *)c0);

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorInfo(a);

}


||<

これを実行すると"STLAllocatorSample1_PlacementNew.txt"に以下のような出力が得られます。

>|

MemoryStart = 0024FA4C
MemoryEnd = 0024FB4C

memory dump
4cfa24004cfa24004cfa240064fa24004cfb2400edededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed


used memory map
1111111111111111111111111111111111111111111111111000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000


Total Used Memory = 24
Total Allocated Memory = 0

TDClass1 Constructor 0024FA80
c0->a = 15

memory dump
64fa240064fa24004cfa240064fa240064fa2400edededed4cfa24004cfa240064fa240094fa24004cfb24000400000064fa24000f000000acacacacacacacac
acacacacacacacacedededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed


used memory map
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111100000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000


Total Used Memory = 72
Total Allocated Memory = 4

TDClass1 Destructor 0024FA80
memory dump
4cfa24004cfa24004cfa240064fa24004cfb2400edededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed


Total Used Memory = 24
Total Allocated Memory = 0



|<

"memory dump"は、アロケーターに渡しているメモリーの内容を16進数で出力しています。
"used memory map"は使用しているメモリーを表わしており、0が使っていない場所、
1が使っている場所です。
"MemoryStart"と"MemoryEnd"はアロケーターに渡されたメモリーのアドレスの始点と終点を表わしております。
"TDClass1 Constructor"は確保したクラスのコンストラクターで、そのあとの値は
インスタンスのアドレスを出力しています。
"TDClass1 Constructor"のアドレスが実際にemoryStart"と"MemoryEnd"の間にあることなどが確認できます。

** STL用のアロケーター

STL用のアロケーターの基本クラスとして以下のようなものを用意しました。

>|cpp|

// STL new delete allocator

template <class TDType> class TDSTLAllocator
{
public:
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	typedef TDType * pointer;
	typedef const TDType * const_pointer;
	typedef TDType & reference;
	typedef const TDType & const_reference;
	typedef TDType value_type;

	template <class TDOther> struct rebind { typedef TDSTLAllocator<TDOther> other; };

public:

	pointer address(reference v) const
	{
		return (&v);
	}

	const_pointer address(const_reference v) const
	{
		return (&v);
	}

	TDSTLAllocator() throw() {}

	TDSTLAllocator(const TDSTLAllocator<TDType> & src) throw() {}

	template<class TDOther> 
		TDSTLAllocator(const TDSTLAllocator<TDOther> & src) throw() {}

	TDSTLAllocator& operator=( const TDSTLAllocator& ha )
	{
		return *this;
	}

	pointer allocate(size_type _Count, const_pointer _Hint = 0)
	{
		unsigned char * tp;
		tp = new unsigned char[_Count * sizeof(TDType)];

		return (pointer)tp;
	}

	void construct(pointer _Ptr, const TDType & _Value)
	{
		new((void*)_Ptr) TDType(_Value);
	}

	void deallocate(pointer _Ptr, size_type _Count)
	{
		delete [] (unsigned char *)_Ptr;
	}

	void destroy(pointer _Ptr)
	{
		_Ptr->~TDType();
	}

	size_type max_size() const throw()
	{
		return std::numeric_limits<size_t>::max() / sizeof(TDType);
	}

	//

	template<class TDTmpType> struct TDDestroyer
	{
		TDSTLAllocator<TDTmpType> a;

		TDDestroyer(TDSTLAllocator<TDTmpType> _a) : a(_a) {}

		TDDestroyer(const TDDestroyer & _d) : a(_d.a) {}

		void operator() ( TDTmpType * p ) 
		{
			a.destroy(p);
			a.deallocate(p, 1);
		}
	};

	
	//template<class TDTmpType> void CreateNewInstance(boost::shared_ptr<TDTmpType> & sp, const TDTmpType & c)
	//{
	//	typename rebind<TDTmpType>::other oa(*this);
	//
	//	TDTmpType * p;
	//	p = (TDTmpType *)oa.allocate(1, 0);
	//	new(p) TDTmpType(c);
	//
	//	TDDestroyer<TDTmpType> d(oa);
	//
	//	sp = boost::shared_ptr<TDTmpType>(p, d, oa);
	//	
	//}
};

template <typename T1> bool operator==( const TDSTLAllocator<T1>& lhs, const TDSTLAllocator<T1>& rhs) throw()
{
	return (bool)true;
}

template <typename T1> bool operator!=( const TDSTLAllocator<T1>& lhs, const TDSTLAllocator<T1>& rhs) throw()
{
	return (bool)false;
}

||<

コメントアウトされている、CreateNewInstanceメソッドは
boost::shared_ptrのカウンター用のアロケーターを設定するというものです。

TDAllocatorBaseのポインタをスタティック変数に持つ
STL用のアロケーターを次のように定義します。

>|cpp|

// STL allocator with TDAllocatorBase.

template <class TDType> class TDSTLAllocatorStatic : public TDSTLAllocator<TDType>
{ 

public:

	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	typedef TDType * pointer;
	typedef const TDType * const_pointer;
	typedef TDType & reference;
	typedef const TDType & const_reference;
	typedef TDType value_type;

	template <class TDOther> struct rebind { typedef TDSTLAllocatorStatic<TDOther> other; };

	static PDAllocatorBase & GetAllocator()
	{
		static PDAllocatorBase a;
		return a;
	}

	TDSTLAllocatorStatic() throw() {}

	TDSTLAllocatorStatic(TDAllocatorBase & a) throw()
	{
		GetAllocator() = &a;
	}

	TDSTLAllocatorStatic(const TDSTLAllocatorStatic<TDType> & src) throw() {}

	template<class TDOther> 
		TDSTLAllocatorStatic(const TDSTLAllocatorStatic<TDOther> & src) throw()
	{
		GetAllocator() = TDSTLAllocatorStatic<TDOther>::GetAllocator();
	}

	TDSTLAllocatorStatic& operator=( const TDSTLAllocatorStatic& ha )
	{
		return *this;
	}

	pointer allocate(size_type _Count, const_pointer _Hint = 0)
	{
		(void)_Hint;
		return (pointer)GetAllocator()->Allocate(_Count * sizeof(TDType));
	}

	void deallocate(pointer _Ptr, size_type _Count)
	{
		(void)_Count;
		GetAllocator()->Deallocate(_Ptr);
	}

	//
	template<class TDTmpType> struct TDDestroyer
	{
		TDSTLAllocatorStatic<TDTmpType> a;

		TDDestroyer(TDSTLAllocatorStatic<TDTmpType> _a) : a(_a) {}

		TDDestroyer(const TDDestroyer & _d) : a(_d.a) {}

		void operator() ( TDTmpType * p ) 
		{
			a.destroy(p);
			a.deallocate(p, 1);
		}
	};

	//template<class TDTmpType> void CreateNewInstance(boost::shared_ptr<TDTmpType> & sp, const TDTmpType & c)
	//{
	//	typename rebind<TDTmpType>::other oa(*this);

	//	TDTmpType * p;
	//	//p = (TDTmpType *)oa.allocate(1, 0);
	//	p = (TDTmpType *)GetAllocator()->Allocate(sizeof(TDTmpType));
	//	//new(p) TDTmpType(c);
	//	oa.construct(p, TDTmpType(c));

	//	TDDestroyer<TDTmpType> d(oa);

	//	sp = boost::shared_ptr<TDTmpType>(p, d, oa);
	//	
	//}

	//template<class TDTmpType, class TDTmpAllocator> void CreateNewInstance(
	//		TDTmpAllocator * ta, boost::shared_ptr<TDTmpType> & sp, const TDTmpType & c)
	//{
	//	typename rebind<TDTmpType>::other oa(*this);

	//	TDTmpType * p;
	//	p = (TDTmpType *)ta->Allocate(sizeof(TDTmpType));
	//	//new(p) TDTmpType(c);
	//	oa.construct(p, TDTmpType(c));

	//	TDDestroyer<TDTmpType> d(oa);

	//	sp = boost::shared_ptr<TDTmpType>(p, d, oa);
	//	
	//}

	//template<class TDTmpType> void CreateNewInstance(boost::shared_ptr<TDTmpType> & sp)
	//{
	//	typename rebind<TDTmpType>::other oa(*this);

	//	TDTmpType * p;
	//	//p = (TDTmpType *)oa.allocate(1, 0);
	//	p = (TDTmpType *)GetAllocator()->Allocate(sizeof(TDTmpType), (void *)&sp);
	//	new(p) TDTmpType(*this);
	//	//oa.construct(p, TDTmpType(c));

	//	TDDestroyer<TDTmpType> d(oa);

	//	sp = boost::shared_ptr<TDTmpType>(p, d, oa);
	//	
	//}

	//template<class TDTmpType, class TDTmpAllocator> void CreateNewInstance(
	//		TDTmpAllocator * ta, boost::shared_ptr<TDTmpType> & sp)
	//{
	//	typename rebind<TDTmpType>::other oa(*this);

	//	TDTmpType * p;
	//	p = (TDTmpType *)ta->Allocate(sizeof(TDTmpType));
	//	new(p) TDTmpType(*this);
	//	//oa.construct(p, TDTmpType(c));

	//	TDDestroyer<TDTmpType> d(oa);

	//	sp = boost::shared_ptr<TDTmpType>(p, d, oa);
	//	
	//}

};

template <typename T1> bool operator==( const TDSTLAllocatorStatic<T1>& lhs, const TDSTLAllocatorStatic<T1>& rhs) throw()
{
	return (bool)true;
}

template <typename T1> bool operator!=( const TDSTLAllocatorStatic<T1>& lhs, const TDSTLAllocatorStatic<T1>& rhs) throw()
{
	return (bool)false;
}


||<

STLのアロケーターは状態を持ってはいけないとか、
コンテナーは同じ型ならばアロケーターは等しいはずとして扱うとかあるため、
static変数に持たせるのはC++の標準に準拠しているかどうかは微妙なのかなと思います。
たぶん、TDAllocatorBaseから派生したクラスをグローバル変数におくなどして
扱う必要があるのかなと思います。
ここでは、ある程度使い方に気をつけるものとして
このような使い方をすることにします。

使い方として灰化のような形です。

>|cpp|

//
void STLAllocatorSample1_STLAllocation()
{
	std::cout << "STLAllocatorSample1_STLAllocation" << std::endl;

	std::ofstream f("STLAllocatorSample1_STLAllocation.txt");

	gf = &f;

	//
	unsigned char d[256];
	::memset(d, 0xed, sizeof(d));
	TDAllocatorFit a(16, DycNextFit, false, d, d + sizeof(d));
	typedef TDSTLAllocatorStatic<TDClass1> TDSA;
	TDSA sa(a);

	(*gf) << "MemoryStart = " << a.GetMemoryStart() << std::endl;
	(*gf) << "MemoryEnd = " << a.GetMemoryEnd() << std::endl;
	(*gf) << std::endl;

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorInfo(a);

	//
	TDClass1 * c0;

	c0 = (TDClass1 *)sa.allocate(1, NULL);
	sa.construct((TDSA::pointer)c0, TDClass1());

	c0->SetA(15);
	(*gf) << "c0->a = " << c0->GetA() << std::endl;
	(*gf) << std::endl;

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

	sa.destroy(c0);
	sa.deallocate((TDSA::pointer)c0, 1);

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

}

||<

これの実行結果は以下のとおりです。

>|
MemoryStart = 0024FA4C
MemoryEnd = 0024FB4C

memory dump
4cfa24004cfa24004cfa240064fa24004cfb2400edededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed


Total Used Memory = 24
Total Allocated Memory = 0

TDClass1 Constructor 0024F93C
TDClass1 Copy Constructor 0024FA80
TDClass1 Destructor 0024F93C
c0->a = 15

memory dump
64fa240064fa24004cfa240064fa240064fa2400edededed4cfa24004cfa240064fa240094fa24004cfb24000400000064fa24000f000000acacacacacacacac
acacacacacacacacedededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed


used memory map
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111100000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000


Total Used Memory = 72
Total Allocated Memory = 4

TDClass1 Destructor 0024FA80
memory dump
4cfa24004cfa24004cfa240064fa24004cfb2400edededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed


used memory map
1111111111111111111111111111111111111111111111111000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000


Total Used Memory = 24
Total Allocated Memory = 0

|<

C++の標準からは外れるかもしれませんがVC++では
statefulなallocatorが使えるようなので、statefulなものも用意しておきます。

>|cpp|

// Statefull STL allocator with TDAllocatorBase.

template <class TDType> class TDSTLAllocatorStatefull : public TDSTLAllocator<TDType>
{ 

public:

	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	typedef TDType * pointer;
	typedef const TDType * const_pointer;
	typedef TDType & reference;
	typedef const TDType & const_reference;
	typedef TDType value_type;

	template <class TDOther> struct rebind { typedef TDSTLAllocatorStatefull<TDOther> other; };

	PDAllocatorBase a;

	TDSTLAllocatorStatefull() throw() {}

	TDSTLAllocatorStatefull(TDAllocatorBase & a) throw() : a(&a) {}

	TDSTLAllocatorStatefull(const TDSTLAllocatorStatefull<TDType> & src) throw() : a(src.a) {}

	template<class TDOther> 
	TDSTLAllocatorStatefull(const TDSTLAllocatorStatefull<TDOther> & src) throw() : a(src.a)
	{
		
	}

	TDSTLAllocatorStatefull& operator=( const TDSTLAllocatorStatefull& ha )
	{
		a = ha.a;
		return *this;
	}

	pointer allocate(size_type _Count, const_pointer _Hint = 0)
	{
		(void)_Hint;
		return (pointer)a->Allocate(_Count * sizeof(TDType));
	}

	void deallocate(pointer _Ptr, size_type _Count)
	{
		(void)_Count;
		a->Deallocate(_Ptr);
	}

	//
	template<class TDTmpType> struct TDDestroyer
	{
		TDSTLAllocatorStatefull<TDTmpType> a;

		TDDestroyer(TDSTLAllocatorStatefull<TDTmpType> _a) : a(_a) {}

		TDDestroyer(const TDDestroyer & _d) : a(_d.a) {}

		void operator() ( TDTmpType * p ) 
		{
			a.destroy(p);
			a.deallocate(p, 1);
		}
	};

	//template<class TDTmpType> void CreateNewInstance(boost::shared_ptr<TDTmpType> & sp, const TDTmpType & c)
	//{
	//	typename rebind<TDTmpType>::other oa(*this);

	//	TDTmpType * p;
	//	//p = (TDTmpType *)oa.allocate(1, 0);
	//	p = (TDTmpType *)GetAllocator()->Allocate(sizeof(TDTmpType));
	//	//new(p) TDTmpType(c);
	//	oa.construct(p, TDTmpType(c));

	//	TDDestroyer<TDTmpType> d(oa);

	//	sp = boost::shared_ptr<TDTmpType>(p, d, oa);
	//	
	//}

	//template<class TDTmpType, class TDTmpAllocator> void CreateNewInstance(
	//		TDTmpAllocator * ta, boost::shared_ptr<TDTmpType> & sp, const TDTmpType & c)
	//{
	//	typename rebind<TDTmpType>::other oa(*this);

	//	TDTmpType * p;
	//	p = (TDTmpType *)ta->Allocate(sizeof(TDTmpType));
	//	//new(p) TDTmpType(c);
	//	oa.construct(p, TDTmpType(c));

	//	TDDestroyer<TDTmpType> d(oa);

	//	sp = boost::shared_ptr<TDTmpType>(p, d, oa);
	//	
	//}

	//template<class TDTmpType> void CreateNewInstance(boost::shared_ptr<TDTmpType> & sp)
	//{
	//	typename rebind<TDTmpType>::other oa(*this);

	//	TDTmpType * p;
	//	//p = (TDTmpType *)oa.allocate(1, 0);
	//	p = (TDTmpType *)GetAllocator()->Allocate(sizeof(TDTmpType), (void *)&sp);
	//	new(p) TDTmpType(*this);
	//	//oa.construct(p, TDTmpType(c));

	//	TDDestroyer<TDTmpType> d(oa);

	//	sp = boost::shared_ptr<TDTmpType>(p, d, oa);
	//	
	//}

	//template<class TDTmpType, class TDTmpAllocator> void CreateNewInstance(
	//		TDTmpAllocator * ta, boost::shared_ptr<TDTmpType> & sp)
	//{
	//	typename rebind<TDTmpType>::other oa(*this);

	//	TDTmpType * p;
	//	p = (TDTmpType *)ta->Allocate(sizeof(TDTmpType));
	//	new(p) TDTmpType(*this);
	//	//oa.construct(p, TDTmpType(c));

	//	TDDestroyer<TDTmpType> d(oa);

	//	sp = boost::shared_ptr<TDTmpType>(p, d, oa);
	//	
	//}

};

template <typename T1> bool operator==( const TDSTLAllocatorStatefull<T1>& lhs, const TDSTLAllocatorStatefull<T1>& rhs) throw()
{
	return lhs.a == rhs.a;
}

template <typename T1> bool operator!=( const TDSTLAllocatorStatefull<T1>& lhs, const TDSTLAllocatorStatefull<T1>& rhs) throw()
{
	return lhs.a != rhs.a;
}

||<

メンバー変数に"PDAllocatorBase a;"を持たせています。
"operator=="と"operator!="は状態が等しいかどうかを判定するために使います。
具体的な例についてはまた後で触れたいと思います。

vectorクラスに対して、カスタムアロケーターを使ってみます。
>|cpp|

//
void STLAllocatorSample1_STLVector()
{
	std::cout << "STLAllocatorSample1_STLVector" << std::endl;

	std::ofstream f("STLAllocatorSample1_STLVector.txt");

	gf = &f;

	//
	unsigned char d[256];
	::memset(d, 0xed, sizeof(d));
	TDAllocatorFit a(16, DycNextFit, false, d, d + sizeof(d));
	typedef TDSTLAllocatorStatic<TDClass1> TDSA;
	TDSA sa(a);

	(*gf) << "MemoryStart = " << a.GetMemoryStart() << std::endl;
	(*gf) << "MemoryEnd = " << a.GetMemoryEnd() << std::endl;
	(*gf) << std::endl;

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);


	//
	typedef std::vector<TDClass1, TDSTLAllocatorStatic<TDClass1> > TDV;
	TDV v0(sa);
	TDV::iterator i;
	TDV::iterator ied;
	int ct;

	v0.resize(3);
	(*gf) << "&v0[0] = " << &v0[0] << std::endl;

	ct = 0;
	ied = v0.end();
	for(i = v0.begin() ; i != ied ; i++)
	{
		i->SetA(ct);
		ct++;
	}

	PrintClass1Container(v0);

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

}

||<

>|
MemoryStart = 0024FA4C
MemoryEnd = 0024FB4C

memory dump
4cfa24004cfa24004cfa240064fa24004cfb2400edededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed


used memory map
1111111111111111111111111111111111111111111111111000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000


Total Used Memory = 24
Total Allocated Memory = 0

TDClass1 Constructor 0024F7B4
TDClass1 Copy Constructor 0024FA80
TDClass1 Copy Constructor 0024FA84
TDClass1 Copy Constructor 0024FA88
TDClass1 Destructor 0024F7B4
&v0[0] = 0024FA80
i->a = 0 -> 0024FA80
i->a = 1 -> 0024FA84
i->a = 2 -> 0024FA88

memory dump
64fa240064fa24004cfa240064fa240064fa2400edededed4cfa24004cfa240064fa24009cfa24004cfb24000c00000064fa2400000000000100000002000000
acacacacacacacacacacacacacacacacedededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed
edededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededed


used memory map
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111110000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000


Total Used Memory = 80
Total Allocated Memory = 12

TDClass1 Destructor 0024FA80
TDClass1 Destructor 0024FA84
TDClass1 Destructor 0024FA88

|<

vectorをresizeするときに一時変数のコンストラクタが作られて、
それをコピーコンストラクタでコピーしている様子が見えます。

>|
TDClass1 Constructor 0024F7B4
TDClass1 Copy Constructor 0024FA80
TDClass1 Copy Constructor 0024FA84
TDClass1 Copy Constructor 0024FA88
TDClass1 Destructor 0024F7B4
|<

vectorのpush_backを使用するときのメモリーの動きを見てみます。

>|cpp|

//
void STLAllocatorSample1_STLVectorPushBack()
{
	std::cout << "STLAllocatorSample1_STLVectorPushBack" << std::endl;

	std::ofstream f("STLAllocatorSample1_STLVectorPushBack.txt");

	gf = &f;

	//
	unsigned char d[1024 * 12];
	::memset(d, 0xed, sizeof(d));
	TDAllocatorFit a(16, DycNextFit, false, d, d + sizeof(d));
	typedef TDSTLAllocatorStatic<TDClass1> TDSA;
	TDSA sa(a);

	(*gf) << "MemoryStart = " << a.GetMemoryStart() << std::endl;
	(*gf) << "MemoryEnd = " << a.GetMemoryEnd() << std::endl;
	(*gf) << std::endl;

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);


	//
	typedef std::vector<TDClass1, TDSTLAllocatorStatic<TDClass1> > TDV;
	TDV v0(sa);

	size_t j, jsz;
	size_t oldCapacity = 0;

	jsz = 640;

	for(j = 0 ; j < jsz ; j++)
	{
		v0.push_back(TDClass1());
		v0.back().SetA(j);

		if(oldCapacity < v0.capacity())
		{
			PrintFitAllocatorUsedMap(a);

			oldCapacity = v0.capacity();
		}
	}

	PrintClass1Container(v0);

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

}

||<

やっていることは、vectorを初期状態からひたすらpush_backで
後ろに要素を追加するということです。
出力は長いので見るべき部分だけを抜き出します。

>|

used memory map
1100000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1111000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1101110000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1100011100000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1111000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1101111000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1100001111000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1111110000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1100011111100000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1100000000111111100000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1111111111000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1100000001111111111111100000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1100000000000000000000111111111111111111000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1100000000000000000000000000000000000001111111111111111111111111
1100000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1111111111111111111111111111111111111110000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1100000000000000000000000000000000000011111111111111111111111111
1111111111111111111111111111100000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1100000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000111111111111111111111111111111111111
1111111111111111111111111111111111111111111111000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

used memory map
1100000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000001111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111100000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

|<

初期状態からpush_backでvectorの要素を増やしていった場合は、
容量が足りないと元のサイズから何倍かした領域を新たに確保して
そこにコピーするということをおこなっているようです。
最初のうちは、確保する領域にオーバーヘッドがあるため、
先頭の領域が繰り返し使われますが、サイズが大きくなってくると
確保できる用量が前のほうになくなるため、後ろに
ずれていきます。

次にreserveでメモリーを確保してから、push_backで追加してみます。

>|cpp|

//
void STLAllocatorSample1_STLVectorPushBackReserved()
{
	std::cout << "STLAllocatorSample1_STLVectorPushBackReserved" << std::endl;

	std::ofstream f("STLAllocatorSample1_STLVectorPushBackReserved.txt");

	gf = &f;

	//
	unsigned char d[1024 * 12];
	::memset(d, 0xed, sizeof(d));
	TDAllocatorFit a(16, DycNextFit, false, d, d + sizeof(d));
	typedef TDSTLAllocatorStatic<TDClass1> TDSA;
	TDSA sa(a);

	(*gf) << "MemoryStart = " << a.GetMemoryStart() << std::endl;
	(*gf) << "MemoryEnd = " << a.GetMemoryEnd() << std::endl;
	(*gf) << std::endl;

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);


	//
	typedef std::vector<TDClass1, TDSTLAllocatorStatic<TDClass1> > TDV;
	TDV v0(sa);

	size_t j, jsz;
	size_t oldCapacity = 0;

	v0.reserve((sizeof(d) - a.GetHeaderSize() - sizeof(TDAllocatorFitChunk) - 1) / sizeof(TDClass1));

	jsz = v0.capacity();

	for(j = 0 ; j < jsz ; j++)
	{
		v0.push_back(TDClass1());
		v0.back().SetA(j);

		if(oldCapacity < v0.capacity())
		{
			PrintFitAllocatorUsedMap(a);

			oldCapacity = v0.capacity();
		}
	}

	PrintClass1Container(v0);

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

}

||<

メモリーの確保の状態は以下のとおりです。

>|
used memory map
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
|<

メモリーの全体領域をくまなく使えることが見て取れます。

vectorをできるだけ大きい要領で使いたい場合は、
reserveで最大使うと思われるメモリーを確保しておくと
よいと思われます。


listクラスを使ってみます。

>|cpp|

//
void STLAllocatorSample1_STLList()
{
	std::cout << "STLAllocatorSample1_STLList" << std::endl;

	std::ofstream f("STLAllocatorSample1_STLList.txt");

	gf = &f;

	//
	unsigned char d[256];
	::memset(d, 0xed, sizeof(d));
	TDAllocatorFit a(16, DycNextFit, false, d, d + sizeof(d));
	typedef TDSTLAllocatorStatic<TDClass1> TDSA;
	TDSA sa(a);

	(*gf) << "MemoryStart = " << a.GetMemoryStart() << std::endl;
	(*gf) << "MemoryEnd = " << a.GetMemoryEnd() << std::endl;
	(*gf) << std::endl;

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);


	//
	typedef std::list<TDClass1, TDSTLAllocatorStatic<TDClass1> > TDV;
	TDV v0(sa);
	TDV::iterator i;
	TDV::iterator ied;
	int ct;

	v0.resize(3);

	ct = 0;
	ied = v0.end();
	for(i = v0.begin() ; i != ied ; i++)
	{
		i->SetA(ct);
		ct++;
	}

	PrintClass1Container(v0);

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

}

||<

メモリーの確保状況は以下のとおりです。

>|
memory dump
64fa24000cfb24004cfa240064fa240064fa2400edededed9cfa24004cfa240064fa24009cfa24009cfa24000c00000064fa2400c0fa240030fb2400acacacac
acacacacacacacacacacacacacacacacd4fa240064fa24009cfa2400d4fa2400d4fa24000c000000acacacacacacacac9cfa2400f0fa240080fa240000000000
acacacacacacacac0cfb24009cfa2400d4fa24000cfb24000cfb24000c000000d4fa240030fb2400c0fa240001000000acacacacacacacacacacacacacacacac
4cfa2400d4fa24000cfb240044fb24004cfb24000c000000acacacacacacacac0cfb240080fa2400f0fa240002000000acacacacacacacacedededededededed


used memory map
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111000000000000000

|<

とっている要素は3で最初にvectorを使ってみたときと同じですが
それに比べるとかなり大きいメモリーを消費していることが見て取れます。
これは、listはメモリーを1つの要素ごとにばらばらにとるため、
このアロケーターだとその分のオーバーヘッドがかなり大きくなってしまっているためと思われます。
配列状にメモリーを用意して、使用しているかしてないかだけのフラグを持たせたような
アロケーターが効率よく働くかもしれません。
ただ、listの場合はallocatorクラスで定義されているrebindを使って型を変更させるため、
要素のサイズが変わることを注意する必要があるかと思います。

以下のページで
http://www.tantalon.com/pete.htm
http://www.tantalon.com/pete/customallocators.ppt
STLのアロケーターにおける状態つきアロケーターを考慮した
STLコンテナの実装についてふれられています。
それは、list::splice関数や（コレクションクラス）::swapなどの
挙動を見ればよいとのこと。
（あとは、よくテストしてくださいという感じ。動けば正義？）

で、listクラスのspliceの動作を見てみます。

>|cpp|

//
void STLAllocatorSample1_STLListSplice()
{
	std::cout << "STLAllocatorSample1_STLListSplice" << std::endl;

	std::ofstream f("STLAllocatorSample1_STLListSplice.txt");

	gf = &f;

	//
	unsigned char d[512];
	::memset(d, 0xed, sizeof(d));
	TDAllocatorFit a(16, DycNextFit, false, d, d + sizeof(d));
	typedef TDSTLAllocatorStatic<TDClass1> TDSA;
	TDSA sa(a);

	(*gf) << "MemoryStart = " << a.GetMemoryStart() << std::endl;
	(*gf) << "MemoryEnd = " << a.GetMemoryEnd() << std::endl;
	(*gf) << std::endl;

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);


	//
	typedef std::list<TDClass1, TDSTLAllocatorStatic<TDClass1> > TDV;
	TDV v0(sa);
	TDV v1(sa);
	TDV::iterator i;
	TDV::iterator ied;
	int ct;

	v0.resize(3);
	ct = 0;
	ied = v0.end();
	for(i = v0.begin() ; i != ied ; i++)
	{
		i->SetA(ct);
		ct++;
	}

	v1.resize(3);
	ied = v1.end();
	for(i = v1.begin() ; i != ied ; i++)
	{
		i->SetA(ct);
		ct++;
	}

	(*gf) << "v0" << std::endl;
	PrintClass1Container(v0);

	(*gf) << "v1" << std::endl;
	PrintClass1Container(v1);

	//
	i = v0.begin();
	i++;
	v0.splice(i, v1);

	//
	(*gf) << "v0" << std::endl;
	PrintClass1Container(v0);

	(*gf) << "v1" << std::endl;
	PrintClass1Container(v1);


	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

}

||<

この動作結果で注意するべきところは以下の部分です。

>|
v0
i->a = 0 -> 0024F9F8
i->a = 1 -> 0024FA38
i->a = 2 -> 0024FA68

v1
i->a = 3 -> 0024FAA8
i->a = 4 -> 0024FAD8
i->a = 5 -> 0024FB18

v0
i->a = 0 -> 0024F9F8
i->a = 3 -> 0024FAA8
i->a = 4 -> 0024FAD8
i->a = 5 -> 0024FB18
i->a = 1 -> 0024FA38
i->a = 2 -> 0024FA68

v1

|<

v1の中身をv0に移し変えているのですが、
v1の要素をそのままv0に持っていっていることがわかります。
アロケーターの状態が同じ場合（operator==がtrueを返す場合）
Visual C++ 2008 と Cygwinのg++-4 (GCC) 4.3.2 20080827 (beta) 2 では
同じように動作します。

これが状態つきのアロケーターで状態が違う場合どうなるかを見てみます。

>|cpp|

void STLAllocatorSample1_STLListSpliceStatefull()
{
	std::cout << "STLAllocatorSample1_STLListSpliceStatefull" << std::endl;

	std::ofstream f("STLAllocatorSample1_STLListSpliceStatefull.txt");

	gf = &f;

	try
	{
		//
		unsigned char d0[512];
		unsigned char d1[512];
		::memset(d0, 0xed, sizeof(d0));
		::memset(d1, 0xed, sizeof(d1));
		TDAllocatorFit a0(16, DycNextFit, false, d0, d0 + sizeof(d0));
		TDAllocatorFit a1(16, DycNextFit, false, d1, d1 + sizeof(d1));
		typedef TDSTLAllocatorStatefull<TDClass1> TDSA;
		TDSA sa0(a0);
		TDSA sa1(a1);

		(*gf) << "a0 MemoryStart = " << a0.GetMemoryStart() << std::endl;
		(*gf) << "a0 MemoryEnd = " << a0.GetMemoryEnd() << std::endl;
		(*gf) << std::endl;

		(*gf) << "a1 MemoryStart = " << a1.GetMemoryStart() << std::endl;
		(*gf) << "a1 MemoryEnd = " << a1.GetMemoryEnd() << std::endl;
		(*gf) << std::endl;

		(*gf) << "d0" << std::endl;
		PrintAllMemory(d0, sizeof(d0));
		PrintFitAllocatorUsedMap(a0);
		PrintFitAllocatorInfo(a0);
		(*gf) << std::endl;

		(*gf) << "d1" << std::endl;
		PrintAllMemory(d1, sizeof(d1));
		PrintFitAllocatorUsedMap(a1);
		PrintFitAllocatorInfo(a1);
		(*gf) << std::endl;
		

		//
		typedef std::list<TDClass1, TDSA > TDV;
		TDV v0(sa0);
		TDV v1(sa1);
		TDV::iterator i;
		TDV::iterator ied;
		int ct;

		v0.resize(3);
		ct = 0;
		ied = v0.end();
		for(i = v0.begin() ; i != ied ; i++)
		{
			i->SetA(ct);
			ct++;
		}

		v1.resize(3);
		ied = v1.end();
		for(i = v1.begin() ; i != ied ; i++)
		{
			i->SetA(ct);
			ct++;
		}

		(*gf) << "v0" << std::endl;
		PrintClass1Container(v0);

		(*gf) << "v1" << std::endl;
		PrintClass1Container(v1);

		//
		i = v0.begin();
		i++;
		v0.splice(i, v1);

		//
		(*gf) << "v0" << std::endl;
		PrintClass1Container(v0);

		(*gf) << "v1" << std::endl;
		PrintClass1Container(v1);


		(*gf) << "d0" << std::endl;
		PrintAllMemory(d0, sizeof(d0));
		PrintFitAllocatorUsedMap(a0);
		PrintFitAllocatorInfo(a0);
		(*gf) << std::endl;

		(*gf) << "d1" << std::endl;
		PrintAllMemory(d1, sizeof(d1));
		PrintFitAllocatorUsedMap(a1);
		PrintFitAllocatorInfo(a1);
		(*gf) << std::endl;
	}
	catch(...)
	{
		(*gf) << "exception called." << std::endl;
		(*gf) << "maybe cannot use stateful allocator." << std::endl;
	}
}

||<

gccではoperator==がfalseの時点で例外を送出するようです。
VC2008では以下のように出力されます。

>|
v0
i->a = 0 -> 0020F998
i->a = 1 -> 0020F9C8
i->a = 2 -> 0020FA08

v1
i->a = 3 -> 0020F788
i->a = 4 -> 0020F7C8
i->a = 5 -> 0020F7F8

v0
i->a = 0 -> 0020F998
i->a = 3 -> 0020FA38
i->a = 4 -> 0020FA78
i->a = 5 -> 0020FAA8
i->a = 1 -> 0020F9C8
i->a = 2 -> 0020FA08

v1

|<

v1の内容がv0へ移動するときにアドレスが、
v0で使っているアロケーターで確保されているものになっています。
つまり、新しい要素を作ってコピーしてコピー元を削除しているようです。

断片化のテストをおこなってみました。

>|cpp|

//

void STLAllocatorSample1_Fragmentation(unsigned int fitType, bool antiFragmentation)
{
	unsigned char d[1024 * 16];
	::memset(d, 0xed, sizeof(d));
	TDAllocatorFit a(16, fitType, antiFragmentation, d, d + sizeof(d));

	(*gf) << "MemoryStart = " << a.GetMemoryStart() << std::endl;
	(*gf) << "MemoryEnd = " << a.GetMemoryEnd() << std::endl;
	(*gf) << std::endl;

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

	const size_t sz = 1024;
	void * p[sz * 2];
	size_t i, isz;

	isz = sz;

	try
	{
		for(i = 0 ; i < isz ; i++)
		{
			p[i * 2 + 0] = a.Allocate(i + 1);
			p[i * 2 + 1] = a.Allocate(1);
			a.Deallocate(p[i * 2 + 0]);
		}
	}
	catch(...)
	{
		(*gf) << "exception called." << std::endl;
		(*gf) << "maybe cannot allocate." << std::endl;
	}

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

	(*gf) << "iteration count = " << i << std::endl;

}

void STLAllocatorSample1_Fragmentation2(unsigned int fitType, bool antiFragmentation)
{
	unsigned char d[1024 * 16];
	::memset(d, 0xed, sizeof(d));
	TDAllocatorFit a(16, fitType, antiFragmentation, d, d + sizeof(d));

	(*gf) << "MemoryStart = " << a.GetMemoryStart() << std::endl;
	(*gf) << "MemoryEnd = " << a.GetMemoryEnd() << std::endl;
	(*gf) << std::endl;

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

	const size_t sz = 1024;
	void * p[sz * 2];
	size_t i, isz;

	isz = sz;

	try
	{
		for(i = 0 ; i < isz ; i++)
		{
			p[i * 2 + 0] = a.Allocate(i + 1);
			p[i * 2 + 1] = a.Allocate(i + 1);
			a.Deallocate(p[i * 2 + 0]);
		}
	}
	catch(...)
	{
		(*gf) << "exception called." << std::endl;
		(*gf) << "maybe cannot allocate." << std::endl;
	}

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

	(*gf) << "iteration count = " << i << std::endl;

}

void STLAllocatorSample1_NoFragmentation(unsigned int fitType, bool antiFragmentation)
{
	unsigned char d[1024 * 16];
	::memset(d, 0xed, sizeof(d));
	TDAllocatorFit a(16, fitType, antiFragmentation, d, d + sizeof(d));

	(*gf) << "MemoryStart = " << a.GetMemoryStart() << std::endl;
	(*gf) << "MemoryEnd = " << a.GetMemoryEnd() << std::endl;
	(*gf) << std::endl;

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

	const size_t sz = 1024;
	void * p[sz * 2];
	size_t i, isz;

	isz = sz;

	try
	{
		for(i = 0 ; i < isz ; i++)
		{
			p[i * 2 + 0] = a.Allocate(i + 1);
			p[i * 2 + 1] = a.Allocate(1);
		}
	}
	catch(...)
	{
		(*gf) << "exception called." << std::endl;
		(*gf) << "maybe cannot allocate." << std::endl;
	}

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

	(*gf) << "iteration count = " << i << std::endl;

}

void STLAllocatorSample1_NoFragmentation2(unsigned int fitType, bool antiFragmentation)
{
	unsigned char d[1024 * 16];
	::memset(d, 0xed, sizeof(d));
	TDAllocatorFit a(16, fitType, antiFragmentation, d, d + sizeof(d));

	(*gf) << "MemoryStart = " << a.GetMemoryStart() << std::endl;
	(*gf) << "MemoryEnd = " << a.GetMemoryEnd() << std::endl;
	(*gf) << std::endl;

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

	const size_t sz = 1024;
	void * p[sz * 2];
	size_t i, isz;

	isz = sz;

	try
	{
		for(i = 0 ; i < isz ; i++)
		{
			p[i * 2 + 0] = a.Allocate(i + 1);
			p[i * 2 + 1] = a.Allocate(i + 1);
		}
	}
	catch(...)
	{
		(*gf) << "exception called." << std::endl;
		(*gf) << "maybe cannot allocate." << std::endl;
	}

	PrintAllMemory(d, sizeof(d));
	PrintFitAllocatorUsedMap(a);
	PrintFitAllocatorInfo(a);

	(*gf) << "iteration count = " << i << std::endl;

}

void STLAllocatorSample1_Fragmentation()
{
	std::cout << "STLAllocatorSample1_Fragmentation" << std::endl;

	{
		std::ofstream f("STLAllocatorSample1_Fragmentation_NextFit_Frag.txt");
		gf = &f;

		STLAllocatorSample1_Fragmentation(DycNextFit, false);
	}

	{
		std::ofstream f("STLAllocatorSample1_Fragmentation_NextFit_AntiFrag.txt");
		gf = &f;

		STLAllocatorSample1_Fragmentation(DycNextFit, true);
	}

	{
		std::ofstream f("STLAllocatorSample1_Fragmentation_FirstFit_Frag.txt");
		gf = &f;

		STLAllocatorSample1_Fragmentation(DycFirstFit, false);
	}

	{
		std::ofstream f("STLAllocatorSample1_Fragmentation_FirstFit_AntiFrag.txt");
		gf = &f;

		STLAllocatorSample1_Fragmentation(DycFirstFit, true);
	}

	{
		std::ofstream f("STLAllocatorSample1_Fragmentation2_NextFit_Frag.txt");
		gf = &f;

		STLAllocatorSample1_Fragmentation2(DycNextFit, false);
	}

	{
		std::ofstream f("STLAllocatorSample1_Fragmentation2_NextFit_AntiFrag.txt");
		gf = &f;

		STLAllocatorSample1_Fragmentation2(DycNextFit, true);
	}

	{
		std::ofstream f("STLAllocatorSample1_Fragmentation2_FirstFit_Frag.txt");
		gf = &f;

		STLAllocatorSample1_Fragmentation2(DycFirstFit, false);
	}

	{
		std::ofstream f("STLAllocatorSample1_Fragmentation2_FirstFit_AntiFrag.txt");
		gf = &f;

		STLAllocatorSample1_Fragmentation2(DycFirstFit, true);
	}

	//

	{
		std::ofstream f("STLAllocatorSample1_NoFragmentation_NextFit_Frag.txt");
		gf = &f;

		STLAllocatorSample1_NoFragmentation(DycNextFit, false);
	}

	{
		std::ofstream f("STLAllocatorSample1_NoFragmentation_NextFit_AntiFrag.txt");
		gf = &f;

		STLAllocatorSample1_NoFragmentation(DycNextFit, true);
	}

	{
		std::ofstream f("STLAllocatorSample1_NoFragmentation_FirstFit_Frag.txt");
		gf = &f;

		STLAllocatorSample1_NoFragmentation(DycFirstFit, false);
	}

	{
		std::ofstream f("STLAllocatorSample1_NoFragmentation_FirstFit_AntiFrag.txt");
		gf = &f;

		STLAllocatorSample1_NoFragmentation(DycFirstFit, true);
	}

	{
		std::ofstream f("STLAllocatorSample1_NoFragmentation2_NextFit_Frag.txt");
		gf = &f;

		STLAllocatorSample1_NoFragmentation2(DycNextFit, false);
	}

	{
		std::ofstream f("STLAllocatorSample1_NoFragmentation2_NextFit_AntiFrag.txt");
		gf = &f;

		STLAllocatorSample1_NoFragmentation2(DycNextFit, true);
	}

	{
		std::ofstream f("STLAllocatorSample1_Fragmentation2_FirstFit_Frag.txt");
		gf = &f;

		STLAllocatorSample1_Fragmentation2(DycFirstFit, false);
	}

	{
		std::ofstream f("STLAllocatorSample1_NoFragmentation2_FirstFit_AntiFrag.txt");
		gf = &f;

		STLAllocatorSample1_NoFragmentation2(DycFirstFit, true);
	}

	
}

||<

やってみたことは、
メモリー確保方法の違い、
Next Fit と First Fitで確保できるメモリーサイズの違い、
フラグメンテーション対策の有無の組み合わせで実行してみました。

メモリー確保方法は以下の4パターンを試しました。

パターン1
>|cpp|
		for(i = 0 ; i < isz ; i++)
		{
			p[i * 2 + 0] = a.Allocate(i + 1);
			p[i * 2 + 1] = a.Allocate(1);
			a.Deallocate(p[i * 2 + 0]);
		}
||<

パターン2
>|cpp|
		for(i = 0 ; i < isz ; i++)
		{
			p[i * 2 + 0] = a.Allocate(i + 1);
			p[i * 2 + 1] = a.Allocate(i + 1);
			a.Deallocate(p[i * 2 + 0]);
		}
||<

パターン3
>|cpp|
		for(i = 0 ; i < isz ; i++)
		{
			p[i * 2 + 0] = a.Allocate(i + 1);
			p[i * 2 + 1] = a.Allocate(1);
		}
||<

パターン4
>|cpp|
		for(i = 0 ; i < isz ; i++)
		{
			p[i * 2 + 0] = a.Allocate(i + 1);
			p[i * 2 + 1] = a.Allocate(i + 1);
		}
||<
前半は、確保と開放を繰り返して、メモリーが断片化しやすくしたもの
後半は、確保のみで、メモリーが断片化しないもの。

フラグメンテーション対策ですが
これは、メモリーを確保するサイズを2のn乗で必要なメモリーを確保できる最小値
で確保するというものです。
これは、むしろ確保できるメモリーの量は小さくなってしまいました。
同じ領域を再利用する可能性が増えると踏んでいたのですが、
確保するメモリーの総量自体が増えてしまって、効果が出なかったようです。
これについてはなんともいえないという結果になっています。

確保できたメモリーの量を表にしてみます。

|*|*パターン1|*パターン2|*パターン3|*パターン4|
|*First Fit|312(14064)|4186(8214)|6440(16320)|8281(16269)|
|*Next Fit|112(5064)|4186(8214)|6440(16320)|8281(16269)|

()内は消費したメモリーの量です。
メモリーは16kbyteあるのですが、
パターン1、パターン2のように
メモリー確保の方法しだいでは小さい量のメモリーしか
確保できないということが見て取れます。

パターン3, 4は消費したメモリーの量は16kbyteに近く
よくメモリーを使えています。

確保を一度におこなってから、開放を一度におこなうという形を取れると
断片化は起こらないと考えられます。
そのため、寿命が同じメモリーに対しては
同じアロケーターを使うことで断片化を防ぐことができると考えられます。

しかしながら、状態を持たないアロケーターだと
これを実現するのは無理なのではないかと思います。
そういう意味では状態つきのアロケーターが使えると
いろいろやりやすいなとは思います。

断片化を防ぐ方法としては、
- vectorで確保するデータ長を一定にする
- 型ごとに細かくallocatorを分ける
などでもある程度対処可能と思われます。

あと、関連性の高いデータがまとまっていると、
プロセッサーごとにメモリーが分かれているような環境で
効率が高い処理を得られるのではないかと考えております。

そうなると状態なしでやる場合は、メモリーを動かせる機構などを用意して
コンパクションなどをおこなえるようにするのがよいかもしれません。
STLのallocatorでは
>|cpp|
typedef TDType * pointer;
||<
のような形でallocatorで定義したpointerを
コンテナーで使用するので、可能そうだなとは思います。

C++ STLのアロケーター(allocator)とか調べたり(2)に続く
http://d.hatena.ne.jp/Dycoon/20100301#1267455397


*1267455397* C++ STLのアロケーター(allocator)とか調べたり(2)

すみません。長すぎて切れていることに気がついていませんでした。
まあ、ソースコードなどが多すぎるので削るなど編集したほうがいいのでしょうが・・・。
とりあえず長すぎて切れていた分を以下に続けました。

====

とりあえず、固定長のメモリーを使用した断片化対策では、
細かく型を分ける必要があるかと思います。
たとえば以下のような形かと思います。

>|cpp|

//
template<class TDType> class TDVec3
{
public:
	TDType x;
	TDType y;
	TDType z;

	TDVec3()
	{
	
	}

	TDVec3(TDType _x, TDType _y, TDType _z)
	{
		x = _x;
		y = _y;
		z = _z;
	}

	void Print(std::ofstream & f)
	{
		f << "(" << x << ", " << y << ", " << z << "), ";
	}

};

template<class TDType>void TDVec3Print(std::ofstream & f, TDType & d)
{
	typename TDType::iterator i, ied;

	ied = d.end();
	for(i = d.begin() ; i != ied ; i++)
	{
		i->Print(f);
	}

	f << std::endl;
}

template<class TDType> class TDClass2
{
public:
	struct TVA : public TDVec3<TDType>
	{
		TVA(){}

		TVA(TDType _x, TDType _y, TDType _z) : TDVec3<TDType>(_x, _y, _z) {}

	};

	struct TVB : public TDVec3<TDType>
	{
		TVB(){}

		TVB(TDType _x, TDType _y, TDType _z) : TDVec3<TDType>(_x, _y, _z) {}

	};

	typedef TDSTLAllocatorStatic<TVA> TVAA;
	typedef TDSTLAllocatorStatic<TVB> TVBA;

	typedef std::vector<TVA, TVAA> TVAV;
	typedef std::list<TVB, TVBA> TVBV;

	TVAV v0;
	TVBV v1;

	TDClass2(TVAA a0, TVBA a1) : v0(a0), v1(a1)
	{
		
	}

	void Init()
	{
		v0.resize(4);
		v0[0] = TVA(0.0, 1.0, 2.0);
		v0[1] = TVA(3.0, 4.0, 5.0);
		v0[2] = TVA(6.0, 7.0, 8.0);
		v0[3] = TVA(9.0, 10.0, 11.0);

		v1.push_back(TVB(12.0, 13.0, 14.0));
		v1.push_back(TVB(15.0, 16.0, 17.0));
		v1.push_back(TVB(18.0, 19.0, 20.0));
		v1.push_back(TVB(21.0, 22.0, 23.0));

	}

	void Print(std::ofstream & f)
	{
		f << "v0" << std::endl;
		TDVec3Print(f, v0);

		f << "v1" << std::endl;
		TDVec3Print(f, v1);
	}

};

void STLAllocatorSample1_TypeAllocator()
{
	std::cout << "STLAllocatorSample1_TypeAllocator" << std::endl;

	std::ofstream f("STLAllocatorSample1_TypeAllocator.txt");
	gf = &f;

	typedef TDClass2<float> TDC;

	unsigned char d0[512];
	unsigned char d1[512];
	::memset(d0, 0xed, sizeof(d0));
	::memset(d1, 0xed, sizeof(d1));
	TDAllocatorFit a0(16, DycNextFit, false, d0, d0 + sizeof(d0));
	TDAllocatorFit a1(16, DycNextFit, false, d1, d1 + sizeof(d1));
	typedef TDSTLAllocatorStatefull<TDClass1> TDSA;
	TDC::TVAA sa0(a0);
	TDC::TVBA sa1(a1);

	(*gf) << "a0 MemoryStart = " << a0.GetMemoryStart() << std::endl;
	(*gf) << "a0 MemoryEnd = " << a0.GetMemoryEnd() << std::endl;
	(*gf) << std::endl;

	(*gf) << "a1 MemoryStart = " << a1.GetMemoryStart() << std::endl;
	(*gf) << "a1 MemoryEnd = " << a1.GetMemoryEnd() << std::endl;
	(*gf) << std::endl;

	(*gf) << "d0" << std::endl;
	PrintAllMemory(d0, sizeof(d0));
	PrintFitAllocatorUsedMap(a0);
	PrintFitAllocatorInfo(a0);
	(*gf) << std::endl;

	(*gf) << "d1" << std::endl;
	PrintAllMemory(d1, sizeof(d1));
	PrintFitAllocatorUsedMap(a1);
	PrintFitAllocatorInfo(a1);
	(*gf) << std::endl;

	//
	TDC c(sa0, sa1);

	c.Init();

	c.Print((*gf));

	(*gf) << "d0" << std::endl;
	PrintAllMemory(d0, sizeof(d0));
	PrintFitAllocatorUsedMap(a0);
	PrintFitAllocatorInfo(a0);
	(*gf) << std::endl;

	(*gf) << "d1" << std::endl;
	PrintAllMemory(d1, sizeof(d1));
	PrintFitAllocatorUsedMap(a1);
	PrintFitAllocatorInfo(a1);
	(*gf) << std::endl;

}

||<

以下のような形で

>|cpp|
	struct TVA : public TDVec3<TDType>
	{
		TVA(){}

		TVA(TDType _x, TDType _y, TDType _z) : TDVec3<TDType>(_x, _y, _z) {}

	};
||<

型を再定義してその型のアロケーターを作るという形になりそうです。
コンストラクタを再度定義しなければいけないのが多少面倒でしょうか。

結構奥が深い話だなと感じているので、今後どれだけ突っ込むかはわかりませんが
とりあえず今わかっている範囲をまとめてみました。

C++  STLのアロケーター(allocator)とか調べたり(1)
http://d.hatena.ne.jp/Dycoon/20100228#1267365213



*1278825696* 「C++ STLのアロケーター(allocator)とか調べたり」に問題があることに気がついた

以下にある
http://d.hatena.ne.jp/Dycoon/20100228
「C++ STLのアロケーター(allocator)とか調べたり」で使用しているテストプログラムに
問題があることに気がつきました。
Releaseモードで実行するとプログラムが停止するというものです。
公開の前にReleaseで実行していれば気がついたはずなので、
この点に関しては大変申し訳なく思います。

※ ちょっとわかったことがありましたので、そのことについて書いてみました。 http://d.hatena.ne.jp/Dycoon/20100801


なぜReleaseモードで動作しないかについて今わかっている範囲で説明したいと思います。
基本的にはランタイムライブラリに何を使うかで問題が起こっているようです。
リリース版のランタイム（コンパイルオプション/MT, /MD）と
デバッグ版のランタイム（コンパイルオプション/MTd, /MDd）でSTL関連の挙動が違うことで起こっています。


1つ目の違いはvectorが生成されたときのメモリー確保の挙動です。
デバッグ版ランタイムではこの時点ではメモリーを確保しませんが、
リリース版ランタイムではこの時点で少量のメモリーを確保します。
テストプログラムではぎりぎりまでメモリーを使おうとしていたため、
この分で計算が合わなくなり、メモリーが足りなくなるということが起こりました。


2つ目の違いは正確に挙動を理解しているわけではありませんが
同じテンプレートでテンプレート引数が違うアロケーターへ
削除処理を呼びにいくことがあるようで、
確保したアロケーターと別のアロケーターに開放処理を
投げてしまうという動作をするようです。
これだと、メモリーを分割したアロケーターや、状態を持つアロケーターは
使えないということになるので、デバッグ版と動作が違いすぎるように思いますが、
とりあえず、現状うまく動作していないようです。
もうちょっと調べる必要があるかもしれませんが。


*1280669119* 「C++ STLのアロケーター(allocator)とか調べたり」に問題があることに気がついた2

先日の日記で
http://d.hatena.ne.jp/Dycoon/20100711

「C++ STLのアロケーター(allocator)とか調べたり」
http://d.hatena.ne.jp/Dycoon/20100228
で使用しているテストプログラムが
リリース版のランタイムを使用するようにすると
問題があることに気がつきましたが、
いくつか作業をおこなっていくうちにわかったことがありますので
とりあえず現時点でのことを書いておこうかと思います。


以下により単純化した再現のプログラムを用意しました。

====

http://www.rmake.net/dycoon/files/stlallocator/AllocatorVectorTest.zip
std::vectorに独自のアロケーターを渡し、
メモリーがどのように確保されるかを標準出力に出力するというものです。
Debugモードではstd::vector::resizeで確保した5byte分しか確保の要求は来ませんが、
Releaseモードではstd::_Aux_contを確保する分の4byteが追加され
最大で9byteのメモリーを確保します。


http://www.rmake.net/dycoon/files/stlallocator/AllocatorTypeTest.zip
こちらでは、アロケーターにスタティックな値を持たせ、
メモリーの確保と開放がどのようにおこなわれるかを確認しました。
Debugモードでは確保時のスタティックな変数の値と、
開放時のスタティック変数の値が同じである様子が見て取れます。
Releaseモードではアロケーターをstd::_Aux_contにrebindして
使用するようで、テンプレート引数がstd::_Aux_contであるアロケーターの
Static変数が、型の違うアロケーターから上書きされてしまう様子が見て取れます。


以下はAllocatorTypeTest.zipのプログラムが出力する内容です。
>||
TStaticBehavior Constructor
TStaticBehavior Constructor
constructior0 this : 0020FBE0, old : 0, new : 0, pt = 00B86074
constructior0 this : 0020FBCF, old : 0, new : 0, pt = 00B86074
TStaticBehavior Constructor
constructior1 this : 0020FC0C, old : 3, new : 0, pt = 00B8609C
allocate this : 0020FC0C, index : 0, pt = 00B8609C
constructior0 this : 0020FC10, old : 0, new : 0, pt = 00B86074
constructior0 this : 0020FBE0, old : 1, new : 1, pt = 00B86078
constructior0 this : 0020FBCF, old : 1, new : 1, pt = 00B86078
constructior1 this : 0020FBF4, old : 0, new : 1, pt = 00B8609C　　<- ここでstd::_Aux_contのスタティック変数を上書きしてしまっている。
allocate this : 0020FBF4, index : 1, pt = 00B8609C
constructior0 this : 0020FBF8, old : 1, new : 1, pt = 00B86078
allocate this : 0020FC10, index : 0, pt = 00B86074
allocate this : 0020FBF8, index : 1, pt = 00B86078
deallocate this : 0020FBF8, index : 1, pt = 00B86078
deallocate this : 0020FBF4, index : 1, pt = 00B8609C
deallocate this : 0020FC10, index : 0, pt = 00B86074
deallocate this : 0020FC0C, index : 1, pt = 00B8609C
TStaticBehavior Destructor
TStaticBehavior Destructor
TStaticBehavior Destructor
||<

以前のサンプルプログラムではスタティック変数は外部から渡された
メモリー管理クラスへのポインタを持たせているため、
そのポインタが上書きされて、std::_Aux_cont確保時に使用したメモリー管理クラスのインスタンスと
std::_Aux_cont開放時に使用するメモリー管理クラスのインスタンスが別のものになってしまっているということが
起こっているようです。


回避方法の案も考えてみました。
http://www.rmake.net/dycoon/files/stlallocator/AllocatorTypeAvoidedTest20100801.zip
こちらも中身について簡単に解説します。
アロケーターのコンストラクタで、スタティック変数（メモリー管理クラスへのポインタなど）をコピーするかどうかを
記述します。
>|cpp|
    TDSTLAllocator(const TDSTLAllocator<TDType> & src) throw()
    {
        if(GetOverWrite() || GetIndex() == 0x7fffffff)
        {
            std::cout << "constructior0 this : " << (void *)this << ", old : " << GetIndex() << ", new : " << src.GetIndex() << ", pt = " << &GetIndex() << std::endl;
            GetIndex() = src.GetIndex();
        }
    }
||<
GetOverWrite()は上書きをおこなうかどうかを指定するもので、
これがtrueの場合(デフォルトでtrue、std::_Aux_cont以外のクラスではtrue、std::_Aux_contではfalseになるようにする)
スタティック変数を常にコピー、そうでない場合は最初だけコピーします。
GetOverWrite()は以下のように定義します。
>|cpp|
    static bool & GetOverWrite()
    {
        static bool overWrite = true;
        return overWrite;
    }
||<
プログラムの開始時にstd::_Aux_contのアロケーターの値を設定するようにします。
例では以下のような形です。
>|cpp|
void InitAuxCont()
{
#ifdef _HAS_ITERATOR_DEBUGGING
#if !_HAS_ITERATOR_DEBUGGING
    TDSTLAllocator<std::_Aux_cont> a0;
    TDSTLAllocator<std::_Aux_cont>::GetIndex() = 1;
    TDSTLAllocator<std::_Aux_cont>::GetOverWrite() = false;
#endif
#endif
}


int main()
{
    InitAuxCont();

    AllocatorTypeTest();
   
    return 0;
}
||<
_HAS_ITERATOR_DEBUGGINGの有無と値を見てこの処理をおこなうかどうかを指定しています。


これによりリリースのランタイムを使った場合にstd::_Aux_contのアロケーターを上書きするという問題については
最初に指定したものが使われ続けるため解消されます。
それ以外のアロケーターに関しては、たとえばローカル変数をメモリーの確保先に指定した場合でも
必要に応じて上書きできるため動作します。


現在マイクロソフトのサポートに連絡していますので
書くべき内容がまた出てきたら書きたいと思います。