c++algorithmvectorstderase-remove-idiom

remove_if removes element even when predicate returns false?


I am writing an octree algorithm. Inside function I traverse octree. I get node pointer and Sphere as input. I check if node should hold sphere then I want to add it to nodes object list and remove it from its parents list. following is code

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;

As you can see for Sphere I have operator== defined.

I see that remove_if is removing element even when predicate is returning false.

for example, first iteration it finds one sphere t and removed it from parents vector using remove_if. This t was present at last of vector. consider now parent remains with 3 spheres in its vector but, when I go to other child now we still try to search t in parent and remove_if still removes last entry. I don't get why?


Solution

  • std::remove_if returns the end iterator provided when it doesn't find anything to remove. You've given node->objectList.end()-1 as the end iterator which is an iterator to the last element in node->objectList. This is what you pass to erase when you don't find t so the last element gets erased.

    To fix the problem, use the overload of erase that takes a range of elements :

    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);
    }
    

    Now if t isn't found erase won't do anything at all. In that case, remove_if returns end_iter and erase tried to erase the elements in the empty range defined by end_iter and itself.

    I'm not sure why you were using node->objectList.end() - 1. I'm assuming it was either a mistake or a workaround for the crash that you would otherwise likely get with the previous code.