I have nearly finished an assignment that calls for implementing a media library. I have pinpointed my current solution for the addItem method in the library class as a memory leak, but so far I am not certain how to fix it. The addItem method I have so far is as follows (addBook shown; Book is a subclass of Item):

const Item* Library::addBook(const string& title, const string& author, const int nPages)
{
    Item* book = new Book(title, author, nPages);
    lib->insert(book); //lib is a set<Item*> container
    return book;
}

I understand that if I use new to allocate an instance of Item, I need to delete it. Of course, I can't delete it before the return statement, nor after. The addBook definition is part of the assignment and can't be changed.

Go through the stored items in the Library 's destructor and explicitly delete the items there.

Comments
Definitely something important that I didn't realize!

In addition, you should have a removeBook() (or some such named) method(s) for the user's convenience.

Comments
It's a good idea although I wouldn't be able to implement it for this particular assignment.

Go through the stored items in the Library 's destructor and explicitly delete the items there.

I have attempted this but I am getting an access violation.

Library::~Library()
{
	for(ItemSet::iterator itr = lib->begin();itr != lib->end();itr++)  //Causes access violation
		delete *itr;
	delete lib;  //No problem
	delete temp;  //No problem
}

This is strange since I can iterate through lib fine in methods outside of the destructor. Is there something about the destructor that disallows iterators to do their magic?

You haven't been trying to delete books anywhere else have you?
Deleting the same book twice is a sure recipe for disaster.

I see your addBook() returns a pointer to a book (why?). What else are you doing with that book pointer?

If you need to remove a book, then you need another member function, say delBook(), which removes the book from the set, and then deletes it.

Comments
You were right, although it wasn't immediately obvious!

You haven't been trying to delete books anywhere else have you?
Deleting the same book twice is a sure recipe for disaster.

Nope. In fact, the memory leaks are a result of the books not being deleted anywhere. The addBooks method is the only place in the program that allocates memory for an instance of Item (as derived class Book).

I see your addBook() returns a pointer to a book (why?). What else are you doing with that book pointer?

That was part of the skeleton code which I am not able to change. The driver routine passes this pointer to other functions, which do things like printing out the object data and adding additional data to the object. I am also not allowed to add to the parameter list, unfortunately.

If you need to remove a book, then you need another member function, say delBook(), which removes the book from the set, and then deletes it.

How would you 'remove' a book from the set? Given that the elements of the set are pointers to books, would you copy the pointer to a local variable, then perform set::erase on the set element and delete the local pointer?

The biggest problem I am seeing now (now that the conceptual stage has been breached - thank you all so far for that) is implementing the proper deletion of the individual pointers. Accessing them via iterators within the destructor has been a failure (due to an inexplicable access violation). And I can think of no other place to do this than from within the destructor.

The reason for this is because I am not allowed to modify the driver routine in any way. The driver routine declares const* Item item, which it uses to reference the pointer that addBook() returns. item is not involved in any interaction with delete. The only delete in the routine is used to free the single instance of library. Of course, since library only contains a set of pointers to all of the items (books), deleting the set itself won't be enough.

The driver routine:

// make no changes to this code, except to have it
// print out your actual name instead of "your name"

#include <iostream>
#include "Library.h"

using namespace std;

static Library  *library;
....
int main(int argc, char **argv)
{
....
    const Item	*item;
....
	// create library instance
	library = new Library();
....
    item = library->addBook();
    if (item != NULL) {
//Do Stuff with item pointer
        }
....
	delete library;  //The only occurrence of delete in this routine
....
}

By the way, the access violation (from the above ~library() example) reading location on my machine is always 0xfeeefeee if that is of any significance.
The violation is in xtree, at:

iterator begin()
{	// return iterator for beginning of mutable sequence
	return (_TREE_ITERATOR(_Lmost())); //Access violation
}

When I step through the code, the violation occurs immediately upon reaching the line

delete library;

in the main routine after everything else is done. I am unable to step into the destructor for library before the program halts (which is as shown in my prior post).
I use the same iterator elsewhere in the code with no ill effects. As far as I can tell, I am not trying to access any empty space with the iterator - library has not been deleted yet, nor have any of the elements of the lib set.
UPDATE: The base class of Book, Item, had a virtual destructor defined. The destructor does nothing other than delete a set container that was allocated in the constructor. I made it virtual because some of the derived classes had additional sets that needed to be deleted also.
I removed the virtual from ~Item() and now the iterator in ~library() no longer causes an access violation and deletes all of the elements.
This eliminated the majority of the memory leaks, but not all. The remainder (2 occurrences) seem to originate from the derived class Book, although this particular class does not add any additional dynamically allocated memory.

The base class of Book, Item, had a virtual destructor defined. The destructor does nothing other than delete a set container that was allocated in the constructor. I made it virtual because some of the derived classes had additional sets that needed to be deleted also.
I removed the virtual from ~Item()

Then the destructor of the derived class will not get called when you
do a thing like ...

Item* book = new Book(title, author, nPages);
delete book; // ~Book() will not be invoked

Maybe you should post the complete code ...

I figured out why I was getting the access violation, and yes, you would have caught it if I had posted all of my code earlier! (I was deleting a private set twice - once through the Item destructor and then through the Book destructor. I removed the redundant delete and now it is working with the virtual base destructor.) Unfortunately, I am still getting that small bit of memory leak. I think it might be because the item pointer is going out of scope. If so, I am not sure how to work around it while keeping within the requirements of the assignment (cannot modify driver routine or library definitions).

This is the debug output for the below code:

Detected memory leaks!
Dumping objects ->
{147} normal block at 0x003363E8, 11 bytes long.
 Data: <class Book > 63 6C 61 73 73 20 42 6F 6F 6B 00 
{146} normal block at 0x003363A0, 8 bytes long.
 Data: < c3     > E8 63 33 00 00 00 00 00 
Object dump complete.

Driver:

// make no changes to this code, except to have it
// print out your actual name instead of "your name"

#ifdef _WIN32
#define _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>
#endif

#include <iostream>
#include "Library.h"

using namespace std;

static Library  *library;

static void printItemSet(ostream& out, const ItemSet *itemSet)
{
    if (itemSet != NULL && itemSet->size() > 0)
		for (ItemSet::const_iterator i = itemSet->begin(); i != itemSet->end(); i++)
			library->printItem(out, (Item *) *i);
	else
		out << "none" << endl << endl;
}

int main(int argc, char **argv)
{
    ostream&	out(cout);
    const Item	*item;

	// create library instance
	library = new Library();

    // add items to library
    cout << ">>> adding items to library:\n\n";
    item = library->addBook("Book Title", "Joe Author", 249);
    if (item != NULL) {
        library->addKeywordForItem(item, "Keyword one");
        library->addKeywordForItem(item, "Another keyword");
		library->printItem(cout, item);
        }

//Two more books added like the one above

    cout << ">>> books:\n\n";
    printItemSet(out, library->books());

    // print items for keyword
    cout << ">>> items for keyword \"Keyword one\"\n\n";
    printItemSet(out, library->itemsForKeyword("Keyword one"));

    // items for artist
    cout << ">>> books by Author:\n\n";
    printItemSet(cout, library->booksByAuthor("Author"));

	delete library;

// in Visual Studio, reports on memory leaks in the Output window
#ifdef _WIN32
	_CrtDumpMemoryLeaks();
#endif
}

Item.h:

#pragma once

#include <ostream>
#include <set>
#include <string>

using namespace std;

typedef set<string>	StringSet;

class Item
{
protected:
	string title;
	string artist;
	StringSet* keywords;

public:
	Item(const string& title, const string& artist);
	virtual ~Item();
	void addKeyword(const string& keyword) const;
	const string* getTitle() const;
	const string* getArtist() const;
	const StringSet* getKeywords() const;
	string printKeywords(const StringSet* keywords) const;
	virtual void print(ostream& out) const;
};

ostream& operator<<(ostream& out, const Item* const item);

Item.cpp:

#include "Item.h"

Item::Item(const string& title, const string& artist)
:title(title),artist(artist),keywords(new StringSet)
{
}

Item::~Item()
{
	delete keywords;
}

void Item::addKeyword(const string& keyword) const
{
	keywords->insert(keyword);
}

const string* Item::getTitle() const
{
	return &title;
}

const string* Item::getArtist() const
{
	return &artist;
}

const StringSet* Item::getKeywords() const
{
	return keywords;
}

string Item::printKeywords(const StringSet* keywords) const
{
	string kwString;
	StringSet::const_iterator itr;

	for(itr = keywords->begin();itr != keywords->end();itr++)
		kwString.append(*itr + ", ");
	kwString.erase(kwString.end() - 2, kwString.end());
	return kwString;
}

void Item::print(ostream& out) const
{
	out << "Should not be printing this!" << endl;
}

ostream& operator<<(ostream& out, const Item* item)
{
	item->print(out);
	return out;
}

Book.h:

#include "Item.h"

using namespace std;

class Book : public Item
{
public:
	Book(const string& title, const string& artist, const int nPages);
	~Book();
	const int getnPages() const;
	virtual void print(ostream& out) const;

private:
	int numPages;
};

ostream& operator<<(ostream& out, const Book* book);

Book.cpp:

#include "Book.h"

Book::Book(const string& title, const string& artist, const int nPages)
:Item(title, artist), numPages(nPages)
{
}

Book::~Book()
{
}

const int Book::getnPages() const
{
	return numPages;
}

void Book::print(ostream& out) const
{
	out << "-Book-" << endl;
	out << "author:    " << *this->getArtist() << endl;
	out << "pages:     " << this->getnPages() << endl;
	out << "title:     " << *this->getTitle() << endl;
	out << "keywords:  " << this->printKeywords(this->getKeywords()) << endl;
	out << endl;
}

ostream& operator<<(ostream& out, const Book* book)
{
	book->print(out);
	return out;
}

Library.h:

#pragma once

#include <ostream>
#include <set>
#include <string>
#include <typeinfo>
#include "Item.h"
#include "Book.h"

using namespace std;

typedef set<Item*>				ItemSet;

class Library
{

public:
	// Constructor
	Library();

	// Destructor
	~Library();

	// general functions
	
	void addKeywordForItem(const Item* const item, const string& keyword);
	const ItemSet* itemsForKeyword(const string& keyword) const;
	void printItem(ostream& out, const Item* const item) const;
	
	// book-related functions
	
	const Item* addBook(const string& title, const string& author, int const nPages);
	const ItemSet* booksByAuthor(const string& author) const;
	const ItemSet* books() const;
	
private:
	ItemSet* lib;
	ItemSet* temp;
};


Library.cpp
:

#include "Library.h"

Library::Library()
:lib(new ItemSet), temp(new ItemSet)
{
}

Library::~Library()
{
	for(ItemSet::iterator itr = lib->begin();itr != lib->end();itr++)
		delete *itr;
	delete lib;
	delete temp;
}

// general functions

void Library::addKeywordForItem(const Item* const item, const string& keyword)
{
	item->addKeyword(keyword);
}

const ItemSet* Library::itemsForKeyword(const string& keyword) const
{
	StringSet* kw;

	temp->clear();
	for(ItemSet::iterator itr = lib->begin();itr != lib->end();itr++)
	{
		kw = const_cast<StringSet*>((*itr)->getKeywords());
		if((kw->find(keyword)) != kw->end())
			temp->insert(*itr);
	}
	return temp;
}

void Library::printItem(ostream& out, const Item* const item) const
{
	out << item;
}

// book-related functions

const Item* Library::addBook(const string& title, const string& author, const int nPages)
{
	Item* book = new Book(title, author, nPages);
	lib->insert(book);
	return book;
}

const ItemSet* Library::booksByAuthor(const string& author) const
{
	string book = "class Book";

	temp->clear();
	for(ItemSet::iterator itr = lib->begin();itr != lib->end();itr++)
	{
		if(book.compare(typeid(*(*itr)).name()) == 0)
		{
			if(author.compare(*(*itr)->getArtist()) == 0)
				temp->insert(*itr);
		}
	}
	return temp;
}

const ItemSet* Library::books() const
{
	string book = "class Book";

	temp->clear();
	for(ItemSet::iterator itr = lib->begin();itr != lib->end();itr++)
	{
		if(book.compare(typeid(*(*itr)).name()) == 0)
			temp->insert(*itr);
	}
	return temp;
}

> {146} normal block at 0x003363A0, 8 bytes long.
> Data: < c3 > E8 63 33 00 00 00 00 00
If this number is anything like consistent (it should be in such a small program), then you can do one of two things.

1. Right at the start of main, do this _CrtSetBreakAlloc( 146 ); 2. In the debugger, open a watch window, then examine the symbol _crtBreakAlloc .
Set that value to 146

Then run the code.
When that block is about to be allocated, you'll drop into the debugger. From there, you can step through the code to work out why you don't free that particular block.

Work your way through the list, starting with the low numbered blocks first.
- they're the ones most likely to have consistent numbers
- if they are containers, then freeing those will probably fix a lot of later allocations as well.

Data: <class Book > 63 6C 61 73 73 20 42 6F 6F 6B 00

Based on that, I'd figure the leak occurs in e.g.

if(book.compare(typeid(*(*itr)).name()) == 0)

But anyhow, do as Salem suggested, so you'll be learning debugging techniques ...

Both blocks (146 and 147) refer to the following line:

const ItemSet* Library::books() const
{
	string book = "class Book";

	temp->clear();
	for(ItemSet::iterator itr = lib->begin();itr != lib->end();itr++)
	{
		if(book.compare(typeid(*(*itr)).name()) == 0)  //This line!
			temp->insert(*itr);
	}
	return temp;
}

As far as I can tell, that line does not allocate anything, nor does it change the addresses of any pointers. I don't see how it can contribute to the leak, yet if I comment out the lines in the driver routine that call this method, the memory leak disappears.

Both blocks (146 and 147) refer to the following line:

if(book.compare(typeid(*(*itr)).name()) == 0)  //This line!

I don't see how it can contribute to the leak.

Well you don't know what takes place behind the scenes, i.e. how the compiler actually manages typeid(*(*itr)).name() .

Well you don't know what takes place behind the scenes, i.e. how the compiler actually manages typeid(*(*itr)).name() .

I did some digging but about all I could do at this point was remove the call to typeid. That has confirmed that typeid is the sole cause of my memory leak. At this point, I can either "properly" use typeid or find an alternative. I'm really stumped either way. I also rewrote the method to make it a bit clearer.

const ItemSet* Library::books() const
{
	string book = "class Book";
	Item* item;

	temp->clear();
	for(ItemSet::iterator itr = lib->begin();itr != lib->end();itr++)
	{
		item = *itr;
		if(book.compare(typeid(*item).name()) == 0)
			temp->insert(item);
	}
	return temp;
}

I have implemented copy constructors now for both Item and Book. Unfortunately, neither seems to ever get called during runtime.

Item::Item(Item const& copy)
:title(copy.title),artist(copy.artist),keywords(new StringSet)
{
	keywords = copy.keywords;
}
//Book inherits from Item
Book::Book(Book const& copy)
:Item(copy.title, copy.artist), numPages(copy.numPages)
{
}

A copy constructor of Book/Item probably won't help here, because it is leaking a std::string, so maybe you could devise and use an arbitrary 'type id' construct for the classes you use. I.e. toss away usage of RTTI altogether.

Thank you everyone for your assistance. I have prevailed.

I added a virtual isType() method to Item, so that any derived class can report their own ID when called. I still don't know why typeid() has failed me, but for now I'll live with it!

This assignment was basically a follow up of an earlier one using Java. After cruising through the Java version, the C++ implementation hit me like a ton of bricks, some of which is detailed here.

I guess I'm a masochist - it wasn't all bad now that it's working!

This is a bug that has been reported to Microsoft since visual C++ 4, and has not been fixed yet. Microsoft says it is fixed in VS 2011. We'll see.

This question has already been answered. Start a new discussion instead.