A short article about removing items from a standard C++ container.
When using the C++ Standard Template Library, one has to be careful not to invalidate iterators in a container that you're iterating over. If that makes any sense to you, then
A colleague of mine had code like this:
class TaskList {
vector<Task*> mTasks;
typedef vector<Task*>::iterator TaskIter;
void removeTask(Task* t) {
TaskIter it = find(mTasks.begin(),mTasks.end(),t);
if(it != mTasks.end()) { mTasks.erase(it); }
}
public:
void addTask(Task* t) { mTasks.push_back(t); }
void processQueue() {
for(TaskIter loopit=mTasks.begin();loopit!=mTasks.end();++loopit) {
Task* task = *loopit;
if(task->isNotDone()) {
task->doSomething();
}
else {
removeTask(task);
}
}
}
};
You might be surprised to hear that the program crashed when the first task had to be removed. The reason is that the removeTask() function erases an item out the collection which invalidates the iterator loopit. When the for-loop tries to increment the iterator, we get unexpected results.
This is a frustrating problem, but it can be solved. In short you have to:
- grab the iterator that is returned from the erase operation
- set your loop iterator to that returned iterator
- change from a for-loop to a while-loop (to ensure that your loop iterator is not incremented when a task is removed)
Here is the modified code:
TaskIter removeTask(Task* t) {
TaskIter it = find(mTasks.begin(); mTasks.end(), t);
if(it != mTasks.end()) { it = mTasks.erase(it); }
return it;
}
void processQueue() {
TaskIter loopit = mTasks.begin();
while(loopit != mTasks.end()) {
Task* task = *loopit;
if(task->isNotDone()) {
task->doSomething();
++loopit;
}
else {
loopit = removeTask(task);
}
}
}
Yea, I’ve had to do that before too.
By the way, I think that should be:
vector<Task*> mTasks;
typedef vector<Task*>::iterator TaskIter;
Thanks Phil, I have corrected the code in the post now.
The other thing to keep in mind is that different STL containers have different iterator semantics, and are optimized for different operations. So if random-access deletion is really important to you (and in a task queue, where you might be removing anywhere from 10-100% of the elements in the container, that would seem to be the case), your choice of container is important.
In this use case, for instance, a list would make a lot more sense, since it supports random-access constant time insertion and deletion without invalidating iterators. I would expect significant performance improvement over a vector when you are frequently removing items from the middle of the list.
On a side note, one of the best things I liked about the Accelerated C++ book from Koenig was its focus on choosing the right container for the job at hand.
Thanks,
–kirby
@Kirby: Thanks for the tips – I will definitely be keeping my eye out for a good price on Accelerated C++
. I really enjoyed Alexandrescu’s work in the same series.