Saturday 31 January 2009

Standard C Date & Time

asctimea textual version of the time
clockreturns the amount of time that the program has been running
ctimereturns a specifically formatted version of the time
difftimethe difference between two times
gmtimereturns a pointer to the current Greenwich Mean Time
localtimereturns a pointer to the current time
mktimereturns the calendar version of a given time
setlocalesets the current locale
strftimereturns individual elements of the date and time
timereturns the current calendar time of the system

Standard C Math

absabsolute value
acosarc cosine
asinarc sine
atanarc tangent
atan2arc tangent, using signs to determine quadrants
ceilthe smallest integer not less than a certain value
coscosine
coshhyperbolic cosine
divreturns the quotient and remainder of a division
expreturns “e” raised to a given power
fabsabsolute value for floating-point numbers
floorreturns the largest integer not greater than a given value
fmodreturns the remainder of a division
frexpdecomposes a number into scientific notation
labsabsolute value for long integers
ldexpcomputes a number in scientific notation
ldivreturns the quotient and remainder of a division, in long integer form
lognatural logarithm (to base e)
log10common logarithm (to base 10)
modfdecomposes a number into integer and fractional parts
powreturns a given number raised to another number
sinsine
sinhhyperbolic sine
sqrtsquare root
tantangent
tanhhyperbolic tangent

Monday 26 January 2009

Keywords in C++

C++'s keywords are a superset of C's keywords. Here is a list of all keywords of the language:

 and        const     float         operator static_cast    using
and_eq const_cast for or struct virtual
asm continue friend or_eq switch void
auto default goto private template volatile
bitand delete if protected this wchar_t
bitor do inline public throw while
bool double int register true xor
break dynamic_cast long reinterpret_cast try xor_eq
case else mutable return typedef
catch enum namespace short typeid
char explicit new signed typename
class extern not sizeof union
compl false not_eq static unsigned

Note the
operator keywords: and, and_eq, bitand, bitor, compl,
not, not_eq, or, or_eq, xor
and xor_eq are symbolic alternatives for,
respectively, &&, &=, &, |, ~, !, !=, ||, |=, ^ and ^=.

Friday 23 January 2009

Type Casting

onverting an expression of a given type into another type is known as type-casting. We have already seen some ways to type cast:

Implicit conversion

Implicit conversions do not require any operator. They are automatically performed when a value is copied to a compatible type. For example:
short a=2000;
int b;
b=a;

Here, the value of a has been promoted from short to int and we have not had to specify any type-casting operator. This is known as a standard conversion. Standard conversions affect fundamental data types, and allow conversions such as the conversions between numerical types (short to int, int to float, double to int...), to or from bool, and some pointer conversions. Some of these conversions may imply a loss of precision, which the compiler can signal with a warning. This can be avoided with an explicit conversion.

Implicit conversions also include constructor or operator conversions, which affect classes that include specific constructors or operator functions to perform conversions. For example:

class A {};
class B { public: B (A a) {} };

A a;
B b=a;

Here, a implicit conversion happened between objects of class A and class B, because B has a constructor that takes an object of class A as parameter. Therefore implicit conversions from A to B are allowed.

Explicit conversion

C++ is a strong-typed language. Many conversions, specially those that imply a different interpretation of the value, require an explicit conversion. We have already seen two notations for explicit type conversion: functional and c-like casting:
short a=2000;
int b;
b = (int) a; // c-like cast notation
b = int (a); // functional notation

The functionality of these explicit conversion operators is enough for most needs with fundamental data types. However, these operators can be applied indiscriminately on classes and pointers to classes, which can lead to code that while being syntactically correct can cause runtime errors. For example, the following code is syntactically correct:

// class type-casting
#include
using namespace std;

class CDummy {
float i,j;
};

class CAddition {
int x,y;
public:
CAddition (int a, int b) { x=a; y=b; }
int result() { return x+y;}
};

int main () {
CDummy d;
CAddition * padd;
padd = (CAddition*) &d;
cout <<>result();
return 0;
}
 

The program declares a pointer to CAddition, but then it assigns to it a reference to an object of another incompatible type using explicit type-casting:

padd = (CAddition*) &d;

Traditional explicit type-casting allows to convert any pointer into any other pointer type, independently of the types they point to. The subsequent call to member result will produce either a run-time error or a unexpected result.

In order to control these types of conversions between classes, we have four specific casting operators: dynamic_cast, reinterpret_cast, static_cast and const_cast. Their format is to follow the new type enclosed between angle-brackets (<>) and immediately after, the expression to be converted between parentheses.

dynamic_cast (expression)
reinterpret_cast (expression)
static_cast (expression)
const_cast (expression)

The traditional type-casting equivalents to these expressions would be:

(new_type) expression
new_type (expression)

but each one with its own special characteristics:

dynamic_cast

dynamic_cast can be used only with pointers and references to objects. Its purpose is to ensure that the result of the type conversion is a valid complete object of the requested class.

Therefore, dynamic_cast is always successful when we cast a class to one of its base classes:

class CBase { };
class CDerived: public CBase { };

CBase b; CBase* pb;
CDerived d; CDerived* pd;

pb = dynamic_cast(&d); // ok: derived-to-base
pd = dynamic_cast(&b); // wrong: base-to-derived

The second conversion in this piece of code would produce a compilation error since base-to-derived conversions are not allowed with dynamic_cast unless the base class is polymorphic.

When a class is polymorphic, dynamic_cast performs a special checking during runtime to ensure that the expression yields a valid complete object of the requested class:

// dynamic_cast
#include
#include
using namespace std;

class CBase { virtual void dummy() {} };
class CDerived: public CBase { int a; };

int main () {
try {
CBase * pba = new CDerived;
CBase * pbb = new CBase;
CDerived * pd;

pd = dynamic_cast(pba);
if (pd==0) cout << "Null pointer on first type-cast" << endl;

pd = dynamic_cast(pbb);
if (pd==0) cout << "Null pointer on second type-cast" << endl;

} catch (exception& e) {cout << "Exception: " << e.what();}
return 0;
}
Null pointer on second type-cast
Compatibility note: dynamic_cast requires the Run-Time Type Information (RTTI) to keep track of dynamic types. Some compilers support this feature as an option which is disabled by default. This must be enabled for runtime type checking using dynamic_cast to work properly.

The code tries to perform two dynamic casts from pointer objects of type CBase* (pba and pbb) to a pointer object of type CDerived*, but only the first one is successful. Notice their respective initializations:

CBase * pba = new CDerived;
CBase * pbb = new CBase;

Even though both are pointers of type CBase*, pba points to an object of type CDerived, while pbb points to an object of type CBase. Thus, when their respective type-castings are performed using dynamic_cast, pba is pointing to a full object of class CDerived, whereas pbb is pointing to an object of class CBase, which is an incomplete object of class CDerived.

When dynamic_cast cannot cast a pointer because it is not a complete object of the required class -as in the second conversion in the previous example- it returns a null pointer to indicate the failure. If dynamic_cast is used to convert to a reference type and the conversion is not possible, an exception of type bad_cast is thrown instead.

dynamic_cast can also cast null pointers even between pointers to unrelated classes, and can also cast pointers of any type to void pointers (void*).

static_cast

static_cast can perform conversions between pointers to related classes, not only from the derived class to its base, but also from a base class to its derived. This ensures that at least the classes are compatible if the proper object is converted, but no safety check is performed during runtime to check if the object being converted is in fact a full object of the destination type. Therefore, it is up to the programmer to ensure that the conversion is safe. On the other side, the overhead of the type-safety checks of dynamic_cast is avoided.
class CBase {};
class CDerived: public CBase {};
CBase * a = new CBase;
CDerived * b = static_cast(a);

This would be valid, although b would point to an incomplete object of the class and could lead to runtime errors if dereferenced.

static_cast can also be used to perform any other non-pointer conversion that could also be performed implicitly, like for example standard conversion between fundamental types:

double d=3.14159265;
int i = static_cast<int>(d);

Or any conversion between classes with explicit constructors or operator functions as described in "implicit conversions" above.

reinterpret_cast

reinterpret_cast converts any pointer type to any other pointer type, even of unrelated classes. The operation result is a simple binary copy of the value from one pointer to the other. All pointer conversions are allowed: neither the content pointed nor the pointer type itself is checked.

It can also cast pointers to or from integer types. The format in which this integer value represents a pointer is platform-specific. The only guarantee is that a pointer cast to an integer type large enough to fully contain it, is granted to be able to be cast back to a valid pointer.

The conversions that can be performed by reinterpret_cast but not by static_cast have no specific uses in C++ are low-level operations, whose interpretation results in code which is generally system-specific, and thus non-portable. For example:

class A {};
class B {};
A * a = new A;
B * b = reinterpret_cast(a);

This is valid C++ code, although it does not make much sense, since now we have a pointer that points to an object of an incompatible class, and thus dereferencing it is unsafe.

const_cast

This type of casting manipulates the constness of an object, either to be set or to be removed. For example, in order to pass a const argument to a function that expects a non-constant parameter:
// const_cast
#include
using namespace std;

void print (char * str)
{
cout << str << endl;
}

int main () {
const char * c = "sample text";
print ( const_cast<char *> (c) );
return 0;
}
sample text

typeid

typeid allows to check the type of an expression:

typeid (expression)

This operator returns a reference to a constant object of type type_info that is defined in the standard header file . This returned value can be compared with another one using operators == and != or can serve to obtain a null-terminated character sequence representing the data type or class name by using its name() member.

// typeid
#include
#include
using namespace std;

int main () {
int * a,b;
a=0; b=0;
if (typeid(a) != typeid(b))
{
cout << "a and b are of different types:\n";
cout << "a is: " << typeid(a).name() << '\n';
cout << "b is: " << typeid(b).name() << '\n';
}
return 0;
}
a and b are of different types:
a is: int *
b is: int

When typeid is applied to classes typeid uses the RTTI to keep track of the type of dynamic objects. When typeid is applied to an expression whose type is a polymorphic class, the result is the type of the most derived complete object:

// typeid, polymorphic class
#include
#include
#include
using namespace std;

class CBase { virtual void f(){} };
class CDerived : public CBase {};

int main () {
try {
CBase* a = new CBase;
CBase* b = new CDerived;
cout << "a is: " << typeid(a).name() << '\n';
cout << "b is: " << typeid(b).name() << '\n';
cout << "*a is: " << typeid(*a).name() << '\n';
cout << "*b is: " << typeid(*b).name() << '\n';
} catch (exception& e) { cout << "Exception: " << e.what() << endl; }
return 0;
}
a is: class CBase *
b is: class CBase *
*a is: class CBase
*b is: class CDerived

Notice how the type that typeid considers for pointers is the pointer type itself (both a and b are of type class CBase *). However, when typeid is applied to objects (like *a and *b) typeid yields their dynamic type (i.e. the type of their most derived complete object).

If the type typeid evaluates is a pointer preceded by the dereference operator (*), and this pointer has a null value, typeid throws a bad_typeid exception.

Exceptions

Exceptions provide a way to react to exceptional circumstances (like runtime errors) in our program by transferring control to special functions called handlers.

To catch exceptions we must place a portion of code under exception inspection. This is done by enclosing that portion of code in a try block. When an exceptional circumstance arises within that block, an exception is thrown that transfers the control to the exception handler. If no exception is thrown, the code continues normally and all handlers are ignored.

A exception is thrown by using the throw keyword from inside the try block. Exception handlers are declared with the keyword catch, which must be placed immediately after the try block:

// exceptions
#include
using namespace std;

int main () {
try
{
throw 20;
}
catch (int e)
{
cout << "An exception occurred. Exception Nr. " << e << endl;
}
return 0;
}
An exception occurred. Exception Nr. 20

The code under exception handling is enclosed in a try block. In this example this code simply throws an exception:

throw 20;

A throw expression accepts one parameter (in this case the integer value 20), which is passed as an argument to the exception handler.

The exception handler is declared with the catch keyword. As you can see, it follows immediately the closing brace of the try block. The catch format is similar to a regular function that always has at least one parameter. The type of this parameter is very important, since the type of the argument passed by the throw expression is checked against it, and only in the case they match, the exception is caught.

We can chain multiple handlers (catch expressions), each one with a different parameter type. Only the handler that matches its type with the argument specified in the throw statement is executed.

If we use an ellipsis (...) as the parameter of catch, that handler will catch any exception no matter what the type of the throw exception is. This can be used as a default handler that catches all exceptions not caught by other handlers if it is specified at last:

try {
// code here
}
catch (int param) { cout << "int exception"; }
catch (char param) { cout << "char exception"; }
catch (...) { cout << "default exception"; }

In this case the last handler would catch any exception thrown with any parameter that is neither an int nor a char.

After an exception has been handled the program execution resumes after the try-catch block, not after the throw statement!.

It is also possible to nest try-catch blocks within more external try blocks. In these cases, we have the possibility that an internal catch block forwards the exception to its external level. This is done with the expression throw; with no arguments. For example:

try {
try {
// code here
}
catch (int n) {
throw;
}
}
catch (...) {
cout << "Exception occurred";
}

Exception specifications

When declaring a function we can limit the exception type it might directly or indirectly throw by appending a throw suffix to the function declaration:

float myfunction (char param) throw (int);

This declares a function called myfunction which takes one agument of type char and returns an element of type float. The only exception that this function might throw is an exception of type int. If it throws an exception with a different type, either directly or indirectly, it cannot be caught by a regular int-type handler.

If this throw specifier is left empty with no type, this means the function is not allowed to throw exceptions. Functions with no throw specifier (regular functions) are allowed to throw exceptions with any type:

int myfunction (int param) throw(); // no exceptions allowed
int myfunction (int param); // all exceptions allowed

Standard exceptions

The C++ Standard library provides a base class specifically designed to declare objects to be thrown as exceptions. It is called exception and is defined in the header file under the namespace std. This class has the usual default and copy constructors, operators and destructors, plus an additional virtual member function called what that returns a null-terminated character sequence (char *) and that can be overwritten in derived classes to contain some sort of description of the exception.
// standard exceptions
#include
#include
using namespace std;

class myexception: public exception
{
virtual const char* what() const throw()
{
return "My exception happened";
}
} myex;

int main () {
try
{
throw myex;
}
catch (exception& e)
{
cout << e.what() << endl;
}
return 0;
}
My exception happened.

We have placed a handler that catches exception objects by reference (notice the ampersand & after the type), therefore this catches also classes derived from exception, like our myex object of class myexception.

All exceptions thrown by components of the C++ Standard library throw exceptions derived from this std::exception class. These are:

exceptiondescription
bad_allocthrown by new on allocation failure
bad_castthrown by dynamic_cast when fails with a referenced type
bad_exceptionthrown when an exception type doesn't match any catch
bad_typeidthrown by typeid
ios_base::failurethrown by functions in the iostream library

For example, if we use the operator new and the memory cannot be allocated, an exception of type bad_alloc is thrown:

try
{
int * myarray= new int[1000];
}
catch (bad_alloc&)
{
cout << "Error allocating memory." << endl;
}

It is recommended to include all dynamic memory allocations within a try block that catches this type of exception to perform a clean action instead of an abnormal program termination, which is what happens when this type of exception is thrown and not caught. If you want to force a bad_alloc exception to see it in action, you can try to allocate a huge array; On my system, trying to allocate 1 billion ints threw a bad_alloc exception.

Because bad_alloc is derived from the standard base class exception, we can handle that same exception by catching references to the exception class:

// bad_alloc standard exception
#include
#include
using namespace std;

int main () {
try
{
int* myarray= new int[1000];
}
catch (exception& e)
{
cout << "Standard exception: " << e.what() << endl;
}
return 0;
}
 

Thursday 22 January 2009

C and C++ are CRAZY!

I’ve learned a lot of crazy things about C and C++ in the last few years, as far as parsing goes. The one that’s always blown me away the most is that parsing C++ is undecidable: you can’t properly parse C++ without doing template instantiation, but template instantiation is turing-complete.

But every time I think I’ve gotten to the point where C and C++ can’t faze me anymore, I find something new. Like this, from the Wikipedia article about operator precedence in C and C++:

The binding of operators in C and C++ is specified (in the corresponding Standards) by a factored language grammar, rather than a precedence table. This creates some subtle conflicts. For example, in C, the syntax for a conditional expression is:

logical-OR-expression ? expression :
conditional-expression

while in C++ it is:

logical-or-expression ? expression :
assignment-expression

Hence, the expression:

e = a ? b : c = d

is parsed differently in the two languages. In C, this expression is parsed as:

e = ((a ? b : c) = d)

which is a semantic error, since the result of a conditional-expression is not an lvalue. In C++, it is parsed as:

e = (a ? b : (c = d))

which is a valid expression.

WHAT?? I had to try this out and determine whether it was true or some crazy Wikipedia anonymous editor who was trying to drive me mad. So I wrote the simple test program:

int main() {
int e = 1, a = 2, b = 3, c = 4, d = 5;
e = a ? b : c = d;
return e;
}

…and attempted to compile it first with gcc as a .c, then with g++ as a .cc, and sure enough:

$ gcc -o /tmp/test /tmp/test.c
/tmp/test.c: In function 'main':
/tmp/test.c:4: error: lvalue required as left operand of assignment
/tmp/test.c:4: error: expected ';' before 'return'
$ g++ -o /tmp/test /tmp/test.cc
$

The world is insane. Luckily Gazelle will be the sword in your right hand, your weapon against a world that conspires against your sanity.

Incidentally, it’s more and more clear that C++ is not a superset of C. Though it’s true enough that most people using the language don’t have to care, for language implementors the differences are significant.

Sunday 18 January 2009

Rounding Algorithms

There are a zillion different ways to round floating point values to integers. C and C++ provide a couple basic ones in or .
There are two general categories of rounding algorithm: those that are symmetric about zero and those that are biased in some way.

Biased Rounding
A bias is a mathematical notion used in statistics to indicate that samples are not exactly representative of their true values; they are skewed in one way or another.

For example, the floor() function is biased towards negative infinity, because it always chooses the lower integer number --that is, it always chooses the number closer to negative infinity.

floor( 7.5 ) --> 7
floor( -7.5 ) --> -8


Suppose your local big city and wanted to know how fast people are driving on a particular freeway. The first step is to gather the exact speeds that individual drivers are going, and the second would be to convert all the individual values into a single value that would represent the normal rate of speed. For simplicity here, we will just use the average value.

Let us say that the equipment which samples a motorist's speed is far more accurate than the computer's ability to store it. (This is actually not uncommon.) Again, for simplicity, we will say that the computer stores the speed as integers.

With a sampling of twelve motorists, we get the following speeds (in miles per hour)

49.087 57.901 28.500 46.738 51.270 53.096
44.795 47.218 46.347 45.989 47.582 50.563

A quick calculation shows that the average speed is 47.424 mph.

If the city were to simply use the floor() function to convert these to integers, it would get

49 57 28 46 51 53
44 47 46 45 47 50

which averages to 46.916 --> 46 mph (remember, integer arithmetic!)

Either way, the sampling is off by about a whole mile per hour. I don't think that the city would actually care about a single mile per hour, but this does illustrate the bias, or tendancy of the floor() function, to make the numbers closer to negative infinity, thuse skewing the data to an inaccurate number.

This was just a simple example that came off the top of my head, but in many sciences and statistical surveys, that difference can mean quite a lot. Suppose that the Apollo missed the moon by 1%? Suppose a pharmaceutical company put too much iron in a daily vitamin pill by 1%? Suppose a construction firm miscalculated the stresses a bridge can take by 1%? In all these scenarios the results would prove deadly. One percent is a lot.


Symmetric Rounding
A special case of bias is centered about zero. Let us fix the floor() function to tend towards zero.
1
2
3
4
5
6
7
 

double floor0( double value )
  {
  if (value < 0.0)
  return ceil( value );
  else
  return floor( value );
  }


Now, the absolute value of the result will always be the same:

floor0( -7.7 ) --> -7 floor0( 7.7 ) --> 7
floor0( -7.5 ) --> -7 floor0( 7.5 ) --> 7
floor0( -7.3 ) --> -7 floor0( 7.3 ) --> 7

Enough about that.


Unbiased Rounding
So, how do we handle these biases? By adding some rule that accounts for it.

Let us apply knowledge we all learned in gradeschool: In arithmetic rounding we round up if the next digit is 5 or more, and if it less than 5 we round down. We write ourselves a little function to do just that:
1
2
3
4
 

double round( double value )
  {
  return floor( value + 0.5 );
  }


The problem is that this is still biased. We have actually reversed the bias of floor() from negative infinity to positive infinity, because we always choose to round up when exactly halfway between two values:

round( 10.3 ) --> 10
round( 10.5 ) --> 11
round( 10.7 ) --> 11

You can actually see the bias in the above table: the result tends towards 11 and away from 10.

This brings us to the trick: which way do we round when exactly halfway between two values?

One very popular method is variously called "bankers rounding", "round to even", "convergent rounding", and even "unbiased rounding", to name a few. It works by skewing the bias itself.

Given a number exactly halfway between two values, round to the even value (zero is considered even here).

round( 1.7 ) --> 2 round( 2.7 ) --> 3
round( 1.5 ) --> 2 round( 2.5 ) --> 2
round( 1.3 ) --> 1 round( 2.3 ) --> 2

For random data this is very convenient. Bankers like it because money deposited and withdrawn is random. (There are trends, mind you, but you cannot predict exactly how much will be deposited and withdrawn.) The important point is that the bankers rounding is still biased if the data is biased. It is only unbiased with random data.

One solution is called "alternate rounding". It works by simply choosing to bias up or down every other time.

round( 1.5 ) --> 2
round( 1.5 ) --> 1
round( 1.5 ) --> 2
round( 1.5 ) --> 1
etc

This is not always useful though.

The only way to eliminate all bias is to use a random bias... This, of course, is impossible to generate in your typical PC, but it still goes toward solving the problem quite nicely.

If the sample is exactly halfway between two integers, it chooses one or the other randomly.

Of course, the Achilles heel of this method is the random number generator you use. The default pseudorandom generator for C and C++ is not that great. The Mersenne Twister is by far the most popular high-quality pseudorandom number generator, but it is non-trivial to implement so I will not include it below.

Anyway, what follows is a convenient, simple library you are free to use. I'll even permit you to cannabalize it at will (since the algorithms are so obvious...)

I may update it sometime in the future if I can figure out a way around the default epsilon issue. Feel free to make suggestions for improvements.

:-)

Friday 16 January 2009

Review of Mastering C++

Mastering C++ is a book written by K. R. Venugopal, T Ravishankar and Rajkumar. The book teaches the computer language C++ from the scratch to the professional level in a very friendly approach to the learning of the otherwise very difficult language.

First published in 1997, the book is recommended by most of the programmers. Basically written with C programmers in mind, this book caters to novices as well.

My brother advised me to read this book as I was desperately trying to learn the language but was unable to do so. At the first sight of the book, I thought,” This book can’t help anyone. This is just another book for engineers and is full of technical jargon.”

Almost two years later I learned ‘C’ language from the book “Let Us C” by Yashwant Kanetkar.
That book helped me clear the basic concepts of programming and get some technical jargon of computers, giving me the break I needed.

I learned the concepts of OOPs from the reference books of NIIT. After that, I was ready to learn C++ in detail. I started from chapter-one which helped me get acquainted with thinking in terms of OOPs. And the following chapters till chapter nine taught me the basics of C++ (non-OOPs) and from 10 to 19 the OOPs side of the language. Chapter 20 was based on the management of software projects.

So after learning it, I decided to write some programs and got disappointed because I could write only console based programs, as standard C++ does not specify the platform independent GUI programming.

Though Mastering C++ is good for learning, to gain expertise in language one must not rely on this book alone. Specialized books in the field of data structures, network programming, games development etc should also be read and kept as reference.

But as far as the question of the language is concerned, this book can be trusted as it teaches the language and its constructs in details. To become expert in any field the base should be firm. And this book does the job.

Best of luck for your adventures in C++.

Thursday 15 January 2009

Two Reasons Why I Prefer C to Java

There are two specific reasons why I prefer C++ to Java: operator overloading and pointers. I strongly believe that these are related to the fact that I started learning C++ first, but I still find them critical to my preference for C++.

Operator overloading, for me, is a critical feature in C++ for providing intuitive code. When creating a mathematical class, such as BigInt, I want to be able to work with variables of that type the same way I work with variables of type int. If + is a meaningful operation on a class, I want to be able to use it. Moreover, I don't want to have to wrap my built-in type int in a class with .add(), .minus(), etc methods so that I can create a template for building rational numbers. I realize that this is a side-effect of my math background, but I believe that I should be able to write math with math symbols wherever possible.

The other irritation I have with Java is that it weakened pointers as found in languages like C++ and Pascal to what it calls a "reference". Anyone who is familiar with pointers in other languages will recognize that Java is using the pointer concept, but weakening it to make the language safer. I realize that this is a deliberate design decision, but it is a decision that irritates me in its implementation. It is both less function than C++ pointers, and more powerful in that it handles garbage collection. For me, losing pointer arithmetic for garbage collection is a bad trade
.

C++ Sets

The C++ Set is an associative STL container that contains a sorted set of unique objects.

Constructorsdefault methods to allocate, copy, and deallocate sets
Operatorsassign and compare sets
beginreturns an iterator to the beginning of the set
clearremoves all elements from the set
countreturns the number of elements matching a certain key
emptytrue if the set has no elements
endreturns an iterator just past the last element of a set
equal_rangereturns iterators to the first and just past the last elements matching a specific key
eraseremoves elements from a set
findreturns an iterator to specific elements
insertinsert items into a set
key_compreturns the function that compares keys
lower_boundreturns an iterator to the first element greater than or equal to a certain value
max_sizereturns the maximum number of elements that the set can hold
rbeginreturns a reverse_iterator to the end of the set
rendreturns a reverse_iterator to the beginning of the set
sizereturns the number of items in the set
swapswap the contents of this set with another
upper_boundreturns an iterator to the first element greater than a certain value
value_compreturns the function that compares values

Tuesday 13 January 2009

Insertion Sort Implementation in C++ [Sorting Algorithms]

Insertion Sort is sorting algorithm similar to Bubble Sort simply because they are basic sorting algorithms. The difference, is that Insertion Sort iterates through the data structure selects an element and inserts it into its correct location until no elements are left to sort.

Insertion Sort Visual Example

26 5 12 -6




First Iteration
The element 5 in position 1 is inserted into its appropriate location (position 0).

5 26 12 -6

26 vs 5 equals SWAP

Second Iteration
The element 26 in position 2 is inserted into its appropriate location (position 1).

5 12 26 -6

26 > 12 equals SWAP

Third Iteration
The element 26 in position 3 is in its appropriate position since it is greater than all the elements before it.

5 12 26 -6

12 <>

Fourth Iteration
The element -6 in position 3 is inserted into its appropriate position (position 0).

5 12 -6 26

26 > -6 SWAP

5 -6 12 26

12 > -6 SWAP

-6 5 12 26

5 > -6 SWAP

Saturday 10 January 2009

Polymorphism

Before getting into this section, it is recommended that you have a proper understanding of pointers and class inheritance. If any of the following statements seem strange to you, you should review the indicated sections:

Statement:
Explained in:
int a::b(c) {};
Classes
a->b
Data Structures
class a: public b;
Friendship and inheritance

Pointers to base class

One of the key features of derived classes is that a pointer to a derived class is type-compatible with a pointer to its base class. Polymorphism is the art of taking advantage of this simple but powerful and versatile feature, that brings Object Oriented Methodologies to its full potential.

We are going to start by rewriting our program about the rectangle and the triangle of the previous section taking into consideration this pointer compatibility property:

// pointers to base class
#include
using namespace std;

class CPolygon {
protected:
int width, height;
public:
void set_values (int a, int b)
{ width=a; height=b; }
};

class CRectangle: public CPolygon {
public:
int area ()
{ return (width * height); }
};

class CTriangle: public CPolygon {
public:
int area ()
{ return (width * height / 2); }
};

int main () {
CRectangle rect;
CTriangle trgl;
CPolygon * ppoly1 = ▭
CPolygon * ppoly2 = &trgl;
ppoly1->set_values (4,5);
ppoly2->set_values (4,5);
cout << rect.area() << endl;
cout << trgl.area() << endl;
return 0;
}
20
10

In function main, we create two pointers that point to objects of class CPolygon (ppoly1 and ppoly2). Then we assign references to rect and trgl to these pointers, and because both are objects of classes derived from CPolygon, both are valid assignations.

The only limitation in using *ppoly1 and *ppoly2 instead of rect and trgl is that both *ppoly1 and *ppoly2 are of type CPolygon* and therefore we can only use these pointers to refer to the members that CRectangle and CTriangle inherit from CPolygon. For that reason when we call the area() members at the end of the program we have had to use directly the objects rect and trgl instead of the pointers *ppoly1 and *ppoly2.

In order to use area() with the pointers to class CPolygon, this member should also have been declared in the class CPolygon, and not only in its derived classes, but the problem is that CRectangle and CTriangle implement different versions of area, therefore we cannot implement it in the base class. This is when virtual members become handy:

Virtual members

A member of a class that can be redefined in its derived classes is known as a virtual member. In order to declare a member of a class as virtual, we must precede its declaration with the keyword virtual:
// virtual members
#include
using namespace std;

class CPolygon {
protected:
int width, height;
public:
void set_values (int a, int b)
{ width=a; height=b; }
virtual int area ()
{ return (0); }
};

class CRectangle: public CPolygon {
public:
int area ()
{ return (width * height); }
};

class CTriangle: public CPolygon {
public:
int area ()
{ return (width * height / 2); }
};

int main () {
CRectangle rect;
CTriangle trgl;
CPolygon poly;
CPolygon * ppoly1 = ▭
CPolygon * ppoly2 = &trgl;
CPolygon * ppoly3 = &poly;
ppoly1->set_values (4,5);
ppoly2->set_values (4,5);
ppoly3->set_values (4,5);
cout <<>area() << endl;
cout <<>area() << endl;
cout <<>area() << endl;
return 0;
}
20
10
0

Now the three classes (CPolygon, CRectangle and CTriangle) have all the same members: width, height, set_values() and area().

The member function area() has been declared as virtual in the base class because it is later redefined in each derived class. You can verify if you want that if you remove this virtual keyword from the declaration of area() within CPolygon, and then you run the program the result will be 0 for the three polygons instead of 20, 10 and 0. That is because instead of calling the corresponding area() function for each object (CRectangle::area(), CTriangle::area() and CPolygon::area(), respectively), CPolygon::area() will be called in all cases since the calls are via a pointer whose type is CPolygon*.

Therefore, what the virtual keyword does is to allow a member of a derived class with the same name as one in the base class to be appropriately called from a pointer, and more precisely when the type of the pointer is a pointer to the base class but is pointing to an object of the derived class, as in the above example.

A class that declares or inherits a virtual function is called a polymorphic class.

Note that despite of its virtuality, we have also been able to declare an object of type CPolygon and to call its own area() function, which always returns 0.

Abstract base classes

Abstract base classes are something very similar to our CPolygon class of our previous example. The only difference is that in our previous example we have defined a valid area() function with a minimal functionality for objects that were of class CPolygon (like the object poly), whereas in an abstract base classes we could leave that area() member function without implementation at all. This is done by appending =0 (equal to zero) to the function declaration.

An abstract base CPolygon class could look like this:

// abstract class CPolygon
class CPolygon {
protected:
int width, height;
public:
void set_values (int a, int b)
{ width=a; height=b; }
virtual int area () =0;
};

Notice how we appended =0 to virtual int area () instead of specifying an implementation for the function. This type of function is called a pure virtual function, and all classes that contain at least one pure virtual function are abstract base classes.

The main difference between an abstract base class and a regular polymorphic class is that because in abstract base classes at least one of its members lacks implementation we cannot create instances (objects) of it.

But a class that cannot instantiate objects is not totally useless. We can create pointers to it and take advantage of all its polymorphic abilities. Therefore a declaration like:

CPolygon poly;

would not be valid for the abstract base class we have just declared, because tries to instantiate an object. Nevertheless, the following pointers:

CPolygon * ppoly1;
CPolygon * ppoly2;

would be perfectly valid.

This is so for as long as CPolygon includes a pure virtual function and therefore it's an abstract base class. However, pointers to this abstract base class can be used to point to objects of derived classes.

Here you have the complete example:

// abstract base class
#include
using namespace std;

class CPolygon {
protected:
int width, height;
public:
void set_values (int a, int b)
{ width=a; height=b; }
virtual int area (void) =0;
};

class CRectangle: public CPolygon {
public:
int area (void)
{ return (width * height); }
};

class CTriangle: public CPolygon {
public:
int area (void)
{ return (width * height / 2); }
};

int main () {
CRectangle rect;
CTriangle trgl;
CPolygon * ppoly1 = ▭
CPolygon * ppoly2 = &trgl;
ppoly1->set_values (4,5);
ppoly2->set_values (4,5);
cout <<>area() << endl;
cout <<>area() << endl;
return 0;
}
20
10

If you review the program you will notice that we refer to objects of different but related classes using a unique type of pointer (CPolygon*). This can be tremendously useful. For example, now we can create a function member of the abstract base class CPolygon that is able to print on screen the result of the area() function even though CPolygon itself has no implementation for this function:

// pure virtual members can be called
// from the abstract base class
#include
using namespace std;

class CPolygon {
protected:
int width, height;
public:
void set_values (int a, int b)
{ width=a; height=b; }
virtual int area (void) =0;
void printarea (void)
{ cout << this->area() << endl; }
};

class CRectangle: public CPolygon {
public:
int area (void)
{ return (width * height); }
};

class CTriangle: public CPolygon {
public:
int area (void)
{ return (width * height / 2); }
};

int main () {
CRectangle rect;
CTriangle trgl;
CPolygon * ppoly1 = ▭
CPolygon * ppoly2 = &trgl;
ppoly1->set_values (4,5);
ppoly2->set_values (4,5);
ppoly1->printarea();
ppoly2->printarea();
return 0;
}
20
10

Virtual members and abstract classes grant C++ the polymorphic characteristics that make object-oriented programming such a useful instrument in big projects. Of course, we have seen very simple uses of these features, but these features can be applied to arrays of objects or dynamically allocated objects.

Let's end with the same example again, but this time with objects that are dynamically allocated:

// dynamic allocation and polymorphism
#include
using namespace std;

class CPolygon {
protected:
int width, height;
public:
void set_values (int a, int b)
{ width=a; height=b; }
virtual int area (void) =0;
void printarea (void)
{ cout << this->area() << endl; }
};

class CRectangle: public CPolygon {
public:
int area (void)
{ return (width * height); }
};

class CTriangle: public CPolygon {
public:
int area (void)
{ return (width * height / 2); }
};

int main () {
CPolygon * ppoly1 = new CRectangle;
CPolygon * ppoly2 = new CTriangle;
ppoly1->set_values (4,5);
ppoly2->set_values (4,5);
ppoly1->printarea();
ppoly2->printarea();
delete ppoly1;
delete ppoly2;
return 0;
}
20
10

Notice that the ppoly pointers:

CPolygon * ppoly1 = new CRectangle;
CPolygon * ppoly2 = new CTriangle;
are declared being of type pointer to CPolygon but the objects dynamically allocated have been declared having the derived class type directly.

Thursday 8 January 2009

Handling a Common strcmp() Case

In this section of the newsletter we will present some practical performance tips for improving code speed and reducing memory usage. Some of these tips will be useful only for C++ code and some will be more general and applicable to C or other languages.

As a first example, consider an application using C-style strings and functions such as strcmp(). A recent experience with this sort of application involved a function that does word stemming, that is, takes words such as "motoring" and reduces them to their root stem, in this case "motor".

In profiling this function, it was observed that much of the overall time was being spent in the strcmp() function. For the C++ compiler in question (Borland 3.1), this function is written in assembly language and is quite fast, and attempts to speed it up by unrolling the equivalent code locally at the point of function call will typically result in slowing things down.

But it's still the case that calling a function, even one implemented in assembly language, has some overhead, which comes from saving registers, manipulating stack frames, actual transfer of control, and so on. So it might be worth trying to exploit a common case -- the case where you can determine the relationship of the strings by looking only at the first character.

So we might use an inline function in C++ to encapsulate this logic:

inline int local_strcmp(const char* s, const char* t)
{
return (*s != *t ? *s - *t : strcmp(s, t));
}

If the first characters of each string do not match, there's no need to go further by calling strcmp(); we already know the answer.

Another way to implement the same idea is via a C macro:

#define local_strcmp(s, t) ((s)[0] != (t)[0] ? (s)[0] - (t)[0] : \
strcmp((s), (t)))

This approach has a couple of disadvantages, however. Macros are hard to get right because of the need to parenthesize arguments so as to avoid subtly wrong semantics. Writing local_strcmp() as a real function is more natural.

And macros are less likely to be understood by development tools such as browsers or debuggers. Inline functions are also a source of problems for such tools, but they at least are part of the C++ language proper, and many C++ compilers have a way of disabling inlining to help address this problem.

How much speedup is this approach good for? In the word stemming program, for input of about 65000 words, the times in seconds were:

strcmp() 9.7

inline local_strcmp() 7.5

#define local_strcmp() 7.5

or a savings of about 23%. Obviously, this figure will vary with the compiler and the application.

This particular speedup is achieved by exploiting a common case -- the case where the first letters of two strings are different. For applications involving English words, this is often a good assumption. For some other types of strings, it may not be.

Character Types and Arrays

There are a couple of differences in the way that ANSI C and C++ treat character constants and arrays of characters. One of these has to do with the type of a character constant. For example:

#include

int main()
{
printf("%d\n", sizeof('x'));

return 0;
}

If this program is compiled as ANSI C, then the value printed will be sizeof(int), typically 2 on PCs and 4 on workstations. If the program is treated as C++, then the printed value will be sizeof(char), defined by the draft ANSI/ISO standard to be 1. So the type of a char constant in C is int, whereas the type in C++ is char. Note that it's possible to have sizeof(char) == sizeof(int) for a given machine architecture, though not very likely.

Another difference is illustrated by this example:

#include

char buf[5] = "abcde";

int main()
{
printf("%s\n", buf);

return 0;
}

This is legal C, but invalid C++. The string literal requires a trailing \0 terminator, and there is not enough room in the character array for it. This is valid C, but you access the resulting array at your own risk. Without the terminating null character, a function like printf() may not work correctly, and the program may not even terminate.

QUEUES

There's a huge crowd at your local grocery store. There are too many people
trying to buy their respective items and the Shopkeeper doesnt know from where
to start. Everyone wants their job done quickly and the shopkeeper needs an
efficient method to solve this problem. What does he do? He introduces a Queue
System based on the First Come, First Serve System. The Last Person trying to
buy an item stands behind the last person at the END of the queue. The
Shopkeeper however is present at the FRONT end of the queue. He gives the item
to the person in FRONT of the queue and after the transaction is done, the
person in FRONT of the Queue Leaves. Then the person second in queue becomes the
First person in the Queue.

Do you get the point here? A Queue is similar to a stack except that addition of
data is done in the BACK end and deletion of data is done in the FRONT.
Writing a queue is a lot harder than writing a stack. We maintain 2 Integers in
our Queue Data Structure, one signifying the FRONT end of the Queue and the
other referring to the BACK end of the Queue.

Let us use the same coding style as we used for the Stack. We first initialise
both the ends to -1 to indicate an empty queue. When Data is added to the queue
both ends get respective postive values. When New Data is added, the back End is
incremented and when data is deleted the front end is decremented. This works
fine but it has a major drawback. What if the Maximum capacity of the Queue is 5
Items. Suppose the User has added 4 items, deleted 3 items and adds 2 again. The
Stack wont permit him to add the last half of the data as it will report that
the stack is full. The Reason is that we are blindly incrementing/decrementing
each end depending on addition/deletion not realising that both the ends are
related to each other. I leave this as an excercise for you to answer. Why will
our proposed Stack report the Stack as Full even though it's actually vacant?
So we need another approach.In this method we focus more on the data than on the
addition end and the deletion end.

What we now use is the grocery store example again. Suppose there are 5 items in
a queue and we want to delete them one by one. We first delete the first data
item pointed by the deletion end. Then we shift all data one step ahead so that
the second item becomes the first, third item becomes second and so on...
Another method would be to maintain the difference between the two ends which is
not practical. Hence we stick to our previous method. It might be slow in Big
Queues, but it certainly works great. Here's the code.

cpp

#include

using namespace std;

#define MAX 5 // MAXIMUM CONTENTS IN QUEUE


class queue
{
private:
int t[MAX];
int al; // Addition End
int dl; // Deletion End

public:
queue
()
{
dl
=-1;
al
=-1;
}

void del()
{
int tmp;
if(dl==-1)
{
cout
<<"Queue is Empty";
}
else
{
for(int j=0;j<=al;j++)
{
if((j+1)<=al)
{
tmp
=t[j+1];
t
[j]=tmp;
}
else
{
al
--;

if(al==-1)
dl
=-1;
else
dl
=0;
}
}
}
}

void add(int item)
{
if(dl==-1 && al==-1)
{
dl
++;
al
++;
}
else
{
al
++;
if(al==MAX)
{
cout
<<"Queue is Full\n";
al
--;
return;
}
}
t
[al]=item;

}

void display()
{
if(dl!=-1)
{
for(int iter=0 ; iter<=al ; iter++)
cout
<<t[iter]<<" ";
}
else
cout
<<"EMPTY";
}

};

int main()
{
queue a
;
int data[5]={32,23,45,99,24};

cout
<<"Queue before adding Elements: ";
a
.display();
cout
<<endl<<endl;

for(int iter = 0 ; iter < 5 ; iter++)
{
a
.add(data[iter]);
cout
<<"Addition Number : "<<(iter+1)<<" : ";
a
.display();
cout
<<endl;
}
cout
<<endl;
cout
<<"Queue after adding Elements: ";
a
.display();
cout
<<endl<<endl;

for(iter=0 ; iter < 5 ; iter++)
{
a
.del();
cout
<<"Deletion Number : "<<(iter+1)<<" : ";
a
.display();
cout
<<endl;
}
return 0;
}


OUTPUT:
Queue before adding Elements: EMPTY

Addition Number : 1 : 32
Addition Number : 2 : 32 23
Addition Number : 3 : 32 23 45
Addition Number : 4 : 32 23 45 99
Addition Number : 5 : 32 23 45 99 24

Queue after adding Elements: 32 23 45 99 24

Deletion Number : 1 : 23 45 99 24
Deletion Number : 2 : 45 99 24
Deletion Number : 3 : 99 24
Deletion Number : 4 : 24
Deletion Number : 5 : EMPTY



As you can clearly see through the output of this program that addition is
always done at the end of the queue while deletion is done from the front end of
the queue. Once again the Maximum limit of Data will be extended later when we
learn Linked Lists.

A Memory Game

This is a simple game which displays 25 push buttons in the client area. On top of each button a bitmap of a different animal is loaded. When you play the game the computer on its own depresses a sequence of buttons at random. As each button is depressed, the color of the animal changes to gray and the button goes in. Both these things are done to give the user a feeling that a button has indeed been depressed. As the computer depresses a sequence of buttons the user is supposed to memorize the sequence. Once the computer has done its job the user is then supposed to depress the buttons by clicking the left mouse button in the same sequence as done by computer. If the user's sequence matches the computer's sequence then a message box appears telling the user of his success and then the computer proceeds to depress another sequence of buttons. This time it depresses one more button than what it did last time around. The user is again supposed to repeat the sequence by clicking the push buttons with the mouse. This goes on till the time the users' sequence matches the computer's sequence. In case of a mismatch the game ends. The following figure shows the game window.


As seen from the figure, there are three items in the menu. Selecting the first menu item results into starting a fresh game. Using the 'Sound' menu item it can be decided whether we want a sound to accompany the depressing of a button. The third menu item is the usual 'About' menu item. The only additional feature in this program's 'About' menu item is that it displays the application icon in the 'About' dialog box. This article explains how to create the memory game. This project has an application class, myapp, and a frame window class, myframe. During execution the real action begins when the control reaches the myframe constructor to create the window. Since we want a user-defined icon and a stock brush of light gray color, we have called the AfxRegisterWndClass( ) function to register the window class with these properties. Once registered, we have created a window based on this class by calling CFrameWnd::Create( ). Once the window is created a WM_CREATE message gets posted into the message queue. In response to this message the function myframe::OnCreate( ) gets called. In this function we have created 25 buttons and loaded 25 different bitmaps on them. b[ ] is an array of CBitmapButton objects. The class CBitmapButton encapsulates owner-drawn push buttons that display pictures in place of text. In the OnCreate( ) handler we have called CBitmapButton::Create( ) to create each button. The first parameter passed to Create( ) is NULL since we don't want any text to be displayed on the button. The window style WS_CHILD indicates that each button is a child of the frame window. The style WS_VISIBLE ensures that each button is shown automatically when its parent (the frame window) gets displayed. The style BS_OWNERDRAW must be included to indicate that the button is owner-drawn. The CRect passed to Create( ) indicates the size of the button, whereas, the this pointer passed to it is the pointer to the parent window object. The last parameter passed to Create( ) stands for the id given to each button. Once the 25 buttons are created, a pair of bitmaps is loaded for each button. These bitmaps must be created using the Resource Editor. When drawing the bitmaps for a CBitmapButton-style button you should follow a few simple rules to ensure that the button's appearance is consistent with that of normal push buttons. Each bitmap is of size 50 * 50 pixels. It is important that both the bitmaps are of same size. For best results, the button's face and edges should be drawn with the colors. Start with the up bitmap, and then create the down bitmap by reversing the border and moving the image on the face of the button right and down by one pixel. This gives the illusion of the button going down when it is clicked. Note that it is not necessary that you should strictly style your buttons as per these guidelines and you are free to decide your own style. However, the users are likely to judge your application more favourably if the appearance and behaviour of their controls are similar to that of the controls in other Windows applications. In fact a CBitmapButton can use as many as four bitmapped images: one depicting the button in its normal, undepressed, state; a second depicting the button when it is depressed; a third depicting the button when it is undepressed and has the input focus; and a fourth depicting the button when it is disabled. At a minimum, you should supply "up" and "down" bitmaps showing the button in its normal and depressed states. When the button is clicked, the framework redraws the button using the down bitmap so that the button appears to recede into the screen. When the button is released it is redrawn with the up bitmap. The "focus" and "disable" bitmaps are optional, hence we have not used them in our program. The parameters passed to CBitmapButton::LoadBitmaps( ) specify, in order, the up bitmap, the down bitmap, the focus bitmap and the disabled bitmap. Since we are using only the up and down bitmaps we have passed 0 (NULL) for the focus and the disabled bitmap as shown below:
b[i].LoadBitmaps ( IDB_BITMAP1 + i, IDB_BITMAP26 + i, 0, 0 ) ;
Once the frame window with 25 buttons and 25 bitmaps atop them appears we can start the game by clicking on the 'New game' menu item. On doing so, the newgame( ), menu handler gets called. This function calls function myframe::computersmove( ) with a value 1. The 1 here indicates that first time the computer should depress only one button. The computersmove( ) is a general function which can depress as many buttons as you ask it to and record the id of each button depressed in an array m_computerplayed[ ]. To show the depressing and releasing of the button the CBitmapButton::SetState( ) function is called by computersmove( ). The SetState( ) function is passed a value 1 or 0 for showing the depressed and the released state respectively. The User's Move The user can imitate the computer's sequence of moves by attempting to click the buttons with the left mouse button in the same sequence. On clicking any button the control reaches usersmove( ). This has been ensured by the following entry in the message map:
ON_CONTROL_RANGE ( BN_CLICKED, 1, 25, usersmove )
This entry maps the group of control with ids 1 to 25 to a single handler usersmove( ). Note that when usersmove( ) gets called the id of the button which prompted the call would be passed to this function. In this function first it is checked whether the user is trying to make a move before the computer makes its move. That is cheating and a message box is immediately popped up to indicate this and the control is returned from the function. If the move is found to be legal then the id of the depressed button is stored in the array m_userplayed[ ]. It is then verified whether this move made by the user matches with the computer's move or not. If it doesn't match then it is promptly reported so and the user is asked to restart the game. If all the moves made by the user match the ones made by the computer then it is concluded that the user has imitated the computer's moves correctly. In such a case the computersmove( ) function is called again to let the computer make its next move. However, the value passed to computersmove( ) this time is one more than what was passed to it last time around . Thus the degree of difficulty of the game goes on increasing as the game proceeds.
As the computer or the user makes a move (depresses a button) we can create a sound by calling ::MessageBeep( ) API function. However, the choice of creating or not creating such a sound has been left to the user. He can exercise his choice by selecting the item 'Yes' or 'No' from the 'Sound' menu. To keep track of what he has selected a variable m_state has been used. To ensure that if he selects 'Yes' then he should not be allowed to select 'Yes' again, the program disables the 'Yes' menu item once it is selected. A similar procedure is adopted for the 'No' menu item. To implement this functionality we have defined the function enable_disable( ) which gets called whenever the sound menu is being displayed. Note that this function is called twice, once when the 'Yes' menu item is being displayed and next when the 'No' menu item is being displayed. A call to this function is arranged through the message map entry,
ON_UPDATE_COMMAND_UI_RANGE ( 201, 202, enable_disable )
On getting called, this function appropriately disables the menu item using the value in the m_state variable. The actual enabling or disabling is done by the function CCmdUI::Enable( ). The CCmdUI MFC class contains lot of other functions to update user interface items. Icon in The 'About' Dialog If we want to show the icon in the 'About' dialog box we should make a provision for it while creating the dialog box in the Resource Editor. The steps involved in doing this are as follows:
Create an icon and save it.
Create a dialog box.
Select 'Picture' control from the 'Controls' toolbar.
Place this control in the dialog box.
Double click on this control in the dialog to get the 'Picture Properties' dialog box.
Select 'General' property page, select 'Icon' from the 'Type' combobox.
Select id of the icon which you wish to include from the 'Image' combobox.
Save the dialog.