为什么数组被认为比STL容器更好？

array与std::queue，这在时间上更好，为什么？为什么数组被认为比STL容器更好？

我写了一个图形处理算法，其中边界顶点存储在std::queue中，并使用push_back()和pop_front()来访问。当我重新实现前端和前端指针指向边界顶点开始和结束的阵列时，我获得了更好的时间结果。对于数据量足够大的数组，数组是否真的比队列更快？

来源

2016-09-21 Bibek Bhattarai

您正在比较苹果和橘子。如果你需要一个队列结构，为什么要使用不是队列的东西？ – NathanOliver

访问数组中和矢量中的元素都是O（1）。时间差异，如果有的话，可以忽略不计。 *不同*是向量是*动态*，当您向矢量添加元素时，可能需要调整其自身的大小，其中包括复制现有数据。这可能很慢。如果您大致了解所需元素的数量，则可以为矢量预留该数量，速度差可以回到几乎为零。如果你想要一个具有编译时固定数量的元素的容器，请改用'std :: array'。 –

一个是静态的，另一个是动态的。 –

对于大多数机器来说，数组速度更快，因为数组的连续元素可以加载到同一个高速缓存行（或者预先加载到高速缓存中）。由于L1缓存读取速度比主存储器访问速度快200倍，因此任何需要获取指针的内容都可能不在缓存中，并且需要更长的主内存获取周期。

https://www.youtube.com/watch?v=YQs6IC-vgmo

来源

2016-09-21 17:28:08 Gregg

std :: queue的实现倾向于分配增加大小的连续内存块（例如，前16个元素的块，然后是他下32个元素的块），其大小或高于高速缓存行大小。所以区别在于后续缓存未命中是否连续，这通常不会产生影响。 –

为什么数组被认为比STL容器更好？

回答

相关问题