注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

anqiang专栏

不要问细节是怎么搞的,源码说明一切

 
 
 

日志

 
 

C++容器使用要点  

2011-06-10 11:26:48|  分类: C++相关 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 

在使用STL容器时,有一点很方便,就是容器对象的大小可以根据插入对象的增加而自动增加。对于Vector,向一个容器中插入对象的过程如下:

 

1.       判断容器是否已经满员,如果没有则插入改对象

2.       如果已经满员,则扩充容器对象大小

 

扩充容器的过程:

1.       扩充容器的大小到当前容器大小的2倍,这个过程分配了一个新的内存区

2.       将旧的容器中的内容copy到新的内存区,

3.       将对象插入到新的容器中

4.       销毁旧的容器中的对象

5.       释放旧容器占有的内存

 

  void push_back(const _Tp& __x) {

         //容器没有满员

    if (_M_finish != _M_end_of_storage) {

      construct(_M_finish, __x);

      ++_M_finish;

    }

Else

 //容器满员后的操作

      _M_insert_aux(end(), __x);

  }

 

template <class _Tp, class _Alloc>

void

vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)

{

  if (_M_finish != _M_end_of_storage) {

    construct(_M_finish, *(_M_finish - 1));

    ++_M_finish;

    _Tp __x_copy = __x;

    copy_backward(__position, _M_finish - 2, _M_finish - 1);

    *__position = __x_copy;

  }

  else {

const size_type __old_size = size();

//分配内存到当前内存的2倍

    const size_type __len = __old_size != 0 ? 2 * __old_size : 1;

    iterator __new_start = _M_allocate(__len);

    iterator __new_finish = __new_start;

__STL_TRY {

//copy旧的容器中的内容(0--positon)到新的内存区域

      __new_finish = uninitialized_copy(_M_start, __position, __new_start);

         //插入对象到新的容器中

      construct(__new_finish, __x);

      ++__new_finish;

         //copy 旧的容器中的内容(postion--_M_finish)到新的内存区域

      __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);

    }

    __STL_UNWIND((destroy(__new_start,__new_finish),

                  _M_deallocate(__new_start,__len)));

    //销毁旧的容器中的内容

destroy(begin(), end());

//释放内存

    _M_deallocate(_M_start, _M_end_of_storage - _M_start);

    _M_start = __new_start;

    _M_finish = __new_finish;

    _M_end_of_storage = __new_start + __len;

  }

}

 

从这段分析中,我们可以看到对于容器的插入操作可能会存在大量的内存分配销毁的操作。我们在使用容器对象时可以尽量避免这些操作。一个简单的办法是,如果大概知道容器对象的大小,可以通过reserve函数,为容器对象设置一个初始大小,这样一次分配内存就满足后面所有容器插入的需求。

 

vector<int> v;

for (int i = 1; i <= 72; ++i) v.push_back(i);

 

对于这样一段代码,需要分配内存6次,2的6次方为72.

 

如果我们这样写这段代码

vector<int> v;

v.reserve(72)

for (int i = 1; i <= 72; ++i) v.push_back(i);

 

那么在这个过程中就仅需要分配一次内存。程序效率会得到很大提高。
  评论这张
 
阅读(1310)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017