我不知道我的确切数字,但我会尽力而为。我有一个 10000 元素的双端队列,它在一开始就填充了。然后我扫描每个元素并让我需要插入一个新元素的每 20 个元素。插入将发生在当前位置,并且可能返回一个元素。
我并不完全需要记住位置,但我也不完全需要随机访问。我想要快速插入。 deque 和 vector 是否需要为插入付出沉重的代价?我应该使用列表吗?
我的另一个选择是有一个第二个双端队列列表,当我遍历每个元素时,将它插入到另一个双端队列列表中,除非我需要执行我正在谈论的插入。这确实需要快速,因为它是一个性能密集型应用程序。但是我使用了很多指针(每个元素都是一个指针),这让我很沮丧,但没有办法解决这个问题,所以我应该假设 L1 缓存总是会丢失?
最佳答案
在这种情况下,我将从 std::vector
开始,但是使用第二个 std::vector
进行大规模突变, reserve()
适本地,然后 swap()
vector 。
更新
它将采用以下一般形式:
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);
Borealid 提出了一个很好的观点,即衡量——执行会根据您的 std 库实现、数据大小、复制的复杂性等而有很大差异。
对于具有 my 配置的这种大小的集合的原始指针,上面的 vector
质量突变和 push_back
比 快 7 倍>std::list
插入。 push_back
比 vector
的范围插入更快。
正如 Emile 在下面指出的那样,std::vector::swap()
不需要移动或重新分配元素——它可以只交换内部元素(前提是分配器类型相同) .
关于c++ - 进行少量插入时应该使用哪个 STL 容器?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9247300/