I am working on a homework assignment where we are supposed to implement a set using a hash based chain implementation.
We are using C++'s forward_list for the buckets.
We have to overload operators + for union, * for intersection, and the assignment operator (=). But every time I run my program, I get this error.
Exception thrown: read access violation.
_Pnext was 0xDDDDDDE1.
This code gives me the error. Specifically the last line
SetT<int> setA;
SetT<int> setB;
SetT<int> setResult;
setA.Add(20);
setB.Add(20);
setResult = setA * setB;
I tried debugging, but it didn't help. It would go through the operator* with no problems, then it would go through the operator=, exit, and then as soon as I got back to main to go to the next line, it would give me the error.
I also looked similar questions, but I wasn't able to find the reason why my program crashes.
These are the private variables for the class SetT
forward_list<T>** buckets; // An array of forward_list's
// (ie, each index is a forward_list pointer)
int numBuckets;
int getHashIndex(const T& elem);
int numElems;
// Iterator variables
int currBucket; // what bucket is the iterator on?
mutable typename forward_list<T>::iterator bucketIter; // the iterator of the current bucket
This is the code for Add:
template<class T>
bool SetT<T>::Add(T elem)
{
// If the set already contains elem, do nothing
if (Contains(elem)) {
return false;
}
// Get the bucket index and add the element to the bucket.
currBucket = getHashIndex(elem);
buckets[currBucket]->push_front(elem);
numElems++;
return true;
// Extra credit: If the load factor becomes too large, change the number of buckets and rehash.
}
The hashing function was given by our professor, and he told us not to touch it.
This is the code for Contains:
template<class T>
bool SetT<T>::Contains(T elem)
{
// Use hash function to find the bucket, then check
// to see if elem is in the bucket.
currBucket = getHashIndex(elem);
for (bucketIter = buckets[currBucket]->begin(); bucketIter != buckets[currBucket]->end(); ++bucketIter) {
if (elem == *bucketIter) {
return true;
}
}
return false;
}
And this is the code for the operators
template<class T>
SetT<T> SetT<T>::operator*(SetT& other)
{
SetT<T> result;
// Your code here
// This function should return the Intersection between "this" and otherSet.
// It should NOT change "this" or otherSet
for (int i = 0; i < numBuckets; i++) {
for (bucketIter = buckets[i]->begin(); bucketIter != buckets[i]->end(); ++bucketIter) {
T value = *bucketIter;
if (Contains(value) && other.Contains(value)) {
result.Add(value);
}
}
}
return result;
}
template<class T>
SetT<T> SetT<T>::operator=(const SetT& other)
{
if (other.numElems == 0) {
return SetT<T>();
}
else {
return other;
}
}
Does anyone know what is causing this error?
Thanks.
Edit: This is the professor's hash function
template<class T>
int SetT<T>::getHashIndex(const T& key)
{
// This is done... No touching!
unordered_map<int, T> mapper;
typename unordered_map<int, T>::hasher hashFunction = mapper.hash_function();
return static_cast<int>(hashFunction(key) % numBuckets);
}