即使谓词 returns 为假，remove_if 也会删除元素？

Question

我正在写一个八叉树算法。内部函数我遍历八叉树。我得到节点指针和 Sphere 作为输入。我检查节点是否应该保持球体然后我想添加它到节点s object list and remove it from its parents 列表。以下是代码

functionBody()
{
 .....

  if (!node->objectList.empty())
      node->objectList.erase(std::remove_if(node->objectList.begin(), node->objectList.end()-1 , [&t](auto& temp) { return temp == t; }));

...
}

typedef struct Sphere
{
    Sphere() = default;
    Sphere(const Vector3 centre_, const float radius_, const Material& material_) : centre(centre_), radius(radius_), material(material_)
    {
        assert(radius != 0);
        invRadius = 1.0 / radius;

        Vector3 radiusOffset = Vector3(radius);
        aabb.min = Vector3(centre - radiusOffset);
        aabb.max = Vector3(centre + radiusOffset);
    }

    bool operator==(const Sphere& rhs)
    {
        return (centre == rhs.centre) && (radius == rhs.radius);
    }

    Vector3 centre;
    float radius;
    float invRadius;
    Material material;
    AABB aabb;

}Sphere;

如您所见，我已经为 Sphere 定义了 operator==。

我看到 remove_if 正在删除元素，即使谓词返回 false。

例如，第一次迭代它找到一个球体 t 并使用 remove_if 从父向量中删除它。这个 t 最后出现在 vector 中。现在考虑父级在其向量中仍然有 3 个球体，但是，当我现在去另一个子级时，我们仍然尝试在父级中搜索 t 并且 remove_if 仍然删除最后一个条目。我不明白为什么？

Answer 1

当您调用只接受一个迭代器（而不是一系列迭代器）的擦除方法时，算法 std::remove_if 是用指定的容器元素范围的第二个迭代器调用的，例如

node->objectList.end()-1

那么即使在容器中找不到元素，算法 remove_if 也会 return 迭代器 node->objectList.end()-1 指向容器中的有效对象。该对象将从容器中删除。

这是一个重现该问题的演示程序。

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main() 
{
    std::vector<int> v = { 1, 3, 5, 7, 9 };

    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout << '\n';

    while ( v.size() > 1 )
    {
        v.erase( std::remove_if( std::begin( v ), std::prev( std::end( v ) ),
                                 []( const auto &item )
                                 { 
                                    return item % 2 == 0; 

                                 } ) );
    }

    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout << '\n';

    return 0;
}

它的输出是

1 3 5 7 9 
1

即vector中none个元素为偶数。尽管如此，除了一个元素之外的所有元素都从向量中删除了。

看来您指定的范围不正确。它应该被指定为一对

node->objectList.begin(), node->objectList.end()

或者在擦除一个元素之前，你应该检查 returned 迭代器是否等于 node->objectList.end() - 1 （前提是你确实想使用问题中显示的范围）。在这种情况下，不应调用擦除方法。或者你应该指定一个迭代器的擦除范围，比如

if (!node->objectList.empty())
      node->objectList.erase(std::remove_if(node->objectList.begin(), node->objectList.end()-1 , [&t](auto& temp) { return temp == t; }).
                             node->objectList.end()-1);

再次假设您确实想使用范围的第二个迭代器，例如 node->objectList.end()-1 而不是 node->objectList.end()。

Answer 2

std::remove_if returns end 迭代器在找不到要删除的任何内容时提供。您已将 node->objectList.end()-1 作为结束迭代器，它是指向 node->objectList 中最后一个元素的迭代器。这是当您找不到 t 时传递给 erase 的内容，因此最后一个元素将被删除。

要解决此问题，请使用采用一系列元素的 erase 的重载：

if (!node->objectList.empty())
{
    auto end_iter = node->objectList.end();
    auto to_remove = std::remove_if(
        node->objectList.begin(), end_iter, 
        [&t](auto& temp) { return temp == t; });

    node->objectList.erase(to_remove, end_iter);
}

现在，如果 t 未找到，erase 将不会执行任何操作。在这种情况下，remove_if returns end_iter 和 erase 试图擦除由 end_iter 及其自身定义的空范围内的元素。

我不确定你为什么要使用 node->objectList.end() - 1。我假设这是一个错误或解决崩溃的方法，否则您可能会遇到以前的代码。

即使谓词 returns 为假，remove_if 也会删除元素？

remove_if removes element even when predicate returns false?

c++

algorithm

vector

c++-standard-library

erase-remove-idiom