从 std::vector 中擦除是否有比交换和弹出更快的方法？

Question

我问这个是因为关于 SO 的其他相关问题似乎是针对旧版本的 C++ 标准，不提及任何形式的并行化，或者专注于保持 ordering/indexing 与元素已删除。

我有一个可能包含数十万或数百万个元素的向量（它们是相当轻的结构，假设它们被压缩，大约 20 个字节）。

由于其他限制，它必须是 std::vector 并且其他容器将无法工作（如 std::forward_list），或者在其他用途。

我最近从简单的 it = std::erase(it) 方法转换为使用像这样的弹出和交换方法：

for(int i = 0; i < myVec.size();) {
  // Do calculations to determine if element must be removed
  // ...

  // Remove if needed
  if(elementMustBeRemoved) {
    myVec[i] = myVec.back();
    myVec.pop_back();
  } else {
    i++;
  }
}

这很有效，并且是一个重大改进。它将方法的运行时间减少到之前的 61%。但我想进一步改进。

C++ 是否有一种方法可以有效地从 std::vector 中删除许多不连续的元素？就像将索引向量传递给 erase() 并让 C++ 在幕后做一些魔术以最大程度地减少数据移动？

如果是这样，我可以让线程单独收集必须并行删除的索引，然后组合它们并将它们传递给 erase()。

Answer 1

看看std::remove_if算法。你可以这样使用它：

auto firstToErase = std::remove_if(myVec.begin(), myVec.end(),
                                   [](const & T x){
                                   // Do calculations to determine if element must be removed
                                   // ...
                                   return elementMustBeRemoved;});
myVec.erase(firstToErase, myVec.end());

cppreference 表示以下代码是 remove_if 的可能实现：

template<class ForwardIt, class UnaryPredicate>
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
   first = std::find_if(first, last, p);
   if (first != last)
       for(ForwardIt i = first; ++i != last; )
           if (!p(*i))
               *first++ = std::move(*i);
   return first;
}

它不是与最后一个元素交换，而是连续移动通过一个容器，构建一个应该被擦除的元素范围，直到这个范围位于向量的最末端。这看起来像是一个对缓存更友好的解决方案，您可能会注意到在非常大的向量上有一些性能改进。

如果您想尝试并行版本，有一个版本 (4) 允许指定执行策略。

Answer 2

或者，从 C++20 开始，您可以稍微减少输入并使用 erase_if。但是，在这种情况下，您将失去选择执行策略的选项。

Answer 3

Is there an even faster approach than swap-and-pop for erasing from std::vector?

自从 C++11 以来，在不保留顺序的情况下从 vector 中移除单个元素的最佳方法是移动和弹出，而不是交换和弹出。

Does C++ have a method to remove many non-consecutive elements from a std::vector efficiently?

移除-擦除（C++20 中的 std::erase）习惯用法是标准提供的最有效的。 std::remove_if 确实保留了顺序，如果您不关心这一点，那么可能会有更高效的算法。但是标准库没有开箱即用的 unstable remove。算法如下：

找到要删除的第一个元素 (a)
找到最后一个不被删除的元素 (b)
将 b 移动到 a。
在 a 和 b 之间重复，直到迭代器相遇。

有提案P0048 to add such algorithm to the standard library, and there is a demo implementation in https://github.com/WG21-SG14/SG14/blob/6c5edd5c34e1adf42e69b25ddc57c17d99224bb4/SG14/algorithm_ext.h#L84

从 std::vector 中擦除是否有比交换和弹出更快的方法？

Is there an even faster approach than swap-and-pop for erasing from std::vector?

c++

stdvector

c++20