Programming: Principles and Practice Using C++ (2014)

---

Our next try is to let operator[] return a pointer to the appropriate element:

class vector {
int sz; // the size
double* elem; // a pointer to the elements
public:
// . . .
double* operator[](int n) { return &elem[n]; } // return pointer
};

Given that definition, we can write

vector v(10);
for (int i=0; i<v.size(); ++i) { // works, but still too ugly
*v[i] = i;
cout << *v[i];
}

Here, v[i] is interpreted as a call v.operator[](i), and that call returns a pointer to v’s element number i. The problem is that we have to write * to dereference that pointer to get to the element. That’s almost as bad as having to write set() and get(). Returning a reference from the subscript operator solves this problem:

class vector {
// . . .
double& operator[ ](int n) { return elem[n]; } // return reference
};

Now we can write

vector v(10);
for (int i=0; i<v.size(); ++i) { // works!
v[i] = i; // v[i] returns a reference element i
cout << v[i];
}

We have achieved the conventional notation: v[i] is interpreted as a call v.operator[](i), and that returns a reference to v’s element number i.

18.5.1 Overloading on const

The operator[]() defined so far has a problem: it cannot be invoked for a const vector. For example:

void f(const vector& cv)
{
double d = cv[1]; // error, but should be fine
cv[1] = 2.0; // error (as it should be)
}

The reason is that our vector::operator[]() could potentially change a vector. It doesn’t, but the compiler doesn’t know that because we “forgot” to tell it. The solution is to provide a version that is a const member function (see §9.7.4). That’s easily done:

class vector {
// . . .
double& operator[](int n); // for non-const vectors
double operator[](int n) const; // for const vectors
};

We obviously couldn’t return a double& from the const version, so we returned a double value. We could equally well have returned a const double&, but since a double is a small object there would be no point in returning a reference (§8.5.6), so we decided to pass it back by value. We can now write

void ff(const vector& cv, vector& v)
{
double d = cv[1]; // fine (uses the const [])
cv[1] = 2.0; // error (uses the const [])
double d = v[1]; // fine (uses the non-const [])
v[1] = 2.0; // fine (uses the non-const [])
}

Since vectors are often passed by const reference, this const version of operator[]() is an essential addition.

18.6 Arrays

For a while, we have used array to refer to a sequence of objects allocated on the free store. We can also allocate arrays elsewhere as named variables. In fact, they are common

• As global variables (but global variables are most often a bad idea)

• As local variables (but arrays have serious limitations there)

• As function arguments (but an array doesn’t know its own size)

• As class members (but member arrays can be hard to initialize)

Now, you might have detected that we have a not-so-subtle bias in favor of vectors over arrays. Use std::vector where you have a choice — and you have a choice in most contexts. However, arrays existed long before vectors and are roughly equivalent to what is offered in other languages (notably C), so you must know arrays, and know them well, to be able to cope with older code and with code written by people who don’t appreciate the advantages of vector.

So, what is an array? How do we define an array? How do we use an array? An array is a homogeneous sequence of objects allocated in contiguous memory; that is, all elements of an array have the same type and there are no gaps between the objects of the sequence. The elements of an array are numbered from 0 upward. In a declaration, an array is indicated by “square brackets”:

const int max = 100;
int gai[max]; // a global array (of 100 ints); “lives forever”

void f(int n)
{
char lac[20]; // local array; “lives” until the end of scope
int lai[60];
double lad[n]; // error: array size not a constant
// . . .
}

Note the limitation: the number of elements of a named array must be known at compile time. If you want the number of elements to be a variable, you must put it on the free store and access it through a pointer. That’s what vector does with its array of elements.

Just like the arrays on the free store, we access named arrays using the subscript and dereference operators ([ ] and *). For example:

void f2()
{
char lac[20]; // local array; “lives” until the end of scope

lac[7] = 'a';
*lac = 'b'; // equivalent to lac[0]='b'

lac[-2] = 'b'; // huh?
lac[200] = 'c'; // huh?
}

This function compiles, but we know that “compiles” doesn’t mean “works correctly.” The use of [ ] is obvious, but there is no range checking, so f2() compiles, and the result of writing to lac[-2] and lac[200] is (as for all out-of-range access) usually disastrous. Don’t do it. Arrays do not range check. Again, we are dealing directly with physical memory here; don’t expect “system support.”

But couldn’t the compiler see that lac has just 20 elements so that lac[200] is an error? A compiler could, but as far as we know no production compiler does. The problem is that keeping track of array bounds at compile time is impossible in general, and catching errors in the simplest cases (like the one above) only is not very helpful.

18.6.1 Pointers to array elements

A pointer can point to an element of an array. Consider:

double ad[10];
double* p = &ad[5]; // point to ad[5]

We now have a pointer p to the double known as ad[5]:

We can subscript and dereference that pointer:

*p =7;
p[2] = 6;
p[-3] = 9;

We get

That is, we can subscript the pointer with both positive and negative numbers. As long as the resulting element is in range, all is well. However, access outside the range of the array pointed into is illegal (as with free-store-allocated arrays; see §17.4.3). Typically, access outside an array is not detected by the compiler and (sooner or later) is disastrous.

Once a pointer points into an array, addition and subscripting can be used to make it point to another element of the array. For example:

p += 2; // move p 2 elements to the right

We get

And

p -= 5; // move p 5 elements to the left

We get

Using +, -, +=, and -= to move pointers around is called pointer arithmetic. Obviously, if we do that, we have to take great care to ensure that the result is not a pointer to memory outside the array:

p += 1000; // insane: p points into an array with just 10 elements
double d = *p; // illegal: probably a bad value
// (definitely an unpredictable value)
*p = 12.34; // illegal: probably scrambles some unknown data

Unfortunately, not all bad bugs involving pointer arithmetic are that easy to spot. The best policy is usually simply to avoid pointer arithmetic.

The most common use of pointer arithmetic is incrementing a pointer (using ++) to point to the next element and decrementing a pointer (using --) to point to the previous element. For example, we could print the value of ad’s elements like this:

for (double* p = &ad[0]; p<&ad[10]; ++p) cout << *p << '\n';

Or backward:

for (double* p = &ad[9]; p>=&ad[0]; --p) cout << *p << '\n';

This use of pointer arithmetic is not uncommon. However, we find the last (“backward”) example quite easy to get wrong. Why &ad[9] and not &ad[10]? Why >= and not >? These examples could equally well (and equally efficiently) be done using subscripting. Such examples could be done equally well using subscripting into a vector, which is more easily range checked.

Note that most real-world uses of pointer arithmetic involve a pointer passed as a function argument. In that case, the compiler doesn’t have a clue how many elements are in the array pointed into: you are on your own. That is a situation we prefer to stay away from whenever we can.

Why does C++ have (allow) pointer arithmetic at all? It can be such a bother and doesn’t provide anything new once we have subscripting. For example:

double* p1 = &ad[0];
double* p2 = p1+7;
double* p3 = &p1[7];
if (p2 != p3) cout << "impossible!\n";

Mainly, the reason is historical. These rules were crafted for C decades ago and can’t be removed without breaking a lot of code. Partly, there can be some convenience gained by using pointer arithmetic in some important low-level applications, such as memory managers.

18.6.2 Pointers and arrays

The name of an array refers to all the elements of the array. Consider:

char ch[100];

The size of ch, sizeof(ch), is 100. However, the name of an array turns into (“decays to”) a pointer with the slightest excuse. For example:

char* p = ch;

Here p is initialized to &ch[0] and sizeof(p) is something like 4 (not 100).

This can be useful. For example, consider a function strlen() that counts the number of characters in a zero-terminated array of characters:

int strlen(const char* p) // similar to the standard library strlen()
{
int count = 0;
while (*p) { ++count; ++p; }
return count;
}

We can now call this with strlen(ch) as well as strlen(&ch[0]). You might point out that this is a very minor notational advantage, and we’d have to agree.

One reason for having array names convert to pointers is to avoid accidentally passing large amounts of data by value. Consider:

int strlen(const char a[]) // similar to the standard library strlen()
{
int count = 0;
while (a[count]) { ++count; }
return count;
}

char lots [100000];

void f()
{
int nchar = strlen(lots);
// . . .
}

Naively (and quite reasonably), you might expect this call to copy the 100,000 characters specified as the argument to strlen(), but that’s not what happens. Instead, the argument declaration char p[] is considered equivalent to char* p, and the call strlen(lots) is considered equivalent tostrlen(&lots[0]). This saves you from an expensive copy operation, but it should surprise you. Why should it surprise you? Because in every other case, when you pass an object and don’t explicitly declare an argument to be passed by reference (§8.5.3-6), that object is copied.

Note that the pointer you get from treating the name of an array as a pointer to its first element is a value and not a variable, so you cannot assign to it:

char ac[10];
ac = new char [20]; // error: no assignment to array name
&ac[0] = new char [20]; // error: no assignment to pointer value

Finally! A problem that the compiler will catch!

As a consequence of this implicit array-name-to-pointer conversion, you can’t even copy arrays using assignment:

int x[100];
int y[100];
// . . .
x = y; // error
int z[100] = y; // error

This is consistent, but often a bother. If you need to copy an array, you must write some more elaborate code to do so. For example:

for (int i=0; i<100; ++i) x[i]=y[i]; // copy 100 ints
memcpy(x,y,100*sizeof(int)); // copy 100*sizeof(int) bytes
copy(y,y+100, x); // copy 100 ints

Note that the C language doesn’t support anything like vector, so in C, you must use arrays extensively. This implies that a lot of C++ code uses arrays (§27.1.2). In particular, C-style strings (zero-terminated arrays of characters; see §27.5) are very common.

If we want assignment, we have to use something like the standard library vector. The vector equivalent to the copying code above is

vector<int> x(100);
vector<int> y(100);
// . . .
x = y; // copy 100 ints

18.6.3 Array initialization

An array of chars can be initialized with a string literal. For example:

char ac[] = "Beorn"; // array of 6 chars

Count those characters. There are five, but ac becomes an array of six characters because the compiler adds a terminating zero character at the end of a string literal:

A zero-terminated string is the norm in C and many systems. We call such a zero-terminated array of characters a C-style string. All string literals are C-style strings. For example:

char* pc = "Howdy"; // pc points to an array of 6 chars

Graphically:

Note that the char with the numeric value 0 is not the character '0' or any other letter or digit. The purpose of that terminating zero is to allow functions to find the end of the string. Remember: An array does not know its size. Relying on the terminating zero convention, we can write

int strlen(const char* p) // similar to the standard library strlen()
{
int n = 0;
while (p[n]) ++n;
return n;
}

Actually, we don’t have to define strlen() because it is a standard library function defined in the <string.h> header (§27.5, §B.11.3). Note that strlen() counts the characters, but not the terminating 0; that is, you need n+1 chars to store n characters in a C-style string.

Only character arrays can be initialized by literal strings, but all arrays can be initialized by a list of values of their element type. For example:

int ai[] = { 1, 2, 3, 4, 5, 6 }; // array of 6 ints
int ai2[100] = {0,1,2,3,4,5,6,7,8,9}; // the last 90 elements are initialized to 0
double ad[100] = { }; // all elements initialized to 0.0
char chars[]= {'a', 'b', 'c'}; // no terminating 0!

Note that the number of elements of ai is six (not seven) and the number of elements for chars is three (not four) — the “add a 0 at the end” rule is for literal character strings only. If an array isn’t given a size, that size is deduced from the initializer list. That’s a rather useful feature. If there are fewer initializer values than array elements (as in the definitions of ai2 and ad), the remaining elements are initialized by the element type’s default value.

18.6.4 Pointer problems

Like arrays, pointers are often overused and misused. Often, the problems people get themselves into involve both pointers and arrays, so we’ll summarize the problems here. In particular, all serious problems with pointers involve trying to access something that isn’t an object of the expected type, and many of those problems involve access outside the bounds of an array. Here we will consider

• Access through the null pointer

• Access through an uninitialized pointer

• Access off the end of an array

• Access to a deallocated object

• Access to an object that has gone out of scope

In all cases, the practical problem for the programmer is that the actual access looks perfectly innocent; it is “just” that the pointer hasn’t been given a value that makes the use valid. Worse (in the case of a write through the pointer), the problem may manifest itself only a long time later when some apparently unrelated object has been corrupted. Let’s consider examples:

Don’t access through the null pointer:

int* p = nullptr;
*p = 7; // ouch!

Obviously, in real-world programs, this typically occurs when there is some code in between the initialization and the use. In particular, passing p to a function and receiving it as the result from a function are common examples. We prefer not to pass null pointers around, but if you have to, test for the null pointer before use:

int* p = fct_that_can_return_a_nullptr();

if (p == nullptr) {
// do something
}
else {
// use p
*p = 7;
}

and

void fct_that_can_receive_a_nullptr(int* p)
{
if (p == nullptr) {
// do something
}
else {
// use p
*p = 7;
}
}

Using references (§17.9.1) and using exceptions to signal errors (§5.6 and §19.5) are the main tools for avoiding null pointers.

Do initialize your pointers:

int* p;
*p = 9; // ouch!

In particular, don’t forget to initialize pointers that are class members.

Don’t access nonexistent array elements:

int a[10];
int* p = &a[10];
*p = 11; // ouch!
a[10] = 12; // ouch!

Be careful with the first and last elements of a loop, and try not to pass arrays around as pointers to their first elements. Instead use vectors. If you really must use an array in more than one function (passing it as an argument), then be extra careful and pass its size along.

Don’t access through a deleted pointer:

int* p = new int{7};
// . . .
delete p;
// . . .
*p = 13; // ouch!

The delete p or the code after it may have scribbled all over *p or used it for something else. Of all of these problems, we consider this one the hardest to systematically avoid. The most effective defense against this problem is not to have “naked” news that require “naked” deletes: use newand delete in constructors and destructors or use a container, such as Vector_ref (§E.4), to handle deletes.

Don’t return a pointer to a local variable:

int* f()
{
int x = 7;
// . . .
return &x;
}

// . . .

int* p = f();
// . . .
*p = 15; // ouch!

The return from f() or the code after it may have scribbled all over *p or used it for something else. The reason for that is that the local variables of a function are allocated (on the stack) upon entry to the function and deallocated again at the exit from the function. In particular, destructors are called for local variables of classes with destructors (§17.5.1). Compilers could catch most problems related to returning pointers to local variables, but few do.

Consider a logically equivalent example:

vector& ff()
{
vector x(7); // 7 elements
// . . .
return x;
} // the vector x is destroyed here

// . . .

vector& p = ff();
// . . .
p[4] = 15; // ouch!

Quite a few compilers catch this variant of the return problem.

It is common for programmers to underestimate these problems. However, many experienced programmers have been defeated by the innumerable variations and combinations of these simple array and pointer problems. The solution is not to litter your code with pointers, arrays, news, and deletes. If you do, “being careful” simply isn’t enough in realistically sized programs. Instead, rely on vectors, RAII (“Resource Acquisition Is Initialization”; see §19.5), and other systematic approaches to the management of memory and other resources.

18.7 Examples: palindrome

Enough technical examples! Let’s try a little puzzle. A palindrome is a word that is spelled the same from both ends. For example, anna, petep, and malayalam are palindromes, whereas ida and homesick are not. There are two basic ways of determining whether a word is a palindrome:

• Make a copy of the letters in reverse order and compare that copy to the original.

• See if the first letter is the same as the last, then see if the second letter is the same as the second to last, and keep going until you reach the middle.

Here, we’ll take the second approach. There are many ways of expressing this idea in code depending on how we represent the word and how we keep track of how far we have come with the comparison of characters. We’ll write a little program that tests whether words are palindromes in a few different ways just to see how different language features affect the way the code looks and works.

18.7.1 Palindromes using string

First, we try a version using the standard library string with int indices to keep track of how far we have come with our comparison:

bool is_palindrome(const string& s)
{
int first = 0; // index of first letter
int last = s.length()-1; // index of last letter
while (first < last) { // we haven’t reached the middle
if (s[first]!=s[last]) return false;
++first; // move forward
--last; // move backward
}
return true;
}

We return true if we reach the middle without finding a difference. We suggest that you look at this code to convince yourself that it is correct when there are no letters in the string, just one letter in the string, an even number of letters in the string, and an odd number of letters in the string. Of course, we should not just rely on logic to see that our code is correct. We should also test. We can exercise is_palindrome() like this:

int main()
{
for (string s; cin>>s; ) {
cout << s << " is";
if (!is_palindrome(s)) cout << " not";
cout << " a palindrome\n";
}
}

Basically, the reason we are using a string is that “strings are good for dealing with words.” It is simple to read a whitespace-separated word into a string, and a string knows its size. Had we wanted to test is_palindrome() with strings containing whitespace, we could have read using getline()(§11.5). That would have shown ah ha and as df fd sa to be palindromes.

18.7.2 Palindromes using arrays

What if we didn’t have strings (or vectors), so that we had to use an array to store the characters? Let’s see:

bool is_palindrome(const char s[], int n)
// s points to the first character of an array of n characters
{
int first = 0; // index of first letter
int last = n-1; // index of last letter
while (first < last) { // we haven’t reached the middle
if (s[first]!=s[last]) return false;
++first; // move forward
--last; // move backward
}
return true;
}

To exercise is_palindrome(), we first have to get characters read into the array. One way to do that safely (i.e., without risk of overflowing the array) is like this:

istream& read_word(istream& is, char* buffer, int max)
// read at most max-1 characters from is into buffer
{
is.width(max); // read at most max-1 characters in the next >>
is >> buffer; // read whitespace-terminated word,
// add zero after the last character read into buffer
return is;
}

Setting the istream’s width appropriately prevents buffer overflow for the next >> operation. Unfortunately, it also means that we don’t know if the read terminated by whitespace or by the buffer being full (so that we need to read more characters). Also, who remembers the details of the behavior of width() for input? The standard library string and vector are really better as input buffers because they expand to fit the amount of input. The terminating 0 character is needed because most popular operations on arrays of characters (C-style strings) assume 0 termination. Usingread_word() we can write

int main()
{
constexpr int max = 128;
for (char s[max]; read_word(cin,s,max); ) {
cout << s << " is";
if (!is_palindrome(s,strlen(s))) cout << " not";
cout << " a palindrome\n";
}
}

The strlen(s) call returns the number of characters in the array after the call of read_word(), and cout<<s outputs the characters in the array up to the terminating 0.

We consider this “array solution” significantly messier than the “string solution,” and it gets much worse if we try to seriously deal with the possibility of long strings. See exercise 10.

18.7.3 Palindromes using pointers

Instead of using indices to identify characters, we could use pointers:

bool is_palindrome(const char* first, const char* last)
// first points to the first letter, last to the last letter
{
while (first < last) { // we haven’t reached the middle
if (*first!=*last) return false;
++first; // move forward
--last; // move backward
}
return true;
}

Note that we can actually increment and decrement pointers. Increment makes a pointer point to the next element of an array and decrement makes a pointer point to the previous element. If the array doesn’t have such a next element or previous element, you have a serious uncaught out-of-range error. That’s another problem with pointers.

We call this is_palindrome() like this:

int main()
{
const int max = 128;
for (char s[max]; read_word(cin,s,max); ) {
cout << s << " is";
if (!is_palindrome(&s[0],&s[strlen(s)-1])) cout << " not";
cout << " a palindrome\n";
}
}

Just for fun, we rewrite is_palindrome() like this:

bool is_palindrome(const char* first, const char* last)
// first points to the first letter, last to the last letter
{
if (first<last) {
if (*first!=*last) return false;
return is_palindrome(first+1,last-1);
}
return true;
}

This code becomes obvious when we rephrase the definition of palindrome: a word is a palindrome if the first and the last characters are the same and if the substring you get by removing the first and the last characters is a palindrome.

Drill

In this chapter, we have two drills: one to exercise arrays and one to exercise vectors in roughly the same manner. Do both and compare the effort involved in each.

Array drill:

1. Define a global int array ga of ten ints initialized to 1, 2, 4, 8, 16, etc.

2. Define a function f() taking an int array argument and an int argument indicating the number of elements in the array.

3. In f():

a. Define a local int array la of ten ints.

b. Copy the values from ga into la.

c. Print out the elements of la.

d. Define a pointer p to int and initialize it with an array allocated on the free store with the same number of elements as the argument array.

e. Copy the values from the argument array into the free-store array.

f. Print out the elements of the free-store array.

g. Deallocate the free-store array.

4. In main():

a. Call f() with ga as its argument.

b. Define an array aa with ten elements, and initialize it with the first ten factorial values (1, 2*1, 3*2*1, 4*3*2*1, etc.).

c. Call f() with aa as its argument.

Standard library vector drill:

1. Define a global vector<int> gv; initialize it with ten ints, 1, 2, 4, 8, 16, etc.

2. Define a function f() taking a vector<int> argument.

3. In f():

a. Define a local vector<int> lv with the same number of elements as the argument vector.

b. Copy the values from gv into lv.

c. Print out the elements of lv.

d. Define a local vector<int> lv2; initialize it to be a copy of the argument vector.

e. Print out the elements of lv2.

4. In main():

a. Call f() with gv as its argument.

b. Define a vector<int> vv, and initialize it with the first ten factorial values (1, 2*1, 3*2*1, 4*3*2*1, etc.).

c. Call f() with vv as its argument.

Review

1. What does “Caveat emptor!” mean?

2. What is the default meaning of copying for class objects?

3. When is the default meaning of copying of class objects appropriate? When is it inappropriate?

4. What is a copy constructor?

5. What is a copy assignment?

6. What is the difference between copy assignment and copy initialization?

7. What is shallow copy? What is deep copy?

8. How does the copy of a vector compare to its source?

9. What are the five “essential operations” for a class?

10. What is an explicit constructor? Where would you prefer one over the (default) alternative?

11. What operations may be invoked implicitly for a class object?

12. What is an array?

13. How do you copy an array?

14. How do you initialize an array?

15. When should you prefer a pointer argument over a reference argument? Why?

16. What is a C-style string?

17. What is a palindrome?

Terms

array

array initialization

copy assignment

copy constructor

deep copy

default constructor

essential operations

explicit constructor

move assignment

move construction

palindrome

shallow copy

Exercises

1. Write a function, char* strdup(const char*), that copies a C-style string into memory it allocates on the free store. Do not use any standard library functions. Do not use subscripting; use the dereference operator * instead.

2. Write a function, char* findx(const char* s, const char* x), that finds the first occurrence of the C-style string x in s. Do not use any standard library functions. Do not use subscripting; use the dereference operator * instead.

3. Write a function, int strcmp(const char* s1, const char* s2), that compares C-style strings. Let it return a negative number if s1 is lexicographically before s2, zero if s1 equals s2, and a positive number if s1 is lexicographically after s2. Do not use any standard library functions. Do not use subscripting; use the dereference operator * instead.

4. Consider what happens if you give strdup(), findx(), and strcmp() an argument that is not a C-style string. Try it! First figure out how to get a char* that doesn’t point to a zero-terminated array of characters and then use it (never do this in real — non-experimental — code; it can create havoc). Try it with free-store-allocated and stack-allocated “fake C-style strings.” If the results still look reasonable, turn off debug mode. Redesign and re-implement those three functions so that they take another argument giving the maximum number of elements allowed in argument strings. Then, test that with correct C-style strings and “bad” strings.

5. Write a function, string cat_dot(const string& s1, const string& s2), that concatenates two strings with a dot in between. For example, cat_dot("Niels", "Bohr") will return a string containing Niels.Bohr.

6. Modify cat_dot() from the previous exercise to take a string to be used as the separator (rather than dot) as its third argument.

7. Write versions of the cat_dot()s from the previous exercises to take C-style strings as arguments and return a free-store-allocated C-style string as the result. Do not use standard library functions or types in the implementation. Test these functions with several strings. Be sure to free (using delete) all the memory you allocated from free store (using new). Compare the effort involved in this exercise with the effort involved for exercises 5 and 6.

8. Rewrite all the functions in §18.7 to use the approach of making a backward copy of the string and then comparing; for example, take "home", generate "emoh", and compare those two strings to see that they are different, so home isn’t a palindrome.

9. Consider the memory layout in §17.4. Write a program that tells the order in which static storage, the stack, and the free store are laid out in memory. In which direction does the stack grow: upward toward higher addresses or downward toward lower addresses? In an array on the free store, are elements with higher indices allocated at higher or lower addresses?

10. Look at the “array solution” to the palindrome problem in §18.7.2. Fix it to deal with long strings by (a) reporting if an input string was too long and (b) allowing an arbitrarily long string. Comment on the complexity of the two versions.

11. Look up (e.g., on the web) skip list and implement that kind of list. This is not an easy exercise.

12. Implement a version of the game “Hunt the Wumpus.” “Hunt the Wumpus” (or just “Wump”) is a simple (non-graphical) computer game originally invented by Gregory Yob. The basic premise is that a rather smelly monster lives in a dark cave consisting of connected rooms. Your job is to slay the wumpus using bow and arrow. In addition to the wumpus, the cave has two hazards: bottomless pits and giant bats. If you enter a room with a bottomless pit, it’s the end of the game for you. If you enter a room with a bat, the bat picks you up and drops you into another room. If you enter the room with the wumpus or he enters yours, he eats you. When you enter a room you will be told if a hazard is nearby:

“I smell the wumpus”: It’s in an adjoining room.

“I feel a breeze”: One of the adjoining rooms is a bottomless pit.

“I hear a bat”: A giant bat is in an adjoining room.

For your convenience, rooms are numbered. Every room is connected by tunnels to three other rooms. When entering a room, you are told something like “You are in room 12; there are tunnels to rooms 1, 13, and 4; move or shoot?” Possible answers are m13 (“Move to room 13”) and s13-4-3 (“Shoot an arrow through rooms 13, 4, and 3”). The range of an arrow is three rooms. At the start of the game, you have five arrows. The snag about shooting is that it wakes up the wumpus and he moves to a room adjoining the one he was in — that could be your room.

Probably the trickiest part of the exercise is to make the cave by selecting which rooms are connected with which other rooms. You’ll probably want to use a random number generator (e.g., randint() from std_lib_facilities.h) to make different runs of the program use different caves and to move around the bats and the wumpus. Hint: Be sure to have a way to produce a debug output of the state of the cave.

Postscript

The standard library vector is built from lower-level memory management facilities, such as pointers and arrays, and its primary role is to help us avoid the complexities of those facilities. Whenever we design a class, we must consider initialization, copying, and destruction.