如何编写无分支 std::vector 扫描？

我想对数组编写一个简单的扫描。我有一个std::vector<int> data我想找到元素小于 9 的所有数组索引并将它们添加到结果向量中。我可以使用分支来编写：

for (int i = 0; i < data.size(); ++i)
    if (data[i] < 9)
        r.push_back(i);

这给出了正确的答案，但我想将其与无分支版本进行比较。

使用原始数组 - 并假设data是一个 int 数组，length是其中的元素数量，并且r是一个有足够空间的结果数组 - 我可以写如下内容：

int current_write_point = 0;
for (int i = 0; i < length; ++i){
    r[current_write_point] = i;
    current_write_point += (data[i] < 9);
}

我如何使用向量获得类​​似的行为data?

我们来看看实际情况编译器输出 https://godbolt.org/g/yB0bSg:

auto scan_branch(const std::vector<int>& v)
{
  std::vector<int> res;
  int insert_index = 0;
  for(int i = 0; i < v.size(); ++i)
  {
    if (v[i] < 9)
    {
       res.push_back(i);
    } 
  }
  return res;
}

这段代码显然在第 26 行有一个分支拆卸 https://godbolt.org/g/yB0bSg。如果它大于或等于 9，它只会继续处理下一个元素，但是如果小于 9，则会为 push_back 执行大量代码，然后我们继续。没什么意外的。

auto scan_nobranch(const std::vector<int>& v)
{
  std::vector<int> res;
  res.resize(v.size());

  int insert_index = 0;
  for(int i = 0; i < v.size(); ++i)
  {
    res[insert_index] = i;
    insert_index += v[i] < 9;
  }

  res.resize(insert_index);
  return res;
}

然而，这个只有一个条件移动，你可以在第 190 行看到这一点。拆卸 https://godbolt.org/g/yB0bSg。看来我们有赢家了。由于条件移动不会导致管道停顿，因此该分支中没有分支（除了 for 条件检查）。