listc++11iterationlistiteratorremove-if

Constraining remove_if on only part of a C++ list


I have a C++11 list of complex elements that are defined by a structure node_info. A node_info element, in particular, contains a field time and is inserted into the list in an ordered fashion according to its time field value. That is, the list contains various node_info elements that are time ordered. I want to remove from this list all the nodes that verify some specific condition specified by coincidence_detect, which I am currently implementing as a predicate for a remove_if operation.

Since my list can be very large (order of 100k -- 10M elements), and for the way I am building my list this coincidence_detect condition is only verified by few (thousands) elements closer to the "lower" end of the list -- that is the one that contains elements whose time value is less than some t_xv, I thought that to improve speed of my code I don't need to run remove_if through the whole list, but just restrict it to all those elements in the list whose time < t_xv.

remove_if() though does not seem however to allow the user to control up to which point I can iterate through the list.

My current code. The list elements:

struct node_info {
char   *type = "x";
int    ID    = -1;
double time  = 0.0;
bool   spk   = true;
};

The predicate/condition for remove_if:

// Remove all events occurring at t_event
class coincident_events {
double t_event; // Event time
bool   spk;     // Spike condition
public:
    coincident_events(double time,bool spk_) : t_event(time), spk(spk_){}
    bool operator()(node_info node_event){
        return ((node_event.time==t_event)&&(node_event.spk==spk)&&(strcmp(node_event.type,"x")!=0));
    }
};

The actual removing from the list:

void remove_from_list(double t_event, bool spk_){
// Remove all events occurring at t_event
coincident_events coincidence(t_event,spk_);
event_heap.remove_if(coincidence);
}  

Pseudo main:

int main(){
    // My list
    std::list<node_info> event_heap;

    ...
    // Populate list with elements with random time values, yet ordered in ascending order
    ...

    remove_from_list(0.5, true);

    return 1;
}

It seems that remove_if may not be ideal in this context. Should I consider instead instantiating an iterator and run an explicit for cycle as suggested for example in this post?


Solution

  • Thanks. I used your comments and came up with this solution, which seemingly increases speed by a factor of 5-to-10.

    void remove_from_list(double t_event,bool spk_){
        coincident_events coincidence(t_event,spk_);
        for(auto it=event_heap.begin();it!=event_heap.end();){
            if(t_event>=it->time){
                if(coincidence(*it)) {
                    it = event_heap.erase(it);
                }
                else
                    ++it;
            }
            else
                break;
            }
    }
    

    The idea to make erase return it (as already ++it) was suggested by this other post. Note that in this implementation I am actually erasing all list elements up to t_event value (meaning, I pass whatever I want for t_xv).