HardBirch

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

时间:09-10-18 栏目:系统技术篇 作者:鲁智森也有文化 评论:0 点击: 1,974 次

这个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控制)

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

  1. [e01]

    2010-07-16 12:27 [回复]

发表评论


QQ群互动

Linux系统与内核学习群:194051772

WP建站技术学习交流群:194062106

魔豆之路QR

魔豆的Linux内核之路

魔豆的Linux内核之路

优秀工程师当看优秀书籍

优秀程序员,要看优秀书!

赞助商广告

友荐云推荐