从std::vector中擦除是否有比swap-and-pop更快的方法？
我问这个是因为关于 SO 的其他相关问题似乎是针对旧版本的 C++ 标准，没有提到任何形式的并行化，或者专注于在删除元素时保持排序/索引相同。
我有一个可能包含数十万或数百万个元素的向量（它们是相当轻的结构，假设它们被压缩了大约 20 个字节）。
由于其他限制，它必须是 astd::vector并且其他容器不起作用（例如std::forward_list），或者在其他用途中甚至不太理想。
我最近从简单的it = std::erase(it)方法切换到使用 pop-and-swap 使用这样的东西：
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有效地从 a 中删除许多非连续元素？就像将索引向量传递给erase()C++ 并让 C++ 在幕后做一些魔术以最大程度地减少数据移动？
如果是这样，我可以让线程单独收集必须并行删除的索引，然后组合它们并将它们传递给擦除（）。
回答
看看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) 允许指定执行策略。
THE END
二维码