Erase item from list of pointers in C++ during iterator

Alec Jacobson

April 15, 2010

weblog/

In a C++ program, I have a std::list (actually std::vector) of pointers to a class Foo:

std::vector my_list;

Maybe I have push a bunch of items onto this list and then selected one (using my UI or whatever). Anyway there is a certain item in the list that points to an instance of Foo that has the is_selected flag flipped to true. I want to implement a simple deleteSelected() function for this list. Here's what I came up with (no guarantees, my C++ skills leave a lot to be desired):

bool deleteSelected(){
  bool deleted_some = false;
  std::vector<Foo*>::iterator my_list_iterator = my_list.begin();
  while(my_list_iterator != my_list.end();)
  {
    if((* my_list_iterator)->is_selected){
      // clear the memory of this item
      delete (* my_list_iterator);
      // erase from list, returns next element in iterator
      my_list_iterator = my_list.erase(my_list_iterator);
      deleted_some = true;
    }else{
      // otherwise, just increment the iterator
      my_list_iterator ++;
    }
  }
  return deleted_some;
}

Any reason why this isn't correct? Note: Erasing this way could lead to an O(N²) running time if many items are selected. How can this be avoided with a std::vector? (Erasing all of the items is trivial, I mean how can I erase a dense general set of items in the list in linear time) Update: My friend told me that a better way to do this is with a decrementing index. Then when you erase using the index the items behind get moved but you're already done processing them and since the index is going backwards it's left in the right position. (This way is also arguably faster at least by a scale factor).