现在的位置: 首页 > 综合 > 正文

用 vectors 改进内存的再分配

2019年03月30日 ⁄ 综合 ⁄ 共 2558字 ⁄ 字号 评论关闭

用 vectors 改进内存的再分配

作者:Danny Kalev
编译:MTT 工作室

原文出处:Improving Memory Reallocation with 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 个元素的空间

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

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

 

抱歉!评论已关闭.