用 vectors 改进内存的再分配

核心提示： #include <algorithm> // for std::copyint reallocate(int* &p, int& size){size*=2; // double the array''s size with each reallocation

#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 个元素的空间

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

作者简介

Danny Kalev 是一名通过认证的系统分析师，专攻 C++ 和形式语言理论的软件工程师。1997 年到 2000 年期间，他是 C++ 标准委员会成员。最近他以优异成绩完成了他在普通语言学研究方面的硕士论文。 业余时间他喜欢听古典音乐，阅读维多利亚时期的文学作品，研究 Hittite、Basque 和 Irish Gaelic 这样的自然语言。其它兴趣包括考古和地理。Danny 时常到一些 C++ 论坛并定期为不同的 C++ 网站和杂志撰写文章。他还在教育机构讲授程序设计语言和应用语言课程。