Problem with priority_queue - Writing memory after heap

Question

Hello again,

I am trying to use priority_queue, and program constantly fails with error message HEAP CORRUPTION DETECTED.

here are the snippets:

class CQueue { ...
              priority_queue<Message, deque<Message>, less<deque<Message>::value_type> > m_messages;
...};

class Message has overloaded operators > and <

Here I fill up queue:

CQueue & operator+=(Message &rhv)
{
 m_messages.push(rhv);  //This is where program fails
 return *this;
}

and in the main program:

string str;
CQueue pq;
for(int i = 0; i < 12; ++i)
{
 cin >> str;

 Message p(str.c_str(), rand()%12); //Create message with random priority
 pq += p;                           //add it to queue
}

I have no idea what seems to be the problem. It happens when I push about 8 items, and it fails on line

    push_heap(c.begin(), c.end(), comp);

in < queue >

:(

Here is the definition of message class - it's very simple:

#pragma once 

#include <iostream>
#include <cstring>
#include <utility>

using namespace std;

 class Poruka
{
private:
char *m_tekst;
int  m_prioritet;
public:
Poruka():m_tekst(NULL), m_prioritet(-1){}

Poruka(const char* tekst, const int prioritet)
{
 if(NULL != tekst)
 {
 // try{
   m_tekst = new char[strlen(tekst) + 1];
  //}
  //catch(bad_alloc&)
 // {
 //  throw;
 // }


  strcpy(m_tekst, tekst);
 }
 else
 { 
 // try
 // {
   m_tekst = new char[1];
 // }
 // catch(bad_alloc&)
 // {
 //  throw;
 // }

  m_tekst[0] = '\0';
 }
 m_prioritet = prioritet;
}

Poruka(const Poruka &p)
{
 if(p.m_tekst != NULL)
 {
  //try
  //{
   m_tekst = new char[strlen(p.m_tekst) + 1];
  //}
  //catch(bad_alloc&)
  //{
  // throw;
  //}

  strcpy(m_tekst, p.m_tekst);
 }
 else
 {
  m_tekst = NULL;
 }
 m_prioritet = p.m_prioritet;
}

~Poruka()
{
  delete [] m_tekst;
}

Poruka& operator=(const Poruka& rhv)
{
 if(&rhv != this)
 {
  if(m_tekst != NULL)
   delete [] m_tekst;

 // try
  //{
   m_tekst = new char[strlen(rhv.m_tekst + 1)];
  //}
  //catch(bad_alloc&)
  //{
  // throw;
  //}

  strcpy(m_tekst, rhv.m_tekst);
  m_prioritet = rhv.m_prioritet;
 }
 return *this;
}

friend ostream& operator<<(ostream& it, const Poruka &p)
{
 it << '[' << p.m_tekst << ']' << p.m_prioritet;
 return it;
}

//Relacioni operatori

friend inline bool operator<(const Poruka& p1, const Poruka& p2)
{
 return p1.m_prioritet < p2.m_prioritet;
}

friend inline bool operator>(const Poruka& p1, const Poruka& p2)
{
 return p2 < p1;
}

friend inline bool operator>=(const Poruka& p1, const Poruka& p2)
{
 return !(p1 < p2);
}

friend inline bool operator<=(const Poruka& p1, const Poruka& p2)
{
 return !(p1 > p2);
}

friend inline bool operator==(const Poruka& p1, const Poruka& p2)
{
 return (!(p1 < p2) && !(p2 < p1));
}

friend inline bool operator!=(const Poruka& p1, const Poruka& p2)
{
 return (p1 < p2) || (p2 < p1);
}

};

Poruka - Message

Answer 1

I think the problem is that your Message objects are keeping pointers to raw C strings which are then getting deallocated. In these lines:

cin >> str;

Message p(str.c_str(), rand()%12);

On each iteration of the loop, you're reading in a new value to str, which invalidates any old pointers returned by its c_str() method, so your older messages are pointing to invalid data. You should change your Message object so that it stores its string as an std::string instead of a char*. This will properly copy the string into the Message object.

Alternatively, if you can't change the Message class, you'll have to explicitly copy the string yourself, e.g. using strdup() or malloc()/new[]+strcpy(), and then you have to remember to deallocate the string copies at some later point.

Answer 2

I can't get it to fail.
But there is not enough info to compile this line:

push_heap(c.begin(), c.end(), comp);

But the only problems I see are:

1) You have a default constructor that could create a Poruka with a NULL name:

Poruka::Poruka():m_tekst(NULL), m_prioritet(-1){}

2) Not a problem because you test for it most places but in the assignment operator you miss a test:

Poruka::Poruka& operator=(const Poruka& rhv)
{
 ....
    // There was no test for 'rhv.m_tekst' being NULL here.
    //
    m_tekst = new char[strlen(rhv.m_tekst + 1)];
    strcpy(m_tekst, rhv.m_tekst);

Notes:

• You could make your code much simpler by using the std::string class.
• If you still want to use char* then if you gurantee it is never NULL then the code is simpler
• Also there is a simpler patter for defining the standard copy constructor and assignment operator. It is refered to as the copy/swap idium.
• You dont need to define all those relational operators. There is a set of template ones that work automatically in see http://www.sgi.com/tech/stl/operators.html. You just need to define operator< and operator==

Here is an example of the copy/swap idium

class X
{
     X(X const& copy)
     {
          // Do the work of copying the object
          m_tekst     = new char[strlen(copy.m_tekst) + 1];
          ...
          m_prioritet = copy.m_prioritet;
     }
     X& operator=(X const& copy)
     {
         // I like the explicit copy as it is easier to read
         // than the implicit copy used by some people (not mentioning names litb)
         //
         X  tmp(copy);  // Use the copy constructor to do the work

         swap(tmp);
     }
     void swap(X& rhs) throws ()
     {
         std::swap(this->m_tekst,   rhs.m_tekst);
         std::swap(this->prioritet, rhs.prioritet);
     }