多线程向std::vector添加元素：三种方案的开销对比与最佳实践

假设我们有一个已包含200个元素的std::vector<Element> vec，现在需要向其中添加count个元素，每个新元素基于随机选取的旧元素（前200个中的一个）创建：

for (int index = 0; index < count; index++) {
  vec.push_back(Element(vec[someRandomIndex(0, 200), ...]));
}

count数值极大（例如同样为200），且Element的构造函数并非轻量，因此并行化新元素的创建操作存在收益。目前有三种实现方式：

1. 调整vec大小并原地修改元素

vec.resize(vec.size() + count);
// 代码将被拆分至多个线程处理，无重叠无数据竞争
for (int index = 0; index < count; index++) {
  vec[200+index] = Element(vec[someRandomIndex(0, 200), ...]);
}

2. 创建大小为count的结果vector，分块修改后整体push_back至vec，此方法会占用额外内存，且元素移动复杂度为线性。
3. 为vec添加std::mutex，将push_back调用置于临界区。此方法开销较高，因为每次写入前需读取旧元素创建新元素。

请问哪种技术的开销最小？是否有通用实践？注：200仅为示例，实际数值可能更大。

开销对比 #

• 方法1开销最小：
  这种方式通过resize一次性完成内存扩容，提前为新元素分配好连续空间。线程可以各自处理独立的索引区间，完全没有锁竞争，也不需要额外内存存储临时数据。元素构造完成后直接写入预分配的位置，避免了push_back可能带来的多次扩容开销。如果Element支持定位构造，还可以用new (&vec[200+index]) Element(...)替代赋值操作，彻底消除临时对象的拷贝/移动开销，进一步提升效率。

• 方法2存在额外开销：
  需要额外申请一块能容纳count个Element的内存，构造完成后还要将临时vector的元素批量移动到原vec中。虽然移动操作通常比拷贝高效，但线性时间的移动加上额外内存的分配、释放，整体开销明显高于方法1，仅适合原vector无法提前扩容的特殊场景。

• 方法3开销最高：
  每次push_back都要执行加锁、解锁操作，锁竞争会随着线程数量增加急剧加剧。此外，频繁的push_back还可能触发原vector的多次内存扩容，导致所有元素拷贝，双重开销叠加后，性能表现最差，完全不适合count极大的场景。

通用实践 #

1. 优先选择预分配内存+并行原地构造：当能提前确定新增元素数量时，先通过resize或reserve（如果用emplace的话）分配足够内存，再让线程处理独立的索引范围，这是并行批量添加元素的最优方案。定位构造（placement new）能最大化消除对象拷贝开销，是这类场景的最佳实践。
2. 避免锁保护的高频写入操作：std::vector并非线程安全容器，高频的锁保护push_back会带来严重的性能瓶颈，除非count极小，否则绝不推荐。
3. 临时vector合并的适用场景：当原vector无法提前扩容（比如被其他线程只读访问且不能修改大小），可以让每个线程构造独立的子vector，最后合并到原vector。只有当合并的开销远低于锁竞争开销时，这种方案才值得考虑。

内容的提问来源于stack exchange，提问作者Kotaka Danski