Invalid heap error when trying to copy elements from a Map to a compatible priority Queue

Question

My program makes a frequency map of characters (which I store in , surprise surprise, a Map), I am trying to copy each element from this map into a Priority Queue so that I can have a sorted copy of these values (I plan to make further use of the Q, that's why am not sorting the map) , but whenever I try to copy these values , the program executes fine for the first two or three iterations and fails on the fourth citing an "Invalid heap" error.

I'm not sure how to proceed from here, so I am posting the code for the classes in question.

#include "srcFile.h"
#include <string>
#include <iostream>

srcFile::srcFile(std::string s_flName)
{
    // Storing the file name
    s_fileName= s_flName;
}

srcFile::srcFile()
{
    // Default constructor (never to be used)
}

srcFile::~srcFile(void)
{
}

void srcFile::dispOverallMap ()
{
    std::map<char,int>::iterator dispIterator;
dispIterator = map_charFreqDistribution.begin();
charElement *currentChar;

std::cout<<"\n Frequency distribution map \n";
while(dispIterator != map_charFreqDistribution.end())
{
    std::cout<< "Character : " << (int)dispIterator->first << " Frequency : "<< dispIterator->second<<'\n';
    currentChar = new charElement(dispIterator->first,dispIterator->second);

    Q_freqDistribution.push(*currentChar);
    dispIterator++;

    // delete currentChar;
}

while(!Q_freqDistribution.empty())
{
    std::cout<<'\n'<<"Queue Element : " << (int)Q_freqDistribution.top().ch_elementChar << " Frequency : " << Q_freqDistribution.top().i_frequency;
    Q_freqDistribution.pop();
}
}

map_charFreqDistribution has already been populated, if I remove the line
Q_freqDistribution.push(*currentChar);
Then I can verify that the Map is indeed there.

Also , both the Q and the use charElement as the template type , its nothing except the character and its frequency, along with 2 pointers to facilitate tree generation (unused upto this point)

Adding the definition of charElement on request

#pragma once
class charElement
{
public:
    // Holds the character for the element in question
char ch_elementChar;

// Holds the number of times the character appeared in the file
int i_frequency;

// Left pointer for tree
charElement* ptr_left;
// Right pointer for tree
charElement* ptr_right;

charElement(char,int);
charElement(void);
~charElement(void);
void operator=(charElement&);
};

class compareCharElt
{
public:
bool operator()(charElement &operand1,charElement &operand2)
{
    // If the frequency of op1 < op2 then return true
    if(operand1.i_frequency < operand2.i_frequency) return true;

    // If the frequency of op1 > op2 then return false
    if(operand1.i_frequency > operand2.i_frequency)return false;

    // If the frequency of op1 == op2 then return true (that is priority is indicated to be less even though frequencies are equal)
    if(operand1.i_frequency == operand2.i_frequency)return false;
}
};

Definition of Map and Queue

// The map which holds the frequency distribution of all characters in the file
    std::map<char,int> map_charFreqDistribution;
    void dispOverallMap();

// Create Q which holds character elements
std::priority_queue<charElement,std::vector<charElement>,compareCharElt>                 Q_freqDistribution;

P.S.This may be a noob question, but Is there an easier way to post blocks of code , putting 4 spaces in front of huge code chunks doesn't seem all that efficient to me! Are pastebin links acceptable here ?

How are types `charElement` and `Q_freqDistribution` defined? Creating a new `currentChar`, then passing in the object itself and not its pointer, and finally deleting the `currentChar` looks like a suspicious sequence. — Eran, Oct 16 '11 at 13:02
If you never intend to use your default constructor, you don't have to define one. Just use the explicit constructor. — jwfriese, Oct 16 '11 at 13:19
@eran I added the definitions to the main question. The new -> add -> delete thing seems to be JAVA hangover (the language I use at work) but essentially I need a new object to be created each iteration and added to the Queue. (Had a brainwave while typing this , should I not delete the variable as it is being held as a reference in the Queue) — angryInsomniac, Oct 16 '11 at 13:31
@JaredFriese Thanks for the tip, this is a rough code draft, that method was added as a stub when the code was in an earlier draft, the comment was to remind me to remove it once I am done. — angryInsomniac, Oct 16 '11 at 13:31
made the change where I no longer delete the object after pushing (I wasn't doing this in earlier drafts of the code either) , it still gives me the same error. — angryInsomniac, Oct 16 '11 at 13:39
Are you doing anything with `ptr_left` and `ptr_right` without initializing them? What is the exact line of the error? — Eran, Oct 16 '11 at 13:48
no , I haven't touched those two yet, the part which uses those two comes much later in the code. The error occurs here : Q_freqDistribution.push(*currentChar); — angryInsomniac, Oct 16 '11 at 13:58
Have you noticed that there's a button to indent a whole block of text by four spaces? — sbi, Oct 16 '11 at 14:12
Why did you post so much code in the first place? Are you sure that `srcFile::~srcFile()` is really necessary? And what's with [passing strings per copy](http://stackoverflow.com/questions/2139224/) and not using [initialization lists](http://stackoverflow.com/questions/1711990/)? You might need [a good C++ book](http://stackoverflow.com/questions/388242/). — sbi, Oct 16 '11 at 14:15
@sbi I had not posted so much code , Just the first class . The rest I added on request. The destructor is an ide generated stub , I am just more concerned with getting stuff working at this point , will trim it down when required. I will look into the "passing strings per copy" issue thanks. — angryInsomniac, Oct 16 '11 at 14:33
@angryInsomniac: I had asked this before I had even seen you had added the second class. Usually, when asking a question, you want a small (<20 lines), self-containing, compiling (unless that's the problem, of course), repro case, no classes unless necessary and no other unnecessary code either. Creating and copying maps and deques is certainly easily done in a single function (preferably in `main()`), nothing else is needed. Also, in 75% of all cases, by boiling down the code to such a small repro you will find the error yourself. — sbi, Oct 16 '11 at 15:16

score 0 · Answer 1 · answered Oct 16 '11 at 13:34

currentChar = new charElement(dispIterator->first,dispIterator->second);

Q_freqDistribution.push(*currentChar);
dispIterator++;

delete currentChar;

In the above code, you create a new charElement object, then push it, and then delete it. When you call delete, that object no longer exists -- not even in the queue. That's probably not what you want.

Puppy · Accepted Answer · 2011-10-16T14:15:00.937

Your vector is reallocating and invalidating your pointers. You need to use a different data structure, or an index into the vector, instead of a raw pointer. When you insert elements into a vector, then pointers to the contents become invalid.

while(dispIterator != map_charFreqDistribution.end())
{
    std::cout<< "Character : " << (int)dispIterator->first << " Frequency : "<< dispIterator->second<<'\n';
    currentChar = new charElement(dispIterator->first,dispIterator->second);

    Q_freqDistribution.push(*currentChar);
    dispIterator++;

    delete currentChar;
}

Completely throws people off because it's very traditional for people to have huge problems when using new and delete directly, but there's actually no need for it whatsoever in this code, and everything is actually done by value.

You have two choices. Pick a structure (e.g. std::list) that does not invalidate pointers, or, allocate all charElements on the heap directly and use something like shared_ptr that cleans up for you.

Invalid heap error when trying to copy elements from a Map to a compatible priority Queue

2 Answers2