STL Containers - 向量、列表和双端队列之间的区别

2022-01-24 00:00:00 containers c++ stl

如果我想在容器的开头也推送元素,我应该使用双端队列而不是向量吗?什么时候应该使用 list,它有什么意义?

Should I use deque instead of vector if i'd like to push elements also in the beginning of the container? When should I use list and what's the point of it?

推荐答案

如果需要在序列的开头和结尾进行高效的插入/删除和随机访问,请使用 deque;如果您需要在任何地方有效插入,请使用 list,但会牺牲随机访问.list 元素的迭代器和引用几乎在容器的任何突变下都??非常稳定,而 deque 具有非常奇特的迭代器和引用失效规则(因此请仔细检查).

Use deque if you need efficient insertion/removal at the beginning and end of the sequence and random access; use list if you need efficient insertion anywhere, at the sacrifice of random access. Iterators and references to list elements are very stable under almost any mutation of the container, while deque has very peculiar iterator and reference invalidation rules (so check them out carefully).

另外,list 是基于节点的容器,而 deque 使用连续内存块,因此内存局部性可能具有渐近复杂度无法捕获的性能影响估计.

Also, list is a node-based container, while a deque uses chunks of contiguous memory, so memory locality may have performance effects that cannot be captured by asymptotic complexity estimates.

deque 几乎可以在任何地方充当 vector 的替代品,并且可能应该被视为 C++ 中的默认"容器(考虑到其更灵活的内存要求);首选 vector 的唯一原因是当您必须保证序列的连续内存布局时.

deque can serve as a replacement for vector almost everywhere and should probably have been considered the "default" container in C++ (on account of its more flexible memory requirements); the only reason to prefer vector is when you must have a guaranteed contiguous memory layout of your sequence.

相关文章