[C++知识库]二、allocator的实现原理

以下内容主要是根据侯捷老师的教学视频所总结的：

最原始的写法

#inclide<cstddef>
#include<iostream>
using namespace std;

class First {
public:
    First(int x):i(x){};
    void* operator new(size_t); //注意啊，这个地方其实有个问题，
    //理论来说要先有对象才能调用这个函数，这就很不合理，我在new的时
    //侯压根还没对象呢。
    void operator delete(void*, size_t);//注意这个参数必须这么写
private:
    First* next;//为了内存块之间的链接多出的一个指针
    static First* freeStore; //内存单链表的首地址
    static const int Chunk; //第一次申请时分配的个数
    int i;//自己本身的成员变量
};

First* First::freeStore=0;
const int First::Chunk=24; //类静态成员初始化

void* First::operator new(size_t size)
{
    First *p;
    if (!freeStore)//没有内存的话，那就分配一大块
    {
        size_t chunk=Chunk* size;//这个size就是sizeof(First)
        //下面这个解释一下，chunk代表字节数，而一个char正好一个字节，
        //理论来说也可以直接malloc(chunk), 然后将首地址转化为First
        //类型，然后就是是内存块的首地址。
        freeStore=p=reinterpret_cast<First*>(new char[chunk]);
        // 把内存块切块，然后用链表指针链起来
      	for(;p!=&freeStore[Chunk-1];++p)//freeStore[n-1]会自动按
      	//找类型size*n找打对应位置。
            p->next=p+1;
        p->next=0;
    }
    p=freeStore;
    freeStore=freeStore->next;
    return p;
}

void First::operator delete(void* p,size_t)
{
    //这个就是把用过的数据查到链表头就行了。
    (static_cast<First*>(p))->next=freeStore;
    freeStore=static_cast<First*>(p);
}

int main()
{
	size_t const N = 100;
	First* p[N];
	for (int i = 0; i < N; ++i)
		p[i] = new Screen(i);

	for (int i = 0; i < 10; ++i)
		cout << p[i] << endl;

	for (int i = 0; i < N; ++i)
	{
		delete p[i];
	}
	return 0;
}

优化后的写法

上面有个问题就是，你一个对象必须要包含一个指针成员变量，第一、虽然省去了cookie, 但是也增加了内存使用量，接下就要利用一种技术就是嵌入式指针的方式，说起来很炫酷，其实就是一块内存复用。

struct person
{
	int age;
	string name;
};
class second {
private:
	union //记得内存复用
	{person item;
	person* next;}

public:
	static void* operator new(size_t size);//看看这里就改成static
	static void operator delete(void* deadObject, size_t size);

private:
	static const int BLOCK_SIZE;
	static Second* headOfFreeList;
};

second* second::headOfFreeList;
const int second::BLOCK_SIZE = 512;

void* second::operator new(size_t size)
{
	//继承时考虑的，先不看
	if (size != sizeof(second)) return ::operator new(size);

	second* p = headOfFreeList;
	if (p) headOfFreeList = p->next;
	else {
		second* newBlock = static_cast<second*>(::operator new(BLOCK_SIZE * sizeof(second)));//这里又开始用全局operator new, 等效于malloc
		//分割做链表
		for (int i = 1; i < BLOCK_SIZE - 1; ++i)
			newBlock[i].next = &newBlock[i + 1]; //要理解unino的用法，不然睁眼瞎
		newBlock[BLOCK_SIZE - 1].next = 0;//结束list
		p = newBlock;
		headOfFreeList = &newBlock[1];
	}
	return p;
}

void second::operator delete(void* deadObject, size_t size)
{
	if (deadObject == 0) return;
	if (size != sizeof(second)) {
		::operator delete(deadObject);
		return;
	}

	Airplane* carcass = static_cast<second*>(deadObject);

	carcass->next = headOfFreeList;
	headOfFreeList = carcass;
}

最后的版本

可以看到，通过内存复用，指针已经省了，但是耦合度比较高，下面继续改进

#include<iostream>
using namespace std;

//将具体动作封装为一个类
struct obj{struct obj* next;}; //单链表
class Allocator
{
public:
	void* allocate(size_t);
	void deallocate(void*, size_t);
private:
	obj* freeStore = nullptr; //包含一个单链表指针
	const int CHUNK = 5;
};

void* Allocator::allocate(size_t size)
{
	obj* p;//定一个单链表指针
	if (!freeStore) {
		size_t chunk = CHUNK * size;
		freeStore = p = (obj*)malloc(chunk);//这里就用malloc了
		//将分配得来的一块当做linked list般，小块小块串接起来
		for (int i = 0; i < (CHUNK - 1); ++i) {
			p->next = (obj*)((char*)p + size);//这个为什么转为char*是因为单链表的对象里面是一个指针4个字节，所以如果不转的话p+size就会到p+4*size这个地址，就错了。
			p = p->next;
		}
		p->next = nullptr;
	}
	p = freeStore;
	freeStore = freeStore->next;
	return p;
}

void Allocator::deallocate(void* p, size_t size)
{
	((obj*)p)->next = freeStore;
	freeStore = (obj*)p;
}


//直接调用分配的类即可
class Foo {
public:
	long L;
	string str;
	static Allocator myAlloc;
public:
	Foo(long l) :L(l){}
	static void* operator new(size_t size)
	{
		return myAlloc.allocate(size);
	}
	static void operator delete(void* pdead,size_t size)
	{
		return myAlloc.deallocate(pdead,size);
	}
};
Allocator Foo::myAlloc;

int main()
{
	Foo* p[100];
	for (int i = 0; i < 23; ++i) {
		p[i] = new Foo(i);
		cout << p[i] << " " << p[i]->L << endl;
	}

	for (int i = 0; i < 23; ++i) {
		delete p[i];
	}

	return 0;
}