并行插入节点时tbb::concurrent_vector的size()访问竞态问题

用tbb::concurrent_vector nodes_并行往树里添加节点时，调用nodes_.size()会出现竞态条件：两个线程同时添加节点后，返回的size()结果和预期不符。要是用mutex锁解决竞态，又会废掉并行添加的优势，白用了concurrent_vector。

想在继续用tbb::concurrent_vector的前提下，避免访问size()时的竞态问题。下面是多线程运行的简化代码：

int PTree::makeNode(int item) {
  nodes_.push_back(PNode(item));
  return nodes_.size() - 1;
}

方法1：利用emplace_back的返回值计算索引 #

tbb::concurrent_vector的元素不会被移动（和std::vector内存布局不同，它采用分段存储），所以可以通过emplace_back返回的迭代器直接计算元素索引，完全绕开size()调用：

int PTree::makeNode(int item) {
  auto it = nodes_.emplace_back(item);
  // 通过地址差计算索引，concurrent_vector不会移动元素，地址始终有效
  return static_cast<int>(&*it - &nodes_[0]);
}

注意：如果代码里调用过nodes_.clear()或者nodes_.shrink_to_fit()，首元素地址可能失效，这个方法就不适用了。

方法2：用原子计数器单独维护节点数量 #

自己加一个std::atomic<int>类型的计数器，每次push_back后原子递增，直接用计数器的值作为新节点的索引，彻底避开size()：

#include <atomic>

class PTree {
private:
  tbb::concurrent_vector<PNode> nodes_;
  std::atomic<int> node_count_{0};
public:
  int makeNode(int item) {
    nodes_.push_back(PNode(item));
    // fetch_add返回递增前的值，正好是新节点的索引
    return node_count_.fetch_add(1, std::memory_order_relaxed);
  }
};

这个方法通用性更强，不管concurrent_vector有没有被clear过，只要保证push_back和计数器递增一一对应就行。只要内存分配不出问题（tbb::concurrent_vector::push_back默认不会抛异常），就不会有问题。

方法3：使用grow_by批量添加（适合批量场景） #

如果业务场景支持批量创建节点，用tbb::concurrent_vector的grow_by方法更高效。它会原子性地添加一批元素，并返回指向第一个新元素的迭代器，同样可以通过地址差计算索引：

// 单个元素的示例（批量场景直接传批量数据即可）
int PTree::makeNode(int item) {
  std::vector<PNode> temp{PNode(item)};
  auto it = nodes_.grow_by(temp.begin(), temp.end());
  return static_cast<int>(&*it - &nodes_[0]);
}

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