如果我想在容器的开头和末尾都添加元素,那么是不是应该使用双端队列(deque)而不是向量(vector)?什么时候该使用列表(list),它的优点是什么?
如果我想在容器的开头和末尾都添加元素,那么是不是应该使用双端队列(deque)而不是向量(vector)?什么时候该使用列表(list),它的优点是什么?
如果你需要在序列的开头和结尾高效插入/删除以及随机访问,请使用deque
; 如果你需要在任何地方高效插入,但牺牲了随机访问,则使用list
。在几乎任何情况下,对list
元素的迭代器和引用都非常稳定,容器的任何变异都不会导致它们失效,而deque
有非常特殊的迭代器和引用失效规则(因此请仔细检查它们)。
另外,list
是一个基于节点的容器,而deque
使用连续内存块,因此内存局部性可能会对性能产生影响,这是渐进复杂度估计无法捕捉的。
deque
几乎可以替代vector
,并且应该被认为是C++中的“默认”容器(由于其更灵活的内存需求); 仅在必须拥有保证的连续内存布局时,才应优先选择vector
。
deque
和 vector
可以提供随机访问,而 list
只能提供线性访问。因此,如果你需要使用 container[i] 这种随机访问的方式,那么就不能选择 list
了。另一方面,你可以在一个 list
中高效地插入和删除元素,而在 vector
和 deque
中间插入或删除元素的操作则较慢。
deque
和 vector
非常相似,在大多数情况下基本上可以互换使用。只有两个值得注意的区别。首先,vector
只能在末尾高效地添加新项,而 deque
可以在两端高效地添加项。那么为什么还要使用 vector
呢?与 deque
不同,vector
保证所有项都存储在连续的内存位置中,在某些情况下可以更快地迭代它们。
vector
几乎总是比deque
更高效。 - Don Reba