1
我有一个令人费解的问题。C++ - 为什么插入类型的顺序影响向量性能（GCC 4.81）
上下文是：未知大小的数据集，该数据集经常迭代，但在初始化之后具有最小的插入（初始化时的速度不是问题）。 数据分为未知数量的有序索引。
所以我使用矢量，但根据索引号定位插入元素。 我发现的奇怪的事情是插入的顺序影响迭代性能。
具体来说，我正在处理一个测试场景，其中我被添加三个相同的元件，具有索引0，1和2
现在，这取决于它们被添加到载体中的顺序上，他们要么是的push_back 'd或.insert'd，以创建正确的数字线性顺序。
我创建了一个遍历这些循环的循环，并查看了在给定的时间范围内（10秒）我可以完成多少个循环。
我发现那是什么，如果我加入他们的顺序是： 1，2，0
我得到了比我加入他们在这个量级，平均为60多个循环：
2， 0,1
和30多个环比该顺序：
0，1，2
在每种情况下插入被正确排序，使得向量内的顺序为0,1,2。它们之间的唯一区别是所需的插入类型。
对于012，每个插入是推回。 对于201，第一个是推回，第二个是插入在.begin（），第三个是插入在对应于'2'的迭代器之前。 对于120，第一个是推回，第二个是推回，第三个是在.begin（）处的插入。
为什么第三种情况会更高效？ 再次重申，有的顺序或存储的数据的类型或数量方面没有方法之间的区别 - 在每种情况下矢量的所得顺序为0，1，2
我测试这与GCC 4.8.1有和没有-O2。结果是可重复的，1-4次回波的波动很小。 为了公平起见，差异仍然很小 - 我们谈论了15000个左右的60个回路。
我能想到的唯一解释是插入类型改变了向量的分配，可能导致更好，或者更糟的是，表现。
你已经通过一个顺序列出案例，然后在另一个顺序中讨论它们，使你的问题变得复杂起来。 – ooga
push_back的成本通常低于任意插入std :: vector中的元素。 push_back是最坏情况的线性时间O（n），但是是平均不变的摊销时间O（1）。最坏的情况发生在向量必须重新调整大小时，因此所有元素都必须复制到新分配的内存中。另一方面，向量中插入一个元素是线性时间，因为你必须移动它后面的所有元素。 – 101010
你是如何评价这件作品的？这些是什么样的元素？ 10秒内15000个循环听起来很慢。 – user2357112