Algorithmic Efficiency -- Beating a Dead Horse Faster

In computer science, often the question is not how to solve a problem, but how to solve a problem well. For instance, take the problem of sorting. Many sorting algorithms are well-known; the problem is not to find a way to sort words, but to find a way to efficiently sort words. This article is about understanding how to compare the relative efficiency of algorithms and why it's important to do so.

If it's possible to solve a problem by using a brute force technique, such as trying out all possible combinations of solutions (for instance, sorting a group of words by trying all possible orderings until you find one that is in order), then why is it necessary to find a better approach? The simplest answer is, if you had a fast enough computer, maybe it wouldn't be. But as it stands, we do not have access to computers fast enough. For instance, if you were to try out all possible orderings of 100 words, that would require 100! (100 factorial) orders of words. (Explanation) That's a number with a 158 digits; were you to compute 1,000,000,000 possibilities were second, you would still be left with the need for over 1x10^149 seconds, which is longer than the expected life of the universe. Clearly, having a more efficient algorithm to sort words would be handy; and, of course, there are many that can sort 100 words within the life of the universe.

Before going further, it's important to understand some of the terminology used for measuring algorithmic efficiency. Usually, the efficiency of an algorithm is expressed as how long it runs in relation to its input. For instance, in the above example, we showed how long it would take our naive sorting algorithm to sort a certain number of words. Usually we refer to the length of input as n; so, for the above example, the efficiency is roughly n!. You might have noticed that it's possible to come up with the correct order early on in the attempt -- for instance, if the words are already partially ordered, it's unlikely that the algorithm would have to try all n! combinations. Often we refer to the average efficiency, would would be in this case n!/2. But because the division by two is nearly insignificant as n grows larger (half of 2 billion is, for instance, still a very large number), we usually ignore constant terms (unless the constant term is zero).

Now that we can describe any algorithm's efficiency in terms of its input length (assuming we know how to compute the efficiency), we can compare algorithms based on their "order". Here, "order" refers to the mathematical method used to compare the efficiency -- for instance, n^2 is "order of n squared," and n! is "order of n factorial." It should be obvious that an order of n^2 algorithm is much less efficient than an algorithm of order n. But not all orders are polynomial -- we've already seen n!, and some are order of log n, or order 2^n.

Often times, order is abbreviated with a capital O: for instance, O(n^2). This notation, known as big-O notation, is a typical way of describing algorithmic efficiency; note that big-O notation typically does not call for inclusion of constants. Also, if you are determining the order of an algorithm and the order turns out to be the sum of several terms, you will typically express the efficiency as only the term with the highest order. For instance, if you have an algorithm with efficiency n^2 + n, then it is an algorithm of order O(n^2).

Algorithmic Efficiency -- Analyzing Algorithms

The ability to analyze a piece of code or an algorithm and understand its efficiency is vital for understanding computer science.

One approach to determining an algorithm's order is to start out assuming an order of O(1), an algorithm that doesn't do anything and immediately terminates no matter what the input. Then, find the section of code that you expect to have the highest order. From there, work out the algorithmic efficiency from the outside in -- figure out the efficiency of the outer loop or recursive portion of the code, then find the efficiency of the inner code; the total efficiency is the efficiency of each layer of code multiplied together.

For instance, to compute the efficiency of a simple selection sort

	for(int x=0; x	{

	  int min = x;

	  for(int y=x; y	  {

		if(array[y]		  min=y;

	  }

	  int temp = array[x];

	  array[x] = array[min];

	  array[min] = temp;

	}

We compute that the order of the outer loop (for(int x = 0; ..)) is O(n); then, we compute that the order of the inner loop is roughly O(n). Note that even though its efficiency varies based on the value of x, the average efficiency is n/2, and we ignore the constant, so it's O(n). After multiplying together the order of the outer and the inner loop, we have O(n^2).

In order to use this approach effectively, you have to be able to deduce the order of the various steps of the algorithm. And you won't always have a piece of code to look at; sometimes you may want to just discuss a concept and determine its order. Some efficiencies are more important than others in computer science, and on the next page, you'll see a list of the most important and useful orders of efficiency, along with examples of algorithms having that efficiency.

Algorithmic Efficiency -- Various Orders and Example

elow, I will list some of the common orders and give example algorithms.

O(1)

An algorithm that runs the same no matter what the input. For instance, an algorithm that always returns the same value regardless of input could be considered an algorithm of efficiency O(1).

O(logn)

Algorithms based on binary trees are often O(logn). This is because a perfectly balanced binary search tree has logn layers, and to search for any element in a binary search tree requires traversing a single node on each layer.

The binary search algorithm is another example of a O(log n) algorithm. In a binary search, one is searching through an ordered array and, beginning in the middle of the remaining space to be searched, whether to search the top or the bottom half. You can divide the array in half only logn times before you reach a single element, which is the element being searched for, assuming it is in the array.

O(n)

Algorithms of efficiency n require only one pass over an entire input. For instance, a linear search algorithm, which searches an array by checking each element in turn, is O(n). Often, accessing an element in a linked list is O(n) because linked lists do not support random access.

O(nlogn)

Often, good sorting algorithms are roughly O(nlogn). An example of an algorithm with this efficiency is merge sort, which breaks up an array into two halves, sorts those two halves by recursively calling itself on them, and then merging the result back into a single array. Because it splits the array in half each time, the outer loop has an efficiency of logn, and for each "level" of the array that has been split up (when the array is in two halves, then in quarters, and so forth), it will have to merge together all of the elements, an operations that has order of n.

O(n^2)

A fairly reasonable efficiency, still in the polynomial time range, the typical examples for this order come from sorting algorithms, such as the selection sort example on the previous page.

O(2^n)

The most important non-polynomial efficiency is this exponential time increase. Many important problems can only be solved by algorithms with this (or worse) efficiency. One example is factoring large numbers expressed in binary; the only known way is by trial and error, and a naive approach would involve dividing every number less than the number being factored into that number until one divided in evenly. For every increase of a single digit, it would require twice as many tests.

Is C++ usage really declining?

A wonderful interview from the father of C++:

It’s probably not complete nonsense. C++ use appears to be declining in some areas and appears to be on an upswing in other areas. If I had to guess, I’d suspect a net decrease sometime during 2002-2004 and a net increase in 2005-2007, but I doubt anyone really knows. Most of the popular measures basically measures noise and ought to report their findings in decibel rather than “popularity.” Many of the major uses are in infrastructure (telecommunications, banking, embedded systems, etc.) where programmers don’t go to conferences or describe their code in public. Many of the most interesting and important C++ applications are not noticed, they are not for sale to the public as programming products, and their implementation language is never mentioned. Examples are Google and “800″ phone numbers. Had I thought of a “C++ inside” logo in 1985, the programming world might have been different today.

Among the positive signs for C++, I can mention an increase in my email and the number of speaking invitations. At the SDWest conference in March, the C++ track was by far the largest, even without counting the “Super tutorial” that I gave with Herb Sutter; more than 300 people attended that one—up by a factor of two compared to two years ago. These are, of course, personal and subjective measures, but they fit with other information that I get from innumerable sources in the industry (worldwide).

It’s a really big world “out there” and the increase in the number of users of one language does not imply the decrease in the numbers of another. I suspect we have reached the point where if you can count your users to the nearest million, you don’t count as a major language. Similarly, I got into a discussion with some friends about how many billions of lines of C++ code there were “out there.” We concluded that we did not know, but it didn’t require much thought to demonstrate that the plural was appropriate.

One simple thing that confuses many discussions of language use/popularity is the distinction between relative and absolute measures. For example, I say that C++ use is growing when I see user population grow by 200,000 programmers from 3.1M to 3.3M. However, somebody else may claim that “C++ is dying” because it’s “popularity” has dropped from 16 percent to 10 percent of the total number of users. Both claims could be simultaneously true as the number of programmers continues to grow and especially as what is considered to be programming continues to change. I think that C++ is more than holding its own in its traditional core domains, such as infrastructure, systems programming, embedded systems, and applications with serious time and/or space constraints. It never was dominant for scripting web applications.

Most of the popularity measures seem to measure buzz/noise, which is basically counting mentions on the web. That’s potentially very misleading. Ten people learning a scripting language will make much more noise than a thousand full time programmers using C++, especially if the thousand C++ programmers are working on a project crucial to a company—such programmers typically don’t post and are often not allowed to. My worry is that such measures may actually measure the number of novices and thus be an indication of a worsening shortage of C++ programmers. Worse, managers and academics may incautiously take such figures seriously (as a measure of quality) and become part of a vicious circle.

C++ atomics and memory ordering

The question that’s been bugging me lately was: How does C++ make the use atomic variables both portable and efficient.

I knew how Java volatile worked–it enforced sequential consistency, which is not always the most efficient thing to do.

C++0x has atomic variables which also enforce sequential consistency when used in the default mode. Without special ordering annotations they work almost like Java’s volatile (interestingly, Java’s volatile doesn’t enforce atomicity–there is an atomic library in Java, though, which does).

However, C++ offers various degrees of relaxation of sequential consistency which, if used correctly, should produce more efficient code.

After studying a bit of the x86 memory model, I realized that some basic lock-free patterns (like the one in double-checked locking) will work without any fences. There should be a way of coding them in C++ such that, when compiled for the x86, no fences are produced. On the other hand, the same C++ code, when compiled for, let’s say, the alpha or the Power PC, should produce the necessary fencing.

To make things more interesting, there are some other algorithms, like the Peterson lock, which do require memory fences on the x86 . So it’s not just the matter of skipping all fencing.

I reduced my question to: How does one write portable code in C++ that results in just the right amount of fencing on the x86?

Specifying memory ordering in C++

The C++0x atomics library proposal underwent a lot of changes before it settled into its current shape. There is now a complete C++0x draft. It’s not an easy read so I’m grateful to Hans Boehm for clarifying some of the fine points.

Without further ado, this is how the publication safety pattern (the mother of all double-checked locking patterns) could be written in C++:

  atomic ready = false;
 atomic data = 0;

Thread 0:

  data.store(1);
 ready.store(true);

Thread 1:

  if (ready.load())
   assert (data.load() == 1);

As you can see, atomic objects have methods store and load that are used for writing and reading underlying shared data. By default, these methods enforce sequential consistency. What it means is that this code has the same semantics as if it were written in Java using volatile variables. Consequently, on the x86, it will generate memory fences after each store.

But we know that these fences are not necessary for publication safety. How can we write code that would produce minimal fencing on the x86?

To make such fine tuning possible, the C++0x atomics library allows the programmer to specify ordering requirements for each load and store. I’ll explain various ordering options in a moment; for now let’s have a look at the optimized version of the publication pattern:

  atomic ready = false;
 atomic data = 0;

Thread 0:

  data.store(1, memory_order_release);
 ready.store(true, memory_order_release);

Thread 1:

  if (ready.load(memory_order_acquire))
   assert (data.load(memory_order_acquire) == 1);

What’s important is that this code will work correctly on any major processor, but it will produce no fences on the x86.

Warning: Even if you know that your program will only ever run on an x86, you can’t remove the atomics and the ordering constraints from your code. They are still necessary to prevent the compiler from doing the reordering.

Fine-tuning memory ordering

Memory order can be specified using the following enumeration:

namespace std {
typedef enum memory_order {
  memory_order_relaxed,
  memory_order_consume,
  memory_order_acquire,
  memory_order_release,
  memory_order_acq_rel,
  memory_order_seq_cst
} memory_order;
}

The default for all operations on atomic variables is memory_order_seq_cst which, just like Java’s volatile, enforces sequential consistency. Other orderings are used to relax sequential consistency and often squeeze better performance from lock-free algorithms.

• memory_order_acquire: guarantees that subsequent loads are not moved before the current load or any preceding loads.
• memory_order_release: preceding stores are not moved past the current store or any subsequent stores.
• memory_order_acq_rel: combines the two previous guarantees.
• memory_order_consume: potentially weaker form of memory_order_acquire that enforces ordering of the current load before other operations that are data-dependent on it (for instance, when a load of a pointer is marked memory_order_consume, subsequent operations that dereference this pointer won’t be moved before it (yes, even that is not guaranteed on all platforms!).
• memory_order_relaxed: all reorderings are okay.

As I discussed before, the x86 guarantees acquire semantics for loads and release semantics for stores, so load(memory_order_acquire) and store(x, memory_order_release) produce no fences. So, indeed, our optimized version of the publication pattern will produce optimal assembly on the x86 (and I presume on other processors too).

But I have also shown before that the Peterson’s algorithm won’t work on the x86 without fencing. So it’s not enough to use just memory_order_acquire and memory_order_release to implement it. In fact, the problem with the Peterson lock was the possibility of reordering loads with stores. The weakest constraint that prevents such reordering is memory_order_acq_rel.

Now here the funny story begins. Without much thinking, I decided that just slapping memory_order_acq_rel on any of the writes would fix the problem. Here’s what I originally wrote:

[begin quote] The correct C++ code in this case is:

Peterson::Peterson() {
  _victim.store(0, memory_order_release);
  _interested[0].store(false, memory_order_release);
  _interested[1].store(false, memory_order_release);
}
void Peterson::lock() {
  int me = threadID; // either 0 or 1
  int he = 1 – me; // the other thread
  _interested[me].exchange(true, memory_order_acq_rel);
  _victim.store(me, memory_order_release);
  while (_interested[he].load(memory_order_acquire)
      && _victim.load(memory_order_acquire) == me)
     continue; // spin
}

The ordering memory_order_acq_rel produces an mfence instruction on the x86. This fence will prevent the movement of the load of _interested[he] before the store to _interested[me], which could otherwise happen (and break the algorithm).[end quote]

You can read comments to this post–especially the ones by Anthony and Dmitriy, who made me eat crow. In short, the point is that the “acquire” part of memory_order_acq_rel has no meaning unless another thread writes to (”releases”) the same variable. Since only thread 0 writes to _interested[0] and only thread 1 one writes to _interested[1], this synchronization accomplished nothing (outside of the x86). Dmitriy’s implementation, which synchronizes on _victim, is correct (but I had to ask many questions before understanding Anthony’s proof of it).

Conclusion

What strikes me about this example is how non-trivial the reasoning behind this implementation was. I had to actually go through the x86 assembly to realize that I needed those and not some other ordering constraints (and I still got it wrong!). In comparison to that, the old fashioned assembly programming looks like a piece of cake.

Any time you deviate from sequential consistency, you increase the complexity of the problem by orders of magnitude.

Microsoft volatile

No, I’m not talking about the stock market. I mentioned before that C++ volatile has nothing to do with multithreading. This is not entirely true because some compiler vendors took the liberty to add non-standard semantics to volatile (out of pure desperation, since they had to support multi-processor code, and pre-0x C++ offered no help in this area). This new semantics, at least in the case of Microsoft compilers, did not include sequential consistency. Instead it guaranteed acquire and release semantics (which, on the x86, didn’t result in any fencing). So, although the publication pattern will work on a Microsoft compiler with volatile variables, the Peterson lock won’t! I thought that was an interesting piece of trivia.

make pyramid with c++

there is the source code to make pyramids. check it out

#include
#include

main()
{
char kar;
int jumlah, dasar, a;
int b=1;
int counter=0;

cout << “—————————————————————-\n”; cout << “ PROGRAM MEMBUAT BENTUK PIRAMIDA \n”; cout << “ OLEH : M. LATIF ROZI \n”; cout << “ SMA NEGERI 3 SEMARANG \n”; cout << “—————————————————————-\n”;

while (cin)
{
cout<<”Masukkan karakter yang akan dibuat piramid : “; cin>>kar;
cout << “Masukkan besar piramid : “; cin >> dasar;
jumlah=(dasar/2)+5-counter;
a=1;
while(jumlah>5)
{
jumlah=(dasar/2)+5-counter;
cout<0)
{
cout<<<<

There is the screenshot

Preprocessor directives

Preprocessor directives are lines included in the code of our programs that are not program statements but directives for the preprocessor. These lines are always preceded by a hash sign (#). The preprocessor is executed before the actual compilation of code begins, therefore the preprocessor digests all these directives before any code is generated by the statements.

These preprocessor directives extend only across a single line of code. As soon as a newline character is found, the preprocessor directive is considered to end. No semicolon (;) is expected at the end of a preprocessor directive. The only way a preprocessor directive can extend through more than one line is by preceding the newline character at the end of the line by a backslash (\).

macro definitions (#define, #undef)

To define preprocessor macros we can use #define. Its format is:

#define identifier replacement

When the preprocessor encounters this directive, it replaces any occurrence of identifier in the rest of the code by replacement. This replacement can be an expression, a statement, a block or simply anything. The preprocessor does not understand C++, it simply replaces any occurrence of identifier by replacement.

#define TABLE_SIZE 100 int table1[TABLE_SIZE]; int table2[TABLE_SIZE];

After the preprocessor has replaced TABLE_SIZE, the code becomes equivalent to:

int table1[100]; int table2[100];

This use of #define as constant definer is already known by us from previous tutorials, but #define can work also with parameters to define function macros:

#define getmax(a,b) a>b?a:b

This would replace any occurrence of getmax followed by two arguments by the replacement expression, but also replacing each argument by its identifier, exactly as you would expect if it was a function:

// function macro #include using namespace std; #define getmax(a,b) ((a)>(b)?(a):(b)) int main() { int x=5, y; y= getmax(x,2); cout << class="kw">return 0; }

5 7

Defined macros are not affected by block structure. A macro lasts until it is undefined with the #undef preprocessor directive:

#define TABLE_SIZE 100 int table1[TABLE_SIZE]; #undef TABLE_SIZE #define TABLE_SIZE 200 int table2[TABLE_SIZE];

This would generate the same code as:

int table1[100]; int table2[200];

Function macro definitions accept two special operators (# and ##) in the replacement sequence:
If the operator # is used before a parameter is used in the replacement sequence, that parameter is replaced by a string literal (as if it were enclosed between double quotes)

#define str(x) #x cout <<>

This would be translated into:

cout << "test";

The operator ## concatenates two arguments leaving no blank spaces between them:

#define glue(a,b) a ## b glue(c,out) << "test";

This would also be translated into:

cout << "test";

Because preprocessor replacements happen before any C++ syntax check, macro definitions can be a tricky feature, but be careful: code that relies heavily on complicated macros may result obscure to other programmers, since the syntax they expect is on many occasions different from the regular expressions programmers expect in C++.

Conditional inclusions (#ifdef, #ifndef, #if, #endif, #else and #elif)

These directives allow to include or discard part of the code of a program if a certain condition is met.

#ifdef allows a section of a program to be compiled only if the macro that is specified as the parameter has been defined, no matter which its value is. For example:

#ifdef TABLE_SIZE int table[TABLE_SIZE]; #endif

In this case, the line of code int table[TABLE_SIZE]; is only compiled if TABLE_SIZE was previously defined with #define, independently of its value. If it was not defined, that line will not be included in the program compilation.

#ifndef serves for the exact opposite: the code between #ifndef and #endif directives is only compiled if the specified identifier has not been previously defined. For example:

#ifndef TABLE_SIZE #define TABLE_SIZE 100 #endif int table[TABLE_SIZE];

In this case, if when arriving at this piece of code, the TABLE_SIZE macro has not been defined yet, it would be defined to a value of 100. If it already existed it would keep its previous value since the #define directive would not be executed.

The #if, #else and #elif (i.e., "else if") directives serve to specify some condition to be met in order for the portion of code they surround to be compiled. The condition that follows #if or #elif can only evaluate constant expressions, including macro expressions. For example:

#if TABLE_SIZE>200 #undef TABLE_SIZE #define TABLE_SIZE 200 #elif TABLE_SIZE<50 #undef TABLE_SIZE #define TABLE_SIZE 50 #else #undef TABLE_SIZE #define TABLE_SIZE 100 #endif int table[TABLE_SIZE];

Notice how the whole structure of #if, #elif and #else chained directives ends with #endif.

The behavior of #ifdef and #ifndef can also be achieved by using the special operators defined and !defined respectively in any #if or #elif directive:

#if !defined TABLE_SIZE #define TABLE_SIZE 100 #elif defined ARRAY_SIZE #define TABLE_SIZE ARRAY_SIZE int table[TABLE_SIZE];

Line control (#line)

When we compile a program and some error happen during the compiling process, the compiler shows an error message with references to the name of the file where the error happened and a line number, so it is easier to find the code generating the error.

The #line directive allows us to control both things, the line numbers within the code files as well as the file name that we want that appears when an error takes place. Its format is:

#line number "filename"

Where number is the new line number that will be assigned to the next code line. The line numbers of successive lines will be increased one by one from this point on.

"filename" is an optional parameter that allows to redefine the file name that will be shown. For example:

#line 20 "assigning variable" int a?;

This code will generate an error that will be shown as error in file "assigning variable", line 20.

Error directive (#error)

This directive aborts the compilation process when it is found, generating a compilation the error that can be specified as its parameter:

#ifndef __cplusplus #error A C++ compiler is required! #endif

This example aborts the compilation process if the macro name __cplusplus is not defined (this macro name is defined by default in all C++ compilers).

Source file inclusion (#include)

This directive has also been used assiduously in other sections of this tutorial. When the preprocessor finds an #include directive it replaces it by the entire content of the specified file. There are two ways to specify a file to be included:

#include "file" #include

The only difference between both expressions is the places (directories) where the compiler is going to look for the file. In the first case where the file name is specified between double-quotes, the file is searched first in the same directory that includes the file containing the directive. In case that it is not there, the compiler searches the file in the default directories where it is configured to look for the standard header files.
If the file name is enclosed between angle-brackets <> the file is searched directly where the compiler is configured to look for the standard header files. Therefore, standard header files are usually included in angle-brackets, while other specific header files are included using quotes.

Pragma directive (#pragma)

This directive is used to specify diverse options to the compiler. These options are specific for the platform and the compiler you use. Consult the manual or the reference of your compiler for more information on the possible parameters that you can define with #pragma.

If the compiler does not support a specific argument for #pragma, it is ignored - no error is generated.

Predefined macro names

The following macro names are defined at any time:

macro	value
__LINE__	Integer value representing the current line in the source code file being compiled.
__FILE__	A string literal containing the presumed name of the source file being compiled.
__DATE__	A string literal in the form "Mmm dd yyyy" containing the date in which the compilation process began.
__TIME__	A string literal in the form "hh:mm:ss" containing the time at which the compilation process began.
__cplusplus	An integer value. All C++ compilers have this constant defined to some value. If the compiler is fully compliant with the C++ standard its value is equal or greater than 199711L depending on the version of the standard they comply.

For example:

// standard macro names #include using namespace std; int main() { cout << "This is the line number " << class="str">" of file " << class="str">".\n"; cout << "Its compilation began " << class="str">" at " << class="str">".\n"; cout << "The compiler gives a __cplusplus value of " << class="kw">return 0; }

An introduction to pointers

Pointers are an extremely powerful programming tool. They can make some things much easier, help improve your program's efficiency, and even allow you to handle unlimited amounts of data. For example, using pointers is one way to have a function modify a variable passed to it. It is also possible to use pointers to dynamically allocate memory, which means that you can write programs that can handle nearly unlimited amounts of data on the fly--you don't need to know, when you write the program, how much memory you need. Wow, that's kind of cool. Actually, it's very cool, as we'll see in some of the next tutorials. For now, let's just get a basic handle on what pointers are and how you use them.

What are pointers? Why should you care?

Pointers are aptly named: they "point" to locations in memory. Think of a row of safety deposit boxes of various sizes at a local bank. Each safety deposit box will have a number associated with it so that the teller can quickly look it up. These numbers are like the memory addresses of variables. A pointer in the world of safety deposit box would simply be anything that stored the number of another safety deposit box. Perhaps you have a rich uncle who stored valuables in his safety deposit box, but decided to put the real location in another, smaller, safety deposit box that only stored a card with the number of the large box with the real jewelery. The safety deposit box with the card would be storing the location of another box; it would be equivalent to a pointer. In the computer, pointers are just variables that store memory addresses, usually the addresses of other variables.

The cool thing is that once you can talk about the address of a variable, you'll then be able to go to that address and retrieve the data stored in it. If you happen to have a huge piece of data that you want to pass into a function, it's a lot easier to pass its location to the function than to copy every element of the data! Moreover, if you need more memory for your program, you can request more memory from the system--how do you get "back" that memory? The system tells you where it is located in memory; that is to say, you get a memory address back. And you need pointers to store the memory address.

A note about terms: the word pointer can refer either to a memory address itself, or to a variable that stores a memory address. Usually, the distinction isn't really that important: if you pass a pointer variable into a function, you're passing the value stored in the pointer--the memory address. When I want to talk about a memory address, I'll refer to it as a memory address; when I want a variable that stores a memory address, I'll call it a pointer. When a variable stores the address of another variable, I'll say that it is "pointing to" that variable.

Pointer Syntax

Pointers require a bit of new syntax because when you have a pointer, you need the ability to request both the memory location it stores and the value stored at that memory location. Moreover, since pointers are somewhat special, you need to tell the compiler when you declare your pointer variable that the variable is a pointer, and tell the compiler what type of memory it points to.

The pointer declaration looks like this:

 *;

For example, you could declare a pointer that stores the address of an integer with the following syntax:

int *points_to_integer;

Notice the use of the *. This is the key to declaring a pointer; if you add it directly before the variable name, it will declare the variable to be a pointer. Minor gotcha: if you declare multiple pointers on the same line, you must precede each of them with an asterisk:

// one pointer, one regular int
int *pointer1, nonpointer1;

// two pointers
int *pointer1, *pointer2;

As I mentioned, there are two ways to use the pointer to access information: it is possible to have it give the actual address to another variable. To do so, simply use the name of the pointer without the *. However, to access the actual memory location, use the *. The technical name for this doing this is dereferencing the pointer; in essence, you're taking the reference to some memory address and following it, to retrieve the actual value. It can be tricky to keep track of when you should add the asterisk. Remember that the pointer's natural use is to store a memory address; so when you use the pointer:

call_to_function_expecting_memory_address(pointer);

then it evaluates to the address. You have to add something extra, the asterisk, in order to retrieve the value stored at the address. You'll probably do that an awful lot. Nevertheless, the pointer itself is supposed to store an address, so when you use the bare pointer, you get that address back.

Pointing to Something: Retrieving an Address

In order to have a pointer actually point to another variable it is necessary to have the memory address of that variable also. To get the memory address of a variable (its location in memory), put the & sign in front of the variable name. This makes it give its address. This is called the address-of operator, because it returns the memory address. Conveniently, both ampersand and address-of start with a; that's a useful way to remember that you use & to get the address of a variable.

For example:

#include 

using namespace std;

int main()
{
 int x;            // A normal integer
 int *p;           // A pointer to an integer

 p = &x;           // Read it, "assign the address of x to p"
 cin>> x;          // Put a value in x, we could also use *p here
 cin.ignore();
 cout<< *p <<"\n"; // Note the use of the * to get the value
 cin.get();
}

The cout outputs the value stored in x. Why is that? Well, let's look at the code. The integer is called x. A pointer to an integer is then defined as p. Then it stores the memory location of x in pointer by using the address-of operator (&) to get the address of the variable. Using the ampersand is a bit like looking at the label on the safety deposit box to see its number rather than looking inside the box, to get what it stores. The user then inputs a number that is stored in the variable x; remember, this is the same location that is pointed to by p.

The next line then passes *p into cout. *p performs the "dereferencing" operation on p; it looks at the address stored in p, and goes to that address and returns the value. This is akin to looking inside a safety deposit box only to find the number of (and, presumably, the key to ) another box, which you then open.

Notice that in the above example, pointer is initialized to point to a specific memory address before it is used. If this was not the case, it could be pointing to anything. This can lead to extremely unpleasant consequences to the program. For instance, the operating system will probably prevent you from accessing memory that it knows your program doesn't own: this will cause your program to crash. If it let you use the memory, you could mess with the memory of any running program--for instance, if you had a document opened in Word, you could change the text! Fortunately, Windows and other modern operating systems will stop you from accessing that memory and cause your program to crash. To avoid crashing your program, you should always initialize pointers before you use them.

It is also possible to initialize pointers using free memory. This allows dynamic allocation of array memory. It is most useful for setting up structures called linked lists. This difficult topic is too complex for this text. An understanding of the keywords new and delete will, however, be tremendously helpful in the future.

The keyword new is used to initialize pointers with memory from free store (a section of memory available to all programs). The syntax looks like the example:

int *ptr = new int;

It initializes ptr to point to a memory address of size int (because variables have different sizes, number of bytes, this is necessary). The memory that is pointed to becomes unavailable to other programs. This means that the careful coder should free this memory at the end of its usage.

The delete operator frees up the memory allocated through new. To do so, the syntax is as in the example.

delete ptr;

After deleting a pointer, it is a good idea to reset it to point to 0. When 0 is assigned to a pointer, the pointer becomes a null pointer, in other words, it points to nothing. By doing this, when you do something foolish with the pointer (it happens a lot, even with experienced programmers), you find out immediately instead of later, when you have done considerable damage.

In fact, the concept of the null pointer is frequently used as a way of indicating a problem--for instance, some functions left over from C return 0 if they cannot correctly allocate memory (notably, the malloc function). You want to be sure to handle this correctly if you ever use malloc or other C functions that return a "NULL pointer" on failure.

In C++, if a call to new fails because the system is out of memory, then it will "throw an exception". For the time being, you need not worry too much about this case, but you can read more about what happens when new fails.

Taking Stock of Pointers

Pointers may feel like a very confusing topic at first but I think anyone can come to appreciate and understand them. If you didn't feel like you absorbed everything about them, just take a few deep breaths and re-read the lesson. You shouldn't feel like you've fully grasped every nuance of when and why you need to use pointers, though you should have some idea of some of their basic uses.

Introduction to Classes

C++ is a bunch of small additions to C, with a few major additions. One major addition is the object-oriented approach (the other addition is support for generic programming, which we'll cover later). As the name object-oriented programming suggests, this approach deals with objects. Of course, these are not real-life objects themselves. Instead, these objects are the essential definitions of real world objects. Classes are collections of data related to a single object type. Classes not only include information regarding the real world object, but also functions to access the data, and classes possess the ability to inherit from other classes. (Inheritance is covered in a later lesson.)

If a class is a house, then the functions will be the doors and the variables will be the items inside the house. The functions usually will be the only way to modify the variables in this structure, and they are usually the only way even to access the variables in this structure. This might seem silly at first, but the idea to make programs more modular - the principle itself is called "encapsulation". The key idea is that the outside world doesn't need to know exactly what data is stored inside the class--it just needs to know which functions it can use to access that data. This allows the implementation to change more easily because nobody should have to rely on it except the class itself.

The syntax for these classes is simple. First, you put the keyword 'class' then the name of the class. Our example will use the name Computer. Then you put an open bracket. Before putting down the different variables, it is necessary to put the degree of restriction on the variable. There are three levels of restriction. The first is public, the second protected, and the third private. For now, all you need to know is that the public restriction allows any part of the program, including parts outside the class, to access the functions and variables specified as public. The protected restriction prevents functions outside the class to access the variable. The private restriction is similar to protected (we'll see the difference later when we look at inheritance. The syntax for declaring these access restrictions is merely the restriction keyword (public, private, protected) and then a colon. Finally, you put the different variables and functions (You usually will only put the function prototype[s]) you want to be part of the class. Then you put a closing bracket and semicolon. Keep in mind that you still must end the function prototype(s) with a semi-colon.

Let's look at these different access restrictions for a moment. Why would you want to declare something private instead of public? The idea is that some parts of the class are intended to be internal to the class--only for the purpose of implementing features. On the other hand, some parts of the class are supposed to be available to anyone using the class--these are the public class functions. Think of a class as though it were an appliance like a microwave: the public parts of the class correspond to the parts of the microwave that you can use on an everyday basis--the keypad, the start button, and so forth. On the other hand, some parts of the microwave are not easily accessible, but they are no less important--it would be hard to get at the microwave generator. These would correspond to the protected or private parts of the class--the things that are necessary for the class to function, but that nobody who uses the class should need to know about. The great thing about this separation is that it makes the class easier to use (who would want to use a microwave where you had to know exactly how it works in order to use it?) The key idea is to separate the interface you use from the way the interface is supported and implemented.

Classes must always contain two functions: a constructor and a destructor. The syntax for them is simple: the class name denotes a constructor, a ~ before the class name is a destructor. The basic idea is to have the constructor initialize variables, and to have the destructor clean up after the class, which includes freeing any memory allocated. If it turns out that you don't need to actually perform any initialization, then you can allow the compiler to create a "default constructor" for you. Similarly, if you don't need to do anything special in the destructor, the compiler can write it for you too!

When the programmer declares an instance of the class, the constructor will be automatically called. The only time the destructor is called is when the instance of the class is no longer needed--either when the program ends, the class reaches the end of scope, or when its memory is deallocated using delete (if you don't understand all of that, don't worry; the key idea is that destructors are always called when the class is no longer usable). Keep in mind that neither constructors nor destructors return arguments! This means you do not want to (and cannot) return a value in them.

Note that you generally want your constructor and destructor to be made public so that your class can be created! The constructor is called when an object is created, but if the constructor is private, it cannot be called so the object cannot be constructed. This will cause the compiler to complain.

The syntax for defining a function that is a member of a class outside of the actual class definition is to put the return type, then put the class name, two colons, and then the function name. This tells the compiler that the function is a member of that class.

For example:

#include 

using namespace std;

class Computer // Standard way of defining the class
{
public:
 // This means that all of the functions below this(and any variables)
 //  are accessible to the rest of the program.
 //  NOTE: That is a colon, NOT a semicolon...
 Computer();
 // Constructor
 ~Computer();
 // Destructor
 void setspeed ( int p );
 int readspeed();
protected:
 // This means that all the variables under this, until a new type of
 //  restriction is placed, will only be accessible to other functions in the
 //  class.  NOTE: That is a colon, NOT a semicolon...
 int processorspeed;
};
// Do Not forget the trailing semi-colon

Computer::Computer()
{
 //Constructors can accept arguments, but this one does not
 processorspeed = 0;
}

Computer::~Computer()
{
 //Destructors do not accept arguments
}

void Computer::setspeed ( int p )
{
 // To define a function outside put the name of the class
 //  after the return type and then two colons, and then the name
 //  of the function.
 processorspeed = p;
}
int Computer::readspeed() 
{
 // The two colons simply tell the compiler that the function is part
 //  of the class
 return processorspeed;
}

int main()
{
 Computer compute; 
 // To create an 'instance' of the class, simply treat it like you would
 //  a structure.  (An instance is simply when you create an actual object
 //  from the class, as opposed to having the definition of the class)
 compute.setspeed ( 100 );
 // To call functions in the class, you put the name of the instance,
 //  a period, and then the function name.
 cout<< compute.readspeed();
 // See above note.
}

This introduction is far from exhaustive and, for the sake of simplicity, recommends practices that are not always the best option. For more detail, I suggest asking questions on our forums and getting a book recommended by our book reviews.

The C++ Modulus Operator

Take simple arithmetic problem: what's left over when you divide 11 by 3? The answer is easy to compute: divide 11 by 3 and take the remainder: 2. But how would you compute this in a programming language like C or C++? It's not hard to come up with a formula, but the language provides a built-in mechanism, the modulus operator ('%'), that computes the remainer that results from performing integer division.

The modulus operator is useful in a variety of circumstances. It is commonly used to take a randomly generated number and reduce that number to a random number on a smaller range, and it can also quickly tell you if one number is a factor of another.

If you wanted to know if a number was odd or even, you could use modulus to quickly tell you by asking for the remainder of the number when divided by 2.

#include 

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;
}

The key line is the one that performs the modulus operation: "num % 2 == 0". A number is even if and only if it is divisible by two, and a number is divisible by another only if there is no remainder.

How could you use modulus to write a program that checks if a number is prime?

Templates and Templated Classes in C++

What's better than having several classes that do the same thing to different datatypes? One class that lets you choose which datatype it acts on.

Templates are a way of making your classes more abstract by letting you define the behavior of the class without actually knowing what datatype will be handled by the operations of the class. In essence, this is what is known as generic programming; this term is a useful way to think about templates because it helps remind the programmer that a templated class does not depend on the datatype (or types) it deals with. To a large degree, a templated class is more focused on the algorithmic thought rather than the specific nuances of a single datatype. Templates can be used in conjunction with abstract datatypes in order to allow them to handle any type of data. For example, you could make a templated stack class that can handle a stack of any datatype, rather than having to create a stack class for every different datatype for which you want the stack to function. The ability to have a single class that can handle several different datatypes means the code is easier to maintain, and it makes classes more reusable.

The basic syntax for declaring a templated class is as follows:

template  class a_class {...};

The keyword 'class' above simply means that the identifier a_type will stand for a datatype. NB: a_type is not a keyword; it is an identifier that during the execution of the program will represent a single datatype. For example, you could, when defining variables in the class, use the following line:

a_type a_var;

and when the programmer defines which datatype 'a_type' is to be when the program instantiates a particular instance of a_class, a_var will be of that type.

When defining a function as a member of a templated class, it is necessary to define it as a templated function:

template void a_class::a_function(){...}
              

When declaring an instance of a templated class, the syntax is as follows:

a_class an_example_class;
             

An instantiated object of a templated class is called a specialization; the term specialization is useful to remember because it reminds us that the original class is a generic class, whereas a specific instantiation of a class is specialized for a single datatype (although it is possible to template multiple types).

Usually when writing code it is easiest to precede from concrete to abstract; therefore, it is easier to write a class for a specific datatype and then proceed to a templated - generic - class. For that brevity is the soul of wit, this example will be brief and therefore of little practical application.

We will define the first class to act only on integers.

class calc
{
 public:
   int multiply(int x, int y);
   int add(int x, int y);
};
int calc::multiply(int x, int y)
{
 return x*y;
}
int calc::add(int x, int y)
{
 return x+y;
}

We now have a perfectly harmless little class that functions perfectly well for integers; but what if we decided we wanted a generic class that would work equally well for floating point numbers? We would use a template.

template  class calc
{
 public:
   A_Type multiply(A_Type x, A_Type y);
   A_Type add(A_Type x, A_Type y);
};
template  A_Type calc::multiply(A_Type x,A_Type y)
{
 return x*y;
}
template  A_Type calc::add(A_Type x, A_Type y)
{
 return x+y;
}

To understand the templated class, just think about replacing the identifier A_Type everywhere it appears, except as part of the template or class definition, with the keyword int. It would be the same as the above class; now when you instantiate an
object of class calc you can choose which datatype the class will handle.

calc  a_calc_class;

Templates are handy for making your programs more generic and allowing your code to be reused later.

Class Design in C++

Understanding Interfaces

When you're designing a class in C++, the first thing you should decide is the public interface for the class. The public interface determines how your class will be used by other programmers (or you), and once designed and implemented it should generally stay pretty constant. You may decide to add to the interface, but once you've started using the class, it will be hard to remove functions from the public interface (unless they aren't used and weren't necessary in the first place).

But that doesn't mean that you should include more functionality in your class than necessary just so that you can later decide what to remove from the interface. If you do this, you'll just make the class harder to use. People will ask questions like, "why are there four ways of doing this? Which one is better? How can I choose between them?" It's usually easier to keep things simple and provide one way of doing each thing unless there's a compelling reason why your class should offer multiple methods with the same basic functionality.

At the same time, just because adding methods to the public interface (probably) won't break anything that doesn't mean that you should start off with a tiny interface. First of all, if anybody decides to inherit from your class and you then choose a function with the same name, you're in for a boatload of confusion. First, if you don't declare the function virtual, then an object of the subclass will have the function chosen depending on the static type of the pointer. This can be messy. Moreover, if you do declare it virtual, then you have the issue that it might provide a different type of functionality than was intended by the original implementation of that function. Finally, you just can't add a pure virtual function to a class that's already in use because nobody who has inherited from it will have implemented that function.

The public interface, then, should remain as constant as possible. In fact, a good approach to designing classes is to write the interface before the implementation because it's what determines how your class interacts with the rest of the world (which is more important for the program as a whole than how the class is actually implemented). Moreover, if you write the interface first, you can get a feel for how the class will work with other classes before you actually dive into the implementation details.

Inheritance and Class Design

The second issue of your class design is what should be available to programmers who wish to create subclasses. This interface is primarily determined by virtual functions, but you can also include protected methods that are designed for use by the class or its subclasses (remember that protected methods are visible to subclasses while private methods are not).

A key consideration is whether it makes sense for a function to be virtual. A function should be virtual when the implementation is likely to differ from subclass to subclass. Vice-versa, whenever a function should not change, then it should be made non-virtual. The key idea is to think about whether to make a function virtual by asking if the function should always be the same for every class.

For example, if you have a class is designed to allow users to monitor network traffic and you want to allow subclasses that implement different ways of analyzing the traffic, you might use the following interface:

class TrafficWatch
{
       public:
       // Packet is some class that implements information about network
       // packets
       void addPacket (const Packet& network_packet);

       int getAveragePacketSize ();

       int getMaxPacket ();

       virtual bool isOverloaded ();
};

In this class, some methods will not change from implementation to implementation; adding a packet should always be handled the same way, and the average packet size isn't going to change either. On the other hand, someone might have a very different idea of what it means to have an overloaded network. This will change from situation to situation and we don't want to prevent someone from changing how this is computed--for some, anything over 10 Mbits/sec of traffic might be an overloaded network, and for others, it would require 100 Mbits/sec on some specific network cables.

Finally, when publicly inheriting from any class or designing for inheritance, remember that you should strive for it to be clear that inheritance models is-a. At heart, the is-a relationship means that the subclass should be able to appear anywhere the parent class could appear. From the standpoint of the user of the class, it should not matter whether a class is the parent class or a subclass.

To design an is-a relationship, make sure that it makes sense for the class to include certain functions to be sure that it doesn't include that subclasses might not actually need. One example of having an extra function is that of a Bird class that implements a fly function. The problem is that not all birds can fly--penguins and emus, for instance. This suggests that a more prudent design choice might be to have two subclasses of birds, one for birds that can fly and one for flightless birds. Of course, it might be overkill to have two subclasses of bird depending on how complex your class hierarchy will be. If you know that nobody would ever expect use your class for a flightless bird, then it's not so bad. Of course, you won't always know what someone will use your class for and it's much easier to think carefully before you start to implement an entire class hierachy than it will be to go back and change it once people are using it.

Binary Trees

The binary tree is a fundamental data structure used in computer science. The binary tree is a useful data structure for rapidly storing sorted data and rapidly retrieving stored data. A binary tree is composed of parent nodes, or leaves, each of which stores data and also links to up to two other child nodes (leaves) which can be visualized spatially as below the first node with one placed to the left and with one placed to the right. It is the relationship between the leaves linked to and the linking leaf, also known as the parent node, which makes the binary tree such an efficient data structure. It is the leaf on the left which has a lesser key value (ie, the value used to search for a leaf in the tree), and it is the leaf on the right which has an equal or greater key value. As a result, the leaves on the farthest left of the tree have the lowest values, whereas the leaves on the right of the tree have the greatest values. More importantly, as each leaf connects to two other leaves, it is the beginning of a new, smaller, binary tree. Due to this nature, it is possible to easily access and insert data in a binary tree using search and insert functions recursively called on successive leaves.

The typical graphical representation of a binary tree is essentially that of an upside down tree. It begins with a root node, which contains the original key value. The root node has two child nodes; each child node might have its own child nodes. Ideally, the tree would be structured so that it is a perfectly balanced tree, with each node having the same number of child nodes to its left and to its right. A perfectly balanced tree allows for the fastest average insertion of data or retrieval of data. The worst case scenario is a tree in which each node only has one child node, so it becomes as if it were a linked list in terms of speed. The typical representation of a binary tree looks like the following:

   
             10
           /    \
          6      14
         / \    /  \
        5   8  11  18

The node storing the 10, represented here merely as 10, is the root node, linking to the left and right child nodes, with the left node storing a lower value than the parent node, and the node on the right storing a greater value than the parent node. Notice that if one removed the root node and the right child nodes, that the node storing the value 6 would be the equivalent a new, smaller, binary tree.
The structure of a binary tree makes the insertion and search functions simple to implement using recursion. In fact, the two insertion and search functions are also both very similar. To insert data into a binary tree involves a function searching for an unused node in the proper position in the tree in which to insert the key value. The insert function is generally a recursive function that continues moving down the levels of a binary tree until there is an unused leaf in a position which follows the rules of placing nodes. The rules are that a lower value should be to the left of the node, and a greater or equal value should be to the right. Following the rules, an insert function should check each node to see if it is empty, if so, it would insert the data to be stored along with the key value (in most implementations, an empty node will simply be a NULL pointer from a parent node, so the function would also have to create the node). If the node is filled already, the insert function should check to see if the key value to be inserted is less than the key value of the current node, and if so, the insert function should be recursively called on the left child node, or if the key value to be inserted is greater than or equal to the key value of the current node the insert function should be recursively called on the right child node. The search function works along a similar fashion. It should check to see if the key value of the current node is the value to be searched. If not, it should check to see if the value to be searched for is less than the value of the node, in which case it should be recursively called on the left child node, or if it is greater than the value of the node, it should be recursively called on the right child node. Of course, it is also necessary to check to ensure that the left or right child node actually exists before calling the function on the node.
Because binary trees have log (base 2) n layers, the average search time for a binary tree is log (base 2) n. To fill an entire binary tree, sorted, takes roughly log (base 2) n * n. Lets take a look at the necessary code for a simple implementation of a binary tree. First, it is necessary to have a struct, or class, defined as a node.

struct node
{
 int key_value;
 node *left;
 node *right;
};

The struct has the ability to store the key_value and contains the two child nodes which define the node as part of a tree. In fact, the node itself is very similar to the node in a linked list. A basic knowledge of the code for a linked list will be very helpful in understanding the techniques of binary trees. Essentially, pointers are necessary to allow the arbitrary creation of new nodes in the tree.
It is most logical to create a binary tree class to encapsulate the workings of the tree into a single area, and also making it reusable. The class will contain functions to insert data into the tree and to search for data. Due to the use of pointers, it will be necessary to include a function to delete the tree in order to conserve memory after the program has finished.

 
class btree
{
   public:
       btree();
       ~btree();

       void insert(int key);
       node *search(int key);
       void destroy_tree();

   private:
       void destroy_tree(node *leaf);
       void insert(int key, node *leaf);
       node *search(int key, node *leaf);
      
       node *root;
};

The insert and search functions that are public members of the class are designed to allow the user of the class to use the class without dealing with the underlying design. The insert and search functions which will be called recursively are the ones which contain two parameters, allowing them to travel down the tree. The destroy_tree function without arguments is a front for the destroy_tree function which will recursively destroy the tree, node by node, from the bottom up.
The code for the class would look similar to the following:

btree::btree()
{
 root=NULL;
}

It is necessary to initialize root to NULL for the later functions to be able to recognize that it does not exist.

btree::~btree()
{
 destroy_tree();
}

The destroy_tree function will set off the recursive function destroy_tree shown below which will actually delete all nodes of the tree.

void btree::destroy_tree(node *leaf)
{
 if(leaf!=NULL)
 {
   destroy_tree(leaf->left);
   destroy_tree(leaf->right);
   delete leaf;
 }
}

The function destroy_tree goes to the bottom of each part of the tree, that is, searching while there is a non-null node, deletes that leaf, and then it works its way back up. The function deletes the leftmost node, then the right child node from the leftmost node's parent node, then it deletes the parent node, then works its way back to deleting the other child node of the parent of the node it just deleted, and it continues this deletion working its way up to the node of the tree upon which delete_tree was originally called. In the example tree above, the order of deletion of nodes would be 5 8 6 11 18 14 10. Note that it is necessary to delete all the child nodes to avoid wasting memory.

void btree::insert(int key, node *leaf)
{
 if(key<>key_value)
 {
   if(leaf->left!=NULL)
    insert(key, leaf->left);
   else
   {
     leaf->left=new node;
     leaf->left->key_value=key;
     leaf->left->left=NULL;    //Sets the left child of the child node to null
     leaf->left->right=NULL;   //Sets the right child of the child node to null
   } 
 }
 else if(key>=leaf->key_value)
 {
   if(leaf->right!=NULL)
     insert(key, leaf->right);
   else
   {
     leaf->right=new node;
     leaf->right->key_value=key;
     leaf->right->left=NULL;  //Sets the left child of the child node to null
     leaf->right->right=NULL; //Sets the right child of the child node to null
   }
 }
}

The case where the root node is still NULL will be taken care of by the insert function that is nonrecursive and available to non-members of the class. The insert function searches, moving down the tree of children nodes, following the prescribed rules, left for a lower value to be inserted and right for a greater value, until it finds an empty node which it creates using the 'new' keyword and initializes with the key value while setting the new node's child node pointers to NULL. After creating the new node, the insert function will no longer call itself.

node *btree::search(int key, node *leaf)
{
 if(leaf!=NULL)
 {
   if(key==leaf->key_value)
     return leaf;
   if(keykey_value)
     return search(key, leaf->left);
   else
     return search(key, leaf->right);
 }
 else return NULL;
}

The search function shown above recursively moves down the tree until it either reaches a node with a key value equal to the value for which the function is searching or until the function reaches an uninitialized node, meaning that the value being searched for is not stored in the binary tree. It returns a pointer to the node to the previous instance of the function which called it, handing the pointer back up to the search function accessible outside the class.

void btree::insert(int key)
{
 if(root!=NULL)
   insert(key, root);
 else
 {
   root=new node;
   root->key_value=key;
   root->left=NULL;
   root->right=NULL;
 }
}

The public version of the insert function takes care of the case where the root has not been initialized by allocating the memory for it and setting both child nodes to NULL and setting the key_value to the value to be inserted. If the root node already exists, insert is called with the root node as the initial node of the function, and the recursive insert function takes over.

node *btree::search(int key)
{
 return search(key, root);
}

The public version of the search function is used to set off the search recursion at the root node, keeping it from being necessary for the user to have access to the root node.

void btree::destroy_tree()
{
 destroy_tree(root);
}

The public version of the destroy tree function is merely used to initialize the recursive destroy_tree function which then deletes all the nodes of the tree.

array

Arrays are useful critters because they can be used in many ways. For example, a tic-tac-toe board can be held in an array. Arrays are essentially a way to store many values under the same name. You can make an array out of any data-type including structures and classes.

Think about arrays like this:


[][][][][][]

Each of the bracket pairs is a slot(element) in the array, and you can put information into each one of them. It is almost like having a group of variables side by side.

Lets look at the syntax for declaring an array.

int examplearray[100]; // This declares an array

This would make an integer array with 100 slots, or places to store values(also called elements). To access a specific part element of the array, you merely put the array name and, in brackets, an index number. This corresponds to a specific element of the array. The one trick is that the first index number, and thus the first element, is zero, and the last is the number of elements minus one. 0-99 in a 100 element array, for example.

What can you do with this simple knowledge? Lets say you want to store a string, because C had no built-in datatype for strings, it was common to use arrays of characters to simulate strings. (C++ now has a string type as part of the standard library.)

For example:

char astring[100];

will allow you to declare a char array of 100 elements, or slots. Then you can receive input into it it from the user, and if the user types in a long string, it will go in the array. The neat thing is that it is very easy to work with strings in this way, and there is even a header file called cstring. There is another lesson on the uses of strings, so its not necessary to discuss here.

The most useful aspect of arrays is multidimensional arrays. How I think about multi-dimensional arrays:

[][][][][]
[][][][][]
[][][][][]
[][][][][]
[][][][][]

This is a graphic of what a two-dimensional array looks like when I visualize it.

For example:

int twodimensionalarray[8][8];

declares an array that has two dimensions. Think of it as a chessboard. You can easily use this to store information about some kind of game or to write something like tic-tac-toe. To access it, all you need are two variables, one that goes in the first slot and one that goes in the second slot. You can even make a three dimensional array, though you probably won't need to. In fact, you could make a four-hundred dimensional array. It would be confusing to visualize, however. Arrays are treated like any other variable in most ways. You can modify one value in it by putting:

arrayname[arrayindexnumber] = whatever;

or, for two dimensional arrays

arrayname[arrayindexnumber1][arrayindexnumber2] = whatever;

However, you should never attempt to write data past the last element of the array, such as when you have a 10 element array, and you try to write to the [10] element. The memory for the array that was allocated for it will only be ten locations in memory, but the next location could be anything, which could crash your computer.

You will find lots of useful things to do with arrays, from storing information about certain things under one name, to making games like tic-tac-toe. One suggestion I have is to use for loops when access arrays.

#include 

using namespace std;

int main()
{
int x;
int y;
int array[8][8]; // Declares an array like a chessboard

for ( x = 0; x < y =" 0;" x =" 0;" y =" 0;"><<"]["<<<"]="<<>

Here you see that the loops work well because they increment the variable for you, and you only need to increment by one. Its the easiest loop to read, and you access the entire array.

One thing that arrays don't require that other variables do, is a reference operator when you want to have a pointer to the string. For example:

char *ptr;
char str[40];
ptr = str;  // Gives the memory address without a reference operator(&)

As opposed to

int *ptr;
int num;
ptr = # // Requires & to give the memory address to the ptr

The reason for this is that when an array name is used as an expression, it refers to a pointer to the first element, not the entire array.

Recursion

Recursion is a programming technique that allows the programmer to express operations in terms of themselves. In C++, this takes the form of a function that calls itself. A useful way to think of recursive functions is to imagine them as a process being performed where one of the instructions is to "repeat the process". This makes it sound very similar to a loop because it repeats the same code, and in some ways it is similar to looping. On the other hand, recursion makes it easier to express ideas in which the result of the recursive call is necessary to complete the task. Of course, it must be possible for the "process" to sometimes be completed without the recursive call. One simple example is the idea of building a wall that is ten feet high; if I want to build a ten foot high wall, then I will first build a 9 foot high wall, and then add an extra foot of bricks. Conceptually, this is like saying the "build wall" function takes a height and if that height is greater than one, first calls itself to build a lower wall, and then adds one a foot of bricks.



A simple example of recursion would be:

void recurse()
{
recurse(); //Function calls itself
}

int main()
{
recurse(); //Sets off the recursion
}

This program will not continue forever, however. The computer keeps function calls on a stack and once too many are called without ending, the program will crash. Why not write a program to see how many times the function is called before the program terminates?

#include 

using namespace std;

void recurse ( int count ) // Each call gets its own count
{
cout<<>

This simple program will show the number of times the recurse function has been called by initializing each individual function call's count variable one greater than it was previous by passing in count + 1. Keep in mind, it is not a function restarting itself, it is hundreds of functions that are each unfinished with the last one calling a new recurse function.

It can be thought of like the Russian dolls that always have a smaller doll inside. Each doll calls another doll, and you can think of the size being a counter variable that is being decremented by one.

Think of a really tiny doll, the size of a few atoms. You can't get any smaller than that, so there are no more dolls. Normally, a recursive function will have a variable that performs a similar action; one that controls when the function will finally exit. The condition where the functin will not call itself is termed the base case of the function. Basically, it is an if-statement that checks some variable for a condition (such as a number being less than zero, or greater than some other number) and if that condition is true, it will not allow the function to call itself again. (Or, it could check if a certain condition is true and only then allow the function to call itself).

A quick example:

void doll ( int size )
{
if ( size == 0 )   // No doll can be smaller than 1 atom (10^0==1) so doesn't call itself
  return;          // Return does not have to return something, it can be used
                   //  to exit a function
doll ( size - 1 ); // Decrements the size variable so the next doll will be smaller.
}
int main()
{
doll ( 10 ); //Starts off with a large doll (its a logarithmic scale)
}

This program ends when size equals one. This is a good base case, but if it is not properly set up, it is possible to have an base case that is always true (or always false).

Once a function has called itself, it will be ready to go to the next line after the call. It can still perform operations. One function you could write could print out the numbers 123456789987654321. How can you use recursion to write a function to do this? Simply have it keep incrementing a variable passed in, and then output the variable...twice, once before the function recurses, and once after...

void printnum ( int begin )
{
cout<<>

This function works because it will go through and print the numbers begin to 9, and then as each printnum function terminates it will continue printing the value of begin in each function from 9 to begin.

This is just the beginning of the usefulness of recursion. Heres a little challenge, use recursion to write a program that returns the factorial of any number greater than 0. (Factorial is number*number-1*number-2...*1).

Hint: Recursively find the factorial of the smaller numbers first, ie, it takes a number, finds the factorial of the previous number, and multiplies the number times that factorial...have fun. :-)

If statements

The ability to control the flow of your program, letting it make decisions on what code to execute, is valuable to the programmer. The if statement allows you to control if a program enters a section of code or not based on whether a given condition is true or false. One of the important functions of the if statement is that it allows the program to select an action based upon the user's input. For example, by using an if statement to check a user entered password, your program can decide whether a user is allowed access to the program.

Without a conditional statement such as the if statement, programs would run almost the exact same way every time. If statements allow the flow of the program to be changed, and so they allow algorithms and more interesting code.

Before discussing the actual structure of the if statement, let us examine the meaning of TRUE and FALSE in computer terminology. A true statement is one that evaluates to a nonzero number. A false statement evaluates to zero. When you perform comparison with the relational operators, the operator will return 1 if the comparison is true, or 0 if the comparison is false. For example, the check 0 == 2 evaluates to 0. The check 2 == 2 evaluates to a 1. If this confuses you, try to use a cout statement to output the result of those various comparisons (for example cout<< ( 2 == 1 );) When programming, the aim of the program will often require the checking of one value stored by a variable against another value to determine whether one is larger, smaller, or equal to the other. There are a number of operators that allow these checks. Here are the relational operators, as they are known, along with examples:

>     greater than              5 > 4 is TRUE
<>=    greater than or equal     4 >= 4 is TRUE
<=    less than or equal        3 <= 4 is TRUE ==    equal to                  5 == 5 is TRUE !=    not equal to  5 != 4 is TRUE

It is highly probable that you have seen these before, probably with
slightly different symbols. They should not present any hindrance to
understanding. Now that you understand TRUE and FALSE in computer
terminology as well as the comparison operators, let us look at the
actual structure of if statements.



The structure of an if statement is as follows:

if ( TRUE )
 Execute the next statement

To have more than one statement execute after an if statement that
evaluates to true, use braces, like we did with the body of a function.
Anything inside braces is called a compound statement, or a block.

For example:

if ( TRUE ) {
 Execute all statements inside the braces
}

There is also the else statement. The code after it (whether a single
line or code between brackets) is executed if the if statement is
FALSE.

It can look like this:

if ( TRUE ) {
 // Execute these statements if TRUE
}
else {
 // Execute these statements if FALSE
}

One use for else is if there are two conditional statements that may
both evaluate to true, yet you wish only one of the two to have the
code block following it to be executed. You can use an else if after
the if statement; that way, if the first statement is true, the else if
will be ignored, but if the if statement is false, it will then check
the condition for the else if statement. If the if statement was true
the else statement will not be checked. It is possible to use numerous
else if statements.

Let's look at a simple program for you to try out on your own.


#include  

using namespace std;
  
int main()                            // Most important part of the program!
{
 int age;                            // Need a variable...

 cout<<"Please input your age: ";    // Asks for age
 cin>> age;                          // The input is put in age
 cin.ignore();                       // Throw away enter
 if ( age < 100 ) {                  // If the age is less than 100
    cout<<"You are pretty young!\n"; // Just to show you it works...
 }
 else if ( age == 100 ) {            // I use else just to show an example
    cout<<"You are old\n";           // Just to show you it works...
 }
 else {
   cout<<"You are really old\n";     // Executed if no other statement is
 }
 cin.get();
}


Boolean operators allow you to create more complex conditional
statements. For example, if you wish to check if a variable is both
greater than five and less than ten, you could use the boolean AND to
ensure both var > 5 and var < 10 are true. In the following
discussion of boolean operators, I will capitalize the boolean
operators in order to distinguish them from normal english. The actual
C++ operators of equivalent function will be described further into the
tutorial - the C++ symbols are not: OR, AND, NOT, although they are of
equivalent function.


When using if statements, you will often wish to check
multiple different conditions. You must understand the Boolean
operators OR, NOT, and AND. The boolean operators function in a similar
way to the comparison operators: each returns 0 if evaluates to FALSE
or 1 if it evaluates to TRUE.


NOT: The NOT operator accepts one input. If that input is
TRUE, it returns FALSE, and if that input is FALSE, it returns TRUE.
For example, NOT (1) evalutes to 0, and NOT (0) evalutes to 1. NOT (any
number but zero) evaluates to 0. In C and C++ NOT is written as !. NOT
is evaluated prior to both AND and OR.

AND: This is another important command. AND returns TRUE if
both inputs are TRUE (if 'this' AND 'that' are true). (1) AND (0) would
evaluate to zero because one of the inputs is false (both must be TRUE
for it to evaluate to TRUE). (1) AND (1) evaluates to 1. (any number
but 0) AND (0) evaluates to 0. The AND operator is written &&
in C++. Do not be confused by thinking it checks equality between
numbers: it does not. Keep in mind that the AND operator is evaluated
before the OR operator.


OR: Very useful is the OR statement! If either (or both) of
the two values it checks are TRUE then it returns TRUE. For example,
(1) OR (0) evaluates to 1. (0) OR (0) evaluates to 0. The OR is written
as || in C++. Those are the pipe characters. On your keyboard, they may
look like a stretched colon. On my computer the pipe shares its key
with \. Keep in mind that OR will be evaluated after AND.


It is possible to combine several boolean operators in a
single statement; often you will find doing so to be of great value
when creating complex expressions for if statements. What is !(1
&& 0)? Of course, it would be TRUE. It is true is because 1
&& 0 evaluates to 0 and !0 evaluates to TRUE (ie, 1).


Try some of these - they're not too hard. If you have questions about them, feel free to stop by our forums.

A. !( 1 || 0 )         ANSWER: 0 
B. !( 1 || 1 && 0 )    ANSWER: 0 (AND is evaluated before OR)
C. !( ( 1 || 0 ) && 0 )  ANSWER: 1 (Parenthesis are useful)

If you find you enjoyed this section, then you might want to look more at Boolean Algebra.

Loops in C++

Loops are used to repeat a block of code. You should understand the concept of C++'s true and false, because it will be necessary when working with loops (the conditions are the same as with if statements). There are three types of loops: for, while, and do..while. Each of them has their specific uses. They are all outlined below.

FOR
for loops are the most useful type. The layout is

for ( variable initialization; condition; variable update ) {
Code to execute while the condition is true
}

The variable initialization allows you to either declare a variable and give it a value or give a value to an already existing variable. Second, the condition tells the program that while the conditional expression is true the loop should continue to repeat itself. The variable update section is the easiest way for a for loop to handle changing of the variable. It is possible to do things like x++, x = x + 10, or even x = random ( 5 ), and if you really wanted to, you could call other functions that do nothing to the variable but still have a useful effect on the code. Notice that a semicolon separates each of these sections, that is important. Also note that every single one of the sections may be empty, though the semicolons still have to be there. If the condition is empty, it is evaluated as true and the loop will repeat until something else stops it.

Example:

#include 

using namespace std; // So the program can see cout and endl

int main()
{
// The loop goes while x < x =" 0;">

This program is a very simple example of a for loop. x is set to zero, while x is less than 10 it calls cout<< and="" it="" adds="" 1="" to="" x="" until="" condition="" keep="" mind="" also="" that="" variable="" incremented="" after="" code="" in="" loop="" is="" run="" for="" the="" first=""> WHILE
WHILE loops are very simple. The basic structure is

while ( condition ) { Code to execute while the condition is true } The true represents a boolean expression which could be x == 1 or while ( x != 7 ) (x does not equal 7). It can be any combination of boolean statements that are legal. Even, (while x = =5 || v == 7) which says execute the code while x equals five or while v equals 7. Notice that a while loop is the same as a for loop without the initialization and update sections. However, an empty condition is not legal for a while loop as it is with a for loop.

Example:

#include 

using namespace std; // So we can see cout and endl

int main()
{
int x = 0;  // Don't forget to declare variables

while ( x < update="" x="" so="" the="" condition="" can="" be="" met="" eventually="">

This was another simple example, but it is longer than the above FOR
loop. The easiest way to think of the loop is that when it reaches the
brace at the end it jumps back up to the beginning of the loop, which
checks the condition again and decides whether to repeat the block
another time, or stop and move to the next statement after the block.

DO..WHILE
DO..WHILE loops are useful for things that want to loop at least once. The structure is

do {
} while ( condition );

Notice that the condition is tested at the end of the block instead of
the beginning, so the block will be executed at least once. If the
condition is true, we jump back to the beginning of the block and
execute it again. A do..while loop is basically a reversed while loop.
A while loop says "Loop while the condition is true, and execute this
block of code", a do..while loop says "Execute this block of code, and
loop while the condition is true".

Example:

#include 

using namespace std;

int main()
{
 int x;

 x = 0;
 do {
   // "Hello, world!" is printed at least one time
   //  even though the condition is false
   cout<<"Hello, world!\n";
 } while ( x != 0 );
 cin.get();


}

Keep in mind that you must include a trailing semi-colon after the while in the above example. A common error is to forget that a do..while loop must be terminated with a semicolon (the other loops should not be terminated with a semicolon, adding to the confusion). Notice that this loop will execute once, because it automatically executes before checking the condition.