deque 和 list STL 容器有什么区别? [英] What's the difference between deque and list STL containers?

问题描述

两者有什么区别?我的意思是方法都是一样的.因此，对于用户而言，它们的工作方式相同.

What is the difference between the two? I mean the methods are all the same. So, for a user, they work identically.

正确吗??

推荐答案

来自(过时但仍然非常有用)SGI STL 总结 deque:

From the (dated but still very useful) SGI STL summary of deque:

一个deque很像一个vector:和vector一样，它是一个序列，支持元素的随机访问，序列末尾元素的恒定时间插入和移除，以及序列中元素的线性时间插入和移除中.

A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.

deque 与 vector 不同的主要方式是 deque 还支持常量时间插入和移除序列开头的元素.此外，deque 没有任何类似于 vector 的 capacity() 和 reserve() 的成员函数，并且不提供与这些成员函数相关联的迭代器有效性的任何保证.

The main way in which deque differs from vector is that deque also supports constant time insertion and removal of elements at the beginning of the sequence. Additionally, deque does not have any member functions analogous to vector's capacity() and reserve(), and does not provide any of the guarantees on iterator validity that are associated with those member functions.

这是list 的摘要，来自同一站点:

Here's the summary on list from the same site:

列表是双向链表.也就是说，它是一个 Sequence，既支持前向遍历，也支持后向遍历，以及(分摊的)常量时间在开头或结尾或中间插入和移除元素.列表有一个重要的特性，即插入和拼接不会使列表元素的迭代器失效，即使删除也只会使指向被删除元素的迭代器失效.迭代器的顺序可能会改变(也就是说，list::iterator 在列表操作之后可能有一个与之前不同的前驱或后继)，但迭代器本身不会失效或指向不同的元素，除非失效或突变是显式的.

A list is a doubly linked list. That is, it is a Sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle. Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, list::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit.

总而言之，容器可能具有共享例程，但是这些例程的时间保证因容器而异.在考虑将哪些容器用于任务时，这一点非常重要:考虑如何最常使用容器(例如，更多用于搜索而不是插入/删除)大有帮助将您引导至正确的容器.

In summary the containers may have shared routines but the time guarantees for those routines differ from container to container. This is very important when considering which of these containers to use for a task: taking into account how the container will be most frequently used (e.g., more for searching than for insertion/deletion) goes a long way in directing you to the right container.

这篇关于deque 和 list STL 容器有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！