Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4584651
  • 博文数量: 1214
  • 博客积分: 13195
  • 博客等级: 上将
  • 技术积分: 9105
  • 用 户 组: 普通用户
  • 注册时间: 2007-01-19 14:41
个人简介

C++,python,热爱算法和机器学习

文章分类

全部博文(1214)

文章存档

2021年(13)

2020年(49)

2019年(14)

2018年(27)

2017年(69)

2016年(100)

2015年(106)

2014年(240)

2013年(5)

2012年(193)

2011年(155)

2010年(93)

2009年(62)

2008年(51)

2007年(37)

分类: C/C++

2010-12-17 10:52:52

  vector的工作原理是系统预先分配一块CAPACITY大小的空间,当插入的数据超过这个空间的时候,这块空间会让某种方式扩展,但是你删除数据的时候,它却不会缩小。 
  vector为了防止大量分配连续内存的开销,保持一块默认的尺寸的内存,clear只是清数据了未清内存,因为vector的capacity容量未变化,系统维护一个的默认值。有什么方法可以释放掉vector中占用的全部内存呢? 
  标准的解决方法如下:

template < class T >
void ClearVector( vector< T >& vt )
{
    vector< T > vtTemp;
    veTemp.swap( vt );
}

    事实上,vector根本就不管内存,它只是负责向内存管理框架acquire/release内存,内存管理框架如果发现内存不够了,就malloc,但是当vector释放资源的时候(比如destruct), stl根本就不调用free以减少内存,因为内存分配在stl的底层:stl假定如果你需要更多的资源就代表你以后也可能需要这么多资源(你的list, hashmap也是用这些内存),所以就没必要不停地malloc/free。 如果是这个逻辑的话这可能是个trade-off。
    一般的STL内存管理器allocator都是用内存池来管理内存的,所以某个容器申请内存或释放内存都只是影响到内存池的剩余内存量,而不是真的把内存归还给系统。这样做一是为了避免内存碎片,二是提高了内存申请和释放的效率——不用每次都在系统内存里寻找一番。 
    真的让容器把不用的内存归还给系统的话,只能自己写一个allocator,并在容器的模板参数里使用它,而且STL的标准容器确实都留了这个接口。不过要意识到这样做给程序性能和系统内存带来的影响。clear和erase可以很好地减少了vector的大小(size),但没有减少它的容量(capactiy)。


在VC++.net上试验的代码,可以看出vector的增长方式:

FILE *file=freopen("1.txt","w",stdout);
vector<int> vec;
cout<<"capacity"<<vec.capacity()<<"size"<<vec.size()<<endl;
for(int i=0;i<100;i++)
{
    vec.push_back(i);
    cout<<"capacity"<<vec.capacity()<<"size"<<vec.size()<<endl;
}


结果如下:
capacity0size0
capacity1size1
capacity2size2
capacity3size3
capacity4size4
capacity6size5
capacity6size6
capacity9size7
capacity9size8
capacity9size9
capacity13size10
capacity13size11
capacity13size12
capacity13size13
capacity19size14
capacity19size15
capacity19size16
capacity19size17
capacity19size18
capacity19size19
capacity28size20
capacity28size21
capacity28size22
capacity28size23
capacity28size24
capacity28size25
capacity28size26
capacity28size27
capacity28size28
capacity42size29
capacity42size30
capacity42size31
capacity42size32
capacity42size33
capacity42size34
capacity42size35
capacity42size36
capacity42size37
capacity42size38
capacity42size39
capacity42size40
capacity42size41
capacity42size42
capacity63size43
capacity63size44
capacity63size45
capacity63size46
capacity63size47
capacity63size48
capacity63size49
capacity63size50
capacity63size51
capacity63size52
capacity63size53
capacity63size54
capacity63size55
capacity63size56
capacity63size57
capacity63size58
capacity63size59
capacity63size60
capacity63size61
capacity63size62
capacity63size63
capacity94size64
capacity94size65
capacity94size66
capacity94size67
capacity94size68
capacity94size69
capacity94size70
capacity94size71
capacity94size72
capacity94size73
capacity94size74
capacity94size75
capacity94size76
capacity94size77
capacity94size78
capacity94size79
capacity94size80
capacity94size81
capacity94size82
capacity94size83
capacity94size84
capacity94size85
capacity94size86
capacity94size87
capacity94size88
capacity94size89
capacity94size90
capacity94size91
capacity94size92
capacity94size93
capacity94size94
capacity141size95
capacity141size96
capacity141size97
capacity141size98
capacity141size99
capacity141size100

对于小的数据类型vector 的性能要比list 好得多,而对于大型的数据类型则相反list 的性能要好得多,区别是由于vector 需要重新增长以及拷贝元素。

无论是list 还是vector ,对于已定义拷贝构造函数的类来说插入这样的类的元素都需要调用拷贝构造函数(用该类型的一个对象初始化该类型的另一个对象)

这正说明了在简单类和string 的链表之间插入代价的区别:简单类对象和大型简单类对象通过按位拷贝插入一个对象的所有位被拷贝到第二个对象的位中,而string 类对象和大型复杂类对象通过调用拷贝构造函数来插入。

另外随着每次重新分配内存,vector 必须为每个元素调用拷贝构造函数,而且在释放原来的内存时它要为每个元素调用其相关类型的析构函数。vector 的动态自我增长越频繁,元素插入的开销就越大。

当然,一种解决方案是,当vector 的开销变得非常大时把vector 转换成list ;另一种经

常使用的方案是通过指针间接存储复杂的类对象。


原文地址1:http://dev.firnow.com/course/3_program/c++/cppsl/2008920/144004.html

阅读(1860) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~