一、二级空间配置器中的内存池结构

（1）内存池初始状态

在这里插入图片描述

（2）当外界使用内存池

my_list.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
#include"my_alloc.h"   
#include"my_iterator.h"
#include"my_construct.h" 

#ifndef MY_LIST_H
#define MY_LIST_H

namespace pzj
{
template<class _Ty,class _A = alloc >
class mylist
{

private:
	struct _Node;
	typedef struct _Node *  _Nodeptr;
	struct _Node
	{
		_Nodeptr _Prev,_Next;
		_Ty      _Value;
	};

	struct _Acc;
	struct _Acc
	{
		typedef struct _Node *& _Nodepref;
		typedef _Ty &           _Vref;
		static _Vref _Value(_Nodeptr _P)
		{
			return (*_P)._Value;
		}
		static _Nodepref _Prev(_Nodeptr _P)
		{
			return (*_P)._Prev;
		}
		static _Nodepref _Next(_Nodeptr _P)
		{
			return (*_P)._Next;
		}
	};
public:
	typedef _Ty          value_type;
	typedef _Ty &        reference;
	typedef _Ty *        pointer;
	typedef const _Ty &  const_reference;
	typedef const _Ty *  const_pointer;

	typedef _A           allocator_type;

	typedef pzj::simple_alloc<_Node,_A> data_allocate;
public:
	class iterator;
	class const_iterator;
	class const_iterator :  public pzj::_Bidit<_Ty,int>
	{
	public:
		const_iterator(_Nodeptr _P = NULL):_Ptr(_P) {}
		const_reference operator*() const 
		{
			return _Acc::_Value(_Ptr);
		}
		const_pointer operator->() const 
		{
			return (&**this);
		}
		const_iterator operator++()
		{
			_Ptr = _Acc::_Next(_Ptr);
			return *this;
		}
		const_iterator operator++(int)
		{
			const_iterator _Tmp = *this;
			++*this;
			return _Tmp;
		}

		const_iterator operator--()
		{
			_Ptr = _Acc::_Prev(_Ptr);
			return *this;
		}
		const_iterator operator--(int)
		{
			const_iterator _Tmp = *this;
			--*this;
			return _Tmp;
		}

		bool operator==(const const_iterator &_X) const
		{
			return (this->_Ptr == _X._Ptr);
		}
		bool operator!=(const const_iterator &_X) const
		{
			return !(*this == _X);
		}
		_Nodeptr _Mynode() const 
		{
			return _Ptr;
		}
	protected:
		_Nodeptr _Ptr;
	};
	class iterator : public const_iterator
	{
	public:
		iterator(_Nodeptr _P = NULL):const_iterator(_P) {}
		reference operator*() const 
		{
			return _Acc::_Value(this->_Ptr);
		}
		pointer operator->() const 
		{
			return (&**this);
		}
		iterator operator++()
		{
			this->_Ptr = _Acc::_Next(this->_Ptr);
			return *this;
		}
		iterator operator++(int)
		{
			iterator _Tmp = *this;
			++*this;
			return _Tmp;
		}

		iterator operator--()
		{
			this->_Ptr = _Acc::_Prev(this->_Ptr);
			return *this;
		}
		iterator operator--(int)
		{
			iterator _Tmp = *this;
			--*this;
			return _Tmp;
		}

		bool operator==(const iterator &_X) const
		{
			return (this->_Ptr == _X._Ptr);
		}
		bool operator!=(const iterator &_X) const
		{
			return !(*this == _X);
		}
	};
public:
	iterator begin() { return iterator(_Acc::_Next(_Head));}
	iterator end() { return iterator(_Head);}
	const_iterator begin() const { return const_iterator(_Acc::_Next(_Head));}
	const_iterator end() const { return const_iterator(_Head);}


public:
	mylist():_Size(0),_Head(_Buynode()) {}

	~mylist()
	{
		clear();
		_Freenode(_Head);
		_Head = NULL;
	}

	typedef const_iterator _It;

	reference front() { return *begin();}
	const_reference front() const { return *begin();}
	
	reference back() { return *--end();}
	const_reference back() const { return *--end();}

	void push_front(const _Ty _X)
	{
		insert(begin(),_X);
	}
	void push_back(const _Ty &_X)
	{
		insert(end(),_X);
	}
	void insert(iterator _P,size_t _N,const _Ty &_X)
	{
		for(int i = 0;i<_N;++i)
		{
			insert(_P,_X);
		}
	}
	void insert(iterator _P,const _Ty *_F, const _Ty *_L)
	{
		for(; _F != _L; ++_F)
		{
			insert(_P,*_F);
		}
	}
	void insert(iterator _P,_It _F, _It _L)
	{
		for(; _F != _L; ++_F)
		{
			insert(_P,*_F);
		}
	}
	iterator insert(iterator _P,const _Ty &_X)
	{
		_Nodeptr _S = _P._Mynode();
		_Acc::_Prev(_S)  = _Buynode(_Acc::_Prev(_S),_S);
		_S = _Acc::_Prev(_S);
		_Acc::_Next(_Acc::_Prev(_S)) = _S;
		//_Acc::_Value(_S) = _X;
		construct(&_Acc::_Value(_S),_X);
		_Size+=1;
		return iterator(_S);
	}
	void clear()
	{
		erase(begin(),end());
	}
	void pop_back()
	{
		erase(--end());
	}
	void pop_front()
	{
		erase(begin());
	}
	void erase(iterator _F, iterator _L)
	{
		for(; _F != _L; )
		{
			erase(_F++);
		}
	}
	void remove(const _Ty &_X)
	{
		iterator _F = begin(), _L = end();
		for(; _F != _L; )
		{
			if(*_F == _X)
			{
				erase(_F++);
			}
			else
			{
				++_F;
			}
		}
	}
	iterator erase(iterator _P)
	{
		_Nodeptr _S = _P++._Mynode();// 
		_Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
		_Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);
		destroy(&_Acc::_Value(_S));
		_Freenode(_S);
		_Size-=1;
		return _P;// 
	}

private:
	_Nodeptr _Buynode(_Nodeptr _Parg = NULL, _Nodeptr _Narg = NULL)
	{
		//_Nodeptr _S = (_Nodeptr)malloc(sizeof(_Node));
		//使用默认的二级空间配置器
		_Nodeptr _S = data_allocate::allocate(1);// malloc 
		_Acc::_Prev(_S) = _Parg == NULL ? _S:_Parg;
		_Acc::_Next(_S) = _Narg == NULL ? _S:_Narg;
		return _S;
	}
	void _Freenode(_Nodeptr _P)
	{
		data_allocate::deallocate(_P,1);
	}

private:
	_Nodeptr _Head;
	size_t   _Size;
	_A       allocator;
};

}
#endif

Demo.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include"my_list.h"
#include"my_alloc.h"
#include "my_construct.h"
#include <iostream>
using namespace std;

int main()
{
	pzj::mylist<int> ilist;
	ilist.push_back(1);

	cout << *ilist.begin() << endl;
	return 0;
}

二、流程分析

  1. 程序运行时调用ilist的默认构造函数
  2. mylist()调用_Buynode()初始化_Head
  3. _Buynode()中调用（simple_alloc<_node , pzj::alloc>）data_allocate::allocate(1)；为_Head申请空间
  4. （simple_alloc<_node , pzj::alloc>）data_allocate::allocate(1)调用（__default_alloc_template<0, 0>默认的二级空间配置器）alloc::allocate(sizeof(T) * n);（其中T是Node类型：12字节）
  5. 12 > 128字节为假，使用二级空间适配器申请空间，将得到的空间还给_Head（细节代码注释见）
  6. 此时mylist()函数结束，ilist初始化完成

三、使用中的内存池

在这里插入图片描述

四、完整代码

（1）类型萃取

my_type_traits.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#ifndef MY_TYPE_TRAITS_H
#define MY_TYPE_TRAITS_H
namespace pzj
{
	struct __true_type {};		//真
	struct __false_type {};		//假

	//自设计类型：大部分是假的无关紧要的类型（人话：有关紧要）
	template<class type> 
	struct __type_traits
	{
		typedef __true_type  this_dummy_member_must_be_first;
		typedef __false_type  has_trivial_default_constructor;
		typedef __false_type  has_trivial_copy_constructor;
		typedef __false_type  has_trivial_assignment_operator;
		typedef __false_type  has_trivial_destructor;
		typedef __false_type  is_POD_type; // struct int 
	};

	//内置类型：基本上都是真的无关紧要的类型（人话：无关紧要）
	template<> struct __type_traits<char>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};

	template<> struct __type_traits<signed char>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};

	template<> struct __type_traits<unsigned char>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};

	template<> struct __type_traits<short>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};

	template<> struct __type_traits<unsigned short>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	template<> struct __type_traits<int>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	template<> struct __type_traits<unsigned int>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	template<> struct __type_traits<long int>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	template<> struct __type_traits<unsigned long int>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};

	template<> struct __type_traits<long long>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	template<> struct __type_traits<unsigned long long>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	template<> struct __type_traits<float>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};

	template<> struct __type_traits<double>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};

	template<> struct __type_traits<long double>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	//所有的指针类型：真的无关紧要
	template<class T>
	struct __type_traits<T*>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
}
#endif


（2）迭代器

my_iterator.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#ifndef MY_ITERATOR_H
#define MY_ITERATOR_H

namespace pzj
{

typedef int ptrdiff_t;

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};


template<class _C, class _Ty, class _D = ptrdiff_t, class _Pointer = _Ty*,
	class _Reference = _Ty&>
struct iterator
{
	typedef _C          iterator_category;
	typedef _Ty         value_type;
	typedef _D          difference_type;
	typedef _Pointer    pointer;
	typedef _Reference  reference;
};

template<class _Iterator>
struct iterator_traits
{
	iterator_traits() {}
	typedef typename _Iterator::iterator_category iterator_category;
	typedef typename _Iterator::value_type        value_type;
	typedef typename _Iterator::difference_type   differce_type;
	typedef typename _Iterator::pointer           pointer;
	typedef typename _Iterator::reference         reference;
};
template<class T>
struct iterator_traits<T*>
{
	iterator_traits() {}
	typedef typename random_access_iterator_tag iterator_category;
	typedef typename T                          value_type;
	typedef typename int                        differce_type;
	typedef typename T *                        pointer;
	typedef typename T&                         reference;
};
template<class T>
struct iterator_traits<const T*>
{
	iterator_traits() {}
	typedef typename random_access_iterator_tag iterator_category;
	typedef typename T                          value_type;
	typedef typename int                        differce_type;
	typedef typename const T*                   pointer;
	typedef typename const T&                   reference;
};
/// SGI
template<class _II>
inline typename iterator_traits<_II>::iterator_category
iterator_category(const _II&)
{
	typedef typename iterator_traits<_II>::iterator_category cate;
	return cate();
}

template<class _II>
inline typename iterator_traits<_II>::value_type *
value_type(const _II&)
{
	return  static_cast<typename iterator_traits<_II>::value_type*>(0);
}

template<class _II>
inline typename iterator_traits<_II>::difference_type*
difference_type(const _II&)
{
	return static_cast<typename iterator_traits<_II>::difference_type*> (0);
}

// 正向迭代器
template<class _Ty, class _D = ptrdiff_t>
struct _Forit :public iterator<forward_iterator_tag, _Ty, _D> {};

// 双向迭代器
template<class _Ty,class _D = ptrdiff_t>
struct _Bidit :public iterator<bidirectional_iterator_tag,_Ty,_D>{};

// 随机迭代器
template<class _Ty,class _D = ptrdiff_t>
struct _Ranit :public iterator< random_access_iterator_tag, _Ty, _D> {};



template<class _II,class _D>
inline void __advance(_II& i, _D n, input_iterator_tag)
{
	while (n--)  ++i;
}

template<class _BI, class _D>
inline void __advance(_BI & i, _D n, bidirectional_iterator_tag)
{
	if (n >= 0)
	{
		while (n--) ++i;
	}
	else
	{
		while (n++) --i;
	}
}

template<class _RAI, class _D>
inline void __advance(_RAI& i, _D n, random_access_iterator_tag)
{
	i += n;
}

template<class _II,class _D>
inline void advance(_II& i, _D n)
{
	//iterator_traits<_II>();
	//typedef typename iterator_traits<_II>::iterator_category cate;
	__advance(i, n, iterator_category(i));
}
template<class _II>
inline typename iterator_traits<_II>::difference_type  
__distance(_II _F, _II _L, input_iterator_tag)
{
	typename iterator_traits<_II>::difference_type n = 0;
	while (_F != _L)
	{
		_F++;
		n++;
	}
	return n;
}
template<class _RAI>
inline typename iterator_traits<_RAI>::difference_type
__distance(_RAI _F, _RAI _L, random_access_iterator_tag)
{
	return _L - _F;
}

template<class _II>
inline typename iterator_traits<_II>::difference_type
distance(_II _F, _II _L)
{
	return __disstance(_F, _L, iterator_category(_F));
}

}

#endif


（3）一、二级空间配置器

my_alloc.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
#ifndef MY_ALLOC_H
#define MY_ALLOC_H
#include<iostream>

namespace pzj
{
#if 0
#include<new>
#define __THROW_BAD_ALLOC throw std::bad_alloc;
#elif !defined(__THROW_BAD_ALLOC)
#define __THROW_BAD_ALLOC std::cerr<<"out of memory"<<std::endl; exit(1)
#endif

template<int inst>
class __malloc_alloc_template
{
public:
	using PFUN = void (*)();
private:
	static void* oom_malloc(size_t n)
	{
		void* result = NULL;
		void (*my_malloc_handler) () = nullptr;
		while(1)
		{
			my_malloc_handler = __malloc_alloc_oom_handler;
			if (nullptr == my_malloc_handler)
			{
				__THROW_BAD_ALLOC;
			}
			my_malloc_handler();
			result = malloc(n);
			if (nullptr != result)
			{
				return result;
			}
		}
	}
	static void* oom_realloc(void* p, size_t new_sz)
	{
		void* result = NULL;
		void (*my_malloc_handler) () = nullptr;
		for (;;)
		{
			my_malloc_handler = __malloc_alloc_oom_handler;
			if (nullptr == my_malloc_handler)
			{
				__THROW_BAD_ALLOC;
			}
			my_malloc_handler();
			result = realloc(p, new_sz);
			if (nullptr != result)
			{
				return result;
			}
		}
	}
	static PFUN __malloc_alloc_oom_handler;
public:
	static void* allocate(size_t n)
	{
		void* result = malloc(n);
		if (nullptr == result)
		{
			result = oom_malloc(n);
		}
		return result;
	}
	static void deallocate(void* p, size_t n)
	{
		free(p);
	}
	static void* reallocate(void* p, size_t old_sz, size_t new_sz)
	{
		void* result = realloc(p, new_sz);
		if (nullptr == result)
		{
			result = oom_realloc(p, new_sz);
		}
		return result;
	}

	static  PFUN set_malloc_handler(PFUN p)
	{
		PFUN old = __malloc_alloc_oom_handler;
		__malloc_alloc_oom_handler = p;
		return old;
	}
};
template<int inst>
typename __malloc_alloc_template<inst>::PFUN
__malloc_alloc_template<inst>::__malloc_alloc_oom_handler = nullptr;

//typedef __malloc_alloc_template<0> malloc_alloc;
using malloc_alloc = __malloc_alloc_template<0>;

enum { __ALIGN = 8 };
enum { __MAX_BYTES = 128 };
enum { __NFREELISTS = __MAX_BYTES / __ALIGN }; // 16

template<bool threads,int inst>
class __default_alloc_template
{
private:
	union obj
	{
		union obj* free_list_link; // next;
		//char client_data[1];
	};
private:
	static obj* volatile free_list[__NFREELISTS];
	static char* start_free;
	static char* end_free;
	static size_t heap_size; // total
	static size_t ROUND_UP(size_t bytes)
	{
		return (bytes + __ALIGN - 1) & ~(__ALIGN - 1);
	}
	static size_t FREELIST_INDEX(size_t bytes)
	{
		return (bytes + __ALIGN - 1) / __ALIGN - 1;
	}

	static char* chunk_alloc(size_t size, int& nobjs)
	{ //                           
		char* result = NULL;
		size_t total_bytes = size * nobjs; 
		size_t bytes_left = end_free - start_free; 
		if (bytes_left >= total_bytes) //
		{
			result = start_free;
			start_free = start_free + total_bytes;
			return result;
		}
		else if (bytes_left >= size) // >= 1 
		{
			nobjs = bytes_left / size; // 
			total_bytes = size * nobjs; //
			result = start_free;
			start_free = start_free + total_bytes;
			return result;
		}
		else
		{
			size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
			if (bytes_left > 0)
			{
				obj* volatile* my_free_list = free_list + FREELIST_INDEX(bytes_left);
				((obj*)start_free)->free_list_link = *my_free_list;
				*my_free_list = (obj*)start_free;
			}
			start_free = (char*)malloc(bytes_to_get);//system heap;
			if (NULL == start_free)
			{
				obj* volatile* my_free_list = NULL;
				obj* p = NULL;
				for (int i = size; i <= __MAX_BYTES; i += __ALIGN)
				{
					my_free_list = free_list + FREELIST_INDEX(i);
					p = *my_free_list;
					if (NULL != p)
					{
						*my_free_list = p->free_list_link;
						start_free = (char*)p;
						end_free = start_free + i;
						return chunk_alloc(size, nobjs);
					}
				}
				start_free = (char*)malloc_alloc::allocate(bytes_to_get);
			}
			end_free = start_free + bytes_to_get;
			heap_size += bytes_to_get;
			return chunk_alloc(size, nobjs);
		}
	}
	static void* refill(size_t size) // 
	{
		int nobjs = 20; 
		char* chunk = chunk_alloc(size, nobjs); // 
		if (1 == nobjs)
		{
			return chunk;
		}
		obj* volatile* my_free_list = NULL;
		obj* result = (obj*)chunk;
		obj* current_obj = NULL ,* next_obj = NULL;
		int i = 0;
		my_free_list = free_list + FREELIST_INDEX(size);
		*my_free_list = next_obj = (obj*)(chunk + size);
		for (i = 1; ; ++i)
		{
			current_obj = next_obj;
			next_obj = (obj*)((char*)next_obj + size);
			if (i == nobjs - 1)
			{
				current_obj->free_list_link = NULL;
				break;
			}
			current_obj->free_list_link = next_obj;
		}
		return result;
	}
public:
	//申请空间
	static void* allocate(size_t size)
	{
		//size > 128 调用一级空间适配器
		if (size > (size_t)__MAX_BYTES)
		{
			return malloc_alloc::allocate(size);
		}
		obj* result = nullptr;
		obj* volatile* my_free_list = nullptr; //
		my_free_list = free_list + FREELIST_INDEX(size);
		result = *my_free_list;
		if (nullptr == result)
		{
			void* r = refill(ROUND_UP(size)); // size = 6; 8 ; size = 10; 16 
			return r;
		}
		*my_free_list = result->free_list_link;
		return result;
	}
	static void deallocate(void* p, size_t n)
	{
		if (n > (size_t)__MAX_BYTES)
		{
			malloc_alloc::deallocate(p, n);
			return;
		}
		obj* q = (obj*)p;
		obj* volatile* my_free_list = free_list +  FREELIST_INDEX(n);
		q->free_list_link = *my_free_list;
		*my_free_list = q;
		return;
	}
	static void* reallocate(void* p, size_t old_sz, size_t new_sz)
	{
		if (old_sz > (size_t)__MAX_BYTES && new_sz > (size_t)__MAX_BYTES)
		{
			return malloc_alloc::reallocate(p, old_sz, new_sz);
		}
		if (ROUND_UP(old_sz) == ROUND_UP(new_sz))
		{
			return p;
		}
		size_t sz = old_sz < new_sz ? old_sz : new_sz;
		void* s = allocate(new_sz);
		memmove(s, p, sz);
		deallocate(p, old_sz);
		return s;
	}
};


template<bool threads, int inst>
typename __default_alloc_template<threads, inst>::obj* volatile
__default_alloc_template<threads, inst>::free_list[__NFREELISTS] = {};

template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::start_free = nullptr;

template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::end_free = nullptr;

template<bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;

///////////////////////////////////////////
// SGI STL
#ifdef __USE_MALLOC
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;
#else
typedef __default_alloc_template<0, 0> alloc;
#endif

template<class T,class Alloc>
class simple_alloc
{
public:
	static T* allocate(size_t n) // n  T 类型 operator new []
	{
		return (T*)Alloc::allocate(sizeof(T) * n); // 
	}
	static T* allocate() //   1 T
	{
		return (T*)Alloc::allocate(sizeof(T));    // operator new 
	}
	static void deallocate(T* p, size_t n) // n T 
	{
		if (NULL == p) return;
		Alloc::deallocate(p, sizeof(T) * n);
	}
	static void deallocate(T* p)
	{
		if (NULL == p) return;
		Alloc::deallocate(p, sizeof(T));
	}
};

}
#endif

（4）构造、析构

my_construct.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#ifndef MY_CONSTRUCT_H
#define MY_CONSTRUCT_H
#include"my_iterator.h"
#include"my_type_traits.h"
namespace pzj
{
template<class T1,class T2>
inline void construct(T1* p, const T2& val)
{
	new (p) T1(val);
}

template<class T>
inline void construct(T *p)
{
	new (p) T();
}
template<class T>
inline void destroy(T* p)
{
	p->~T();
}

template<class _FI>
inline void __destroy_aux(_FI _F, _FI _L, pzj::__true_type)
{}

template<class _FI>
inline void __destroy_aux(_FI _F, _FI _L, pzj::__false_type)
{
	for (; _F != _L; ++_F)
	{
		destroy(&*_F);
	}
}
template<class _FI, class T>
inline void __destroy(_FI _F, _FI _L, T*) // value_type;
{
	//cout << typeid(T).name() << endl;
	//pzj::__type_traits<T>();
	typedef typename pzj::__type_traits<T>::has_trivial_destructor dest;
	__destroy_aux(_F, _L, dest());
}
template<class _FI>
inline void destroy(_FI _F, _FI _L)
{
	__destroy(_F, _L, pzj::value_type(_F));
}

}
#endif