A "Duh" moment

I'm putting together solutions for homework exercises for this class I'm teaching. One of the exercises is to implement a simplified version of the standard list template, including erase.

To simplify the code, I decided to implement single-element erase in terms of generalized erase:

template<class T> class List {
    // ...
    List_iter erase(List_iter, List_iter); // Implemented elsewhere
    List_iter erase(List_iter it) {
        return this->erase(it, it);
    }
    // ...
};

It took surprisingly long for me to see the obvious mistake I had made. How long did it take you to spot it?

In case you haven't seen it yet, the problem is that the call to erase(it, it) is wrong: It erases an empty range. This fact should be obvious because the two arguments to erase are the same.

Having seen that, I can at least give myself credit for also seeing that

    List_iter erase(List_iter it) {
        return this->erase(it, ++it);
    }

would have made matters worse, because it modifies it twice between sequence points.

So I had to do it this way:

    List_iter erase(List_iter it) {
        List_iter next = it;
        return this->erase(it, ++next);
    }

Sometimes the simplest things cause the most trouble.

Posted by Andrew Koenig at 09:31 AM  Permalink