注册 登录
编程论坛 C++教室

三种顺序容器vector、list、deque的优缺点是?

墨清扬 发布于 2012-02-16 19:04, 1817 次点击
deque的优点就是方便管理队列吧,不像C一样自己管那么麻烦,不知道我想的对不对……list和vector就完全不懂了,和c的用[]定义数组比较区别在什么地方?求指点
5 回复
#2
rjsp2012-02-17 09:22
vector是 数组, list是 链表
数组 和 链表 的特性你知道吧,不知道的话去google
deque 的性能介乎 vector 和 list 之间
比如 插入效率,远高于vector,但低于list
比如 定位效率,远高于list,但低于vector
#3
pangding2012-02-17 10:53
这个属于数据结构的基本知识。楼主可能没有这方面的知识,学了之后应该就全明白。

vector 就是一头开口的队列,所以就是一般意义上的队列。
deque 是两头开口的。既能往前插也能往后插。
但是它两都一样,如果非要往中间插,就得腾地。vector 没办法,不管往哪插都得往后挪,所以你往第一个插最惨,整个序列都要复制。deque 好一点,如果你插入的位置比较靠前,它会想办法把前面的部分往前挪来腾地。所以最惨的是往中间插。
但是它们的访问效率都很高,vector 只要用首地址,加偏移量就可以直接找到要访问的元素。deque 稍微复杂,但总的来说,访问的位置也是直接算出来的,所以它们的访问时间都是常数 O(1)。

list 和它们思路不一样。你可以自由的在任何位置插入,插入时间是常数。但访问很慢,它根本不知道你要找的元素在哪里,只能从头遍历。
#4
pangding2012-02-17 10:55
如果楼主只是想用一般的队列,应该考虑用 queue。它的底层是 deque,但屏蔽了除了往后插以外的插入操作。
#5
墨清扬2012-02-18 09:24
谢谢啦!
#6
donggegege2012-02-21 13:30
建议你学学 数据结构
1