C++STL中用vector改进内存的再分配

C&＃43;&＃43; STL中用vector 改进内存的再分配

作者&＃xff1a; winter

本文说明了vector 容器使用时应该注意的内存分配问题&＃xff0c;原理说的比较详细&＃xff0c;对于初学者比较适用。 

本文描述的是一种很常见的情况&＃xff1a;当你在某个缓存中存储数据时&＃xff0c;常常需要在运行时调整该缓存的大小&＃xff0c;以便能容纳更多的数据。本文将讨论如何使用 STL 的 vector 进行内存的再分配。

　　这里描述的是一种很常见的情况&＃xff1a;当你在某个缓存中存储数据时&＃xff0c;常常需要在运行时调整该缓存的大小&＃xff0c;以便能容纳更多的数据。传统的内存再分配技术非常繁琐&＃xff0c;而且容易出错&＃xff1a;在 C 语言中&＃xff0c;一般都是每次在需要扩充缓存的时候调用 realloc()。在 C&＃43;&＃43; 中情况更糟&＃xff0c;你甚至无法在函数中为 new 操作分配的数组重新申请内存。你不仅要自己做分配处理&＃xff0c;而且还必须把原来缓存中的数据拷贝到新的目的缓存&＃xff0c;然后释放先前数组的缓存。本文将针对这个问题提供一个安全、简易并且是自动化的 C&＃43;&＃43; 内存再分配技术——即使用 STL 的 vector。

　　用 STL vector 对象取代内建的数组来保存获取的数据&＃xff0c;既安全又简单&＃xff0c;并且是自动化的。

　　进一步的问题分析

　　在提出解决方案之前&＃xff0c;我先给出一个具体的例子来说明 C&＃43;&＃43; 重新分配内存的弊病和复杂性。假设你有一个编目应用程序&＃xff0c;它读取用户输入的 ISBNs&＃xff0c;然后将之插入一个数组&＃xff0c;直到用户输入 0 为止。如果用户插入的数据多于数组的容量&＃xff0c;那么你必须相应地增加它的大小&＃xff1a;

　 

　　注意上述这个向数组插入数据的过程是多么的繁琐。每次反复&＃xff0c;循环都要检查缓存是否达到上限。如果是&＃xff0c;则程序调用用户定义的函数 reallocate()&＃xff0c;该函数实现如下&＃xff1a; 

　

　　reallocate() 使用 STL std::copy() 算法对缓存进行合理的扩充——每次扩充都放大一倍。这种方法可以避免预先分配过多的内存&＃xff0c;从量上减少需要重新分配的内存。这个技术需要得到充分的测试和调试&＃xff0c;当初学者实现时尤其如此。此外&＃xff0c;reallocate() 并不通用&＃xff0c;它只能处理整型数组的情形。对于其它数据类型&＃xff0c;它无能为力&＃xff0c;你必须定义该函数额外的版本或将它模板化。幸运的是&＃xff0c;有一个更巧妙的办法来实现。

　　创建和优化 vector

　　每一个 STL 容器都具备一个分配器&＃xff08;allocator&＃xff09;&＃xff0c;它是一个内建的内存管理器&＃xff0c;能自动按需要重新分配容器的存储空间。因此&＃xff0c;上面的程序可以得到大大简化&＃xff0c;并摆脱 reallocator 函数。

　　第一步&＃xff1a;创建 vector

　　用 vector 对象取代内建的数组来保存获取的数据。main() 中的循环读取 ISBN&＃xff0c;检查它是否为 0&＃xff0c;如果不为 0 &＃xff0c;则通过调用 push_back() 成员函数将值插入

　

　　在 vector 对象构造期间&＃xff0c;它先分配一个由其实现定义的默认的缓存大小。一般 vector 分配的数据存储初始空间是 64-256 存储槽&＃xff08;slots&＃xff09;。当 vector 感觉存储空间不够时&＃xff0c;它会自动重新分配更多的内存。实际上&＃xff0c;只要你愿意&＃xff0c;你可以调用 push_back() 任何多次&＃xff0c;甚至都不用知道一次又一次的分配是在哪里发生的。

　　为了存取 vector 元素&＃xff0c;使用重载的 [] 操作符。下列循环在屏幕上显示所有 vector 元素&＃xff1a;

　

　　第二步&＃xff1a;优化

　　在大多数情况下&＃xff0c;你应该让 vector 自动管理自己的内存&＃xff0c;就像我们在上面程序中所做的那样。但是&＃xff0c;在注重时间的任务中&＃xff0c;改写默认的分配方案也是很有用的。假设我们预先知道 ISBNs 的数量至少有 2000。那么就可以在对象构造期间指出容量&＃xff0c;以便 vector 具有至少 2000 个元素的容量&＃xff1a;

　

　　除此之外&＃xff0c;我们还可以调用 resize() 成员函数&＃xff1a;

　

　　这样&＃xff0c;便避免了中间的再分配&＃xff0c;从而提高了效率。