Hmm, and I though everything was going so well. :-/

OK, any C++ experts have any idea why this code snippet causes my 
program to crash at runtime?

   typedef std::vector<bool> Codeword;

   std::string codeword(const Codeword &c)
   {
     std::string out;

     for (unsigned int i=0; i<c.size(); i++)
       if (c[i]) out.append("1"); else out.append("0");

     return out;
   }

"Unhandled exception at 0x00414166 in Huffman01.exe: 0xC0000005: Access 
violation reading location 0x00000004."

The code looks fine to me - but what I do know?

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> OK, any C++ experts have any idea why this code snippet causes my 
> program to crash at runtime?

>    typedef std::vector<bool> Codeword;

>    std::string codeword(const Codeword &c)
>    {
>      std::string out;

>      for (unsigned int i=0; i<c.size(); i++)
>        if (c[i]) out.append("1"); else out.append("0");

>      return out;
>    }

  I can't see anything wrong with it, and I tried it and there was
nothing wrong with it. The error must be somewhere else.

  If you are running it in linux, try running it using valgrind (if you
don't have it, install it; it's essential). In other words:

valgrind ./yourprogram

  If will tell you if you have some out-of-bounds access or memory leaks.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   I can't see anything wrong with it, and I tried it and there was
> nothing wrong with it. The error must be somewhere else.

Right. So maybe I'm passing it a reference to something that doesn't 
exist anymore then?

>   If you are running it in linux, try running it using valgrind (if you
> don't have it, install it; it's essential). In other words:
> 
> valgrind ./yourprogram
> 
>   If will tell you if you have some out-of-bounds access or memory leaks.

M$ Visual Studio is telling me something is wrong, but it isn't telling 
me much beyond that. (I probably need to figure out how to work the 
debugger first...)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Warp wrote:

> >   I can't see anything wrong with it, and I tried it and there was
> > nothing wrong with it. The error must be somewhere else.

> Right. So maybe I'm passing it a reference to something that doesn't 
> exist anymore then?

  Without seeing the whole program it's impossible to tell.

  Btw, have you been using the at() function rather than operator [] like
I have been suggesting?

> >   If you are running it in linux, try running it using valgrind (if you
> > don't have it, install it; it's essential). In other words:
> > 
> > valgrind ./yourprogram
> > 
> >   If will tell you if you have some out-of-bounds access or memory leaks.

> M$ Visual Studio is telling me something is wrong, but it isn't telling 
> me much beyond that. (I probably need to figure out how to work the 
> debugger first...)

  Just compile in debug mode and run the debugger (F5).

  However, the Visual Studio debugger won't tell you if you have, for
example, a memory leak. The place where the program crashes (which will
be shown by the debugger) is not necessarily the place where the bug is.
It might be able to tell you if you are writing out of bounds or accessing
freed memory, but not necessarily. Valgrind will be able to do that.
Unfortunately, AFAIK, valgrind is not available for Windows or VS projects,
so you'll have to do the testing in linux.

  (Profilers like valgrind which support VS programs in Windows exist,
but I know of no free one.)

-- 
                                                          - Warp

Post a reply to this message

>  Just compile in debug mode and run the debugger (F5).
>
>  However, the Visual Studio debugger won't tell you if you have, for
> example, a memory leak. The place where the program crashes (which will
> be shown by the debugger) is not necessarily the place where the bug is.

True; sometimes you have to step carefully through the program to see what 
it's doing and figure out where your memory management is going wrong. In 
this case though, the error is

"Unhandled exception at 0x00414166 in Huffman01.exe: 0xC0000005: Access
violation reading location 0x00000004."

Access violation reading location 0x00000004 means it's very likely you're 
dereferencing a NULL pointer somewhere, because of how close 4 is to 0. (The 
program is taking a NULL pointer, treating it as a struct or class of some 
sort, and trying to get the member that is 4 bytes into it.) So, if you just 
hit F5 and run the program as usual, it will tell you right where it is when 
it crashes by pointing at the line. You can also look at the call stack pane 
to see how it got there. It will probably be easy to see what the NULL 
pointer is.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

>     for (unsigned int i=0; i<c.size(); i++)
>       if (c[i]) out.append("1"); else out.append("0");

This isn't the cause of your crash, but I recommend not squishing your code 
together like that. Keep each statement on a separate line and use brackets 
around anything that's not a single simple statement:

    for ( unsigned int i = 0; i < c.size(); i++ )
    {
        if ( c[i] )
            out.append( "1" );
        else
            out.append( "0" );
    }

Also put spaces around your operators like "=", "+" and "<". Readable code 
is superior to short code.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

Slime wrote:
>>     for (unsigned int i=0; i<c.size(); i++)
>>       if (c[i]) out.append("1"); else out.append("0");
> 
> This isn't the cause of your crash, but I recommend not squishing your code 
> together like that. Keep each statement on a separate line and use brackets 
> around anything that's not a single simple statement:
> 
>     for ( unsigned int i = 0; i < c.size(); i++ )
>     {
>         if ( c[i] )
>             out.append( "1" );
>         else
>             out.append( "0" );
>     }

If he wants brevity he could also code it like this:

  for (int i = 0; i < c.size(); i++)
    out.append(c[i] ? "1" : "0");

which is just as valid and avoids running the if/else together.

-- Chris

Post a reply to this message

Slime wrote:

> "Unhandled exception at 0x00414166 in Huffman01.exe: 0xC0000005: Access
> violation reading location 0x00000004."
> 
> Access violation reading location 0x00000004 means it's very likely you're 
> dereferencing a NULL pointer somewhere, because of how close 4 is to 0.

Yeah, seems plausible. (Except that I'm not using pointers anywhere, 
only references.)

> So, if you just 
> hit F5 and run the program as usual, it will tell you right where it is when 
> it crashes by pointing at the line. You can also look at the call stack pane 
> to see how it got there. It will probably be easy to see what the NULL 
> pointer is.

It's somewhere inside vector.cpp. (And the code makes *no sense* to me 
at all. The comments mumble something about copy constructors though...)

Now if I could somehow figure out which part of *my* code is calling the 
failing routine, and with what arguments, I'd have a shot...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Warp wrote:

>   Without seeing the whole program it's impossible to tell.

Well, the program isn't that large, so just for a giggle I'll include it 
here. The compiler claims there's nothing wrong with it, but clearly 
there is. I can't wait to see how many different kinds of mistake I've 
made... :-}



#include <iostream>
#include <vector>
#include <string>

typedef char Symbol;
typedef std::vector<bool> Codeword;

std::string codeword(const Codeword &c)
{
   std::string out;

   for (unsigned int i=0; i<c.size(); i++)
     if (c[i]) out.append("1"); else out.append("0");

   return out;
}

class SymbolInfo
{
public:
   Symbol symbol;
   double prob;
   Codeword code;

   SymbolInfo(Symbol s, double pr) : code()
   {
     symbol = s;
     prob = pr;
   }

   void prefix(const bool p)
   {
     code.push_back(p);
   }
};

class Tree
{
public:
   Tree(SymbolInfo& s) : symbols()
   {
     symbols.push_back(s);
     prob = s.prob;
   }

   void join(const Tree& tree)
   {
     for (unsigned int i=0; i<symbols.size(); i++)
       symbols[i].prefix(false);

     for (unsigned int i=0; i<tree.symbols.size(); i++)
     {
       SymbolInfo s = tree.symbols[i];
       s.prefix(true);
       symbols.push_back(s);
       prob += s.prob;
     }
   }

   const Codeword& lookup(const Symbol key)
   {
     for (unsigned int i=0; i<symbols.size(); i++)
       if (symbols[i].symbol == key) return symbols[i].code;
   }

   const double Prob() {return prob;}

private:
   std::vector<SymbolInfo> symbols;
   double prob;
};

const Tree& build_tree(std::vector<SymbolInfo> info)
{
   std::vector<Tree> trees;

   for (unsigned int i=0; i<info.size(); i++)
   {
     Tree t(info[i]);
     trees.push_back(t);
   }

   while (trees.size() > 1)
   {
     int index = 0;
     for (unsigned int i = 1; i<trees.size(); i++)
       if (trees[i].Prob() < trees[index].Prob()) index = i;

     Tree t0 = trees[index];
     trees.erase(trees.begin() + index);

     index = 0;
     for (unsigned int i = 1; i<trees.size(); i++)
       if (trees[i].Prob() < trees[index].Prob()) index = i;

     Tree t1 = trees[index];
     trees.erase(trees.begin() + index);

     t0.join(t1);
     trees.push_back(t0);
   }

   return trees[0];
}

int main()
{
   SymbolInfo A('A', 0.5);
   SymbolInfo B('B', 0.25);
   SymbolInfo C('C', 0.125);
   SymbolInfo D('D', 0.125);
   std::vector<SymbolInfo> symbols;
   symbols.push_back(A);
   symbols.push_back(B);
   symbols.push_back(C);
   symbols.push_back(D);
   Tree t = build_tree(symbols);

   std::cout << "A: " << codeword(t.lookup('A')) << std::endl;
   std::cout << "B: " << codeword(t.lookup('B')) << std::endl;
   std::cout << "C: " << codeword(t.lookup('C')) << std::endl;
   std::cout << "D: " << codeword(t.lookup('D')) << std::endl;
}

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

> It's somewhere inside vector.cpp. (And the code makes *no sense* to me at 
> all. The comments mumble something about copy constructors though...)

Yeah, the STL code provided with visual studio is very unreadable.

> Now if I could somehow figure out which part of *my* code is calling the 
> failing routine, and with what arguments, I'd have a shot...

You need to find the call stack window. It will give you a list of the 
functions that called each other to get where the code is currently 
executing. It should be one of the tabs along the bottom when debugging, or 
you might have to look through the menus (under "window" or "debug") to turn 
it on. Then you can double click on each level of function call and see what 
its local variables' values are.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

> const Tree& build_tree(std::vector<SymbolInfo> info)
> {
>   std::vector<Tree> trees;
>
...
>
>   return trees[0];
> }

You are returning a reference to a local variable. When the function 
finishes, trees' destructor will be called and all of its contents will be 
deallocated. So you're returning a reference to invalid memory. If you're 
not worried about copying Trees around, you can just remove the & from the 
return type.

You might also want to assert( trees.size() > 0 ) to make sure the function 
worked properly and there's something there to return.

That's the only actual problem I see. Otherwise I'm a little worried, 
efficiency-wise, about how many vectors you're copying around, but that may 
not be worth worrying about at this stage.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

Slime wrote:
>> const Tree& build_tree(std::vector<SymbolInfo> info)
>> {
>>   std::vector<Tree> trees;
>>
> ...
>>   return trees[0];
>> }
> 
> You are returning a reference to a local variable.

DOH!! >_<

Yeah, that can't be good...

> You might also want to assert( trees.size() > 0 ) to make sure the function 
> worked properly and there's something there to return.

The loop right above that is while(trees.size() > 1). Each pass of the 
loop removes two trees and inserts one tree.

> That's the only actual problem I see. Otherwise I'm a little worried, 
> efficiency-wise, about how many vectors you're copying around, but that may 
> not be worth worrying about at this stage.

Yeah, that too...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

>> You might also want to assert( trees.size() > 0 ) to make sure the 
>> function worked properly and there's something there to return.
>
> The loop right above that is while(trees.size() > 1). Each pass of the 
> loop removes two trees and inserts one tree.

It definitely matters less when you're the only one editing the code, but 
asserting things like this is still a good habit to get into. I noticed that 
the loop had that behavior, but what if:

 - The loop didn't work as intended and sometimes, for instance, broke out 
before inserting the new element?
 - The loop works right, but at a later date you change it for some 
unrelated reason and break it in a subtle way?
 - trees.size() is 0 in the first place? This could happen if an empty 
vector was passed in.

The alternative to adding an assert is a small risk that at some point in 
the future you'll spend hours tracking down a crash. The more asserts you 
use, the more time you'll save! It takes time to learn where to add them, 
and I admit I went for years without using a single one. Once you start to 
use them consistently, you can be surprised at how frequently you see them 
fail, and you learn more about your own potential to make mistakes.

By the way, I wouldn't have recommended adding that assert if the loop were 
while( trees.size() != 1 ), since that would make the assert perfectly 
redundant. Of course in that case, I would assert that trees.size() >= 1 
before the loop to make sure the loop could work properly.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
>    Tree t = build_tree(symbols);

  In this case the error messages given by valgrind wouldn't have been
the clearest possible, but they nevertheless point to this line being
the ultimate culprit (which, ultimately, is caused by build_tree() returning
a reference to a local variable).

  Anyways, I'm wondering why you are passing the parameter by value rather
than by const reference...

-- 
                                                          - Warp

Post a reply to this message

On Sun, 05 Oct 2008 06:42:07 +0200, Chris Cason  
<del### [at] deletethistoopovrayorg> wrote:
>
> If he wants brevity he could also code it like this:
>
>   for (int i = 0; i < c.size(); i++)
>     out.append(c[i] ? "1" : "0");
>
> which is just as valid and avoids running the if/else together.

The compiler would likely warn about the signed/unsigned comparison in the  
loop condition. The proper type for the index is Codeword::size_type.

He could also skip the conditional in the loop body entirely:


typedef std::vector<bool> Codeword;

std::string codeword( Codeword const& c )
{
	std::string out;

	for( Codeword::size_type i = 0; i < c.size(); ++i )
		out += ( '0' + int(c[i]) );

	return out;
}



-- 
FE

Post a reply to this message

Fredrik Eriksson <fe79}--at--{yahoo}--dot--{com> wrote:
> std::string codeword( Codeword const& c )
> {
>         std::string out;

  Also after this it can be a good idea to do:

          out.reserve(c.size());

  This will make it slightly more efficient because it avoids reallocations
later, when the string is filled with that many characters.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Orchid XP v8 <voi### [at] devnull> wrote:
>>    Tree t = build_tree(symbols);
> 
>   In this case the error messages given by valgrind wouldn't have been
> the clearest possible, but they nevertheless point to this line being
> the ultimate culprit (which, ultimately, is caused by build_tree() returning
> a reference to a local variable).

Yeah. I guess since the error only came to light when I added a new 
function, I assumed that the new function must be the problem. In fact 
it was just exhibiting a problem that already existed...

>   Anyways, I'm wondering why you are passing the parameter by value rather
> than by const reference...

Ooo, well spotted. That's simply an oversight on my part. Since all the 
syntax is still kinda new to me, I keep forgetting to write bits. (E.g., 
the compiler keeps complaining that I'm using signed integers to index 
things.)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Slime wrote:

> It definitely matters less when you're the only one editing the code, but 
> asserting things like this is still a good habit to get into.

OK, fair enough.

>  - trees.size() is 0 in the first place? This could happen if an empty 
> vector was passed in.

There probably *should* be an assert to check that the vector passed in 
is non-empty...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Chris Cason wrote:

> If he wants brevity he could also code it like this:
> 
>   for (int i = 0; i < c.size(); i++)
>     out.append(c[i] ? "1" : "0");
> 
> which is just as valid and avoids running the if/else together.

Ooo, I like that. (It makes it clear that append() is always called, and 
it's only the argument that changes depending on c[i].)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Slime wrote:

> If you're 
> not worried about copying Trees around, you can just remove the & from the 
> return type.

Changing this single character makes my program work as intended. Yay me!

I guess the efficient thing to do would be to have the caller allocate 
an empty tree and pass it in by reference and mutate that... Hmm, but 
how to be sure the tree passed in is empty? I guess I could just add 
another assert() for that...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

On 05-Oct-08 6:42, Chris Cason wrote:
> Slime wrote:
>>>     for (unsigned int i=0; i<c.size(); i++)
>>>       if (c[i]) out.append("1"); else out.append("0");
>> This isn't the cause of your crash, but I recommend not squishing your code 
>> together like that. Keep each statement on a separate line and use brackets 
>> around anything that's not a single simple statement:
>>
>>     for ( unsigned int i = 0; i < c.size(); i++ )
>>     {
>>         if ( c[i] )
>>             out.append( "1" );
>>         else
>>             out.append( "0" );
>>     }
> 
> If he wants brevity he could also code it like this:
> 
>   for (int i = 0; i < c.size(); i++)
>     out.append(c[i] ? "1" : "0");
> 
> which is just as valid and avoids running the if/else together.
> 
Didn't we code that more like out.append("0" + c[i]) just to confuse the 
readers?

Post a reply to this message

On Sun, 05 Oct 2008 15:36:45 +0200, andrel <a_l### [at] hotmailcom>  
wrote:
>>
> Didn't we code that more like out.append("0" + c[i]) just to confuse the  
> readers?

Nitpick: It has to be '0', not "0".


You could also do it like this:
	out += c[i]["01"];

If you were in a particularly foul mood, you could write it like this:
	out += c??(i??)??("01"??);


-- 
FE

Post a reply to this message

On 05-Oct-08 15:36, andrel wrote:
> On 05-Oct-08 6:42, Chris Cason wrote:
>> Slime wrote:
>>>>     for (unsigned int i=0; i<c.size(); i++)
>>>>       if (c[i]) out.append("1"); else out.append("0");
>>> This isn't the cause of your crash, but I recommend not squishing 
>>> your code together like that. Keep each statement on a separate line 
>>> and use brackets around anything that's not a single simple statement:
>>>
>>>     for ( unsigned int i = 0; i < c.size(); i++ )
>>>     {
>>>         if ( c[i] )
>>>             out.append( "1" );
>>>         else
>>>             out.append( "0" );
>>>     }
>>
>> If he wants brevity he could also code it like this:
>>
>>   for (int i = 0; i < c.size(); i++)
>>     out.append(c[i] ? "1" : "0");
>>
>> which is just as valid and avoids running the if/else together.
>>
> Didn't we code that more like out.append("0" + c[i]) just to confuse the 
> readers?

Been a long time since I actually did write sufficient amount of C. :( I 
think I meant the character constant '0' and not the string "0".

Post a reply to this message

On 05-Oct-08 15:51, Fredrik Eriksson wrote:
> On Sun, 05 Oct 2008 15:36:45 +0200, andrel <a_l### [at] hotmailcom> 
> wrote:
>>>
>> Didn't we code that more like out.append("0" + c[i]) just to confuse 
>> the readers?
> 
> Nitpick: It has to be '0', not "0".

Yeah I remembered too late.

> You could also do it like this:
>     out += c[i]["01"];

Is that C or C++?

> If you were in a particularly foul mood, you could write it like this:
>     out += c??(i??)??("01"??);
what += does??(that??)??("Mean"??)

Post a reply to this message

On Sun, 05 Oct 2008 15:56:12 +0200, andrel <a_l### [at] hotmailcom>  
wrote:
>
>> You could also do it like this:
>>     out += c[i]["01"];
>
> Is that C or C++?

Either.


>> If you were in a particularly foul mood, you could write it like this:
>>     out += c??(i??)??("01"??);
> what += does??(that??)??("Mean"??)

??( is an alternative token for [. Similarly for ??) and ].


-- 
FE

Post a reply to this message

On 05-Oct-08 16:03, Fredrik Eriksson wrote:

> 
>>> If you were in a particularly foul mood, you could write it like this:
>>>     out += c??(i??)??("01"??);
>> what += does??(that??)??("Mean"??)
> 
> ??( is an alternative token for [. Similarly for ??) and ].

I don't remember that one. I seem to have dislocated my k&r and bjarne 
books and I seem not to be able to find that on the web either. Are you 
sure that that isn't just a compiler/hardware specific hack?

Post a reply to this message

andrel <a_l### [at] hotmailcom> wrote:
> > ??( is an alternative token for [. Similarly for ??) and ].

> I don't remember that one. I seem to have dislocated my k&r and bjarne 
> books and I seem not to be able to find that on the web either. Are you 
> sure that that isn't just a compiler/hardware specific hack?

http://en.wikipedia.org/wiki/C_trigraph

-- 
                                                          - Warp

Post a reply to this message

On Sun, 05 Oct 2008 16:39:42 +0200, andrel <a_l### [at] hotmailcom>  
wrote:
>>  ??( is an alternative token for [. Similarly for ??) and ].
>
> I don't remember that one. I seem to have dislocated my k&r and bjarne  
> books and I seem not to be able to find that on the web either. Are you  
> sure that that isn't just a compiler/hardware specific hack?

Yes, I am sure. They are called trigraphs and are listed in section 2.3 of  
the C++ standard.

Strictly speaking, they are not actually alternative tokens. They are  
substituted before any other processing of the source.

There is a set of actual alternative tokens though. They are sometimes  
called digraphs. You could thus write:
	out += c<:i:><:"01":>;


-- 
FE

Post a reply to this message

On 05-Oct-08 17:12, Warp wrote:
> andrel <a_l### [at] hotmailcom> wrote:
>>> ??( is an alternative token for [. Similarly for ??) and ].
> 
>> I don't remember that one. I seem to have dislocated my k&r and bjarne 
>> books and I seem not to be able to find that on the web either. Are you 
>> sure that that isn't just a compiler/hardware specific hack?
> 
> http://en.wikipedia.org/wiki/C_trigraph
> 
Thanks warp and frederick. This wiki page still keeps me wondering when 
these trigraphs were introduced. Must be before the 1994 digraphs (which 
is indeed long after my sort of formal training in C).

I could not find them with google. searching for ??) did not give any 
result. Any of the google wizards know what I should have asked? (Apart 
from trigraph, because that was the term I didn't know, otherwise I 
would not be looking)

Post a reply to this message

On Sun, 05 Oct 2008 17:48:04 +0200, andrel <a_l### [at] hotmailcom>  
wrote:
>>
> This wiki page still keeps me wondering when these trigraphs were  
> introduced. Must be before the 1994 digraphs (which is indeed long after  
> my sort of formal training in C).

Late eighties I think.


-- 
FE

Post a reply to this message

Orchid XP v8 nous illumina en ce 2008-10-04 14:37 -->
> Hmm, and I though everything was going so well. :-/
> 
> OK, any C++ experts have any idea why this code snippet causes my 
> program to crash at runtime?
> 
>   typedef std::vector<bool> Codeword;
> 
>   std::string codeword(const Codeword &c)
>   {
>     std::string out;
> 
>     for (unsigned int i=0; i<c.size(); i++)
>       if (c[i]) out.append("1"); else out.append("0");
> 
>     return out;
>   }
> 
> "Unhandled exception at 0x00414166 in Huffman01.exe: 0xC0000005: Access 
> violation reading location 0x00000004."
> 
> The code looks fine to me - but what I do know?
> 
Maybe you have an uninitialised pointer.

Do you get any output? If you don't, it mean that the variable "c" don't get 
initialised properly.
Look at the caller. Maybe the variable that is supposed to be passed is in fact 
a null, or an uninitialised pointer, or maybe a constant.

-- 
Alain
-------------------------------------------------
"The way England treats her prisoners, she doesn't deserve to have any." 
        --Oscar Wilde

Post a reply to this message