Читаем C++ Primer Plus полностью

C++ Primer Plus

Стивен Прата

<< (void *) buffer << " heap: " << pc2 <

cout << "Memory contents:\n";

cout << pc1 << ": ";

pc1->Show();

cout << pc2 << ": ";

pc2->Show();

JustTesting *pc3, *pc4;

pc3 = new (buffer) JustTesting("Bad Idea", 6);

pc4 = new JustTesting("Heap2", 10);

cout << "Memory contents:\n";

cout << pc3 << ": ";

pc3->Show();

cout << pc4 << ": ";

pc4->Show();

delete pc2; // free Heap1

delete pc4; // free Heap2

delete [] buffer; // free buffer

cout << "Done\n";

return 0;

}

The program in Listing 12.8 uses new to create a memory buffer of 512 bytes. It then uses new to create two objects of type JustTesting on the heap and attempts to use placement new to create two objects of type JustTesting in the memory buffer. Finally, it uses delete to free the memory allocated by new. Here is the output:

Just Testing constructed

Heap1 constructed

Memory block addresses:

buffer: 00320AB0 heap: 00320CE0

Memory contents:

00320AB0: Just Testing, 0

00320CE0: Heap1, 20

Bad Idea constructed

Heap2 constructed

Memory contents:

00320AB0: Bad Idea, 6

00320EC8: Heap2, 10

Heap1 destroyed

Heap2 destroyed

Done

As usual, the formatting and exact values for the memory addresses will vary from system to system.

There are a couple problems with placement new as used in Listing 12.8. First, when creating a second object, placement new simply overwrites the same location used for the first object with a new object. Not only is this rude, it means that the destructor was never called for the first object. This, of course, would create real problems if, say, the class used dynamic memory allocation for its members.

Second, using delete with pc2 and pc4 automatically invokes the destructors for the two objects that pc2 and pc4 point to. But using delete [] with buffer does not invoke the destructors for the objects created with placement new.

One lesson to be learned here is the same lesson you learned in Chapter 9: It’s up to you to manage the memory locations in a buffer that placement new populates. To use two different locations, you provide two different addresses within the buffer, making sure that the locations don’t overlap. You can, for example, use this:

pc1 = new (buffer) JustTesting;

pc3 = new (buffer + sizeof (JustTesting)) JustTesting("Better Idea", 6);

Here the pointer pc3 is offset from pc1 by the size of a JustTesting object.

The second lesson to be learned here is that if you use placement new to store objects, you need to arrange for their destructors to be called. But how? For objects created on the heap, you can use this:

delete pc2; // delete object pointed to by pc2

But you can’t use this:

delete pc1; // delete object pointed to by pc1? NO!

delete pc3; // delete object pointed to by pc3? NO!

The reason is that delete works in conjunction with new but not with placement new. The pointer pc3, for example, does not receive an address returned by new, so delete pc3 throws a runtime error. The pointer pc1, on the other hand, has the same numeric value as buffer, but buffer is initialized using new [], so it’s freed using delete [], not delete. Even if buffer were initialized by new instead of new [], delete pc1 would free buffer, not pc1. That’s because the new/delete system knows about the 256-byte block that is allocated, but it doesn’t know anything about what placement new does with the block.

Note that the program does free the buffer:

delete [] buffer; // free buffer

As this comment suggests, delete [] buffer; deletes the entire block of memory allocated by new. But it doesn’t call the destructors for any objects that placement new constructs in the block. You can tell this is so because this program uses chatty destructors, which report the demise of "Heap1" and "Heap2" but which remain silent about "Just Testing" and "Bad Idea".

The solution to this quandary is that you must call the destructor explicitly for any object created by placement new. Normally, destructors are called automatically; this is one of the rare cases that require an explicit call. An explicit call to a destructor requires identifying the object to be destroyed. Because there are pointers to the objects, you can use these pointers:

pc3->~JustTesting(); // destroy object pointed to by pc3

pc1->~JustTesting(); // destroy object pointed to by pc1

Listing 12.9 fixes Listing 12.8 by managing memory locations used by placement new and by adding appropriate uses of delete and of explicit destructor calls. One important fact is the proper order of deletion. The objects constructed by placement new should be destroyed in order opposite that in which they were constructed. The reason is that, in principle, a later object might have dependencies on an earlier object. And the buffer used to hold the objects should be freed only after all the contained objects are destroyed.

Listing 12.9. placenew2.cpp

// placenew2.cpp -- new, placement new, no delete

#include

using namespace std;

const int BUF = 512;

class JustTesting

{

private:

string words;

int number;

public:

JustTesting(const string & s = "Just Testing", int n = 0)

{words = s; number = n; cout << words << " constructed\n"; }

~JustTesting() { cout << words << " destroyed\n";}

void Show() const { cout << words << ", " << number << endl;}

};

int main()

{

char * buffer = new char[BUF]; // get a block of memory

JustTesting *pc1, *pc2;

pc1 = new (buffer) JustTesting; // place object in buffer

pc2 = new JustTesting("Heap1", 20); // place object on heap

cout << "Memory block addresses:\n" << "buffer: "

<< (void *) buffer << " heap: " << pc2 <

cout << "Memory contents:\n";

cout << pc1 << ": ";

pc1->Show();

cout << pc2 << ": ";

pc2->Show();

JustTesting *pc3, *pc4;

// fix placement new location

pc3 = new (buffer + sizeof (JustTesting))

JustTesting("Better Idea", 6);

pc4 = new JustTesting("Heap2", 10);

cout << "Memory contents:\n";

cout << pc3 << ": ";

pc3->Show();

cout << pc4 << ": ";

pc4->Show();

delete pc2; // free Heap1

delete pc4; // free Heap2

// explicitly destroy placement new objects

pc3->~JustTesting(); // destroy object pointed to by pc3

pc1->~JustTesting(); // destroy object pointed to by pc1

delete [] buffer; // free buffer

cout << "Done\n";

return 0;

}

Here is the output of the program in Listing 12.9:

Just Testing constructed

Heap1 constructed

Memory block addresses:

buffer: 00320AB0 heap: 00320CE0

Memory contents:

00320AB0: Just Testing, 0

00320CE0: Heap1, 20

Better Idea constructed

Heap2 constructed

Memory contents:

00320AD0: Better Idea, 6

00320EC8: Heap2, 10

Heap1 destroyed

Heap2 destroyed

Better Idea destroyed

Just Testing destroyed

Done

The program in Listing 12.9 places the two placement new objects in adjacent location and calls the proper destructors.

Reviewing Techniques

By now, you’ve encountered several programming techniques for dealing with various class-related problems, and you may be having trouble keeping track of all of them. So the following sections summarize several techniques and when they are used.

Overloading the << Operator

To redefine the << operator so that you use it with cout to display an object’s contents, you define a friend operator function that has the following form:

ostream & operator<<(ostream & os, const c_name & obj)

{

os << ... ; // display object contents

return os;

}

Here c_name represents the name of the class. If the class provides public methods that return the required contents, you can use those methods in the operator function and dispense with the friend status.

Conversion Functions

To convert a single value to a class type, you create a class constructor that has the following prototype:

c_name(type_name value);

Here c_name represents the class name, and type_name represents the name of the type you want to convert.

To convert a class type to some other type, you create a class member function that has the following prototype:

operator type_name();

Although this function has no declared return type, it should return a value of the desired type.

Remember to use conversion functions with care. You can use the keyword explicit when declaring a constructor to prevent it from being used for implicit conversions.

Classes Whose Constructors Use new

You need to take several precautions when designing classes that use the new operator to allocate memory pointed to by a class member (yes, we summarized these precautions recently, but the rules are very important to remember, particularly because the compiler does not know them and thus won’t catch your mistakes):

• Any class member that points to memory allocated by new should have the delete operator applied to it in the class destructor. This frees the allocated memory.

• If a destructor frees memory by applying delete to a pointer that is a class member, every constructor for that class should initialize that pointer, either by using new or by setting the pointer to the null pointer.

• Constructors should settle on using either new [] or new, but not a mixture of both. The destructor should use delete [] if the constructors use new [], and it should use delete if the constructors use new.

• You should define a copy constructor that allocates new memory rather than copying a pointer to existing memory. This enables a program to initialize one class object to another. The constructor should normally have the following prototype:

className(const className &)

• You should define a class member function that overloads the assignment operator and that has a function definition with the following prototype (where c_pointer is a member of the c_name class and has the type pointer-to-type_name). The following example assumes that the constructors initialize the variable c_pointer by using new []:

c_name & c_name::operator=(const c_name & cn)

{

if (this == & cn)

return *this; // done if self-assignment

delete [] c_pointer;

// set size number of type_name units to be copied

c_pointer = new type_name[size];

// then copy data pointed to by cn.c_pointer to

// location pointed to by c_pointer

...

return *this;

}

A Queue Simulation

Let’s apply your improved understanding of classes to a programming problem. The Bank of Heather wants to open an automatic teller machine (ATM) in the Food Heap supermarket. The Food Heap management is concerned about lines at the ATM interfering with traffic flow in the market and may want to impose a limit on the number of people allowed to line up at the ATM. The Bank of Heather people want estimates of how long customers will have to wait in line. Your task is to prepare a program that simulates the situation so that management can see what the effect of the ATM might be.

A rather natural way of representing the problem is to use a queue of customers. A queue is an abstract data type (ADT) that holds an ordered sequence of items. New items are added to the rear of the queue, and items can be removed from the front. A queue is a bit like a stack, except that a stack has additions and removals at the same end. This makes a stack a LIFO (last in, first out) structure, whereas the queue is a FIFO (first in, first out) structure. Conceptually, a queue is like a line at a checkout stand or an ATM, so it’s ideally suited to the task. So one part of the project is to define a Queue class. (In Chapter 16, you’ll read about the Standard Template Library queue class, but you’ll learn more by developing your own than by just reading about such a class.)

The items in the queue will be customers. A Bank of Heather representative tells you that, on average, a third of the customers will take one minute to be processed, a third will take two minutes, and a third will take three minutes. Furthermore, customers arrive at random intervals, but the average number of customers per hour is fairly constant. Two more parts of your project will be to design a class representing customers and to put together a program that simulates the interactions between customers and the queue (see Figure 12.7).

Figure 12.7. A queue.

A Queue Class

The first order of business is to design a Queue class. First, you need to list the attributes of the kind of queue you’ll need:

• A queue holds an ordered sequence of items.

• A queue has a limit on the number of items it can hold.

• You should be able to create an empty queue.

• You should be able to check whether a queue is empty.

• You should be able to check whether a queue is full.

• You should be able to add an item to the end of a queue.

• You should be able to remove an item from the front of a queue.

• You should be able to determine the number of items in the queue.

As usual when designing a class, you need to develop a public interface and a private implementation.

The Queue Class Interface

The queue attributes listed in the preceding section suggest the following public interface for a queue class:

class Queue

{

enum {Q_SIZE = 10};

private:

// private representation to be developed later

public:

Queue(int qs = Q_SIZE); // create queue with a qs limit

~Queue();

bool isempty() const;

bool isfull() const;

int queuecount() const;

bool enqueue(const Item &item); // add item to end

bool dequeue(Item &item); // remove item from front

};

The constructor creates an empty queue. By default, the queue can hold up to 10 items, but that can be overridden with an explicit initialization argument:

Queue line1; // queue with 10-item limit

Queue line2(20); // queue with 20-item limit

When using the queue, you can use a typedef to define Item. (In Chapter 14, “Reusing Code in C++,” you’ll learn how to use class templates instead.)

The Queue Class Implementation

After you determine the interface, you can implement it. First, you have to decide how to represent the queue data. One approach is to use new to dynamically allocate an array with the required number of elements. However, arrays aren’t a good match to queue operations. For example, removing an item from the front of the array should be followed up by shifting every remaining element one unit closer to the front. Otherwise, you need to do something more elaborate, such as treat the array as circular. Using a linked list, however, is a reasonable fit to the requirements of a queue. A linked list consists of a sequence of nodes. Each node contains the information to be held in the list, plus a pointer to the next node in the list. For the queue in this example, each data part is a type Item value, and you can use a structure to represent a node:

struct Node

{

Item item; // data stored in the node

struct Node * next; // pointer to next node

};

Figure 12.8 illustrates a linked list.

Figure 12.8. A linked list.

The example shown in Figure 12.8 is called a singly linked list because each node has a single link, or pointer, to another node. If you have the address of the first node, you can follow the pointers to each subsequent node in the list. Commonly, the pointer in the last node in the list is set to NULL (or, equivalently, to 0) to indicate that there are no further nodes. With C++11, you should use the new nullptr keyword. To keep track of a linked list, you must know the address of the first node. You can use a data member of the Queue class to point to the beginning of the list. In principle, that’s all the information you need because you can trace down the chain of nodes to find any other node. However, because a queue always adds a new item to the end of the queue, it is convenient to have a data member point to the last node, too (see Figure 12.9). In addition, you can use data members to keep track of the maximum number of items allowed in the queue and of the current number of items. Thus, the private part of the class declaration can look like this:

class Queue

{

private:

// class scope definitions

// Node is a nested structure definition local to this class

struct Node { Item item; struct Node * next;};

enum {Q_SIZE = 10};

// private class members

Node * front; // pointer to front of Queue

Node * rear; // pointer to rear of Queue

int items; // current number of items in Queue

const int qsize; // maximum number of items in Queue

...

public:

//...

};

Figure 12.9. A Queue object.

The declaration uses the C++ ability to nest a structure or class declaration inside a class. By placing the Node declaration inside the Queue class, you give it class scope. That is, Node is a type that you can use to declare class members and as a type name in class methods, but the type is restricted to the class. That way, you don’t have to worry about this declaration of Node conflicting with some global declaration or with a Node declared inside some other class. Some obsolescent compilers do not support nested structures and classes. If yours doesn’t, then you have to define a Node structure globally, giving it file scope.

Nested Structures and Classes

A structure, a class, or an enumeration declared within a class declaration is said to be nested in the class. It has class scope. Such a declaration doesn’t create a data object. Rather, it specifies a type that can be used internally within the class. If the declaration is made in the private section of the class, then the declared type can be used only within the class. If the declaration is made in the public section, then the declared type can also be used out of the class, through use of the scope-resolution operator. For example, if Node were declared in the public section of the Queue class, you could declare variables of type Queue::Node outside the Queue class.

After you settle on a data representation, the next step is to code the class methods.

The Class Methods

A class constructor should provide values for the class members. Because the queue in this example begins in an empty state, you should set the front and rear pointers to NULL (or 0 or nullptr) and items to 0. Also you should set the maximum queue size qsize to the constructor argument qs. Here’s an implementation that does not work:

Queue::Queue(int qs)

{

front = rear = NULL;

items = 0;

qsize = qs; // not acceptable!

}

The problem is that qsize is a const, so it can be initialized to a value, but it can’t be assigned a value. Conceptually, calling a constructor creates an object before the code within the brackets is executed. Thus, calling the Queue(int qs) constructor causes the program to first allocate space for the four member variables. Then program flow enters the brackets and uses ordinary assignment to place values into the allocated space. Therefore, if you want to initialize a const data member, you have to do so when the object is created before execution reaches the body of the constructor. C++ provides a special syntax for doing just that. It’s called a member initializer list. The member initializer list consists of a comma-separated list of initializers preceded by a colon. It’s placed after the closing parenthesis of the argument list and before the opening bracket of the function body. If a data member is named mdata and if it’s to be initialized to the value val, the initializer has the form mdata(val). Using this notation, you can write the Queue constructor like this:

Queue::Queue(int qs) : qsize(qs) // initialize qsize to qs

{

front = rear = NULL;

items = 0;

}

In general, the initial value can involve constants and arguments from the constructor’s argument list. The technique is not limited to initializing constants; you can also write the Queue constructor like this:

Queue::Queue(int qs) : qsize(qs), front(NULL), rear(NULL), items(0)

{

}

Only constructors can use this initializer-list syntax. As you’ve seen, you have to use this syntax for const class members. You also have to use it for class members that are declared as references:

class Agency {...};

class Agent

{

private:

Agency & belong; // must use initializer list to initialize

...

};

Agent::Agent(Agency & a) : belong(a) {...}

That’s because references, like const data, can be initialized only when created. For simple data members, such as front and items, it doesn’t make much difference whether you use a member initializer list or use assignment in the function body. As you’ll see in Chapter 14, however, it’s more efficient to use the member initializer list for members that are themselves class objects.

The Member Initializer List Syntax

If Classy is a class and if mem1, mem2, and mem3 are class data members, a class constructor can use the following syntax to initialize the data members:

Classy::Classy(int n, int m) :mem1(n), mem2(0), mem3(n*m + 2)

{

//...

}

This initializes mem1 to n, mem2 to 0, and mem3 to n*m + 2. Conceptually, these initializations take place when the object is created and before any code within the brackets is executed. Note the following:

• This form can be used only with constructors.

• You must (at least, in pre-C++11) use this form to initialize a nonstatic const data member.

• You must use this form to initialize a reference data member.

Data members are initialized in the order in which they appear in the class declaration, not in the order in which initializers are listed.

Caution

You can’t use the member initializer list syntax with class methods other than constructors.

The parenthesized form used in the member initializer list can be used in ordinary initializations, too. That is, if you like, you can replace code such as

int games = 162;

double talk = 2.71828;

with

int games(162);

double talk(2.71828);

This allows initializing built-in types to look like initializing class objects.

C++11 Member In-Class Initialization

C++11 allows you to do what would seem to be the intuitively obvious thing to do:

class Classy

{

int mem1 = 10; // in-class initialization

const int mem2 = 20; // in-class initialization

//...

};

This is equivalent to using a member initialization list in the constructors:

Classy::Classy() : mem1(10), mem2(20) {...}

The members mem1 and mem2 get initialized to 10 and 20, respectively, unless a constructor using a member initialization list is called. Then the actual list overrides these default initializations:

Classy::Classy(int n) : mem1(n) {...}

In this case, the constructor would use the value of n to initialize mem1, and mem2 still would be set to 20.

The code for isempty(), isfull(), and queuecount() is simple. If items is 0, the queue is empty. If items is qsize, the queue is full. Returning the value of items answers the question of how many items are in the queue. You’ll see the code later this chapter in Listing 12.11.

Adding an item to the rear of the queue (enqueuing) is more involved. Here is one approach:

bool Queue::enqueue(const Item & item)

{

if (isfull())

return false;

Node * add = new Node; // create node

// on failure, new throws std::bad_alloc exception

add->item = item; // set node pointers

add->next = NULL; // or nullptr;

items++;

if (front == NULL) // if queue is empty,

front = add; // place item at front

else

rear->next = add; // else place at rear

rear = add; // have rear point to new node

return true;

}

In brief, the method goes through the following phases (see Figure 12.10):

1. Terminate if the queue is already full. (For this implementation, the maximum size is selected by the user via the constructor.)

2. Create a new node. If new can’t do so, it throws an exception, which is a topic taken up in Chapter 15, “Friends, Exceptions, and More.” The practical upshot is that unless one provides additional programming to handle the exception, the program terminates.

3. Place proper values into the node. In this case, the code copies an Item value into the data part of the node and sets the node’s next pointer to NULL (or 0 or, in C++11, nullptr). This prepares the node to be the last item in the queue.

4. Increase the item count (items) by one.

5. Attach the node to the rear of the queue. There are two parts to this process. The first is linking the node to the other nodes in the list. This is done by having the next pointer of the currently rear node point to the new rear node. The second part is to set the Queue member pointer rear to point to the new node so that the queue can access the last node directly. If the queue is empty, you must also set the front pointer to point to the new node. (If there’s just one node, it’s both the front and the rear node.)

Figure 12.10. Enqueuing an item.

Removing an item from the front of the queue (dequeuing) also has several steps. Here is one approach:

bool Queue::dequeue(Item & item)

{

if (front == NULL)

return false;

item = front->item; // set item to first item in queue

items--;

Node * temp = front; // save location of first item

front = front->next; // reset front to next item

delete temp; // delete former first item

if (items == 0)

rear = NULL;

return true;

}

In brief, the method goes through the following phases (see Figure 12.11):

1. Terminate if the queue is already empty.

2. Provide the first item in the queue to the calling function. This is accomplished by copying the data portion of the current front node into the reference variable passed to the method.

3. Decrease the item count (items) by one.

4. Save the location of the front node for later deletion.

5. Take the node off the queue. This is accomplished by setting the Queue member pointer front to point to the next node, whose address is provided by front->next.

6. To conserve memory, delete the former first node.

7. If the list is now empty, set rear to NULL. (The front pointer would already be NULL in this case, after setting front->next.) Again, you can use 0 instead of NULL, or, with C++11, you can use nullptr.

Figure 12.11. Dequeuing an item.

Step 4 is necessary because step 5 erases the queue’s memory of where the former first node is.

Other Class Methods?

Do you need any more methods? The class constructor doesn’t use new, so at first glance, it may appear that you don’t have to worry about the special requirements of classes that do use new in the constructors. Of course, that first glance is misleading because adding objects to a queue does invoke new to create new nodes. It’s true that the dequeue() method cleans up by deleting nodes, but there’s no guarantee that a queue will be empty when it expires. Therefore, the class does require an explicit destructor—one that deletes all remaining nodes. Here’s an implementation that starts at the front of the list and deletes each node in turn:

Queue::~Queue()

{

Node * temp;

while (front != NULL) // while queue is not yet empty

{

temp = front; // save address of front item

front = front->next;// reset pointer to next item

delete temp; // delete former front

}

Hmmm. You’ve seen that classes that use new usually require explicit copy constructors and assignment operators that do deep copying. Is that the case here? The first question to answer is, “Does the default memberwise copying do the right thing?” The answer is no. Memberwise copying of a Queue object would produce a new object that points to the front and rear of the same linked list as the original. Thus, adding an item to the copy Queue object changes the shared linked list. That’s bad enough. What’s worse is that only the copy’s rear pointer gets updated, essentially corrupting the list from the standpoint of the original object. Clearly, then, cloning or copying queues requires providing a copy constructor and an assignment constructor that do deep copying.

Of course, that raises the question of why you would want to copy a queue. Well, perhaps you would want to save snapshots of a queue during different stages of a simulation. Or you would like to provide identical input to two different strategies. Actually, it might be useful to have operations that split a queue, the way supermarkets sometimes do when opening an additional checkout stand. Similarly, you might want to combine two queues into one or truncate a queue.

But suppose you don’t want to do any of these things in this simulation. Can’t you simply ignore those concerns and use the methods you already have? Of course you can. However, at some time in the future, you might need to use a queue again, but with copying. And you might forget that you failed to provide proper code for copying. In that case, your programs will compile and run, but they will generate puzzling results and crashes. So it would seem that it’s best to provide a copy constructor and an assignment operator, even though you don’t need them now.

Fortunately, there is a sneaky way to avoid doing this extra work while still protecting against future program crashes. The idea is to define the required methods as dummy private methods:

class Queue

{

private:

Queue(const Queue & q) : qsize(0) { } // preemptive definition

Queue & operator=(const Queue & q) { return *this;}

//...

};

This has two effects. First, it overrides the default method definitions that otherwise would be generated automatically. Second, because these methods are private, they can’t be used by the world at large. That is, if nip and tuck are Queue objects, the compiler won’t allow the following:

Queue snick(nip); // not allowed

tuck = nip; // not allowed

Therefore, instead of being faced with mysterious runtime malfunctions in the future, you’ll get an easier-to-trace compiler error, stating that these methods aren’t accessible. Also this trick is useful when you define a class whose objects really should not be copied.

C++11 provides an alternative way to disable a method by using the keyword delete; Chapter 18 returns to this topic.

Are there any other effects to note? Yes. Recall that a copy constructor is invoked when objects are passed (or returned) by value. However, this is no problem if you follow the preferred practice of passing objects as references. Also a copy constructor is used to create other temporary objects. But the Queue definition lacks operations that lead to temporary objects, such as overloading the addition operator.

The Customer Class

At this point, we need to design a customer class. In general, an ATM customer has many properties, such as a name, account numbers, and account balances. However, the only properties you need for the simulation are when a customer joins the queue and the time required for the customer’s transaction. When the simulation produces a new customer, the program should create a new customer object, storing in it the customer’s time of arrival and a randomly generated value for the transaction time. When the customer reaches the front of the queue, the program should note the time and subtract the queue-joining time to get the customer’s waiting time. Here’s how you can define and implement the Customer class:

class Customer

{

private:

long arrive; // arrival time for customer

int processtime; // processing time for customer

public:

Customer() { arrive = processtime = 0; }

void set(long when);

long when() const { return arrive; }

int ptime() const { return processtime; }

};

void Customer::set(long when)

{

processtime = std::rand() % 3 + 1;

arrive = when;

}

The default constructor creates a null customer. The set() member function sets the arrival time to its argument and randomly picks a value from 1 through 3 for the processing time.

Listing 12.10 gathers together the Queue and Customer class declarations, and Listing 12.11 provides the methods.

Listing 12.10. queue.h

// queue.h -- interface for a queue

#ifndef QUEUE_H_

#define QUEUE_H_

// This queue will contain Customer items

class Customer

{

private:

long arrive; // arrival time for customer

int processtime; // processing time for customer

public:

Customer() { arrive = processtime = 0; }

void set(long when);

long when() const { return arrive; }

int ptime() const { return processtime; }

};

typedef Customer Item;

class Queue

{

private:

// class scope definitions

// Node is a nested structure definition local to this class

struct Node { Item item; struct Node * next;};

enum {Q_SIZE = 10};

// private class members

Node * front; // pointer to front of Queue

Node * rear; // pointer to rear of Queue

int items; // current number of items in Queue

const int qsize; // maximum number of items in Queue

// preemptive definitions to prevent public copying

Queue(const Queue & q) : qsize(0) { }

Queue & operator=(const Queue & q) { return *this;}

public:

Queue(int qs = Q_SIZE); // create queue with a qs limit

~Queue();

bool isempty() const;

bool isfull() const;

int queuecount() const;

bool enqueue(const Item &item); // add item to end

bool dequeue(Item &item); // remove item from front

};

#endif

Listing 12.11. queue.cpp

// queue.cpp -- Queue and Customer methods

#include "queue.h"

#include // (or stdlib.h) for rand()

// Queue methods

Queue::Queue(int qs) : qsize(qs)

{

front = rear = NULL; // or nullptr

items = 0;

}

Queue::~Queue()

{

Node * temp;

while (front != NULL) // while queue is not yet empty

{

temp = front; // save address of front item

front = front->next;// reset pointer to next item

delete temp; // delete former front

}

bool Queue::isempty() const

{

return items == 0;

}

bool Queue::isfull() const

{

return items == qsize;

}

int Queue::queuecount() const

{

return items;

}

// Add item to queue

bool Queue::enqueue(const Item & item)

{

if (isfull())

return false;

Node * add = new Node; // create node

// on failure, new throws std::bad_alloc exception

add->item = item; // set node pointers

add->next = NULL; // or nullptr;

items++;

if (front == NULL) // if queue is empty,

front = add; // place item at front

else

rear->next = add; // else place at rear

rear = add; // have rear point to new node

return true;

}

// Place front item into item variable and remove from queue

bool Queue::dequeue(Item & item)

{

if (front == NULL)

return false;

item = front->item; // set item to first item in queue

items--;

Node * temp = front; // save location of first item

front = front->next; // reset front to next item

delete temp; // delete former first item

if (items == 0)

rear = NULL;

return true;

}

// customer method

// when is the time at which the customer arrives

// the arrival time is set to when and the processing

// time set to a random value in the range 1 - 3

void Customer::set(long when)

{

processtime = std::rand() % 3 + 1;

arrive = when;

}

The ATM Simulation

You now have the tools needed for the ATM simulation. The program should allow the user to enter three quantities: the maximum queue size, the number of hours the program will simulate, and the average number of customers per hour. The program should use a loop in which each cycle represents one minute. During each minute cycle, the program should do the following:

1. Determine whether a new customer has arrived. If so, add the customer to the queue if there is room; otherwise, turn the customer away.

2. If no one is being processed, take the first person from the queue. Determine how long the person has been waiting and set a wait_time counter to the processing time that the new customer will need.

3. If a customer is being processed, decrement the wait_time counter by one minute.

4. Track various quantities, such as the number of customers served, the number of customers turned away, cumulative time spent waiting in line, and cumulative queue length.

When the simulation cycle is finished, the program should report various statistical findings.

An interesting matter is how the program determines whether a new customer has arrived. Suppose that on average, 10 customers arrive per hour. That amounts to a customer every 6 minutes. The program computes and stores that value in the variable min_per_cust. However, having a customer show up exactly every 6 minutes is unrealistic. What you really want (at least most of the time) is a more random process that averages to a customer every 6 minutes. The program uses this function to determine whether a customer shows up during a cycle:

bool newcustomer(double x)

{

return (std::rand() * x / RAND_MAX < 1);

}

Here’s how it works. The value RAND_MAX is defined in the cstdlib file (formerly stdlib.h) and represents the largest value the rand() function can return (0 is the lowest value). Suppose that x, the average time between customers, is 6. Then the value of rand() * x / RAND_MAX will be somewhere between 0 and 6. In particular, it will be less than 1 one-sixth of the time, on average. However, it’s possible that this function might yield two customers spaced 1 minute apart one time and two customers 20 minutes apart another time. This behavior leads to the clumpiness that often distinguishes real processes from the clocklike regularity of exactly one customer every 6 minutes. This particular method breaks down if the average time between arrivals drops below 1 minute, but the simulation is not intended to handle that scenario. If you did need to deal with such a case, you’d use a finer time resolution, perhaps letting each cycle represent 10 seconds.

Listing 12.12 presents the details of the simulation. Running the simulation for a long time period provides insight into long-term averages, and running it for short times provides insight into short-term variations.

Listing 12.12. bank.cpp

// bank.cpp -- using the Queue interface

// compile with queue.cpp

#include

#include // for rand() and srand()

#include // for time()

#include "queue.h"

const int MIN_PER_HR = 60;

bool newcustomer(double x); // is there a new customer?

int main()

{

using std::cin;

using std::cout;

using std::endl;

using std::ios_base;

// setting things up

std::srand(std::time(0)); // random initializing of rand()

cout << "Case Study: Bank of Heather Automatic Teller\n";

cout << "Enter maximum size of queue: ";

int qs;

cin >> qs;

Queue line(qs); // line queue holds up to qs people

cout << "Enter the number of simulation hours: ";

int hours; // hours of simulation

cin >> hours;

// simulation will run 1 cycle per minute

long cyclelimit = MIN_PER_HR * hours; // # of cycles

cout << "Enter the average number of customers per hour: ";

double perhour; // average # of arrival per hour

cin >> perhour;

double min_per_cust; // average time between arrivals

min_per_cust = MIN_PER_HR / perhour;

Item temp; // new customer data

long turnaways = 0; // turned away by full queue

long customers = 0; // joined the queue

long served = 0; // served during the simulation

long sum_line = 0; // cumulative line length

int wait_time = 0; // time until autoteller is free

long line_wait = 0; // cumulative time in line

// running the simulation

for (int cycle = 0; cycle < cyclelimit; cycle++)

{

if (newcustomer(min_per_cust)) // have newcomer

{

if (line.isfull())

turnaways++;

else

{

customers++;

temp.set(cycle); // cycle = time of arrival

line.enqueue(temp); // add newcomer to line

}

if (wait_time <= 0 && !line.isempty())

{

line.dequeue (temp); // attend next customer

wait_time = temp.ptime(); // for wait_time minutes

line_wait += cycle - temp.when();

served++;

}

if (wait_time > 0)

wait_time--;

sum_line += line.queuecount();

}

// reporting results

if (customers > 0)

{

cout << "customers accepted: " << customers << endl;

cout << " customers served: " << served << endl;

cout << " turnaways: " << turnaways << endl;

cout << "average queue size: ";

cout.precision(2);

cout.setf(ios_base::fixed, ios_base::floatfield);

cout << (double) sum_line / cyclelimit << endl;

cout << " average wait time: "

<< (double) line_wait / served << " minutes\n";

}

else

cout << "No customers!\n";

cout << "Done!\n";

return 0;

}

// x = average time, in minutes, between customers

// return value is true if customer shows up this minute

bool newcustomer(double x)

{

return (std::rand() * x / RAND_MAX < 1);

}

Note

You might have a compiler that has not implemented bool. In that case, you can use int instead of bool, 0 instead of false, and 1 instead of true. You might also have to use stdlib.h and time.h instead of the newer cstdlib and ctime. You might have to define RAND_MAX yourself.

Here are a few sample runs of the program built from Listings 12.10, 12.11, and 12.12:

Case Study: Bank of Heather Automatic Teller

Enter maximum size of queue: 10

Enter the number of simulation hours: 100

Enter the average number of customers per hour: 15

customers accepted: 1485

customers served: 1485

turnaways: 0

average queue size: 0.15

average wait time: 0.63 minutes

Done!

Case Study: Bank of Heather Automatic Teller

Enter maximum size of queue: 10

Enter the number of simulation hours: 100

Enter the average number of customers per hour: 30

customers accepted: 2896

customers served: 2888

turnaways: 101

average queue size: 4.64

average wait time: 9.63 minutes

Done!

Case Study: Bank of Heather Automatic Teller

Enter maximum size of queue: 20

Enter the number of simulation hours: 100

Enter the average number of customers per hour: 30

customers accepted: 2943

customers served: 2943

turnaways: 93

average queue size: 13.06

average wait time: 26.63 minutes

Done!

Note that going from 15 customers per hour to 30 customers per hour doesn’t double the average wait time; it increases it by about a factor of 15. Allowing a longer queue just makes matters worse. However, the simulation doesn’t allow for the fact that many customers, frustrated with a long wait, would simply leave the queue.

Here are a few more sample runs of the program in Listing 12.12; they illustrate the short-term variations you might see, even though the average number of customers per hour is kept constant:

Case Study: Bank of Heather Automatic Teller

Enter maximum size of queue: 10

Enter the number of simulation hours: 4

Enter the average number of customers per hour: 30

customers accepted: 114

customers served: 110

turnaways: 0

average queue size: 2.15

average wait time: 4.52 minutes

Done!

Case Study: Bank of Heather Automatic Teller

Enter maximum size of queue: 10

Enter the number of simulation hours: 4

Enter the average number of customers per hour: 30

customers accepted: 121

customers served: 116

turnaways: 5

average queue size: 5.28

average wait time: 10.72 minutes

Done!

Case Study: Bank of Heather Automatic Teller

Enter maximum size of queue: 10

Enter the number of simulation hours: 4

Enter the average number of customers per hour: 30

customers accepted: 112

customers served: 109

turnaways: 0

average queue size: 2.41

average wait time: 5.16 minutes

Done!

Summary

This chapter covers many important aspects of defining and using classes. Several of these aspects are subtle—even difficult—concepts. If some of them seem obscure or unusually complex to you, don’t feel bad; they affect most newcomers to C++ that way. Often the way you come to really appreciate concepts such as copy constructors is through getting into trouble by ignoring them. So some of the material in this chapter may seem vague to you until your own experiences enrich your understanding.

You can use new in a class constructor to allocate memory for data and then assign the address of the memory to a class member. This enables a class, for example, to handle strings of various sizes without committing the class design in advance to a fixed array size. Using new in class constructors also raises potential problems when an object expires. If an object has member pointers pointing to memory allocated by new, freeing the memory used to hold the object does not automatically free the memory pointed to by the object member pointers. Therefore, if you use new in a class constructor to allocate memory, you should use delete in the class destructor to free that memory. That way, the demise of an object automatically triggers the deletion of pointed-to memory.

Objects that have members pointing to memory allocated by new also have problems with initializing one object to another or assigning one object to another. By default, C++ uses memberwise initialization and assignment, which means that the initialized or the assigned-to object winds up with exact copies of the original object’s members. If an original member points to a block of data, the copy member points to the same block. When the program eventually deletes the two objects, the class destructor attempts to delete the same block of memory twice, which is an error. The solution is to define a special copy constructor that redefines initialization and to overload the assignment operator. In each case, the new definition should create duplicates of any pointed-to data and have the new object point to the copies. That way, both the old and the new objects refer to separate but identical data, with no overlap. The same reasoning applies to defining an assignment operator. In each case, the goal is to make a deep copy—that is, to copy the real data and not just pointers to the data.

When an object has automatic storage or external storage, the destructor for that object is called automatically when the object ceases to exist. If you allocate storage for an object by using new and assign its address to a pointer, the destructor for that object is called automatically when you apply delete to the pointer. However, if you allocate storage for class objects by using placement new instead of regular new, you also take on the responsibility of calling the destructor for that object explicitly by invoking the destructor method with a pointer to the object. C++ allows you to place structure, class, and enumeration definitions inside a class. Such nested types have class scope, meaning that they are local to the class and don’t conflict with structures, classes, and enumerations of the same name that are defined elsewhere.

C++ provides a special syntax for class constructors that can be used to initialize data members. This syntax consists of a colon followed by a comma-separated list of initializers. This is placed after the closing parenthesis of the constructor arguments and before the opening brace of the function body. Each initializer consists of the name of the member being initialized followed by parentheses containing the initialization value. Conceptually, these initializations take place when the object is created and before any statements in the function body are executed. The syntax looks like this:

queue(int qs) : qsize(qs), items(0), front(NULL), rear(NULL) { }

This form is obligatory if the data member is a nonstatic const member or a reference, except that C++11 in-class initialization can be used for nonstatic const members.

C++11 allows in-class initialization (that is, initialization in the class definition):

class Queue

{

private:

...

Node * front = NULL;

enum {Q_SIZE = 10};

Node * rear = NULL;

int items = 0;

const int qsize = Q_SIZE;

...

};

This is equivalent to using a member initialization list. However, any constructor using a membership initialization list will override the corresponding in-class initializations.

As you might have noticed, classes require much more care and attention to detail than do simple C-style structures. In return, they do much more for you.

Chapter Review

1. Suppose a String class has the following private members:

class String

{

private:

char * str; // points to string allocated by new

int len; // holds length of string

//...

};

a. What’s wrong with this default constructor?

String::String() {}

b. What’s wrong with this constructor?

String::String(const char * s)

{

str = s;

len = strlen(s);

}

c. What’s wrong with this constructor?

String::String(const char * s)

{

strcpy(str, s);

len = strlen(s);

}

2. Name three problems that may arise if you define a class in which a pointer member is initialized by using new. Indicate how they can be remedied.

3. What class methods does the compiler generate automatically if you don’t provide them explicitly? Describe how these implicitly generated functions behave.

4. Identify and correct the errors in the following class declaration:

class nifty

{

// data

char personality[];

int talents;

// methods

nifty();

nifty(char * s);

ostream & operator<<(ostream & os, nifty & n);

}

nifty:nifty()

{

personality = NULL;

talents = 0;

}

nifty:nifty(char * s)

{

personality = new char [strlen(s)];

personality = s;

talents = 0;

}

ostream & nifty:operator<<(ostream & os, nifty & n)

{

os << n;

}

5. Consider the following class declaration:

class Golfer

{

private:

char * fullname; // points to string containing golfer's name

int games; // holds number of golf games played

int * scores; // points to first element of array of golf scores

public:

Golfer();

Golfer(const char * name, int g= 0);

// creates empty dynamic array of g elements if g > 0

Golfer(const Golfer & g);

~Golfer();

};

a. What class methods would be invoked by each of the following statements?

Golfer nancy; // #1

Golfer lulu("Little Lulu"); // #2

Golfer roy("Roy Hobbs", 12); // #3

Golfer * par = new Golfer; // #4

Golfer next = lulu; // #5

Golfer hazzard = "Weed Thwacker"; // #6

*par = nancy; // #7

nancy = "Nancy Putter"; // #8

b. Clearly, the class requires several more methods to make it useful. What additional method does it require to protect against data corruption?

Programming Exercises

1. Consider the following class declaration:

class Cow {

char name[20];

char * hobby;

double weight;

public:

Cow();

Cow(const char * nm, const char * ho, double wt);

Cow(const Cow c&);

~Cow();

Cow & operator=(const Cow & c);

void ShowCow() const; // display all cow data

};

Provide the implementation for this class and write a short program that uses all the member functions.

2. Enhance the String class declaration (that is, upgrade string1.h to string2.h) by doing the following:

a. Overload the + operator to allow you to join two strings into one.

b. Provide a stringlow() member function that converts all alphabetic characters in a string to lowercase. (Don’t forget the cctype family of character functions.)

c. Provide a stringup() member function that converts all alphabetic characters in a string to uppercase.

d. Provide a member function that takes a char argument and returns the number of times the character appears in the string.

Test your work in the following program:

// pe12_2.cpp

#include

using namespace std;

#include "string2.h"

int main()

{

String s1(" and I am a C++ student.");

String s2 = "Please enter your name: ";

String s3;

cout << s2; // overloaded << operator

cin >> s3; // overloaded >> operator

s2 = "My name is " + s3; // overloaded =, + operators

cout << s2 << ".\n";

s2 = s2 + s1;

s2.stringup(); // converts string to uppercase

cout << "The string\n" << s2 << "\ncontains " << s2.has('A')

<< " 'A' characters in it.\n";

s1 = "red"; // String(const char *),

// then String & operator=(const String&)

String rgb[3] = { String(s1), String("green"), String("blue")};

cout << "Enter the name of a primary color for mixing light: ";

String ans;

bool success = false;

while (cin >> ans)

{

ans.stringlow(); // converts string to lowercase

for (int i = 0; i < 3; i++)

{

if (ans == rgb[i]) // overloaded == operator

{

cout << "That's right!\n";

success = true;

break;

}

if (success)

break;

else

cout << "Try again!\n";

}

cout << "Bye\n";

return 0;

}

Your output should look like this sample run:

Please enter your name: Fretta Farbo

My name is Fretta Farbo.

The string

MY NAME IS FRETTA FARBO AND I AM A C++ STUDENT.

contains 6 'A' characters in it.

Enter the name of a primary color for mixing light: yellow

Try again!

BLUE

That's right!

Bye

3. Rewrite the Stock class, as described in Listings 10.7 and 10.8 in Chapter 10 so that it uses dynamically allocated memory directly instead of using string class objects to hold the stock names. Also replace the show() member function with an overloaded operator<<() definition. Test the new definition program in Listing 10.9.

4. Consider the following variation of the Stack class defined in Listing 10.10:

// stack.h -- class declaration for the stack ADT

typedef unsigned long Item;

class Stack

{

private:

enum {MAX = 10}; // constant specific to class

Item * pitems; // holds stack items

int size; // number of elements in stack

int top; // index for top stack item

public:

Stack(int n = MAX); // creates stack with n elements

Stack(const Stack & st);

~Stack();

bool isempty() const;

bool isfull() const;

// push() returns false if stack already is full, true otherwise

bool push(const Item & item); // add item to stack

// pop() returns false if stack already is empty, true otherwise

bool pop(Item & item); // pop top into item

Stack & operator=(const Stack & st);

};

As the private members suggest, this class uses a dynamically allocated array to hold the stack items. Rewrite the methods to fit this new representation and write a program that demonstrates all the methods, including the copy constructor and assignment operator.

5. The Bank of Heather has performed a study showing that ATM customers won’t wait more than one minute in line. Using the simulation from Listing 12.10, find a value for number of customers per hour that leads to an average wait time of one minute. (Use at least a 100-hour trial period.)

6. The Bank of Heather would like to know what would happen if it added a second ATM. Modify the simulation in this chapter so that it has two queues. Assume that a customer will join the first queue if it has fewer people in it than the second queue and that the customer will join the second queue otherwise. Again, find a value for number of customers per hour that leads to an average wait time of one minute. (Note: This is a nonlinear problem in that doubling the number of ATMs doesn’t double the number of customers who can be handled per hour with a one-minute wait maximum.)

Перейти на страницу: