STL question: is this O/T ?

[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 AddSubTreeToVec tor(vector<stri ng>& v, string currentString);
};
int main()
{
list<HuffmanNod e> 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.siz e() >1)
{
cout << "\n\tListSi ze: " << nodes.size();
HuffmanNode newNode;
newNode.pLeft = new HuffmanNode;
newNode.pRight = new HuffmanNode;

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

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

//Find the next Snmallest
smallest = nodes.begin();
for(it = nodes.begin();i t != nodes.end();it+ +)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pRight = *smallest;
newNode.frequen cy += smallest->frequency;
nodes.erase(sma llest);
//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.pu sh_back(str);
}

hmt.AddSubTreeT oVector(Huffman Codes,"");
for(int i=0;i<256;i++)
{
string str = HuffmanCodes[i];
cout << i << ": " << str.c_str() << endl;
}
system("PAUSE") ;
}



void HuffmanNode::Ad dSubTreeToVecto r(vector<string >& v, string
currentString)
{
assert(this);
if(Represented != -1) v[Represented] = currentString;
//LeftSubTree
if(pLeft)
{
string LeftString;
LeftString = currentString;
LeftString.appe nd("0");
pLeft->AddSubTreeToVe ctor(v,LeftStri ng);
}
//RightSubTree
if(pRight)
{
string RightString;
RightString = currentString;
RightString.app end("0");
pRight->AddSubTreeToVe ctor(v,RightStr ing);
}
}

[Karthik]

Michael wrote:

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
The code didn't compile in the first place.



#include <assert.h>
#include <vector>
#include <list>
using std::list;
using std::vector;
#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 AddSubTreeToVec tor(vector<stri ng>& v, string currentString);
};
int main()
{
list<HuffmanNod e> nodes;
for(int i=0;i<256;i++) // 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.siz e() >1)
{
cout << "\n\tListSi ze: " << nodes.size();
HuffmanNode newNode;
newNode.pLeft = new HuffmanNode;
newNode.pRight = new HuffmanNode;

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

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

//Find the next Snmallest
smallest = nodes.begin();
for(it = nodes.begin();i t != nodes.end();it+ +)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pRight = *smallest;
newNode.frequen cy += smallest->frequency;
nodes.erase(sma llest);
//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.pu sh_back(str);
}

hmt.AddSubTreeT oVector(Huffman Codes,"");
for(int i=0;i<256;i++)
{
string str = HuffmanCodes[i];
cout << i << ": " << str.c_str() << endl;
}
system("PAUSE") ; // 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::Ad dSubTreeToVecto r(vector<string >& v, string
currentString)
{
assert(this);
if(Represented != -1) v[Represented] = currentString;

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.
--
Karthik
Humans please 'removeme_' for my real email.

[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.

Oops !! I meant size_t here , and not unsigned int.
--
Karthik
Humans please 'removeme_' for my real email.

[Andre Kostur]

Karthik <re************ *******@yahoo.c om> wrote in
news:4092b08f$1 @darkstar:

Michael wrote:

system("PAUSE") ;

// 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 .

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.....

[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.....

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.

--
Karthik
Humans please 'removeme_' for my real email.

[Jeff Schwab]

Karthik wrote:

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.....

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.

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.

[Andre Kostur]

Karthik <re************ *******@yahoo.c om> wrote in
news:4092c7de$1 @darkstar:

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.....

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.

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

[Rolf Magnus]

Karthik wrote:

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.....
Might have been the case with a primitive compiler.

If by 'primitive' you mean standard compliant.
Modern compilers refuse to compile, without that ( and it does make
sense to be that way).
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.

--
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)

[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??


"Rolf Magnus" <ra******@t-online.de> wrote in message
news:c6******** *****@news.t-online.com...

Karthik wrote:

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.....

Might have been the case with a primitive compiler.

If by 'primitive' you mean standard compliant.

Modern compilers refuse to compile, without that ( and it does make
sense to be that way).

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.

--
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)

[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(Represe nted) < 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 AddSubTreeToVec tor(vector<stri ng>& v, string currentString);
};
int main()
{
list<HuffmanNod e> 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.siz e() >1)
{
cout << "\n\tListSi ze: " << nodes.size();
HuffmanNode newNode;
newNode.pLeft = new HuffmanNode;
newNode.pRight = new HuffmanNode;

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

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

//Find the next Snmallest
smallest = nodes.begin();
for(it = nodes.begin();i t != nodes.end();it+ +)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pRight = *smallest;
newNode.frequen cy += smallest->frequency;
nodes.erase(sma llest);
//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.pu sh_back(str);
}

hmt.AddSubTreeT oVector(Huffman Codes,"");
for(int i=0;i<256;i++)
{
string str = HuffmanCodes[i];
cout << i << ": " << str.c_str() << endl;
}
system("PAUSE") ;
}



void HuffmanNode::Ad dSubTreeToVecto r(vector<string >& v, string
currentString)
{
if(!this) return;
if(Represented != -1) v[Represented] = currentString;
//LeftSubTree
if(pLeft)
{
string LeftString;
LeftString = currentString;
LeftString.appe nd("0");
pLeft->AddSubTreeToVe ctor(v,LeftStri ng);
}
//RightSubTree
if(pRight)
{
string RightString;
RightString = currentString;
RightString.app end("0");
pRight->AddSubTreeToVe ctor(v,RightStr ing);
}
}

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

"Michael" <sl***********@ hotmail.com> wrote in message
news:c6******** **@sparta.btint ernet.com...

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 AddSubTreeToVec tor(vector<stri ng>& v, string currentString);
};
int main()
{
list<HuffmanNod e> 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.siz e() >1)
{
cout << "\n\tListSi ze: " << nodes.size();
HuffmanNode newNode;
newNode.pLeft = new HuffmanNode;
newNode.pRight = new HuffmanNode;

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

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

//Find the next Snmallest
smallest = nodes.begin();
for(it = nodes.begin();i t != nodes.end();it+ +)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pRight = *smallest;
newNode.frequen cy += smallest->frequency;
nodes.erase(sma llest);
//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.pu sh_back(str);
}

hmt.AddSubTreeT oVector(Huffman Codes,"");
for(int i=0;i<256;i++)
{
string str = HuffmanCodes[i];
cout << i << ": " << str.c_str() << endl;
}
system("PAUSE") ;
}



void HuffmanNode::Ad dSubTreeToVecto r(vector<string >& v, string
currentString)
{
assert(this);
if(Represented != -1) v[Represented] = currentString;
//LeftSubTree
if(pLeft)
{
string LeftString;
LeftString = currentString;
LeftString.appe nd("0");
pLeft->AddSubTreeToVe ctor(v,LeftStri ng);
}
//RightSubTree
if(pRight)
{
string RightString;
RightString = currentString;
RightString.app end("0");
pRight->AddSubTreeToVe ctor(v,RightStr ing);
}
}