你不能不知道的内存分配，从全局概览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)