是否有类似 std::remove() 的东西不保留向量保留元素的顺序？

Question

在 C++14 中，我有一个std::vector值，我想删除与给定值匹配的所有元素，并且我不关心在删除后保留元素的顺序。规范规定std::remove保留剩余元素的相对顺序。

是否有内置算法可以执行类似 a 的操作std::remove，但不保留顺序？我希望这样做，因为将向量末尾的元素交换到要删除的位置的工作量较少，从而打乱向量中元素的顺序。该算法仍然是线性的，因为它必须访问每个元素来检查是否被删除，但如果最终只有少数项目被删除，那么它必须在每个元素上执行的持续工作量就会大大减少。

Answer 1

是否有内置算法可以执行类似 std::remove 的操作，但不保留顺序？我希望这样做，因为将向量末尾的元素交换到要删除的位置的工作量较少

std::partition()是一种可以满足您要求的算法。您需要为要保留的值提供谓词，而不是要删除的值。

例如，给定std::vector v;，而不是

v.erase( std::remove(v.begin(), v.end(), value), v.end() );

你会写：

v.erase( std::partition(v.begin(), v.end(), [&](const auto& elem){return elem!=value;}), v.end() );

然而，这并不一定比std::remove(). 问题是它std::remove()不会交换 - 相反，它只移动元素，使要删除的元素保持在任意移出状态。这可能比交换更有效，尤其是在交换向量元素并不便宜的情况下。