STL question: is this O/T ?

M

Michael

Guys,
I'm trying to compile this code to build a huffman tree, but I'm getting a
runtime error and my degugger ends up somewhere in the STL files. What am i
doing wrong. I appreciate its not effiecient/stylistic, etc, it was just
something i wanted to try
Thanks

Mike





#include <assert.h>
#include <vector>
#include <list>
using std::list;
using std::vector;


class HuffmanNode
{
public:
HuffmanNode* pLeft;
HuffmanNode* pRight;
char Represented;
float frequency;
HuffmanNode() : pLeft(NULL), pRight(NULL), Represented(-1),
frequency(-1) {}
void AddSubTreeToVector(vector<string>& v, string currentString);
};


int main()
{
list<HuffmanNode> nodes;
for(int i=0;i<256;i++)
{
HuffmanNode n;
n.Represented = i;
n.frequency = (i*i *10 )% 300;
nodes.push_back(n);
}
cout << "Populated Source List: " << nodes.size();

while(nodes.size() >1)
{
cout << "\n\tListSize: " << nodes.size();
HuffmanNode newNode;
newNode.pLeft = new HuffmanNode;
newNode.pRight = new HuffmanNode;

list<HuffmanNode>::iterator it;
list<HuffmanNode>::iterator smallest = nodes.begin();

//Find Smallest
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pLeft = *(smallest);
newNode.frequency = smallest->frequency;
nodes.erase(smallest);

//Find the next Snmallest
smallest = nodes.begin();
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pRight = *smallest;
newNode.frequency += smallest->frequency;
nodes.erase(smallest);
//Add the New Node
nodes.push_back(newNode);
}



HuffmanNode hmt = *(nodes.begin());
//Move Tree into vector for encoding:
vector<string> HuffmanCodes;
for(int i=0;i<256;i++)
{
string str;
HuffmanCodes.push_back(str);
}

hmt.AddSubTreeToVector(HuffmanCodes,"");
for(int i=0;i<256;i++)
{
string str = HuffmanCodes;
cout << i << ": " << str.c_str() << endl;
}


system("PAUSE");
}









void HuffmanNode::AddSubTreeToVector(vector<string>& v, string
currentString)
{
assert(this);
if(Represented != -1) v[Represented] = currentString;
//LeftSubTree
if(pLeft)
{
string LeftString;
LeftString = currentString;
LeftString.append("0");
pLeft->AddSubTreeToVector(v,LeftString);
}
//RightSubTree
if(pRight)
{
string RightString;
RightString = currentString;
RightString.append("0");
pRight->AddSubTreeToVector(v,RightString);
}
}
 
K

Karthik

Michael said:
Guys,
I'm trying to compile this code to build a huffman tree, but I'm getting a
runtime error and my degugger ends up somewhere in the STL files. What am i
doing wrong. I appreciate its not effiecient/stylistic, etc, it was just
something i wanted to try
Thanks

Mike
Click to expand...

The code didn't compile in the first place.
#include <assert.h>
#include <vector>
#include <list>
using std::list;
using std::vector;
Click to expand...
#include <string>
#include <iostream>
#include <iterator>
#include <cstdlib>

using std::string;
using std::cout;
using std::endl;
class HuffmanNode
{
public:
HuffmanNode* pLeft;
HuffmanNode* pRight;
char Represented;
float frequency;
HuffmanNode() : pLeft(NULL), pRight(NULL), Represented(-1),
frequency(-1) {}
void AddSubTreeToVector(vector<string>& v, string currentString);
};


int main()
{
list<HuffmanNode> nodes;
for(int i=0;i<256;i++)
Click to expand...
// Go for unsigned int or better, size_t type for indexing into
//the vector.
{
HuffmanNode n;
n.Represented = i;
n.frequency = (i*i *10 )% 300;
nodes.push_back(n);
}
cout << "Populated Source List: " << nodes.size();

while(nodes.size() >1)
{
cout << "\n\tListSize: " << nodes.size();
HuffmanNode newNode;
newNode.pLeft = new HuffmanNode;
newNode.pRight = new HuffmanNode;

list<HuffmanNode>::iterator it;
list<HuffmanNode>::iterator smallest = nodes.begin();

//Find Smallest
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pLeft = *(smallest);
newNode.frequency = smallest->frequency;
nodes.erase(smallest);

//Find the next Snmallest
smallest = nodes.begin();
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pRight = *smallest;
newNode.frequency += smallest->frequency;
nodes.erase(smallest);
//Add the New Node
nodes.push_back(newNode);
}



HuffmanNode hmt = *(nodes.begin());
//Move Tree into vector for encoding:
vector<string> HuffmanCodes;
for(int i=0;i<256;i++)
{
string str;
HuffmanCodes.push_back(str);
}

hmt.AddSubTreeToVector(HuffmanCodes,"");
for(int i=0;i<256;i++)
{
string str = HuffmanCodes;
cout << i << ": " << str.c_str() << endl;
}


system("PAUSE");
Click to expand...

// As far as possible try not to use system command. It is a separate
topic, but many programmers loathe it since it affects readability of
the code.

// Where is the return statement for main function .
}









void HuffmanNode::AddSubTreeToVector(vector<string>& v, string
currentString)
{
assert(this);
if(Represented != -1) v[Represented] = currentString;
Click to expand...

The type of Represented happens to be a 'char' !! Change that to
size_t type. Do not make such dangerous conversions. Then heed your
compiler's warnings after converting the same to unsigned int. That
should help.
 
A

Andre Kostur

// As far as possible try not to use system command. It is a
separate
topic, but many programmers loathe it since it affects readability of
the code.

// Where is the return statement for main function .
Click to expand...

Not required. If main ends without a return statement, it effectively has
an automatic "return 0;". Stylistically speaking I prefer to always have
it in there anyway.....
 
K

Karthik

Karthik wrote:

The type of Represented happens to be a 'char' !! Change that to
size_t type. Do not make such dangerous conversions. Then heed your
compiler's warnings after converting the same to unsigned int.
Click to expand...

Oops !! I meant size_t here , and not unsigned int.
 
K

Karthik

Andre Kostur wrote:

Not required. If main ends without a return statement, it effectively has
an automatic "return 0;". Stylistically speaking I prefer to always have
it in there anyway.....
Click to expand...

Might have been the case with a primitive compiler. Modern compilers
refuse to compile, without that ( and it does make sense to be that
way). More than return 0, I would prefer still - EXIT_SUCCESS to make it
complete.
 
A

Andre Kostur

Andre Kostur wrote:



Might have been the case with a primitive compiler. Modern
compilers
refuse to compile, without that ( and it does make sense to be that
way). More than return 0, I would prefer still - EXIT_SUCCESS to make
it complete.
Click to expand...

Then the modern compilers would be refusing to compile a well-formed C++
program. (Section 3.6.1.5).
 
J

Jeff Schwab

Karthik said:
Andre Kostur wrote:




Might have been the case with a primitive compiler. Modern compilers
refuse to compile, without that ( and it does make sense to be that
way). More than return 0, I would prefer still - EXIT_SUCCESS to make it
complete.
Click to expand...

The return statement in main() is optional (3.6.1). If it's just going
to return a zero-valued constant, I prefer not to clutter the code with it.
 
R

Rolf Magnus

Karthik said:
Andre Kostur wrote:



Might have been the case with a primitive compiler.
Click to expand...

If by 'primitive' you mean standard compliant.
Modern compilers refuse to compile, without that ( and it does make
sense to be that way).
Click to expand...

It may make sense, but you should still replace those "modern compilers"
by old-fashioned
More than return 0, I would prefer still - EXIT_SUCCESS to make
it complete.
Click to expand...

--
Prof: I'm sorry, Fry, but astronomers renamed Uranus in 2620
to end that stupid joke once and for all.
Fry: Oh. What's it called now?
Prof: Urectum.
(ü+#äfrom Futurama)
fro,.-m Futurama)
 
M

Michael

Guys, thanks for advice on style but you haven't replied to my actual
question, whats wrong with the code, why does it crash??
 
A

Adriano Dal Bosco

Michael,

Karthik had the right hint. Represented not only happens to be a char
(and you are using it as an index to a vector -- which should be a size_t),
but worse, you allow it to assume values out of range to your vector. The
problem is here:

if(Represented != -1) v[Represented] = currentString;

I don't understand the conversion very well, but it will run if you only
change the above line to:

if(Represented < -1) v[Represented] = currentString;

or:

if(Represented > -1) v[Represented] = currentString;
(and I guess this gives the result you want)

or even:

if((Represented != -1) && (size_t(Represented) < v.size())) v[Represented] =
currentString;

or you can just keep it as it is and change the type of Represented to int.

This solves this problem, but I think other may appear further on.
Especially because you are using new to allocate memory, but you are not
deleting the new objects anywhere. Another problem is that you are not
defining a copy constructor and an assignment operator. This produce
surprising restults in many cases. The problem is that you have pointer
members and if you don't tell the compiler how to copy them, the compiler
will copy only their *addressess*.
So, I recomend that you define a destructor, a copy constructor and an
assignment operator for HuffmanNode.

Below is a code that compiles an runs withou errors (I just included some
extra headers and changed the type of Represented to int)

// -------------- start --------------------

#include <iostream>
#include <assert.h>
#include <vector>
#include <list>
#include <string>


using namespace std;


class HuffmanNode
{
public:
HuffmanNode* pLeft;
HuffmanNode* pRight;
int Represented;
float frequency;
HuffmanNode() : pLeft(NULL), pRight(NULL), Represented(-1),
frequency(-1) {}
void AddSubTreeToVector(vector<string>& v, string currentString);
};


int main()
{
list<HuffmanNode> nodes;
for(int i=0;i<256;i++)
{
HuffmanNode n;
n.Represented = i;
n.frequency = (i*i *10 )% 300;
nodes.push_back(n);
}
cout << "Populated Source List: " << nodes.size();

while(nodes.size() >1)
{
cout << "\n\tListSize: " << nodes.size();
HuffmanNode newNode;
newNode.pLeft = new HuffmanNode;
newNode.pRight = new HuffmanNode;

list<HuffmanNode>::iterator it;
list<HuffmanNode>::iterator smallest = nodes.begin();

//Find Smallest
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pLeft = *(smallest);
newNode.frequency = smallest->frequency;
nodes.erase(smallest);

//Find the next Snmallest
smallest = nodes.begin();
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pRight = *smallest;
newNode.frequency += smallest->frequency;
nodes.erase(smallest);
//Add the New Node
nodes.push_back(newNode);
}



HuffmanNode hmt = *(nodes.begin());
//Move Tree into vector for encoding:
vector<string> HuffmanCodes;
for(int i=0;i<256;i++)
{
string str;
HuffmanCodes.push_back(str);
}

hmt.AddSubTreeToVector(HuffmanCodes,"");
for(int i=0;i<256;i++)
{
string str = HuffmanCodes;
cout << i << ": " << str.c_str() << endl;
}


system("PAUSE");
}









void HuffmanNode::AddSubTreeToVector(vector<string>& v, string
currentString)
{
if(!this) return;
if(Represented != -1) v[Represented] = currentString;
//LeftSubTree
if(pLeft)
{
string LeftString;
LeftString = currentString;
LeftString.append("0");
pLeft->AddSubTreeToVector(v,LeftString);
}
//RightSubTree
if(pRight)
{
string RightString;
RightString = currentString;
RightString.append("0");
pRight->AddSubTreeToVector(v,RightString);
}
}

// -------------- end --------------------





Michael said:
Guys,
I'm trying to compile this code to build a huffman tree, but I'm getting a
runtime error and my degugger ends up somewhere in the STL files. What am i
doing wrong. I appreciate its not effiecient/stylistic, etc, it was just
something i wanted to try
Thanks

Mike





#include <assert.h>
#include <vector>
#include <list>
using std::list;
using std::vector;


class HuffmanNode
{
public:
HuffmanNode* pLeft;
HuffmanNode* pRight;
char Represented;
float frequency;
HuffmanNode() : pLeft(NULL), pRight(NULL), Represented(-1),
frequency(-1) {}
void AddSubTreeToVector(vector<string>& v, string currentString);
};


int main()
{
list<HuffmanNode> nodes;
for(int i=0;i<256;i++)
{
HuffmanNode n;
n.Represented = i;
n.frequency = (i*i *10 )% 300;
nodes.push_back(n);
}
cout << "Populated Source List: " << nodes.size();

while(nodes.size() >1)
{
cout << "\n\tListSize: " << nodes.size();
HuffmanNode newNode;
newNode.pLeft = new HuffmanNode;
newNode.pRight = new HuffmanNode;

list<HuffmanNode>::iterator it;
list<HuffmanNode>::iterator smallest = nodes.begin();

//Find Smallest
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pLeft = *(smallest);
newNode.frequency = smallest->frequency;
nodes.erase(smallest);

//Find the next Snmallest
smallest = nodes.begin();
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pRight = *smallest;
newNode.frequency += smallest->frequency;
nodes.erase(smallest);
//Add the New Node
nodes.push_back(newNode);
}



HuffmanNode hmt = *(nodes.begin());
//Move Tree into vector for encoding:
vector<string> HuffmanCodes;
for(int i=0;i<256;i++)
{
string str;
HuffmanCodes.push_back(str);
}

hmt.AddSubTreeToVector(HuffmanCodes,"");
for(int i=0;i<256;i++)
{
string str = HuffmanCodes;
cout << i << ": " << str.c_str() << endl;
}


system("PAUSE");
}









void HuffmanNode::AddSubTreeToVector(vector<string>& v, string
currentString)
{
assert(this);
if(Represented != -1) v[Represented] = currentString;
//LeftSubTree
if(pLeft)
{
string LeftString;
LeftString = currentString;
LeftString.append("0");
pLeft->AddSubTreeToVector(v,LeftString);
}
//RightSubTree
if(pRight)
{
string RightString;
RightString = currentString;
RightString.append("0");
pRight->AddSubTreeToVector(v,RightString);
}
}
Click to expand...
 
M

Michael

Cool, Many thanks I'm back in business!!
Adriano Dal Bosco said:
Michael,

Karthik had the right hint. Represented not only happens to be a char
(and you are using it as an index to a vector -- which should be a size_t),
but worse, you allow it to assume values out of range to your vector. The
problem is here:

if(Represented != -1) v[Represented] = currentString;

I don't understand the conversion very well, but it will run if you only
change the above line to:

if(Represented < -1) v[Represented] = currentString;

or:

if(Represented > -1) v[Represented] = currentString;
(and I guess this gives the result you want)

or even:

if((Represented != -1) && (size_t(Represented) < v.size())) v[Represented] =
currentString;

or you can just keep it as it is and change the type of Represented to int.

This solves this problem, but I think other may appear further on.
Especially because you are using new to allocate memory, but you are not
deleting the new objects anywhere. Another problem is that you are not
defining a copy constructor and an assignment operator. This produce
surprising restults in many cases. The problem is that you have pointer
members and if you don't tell the compiler how to copy them, the compiler
will copy only their *addressess*.
So, I recomend that you define a destructor, a copy constructor and an
assignment operator for HuffmanNode.

Below is a code that compiles an runs withou errors (I just included some
extra headers and changed the type of Represented to int)

// -------------- start --------------------

#include <iostream>
#include <assert.h>
#include <vector>
#include <list>
#include <string>


using namespace std;


class HuffmanNode
{
public:
HuffmanNode* pLeft;
HuffmanNode* pRight;
int Represented;
float frequency;
HuffmanNode() : pLeft(NULL), pRight(NULL), Represented(-1),
frequency(-1) {}
void AddSubTreeToVector(vector<string>& v, string currentString);
};


int main()
{
list<HuffmanNode> nodes;
for(int i=0;i<256;i++)
{
HuffmanNode n;
n.Represented = i;
n.frequency = (i*i *10 )% 300;
nodes.push_back(n);
}
cout << "Populated Source List: " << nodes.size();

while(nodes.size() >1)
{
cout << "\n\tListSize: " << nodes.size();
HuffmanNode newNode;
newNode.pLeft = new HuffmanNode;
newNode.pRight = new HuffmanNode;

list<HuffmanNode>::iterator it;
list<HuffmanNode>::iterator smallest = nodes.begin();

//Find Smallest
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pLeft = *(smallest);
newNode.frequency = smallest->frequency;
nodes.erase(smallest);

//Find the next Snmallest
smallest = nodes.begin();
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pRight = *smallest;
newNode.frequency += smallest->frequency;
nodes.erase(smallest);
//Add the New Node
nodes.push_back(newNode);
}



HuffmanNode hmt = *(nodes.begin());
//Move Tree into vector for encoding:
vector<string> HuffmanCodes;
for(int i=0;i<256;i++)
{
string str;
HuffmanCodes.push_back(str);
}

hmt.AddSubTreeToVector(HuffmanCodes,"");
for(int i=0;i<256;i++)
{
string str = HuffmanCodes;
cout << i << ": " << str.c_str() << endl;
}


system("PAUSE");
}









void HuffmanNode::AddSubTreeToVector(vector<string>& v, string
currentString)
{
if(!this) return;
if(Represented != -1) v[Represented] = currentString;
//LeftSubTree
if(pLeft)
{
string LeftString;
LeftString = currentString;
LeftString.append("0");
pLeft->AddSubTreeToVector(v,LeftString);
}
//RightSubTree
if(pRight)
{
string RightString;
RightString = currentString;
RightString.append("0");
pRight->AddSubTreeToVector(v,RightString);
}
}

// -------------- end --------------------





Michael said:
Guys,
I'm trying to compile this code to build a huffman tree, but I'm getting a
runtime error and my degugger ends up somewhere in the STL files. What
Click to expand...
am
i
doing wrong. I appreciate its not effiecient/stylistic, etc, it was just
something i wanted to try
Thanks

Mike





#include <assert.h>
#include <vector>
#include <list>
using std::list;
using std::vector;


class HuffmanNode
{
public:
HuffmanNode* pLeft;
HuffmanNode* pRight;
char Represented;
float frequency;
HuffmanNode() : pLeft(NULL), pRight(NULL), Represented(-1),
frequency(-1) {}
void AddSubTreeToVector(vector<string>& v, string currentString);
};


int main()
{
list<HuffmanNode> nodes;
for(int i=0;i<256;i++)
{
HuffmanNode n;
n.Represented = i;
n.frequency = (i*i *10 )% 300;
nodes.push_back(n);
}
cout << "Populated Source List: " << nodes.size();

while(nodes.size() >1)
{
cout << "\n\tListSize: " << nodes.size();
HuffmanNode newNode;
newNode.pLeft = new HuffmanNode;
newNode.pRight = new HuffmanNode;

list<HuffmanNode>::iterator it;
list<HuffmanNode>::iterator smallest = nodes.begin();

//Find Smallest
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pLeft = *(smallest);
newNode.frequency = smallest->frequency;
nodes.erase(smallest);

//Find the next Snmallest
smallest = nodes.begin();
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pRight = *smallest;
newNode.frequency += smallest->frequency;
nodes.erase(smallest);
//Add the New Node
nodes.push_back(newNode);
}



HuffmanNode hmt = *(nodes.begin());
//Move Tree into vector for encoding:
vector<string> HuffmanCodes;
for(int i=0;i<256;i++)
{
string str;
HuffmanCodes.push_back(str);
}

hmt.AddSubTreeToVector(HuffmanCodes,"");
for(int i=0;i<256;i++)
{
string str = HuffmanCodes;
cout << i << ": " << str.c_str() << endl;
}


system("PAUSE");
}









void HuffmanNode::AddSubTreeToVector(vector<string>& v, string
currentString)
{
assert(this);
if(Represented != -1) v[Represented] = currentString;
//LeftSubTree
if(pLeft)
{
string LeftString;
LeftString = currentString;
LeftString.append("0");
pLeft->AddSubTreeToVector(v,LeftString);
}
//RightSubTree
if(pRight)
{
string RightString;
RightString = currentString;
RightString.append("0");
pRight->AddSubTreeToVector(v,RightString);
}
}
Click to expand...
Click to expand...
 
J

Julie

Michael said:
Guys, thanks for advice on style but you haven't replied to my actual
question, whats wrong with the code, why does it crash??
Click to expand...

You asked the wrong question, then.

If you want an answer as to why something doesn't work, ask a question on
style. If you want answers to style, ask why something doesn't work.
 
D

Dave Townsend

Michael


The reason your code crashes is you have an invalid
index in:

void HuffmanNode::AddSubTreeToVector( vector<string>& v, string
currentString)
{
assert(this);
if(Represented != -1) v[Represented] = currentString;

The value of Represented is some negative number.
This is because the type of represented souldbe unsigned char,
not char, so you can stuff a 0..255 value in that.

dave
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

GET NEIL DEGRASSES TYSON, I ripped a hole with this one... 0
newbie question about data I/O 15
STL - erasing from a set 5
question on vector<T> 11
STL::MAP: Printing values only once .. 9
iterator: not declared in this scope 1
STL - erasing from a set 5
STL ?? 2

Members online

Total: 75 (members: 1, guests: 74)
Robots: 439

Forum statistics

Threads
473,995
Messages
2,570,231
Members
46,820
Latest member
GilbertoA5

Latest Threads

Top