Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1001497
  • 博文数量: 128
  • 博客积分: 10012
  • 博客等级: 上将
  • 技术积分: 2050
  • 用 户 组: 普通用户
  • 注册时间: 2008-10-15 17:49
文章分类

全部博文(128)

文章存档

2011年(16)

2009年(57)

2008年(55)

分类: C/C++

2009-01-04 17:34:10

在stl中基本容器有string vector list deque set map


set 和map都是无序的保存元素 只能通过它提供的接口对里面的元素进行访问

set 集合, 用来判断某一个元素是不是在一个组里面 使用的比较少
map 映射 相当于字典 把一个值映射成另一个值 如果想创建字典的话使用它好了


string vector list deque set 是有序容器
string 是basic_string 的实现,
在内存中是连续存放的 为了提高效率,都会有保留内存,如string s= "abcd",这时s使用的空间可能就是255, 当string再次往s里面添加内容时不会再次分配内存 直到内容>255刊才会再次申请内存 因此提高了它的性能
当内容>255时 string会先分配一个新内存 然后再把内容复制过去 再复制先前的内容

对string的操作 如果是添加到最后时 一般不需要分配内存 所以性能最快
如果是对中间或是开始部分操作 如往那里添加元素或是删除元素 或是代替元素 这时需要进行内存复制 性能会降低

如果删除元素 string一般不会释放它已经分配的内存 为了是下次使用时可以更高效

由于string会有预保留内存 所以如果大量使用的话 会有内存浪费 这点需要考虑
还有就是删除元素时不释放过多的内存 这也要考虑

string中内存是在堆中分配的 所以串的长度可以很大 而char[] 是在栈中分配的 长度受到可使用的最大栈长度限制

如果对知道要使用的字符串的最大长度 那么可以使用普通的char[] 实现而不必使用string
string用在串长度不可知的情况 或是变化很大的情况

如果string已经经历了多次添加删除 现在的尺寸比最大的尺寸要小很多 想减少string使用的大小 可以使用
string s = "abcdefg";
string y(s); //因为再次分配内存时 y只会分配与s中内容大一点的内存 所以浪费不会很大
s.swap(y);//减少s使用的内存

如果内存够多的话就不用考虑这个了







capacity是查看现在使用内存的函数
大家可以试试看string分配一个一串后的capacity返回值
还有其它操作后的返回值

第二个是vector
vector就是动态数组 它也是在堆中分配内存 元素连续存放 有保留内存 如果减少大小后央存也不会释放 如果新值.当前大小时才会再分配内存
对最后元素操作最快 (在后面添加删除最快 ) 此时一般不需要移动内存 只有保留内存不够时才需要
对中间和开始处进行添加删除元素操作需要移动内存 如果你的元素是结构或是类 那么移动的同时还会进行构造和析构操作 所以性能不高

访问方面 对任何元素的访问都是O(1) 也就是是常数的 所以vector常用来保存需要经常进行随机访问的内容 并且不需要经常对中间元素进行添加删除操作

相比较可以看到vector的属性与string差不多 同样可以使用capacity看当前保留的内存
使用swap来减少它使用的内存

总结
需要经常随机访问请用vector






list
list就是链表 元素也是在堆中存放
每个元素都是放在一块内存中

list没有空间预留习惯 所以每分配一个元素都会从内存中分配
每删除一个元素都会释放它占用的内存 这与上面不同 可要看好了

list在哪里添加删除元素性能都很高 不需要移动内存 当然也不需要对每个元素都进行构造与析构了 所以常用来做随机操作容器
但是访问list里面的元素时就开始和最后访问最快
访问其它元素都是O(n) 所以 如果需要经常随机访问的话 还是使用其它的好

总结
如果你喜欢经常添加删除大对象的话 那么请使用list
要保存的对象不大 构造与析构操作不复杂 那么可以使用vector代替
list<指针> 完全是性能最低的做法 这种情况下还是使用vector<指针>好
因为指针没有构造与析构 也不占用很大内存







deque
双端队列

也是在堆中保存内容的

它的保存形式如下

[堆1]
...
[堆2]
...
[堆三]


每个堆保存好几个元素
然后堆和堆之间有指针指向

看起来像是list和vector的结合品
不过确实也是如此

deque的让你可以在前面快速的添加删除元素
或是在后面快速的添加删除元素
然后还可以比较高的随机访问速度

vector是可以快速的在最后添加删除元素 并可以快速的访问任意元素
list是可以快速的在所有地方添加删除元素 但是只能快速的访问最开始与最后的元素
deque在开始和最后添加元素都一样快 并提供了随机访问方法 像vector一样使用[]访问任意元素 但是 随机访问速度比不上vector快 因为它要内部处理堆跳转

deque也有保留空间 另外 由于deque不要求连续空间 所以可以保存的元素比vector更大 这点也要注意一下 还有就是在前面和后面添加元素时都不需要移动其它块的元素 所以 性能也很高
阅读(4703) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~