Safe Delete in C++

Question

I have developed an array based implementation of a hashTable with several stock names, symbols, prices, and the like. I need to remove a stock from my array. I am told that using the delete operator is bad object oriented design. What is the good object oriented design for deletion?

bool hash::remove(char const * const symbol, stock &s,
int& symbolHash, int& hashIndex, int& usedIndex)
{
 symbolHash = this->hashStr( symbol ); // hash to try to reduce our search.
         hashIndex = symbolHash % maxSize;
         usedIndex = hashIndex;

 if (     hashTable[hashIndex].symbol != NULL &&
  strcmp( hashTable[hashIndex].symbol , symbol ) == 0 ) 
 {
  delete hashTable[hashIndex].symbol;
  hashTable[hashIndex].symbol = NULL; 
  return true;
 }
 for ( int myInt = 0; myInt < maxSize; myInt++ )
 {
  ++usedIndex %= maxSize;
  if ( hashTable[usedIndex].symbol != NULL &&
    strcmp( hashTable[usedIndex].symbol , symbol ) == 0 )
   {
    delete hashTable[usedIndex].symbol;
    hashTable[usedIndex].symbol = NULL;
    return true; 
  }
 }
 return false;
}

Noticing that i have a stock &s as a paramter, i can use it like this:

s = &hashTable[usedIndex];
delete s.symbol;
s.symbol = NULL;
hashTable[usedIndex] = &s;

This does work however, it results in a memory leaks. Even then, i am not sure if it is good object orinted design.

here is my header, where stock and all that stuff is initialized and defined.

//hash.h

private:
 friend class stock;
 int isAdded; // Will contain the added hash index.
 // Test for empty tables.
 // Can possibly make searches efficient.
 stock *hashTable; // the hashtable will hold all the stocks in an array

};

// hashtable ctor

hash::hash(int capacity) : isAdded(0),
hashTable(new stock[capacity]) // allocate array with a fixed size
{
 if ( capacity < 1 ) exit(-1);

    maxSize = capacity;

 // We can initialize our attributes for the stock
 // to NULL, and test for that when searching.
 for ( int index = 0; index < maxSize; index++ )
 {
  hashTable[index].name = NULL;
  hashTable[index].sharePrice = NULL;
  hashTable[index].symbol = NULL;
 }
}

// stock.h

... friend class hashmap;

private:

 const static int maxSize; // holds the capacity of the hash table minus one
 date  priceDate; // Object for the date class. Holds its attributes.
 char *symbol;
 char *name;
 int   sharePrice;
 };

My question is still just, how do i preform a safe remove?

s = &hashTable[usedIndex];
delete s.symbol;
s.symbol = NULL;
hashTable[usedIndex] = &s;

That seems to work, but results in memory leaks! How is this done safely?

delete hashTable[usedIndex].symbol; hashTable[usedIndex].symbol = NULL; <-- without doing this.

The status of the slot in the array (empty, etc) should not be recorded in the stock instance. That's bad object oriented design. Instead, I need to store the status of an array slot in the array slot itself.

How would i do that?

Answer 1

It looks like you're using (or trying to use) open addressing with linear-probing for collision resolution. In that case, you need to somehow mark items as deleted (as opposed to empty), so that you can still access items which fall after deleted items. Otherwise, you won't be able to lookup certain items because your probing sequence will be terminated prematurely if it finds a deleted bucket. Therefore, you won't be able to access certain items in the table anymore and that's probably why you're getting a memory leak.

Basically, you're supposed to start at the hash index, compare the item with your key, and then if it isn't equal to your key, increment to the next index and repeat until either you find the item, or until you encounter an empty bucket. If you find the item, delete the item and mark that index as deleted. But the important thing is that you have some way to distinguish between an empty hash bucket, and a deleted hash bucket, otherwise a deleted bucket will cause you to terminate your probing sequence early.

As for "good object oriented design", there is no inherent property of object-oriented programming that necessarily makes using delete a bad design. Every data structure that allocates memory has to free it somehow. What you're probably referring to is the fact that it's usually safer and less work to implement classes that don't manage their own memory, but rather delegate that responsibility to pre-made container classes, like std::vector or std::string

Answer 2

To get good object oriented design, a collection should be agnostic of what is stored in it. This really has nothing to do with using the delete operator per se, but requiring an object (your stock in this case) to store data structure specific code is.

There are two plans things I can see to quickly fix this issue.

1. Use an array of stock * instead of just stock. Then a null value will mean the slot is open, and a non-null value will mean the slot can be used. In this plan you would call new and delete on the entire stock object as it is inserted and then as it is removed, which is more object oriented than just the symbol.

2. Create a HashSlot class that wraps the stock item, adding the book keeping values that are needed. Your hash table would then be an array of HashSlot items.

I prefer the second. In either case, stock should have a destructor that clears up its own internal memory.

Answer 3

NOTE: This answer is just addressing some of the things you are doing incorrectly. This is not the best way to do what you are doing. An array of stock** would make more sense.

Doesn't your stock class have a constructor? You don't need to know anything about the stock class if it is a proper object:

hash::hash(int capacity) // change this to unsigned and then you can't have capacity < 0
  : isAdded(0)
  , hashTable(0) // don't call new here with bad parameters
{
   if ( capacity < 1 ) exit(-1); // this should throw something, maybe bad_alloc

   maxSize = capacity;
   hashTable = new stock[capacity]; // this calls the stock() constructor

   // constructor already called. All this code is useless
   // We can initialize our attributes for the stock
   // to NULL, and test for that when searching.
//   for ( int index = 0; index < maxSize; index++ )
//   {
//       hashTable[index].name = NULL;
//      hashTable[index].sharePrice = NULL;
//      hashTable[index].symbol = NULL;
//   }
}

class stock {
    char* name; // these should be std::string as it will save you many headaches
    char* sharePrice; // but I'll do it your way here so you can see how to
    char* symbol;  // avoid memory leaks
public:
    stock() : name(0), sharePrice(0), symbol(0) {}
    ~stock() { delete[] name; delete[] sharePrice; delete[] symbol; }
    setName(const char* n) { name = new char[strlen(n)+1]; strcpy(name, n); }
    setPrice(const char* p) { sharePrice = new char[strlen(p)+1]; strcpy(sharePrice, p); }
    setSymbol(const char* s) { symbol = new char[strlen(s)+1]; strcpy(symbol, n); }

    const char* getName() const { return name; }
    const char* getPrice() const { return sharePrice; }
    const char* getSymbol() const { return symbol; }
}

Answer 4

I have developed an array based implementation of a hashTable with several stock names, symbols, prices, and the like. I need to remove a stock from my array. I am told that using the delete operator is bad object oriented design. What is the good object oriented design for deletion?

Well, one of the key principles behind object oriented design is reusability.

Hence, the only good object oriented design is to reuse the solutions that have already been developed for you!

C++ comes with a perfecetly good map class. Most recent compilers also support TR1, which adds a hash table under the name unordered_map.

The Boost libraries also contain an implementations of unordered_map in case you're stuck on a compiler without TR1 support.

As for your question about delete:
I'm not sure who told you that delete is "bad object-oriented design", or why, but what they might have meant is that it is bad C++ design.

A common guideline is that you should never explicitly call delete. Instead, it should be called implicitly through the use of the RAII idiom.

Whenever you create a resource that must, at some later point, be deleted, you wrap it in a small stack-allocated object, whose destructor calls delete for you.

This guarantees that it gets deleted when the RAII object goes out of scope, regardless of how you leave the scope. Even if an exception is thrown, the object still gets cleaned up, its destructor called, and your resource deleted. If you need more complex ways to manage the object's lifetime, you might want to use smart pointers, or just extend your RAII wrapper with copy constructor and assignment operator to allow ownership of the resource to be copied or moved.

That is good C++ practice, but has nothing to do with object-oriented design. Not everything does. OOP isn't the holy grail of programming, and not everything has to be OOP. Good design is much more important than good OOP.