C++ Heap Corruption in Template array

Question

As the title already says, I have a problem with a heap corruption in my C++ code. I know there are a lot of topics that cover heap corruption problems, and I have visited a lot of them, I read up on a lot of sites about these matters and I've even used Visual Leak Detector to find the location of the memory leak. I still can't seem to figure out why I have a heap corruption.

My code:

#include <iostream>
#include "stdafx.h"
#include "cstdlib"
#include <vld.h>
#include <math.h>

using namespace std;

template <class T>
class PrioQueue
{
private:
    int size_;
    int tempIndex;
public:
    T *bottom_;
    T *top_;
    PrioQueue(int n =20){
        size_ = n;
        bottom_ = new T[size_];
        top_ = bottom_;
    }
    void push(T c){
        //add the item to the list
        *top_ = c;
        top_++;

        //Save the old stack values in the temp memory
        T* values = bottom_;
        T tempItem;
        int index = num_items();
        cout << "Num items: " << index << endl;
        cout << "1" << endl;
        while(index > 1){
            cout << "2" << endl;
            if(values[index-1] > values[index-2])
            {
                cout << "2b" << endl;
                tempItem = values[index-2];
                values[index-2] = c;
                values[index-1] = tempItem;

            }
            cout << "3" << endl;
            index--;
        }
        cout << "4" << endl;

    }

    // + operator 
    PrioQueue* operator+ (PrioQueue que2)
    {
        PrioQueue<T>* temp = new PrioQueue<T>();
        cout << "Created temporary queue" << endl;
        for(int i = 0; i <num_items(); i++)
        {
            cout << "Element in list: " << bottom_[i] << endl;
            temp->push(bottom_[i]);
            cout << "Temp is now: ";
            temp->print();
        }
        for(int i = 0; i < que2.num_items(); i++)
        {
            cout << "Element in list: " << que2.bottom_[i] << endl;
            temp->push(que2.bottom_[i]);
            cout << "Temp is now: ";
            temp->print();
        }
        cout << "Ran loop" << endl;
        return temp;
    }

    // * operator 
    PrioQueue* operator* (PrioQueue que2)
    {
        PrioQueue<T>* temp = new PrioQueue<T>(); 
        for(int i = 0; i < num_items(); i++)
        {
            for(int j = 0; j < que2.num_items(); j++)
            {
                if(bottom_[i] == que2.bottom_[j])
                {
                    temp->push(bottom_[i]);
                    break;
                }
            }
        }

        return temp;
    }

    friend ostream& operator<< (ostream& output, PrioQueue& q) {
        for(T *element = q.bottom_; element < q.top_; element++)
            output << *element << " | ";
        return output;
    }

    int num_items() {
        return (top_ - bottom_ );
    }
    T pop(){
        top_--;
        return *top_;
    }
    int full() {
        return (num_items() >= size_);
    }
    int empty() {
        return (num_items() <= 0);
    }
    void print(){
        cout << "Print function..." << endl;
        cout << "Stack currently holds " << num_items() << " items: " ;
        for (T *element=bottom_; element<top_; element++) {
            cout << " " << *element;
        }
        cout << "\n";
    }
    ~PrioQueue(){ // stacks when exiting functions
        delete [] bottom_;
    }
};

int main()
{
    PrioQueue<int> *p1 = new PrioQueue<int>(20);
    p1->push(5);
    p1->push(2);
    p1->push(8);
    p1->push(4);
    p1->print(); cout << "\n";

    PrioQueue<int> *p2 = new PrioQueue<int>(5);
    p2->push(33);
    p2->push(66);
    p2->push(8);
    p2->push(5);
    p2->print(); cout << "\n";

    //add them together

    p1->print();
    p2->print();

    ((*p1) + (*p2))->print();
    ((*p1) * (*p2))->print();


    PrioQueue<float> *f1 = new PrioQueue<float>(5);
    f1->push(1.1f);
    f1->push(5.2f);
    f1->push(8.3f);
    f1->push(14.4f);
    f1->push(17.5f);
    f1->print(); cout << "\n";

    PrioQueue<float> *f2 = new PrioQueue<float>(4);
    f2->push(2.2f);
    f2->push(6.7f);
    f2->push(10.3f);
    f2->push(15.6f);
    f2->print(); 
    cout << "\n";

    //add them together
    ((*f1) + (*f2))->print();

    // Multiply them.
    ((*f1) * (*f2))->print();

    cout << "\n";
    cout << p1 << endl;
    cout << f1 << endl;

    cout << "Press any key to exit...";
    cin.get();
    cin.get();

    delete p1;
    delete p2;
    delete f1;
    delete f2;
    return 0;
}

I already tried removing everything and start at the beginning. It seemed that changing:

    delete [] bottom_;

To:

    delete bottom_;

Fixed it, but that was before I pushed a value to the array.

Could some of you please enlighten me on what is wrong. It would be very much appreciated.

Thank you in advance,

Greatings Matti Groot.

Answer 1

1. Stop using new everywhere.

If you want a new Object to work with, create one on the stack.

PrioQueue *p1 = new PrioQueue(20); // NO! PrioQueue q1(20); // YES!

2. Consider to use unsigned values where usigned values are appropriate.

3. In your operator+() you'll have to set the size of the new temporary Queue appropriately.

4. See Blastfurnace's answer regarding resource managment and operator design.

5. Try to find out what resource acquisition is initialization (RAII) is and use this knowledge.

I addressed some of your issues

template <class T>
class PrioQueue
{
private:
  size_t size_;
  T *bottom_;
  T *top_;
public:
  PrioQueue (void)
    : size_(20U), bottom_(new T[20U]), top_(bottom_)
  {
  }

  PrioQueue(size_t n) 
    : size_(n), bottom_(new T[n]), top_(bottom_)
  {
  }

  PrioQueue(PrioQueue<T> const & rhs) 
    : size_(rhs.size_), bottom_(new T[rhs.size_]), top_(bottom_)
  {
    for (size_t i=0; i<size_; ++i)
    {
      bottom_[i] = rhs.bottom_[i];
    }
  }

  PrioQueue<T> & operator= (PrioQueue<T> rhs)
  {
    swap(rhs);
  }

  void push (T c)
  {

    // check if its full
    if (full()) throw std::logic_error("full");

    //add the item to the list
    *top_ = c;
    top_++;

    // there is no point operating on a new pointer named "values" here
    // your still addressing the same memory, so you can just operate on bottom_ instead
    for (size_t index = num_items()-1; index > 0; --index)
    {
      if(bottom_[index] > bottom_[index-1])
      {
        std::swap(bottom_[index], bottom_[index-1]);
      }
    }
  }

  // + operator 
  PrioQueue<T> operator+ (PrioQueue<T> const & que2)
  {
    // you need a temporary queue that is large enough 
    // so give it the proper size (sum of both sizes)
    PrioQueue<T> temp(num_items() + que2.num_items());
    std::cout << "Created temporary queue" << std::endl;
    for(size_t i = 0; i <num_items(); i++)
    {
        std::cout << "Element in list: " << bottom_[i] << std::endl;
        temp.push(bottom_[i]);
        std::cout << "Temp is now: ";
        temp.print();
    }
    for(size_t i = 0; i < que2.num_items(); i++)
    {
        std::cout << "Element in list: " << que2.bottom_[i] << std::endl;
        temp.push(que2.bottom_[i]);
        std::cout << "Temp is now: ";
        temp.print();
    }
    std::cout << "Ran loop" << std::endl;
    return temp;
  }

  // * operator 
  PrioQueue<T> operator* (PrioQueue<T> const & que2)
  {
    size_t que1_items = num_items(), que2_items = que2.num_items();
    PrioQueue<T> temp(que1_items);
    for (size_t i = 0U; i < que1_items; ++i)
    {
      for(size_t j = 0U; j < que2_items; ++j)
      {
        if(bottom_[i] == que2.bottom_[j])
        {
          temp.push(bottom_[i]);
        }
      }
    }
    return temp;
  }

  friend std::ostream& operator<< (std::ostream& output, PrioQueue<T> & q) 
  {
      for(T *element = q.bottom_; element < q.top_; element++)
          output << *element << " | ";
      return output;
  }

  size_t num_items(void) const
  {
      return size_t(top_ - bottom_ );
  }

  T pop (void)
  {
    // you actually popped of the last element and returned the next
    // i think it is likely you want to return the element you pop off
    return *(top_--);
  }

  // why int? full or not is a rather boolean thing i guess
  bool full (void) const
  {
    // num_items() > size_ must not happen!
    return (num_items() == size_);
  }

  bool empty(void) const
  {
    // an unsigned type cannot be < 0
    return (num_items() == 0);
  }

  void swap (PrioQueue<T> & rhs)
  {
    std::swap(size_, rhs.size_);
    std::swap(bottom_, rhs.bottom_);
    std::swap(top_, rhs.top_);
  }

  void print (void) const
  {
      cout << "Print function..." << endl;
      cout << "Stack currently holds " << num_items() << " items: " ;
      for (T * element=bottom_; element<top_; ++element) 
      {
        cout << " " << *element;
      }
      cout << endl;
  }

  ~PrioQueue()
  {
    delete [] bottom_;
  }

};

int main()
{
  PrioQueue<int> q1;
  q1.push(5);
  q1.push(2);
  q1.push(8);
  q1.push(4);
  q1.print();

  PrioQueue<int> q2;
  q2.push(33);
  q2.push(66);
  q2.push(8);
  q2.push(5);
  q2.print();

  std::cout << "Plus: " << std::endl;
  PrioQueue<int> q_plus = q1+q2;
  q_plus.print();

  std::cout << "Multi: " << std::endl;
  PrioQueue<int> q_multi = q1*q2;
  q_multi.print();
}

Answer 2

The change you mention leads to undefined behavior. If you got something with new[] you must pass it to delete[]. Plain delete is only good for what you got with plain new.

Your operator + and * creates new objects and return pointer to it. I don't see any attempt to delete those objects, so no wonder you have leaks. (It counts as bad design to return pointers-with-obligation for no good reason, even more so from operators on objects that should produce objects.)

Answer 3

1. Your class manages a resource (memory) but you don't correctly handle copying or assignment. Please see: What is The Rule of Three?.

2. The design of your operator+() and operator*() is unusual and leaks memory. Returning PrioQueue* makes it cumbersome or impossible to properly free temporary objects. Please see: Operator overloading

You might be interested in The Definitive C++ Book Guide and List to learn the language basics and some good practices.

Answer 4

I suggest you try re-writing this without using new or delete. Change your * and + operators to return a PrioQueue. Change the PrioQueue to use a vector<T> instead of an array. You can then focus on writing your own priority queue. Make sure you use the standard priority queue if you actually need one though.

Answer 5

((*p1) + (*p2))->print(); 

and statements like these .. Your + & * operator returns a new'ed PrioQueue . So you are not deleting it anywhere .

So try to take return value in a temp PrioQueue pointer and call delete on it as well .