哪个是C++中最快的STL数据结构来迭代大量元素？

Question

元素遵循某种属性,其中每个元素通过某种复杂关系与其前一个元素相关(假设没有已知的简单公式来找出第i个元素)我想计算该系列的某个元素的值我必须计算每个元素的值,并在此过程中迭代完整的元素列表.

我使用了一个数组,它可能会导致一些内存分配错误(SIGABRT).我用了一个矢量,同样的错误.也许是因为元素的数量巨大而且它们是连续存储的.然后我使用了一个列表,没有这样的错误,但它花费的时间超过了可接受的时间限制.

Answer 1

你可以尝试std :: deque

与std :: vector相反,deque的元素不是连续存储的:典型的实现使用一系列单独分配的固定大小的数组.

deques上常见操作的复杂性(效率)如下:

Random access - constant O(1)
Insertion or removal of elements at the end or beginning - constant O(1)
Insertion or removal of elements - linear O(n)