Advanced Compiler Details

Intro to the C++ Language

 
#include <iostream>

using namespace std;

int main()
{
  cout<<"HEY, you, I'm alive! Oh, and Hello World!\n";
  cin.get();
}

 
#include <iostream>

using namespace std;

int main()
{
  cout<<"HEY, you, I'm alive! Oh, and Hello World!\n";
  cin.get();

  return 1;
}

An Aside on Commenting Your Programs

User interaction and Saving Information with Variables

What's with all these variable types?

Declaring Variables in C++

 
int x;
char letter;
float the_float;

int a, b, c, d;

Common Errors when Declaring Variables in C++

Case Sensitivity

Using Variables

 
#include <iostream>

using namespace std;

int main()
{
  int thisisanumber;

  cout<<"Please enter a number: ";
  cin>> thisisanumber;
  cin.ignore();
  cout<<"You entered: "<< thisisanumber <<"\n";
  cin.get();
}

Changing and Comparing Variables

 
a = 4 * 6; // (Note use of comments and of semicolon) a is 24
a = a + 5; // a equals the original value of a with five added to it
a == 5     // Does NOT assign five to a. Rather, it checks to see if a equals 5.

 
a < 5  // Checks to see if a is less than five
a > 5  // Checks to see if a is greater than five
a == 5 // Checks to see if a equals five, for good measure 

Understanding Different Base Systems

  4 x 102 + 3 x 101+ 2 x 100

  4 x 162 + 3 x 161+ 2 x 100

 1 * 231 * 221 * 211 * 20

Converting from decimal to octal or hexadecimal

   0 * 28  1 * 27  0 * 26  0 * 25+ 1 * 24+ 1 * 23+ 1 * 22+ 1 * 21+ 0 * 20

   0 * 22 * 26+ 1 * 21 * 26+ 0 * 20 * 26+ 0 * 22 * 23+ 1 * 21 * 23+ 1 * 20 * 23+ 1 * 22 * 20+ 1 * 21 * 20+ 0 * 20 * 20

Binary Search Trees
Binary search trees (also known as just binary trees) are ordered trees in which all nodes have no more than two children. The parent node is always greater than all of the data in the left sub-tree that extends from the left child node, and the parent node is less than all of the data in the right sub-tree that extends from the right child node.

Here is the basic framwork for the binary search tree:

class binTree {
  public:
    binTree(void);         // Constructor
    ~binTree(void);        // Destructor

    void add(int item);    // Add function
    void remove(int item); // Remove function
    bool search(int item); // Search function
    void print(void);      // Print function
  
  private:
    binTreeNode *root;     // Root pointer

    // ...
    // The extra functions needed for implementation are put here
};

class binTreeNode {
  public:
    int data;                 // Actual data
    binTreeNode *left_child;  // Left child pointer
    binTreeNode *right_child; // Right child pointer
};

This code is very similar to the code of the linked list, but the node here is differs from the node to the linked list in that thisbinTreeNode points to two other nodes instead of just one.

Since the left child is always less than the parent and the right child is greater than the parent, the tree can easily print an ordered list of all of the elements with the following algorithm, also known as in-order traversal:

void printTree(binTreeNode *node) {
  printTree(node->left_child);  // Left child first
  cout << node->data << endl;   // Then this node
  printTree(node->right_child); // Then right child
}

To print the tree, you would call the function with the value of root. Each time, the function would keep calling itself (recursion!) until it reaches the leftmost node, which is the least value in the entire tree. Then, it would cycle through the entire tree, and then the right children, until it reaches the rightmost, or greatest, value in the tree.

Other traversals of trees are pre-order and post-order traversals. In pre-order, the root is processed first, then the left children, and then the right children. In post-order, the left children and right children are processed before the root.

Try writing the code for the binary tree as an exercise. It's a little tricky this time, especially with the remove() function. (HINT: Most of the functions require helper, or auxiliary, functions. Some, but definitely not all, of the functions may be recursive.)

The C Preprocessor

Header Files

Constants

#define [identifier name] [value]

#define PI_PLUS_ONE (3.14 + 1)

x = PI_PLUS_ONE * 5;

x = 3.14 + 1 * 5;

#define [identifier name]

Conditional Compilation

Commenting out Code

#if 0
/* comment ...
*/

// code

/* comment */
#endif

Avoiding Including Files Multiple Times (idempotency)

#ifndef _FILE_NAME_H_
#define _FILE_NAME_H_

/* code */

#endif // #ifndef _FILE_NAME_H_

#ifndef NULL
#define NULL (void *)0
#endif // #ifndef NULL

Macros

#define MACRO_NAME(arg1, arg2, ...) [code to expand to]

#define INCREMENT(x) x++

#define MULT(x, y) x * y

int z = MULT(3 + 2, 4 + 2);

int z = 3 + 2 * 4 + 2;    // 2 * 4 will be evaluated first!

#define MULT(x, y) (x) * (y)
// now MULT(3 + 2, 4 + 2) will expand to (3 + 2) * (4 + 2)

#define ADD_FIVE(a) (a) + 5

int x = ADD_FIVE(3) * 3;
// this expands to (3) + 5 * 3, so 5 * 3 is evaluated first
// Now x is 18, not 24!

#define ADD_FIVE(a) ((a) + 5)

int x = ADD_FIVE(3) * 3;

// We use a trick involving exclusive-or to swap two variables
#define SWAP(a, b)  a ^= b; b ^= a; a ^= b; 

int x = 10;
int y = 5;

// works OK
SWAP(x, y);

// What happens now?
if(x < 0)
    SWAP(x, y);

#define SWAP(a, b)  {a ^= b; b ^= a; a ^= b;} 

#define SWAP(a, b)  { a ^= b; b ^= a; a ^= b; }

int x = 10;
int y = 5;
int z = 4;

// What happens now?
if(x < 0)
    SWAP(x, y);
else
    SWAP(x, z); 

#define SWAP(a, b)  do { a ^= b; b ^= a; a ^= b; } while ( 0 )

int x = 10;
int y = 5;
int z = 4;

// What happens now?
if(x < 0)
    SWAP(x, y);
else
    SWAP(x, z); 

More Gotchas

#define MAX(a, b) ((a) < (b) ? (b) : (a))
int x = 5, y = 10;
int z = MAX(x++, y++);

int x = (x++ < y++ ? y++ : x++)

Multiline macros

#define SWAP(a, b)  {                   \
                        a ^= b;         \
                        b ^= a;         \ 
                        a ^= b;         \
                    } 

Advanced Macro Tricks

Pasting Tokens

#define BUILD_FIELD(field) my_struct.inner_struct.union_a.##field

my_struct.inner_struct.union_a.field1

String-izing Tokens

#define PRINT_TOKEN(token) printf(#token " is %d", token)

printf("<foo>" " is %d" <foo>)

PRINT_TOKEN(x + y);

Avoiding Macros in C++

The C++ Modulus Operator

#include <iostream>

using namespace std;

int main()
{
    int num;
    cin >> num;
    // num % 2 computes the remainder when num is divided by 2
    if ( num % 2 == 0 )
    {
        cout << num << " is even ";
    }

    return 0;
}

Getting Random Values in C and C++ with Rand

At some point in any programmer's life, he or she must learn how to get a random value, or values, in their program. To some this seems involved, difficult, or even beyond their personal ability. This, however, is simply not the case.

Randomizing of values is, at its most basic form, one of the easier things a programmer can do with the C++ language. I have created this short tutorial for Cprogramming.com to aid you in learning, constructing, and using the functions available to you to randomize values.

I will first start with an introduction to the idea of randomizing values, followed by a simple example program that will output three random values. Once a secure understanding of these concepts is in place (hopefully it will be), I will include a short program that uses a range of values from which the random values can be taken.

Ok, now that you know why this tutorial was written, and what it includes, you are ready to learn how to randomize values! So without further ado, let's get started, shall we?

Many programs that you will write require the use of random numbers. For example, a game such as backgammon requires a roll of two dice on each move. Since there are 6 numbers on each die, you could calculate each roll by finding a random number from 1 to 6 for each die.

To make this task a little easier, C++ provides us with a library function, called rand that returns an integer between 0 and RAND_MAX. Let's take a break to explain what RAND_MAX is. RAND_MAX is a compiler-dependent constant, and it is inclusive. Inclusive means that the value of RAND_MAX is included in the range of values. The function, rand, and the constant, RAND_MAX, are included in the library header file stdlib.h.

The number returned by function rand is dependent on the initial value, called a seed that remains the same for each run of a program. This means that the sequence of random numbers that is generated by the program will be exactly the same on each run of the program.

How do you solve this problem you ask? Well I'll tell you! To help us combat this problem we will use another function, srand(seed), which is also declared in the stdlib.h header file. This function allows an application to specify the initial value used by rand at program startup.

Using this method of randomization, the program will use a different seed value on every run, causing a different set of random values every run, which is what we want in this case. The problem posed to us now, of course, is how to get an arbitrary seed value. Forcing the user or programmer to enter this value every time the program was run wouldn't be very efficient at all, so we need another way to do it.

So we turn to the perfect source for our always-changing value, the system clock. The C++ data type time_t and the function time, both declared in time.h, can be used to easily retrieve the time on the computers clock.

When converted to an unsigned integer, a positive whole number, the program time (at execution of program) can make a very nice seed value. This works nicely because no two program executions will occur at the same instant of the computers clock.

As promised, here is a very basic example program. The following code was written in Visual C++ 6.0, but should compile fine on most computers (given u have a compiler, which if your reading this I assume you do). The program outputs three random values.

/*Steven Billington
January 17, 2003
Ranexample.cpp
Program displays three random integers.
*/
/*
Header: iostream
Reason: Input/Output stream
Header: cstdlib
Reason: For functions rand and srand
Header: time.h
Reason: For function time, and for data type time_t
*/
#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
/*
Declare variable to hold seconds on clock.
*/
time_t seconds;
/*
Get value from system clock and
place in seconds variable.
*/
time(&seconds);
/*
Convert seconds to a unsigned
integer.
*/
srand((unsigned int) seconds);
/*
Output random values.
*/
cout<< rand() << endl;
cout<< rand() << endl;
cout<< rand() << endl;
return 0;
}

Users of a random number generator might wish to have a narrower or a wider range of numbers than provided by the rand function. Ideally, to solve this problem a user would specify the range with integer values representing the lower and the upper bounds. To understand how we might accomplish this with the rand function, consider how to generate a number between 0 and an arbitrary upper bound, referred to as high, inclusive.

For any two integers, say a and b, a % b is between 0 and b - 1, inclusive. With this in mind, the expression rand() % high + 1 would generate a number between 1 and high, inclusive, where high is less than or equal to RAND_MAX, a constant defined by the compiler. To place a lower bound in replacement of 1 on that result, we can have the program generate a random number between 0 and (high - low + 1) + low.

I realize how confused you might be right now, so take a look at the next sample program I promised, run it, toy with it, and alternate it to give you different values. It has been a pleasure to teach you another chapter in the world of C++, and you may feel free to email me at Silent_Death17@hotmail.com or to contact me on the message boards of this fine website, where I use the name RoD.

/*
Steven Billington
January 17, 2003
exDice.cpp
Program rolls two dice with random
results.
*/
/*
Header: iostream
Reason: Input/Output stream
Header: stdlib
Reason: For functions rand and srand
Header: time.h
Reason: For function time, and for data type time_t
*/
#include <iostream>
#include <cstdlib>
#include <time.h>
/*
These constants define our upper
and our lower bounds. The random numbers
will always be between 1 and 6, inclusive.
*/
const int LOW = 1;
const int HIGH = 6;

using namespace std;

int main()
{
/*
Variables to hold random values
for the first and the second die on
each roll.
*/
int first_die, sec_die;
/*
Declare variable to hold seconds on clock.
*/
time_t seconds;
/*
Get value from system clock and
place in seconds variable.
*/
time(&seconds);
/*
Convert seconds to a unsigned
integer.
*/
srand((unsigned int) seconds);
/*
Get first and second random numbers.
*/
first_die = rand() % (HIGH - LOW + 1) + LOW;
sec_die = rand() % (HIGH - LOW + 1) + LOW;
/*
Output first roll results.
*/
cout<< "Your roll is (" << first_die << ", "
<< sec_die << "}" << endl << endl;
/*
Get two new random values.
*/
first_die = rand() % (HIGH - LOW + 1) + LOW;
sec_die = rand() % (HIGH - LOW + 1) + LOW;
/*
Output second roll results.
*/
cout<< "My roll is (" << first_die << ", "
<< sec_die << "}" << endl << endl;
return 0;
}