旅途

如果想飞得高,就该把地平线忘掉

vector list

vector 表示一段连续的内存区域每个元素被顺序存储在这段内存中
对vector 的随机访问比如先访问元素5 然后访问15 然后再访问7 等等效率很高
因为每次访问离vector起始处的位移都是固定的
但是在任意位置而不是在vector 末尾插人元素则效率很低因为它需要把待插入元素右边的每个元素都拷贝一遍类似地删除任意一个而不是vector的最后一个元素效率同样很低因为待删除元素右边的每个元素都必须被复制一遍这种代价对于大型的复杂的类对象来说尤其大

一个deque 也表示一段连续的内存区域但
是与vector 不同的是它支持高效地在其首部插入和删除元素它通过两级数组结构来实
现一级表示实际的容器第二级指向容器的首和尾

list 表示非连续的内存区域并通过一对指向首尾元素的指针双向链接起来从而允许
向前和向后两个方向进行遍历在list 的任意位置插入和删除元素的效率都很高指针必须
被重新赋值但是不需要用拷贝元素来实现移动另一方面它对随机访问的支持并不好
访问一个元素需要遍历中间的元素另外每个元素还有两个指针的额外空间开销

下面是选择顺序容器类型的一些准则
如果我们需要随机访问一个容器则vector 要比list 好得多
如果我们已知要存储元素的个数则vector 又是一个比list 好的选择
如果我们需要的不只是在容器两端插入和删除元素则list 显然要比vector 好
除非我们需要在容器首部插入和删除元素否则vector 要比deque

posted on 2007-09-20 14:58 旅途 阅读(1597) 评论(0)  编辑 收藏 引用 所属分类: C++ STL


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理