• C++模板与STL（六）：内存空间配置器及内存池技术模拟

    目录

    1.容器内存空间配置器的概念 

    2. Vector List deque的内存分配策略

    2.1 Vector的内存分配策略模拟

    2.2 List的内存分配策略

    2.3 deque的内存分配策略

    3.内存池技术及其仿真

    1.容器内存空间配置器的概念 

    Allocator：对容器与内存分布进行管理的承担者

    2. Vector List deque的内存分配策略

    2.1 Vector的内存分配策略模拟

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. //空间配置器的基类模板
    8. template<class _Ty>
    9. struct Allocator_base {
    10. 	typedef _Ty value_type;
    11. };
    12.  
    13. template<class _Ty>
    14. struct Allocator_base<const _Ty> {
    15. 	typedef _Ty value_type;
    16. };
    17.  
    18. //空间配置器的类模板设计
    19. template<class _Ty>
    20. class Allocator :public Allocator_base<_Ty> {
    21. public:
    22. 	//内嵌数据类型表
    23. 	typedef typename std::size_t size_type;
    24. 	typedef typename std::ptrdiff_t difference_type;
    25. 	typedef _Ty* pointer;
    26. 	typedef const _Ty* const_pointer;
    27. 	typedef _Ty& reference;
    28. 	typedef const _Ty& const_reference;
    29. 	typedef Allocator_base<_Ty> _Mybase;
    30. 	typedef typename _Mybase::value_type value_type;
    31.  
    32. 	//配置器类型的嵌入类型
    33. 	template<class _U>
    34. 	struct rebind {
    35. 		typedef Allocator<_U>other;
    36. 	};
    37.  
    38. 	//构造函数
    39. 	Allocator()throw() {
    40.  
    41. 	}
    42. 	Allocator(const Allocator&)throw() {}
    43.  
    44. 	//可以接受不同类型的其他allocator的拷贝构造
    45. 	template<class _otherAll>
    46. 	Allocator(const Allocator<_otherAll>&)throw() {}
    47.  
    48. 	~Allocator()throw()
    49. 	{
    50.  
    51. 	}
    52.  
    53. 	//请求内存空间
    54. 	pointer allocate(size_type num, typename Allocator<_Ty>::const_pointer hint = 0) {
    55. 		//显示一下内存空间发呢配信息
    56. 		static int i = 0;
    57. 		i++;
    58. 		cout << endl;
    59. 		cout << "第" << i << "次分配" << "-----------------------" << endl;
    60. 		cout << "本次需要分配可容纳" << num << "个元素空间" << endl;
    61. 		return (pointer)(::operator new(num * sizeof(_Ty)));
    62. 	}
    63.  
    64. 	//在已经请求的内存空间中构造容器元素对象：operator new之后，用placement new指向
    65. 	void construct(pointer p, const_reference value) {
    66. 		new(p)_Ty(value);
    67. 	}
    68.  
    69. 	//析构容器元素对象
    70. 	void destroy(pointer p) {
    71. 		p->~_Ty();
    72. 	}
    73.  
    74. 	//释放已有的内存空间
    75. 	void deallocate(pointer p, size_type size) {
    76. 		::operator delete(p);
    77. 	}
    78.  
    79. };
    80.  
    81. //调用
    82. template<typename _T>
    83. void print(vector<_T, Allocator<_T>>& iv) {
    84. 	cout << "现在空间可容纳" << iv.capacity() << "个元素";
    85. 	cout << "\t 容器当前所存储元素数目：" << iv.size() << endl;
    86. 	cout << "容器中的元素数据：";
    87. 	for_each(iv.begin(), iv.end(), [](int n) {cout << " " << n; });
    88. 	cout << endl;
    89. }
    90.  
    91. int main() {
    92. 	int a[] = { 1,2,3 };
    93. 	vector<int, Allocator<int>>vec(a, a + 3);
    94. 	print<int>(vec);
    95. 	for (int i = 1; i < 10; i++) {
    96. 		vec.push_back(10 * i);
    97. 		print<int>(vec);
    98. 	}
    99. 	return 0;
    100. }

    可以看到每次分配的内存空间均为上次的1.5倍，这也是VS编译器所采取的策略。

    不同C++编译器分配内存策略不同，例如g++就是2倍。

    2.2 List的内存分配策略

    对之前的代码做以下修改，变为list的，其他代码保持不变：

    1. //调用
    2. template<typename _T>
    3. void print(list<_T, Allocator<_T>>& iv) {
    4. 	//cout << "现在空间可容纳" << iv.capacity() << "个元素";
    5. 	cout << "\t 容器当前所存储元素数目：" << iv.size() << endl;
    6. 	cout << "容器中的元素数据：";
    7. 	for_each(iv.begin(), iv.end(), [](int n) {cout << " " << n; });
    8. 	cout << endl;
    9. }
    10.  
    11. int main() {
    12. 	int a[] = { 1,2,3 };
    13. 	//vector>vec(a, a + 3);
    14. 	list<int, Allocator<int>>myList(a, a + 3);
    15. 	print<int>(myList);
    16. 	for (int i = 1; i < 5; i++) {
    17. 		myList.push_back(10 * i);
    18. 		print<int>(myList);
    19. 	}
    20. 	return 0;
    21. }

     

    可以看到list的分配内存方式是一个一个分配的，需要一个就分配一个，不留余量。 

    2.3 deque的内存分配策略

    1. //调用
    2. template<typename _T>
    3. void print(deque<_T, Allocator<_T>>& iv) {
    4. 	//cout << "现在空间可容纳" << iv.capacity() << "个元素";
    5. 	cout << "\t 容器当前所存储元素数目：" << iv.size() << endl;
    6. 	cout << "容器中的元素数据：";
    7. 	for_each(iv.begin(), iv.end(), [](int n) {cout << " " << n; });
    8. 	cout << endl;
    9. }
    10.  
    11. int main() {
    12. 	int a[] = { 1,2,3 };
    13. 	//vector>vec(a, a + 3);
    14. 	//list>myList(a, a + 3);
    15. 	deque<int,Allocator<int>>deq(a, a + 3);
    16. 	print<int>(deq);
    17. 	for (int i = 1; i < 200; i++) {
    18. 		deq.push_back(i);
    19. 		//print(deq);
    20. 	}
    21. 	return 0;
    22. }

     deque每次分配固定大小内存，每次4个，逐次累加。

    3.内存池技术及其仿真

    1. #include 
    2. #define MEMPOOL_ALIGNMENT 8
    3. using namespace std;
    4.  
    5. //内存块
    6. template<typename _T>
    7. struct MemoryBlock{
    8. 	//表域
    9. 	int nSize;//内存块大小，以字节为单位
    10. 	int nFree;//表示内存剩余可分配的单位
    11. 	int nFirst;//首个剩余单位的序号
    12.  
    13. 	MemoryBlock* pNext;
    14. 	char aData[1];//内存空间开始位置标记
    15.  
    16.  
    17. 	MemoryBlock(int nUnitSize, int nUninAmount) :
    18. 		nSize(nUnitSize* nUninAmount), nFree(nUninAmount - 1), nFirst(1), pNext(nullptr)
    19. 	{
    20. 		//下一个可以分配的单位序号需要记录当前单元的强两个字节
    21. 		char* ppData = aData;
    22. 		cout << "存储区首地址ppData=" << (int)*ppData << endl;
    23. 		for (int i = 1; i < nUninAmount; i++) {
    24. 			//在当前存储单位空间 存储下一个可分配的单位序号
    25. 			(*(unsigned short*)ppData) = i;
    26. 			ppData += nUnitSize;
    27. 		}
    28. 		cout << "内存块的构造函数被调用了" << endl;
    29. 	}
    30.  
    31. 	//nUnitSize:存储单位大小
    32. 	//nUnitAmount:内存块的规模（数量）
    33. 	void* operator new(size_t, int nUnitSize, int nUnitAmount) {
    34. 		cout << "分配内存空间并创建MemoryBlock" << endl;
    35. 		return ::operator new(sizeof(MemoryBlock) + nUnitSize * nUnitAmount);
    36. 	}
    37.  
    38. 	void operator delete(void* pBlock) {
    39. 		cout << "调用了内存的析构" << endl;
    40. 	}
    41. };
    42.  
    43. //内存池 Mempool
    44. template<typename _T>
    45. struct MemoryPool
    46. {
    47. 	int nInitSize;
    48. 	int nGrowSize;
    49. 	int nUnitSize;
    50. 	MemoryBlock<_T>* pBlock;
    51.  
    52. 	MemoryPool(int _nGrowSize = 10, int _nInitSize = 3) {
    53. 		cout << "调用了内存池的构造函数" << endl;
    54. 		nInitSize = _nInitSize;
    55. 		nGrowSize = _nGrowSize;
    56.  
    57. 		pBlock = nullptr;
    58. 		nUnitSize = (sizeof(_T));
    59.  
    60. 		//纯出单位的大小调整
    61. 		if (sizeof(_T) > 4) {
    62. 			//8字节对齐
    63. 			nUnitSize = (sizeof(_T) + (MEMPOOL_ALIGNMENT - 1)) &
    64. 				~(MEMPOOL_ALIGNMENT - 1);
    65. 		}
    66. 		else {
    67. 			if (sizeof(_T) < 2) { nUnitSize = 2; }
    68. 			else { nUnitSize = 4; }
    69. 		}
    70. 	}
    71.  
    72. 	~MemoryPool() {
    73. 		MemoryBlock<_T>* pMyBlock = pBlock;
    74. 		while (pMyBlock != nullptr) {
    75. 			pMyBlock = pMyBlock->pNext;
    76. 			delete(pMyBlock);
    77. 		}
    78. 		cout << "调用了内存池的析构函数" << endl;
    79. 	}
    80.  
    81. 	void* allocate(size_t num) {
    82. 		for (int i = 0; i < num; i++) {
    83. 			if (pBlock == nullptr) {
    84. 				//创建首个内存块
    85. 				pBlock = (MemoryBlock<_T>*)new(nUnitSize, nInitSize)MemoryBlock<_T>(nUnitSize, nInitSize);
    86. 				return (void*)pBlock->aData;
    87. 			}
    88. 			//为内存寻求合适的内存块
    89. 			MemoryBlock<_T>* pMyBlock = pBlock;
    90. 			while (pMyBlock != nullptr && pMyBlock->nFree == 0) {
    91. 				pMyBlock = pMyBlock->pNext;
    92. 			}
    93. 			if (pMyBlock != nullptr) {
    94. 				cout << "内存空间已经找到，First=" << pMyBlock->nFirst << endl;
    95. 				char* pFree = pMyBlock->aData + pMyBlock->nFirst * nUnitSize;
    96. 				pMyBlock->nFirst = *((unsigned short*)pFree);
    97. 				pMyBlock->nFree--;
    98. 				return (void*)pFree;
    99. 			}
    100. 			else {
    101. 				//说明内存用完了
    102. 				if (nGrowSize == 0) {
    103. 					return nullptr;
    104. 				}
    105. 				cout << "分配新内存" << endl;
    106. 				pMyBlock = (MemoryBlock<_T>*)new (nUnitSize, nGrowSize)MemoryBlock<_T>(nUnitSize, nGrowSize);
    107.  
    108. 				if (pMyBlock == nullptr) {
    109. 					return nullptr;
    110. 				}
    111. 				//如果成功那么，将新内存插入链表
    112. 				pMyBlock->pNext = pBlock;
    113. 				pBlock = pMyBlock;
    114. 				return (void*)pMyBlock->aData;
    115. 			}
    116. 		}
    117. 	}
    118.  
    119. 	void free(void* pFree) {
    120. 		cout << "释放存储单位的空间" << endl;
    121. 		//找到p所在的内存块
    122. 		MemoryBlock<_T>* pMyBlock = pBlock;
    123. 		MemoryBlock<_T>* PreBlock = nullptr;
    124.  
    125. 		while (pMyBlock != nullptr && (pBlock->aData > pFree) 
    126. 			|| pMyBlock->aData + pMyBlock->nSize) {
    127. 			PreBlock = pMyBlock;
    128. 			pMyBlock = pMyBlock->pNext;
    129. 		}
    130.  
    131. 		//该内存在本内存池中的指向位置
    132. 		if (pMyBlock != nullptr) {
    133. 			//修改数组链表
    134. 			*((unsigned short*)pFree) = pMyBlock->nFirst;
    135. 			pMyBlock->nFirst = (unsigned short)((unsigned long)pFree - (unsigned long)pMyBlock->aData) / nUnitSize;
    136. 			pMyBlock->nFree++;
    137.  
    138. 			//判断是否需要向操作系统释放内存
    139. 			if (pMyBlock->nSize == pMyBlock->nFree * nUnitSize) {
    140. 				delete(pMyBlock);
    141. 			}
    142. 			else {
    143. 				PreBlock = pMyBlock->pNext;
    144. 				pMyBlock->pNext = pBlock;
    145. 				pBlock = pMyBlock;
    146. 			}
    147. 		}
    148. 	}
    149. };
    150.  
    151. class UserCls {
    152. 	int s;
    153. 	double s1;
    154. 	double s2;
    155. public:
    156. 	UserCls(int x) :s(x) {
    157. 		cout << "调用了UserCls的构造函数" << endl;
    158. 	}
    159. 	int get() { return s; }
    160. 	~UserCls()
    161. 	{
    162. 		cout << "调用了UserCls的析构函数" << endl;
    163. 	}
    164. };
    165.  
    166. int main() {
    167. 	MemoryPoolM_Pool;
    168.  
    169. 	UserCls* dp1 = (UserCls*)M_Pool.allocate(1);
    170. 	cout << "dp1=" << dp1 << endl;
    171. 	new(dp1)UserCls(111);
    172. 	cout << "dp1中的数据是" << dp1->get() << endl;
    173. 	cout << endl;
    174.  
    175. 	UserCls* dp2 = (UserCls*)M_Pool.allocate(1);
    176. 	cout << "dp2=" << dp2 << endl;
    177. 	new(dp2)UserCls(222);
    178. 	cout << "dp2中的数据是" << dp2->get() << endl;
    179. 	cout << endl;
    180.  
    181. 	UserCls* dp3 = (UserCls*)M_Pool.allocate(1);
    182. 	cout << "dp3=" << dp3 << endl;
    183. 	new(dp3)UserCls(333);
    184. 	cout << "dp3中的数据是" << dp3->get() << endl;
    185. 	cout << endl;
    186.  
    187. 	UserCls* dp4 = (UserCls*)M_Pool.allocate(1);
    188. 	cout << "dp4=" << dp4 << endl;
    189. 	new(dp4)UserCls(444);
    190. 	cout << "dp4中的数据是" << dp4->get() << endl;
    191. 	cout << endl;
    192.  
    193. 	UserCls* dp5 = (UserCls*)M_Pool.allocate(1);
    194. 	cout << "dp5=" << dp5 << endl;
    195. 	new(dp5)UserCls(555);
    196. 	cout << "dp5中的数据是" << dp5->get() << endl;
    197. 	cout << endl;
    198.  
    199. 	return 0;
    200. }

  • 相关阅读:
    Java8实战-总结30
    Spring Cloud中，Eureka常见问题总结
    力扣第617题 合并二叉树 c++ 前中后序 完成 附加迭代版本
    信息学奥赛一本通：1397：简单算术表达式求值
    问题解析：为什么数组下标从0 开始而不是 1 ？
    [C]详解C语言动态内存分配
    Win11快速助手在哪里？Win11打开快速助手的方法
    【Unity3D】资源管理
    C++ 实现HTTP的客户端、服务端demo和HTTP三方库介绍
    【C++--类和对象】构造函数&&析构函数
  • 原文地址：https://blog.csdn.net/Jason6620/article/details/126252707