Please find below my code. I need an array of lists which are of type
Info. My problem is that I;m not quite sure if I should use an pointer
to a list ( see private member variable of class HashTable) or not. And
if i must use pointers, how should i modify my code? Thanks!
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;
template <class Type>
struct Info
{
Info(const string& k, const Type& myData)
{
key = k;
data = myData;
occupied=false;
hasBeenOccupied = false;
}
const string& getKey() const
{ return key; }
// Overloaded operators
bool operator==(cons t Info& rhs) const
{ return getKey() == rhs.getKey(); }
bool operator!=(cons t Info& rhs) const
{ return !(*this == rhs); }
string key;
Type data;
bool occupied;
bool hasBeenOccupied ;
};
template <class Info>
class HashTable
{
public:
// constructor and destructor
HashTable(int currentSize);
~HashTable();
// other functions
bool put(const Info& x); // enter data into table
void remove(const Info& x); // delete from table
bool isIn(const Info& x) const; // is key in table
bool isEmpty() const; // is table empty
int getTableSize() { return tableSize; }
// hash functions
int myhash(const Info& x, int tableSize) const;
private:
vector<std::lis t <Info> > myLists; // the array of lists
int tableSize;
int numberInTable; // number of items in table
};
// Class Implementation
template <class Info>
HashTable<Info> ::HashTable(int currentSize)
{
numberInTable = 0;
tableSize = currentSize;
// myLists = new vector<std::lis t<Info> > [currentSize];
for (int i = 0; i < tableSize; i++)
{
myLists[i].clear();
}
}
template <class Info>
HashTable<Info> ::~HashTable()
{}
// global main hash function
int hash(const string& key, int tableSize)
{
int index = 0;
for (int j = 0; j < key.length(); j++)
{
index += key[j];
}
return index % tableSize;
}
// my hash function takes an Info object as argument
template <class Info>
int HashTable<Info> ::myhash(const Info& x, int tableSize) const
{
int index = hash(x.key, tableSize);
index %= myLists.size();
if (index < 0)
{
index += myLists.size();
}
return index;
}
// insert data into hash table
template <class Info>
bool HashTable<Info> ::put(const Info& x)
{
int index = myhash(x, tableSize);
list<Info> & thelist = myLists[index];
if( find(thelist.be gin(), thelist.end(), x) != thelist.end() )
{
return false;
}
thelist.push_ba ck(x);
return true;
}
