0

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);
}
  • 1
    0xDDDDDDDD is a magic debugging code marking freed heap memory. Related: [https://stackoverflow.com/questions/127386/in-visual-studio-c-what-are-the-memory-allocation-representations](https://stackoverflow.com/questions/127386/in-visual-studio-c-what-are-the-memory-allocation-representations) – drescherjm Nov 17 '20 at 03:35
  • 1
    There's both too much code here to review, and not enough code here to reproduce the problem. – tadman Nov 17 '20 at 03:36
  • Did run your code in a **debugger** to see where that error occurs, then run it again with a breakpoint near that failure so you can step carefully ahead and watch what happens leading up to that point? – tadman Nov 17 '20 at 03:37
  • First, I think you're using one more level of indirection than you actually need. Second, I think you're using *two* more levels of indirection than you actually need. a `std::vector>` would, in theory, provide all you need for a reasonable hash table. Second, your hash function *result* should be taken modulo your bucket count to ensure no breach. Since your "prof" said not to touch it, and you've chosen not to *show* it, we are left to assume it returns a result in-range of your bucket sequence, which is a far leap indeed. – WhozCraig Nov 17 '20 at 03:38
  • 1
    @tadman Specifically, the code where I get the error is operator=, at the very end of the debug. It reaches the end of the function, and then it gives me the error. I included more code in case I made a mistake somewhere else, but that's where the error comes from. – MoisesYacila Nov 17 '20 at 03:41
  • @WhozCraig that part was given by our professor, sorry that I didn't mention it – MoisesYacila Nov 17 '20 at 03:42
  • You did mention it; you just didn't *show it* (e.g. the hash function implementation). Further, if `operator *` is not supposed to modify either the current object or the passed argument, *both* should be const. I.e. the operator should be `template SetT SetT::operator*(SetT const & other) const` , and declared accordingly in the class def. Better safe than sorry. – WhozCraig Nov 17 '20 at 03:43
  • I think one or more of your pointers were already freed. At least that is what the 0xDDDDDDE1 address tells me. – drescherjm Nov 17 '20 at 03:45
  • @WhozCraig I included it. Sorry I didn't include it before, I didn't think that's where the error was coming from. Thanks for your help – MoisesYacila Nov 17 '20 at 03:48
  • @drescherjm I only have a delete statement in the destructor. Could that be causing the error? – MoisesYacila Nov 17 '20 at 03:50
  • 3
    If your Set is not [RO3 compliant](https://en.cppreference.com/w/cpp/language/rule_of_three), yeah, that can be a huge problem. – WhozCraig Nov 17 '20 at 03:56
  • @WhozCraig I didn't know that. Thanks, hopefully that'll fix the problem – MoisesYacila Nov 17 '20 at 04:01
  • This certainly could be caused by violating the rule of 3 / 5 /0 – drescherjm Nov 17 '20 at 04:09
  • Fyi, your professor's hash function is both overt and completely wrong. It will not work for anything besides integral `T` types, and even there unintended conversions can/will happen Constructing an `unordered_map` (without `std` namespace resolution, oh my) with an `int` key type, then using the unordered map's `hasher` type and `hash_function` exposure means effectively your "hash" function is simply `std:hash::operator()` . In short, that function is worthless unless `T` is `int` or convertible to `int`. Try using `Set` and see what happens. – WhozCraig Nov 17 '20 at 14:49
  • @WhozCraig Ok, so I realized that the problem is that when I return result in operator*, result gets immediately destroyed due to it being a local variable, and then by the time the operator= tries to access it. It can't because the memory has been freed. Do you know how I could possibly access the data for operator= before it gets destroyed? – MoisesYacila Nov 17 '20 at 18:48
  • You need a proper RO3 compliance. Your `Set` destroys its guts on the way out, that's one of the three legs of the stool; and if you need one, you pretty much *always* need them *all*. I.e. you need a proper copy-ctor and a proper copy-assignment operator. Or.... [perhaps this](https://ideone.com/ESnxLU). – WhozCraig Nov 17 '20 at 19:36
  • @WhozCraig Thanks Craig – MoisesYacila Nov 17 '20 at 19:44

0 Answers0