它们都具有O(1)的访问复杂度和O(n)的随机插入/删除复杂性.但是,由于重新分配和复制,向量在扩展时会花费更多,而deque没有这个问题.
似乎deque有更好的性能,但为什么大多数人使用vector而不是deque？
从C++标准第23.1.1节:
vector is the type of sequence that should be used by default... deque is
the data structure of choice when most insertions and deletions take place
at the beginning or at the end of the sequence.
然而,有一些相反方向的论点.
理论上vector至少与deque提供其功能的子集一样有效.如果你的任务只需要vector的界面提供,那就更喜欢vector - 它不会比deque更糟糕.
why most people use vector instead of deque?
因为这是他们所教授的.
vector和deque服务略有不同的目的.它们都可以用作对象的简单容器,如果这就是你所需要的.当学习编程的C++,这是大家都需要的-一个桶中砸的东西,得到的东西抽出来,走了过来.
当StackOverflow被问到像"默认情况下我应该使用哪个容器"这样的问题时,答案几乎总是如此vector.问题通常是从学习C++编程的背景中提出的,而且在程序员提出这样一个问题的时候,他们还不知道他们不知道什么.还有很多他们还不知道.因此,我们(StackOverflow)需要一个几乎适合所有需求的容器,可以在几乎任何环境中使用,并且不需要程序员在登陆接近正确答案的内容之前询问所有正确的问题.此外,标准特别推荐使用vector. 对所有用途vector来说都不是最好的,实际上deque比用得更好vector对于许多常见的用途 - 但对于学习程序员而言,我们应该从标准的建议到新手C++程序员不同,所以StackOverflow着陆vector.
在学习了语法的基础知识之后,我们应该说,C++中的编程背后的策略,程序员分成两个分支:那些关心学习更多,编写更好的程序的人,以及那些不编程的人.那些不这样做的人会vector永远坚持下去.我想很多程序员都会参加这个阵营.
试图超越这个阶段的稀有程序员开始提出其他问题 - 像你在这里问过的问题.他们知道有很多他们还不知道,他们想要开始发现这些东西是什么.他们会迅速(以下快)发现之间进行选择时vector和deque,有些问题他们并不认为是前问:
然后他们真正开始思考他们正在编写的代码,发现更多他们不知道的东西,并且节拍继续......
但是,由于重新分配和复制,矢量在扩展时会花费更多
虽然vector有时必须在数组增长时重新分配数组,但它会呈指数级增长,因此摊销的复杂性仍为O(1).通常,您可以通过明智地使用来避免重新分配reserve().
看来deque有更好的表现
表现有很多方面; 所花的时间push_back只有一个.在某些应用程序中,容器可能很少被修改,或者在启动时填充,然后从不修改.在这种情况下,迭代和访问速度可能更重要.
vector是最简单的容器:连续的数组.这意味着可以通过简单的指针算法实现迭代和随机访问,并且访问元素可以与解除引用指针一样快.
deque有进一步的要求:它不能移动元素.这意味着典型的实现需要额外的间接级别 - 它通常被实现为类似于数组指针的数组.这意味着元素访问需要解除引用两个指针,这两个指针将慢于一个指针.
当然,速度通常不是关键问题,您根据行为属性而不是性能来选择容器.您可以选择vector是否需要连续的元素,也许是为了使用基于指针和数组的API.您可以选择deque或者list如果您想要保证元素不会移动,那么您可以存储指针.