There are two almost identical ways to access characters in a string. The easier to use and faster version is the overloaded operator[]:

string sSource("abcdefg");
cout << sSource[5] << endl;
sSource[5] = 'X';
cout << sSource << endl;

f
abcdeXg

There is also a non-operator version. This version is slower since it uses exceptions to check if the nIndex is valid. If you are not sure whether nIndex is valid, you should use this version to access the array:

string sSource("abcdefg");
cout << sSource.at(5) << endl;
sSource.at(5) = 'X';
cout << sSource << endl;

f
abcdeXg

Conversion to C-style arrays

Many functions (including all C functions) expect strings to be formatted as C-style strings rather than std::string. For this reason, std::string provides 3 different ways to convert std::string to C-style strings.

string sSource("abcdefg");
cout << strlen(sSource.c_str());

7

string sSource("abcdefg");
char *szString = "abcdefg";
// memcmp compares the first n characters of two C-style strings and returns 0 if they are equal
if (memcmp(sSource.data(), szString, sSource.length()) == 0)
    cout << "The strings are equal";
else
    cout << "The strings are not equal";

The strings are equal

string sSource("sphinx of black quartz, judge my vow");

char szBuf[20];
int nLength = sSource.copy(szBuf, 5, 10);
szBuf[nLength]='\0';  // Make sure we terminate the string in the buffer

cout << szBuf << endl;

black

Unless you need every bit of efficiency, c_str() is the easiest and safest of the three functions to use.

Index

17.3 — std::string length and capacity

Length of a string

The length of the string is quite simple — it’s the number of characters in the string. There are two identical functions for determining string length:

string sSource("012345678");
cout << sSource.length() << endl;

9

Although it’s possible to use length() to determine whether a string has any characters or not, it’s more efficient to use the empty() function:

string sString1("Not Empty");
cout << (sString1.empty() ? "true" : "false") << endl;
string sString2; // empty
cout << (sString2.empty() ? "true" : "false")  << endl;

false
true

There is one more size-related function that you will probably never use, but we’ll include it here for completeness:

string sString("MyString");
cout << sString.max_size() << endl;

4294967294

Capacity of a string

The capacity of a string reflects how much memory the string allocated to hold it’s contents. This value is measured in string characters, excluding the NULL terminator. For example, a string with capacity 8 could hold 8 characters.

string sString("01234567");
cout << "Length: " << sString.length() << endl;
cout << "Capacity: " << sString.capacity() << endl;

Length: 8
Capacity: 15

Note that the capacity is higher than the length of the string! Although our string was length 8, the string actually allocated enough memory for 15 characters! Why was this done?

The important thing to recognize here is that if a user wants to put more characters into a string than the string has capacity for, the string has to be reallocated to a larger capacity. For example, if a string had both length and capacity of 8, then adding any characters to the string would force a reallocation. By making the capacity larger than the actual string, this gives the user some buffer room to expand the string before reallocation needs to be done.

As it turns out, reallocation is bad for several reasons:

First, reallocating a string is comparatively expensive. First, new memory has to be allocated. Then each character in the string has to be copied to the new memory. This can take a long time if the string is big. Finally, the old memory has to be deallocated. If you are doing many reallocations, this process can slow your program down significantly.

Second, whenever a string is reallocated, the contents of the string change to a new memory address. This means all references, pointers, and iterators to the string become invalid!

Note that it’s not always the case that strings will be allocated with capacity greater than length. Consider the following program:

string sString("0123456789abcde");
cout << "Length: " << sString.length() << endl;
cout << "Capacity: " << sString.capacity() << endl;

This program outputs:

Length: 15
Capacity: 15

(Results may vary depending on compiler).

Let’s add one character to the string and watch the capacity change:

string sString("0123456789abcde");
cout << "Length: " << sString.length() << endl;
cout << "Capacity: " << sString.capacity() << endl;

// Now add a new character
sString += "f";
cout << "Length: " << sString.length() << endl;
cout << "Capacity: " << sString.capacity() << endl;

This produces the result:

Length: 15
Capacity: 15
Length: 16
Capacity: 31

string sString("01234567");
cout << "Length: " << sString.length() << endl;
cout << "Capacity: " << sString.capacity() << endl;

sString.reserve(200);
cout << "Length: " << sString.length() << endl;
cout << "Capacity: " << sString.capacity() << endl;

sString.reserve();
cout << "Length: " << sString.length() << endl;
cout << "Capacity: " << sString.capacity() << endl;

Length: 8
Capacity: 15
Length: 8
Capacity: 207
Length: 8
Capacity: 207

This example shows two interesting things. First, although we requested a capacity of 200, we actually got a capacity of 207. The capacity is always guaranteed to be at least as large as your request, but may be larger. We then requested the capacity change to fit the string. This request was ignored, as the capacity did not change.

If you know in advance that you’re going to be constructing a large string by doing lots of string operations that will add to the size of the string, you can avoid having the string reallocated multiple times by immediately setting the string to it’s final capacity:

#include <iostream>
#include <string>
#include <cstdlib> // for rand() and srand()
#include <ctime> // for time()

using namespace std;

int main()
{
    srand(time(0)); // seed random number generator

    string sString; // length 0
    sString.reserve(64); // reserve 64 characters

    // Fill string up with random lower case characters
    for (int nCount=0; nCount < 64; ++nCount)
        sString += 'a' + rand() % 26;

    cout << sString;
}

The result of this program will change each time, but here’s the output from one execution:

wzpzujwuaokbakgijqdawvzjqlgcipiiuuxhyfkdppxpyycvytvyxwqsbtielxpy

Rather than having to reallocate sString multiple times, we set the capacity once and then fill the string up. This can make a huge difference in performance when constructing large strings via concatenation.

17.4 — std::string character access and conversion to C-style arrays

Index

17.2 — std::string construction and destruction

String construction

The string classes have a number of constructors that can be used to create strings. We’ll take a look at each of them here.

Note: string::size_type resolves to size_t, which is the same unsigned integral type that is returned by the sizeof operator. It’s actual size varies depending on environment. For purposes of this tutorial, envision it as an unsigned int.

std::string sSource;
cout << sSource;

string sSource("my string");
string sOutput(sSource);
cout << sOutput;

my string

string sSource("my string");
string sOutput(sSource, 3);
cout << sOutput<< endl;
string sOutput2(sSource, 3, 4);
cout << sOutput2 << endl;

string
stri

const char *szSource("my string");
string sOutput(szSource);
cout << sOutput << endl;

my string

const char *szSource("my string");
string sOutput(szSource, 4);
cout << sOutput << endl;

my s

string sOutput(4, 'Q');
cout << sOutput << endl;

QQQQ

Constructing strings from numbers

One notable omission in the std::string class is the lack of ability to create strings from numbers. For example:

    string sFour(4);

Produces the following error:

c:\vcprojects\test2\test2\test.cpp(10) : error C2664: 'std::basic_string<_Elem,_Traits,_Ax>::basic_string(std::basic_string<_Elem,_Traits,_Ax>::_Has_debug_it)' : cannot convert parameter 1 from 'int' to 'std::basic_string<_Elem,_Traits,_Ax>::_Has_debug_it'

Remember what I said about the string classes producing horrible looking errors? The relevant bit of information here is:

cannot convert parameter 1 from 'int' to 'std::basic_string

In other words, it tried to convert your int into a string but failed.

The easiest way to convert numbers into strings is to involve the std::ostringstream class. std::ostringstream is already set up to accept input from a variety of sources, including characters, numbers, strings, etc… It is also capable of outputting strings (either via the extraction operator>>, or via the str() function). For more information on std::ostringstream, see Lesson 13.4 — Stream classes for strings.

Here’s a simple solution for creating std::string from various types of inputs:

#include <iostream>
#include <sstream>
#include <string>

template <typename T>
inline std::string ToString(T tX)
{
    std::ostringstream oStream;
    oStream << tX;
    return oStream.str();
}

Here’s some sample code to test it:

int main()
{
    string sFour(ToString(7));
    string sSixPointSeven(ToString(6.7));
    string sA(ToString('A'));
    cout << sFour << endl;
    cout << sSixPointSeven << endl;
    cout << sA << endl;
}

And the output:

4
6.7
A

Note that this solution omits any error checking. It is possible that inserting tX into oStream could fail. An appropriate response would be to throw an exception if the conversation fails.

Converting strings to numbers

Similar to the solution above:

#include <iostream>
#include <sstream>
#include <string>

template <typename T>
inline bool FromString(const std::string& sString, T &tX)
{
    std::istringstream iStream(sString);
    return (iStream >> tX) ? true : false;
}

Here’s some sample code to test it:

int main()
{
    double dX;
    if (FromString("3.4", dX))
        cout << dX << endl;
    if (FromString("ABC", dX))
        cout << dX << endl;
}

And the output:

3.4

Note that the second conversation failed and returned false.

17.3 — std::string length and capacity

Index

17.1 — std::string and std::wstring

Note: C-style strings will be referred to as “C-style strings”, whereas std::strings (and std::wstring) will be referred to simply as “strings”.

Motivation for a string class

In a previous lesson, we covered C-style strings, which using char arrays to store a string of characters. If you’ve tried to do anything with C-style strings, you’ll very quickly come to the conclusion that they are a pain to work with, easy to mess up, and hard to debug.

C-style strings have many shortcomings, primarily revolving around the fact that you have to do all the memory management yourself. For example, if you want to assign the string “hello!” into a buffer, you have to first dynamically allocate a buffer of the correct length:

char *strHello = new char(7);

Don’t forget to account for an extra character for the null terminator!

Then you have to actually copy the value in:

strcpy(strHello, "hello!");

Hopefully you made your buffer large enough so there’s no buffer overflow!

And of course, because the string is dynamically allocated, you have to remember to deallocate it properly when you’re done with it:

delete[] strHello;

Don’t forget to use array delete instead of normal delete!

Furthermore, many of the intuitive operators that C provides to work with numbers, such as assignment and comparisons, simply don’t work with C-style strings. Sometimes these will appear to work but actually produce incorrect results — for example, comparing two C-style strings using == will actually do a pointer comparison, not a string comparison. Assigning one C-style string to another using operator= will appear to work at first, but is actually doing a pointer copy (shallow copy), which is not generally what you want. These kinds of things can lead to program crashes that are very hard to find and debug!

The bottom line is that working with C-style strings requires remembering a lot of nit-picky rules about what is safe/unsafe, memorizing a bunch of functions that have funny names like strcat() and strcmp() instead of using intuitive operators, and doing lots of manual memory management.

Fortunately, C++ and the standard library provide a much better way to deal with strings: the std::string and std::wstring classes. By making use of C++ concepts such as constructors, destructors, and operator overloading, std::string allows you to create and manipulate strings in an intuitive and safe manner! No more memory management, no more weird function names, and a much reduced potential for disaster.

Sign me up!

String overview

All string functionality in the standard library lives in the <string> header file. To use it, simply include the string header:

    #include <string>

There are actually 3 different string classes in the string header. The first is a templated base class named basic_string<>:

namespace std
{
    template<class charT, class traits = char_traits<charT>, class Allocator = allocator<charT> >
        class basic_string;
}

You won’t be working with this class directly, so don’t worry about what traits or an Allocator is for the time being. The default values will suffice in almost every imaginable case.

There are two specializations of basic_string<> provided by the standard library:

namespace std
{
    typedef basic_string<char> string;
    typedef basic_string<wchar_t> wstring;
}

These are the two classes that you will actually use. std::string is used for standard ascii (utf-8) strings. std::wstring is used for wide-character/unicode (utf-16) strings. There is no built-in class for utf-32 strings (though you should be able to extend your own from basic_string<> if you need one).

Although you will directly use std::string and std::wstring, it turns out that all of the string functionality is actually implemented in the basic_string<> class and then inherited by string and wstring. Consequently, all of the functions presented will work for both string and wstring. However, because basic_string is a templated class, it also means the compiler will produce horrible looking template errors when you do something syntactically incorrect with a string or wstring. Don’t be intimidated by these errors; they look far worse than they are!

Here’s a list of all the functions in the string class. Most of these functions have multiple flavors to handle different types of inputs, which we will cover in more depth in the next lessons.

While the standard library string classes provide a lot of functionality, there are a few notable omissions:

• Regular expression support
• Constructors for creating strings from numbers
• Capitalization / upper case / lower case functions
• Case-insensitive comparisons
• Tokenization / splitting string into array
• Easy functions for getting the left or right hand portion of string
• Whitespace trimming
• Formatting a string sprintf style
• Conversion from utf-8 to utf-16 or vice-versa

For most of these, you will have to either write your own functions, or convert your string to a C-style string (using c_str()) and use the C functions that offer this functionality.

In the next lessons, we will look at the various functions of the string class in more depth. Although we will use string for our examples, everything is equally applicable to wstring.

17.2 — std::string construction and destruction

Index

15.6 — Exceptions dangers and downsides

The most important thing to remember (and hardest thing to do) is to design your program before you start coding. In many regards, programming is like architecture. What would happen if you tried to build a house without following an architectural plan? Odds are, unless you were very talented, you’d end up with a house that had a lot of problems: leaky roofs, walls that weren’t straight, etc… Similarly, if you try to program before you have a good gameplan moving forward, you’ll likely find that your code has a lot of problems, and you’ll have to spend a lot of time fixing problems that could have been avoided altogether with a little design.

A little up-front planning will save you both time and frustration in the long run.

Step 1: Define the problem

The first thing you need to figure out is what problem your program is attempting to solve. Ideally, you should be able to state this in a sentence or two. For example:

• I want to write a phone book application to help me keep track of my friend’s phone numbers.
• I want to write a random dungeon generator that will produce interesting looking caverns.
• I want to write a program that will take information about stocks and attempt to predict which ones I should buy.

Although this step seems obvious, it’s also highly important. The worst thing you can do is write a program that doesn’t actually do what you (or your boss) wanted!

Step 2: Define your targets

When you are an experienced programmer, there are many other steps that typically would take place at this point, including:

• Understanding who your target user is
• Defining what target architecture and/or OS your program will run on
• Determining what set of tools you will be using
• Determining whether you will write your program alone or as part of a team
• Collecting requirements (a documented list of what the program should do)

However, as a new programmer, the answers to these questions are typically simple: You are writing a program for your own use, alone, on your own system, using an IDE you purchased or downloaded. This makes things easy, so we won’t spend any time on this step.

Step 3: Make a heirarchy of tasks

In real life, we often need to perform tasks that are very complex. Trying to figure out how to do these tasks can be very challenging. In such cases, we often make use of the top down method of problem solving. That is, instead of solving a single complex task, we break that task into multiple subtasks, each of which is individually easier to solve. If those subtasks are still too difficult to solve, they can be broken down further. By continuously splitting complex tasks into simpler ones, you can eventually get to a point where each individual task is manageable, if not trivial.

Let’s take a look at an example of this. Let’s say we want to write a report on carrots. Our task hierarchy currently looks like this:

• Write report on carrots

Writing a report on carrots is a pretty big task to do in one sitting, so let’s break it into subtasks:

• Write report on carrots
• Do research on carrots
• Write outline
• Fill in outline with details about carrots

That’s a more managable, as we now have three tasks that we can focus on individually. However, in this case, “Do research on carrots is somewhat vague”, so we can break it down further:

• Write report on carrots
• Do research on carrots
• Go to library and get book on carrots
• Look for information about carrots on internet
• Write outline
• Information about growing
• Information about processing
• Information about nutrition
• Fill in outline with details about carrots

Now we have a hierarchy of tasks, none of them particularly hard. By completing each of these relatively manageable sub-items, we can complete the more difficult overall task of writing a report on carrots.

The other way to create a hierarchy of tasks is to do so from the bottom up. In this method, we’ll start from a list of easy tasks, and construct the hierarchy by grouping them.

As an example, many people have to go to work or school on weekdays, so let’s say we want to solve the problem of “get from bed to work”. If you were asked what tasks you did in the morning to get from bed to work, you might come up with the following list:

• Pick out clothes
• Get dressed
• Eat breakfast
• Drive to work
• Brush your teeth
• Get out of bed
• Prepare breakfast
• Get in your car
• Take a shower

Using the bottom up method, we can organize these into a hierarchy of items by looking for ways to group items with similarities together:

• Get from bed to work
• Bedroom things
• Get out of bed
• Pick out clothes
• Bathroom things
• Take a shower
• Brush your teeth
• Breakfast things
• Prepare breakfast
• Eat breakfast
• Transportation things
• Get in your car
• Drive to work

As it turns out, these task hierarchies are extremely useful in programming, because once you have a task hierarchy, you have essentially defined the structure of your overall program. The top level task (in this case, “Write a report on carrots” or “Get from bed to work”) becomes main() (because it is the main item you are trying to solve). The subitems become functions in the program.

If it turns out that one of the items (functions) is too difficult to implement, simply split that item into multiple subitems, and have that function call multiple subfunctions that implement those new tasks. Eventually you should reach a point where each function in your program is trivial to implement.

Step 4: Figure out the sequence of events

Now that your program has a structure, it’s time to determine how to link all the tasks together. The first step is to determine the sequence of events that will be performed. For example, when you get up in the morning, what order do you do the above tasks? It might look like this:

• Get out of bed
• Pick out clothes
• Take a shower
• Get dressed
• Prepare breakfast
• Eat breakfast
• Brush your teeth
• Get in your car
• Drive to work

If we were writing a calculator, we might do things in this order:

• Get first number from user
• Get mathematical operation from user
• Get second number from user
• Calculate result
• Print result

This list essentially defines what will go into your main() function:

int main()
{
    GetOutOfBed();
    PickOutClothes();
    TakeAShower();
    GetDressed();
    PrepareBreakfast();
    EatBreakfast();
    BrushTeeth();
    GetInCar();
    DriveToWork();
}

Or in the case of the calculator:

int main()
{
    // Get first number from user
    GetUserInput();

    // Get mathematical operation from user
    GetMathematicalOperation();

    // Get second number from user
    GetUserInput();

    // Calculate result
    CalculateResult();

    // Print result
    PrintResult();
}

Step 5: Figure out the data inputs and outputs for each task

Once you have a hierarchy and a sequence of events, the next thing to do is figure out what input data each task needs to operate, and what data it produces (if any). If you already have the input data from a previous step, that input data will become a parameter. If you are calculating output for use by some other function, that output will generally become a return value.

When we are done, we should have prototypes for each function. In case you’ve forgotten, a function prototype is a declaration of a function that includes the function’s name, parameters, and return type, but does not implement the function.

Let’s do a couple examples. GetUserInput() is pretty straightforward. We’re going to get a number from the user and return it back to the caller. Thus, the function prototype would look like this:

int GetUserInput()

In the calculator example, the CalculateResult() function will need to take 3 pieces of input: Two numbers and a mathematical operator. We should already have all three of these by the time we get to the point where this function is called, so these three pieces of data will be function parameters. The CalculateResult() function will calculate the result value, but it does not display the result itself. Consequently, we need to return that result as a return value so that other functions can use it.

Given that, we could write the function prototype like this:

int CalculateResult(int nInput1, char chOperator, int nInput2);

Step 6: Write the task details

In this step, for each task, you will write it’s actual implementation. If you have broken the tasks down into small enough pieces, each task should be fairly simple and straightforward. If a given task still seems overly-complex, perhaps it needs to be broken down into subtasks that can be more easily implemented.

For example:

char GetMathematicalOperation()
{
    char chOperation;
    cin >> chOperation;
    // What if the user enters an invalid character?
    // We'll ignore this possibility for now
    return chOperation;
}

Step 7: Connect the data inputs and outputs

Finally, the last step is to connect up the inputs and outputs of each task in whatever way is appropriate. For example, you might send the output of CalculateResult() into an input of PrintResult(), so it can print the calculated answer. This will often involve the use of intermediary variables to temporary store the result so it can be passed between functions. For example:

// nResult is a temporary value used to transfer the output of CalculateResult()
// into an input of PrintResult()
int nResult = CalculateResult(nInput1, chOperator, nInput2);
PrintResult(nResult);

This tends to be much more readable than the alternative condensed version that doesn’t use a temporary variable:

PrintResult( CalculateResult(nInput1, chOperator, nInput2) );

This is often the hardest step for new programmers to get the hang of.

Words of advice when writing programs

Keep your program simple to start. Often new programmers have a grand vision for all the things they want their program to do. “I want to write a role-playing game with graphics and sound and random monsters and dungeons, with a town you can visit to sell the items that you find in the dungeon” If you try to write something too complex to start, you will become overwhelmed and discouraged at your lack of progress. Instead, make your first goal as simple as possible, something that is definitely within your reach. For example, “I want to be able to display a 2d representation of the world on the screen”.

Add features over time. Once you have your simple program working and working well, then you can add features to it. For example, once you can display your 2d world, add a character who can walk around. Once you can walk around, add walls that can impede your progress. Once you have walls, build a simple town out of them. Once you have a town, add merchants. By adding each feature incrementally your program will get progressively more complex without overwhelming you in the process.

Focus on one area at a time. Don’t try to code everything at once, and don’t divide your attention across multiple tasks. Focus on one task at a time, and see it through to completion as much as is possible. It is much better to have one fully working task and five that haven’t been started yet than six partially-working tasks. If you split your attention, you are more likely to make mistakes and forget important details.

Test each piece of code as you go. New programmers will often write the entire program in one pass. Then when they compile it for the first time, the compiler reports hundreds of errors. This can not only be intimidating, if your code doesn’t work, it may be hard to figure out why. Instead, write a piece of code, and then compile and test it immediately. If it doesn’t work, you’ll know exactly where the problem is, and it will be easy to fix. Once you are sure that the code works, move to the next piece and repeat. It may take longer to finish writing your code, but when you are done the whole thing should work, and you won’t have to spend twice as long trying to figure out why it doesn’t.

Most new programmers will shortcut many of these steps and suggestions (because it seems like a lot of work and/or it’s not as much fun as writing the code). However, for any non-trivial project, following these steps will definitely save you a lot of time in the long run. A little planning up front saves a lot of debugging at the end.

The good news is that once you become comfortable with all of these concepts, they will start coming naturally to you without even thinking about it. Eventually you will get to the point where you can write entire functions without any pre-planning at all.

1.11 — Comprehensive quiz

Index

1.10 — A first look at the preprocessor

Alex

I’ve just upgraded the web site to wordpress 2.7. If you’ve noticed that anything has broken, please report it here.

No additional downtime is expected at this time. :)

Thanks,
Alex

So how do we generate random numbers? In real life, we often generate random results by doing things like flipping a coin, rolling a dice, or shuffling a deck of cards. These events involve so many physical variables (eg. gravity, friction, air resistance, momentum, etc…) that they become almost impossible to predict or control, and produce results that are for all intents and purposes random.

However, computers aren’t designed to take advantage of physical variables — your computer can’t toss a coin, throw a dice, or shuffle real cards. Computers live in a very controlled electrical world where everything is binary (false or true) and there is no in-between. By their very nature, computers are designed to produce results that are as predictable as possible. When you tell the computer to calculate 2 + 2, you ALWAYS want the answer to be 4. Not 3 or 5 on occasion.

Consequently, computers are generally incapable of generating random numbers. Instead, they must simulate randomness, which is most often done using pseudo-random number generators.

A pseudo-random number generator (PRNG) is a program that takes a starting number (called a seed), and performs mathematical operations on it to transform it into some other number that appears to be unrelated to the seed. It then takes that generated number and performs the same mathematical operation on it to transform it into a new number that appears unrelated to the number it was generated from. By continually applying the algorithm to the last generated number, it can generate a series of new numbers that will appear to be random if the algorithm is complex enough.

It’s actually fairly easy to write a PRNG. Here’s a short program that generates 100 pseudo-random numbers:

#include <stdafx.h>
#include <iostream>
using namespace std;

unsigned int PRNG()
{
    // our initial starting seed is 5323
    static unsigned int nSeed = 5323;

    // Take the current seed and generate a new value from it
    // Due to our use of large constants and overflow, it would be
    // very hard for someone to predict what the next number is
    // going to be from the previous one.
    nSeed = (8253729 * nSeed + 2396403);

    // Take the seed and return a value between 0 and 32767
    return nSeed  % 32767;
}

int main()
{
    // Print 100 random numbers
    for (int nCount=0; nCount < 100; ++nCount)
    {
        cout << PRNG() << "\t";

        // If we've printed 5 numbers, start a new column
        if ((nCount+1) % 5 == 0)
            cout << endl;
	}
}

The result of this program is:

20433	22044	9937	30185	29341
14783	29730	8430	3076	28768
18053	16066	26537	100	30493
4943	19511	19251	6669	32117
31575	3373	32383	30496	12710
23999	11929	5425	9938	12107
28541	1938	3450	20283	16726
6440	4938	26094	24391	12248
24803	30416	16244	19590	6644
24646	4873	2841	23831	23476
17958	8827	17400	32129	32760
25744	25405	13591	8859	15932
19086	19666	19265	14179	1165
27168	20996	29427	5857	3434
18964	11980	564	4620	400
17362	16934	11889	419	9714
19808	29699	3694	25612	5512
20256	10009	10247	1860	1846
1487	14030	2615	16035	8107
28736	267	29395	9438	20294

Each number appears to be pretty random with respect to the previous one. As it turns out, our algorithm actually isn’t very good, for reasons we will discuss later. But it does effectively illustrate the principle of PRNG number generation.

Generating random numbers in C++

C (and by extension C++) comes with a built-in pseudo-random number generator. It is implemented as two separate functions that live in the cstdlib header:

srand() sets the initial seed value. srand() should only be called once.

rand() generates the next random number in the sequence (starting from the seed set by srand()).

Here’s a sample program using these functions:

#include <stdafx.h>
#include <iostream>
#include <cstdlib> // for rand() and srand()
using namespace std;

int main()
{
    srand(5323); // set initial seed value to 5323

    // Print 100 random numbers
    for (int nCount=0; nCount < 100; ++nCount)
    {
        cout << rand() << "\t";

        // If we've printed 5 numbers, start a new column
        if ((nCount+1) % 5 == 0)
            cout << endl;
	}
}

Here’s the output of this program:

17421	8558	19487	1344	26934
7796	28102	15201	17869	6911
4981	417	12650	28759	20778
31890	23714	29127	15819	29971
1069	25403	24427	9087	24392
15886	11466	15140	19801	14365
18458	18935	1746	16672	22281
16517	21847	27194	7163	13869
5923	27598	13463	15757	4520
15765	8582	23866	22389	29933
31607	180	17757	23924	31079
30105	23254	32726	11295	18712
29087	2787	4862	6569	6310
21221	28152	12539	5672	23344
28895	31278	21786	7674	15329
10307	16840	1645	15699	8401
22972	20731	24749	32505	29409
17906	11989	17051	32232	592
17312	32714	18411	17112	15510
8830	32592	25957	1269	6793

The range of rand()

rand() generates pseudo-random integers between 0 and RAND_MAX, a constant in cstdlib that is typically set to 32767.

Generally, we do not want random numbers between 0 and RAND_MAX — we want numbers between two other values, which we’ll call nLow and nHigh. For example, if we’re trying to simulate the user rolling a dice, we want random numbers between 1 and 6.

It turns out it’s quite easy to take the result of rand() can convert it into whatever range we want:

// Generate a random number between nLow and nHigh (inclusive)
unsigned int GetRandomNumber(int nLow, int nHigh)
{
    return (rand() % (nHigh - nLow + 1)) + nLow;
}

PRNG sequences

If you run the rand() sample program above multiple times, you will note that it prints the same result every time! This means that while each number in the sequence is seemingly random with regards to the previous ones, the entire sequence is not random at all! And that means our program ends up totally predictable (the same inputs lead to the same outputs every time). There are cases where this can be useful or even desired (eg. you want a scientific simulation to be repeatable, or you’re trying to debug why your random dungeon generator crashes).

But often, this is not what is desired. If you’re writing a game of hi-lo (where the user has 10 tries to guess a number, and the computer tells them whether their guess is too high or to low), you don’t want the program picking the same numbers each time. So let’s take a deeper look at why this is happening, and how we can fix it.

Remember that each number in a PRNG sequence is generated from the previous number, in a deterministic way. Thus, given any starting seed number, PRNGs will always generate the same sequence of numbers from that seed as a result! We are getting the same sequence because our starting seed number is always 5323.

In order to make our entire sequence randomized, we need some way to pick a seed that’s not a fixed number. The first answer that probably comes to mind is that we need a random number! That’s a good thought, but if we need a random number to generate random numbers, then we’re in a catch-22. It turns out, we really don’t need our seed to be a random number — we just need to pick something that changes each time the program is run. Then we can use our PRNG to generate a unique sequence of pseudo-random numbers from that seed.

The commonly accepted method for doing this is to enlist the system clock. Each time the user runs the program, the time will be different. If we use this time value as our seed, then our program will generate a different sequence of numbers each time it is run!

C comes with a function called time() that returns the number of seconds since midnight on Jan 1, 1970. To use it, we merely need to include the ctime header, and then initialize srand() with a call to time(0):

#include <stdafx.h>
#include <iostream>
#include <cstdlib> // for rand() and srand()
#include <ctime> // for time()
using namespace std;

int main()
{

    srand(time(0)); // set initial seed value to system clock
    for (int nCount=0; nCount < 100; ++nCount)
    {
        cout << rand() << "\t";

        if ((nCount+1) % 5 == 0)
            cout << endl;
	}
}

Now our program will generate a different sequence of random numbers every time!

What is a good PRNG?

As I mentioned above, the PRNG we wrote isn’t a very good one. This section will discuss the reasons why. It is optional reading because it’s not strictly related to C or C++, but if you like programming you will probably find it interesting anyway.

In order to be a good PRNG, the PRNG needs to exhibit a number of properties:

First, the PRNG should generate each number with approximately the same probability. This is called distribution uniformity. If some numbers are generated more often than others, the result of the program that uses the PRNG will be biased!

For example, let’s say you’re trying to write a random item generator for a game. You’ll pick a random number between 1 and 10, and if the result is a 10, the monster will drop a powerful item instead of a common one. You would expect a 1 in 10 chance of this happening. But if the underlying PRNG is not uniform, and generates a lot more 10s than it should, your players will end up getting more rare items than you’d intended, possibly trivializing the difficulty of your game.

Generating PRNGs that produce uniform results is difficult, and it’s one of the main reasons the PRNG we wrote at the top of this lesson isn’t a very good PRNG.

Second, the method by which the next number in the sequence shouldn’t be obvious or predictable. For example, consider the following PRNG algorithm: nNum = nNum + 1. This PRNG is perfectly uniform, but it’s not very useful as a sequence of random numbers!

Third, the PRNG should have a good dimensional distribution of numbers. This means it should return low numbers, middle numbers, and high numbers seemingly at random. A PRNG that returned all low numbers, then all high numbers may be uniform and non-predictable, but it’s still going to lead to biased results, particularly if the number of random numbers you actually use is small.

Fourth, all PRNGs are periodic, which means that at some point the sequence of numbers generated will eventually begin to repeat itself. As mentioned before, PRNGs are deterministic, and given an input number, a PRNG will produce the same output number every time. Consider what happens when a PRNG generates a number it has previously generated. From that point forward, it will begin to duplicate the sequence between the first occurrence of that number and the next occurrence of that number over and over. The length of this sequence is known as the period

For example, here are the first 100 numbers generated from a PRNG with poor periodicity:

112	9	130	97	64
31	152	119	86	53
20	141	108	75	42
9	130	97	64	31
152	119	86	53	20
141	108	75	42	9
130	97	64	31	152
119	86	53	20	141
108	75	42	9	130
97	64	31	152	119
86	53	20	141	108
75	42	9	130	97
64	31	152	119	86
53	20	141	108	75
42	9	130	97	64
31	152	119	86	53
20	141	108	75	42
9	130	97	64	31
152	119	86	53	20
141	108	75	42	9

You will note that it generated 9 as the second number, and 9 again as the 16th number. The PRNG gets stuck generating the sequence in-between these two 9’s repeatedly: 9-130-97-64-31-152-119-86-53-20-141-108-75-42-(repeat).

A good PRNG should have a long period for all seed numbers. Designing an algorithm that meets this property can be extremely difficult — most PRNGs will have long periods for some seeds and short periods for others. If the user happens to pick that seed, then the PRNG won’t be doing a good job.

Despite the difficulty in designing algorithms that meet all of these criteria, a lot of research has been done in this area because of it’s importance to scientific computing.

rand() is a mediocre PRNG

The algorithm used to implement rand() can vary from compiler to compiler, leading to results that may not be consistent across compilers. Most implementations of rand() use a method called a Linear Congruential Generator (LCG). If you have a look at the first example in this lesson, you’ll note that it’s actually a LCG, though one with intentionally poorly picked bad constants. LCGs tend to have shortcomings that make them not good choices for certain kinds of problems.

One of the main shortcomings of rand() is that RAND_MAX is usually set to 32767 (essentially 16-bits). This means if you want to generate numbers over a larger range (eg. 32-bit integers), the algorithm is not suitable. Also, rand() isn’t good if you want to generate random floating point numbers (eg. between 0.0 and 1.0), which is often useful when doing statistical modelling. Finally, rand() tends to have a relatively short period compared to other algorithms.

That said, rand() is entirely suitable for learning how to program, and for programs in which a high-quality PRNG is not a necessity. For such applications, I would highly recommend Mersenne Twister, which produces great results and is relatively easy to use.

6.1 — Arrays (Part I)

Index

5.8 — Break and Continue

Cleaning up resources

One of the biggest problems that new programmers run into when using exceptions is the issue of cleaning up resources when an exception occurs. Consider the following example:

try
{
    OpenFile(strFilename);
    WriteFile(strFilename, strData);
    CloseFile(strFilename);
}
catch (FileException &cException)
{
    cerr << "Failed to write to file: " << cException.what() << endl;
}

What happens if WriteFile() fails and throws a FileException? At this point, we’ve already opened the file, and now control flow jumps to the FileException handler, which prints an error and exits. Note that the file was never closed! This example should be rewritten as follows:

try
{
    OpenFile(strFilename);
    WriteFile(strFilename, strData);
    CloseFile(strFilename);
}
catch (FileException &cException)
{
    // Make sure file is closed
    CloseFile(strFilename);
    // Then write error
    cerr << "Failed to write to file: " << cException.what() << endl;
}

This kind of error often crops up in another form when dealing with dynamically allocated memory:

try
{
    Person *pJohn = new Person("John", 18, E_MALE);
    ProcessPerson(pJohn);
    delete pJohn;
}
catch (PersonException &cException)
{
    cerr << "Failed to process person: " << cException.what() << endl;
}

If ProcessPerson() throws an exception, control flow jumps to the catch handler. As a result, pJohn is never deallocated! This example is a little more tricky than the previous one — because pJohn is local to the try block, it goes out of scope when the try block exits. That means the exception handler can not access pJohn at all (its been destroyed already), so there’s no way for it to deallocate the memory.

However, there are two relatively easy ways to fix this. First, declare pJohn outside of the try block so it does not go out of scope when the try block exits:

Person *pJohn = NULL;
try
{
    pJohn = new Person("John", 18, E_MALE);
    ProcessPerson(pJohn );
    delete pJohn;
}
catch (PersonException &cException)
{
    delete pJohn;
    cerr << "Failed to process person: " << cException.what() << endl;
}

Because pJohn is declared outside the try block, it is accessible both within the try block and the catch handlers. This means the catch handler can do cleanup properly.

The second way is to use a local variable of a class that knows how to cleanup itself when it goes out of scope. The standard library provides a class called std::auto_ptr that can be used for this purpose. std::auto_ptr is a template class that holds a pointer, and deallocates it when it goes out of scope.

#include <memory> // for std::auto_ptr
try
{
    pJohn = new Person("John", 18, E_MALE);
    auto_ptr<Person> pxJohn(pJohn); // pxJohn now owns pJohn

    ProcessPerson(pJohn);

    // when pxJohn goes out of scope, it will delete pJohn
}
catch (PersonException &cException)
{
    cerr << "Failed to process person: " << cException.what() << endl;
}

Note that std::auto_ptr should not be set to point to arrays. This is because it uses the delete operator to clean up, not the delete[] operator. In fact, there is no array version of std::auto_ptr! It turns out, there isn’t really a need for one. In the standard library, if you want to do dynamically allocated arrays, you’re supposed to use the std::vector class, which will deallocate itself when it goes out of scope.

Exceptions and destructors

Unlike constructors, where throwing exceptions can be a useful way to indicate that object creation succeeded, exceptions should not be thrown in destructors.

The problem occurs when an exception is thrown from a destructor during the stack unwinding process. If that happens, the compiler is put in a situation where it doesn’t know whether to continue the stack unwinding process or handle the new exception. The end result is that your program will be terminated immediately.

Consequently, the best course of action is just to abstain from using exceptions in destructors altogether. Write a message to a log file instead.

Performance concerns

Exceptions do come with a small performance price to pay. They increase the size of your executable, and they will also cause it to run slower due to the additional checking that has to be performed. However, the main performance penalty for exceptions happens when an exception is actually thrown. In this case, the stack must be unwound and an appropriate exception handler found, which is a relatively an expensive operation. Consequently, exception handling should only be used for truly exceptional cases and catastrophic errors.

17.1 — std::string and std::wstring

Index

15.5 — Exceptions, classes, and inheritance

Up to this point in the tutorial, you’ve only seen exceptions used in non-member functions. However, exceptions are equally useful in member functions, and even moreso in overloaded operators. Consider the following overloaded [] operator as part of a simple integer array class:

int IntArray::operator[](const int nIndex)
{
    return m_nData[nIndex];
}

Although this function will work great as long as nIndex is a valid array index, this function is sorely lacking in some good error checking. We could add an assert statement to ensure the index is valid:

int IntArray::operator[](const int nIndex)
{
    assert (nIndex >= 0 && nIndex < GetLength());
    return m_nData[nIndex];
}

Now if the user passes in an invalid index, the program will cause an assertion error. While this is useful to indicate to the user that something went wrong, sometimes the better course of action is to fail silently and let the caller know something went wrong so they can deal with it as appropriate.

Unfortunately, because overloaded operators have specific requirements as to the number and type of parameter(s) they can take and return, there is no flexibility for passing back error codes or boolean values to the caller. However, since exceptions do not change the signature of a function, they can be put to great use here. Here’s an example:

int IntArray::operator[](const int nIndex)
{
    if (nIndex < 0 || nIndex >= GetLength())
        throw nIndex;

    return m_nData[nIndex];
}

Now, if the user passes in an invalid exception, operator[] will throw an int exception.

When constructors fail

Constructors are another area of classes in which exceptions can be very useful. If a constructor fails, simply throw an exception to indicate the object failed to create. The object’s construction is aborted and its destructor is never executed.

Exception classes

One of the major problem with using basic data types (such as int) as exception types is that they are inherently vague. An even bigger problem is disambiguation of what an exception means when there are multiple statements or function calls within a try block.

try
{
    int *nValue = new int(anArray[nIndex1] + anArray[nIndex2]);
}
catch (int nValue)
{
    // What are we catching here?
}

In this example, if we were to catch an int exception, what does that really tell us? Was one of the array indexes out of bounds? Did operator+ cause integer overflow? Did operator new fail because it ran out of memory? Unfortunately, in this case, there’s just no easy way to disambiguate. While we can throw char* exceptions to solve the problem of identifying WHAT went wrong, this still does not provide us the ability to handle exceptions from various sources differently.

One way to solve this problem is to use exception classes. An exception class is just a normal class that is designed specifically to be thrown as an exception. Let’s design a simple exception class to be used with our IntArray class:

class ArrayException
{
private:
    std::string m_strError;

    ArrayException() {}; // not meant to be called
public:
    ArrayException(std::string strError)
        : m_strError(strError)
    {
    }

    std::string GetError() { return m_strError; }
}

Here’s our overloaded operator[] throwing this class:

int IntArray::operator[](const int nIndex)
{
    if (nIndex < 0 || nIndex >= GetLength())
        throw ArrayException("Invalid index");

    return m_nData[nIndex];
}

And a sample usage of this class:

try
{
    int nValue = anArray[5];
}
catch (ArrayException &cException)
{
    cerr << "An array exception occurred (" << cException.GetError() << ")" << endl;
}

Using such a class, we can have the exception return a description of the problem that occurred, which provides context for what went wrong. And since ArrayException is it’s own unique type, we can specifically catch exceptions thrown by the array class and treat them differently from other exceptions if we wish.

Note that exception handlers should catch class exception objects by reference instead of by value. This prevents the compiler from make a copy of the exception, which can be expensive when the exception is a class object. Catching exceptions by pointer should generally be avoided unless you have a specific reason to do so.

std::exception

The C++ standard library comes with an exception class that is used by many of the other standard library classes. The class is almost identical to the ArrayException class above, except the GetError() function is named what():

try
{
    // do some stuff with the standard library here
}
catch (std::exception &cException)
{
    cerr << "Standard exception: " << cException.what() << endl;
}

We’ll talk more about std::exception in a moment.

Exceptions and inheritance

Since it’s possible to throw classes as exceptions, and classes can be derived from other classes, we need to consider what happens when we use inherited classes as exceptions. As it turns out, exception handlers will not only match classes of a specific type, they’ll also match classes derived from that specific type as well! Consider the following example:

class Base
{
public:
    Base() {}
};

class Derived: public Base
{
public:
    Derived() {}
};

int main()
{
    try
    {
        throw Derived();
    }
    catch (Base &cBase)
    {
        cerr << "caught Base";
    }
    catch (Derived &cDerived)
    {
        cerr << "caught Derived";
    }

    return 0;
}

In the above example we throw an exception of type Derived. However, the output of this program is:

caught Base

What happened?

First, as mentioned above, derived classes will be caught by handlers for the base type. Because Derived is derived from Base, Derived is-a Base (they have an is-a relationship). Second, when C++ is attempting to find a handler for a raised exception, it does so sequentially. Consequently, the first thing C++ does is check whether the exception handler for Base matches the Derived exception. Because Derived is-a Base, the answer is yes, and it executes the catch block for type Base! The catch block for Derived is never even tested in this case.

In order to make this example work as expected, we need to flip the order of the catch blocks:

class Base
{
public:
    Base() {}
};

class Derived: public Base
{
public:
    Derived() {}
};

int main()
{
    try
    {
        throw Derived();
    }
    catch (Derived &cDerived)
    {
        cerr << "caught Derived";
    }
    catch (Base &cBase)
    {
        cerr << "caught Base";
    }

    return 0;
}

This way, the Derived handler will get first shot at catching objects of type Derived (before the handler for Base can). Objects of type Base will not match the Derived handler (Derived is-a Base, but Base is not a Derived), and thus will “fall through” to the Base handler.

Rule: Handlers for derived exception classes should be listed before those for base classes.

The ability to use a handler to catch exceptions of derived types using a handler for the base class turns out to be exceedingly useful.

Let’s take a look at this using std::exception. There are many classes derived from std::exception, such as std::bad_alloc, std::bad_cast, std::runtime_error, and others. When the standard library has an error, it can throw a derived exception correlating to the appropriate specific problem it has encountered.

Most of the time, we probably won’t care whether the problem was a bad allocation, a bad cast, or something else. We just care that we got an exception from the standard library. In this case, we just set up an exception handler to catch std::exception, and we’ll end up catching std::exception and all of the derived exceptions together in one place. Easy!

try
{
     // code using standard library goes here
}
// This handler will catch std::exception and all the derived exceptions too
catch (std::exception &cException)
{
    cerr << "Standard exception: " << cException.what() << endl;
}

However, sometimes we’ll want to handle a specific type of exception differently. In this case, we can add a handler for that specific type, and let all the others “fall through” to the base handler. Consider:

try
{
     // code using standard library goes here
}
// This handler will catch std::bad_alloc (and any exceptions derived from it) here
catch (std::bad_alloc &cException)
{
    cerr << "You ran out of memory!" << endl;
}
// This handler will catch std::exception (and any exception derived from it) that fall
// through here
catch (std::exception &cException)
{
    cerr << "Standard exception: " << cException.what() << endl;
}

In this example, exceptions of type std::bad_alloc will be caught by the first handler and handled there. Exceptions of type std::exception and all of the other derived classes will be caught by the second handler.

Such inheritance hierarchies allow us to use specific handlers to target specific derived exception classes, or to use base class handlers to catch the whole hierarchy of exceptions. This allows us a fine degree of control over what kind of exceptions we want to handle while ensuring we don’t have to do too much work to catch “everything else” in a hierarchy.

15.6 — Exception dangers and downsides

Index

15.4 — Uncaught exceptions, catch-all handlers, and exception specifiers