为什么std :: vector比std :: deque更受欢迎？

Question

可能重复:
为什么我更喜欢使用vector来deque

我很好奇为什么它std::vector比这更受欢迎std::deque.Deque几乎和查找一样有效,插入更有效(没有vector :: reserve),允许在前面插入/删除.

Herb Sutter曾经建议如果你想使用矢量,那就更喜欢deque(我在解读).然而,在最近关于编写Modern C++的演讲中,他再次强烈建议将其std::vector视为默认容器.根据我之前链接的GOTW,即使标准也有类似的措辞.

有这种差异的原因吗？它vector是否更简单,更为人所知,还是有技术原因？或者它vector只是一个更酷的名字..？

Answer 1

我不能为别人说话,但我可以为自己.

当我第一次读到这篇文章的时候std::deque,我觉得很酷,有一段时间,我不仅把它当作默认容器,而且几乎是我用过的唯一容器.

然后有人问起为什么,我详细阐述了它的优点,以及为什么它是几乎所有东西都使用的最好的容器,以及它如何比它更通用std::vector.

幸运的是,那个质疑我的决定的人很有说服力,我做了一些测试.测试表明,几乎在每种情况下,std::deque都比较慢std::vector- 通常是一个重要因素(例如,大约2).事实上,代码我会使用写入std::deque,只是更换std::deque用std::vector了所有的加速,但病例屈指可数.

std::deque从那以后我在一些情况下使用过,但绝对不再将它视为默认值.一个简单的事实是,在通常的实现是明显慢std::vector于大多数的目的.

然而,我要补充的是,我有理由相信用正确的实现,它可以几乎等同于std::vector在几乎所有情况下.大多数人使用从渐近的观点来看无疑是伟大的表达,但在现实世界中并没有如此奇妙地(出于许多目的).

Answer 2

std::vector 非常容易理解,简单并且与C兼容(在内存布局方面,以及在使用指针作为迭代器方面).

对于某些操作,它也比它更有效std::deque.通过索引访问元素就是一个例子.

对于给定的任务,使用最简单的容器来完成工作是有意义的.在许多情况下,最简单的容器是std::vector.

Answer 3

除了std::vector是最常见的容器类外,它还有几个优点std::deque,即:

• 典型地std::deque需要额外的间接访问元素,这与在案例中的情况不同std::vector.
• 迭代器std::deque必须是智能指针,而不是像指针一样的指针std::vector.
• a的元素std::vector保证是连续的,因此它与以数组作为参数的c风格函数兼容.
• std::deque 不提供支持来控制容量和重新分配的时刻.

特别是,最后一点值得注意.

Answer 4

人们在std :: deque上使用std :: vector的原因很简单.它们与许多C库接口,并且它们具有带参数的函数,这些参数需要指向连续存储的指针,而std :: deque不能(不能)保证.

另一个原因是当您根据std :: deque构建代码并且您的需求发生变化以便您必须支持连续访问时,您将需要进行一些重构.

我不得不提到有些库,其作者声称创建了更有效的矢量实现,以便在容量增加时克服低效率.

Answer 5

结构std::deque有点复杂,使得天真的迭代比它更昂贵std::vector.插入std::vector其重新分配往往不是一个大问题,特别是在使用时reserve(),只是附加到最后.此外,更容易理解失效规则std::vector虽然实际上std::deque只有在两端插入/移除时保持对象的优势(注意std::deque迭代器在每次插入时都会失效,与插入发生的位置无关).另一个好处std:vector是保证值在内存中是连续的,从而减少内存分配.

我想,我会建议使用std::deque一致优化的算法来使用分段序列(我不知道任何标准的C++库都会进行这种优化)并且用户使用算法一致地访问序列(据我所知,只有一小部分)用户分数考虑使用算法的选项).否则我会怀疑std::deque只有当你利用它的特定属性时(例如,那些对象保持不变并且你可以在最后插入/删除),这是性能方面的更好选择.不过,值得描述两种选择.