我确实不需要记住位置,但我也不需要随机访问。我希望插入速度快。在插入方面,deque和vector是否需要付出很高的代价?我应该使用链表(list)吗?
我的另一个选择是拥有第二个双向队列列表,在遍历每个元素时将其插入到另一个双向队列列表中,除非我需要进行上述插入操作。由于这是一个性能密集型应用程序,因此这需要很快速。但是我正在使用大量指针(每个元素都是指针),这使我感到不安,但没有其他办法,所以我应该假设L1缓存总是会错过吗?
在这种情况下,我会建议使用std::vector
,但是使用第二个std::vector
来进行您的批量变异,适当地使用reserve()
,然后将两个向量swap()
。
更新
它的一般形式如下:
std:vector<t_object*> source; // << source already holds 10000 elements
std:vector<t_object*> tmp;
// to minimize reallocations and frees to 1 and 1, if possible.
// if you do not swap or have to grow more, reserving can really work against you.
tmp.reserve(aMeaningfulReserveValue);
while (performingMassMutation) {
// "i scan through each element and lets every 20 elements"
for (twentyElements)
tmp.push_back(source[readPos++]);
// "every 20 elements i'll need to insert an new element"
tmp.push_back(newElement);
}
// approximately 500 iterations later…
source.swap(tmp);
vector
大规模突变和push_back
比std::list
插入快7倍。push_back
比vector
的范围插入更快。std::vector::swap()
不需要移动或重新分配元素--它只能交换内部(前提是分配器是相同类型)。首先,回答所有关于性能的问题的答案都是“进行基准测试”。始终如此。现在...
如果您不关心内存开销,也不需要随机访问,但您确实关心具有恒定插入时间,则list
可能适合您。
std::vector
将在具有足够容量时以常数时间插入在末尾。当超过容量时,它需要一个线性时间复制。 deque
更好,因为它链接离散分配,避免了完全复制,并让您在前面进行恒定时间插入。随机插入(每20个元素)将始终是线性时间。
至于缓存局部性,vector
是您可以得到的最好的(连续的内存),但是您说您关心的是插入而不是查找;在我的经验中,当情况如此时,您不关心扫描到转储时缓存变得多热,因此list
的差劲行为并不太重要。
reserve
以大于向量大小的容量时,下一个插入到末尾将是常数时间。这是C++标准的一部分。而“平摊常数”并不意味着特定的插入是常数时间 - 这就是我所说的。 - Borealiddeque
的评论是错误的。当容量已满时,只需分配另一个“页面”,不需要复制先前的元素。 deque
基本上是指向包含固定数量元素的页面的指针数组。 - Xeodeque
不会将所有元素放在一起。已更正。 - Borealidstd::vector::reserve
来分配必要的内存。你传递给reserve
的值不需要精确,只需要近似;如果比所需大小小,向量将在必要时自动调整大小。std::vector/deque::insert
等函数所做的复制次数与插入位置后面的元素数量成比例(需要移动的元素数量)。对于std::vector
,最坏情况是在容器前面插入,时间复杂度为O(N)
。如果要插入M
个元素,则最坏情况的时间复杂度为O(M*N)
,不是很好。
如果超出了容器的容量,就可能涉及到重新分配内存。你可以通过确保预先使用::reserve
来避免重新分配。
另一个建议是将数据复制到第二个std::vector/deque
容器中,这样始终可以组织以实现O(N)
的复杂度,但代价是暂时存储两个容器。
使用std::list
可以实现原地O(1)
插入,但代价是额外的内存开销(存储链表指针等)和降低的内存局部性(列表节点不是连续分配的)。您可以通过使用池化内存分配器(例如 Boost pools)来提高内存局部性。
总的来说,您需要进行基准测试以确定哪种方法是“最快”的。
希望这能帮到您。
list<void*>
是否和 2 个 vector<void*>
一样大。 - user345372 * N * sizeof(data_type)
。1个列表将是:N * sizeof(data_type) + 2 * N * sizeof(void *)
。如果你的data_type
大小很小(我认为你说它只是一个指针),那么列表可能会使用更多内存... - Darren Engwirdavector
和deque
绝对不适合您:对于这些容器,在每次插入时,该元素和末尾之间的所有元素都必须被移动。在内置容器中,list
几乎肯定是您最好的选择。然而,对于您的情况,更好的数据结构可能是VList,因为它提供了更好的缓存局部性,但这并不是由C++标准库提供的。维基百科页面链接到一个C++实现,但从接口的快速查看来看,它似乎并不完全兼容STL;我不知道这是否对您造成了问题。
当然,最终确定最佳解决方案的唯一方法是测量性能。
vector::swap
是常数时间的。即使每个向量都有数百万个元素,也只会在它们之间交换两到三个指针,例如m_start
、m_end
和m_storage_end
。即使在向量中存储大型对象的情况下,vector::swap
也会非常快速。 - Emile Cormier