STL erase-remove idiom vs custom delete operation and valgrind

Question

This is an attempt to rewrite some old homework using STL algorithms instead of hand-written loops and whatnot.

I have a class called Database which holds a Vector<Media *>, where Media * can be (among other things) a CD, or a Book. Database is the only class that handles dynamic memory, and when the program starts it reads a file formatted as seen below (somewhat simplified), allocating space as it reads the entries, adding them to the vector (v_) above.

CD
Artist
Album
Idnumber
Book
Author
Title
Idnumber
Book
...
...

Deleting these object works as expected when using a hand-written loop: EDIT: Sorry I spoke too soon, it's not actually a 'hand-written' loop per-se.. I've been editing the project to remove hand-written loops and this actually uses the find_if algorithm and a manual deletion, but the question is till valid. /EDIT.

typedef vector<Media *>::iterator v_iter;

...
void Database::removeById(int id) {
    v_iter it = find_if(v_.begin(), v_.end(), Comparer(id));
    if (it != v_.end()) {
        delete *it;
        v_.erase(it);
    }
}

That should be pretty self-explanatory - the functor returns true if it find an id matching the parameter, and the object is destroyed. This works and valgrind reports no memory leaks, but since I'd like to use the STL, the obvious solution should be to use the erase-remove idiom, resulting in something like below

void Database::removeById(int id) {
    v_.erase(remove_if(v_.begin(), v_.end(), Comparer(id)), v_.end());
};

This, however, 'works' but causes a memory leak according to valgrind, so what gives? The first version works fine with no leaks at all - while this one always show 3 allocs 'not freed' for every Media object I delete.

Answer 1

The rule is: if you apply remove() on a vector that contains and is the owner of pointers you leak memory.

There is a nice solution in "Effective STL", by Scott Meyers. And it involves no smart pointers! Using smart pointers only to make erase-remove work is an overkill.

Here it is (from the book, Item 33). The task is to selectively remove from a vector widgets for which isCertified() returns false.

class Widget
{
  public:
    isCertified() const;
  ...
};

void delAndNullifyUncertified(Widget*& pWidget)
{
  if (!pWidget->isCertified())
  {
    delete pWidget;
    pWidget = 0;
  }
}

vector<Widget *> v;
v.push_back(new Widget);
...
// set to NULL all uncertified widgets
for_each(v.begin(), v.end(), delAndNullifyUncertified);
// eliminate all NULL pointers from v
v.erase(remove(v.begin(), v.end(), static_cast<Widget *>(0)),
        v.end();

I hope this helps.

edit (August 28th, 2012): to reflect a valid observation from Slavik81

Answer 2

In the first version, you're carefully calling delete *it. In the updated version, you're not.... v_.erase is de-allocating the pointer, but not the object the pointer references.

Answer 3

This is why you should always, ALWAYS use smart pointers. The reason that you have a problem is because you used a dumb pointer, removed it from the vector, but that didn't trigger freeing the memory it pointed to. Instead, you should use a smart pointer that will always free the pointed-to memory, where removal from the vector is equal to freeing the pointed-to memory.

Answer 4

You already have a specific answer. However, your underlying problem is that you're using naked pointers to manually manage resources. That is hard, and sometimes it hurts.
Change your type to std::vector<std::shared_ptr<Media> > and things become much easier.

(If your compiler doesn't yet support std::shared_ptr, it will very likely have std::tr1::shared_ptr. Otherwise use boost's boost::shared_ptr.)

Answer 5

There is no call to delete in the second version of removeById. Erasing an element from a vector of pointers doesn't call delete on the pointer.

The erase-remove version presented is roughly equivalent to using the original removeById, but with a small change:

void Database::removeById(int id) {
    v_iter it = find_if(v_.begin(), v_.end(), Comparer(id));
    if (it != v_.end()) {
        //delete *it;
        v_.erase(it);
    }
}

Hopefully this makes it clearer what's going on, and why the leaks are appearing.

Answer 6

Obviously your vector OWNS the objects it contains.

As you noticed the STL containers are not OO-friendly in the sense that they do not easily adapt to inheritance. You need to use dynamically allocated memory and all its woes for that.

The first and easy solution is to replace plain pointers (please, no more) by smart pointers. People will usually recommend shared_ptr, but if you have access to C++0x prefer them unique_ptr.

There is also another solution that you should considerate. Containers that mimicks the STL ones but have been designed to work with inheritance hierarchy. They use pointers under the hood (obviously) but relieves you of the tedium of managing the memory yourself and the overhead associated with smart pointers (especially shared_ptr).

Behold the Boost Pointer Container library!

It is clearly here the best solution, for it has been created exactly for the problem you are trying to solve.

Furthermore, its containers are (mostly I think) STL compliant, so you'll be able to use the erase/remove idiom, the find_if algorithm, etc...

Answer 7

This means that the second version is incorrect. If you want to use it, consider shared_ptr:

typedef vector< shared_ptr<Media> > MediaVector;
...