C 中用vectors改进内存的再分配

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

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

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

　　进一步的问题分析

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

#include ＜iostream＞ using namespace std; int main() { 　int size=2; // 初始化数组大小；在运行时调整。 　int *p = new int[size]; 　int isbn; 　for(int n=0; ; n) 　{ 　　cout＜＜ "enter an ISBN; press 0 to stop "; 　　cin＞＞isbn; 　　if (isbn==0) 　　　break; 　　if (n==size) // 数组是否到达上限? 　　　reallocate(p, size); 　　　p[n]=isbn; // 将元素插入扩容的数组 　} 　delete [] p; // 不要忘了这一步! }

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

#include ＜algorithm＞ // for std::copy int reallocate(int* &p, int& size) { 　size*=2; // double the array''s size with each reallocation 　int * temp = new int[size]; 　std::copy(p, p (size/2), temp); 　delete [] p; // release original, smaller buffer 　p=temp; // reassign p to the newly allocated buffer }

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

　　创建和优化 vector

　　每一个 STL 容器都具备一个分配器（allocator），他是个内建的内存管理器，能自动按需要重新分配容器的存储空间。因此，上面的程式能够得到大大简化，并摆脱 reallocator 函数。

　　第一步：创建 vector

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

vector： #include ＜iostream＞ #include ＜vector＞ using namespace std; int main() { 　vector ＜int＞ vi; 　int isbn; 　while(true) 　{ 　　cout ＜＜ "enter an ISBN; press 0 to stop "; 　　cin ＞＞ isbn; 　　if (isbn==0) 　　　break; 　　vi.push_back(isbn); // insert element into vector 　}　 }

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

　　为了存取 vector 元素，使用重载的 [] 操作符。下列循环在屏幕上显示任何 vector 元素：

for (int n=0; n＜vi.size(); n) { 　cout＜＜"ISBN: "＜＜vi[n]＜＜endl; }

　　第二步：优化

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

vector ＜int＞ vi(2000); // 初始容量为 2000 个元素

　　除此之外，我们还能够调用 resize() 成员函数：

vi.resize(2000);// 建立不小于 2000 个元素的空间

　　这样，便避免了中间的再分配，从而提高了效率。