删除for-each循环中的一些向量元素,而不迭代整个向量

Question

我有一个向量,我正在搜索其中的元素,同时用for-each循环迭代向量.如果我在搜索过程中发现任何无效元素,我想将它们从向量中删除.

基本上,我想做这样的事情:

for (auto el : vec) {
    if (el == whatImLookingFor) {
        return el;
    } else if (isInvalid(el)) {
        vec.erase(el);
    }
}

我看了一些像这样和这个的其他问题,但都推荐使用std::remove_if.这将迭代整个向量并删除所有无效元素,而不是仅迭代直到找到我正在寻找的元素,并忽略之后的任何元素.

这样做有什么好办法？

Answer 1

您仍然应该使用std::remove_if,只需std::find提前致电.

auto el = std::find(vec.begin(), vec.end(), whatImLookingFor);
auto p = std::remove_if(vec.begin(), el, isInvalid);

// returns the iterator, not the element itself.
// if the element is not found, el will be vec.end()
return vec.erase(p, el);

这通常比一次删除一个元素更有效.

Answer 2

我很好奇这个的表现,所以我跑了一个快速天真的基准比较Benjamin的发现然后部分清洁和hnefatl的for循环.本杰明确实更快:快了113倍.令人印象深刻.

不过我很好奇,大部分的计算打算,因为它比的总和remove_if和find,这是实际上是通过遍历数组的唯一功能.然而,事实证明,vec.erase他的代码中的行实际上非常慢.这是因为remove_if他正在从找到值的起点到位置清洁区域,这导致阵列中间与无效值之间存在间隙.vec.erase然后必须复制剩余的值以填补空白,最后调整数组的大小.

我用全尺寸remove_if/ vec.erase后跟a 运行了第三次测试find,所以差距发生在最后并且不需要复制,只是截断.事实证明它的速度提高了约15%,并使整个矢量保持清洁.请注意,这假设测试有效性很便宜.正如克里斯在评论中所指出的那样,如果这不仅仅是一些简单的比较,那么本杰明的答案就会赢得胜利.

代码

auto p = std::remove_if(vec.begin(), vec.end(), isInvalid);
vec.erase(p, vec.end());
return std::find(vec.begin(), vec.end(), whatImLookingFor);

基准

Answer 3

这是保持循环结构的问题的直观方法 - 虽然它只执行单次传递,但由于重复擦除,它可能比双遍方法效率低.对于这种更有效的方法,你应该使用Benjamin Lindley的答案.

修改你给出的第一个链接的答案中的代码,它看起来像这样符合你的规范:

for (auto i = vec.begin(); i != vec.end();)
{
    if (*i == whatImLookingFor)
        return i;
    else if (isInvalid(*i))
        i = vec.erase(i);       // slow, don't use this version for real
    else
        ++i;
}

• 如果我们找到您要搜索的元素,我们将返回一个迭代器.
• 如果我们在途中发现了一个无效元素(但不是在所需元素之后),我们将其删除.
• 我们通过保持返回的迭代器来避免迭代器失效erase.

您仍然需要处理未找到元素的情况,可能是通过返回vec.end().