remove_if with boost::bind is slow

Question

I have a std::list of classes and want to remove entries that are marked for delete. I am using std::remove_if and erase.

class MyClass
{
    bool isDone(MyData& myData)
    {
        return myData.isDone();
    }

    void removeIfDone(std::list<MyData>& myList)
    {
        std::list<MyData>::iterator it =
            remove_if(myList.begin(), myList.end(), 
                  boost::bind(&MyClass::isDone, this, _1));
        myList.erase(it, myList.end());
    }
};

I am running on a small processor for which memory allocation and deallocation is very expensive. This remove is calling new and delete thousands of times in my application.

I have previously used boost::ref when passing a non-trivial variable as a bind parameter but in this case I think it is probably the creation and destruction of the functor itself or the copying of it which is causing the problem.

I would like to do something like

boost::bind(&MyClass::isDone, boost::ref(this), boost::ref(_1));

I can't find documentation on what is being created and destroyed. So my simple question is how do I make this more efficient?

Answer 1

Try replacing the call to std::remove_if with std::list::remove_if. The latter should only copy some pointers from the preceding and succeeding elements, instead of trying to move the elements to the end of the list, which is the cause of the multiple allocations you're seeing. An additional benefit is that since it is a member function of std::list, it actually removes (i.e. erases) the elements matching your criterion.

class MyClass
{
    bool isDone(MyData& myData)
    {
        return myData.isDone();
    }

    void removeIfDone(std::list<MyData>& myList)
    {
        myList.remove_if( boost::bind( &MyClass::isDone, this, _1 ) );
    }
};

Answer 2

You could perhaps solve your problem using a simple functor that you pass to your std::remove_if. This way you don't need to pass any args to it in the remove_if and save yourself a boost::bind

struct functor
{
public:
    bool operator()(MyData& mydata)
    { 
       return mydata.IsDone();
    }   
};

void removeIfDone(std::list<MyData>& myList)
{
   std::list<MyData>::iterator it =
     remove_if(myList.begin(), myList.end(), 
         functor()); //call operator() on functor
     myList.erase(it, myList.end());
}

An example that compiles here