STL剖析:从capacity()和resize()看容器的内存分配思想

类别:编程语言 点击:0 评论:0 推荐:

这个blog来源于一个朋友提出的的问题

下面的代码想输出0-9,可不行。原因是iterStart居然等于iterEnd,为什么?

 list<int> li;
 vector<int> vi;

 for(int c=0;c<10;c++) li.push_back(c);
 vi.reserve(li.size());

 copy(li.begin(),li.end(),vi.begin());

 vector<int>::iterator iterStart=vi.begin();
 vector<int>::iterator iterEnd=vi.end();

 vector<int>::iterator it=iterStart;
 
 for(;it!=iterEnd;it++)
 {
  cout<<*it<<endl;
 }

---------------------------------------------------------


有趣的问题,2种解决方案:
1)把
vi.reserve(li.size());
修改为
vi.resize(li.size());

2)在构造时指定空间
 vector<int> vi(li.size())

问题在于对reserve()函数的理解:
下面是reserve()的MSDN帮助:
vector::reserve
void reserve(size_type n);
The member function ensures that capacity() henceforth returns at least n.
下面是resize()的MSDN帮助:
vector::resize
void resize(size_type n, T x = T());
The member function ensures that size() henceforth returns n. If it must lengthen the controlled sequence, it appends elements with value x.

关键在于:reserve()已经分配了空间,但是“不可以使用”!考虑以下的使用场景:
Step1:现在大小是10(size()和capacity()返回10),保留1000个元素的空间(使用reserve()),说明以后1000个元素的空间已经分配成功了,但是size()仍然返回10,capacity()返回1000!
Step2:调用resize(100),实际没有重新分配空间(因为已经“分配并保留”了1000)。此时size()返回100, capacity()返回1000!

A little deeper:查看STL的源代码会更容易的理解这个问题。列出vector的size()和capacity()函数的实现:
 size_type size() const
  {return (_First == 0 ? 0 : _Last - _First); }
 size_type capacity() const
  {return (_First == 0 ? 0 : _End - _First); }
注意:size()使用了_Last指针,而capacity()使用了_End指针!
Aha!原来所谓的“尾指针”有2个:
_Last表示真正的数据(允许使用的空间)的尾指针;
_End表示已经分配的空间的尾指针;

这个问题的根本还是对于STL容器的内存分配方式的理解,i.e. reserve()和resize()的区别。如果没有提供reserve()方法,相信会更加容易理解,代价是失去了更好的内存管理的手段。提供reserve()方法的目的,我理解是允许用户使用memory pool的思想来手动控制内存的分配,即预先保留足够多的空间(由_End控制),然后根据需要使用实际的内存空间(由_Last控制)

 

本文地址:http://com.8s8s.com/it/it27448.htm