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

---

17.6 Access to elements

For vector to be usable, we need a way to read and write elements. For starters, we can provide simple get() and set() member functions:

// a very simplified vector of doubles
class vector {
int sz; // the size
double* elem; // a pointer to the elements
public:
vector(int s) :sz{s}, elem{new double[s]} { /* . . . */ } // constructor
~vector() { delete[] elem; } // destructor

int size() const { return sz; } // the current size

double get(int n) const { return elem[n]; } // access: read
void set(int n, double v) { elem[n]=v; } // access: write
};

Both get() and set() access the elements using the [ ] operator on the elem pointer: elem[n].

Now we can make a vector of doubles and use it:

vector v(5);
for (int i=0; i<v.size(); ++i) {
v.set(i,1.1*i);
cout << "v[" << i << "]==" << v.get(i) << '\n';
}

This will output

v[0]==0
v[1]==1.1
v[2]==2.2
v[3]==3.3
v[4]==4.4

This is still an overly simple vector, and the code using get() and set() is rather ugly compared to the usual subscript notation. However, we aim to start small and simple and then grow our programs step by step, testing along the way. As ever, this strategy of growth and repeated testing minimizes errors and debugging.

17.7 Pointers to class objects

The notion of “pointer” is general, so we can point to just about anything we can place in memory. For example, we can use pointers to vectors exactly as we use pointers to chars:

vector* f(int s)
{
vector* p = new vector(s); // allocate a vector on free store
// fill *p
return p;
}
void ff()
{
vector* q = f(4);
// use *q
delete q; // free vector on free store
}

Note that when we delete a vector, its destructor is called. For example:

vector* p = new vector(s); // allocate a vector on free store
delete p; // deallocate

Creating the vector on the free store, the new operator

• First allocates memory for a vector

• Then invokes the vector’s constructor to initialize that vector; the constructor allocates memory for the vector’s elements and initializes those elements

Deleting the vector, the delete operator

• First invokes the vector’s destructor; the destructor invokes the destructors for the elements (if they have destructors) and then deallocates the memory used for the vector’s elements

• Then deallocates the memory used for the vector

Note how nicely that works recursively (see §8.5.8). Using the real (standard library) vector we can also do

vector<vector<double>>* p = new vector<vector<double>>(10);
delete p;

Here, delete p invokes the destructor for vector<vector<double>>; this destructor in turn invokes the destructor for its vector<double> elements, and all is neatly cleaned up, leaving no object undestroyed and leaking no memory.

Because delete invokes destructors (for types, such as vector, that have one), delete is often said to destroy objects, not just deallocate them.

As usual, please remember that a “naked” new outside a constructor is an opportunity to forget to delete the object that new created. Unless you have a good (that is, really simple, such as Vector_ref from §13.10 and §E.4) strategy for deleting objects, try to keep news in constructors anddeletes in destructors.

So far, so good, but how do we access the members of a vector, given only a pointer? Note that all classes support the operator . (dot) for accessing members, given the name of an object:

vector v(4);
int x = v.size();
double d = v.get(3);

Similarly, all classes support the operator -> (arrow) for accessing members, given a pointer to an object:

vector* p = new vector(4);
int x = p->size();
double d = p->get(3);

Like . (dot), -> (arrow) can be used for both data members and function members. Since built-in types, such as int and double, have no members, -> doesn’t apply to built-in types. Dot and arrow are often called member access operators.

17.8 Messing with types: void* and casts

Using pointers and free-store-allocated arrays, we are very close to the hardware. Basically, our operations on pointers (initialization, assignment, *, and [ ]) map directly to machine instructions. At this level, the language offers only a bit of notational convenience and the compile-time consistency offered by the type system. Occasionally, we have to give up even that last bit of protection.

Naturally, we don’t want to make do without the protection of the type system, but sometimes there is no logical alternative (e.g., we need to interact with another language that doesn’t know about C++’s types). There are also an unfortunate number of cases where we need to interface with old code that wasn’t designed with static type safety in mind. For that, we need two things:

• A type of pointer that points to memory without knowing what kinds of objects reside in that memory

• An operation to tell the compiler what kind of type to assume (without proof) for memory pointed to by one of those pointers

The type void* means “pointer to some memory that the compiler doesn’t know the type of.” We use void* when we want to transmit an address between pieces of code that really don’t know each other’s types. Examples are the “address” arguments of a callback function (§16.3.1) and the lowest level of memory allocators (such as the implementation of the new operator).

There are no objects of type void, but as we have seen, we use void to mean “no value returned”:

void v; // error: there are no objects of type void
void f(); // f() returns nothing — f() does not return an object of type void

A pointer to any object type can be assigned to a void*. For example:

void* pv1 = new int; // OK: int* converts to void*
void* pv2 = new double[10]; // OK: double* converts to void*

Since the compiler doesn’t know what a void* points to, we must tell it:

void f(void* pv)
{
void* pv2 = pv; // copying is OK (copying is what void*s are for)
double* pd = pv; // error: cannot convert void* to double*
*pv = 7; // error: cannot dereference a void*
// (we don’t know what type of object it points to)
pv[2] = 9; // error: cannot subscript a void*
int* pi = static_cast<int*>(pv); // OK: explicit conversion
// . . .
}

A static_cast can be used to explicitly convert between related pointer types, such as void* and double* (§A.5.7). The name static_cast is a deliberately ugly name for an ugly (and dangerous) operation — use it only when absolutely necessary. You shouldn’t find it necessary very often — if at all. An operation such as static_cast is called an explicit type conversion (because that’s what it does) or colloquially a cast (because it is used to support something that’s broken).

C++ offers two casts that are potentially even nastier than static_cast:

• reinterpret_cast can cast between unrelated types, such as int and double*.

• const_cast can “cast away const.”

For example:

Register* in = reinterpret_cast<Register*>(0xff);

void f(const Buffer* p)
{
Buffer* b = const_cast<Buffer*>(p);
// . . .
}

The first example is the classical necessary and proper use of a reinterpret_cast. We tell the compiler that a certain part of memory (the memory starting with location 0xFF) is to be considered a Register (presumably with special semantics). Such code is necessary when you write things like device drivers.

In the second example, const_cast strips the const from the const Buffer* called p. Presumably, we know what we are doing.

At least static_cast can’t mess with the pointer/integer distinction or with “const-ness,” so prefer static_cast if you feel the need for a cast. When you think you need a cast, reconsider: Is there a way to write the code without the cast? Is there a way to redesign that part of the program so that the cast is not needed? Unless you are interfacing to other people’s code or to hardware, there usually is a way. If not, expect subtle and nasty bugs. Don’t expect code using reinterpret_cast to be portable.

17.9 Pointers and references

You can think of a reference as an automatically dereferenced immutable pointer or as an alternative name for an object. Pointers and references differ in these ways:

• Assignment to a pointer changes the pointer’s value (not the pointed-to value).

• To get a pointer you generally need to use new or &.

• To access an object pointed to by a pointer you use * or [ ].

• Assignment to a reference changes the value of the object referred to (not the reference itself).

• You cannot make a reference refer to a different object after initialization.

• Assignment of references does deep copy (assigns to the referred-to object); assignment of pointers does not (assigns to the pointer object itself).

• Beware of null pointers.

For example:

int x = 10;
int* p = &x; // you need & to get a pointer
*p = 7; // use * to assign to x through p
int x2 = *p; // read x through p
int* p2 = &x2; // get a pointer to another int
p2 = p; // p2 and p both point to x
p = &x2; // make p point to another object

The corresponding example for references is

int y = 10;
int& r = y; // the & is in the type, not in the initializer
r = 7; // assign to y through r (no * needed)
int y2 = r; // read y through r (no * needed)
int& r2 = y2; // get a reference to another int
r2 = r; // the value of y is assigned to y2
r = &y2; // error: you can’t change the value of a reference
// (no assignment of an int* to an int&)

Note the last example; it is not just this construct that will fail — there is no way to get a reference to refer to a different object after initialization. If you need to point to something different, use a pointer. For ideas of how to use pointers, see §17.9.3.

A reference and a pointer are both implemented by using a memory address. They just use that address differently to provide you — the programmer — slightly different facilities.

17.9.1 Pointer and reference parameters

When you want to change the value of a variable to a value computed by a function, you have three choices. For example:

int incr_v(int x) { return x+1; } // compute a new value and return it
void incr_p(int* p) { ++*p; } // pass a pointer
// (dereference it and increment the result)
void incr_r(int& r) { ++r; } // pass a reference

How do you choose? We think returning the value often leads to the most obvious (and therefore least error-prone) code; that is:

int x = 2;
x = incr_v(x); // copy x to incr_v(); then copy the result out and assign it

We prefer that style for small objects, such as an int. In addition, if a “large object” has a move constructor (§18.3.4) we can efficiently pass it back and forth.

How do we choose between using a reference argument and using a pointer argument? Unfortunately, either way has both attractions and problems, so again the answer is less than clear-cut. You have to make a decision based on the individual function and its likely uses.

Using a pointer argument alerts the programmer that something might be changed. For example:

int x = 7;
incr_p(&x) // the & is needed
incr_r(x);

The need to use & in incr_p(&x) alerts the user that x might be changed. In contrast, incr_r(x) “looks innocent.” This leads to a slight preference for the pointer version.

On the other hand, if you use a pointer as a function argument, the function has to beware that someone might call it with a null pointer, that is, with a nullptr. For example:

incr_p(nullptr); // crash: incr_p() will try to dereference the null pointer
int* p = nullptr;
incr_p(p); // crash: incr_p() will try to dereference the null pointer

This is obviously nasty. The person who writes incr_p() can protect against this:

void incr_p(int* p)
{
if (p==nullptr) error("null pointer argument to incr_p()");
++*p; // dereference the pointer and increment the object pointed to
}

But now incr_p() suddenly doesn’t look as simple and attractive as before. Chapter 5 discusses how to cope with bad arguments. In contrast, users of a reference (such as incr_r()) are entitled to assume that a reference refers to an object.

If “passing nothing” (passing no object) is acceptable from the point of view of the semantics of the function, we must use a pointer argument. Note: That’s not the case for an increment operation — hence the need for throwing an exception for p==nullptr.

So, the real answer is: “The choice depends on the nature of the function”:

• For tiny objects prefer pass-by-value.

• For functions where “no object” (represented by nullptr) is a valid argument use a pointer parameter (and remember to test for nullptr).

• Otherwise, use a reference parameter.

See also §8.5.6.

17.9.2 Pointers, references, and inheritance

In §14.3, we saw how a derived class, such as Circle, could be used where an object of its public base class Shape was required. We can express that idea in terms of pointers or references: a Circle* can be implicitly converted to a Shape* because Shape is a public base of Circle. For example:

void rotate(Shape* s, int n); // rotate *s n degrees

Shape* p = new Circle{Point{100,100},40};
Circle c {Point{200,200},50};
rotate(p,35);
rotate(&c,45);

And similarly for references:

void rotate(Shape& s, int n); // rotate s n degrees

Shape& r = c;
rotate(r,55);
rotate(*p,65);
rotate(c,75);

This is crucial for most object-oriented programming techniques (§14.3-4).

17.9.3 An example: lists

Lists are among the most common and useful data structures. Usually, a list is made out of “links” where each link holds some information and pointers to other links. This is one of the classical uses of pointers. For example, we could represent a short list of Norse gods like this:

A list like this is called a doubly-linked list because given a link, we can find both the predecessor and the successor. A list where we can find only the successor is called a singly-linked list. We use doubly-linked lists when we want to make it easy to remove an element. We can define these links like this:

struct Link {
string value;
Link* prev;
Link* succ;
Link(const string& v, Link* p = nullptr, Link* s = nullptr)
: value{v}, prev{p}, succ{s} { }
};

That is, given a Link, we can get to its successor using the succ pointer and to its predecessor using the prev pointer. We use the null pointer to indicate that a Link doesn’t have a successor or a predecessor. We can build our list of Norse gods like this:

Link* norse_gods = new Link{"Thor",nullptr,nullptr};
norse_gods = new Link{"Odin",nullptr,norse_gods};
norse_gods->succ->prev = norse_gods;
norse_gods = new Link{"Freia",nullptr,norse_gods};
norse_gods->succ->prev = norse_gods;

We built that list by creating the Links and tying them together as in the picture: first Thor, then Odin as the predecessor of Thor, and finally Freia as the predecessor of Odin. You can follow the pointer to see that we got it right, so that each succ and prev points to the right god. However, the code is obscure because we didn’t explicitly define and name an insert operation:

Link* insert(Link* p, Link* n) // insert n before p (incomplete)
{
n->succ = p; // p comes after n
p->prev->succ = n; // n comes after what used to be p’s predecessor
n->prev = p->prev; // p’s predecessor becomes n’s predecessor
p->prev = n; // n becomes p’s predecessor
return n;
}

This works provided that p really points to a Link and that the Link pointed to by p really has a predecessor. Please convince yourself that this really is so. When thinking about pointers and linked structures, such as a list made out of Links, we invariably draw little box-and-arrow diagrams on paper to verify that our code works for small examples. Please don’t be too proud to rely on this effective low-tech design technique.

That version of insert() is incomplete because it doesn’t handle the cases where n, p, or p->prev is nullptr. We add the appropriate tests for the null pointer and get the messier, but correct, version:

Link* insert(Link* p, Link* n) // insert n before p; return n
{
if (n==nullptr) return p;
if (p==nullptr) return n;
n->succ = p; // p comes after n
if (p->prev) p->prev->succ = n;
n->prev = p->prev; // p’s predecessor becomes n’s predecessor
p->prev = n; // n becomes p’s predecessor
return n;
}

Given that, we could write

Link* norse_gods = new Link{"Thor"};
norse_gods = insert(norse_gods,new Link{"Odin"});
norse_gods = insert(norse_gods,new Link{"Freia"});

Now all the error-prone fiddling with the prev and succ pointers has disappeared from sight. Pointer fiddling is tedious and error-prone and should be hidden in well-written and well-tested functions. In particular, many errors in conventional code come from people forgetting to test pointers against nullptr — just as we (deliberately) did in the first version of insert().

Note that we used default arguments (§15.3.1, §A.9.2) to save users from mentioning predecessors and successors in every constructor use.

17.9.4 List operations

The standard library provides a list class, which we will describe in §20.4. It hides all link manipulation, but here we will elaborate on our notion of list based on the Link class to get a feel for what goes on “under the covers” of list classes and see more examples of pointer use.

What operations does our Link class need to allow its users to avoid “pointer fiddling”? That’s to some extent a matter of taste, but here is a useful set:

• The constructor

• insert: insert before an element

• add: insert after an element

• erase: remove an element

• find: find a Link with a given value

• advance: get the nth successor

We could write these operations like this:

Link* add(Link* p, Link* n) // insert n after p; return n
{
// much like insert (see exercise 11)
}

Link* erase(Link* p) // remove *p from list; return p’s successor
{
if (p==nullptr) return nullptr;
if (p->succ) p->succ->prev = p->prev;
if (p->prev) p->prev->succ = p->succ;
return p->succ;
}

Link* find(Link* p, const string& s) // find s in list;
// return nullptr for “not found”
{
while (p) {
if (p->value == s) return p;
p = p->succ;
}
return nullptr;
}

Link* advance(Link* p, int n) // move n positions in list
// return nullptr for “not found”
// positive n moves forward, negative backward
{
if (p==nullptr) return nullptr;
if (0<n) {
while (n--) {
if (p->succ == nullptr) return nullptr;
p = p->succ;
}
}
else if (n<0) {
while (n++) {
if (p->prev == nullptr) return nullptr;
p = p->prev;
}
}
return p;
}

Note the use of the postfix n++. This form of increment (“post-increment”) yields the value before the increment as its value.

17.9.5 List use

As a little exercise, let’s build two lists:

Link* norse_gods = new Link("Thor");
norse_gods = insert(norse_gods,new Link{"Odin"});
norse_gods = insert(norse_gods,new Link{"Zeus"});
norse_gods = insert(norse_gods,new Link{"Freia"});

Link* greek_gods = new Link("Hera");
greek_gods = insert(greek_gods,new Link{"Athena"});
greek_gods = insert(greek_gods,new Link{"Mars"});
greek_gods = insert(greek_gods,new Link{"Poseidon"});

“Unfortunately,” we made a couple of mistakes: Zeus is a Greek god, rather than a Norse god, and the Greek god of war is Ares, not Mars (Mars is his Latin/Roman name). We can fix that:

Link* p = find(greek_gods, "Mars");
if (p) p->value = "Ares";

Note how we were cautious about find() returning a nullptr. We think that we know that it can’t happen in this case (after all, we just inserted Mars into greek_gods), but in a real example someone might change that code.

Similarly, we can move Zeus into his correct Pantheon:

Link* p = find(norse_gods,"Zeus");
if (p) {
erase(p);
insert(greek_gods,p);
}

Did you notice the bug? It’s quite subtle (unless you are used to working directly with links). What if the Link we erase() is the one pointed to by norse_gods? Again, that doesn’t actually happen here, but to write good, maintainable code, we have to take that possibility into account:

Link* p = find(norse_gods, "Zeus");
if (p) {
if (p==norse_gods) norse_gods = p->succ;
erase(p);
greek_gods = insert(greek_gods,p);
}

While we were at it, we also corrected the second bug: when we insert Zeus before the first Greek god, we need to make greek_gods point to Zeus’s Link. Pointers are extremely useful and flexible, but subtle.

Finally, let’s print out those lists:

void print_all(Link* p)
{
cout << "{ ";
while (p) {
cout << p->value;
if (p=p->succ) cout << ", ";
}
cout << " }";
}
print_all(norse_gods);
cout<<"\n";

print_all(greek_gods);
cout<<"\n";

This should give

{ Freia, Odin, Thor }
{ Zeus, Poseidon, Ares, Athena, Hera }

17.10 The this pointer

Note that each of our list functions takes a Link* as its first argument and accesses data in that object. That’s the kind of function that we often make member functions. Could we simplify Link (or link use) by making the operations members? Could we maybe make the pointers private so that only the member functions have access to them? We could:

class Link {
public:
string value;

Link(const string& v, Link* p = nullptr, Link* s = nullptr)
: value{v}, prev{p}, succ{s} { }

Link* insert(Link* n) ; // insert n before this object
Link* add(Link* n) ; // insert n after this object
Link* erase() ; // remove this object from list
Link* find(const string& s); // find s in list
const Link* find(const string& s) const; // find s in const list (see §18.5.1)

Link* advance(int n) const; // move n positions in list

Link* next() const { return succ; }
Link* previous() const { return prev; }
private:
Link* prev;
Link* succ;
};

This looks promising. We defined the operations that don’t change the state of a Link into const member functions. We added (nonmodifying) next() and previous() functions so that users could iterate over lists (of Links) — those are needed now that direct access to succ and prev is prohibited. We left value as a public member because (so far) we have no reason not to; it is “just data.”

Now let’s try to implement Link::insert() by copying our previous global insert() and modifying it suitably:

Link* Link::insert(Link* n) // insert n before p; return n
{
Link* p = this; // pointer to this object
if (n==nullptr) return p; // nothing to insert
if (p==nullptr) return n; // nothing to insert into
n->succ = p; // p comes after n
if (p->prev) p->prev->succ = n;
n->prev = p->prev; // p’s predecessor becomes n’s predecessor
p->prev = n; // n becomes p’s predecessor
return n;
}

But how do we get a pointer to the object for which Link::insert() was called? Without help from the language we can’t. However, in every member function, the identifier this is a pointer that points to the object for which the member function was called. Alternatively, we could simply usethis instead of p:

Link* Link::insert(Link* n) // insert n before this object; return n
{
if (n==nullptr) return this;
if (this==nullptr) return n;
n->succ = this; // this object comes after n
if (this->prev) this->prev->succ = n;
n->prev = this->prev; // this object’s predecessor
// becomes n’s predecessor
this->prev = n; // n becomes this object’s predecessor
return n;
}

This is a bit verbose, but we don’t need to mention this to access a member, so we can abbreviate:

Link* Link::insert(Link* n) // insert n before this object; return n
{
if (n==nullptr) return this;
if (this==nullptr) return n;
n->succ = this; // this object comes after n
if (prev) prev->succ = n;
n->prev = prev; // this object’s predecessor becomes n’s predecessor
prev = n; // n becomes this object’s predecessor
return n;
}

In other words, we have been using the this pointer — the pointer to the current object — implicitly every time we accessed a member. It is only when we need to refer to the whole object that we need to mention it explicitly.

Note that this has a specific meaning: it points to the object for which a member function is called. It does not point to any old object. The compiler ensures that we do not change the value of this in a member function. For example:

struct S {
// . . .
void mutate(S* p)
{
this = p; // error: this is immutable
// . . .
}
};

17.10.1 More link use

Having dealt with the implementation issues, we can see how the use now looks:

Link* norse_gods = new Link{"Thor"};
norse_gods = norse_gods->insert(new Link{"Odin"});
norse_gods = norse_gods->insert(new Link{"Zeus"});
norse_gods = norse_gods->insert(new Link{"Freia"});

Link* greek_gods = new Link{"Hera"};
greek_gods = greek_gods->insert(new Link{"Athena"});
greek_gods = greek_gods->insert(new Link{"Mars"});
greek_gods = greek_gods->insert(new Link{"Poseidon"});

That’s very much like before. As before, we correct our “mistakes.” Correct the name of the god of war:

Link* p = greek_gods->find("Mars");
if (p) p->value = "Ares";

Move Zeus into his correct Pantheon:

Link* p2 = norse_gods->find("Zeus");
if (p2) {
if (p2==norse_gods) norse_gods = p2->next();
p2->erase();
greek_gods = greek_gods->insert(p2);
}

Finally, let’s print out those lists:

void print_all(Link* p)
{
cout << "{ ";
while (p) {
cout << p->value;
if (p=p->next()) cout << ", ";
}
cout << " }";
}
print_all(norse_gods);
cout<<"\n";

print_all(greek_gods);
cout<<"\n";

This should again give

{ Freia, Odin, Thor }
{ Zeus, Poseidon, Ares, Athena, Hera }

So, which version do you like better: the one where insert(), etc. are member functions or the one where they are freestanding functions? In this case the differences don’t matter much, but see §9.7.5.

One thing to observe here is that we still don’t have a list class, only a link class. That forces us to keep worrying about which pointer is the pointer to the first element. We can do better than that — by defining a class List — but designs along the lines presented here are very common. The standard library list is presented in §20.4.

Drill

This drill has two parts. The first exercises/builds your understanding of free-store-allocated arrays and contrasts arrays with vectors:

1. Allocate an array of ten ints on the free store using new.

2. Print the values of the ten ints to cout.

3. Deallocate the array (using delete[]).

4. Write a function print_array10(ostream& os, int* a) that prints out the values of a (assumed to have ten elements) to os.

5. Allocate an array of ten ints on the free store; initialize it with the values 100, 101, 102, etc.; and print out its values.

6. Allocate an array of 11 ints on the free store; initialize it with the values 100, 101, 102, etc.; and print out its values.

7. Write a function print_array(ostream& os, int* a, int n) that prints out the values of a (assumed to have n elements) to os.

8. Allocate an array of 20 ints on the free store; initialize it with the values 100, 101, 102, etc.; and print out its values.

9. Did you remember to delete the arrays? (If not, do it.)

10. Do 5, 6, and 8 using a vector instead of an array and a print_vector() instead of print_array().

The second part focuses on pointers and their relation to arrays. Using print_array() from the last drill:

1. Allocate an int, initialize it to 7, and assign its address to a variable p1.

2. Print out the value of p1 and of the int it points to.

3. Allocate an array of seven ints; initialize it to 1, 2, 4, 8, etc.; and assign its address to a variable p2.

4. Print out the value of p2 and of the array it points to.

5. Declare an int* called p3 and initialize it with p2.

6. Assign p1 to p2.

7. Assign p3 to p2.

8. Print out the values of p1 and p2 and of what they point to.

9. Deallocate all the memory you allocated from the free store.

10. Allocate an array of ten ints; initialize it to 1, 2, 4, 8, etc.; and assign its address to a variable p1.

11. Allocate an array of ten ints, and assign its address to a variable p2.

12. Copy the values from the array pointed to by p1 into the array pointed to by p2.

13. Repeat 10-12 using a vector rather than an array.

Review

1. Why do we need data structures with varying numbers of elements?

2. What four kinds of storage do we have for a typical program?

3. What is the free store? What other name is commonly used for it? What operators support it?

4. What is a dereference operator and why do we need one?

5. What is an address? How are memory addresses manipulated in C++?

6. What information about a pointed-to object does a pointer have? What useful information does it lack?

7. What can a pointer point to?

8. What is a leak?

9. What is a resource?

10. How can we initialize a pointer?

11. What is a null pointer? When do we need to use one?

12. When do we need a pointer (instead of a reference or a named object)?

13. What is a destructor? When do we want one?

14. When do we want a virtual destructor?

15. How are destructors for members called?

16. What is a cast? When do we need to use one?

17. How do we access a member of a class through a pointer?

18. What is a doubly-linked list?

19. What is this and when do we need to use it?

Terms

address

address of: &

allocation

cast

container

contents of: *

deallocationa

delete

delete[]

dereference

destructor

free store

link

list

member access: ->

member destructor

memory

memory leak

new

null pointer

nullptr

pointer

range

resource leak

subscripting

subscript: [ ]

this

type conversion

virtual destructor

void*

Exercises

1. What is the output format of pointer values on your implementation? Hint: Don’t read the documentation.

2. How many bytes are there in an int? In a double? In a bool? Do not use sizeof except to verify your answer.

3. Write a function, void to_lower(char* s), that replaces all uppercase characters in the C-style string s with their lowercase equivalents. For example, Hello, World! becomes hello, world!. Do not use any standard library functions. A C-style string is a zero-terminated array of characters, so if you find a char with the value 0 you are at the end.

4. 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.

5. Write a function, char* findx(const char* s, const char* x), that finds the first occurrence of the C-style string x in s.

6. This chapter does not say what happens when you run out of memory using new. That’s called memory exhaustion. Find out what happens. You have two obvious alternatives: look for documentation, or write a program with an infinite loop that allocates but never deallocates. Try both. Approximately how much memory did you manage to allocate before failing?

7. Write a program that reads characters from cin into an array that you allocate on the free store. Read individual characters until an exclamation mark (!) is entered. Do not use a std::string. Do not worry about memory exhaustion.

8. Do exercise 7 again, but this time read into a std::string rather than to memory you put on the free store (string knows how to use the free store for you).

9. Which way does the stack grow: up (toward higher addresses) or down (toward lower addresses)? Which way does the free store initially grow (that is, before you use delete)? Write a program to determine the answers.

10. Look at your solution of exercise 7. Is there any way that input could get the array to overflow; that is, is there any way you could enter more characters than you allocated space for (a serious error)? Does anything reasonable happen if you try to enter more characters than you allocated?

11. Complete the “list of gods” example from §17.10.1 and run it.

12. Why did we define two versions of find()?

13. Modify the Link class from §17.10.1 to hold a value of a struct God. struct God should have members of type string: name, mythology, vehicle, and weapon. For example, God{"Zeus", "Greek", "", "lightning"} and God{"Odin", "Norse", "Eight-legged flying horse called Sleipner", "Spear called Gungnir"}. Write a print_all() function that lists gods with their attributes one per line. Add a member function add_ordered() that places its new element in its correct lexicographical position. Using the Links with the values of type God, make a list of gods from three mythologies; then move the elements (gods) from that list to three lexicographically ordered lists — one for each mythology.

14. Could the “list of gods” example from §17.10.1 have been written using a singly-linked list; that is, could we have left the prev member out of Link? Why might we want to do that? For what kind of examples would it make sense to use a singly-linked list? Re-implement that example using only a singly-linked list.

Postscript

Why bother with messy low-level stuff like pointers and free store when we can simply use vector? Well, one answer is that someone has to design and implement vector and similar abstractions, and we’d like to know how that’s done. There are programming languages that don’t provide facilities equivalent to pointers and thus dodge the problems with low-level programming. Basically, programmers of such languages delegate the tasks that involve direct access to hardware to C++ programmers (and programmers of other languages suitable for low-level programming). Our favorite reason, however, is simply that you can’t really claim to understand computers and programming until you have seen how software meets hardware. People who don’t know about pointers, memory addresses, etc. often have the strangest ideas of how their programming language facilities work; such wrong ideas can lead to code that’s “interestingly poor.”