H14-106ClassClient.pdf

(197 KB) Pobierz

CS106B

J Zelenski

Handout #14

Jan 16, 2008

The fun life of CS106 class client

Our CS106 library contains a set of classes that model the classic CS data structures—vectors,

stacks, sets, maps, and more. We will spend quite a bit of time this quarter exploring these classes

and considering them from two perspectives. Initially, we will interact with the classes solely in the

position of a client. Later in the quarter, we will revisit the classes from an implementer's perspective

and work through different implementation options and their tradeoffs. This handout provides

information on the client-side use of the classes to share with you on what's available and how to

put it to work. The later chapters of the reader will dig into the internals of the classes and explore

various implementation strategies.

Objects and classes

From your CS106A (or equivalent) experience, we are expecting that you are familiar with using

classes. Object-oriented programming in C++ is quite similar in concept to Java, but there are

some various syntactic differences. Reader section 8.1 gives an overview of object-oriented

programming in general and our earlier "Getting started in C++" handout notes how the features

are expressed in C++. You already have seen using C++ objects— the string and stream

classes—so by now you're on your way to becoming an old pro!

One key difference between Java and C++ objects is that Java creates all objects in the heap and

accesses them via pointers (although they are called "references" and don't explicitly mention

they are pointers, nonetheless). In C++, you have the option of allocating objects on the stack or in

the heap, but by default we use stack allocation as it is convenient and efficient.

One feature of Java's "objects-are-always-pointers" strategy is that you are automatically always

passing/assigning pointers, which is more efficient than making full object copies. In C++, we can

achieve similar efficiency by taking care to pass objects by reference whenever possible and only

using assignment between objects when a full copy is truly needed. It's a good idea to get used to

these habits now since they are endemic among C++ programmers, and, of course, you want to fit

in at all the hippest parties.

CS106 class library

The classes in our library are the

Scanner

Vector

Grid

Stack

Queue

Set

, and

Map

This

handout provides an introduction to these classes with a listing of the class interfaces and some

sample client code for each.

The CS106 classes represent many of the classic, fundamental data structures of computer science

and you'll soon discover that they provide tremendously useful functionality. It is a real delight to

use these classes as a client. Without any concern for how it works internally, you will be able to

create a set, for example, and use its member functions to add and remove elements or intersect with

other sets and so on.

There is a huge amount of leverage gained by having such commonly needed functionality in a

shared library. For starters, the range of problems that you can attempt to solve is vastly enlarged by

having better tools. My colleague Nick Parlante likes to describe this as "living higher on the food

chain"—you can focus solving more interesting problems when you're not bogged down in the

1 The official C++ Standard Template Library (STL) contains classes similar in spirit to those in our library. As much I love

to teach to standards, the design of the STL is hairy enough that I believe it would interfere with our pedagogical goals. We

may spend a little time at the end of the quarter on the STL, but only after you have experience using our kinder, gentler

version. The optional lab CS106L will discuss the STL if you want to drop in to become acquainted with it.

petty details of directly managing an array and so on. The classes are very efficiently implemented,

by using advanced techniques we will later learn, but in the meantime, you are still able to take

advantage of that streamlined performance by using the classes, without having to know how they

work. By having each class model a clear abstraction (such as the waiting line analog for a queue),

you can choose the right data model for your program and naturally express your computation in

terms of member function calls on that object, which leads to clear and clean code.

I just can't speak highly enough of how much more reliable, efficient, and just plain fun coding

becomes when you are able to work as a client of well-written libraries, so let's get started!

Scanner

The

Scanner

class provides functionality for dividing a string into separate words or

tokens.

Although the standard stream extraction >> has some features that could be used for this, that

approach is somewhat primitive and inflexible and involves some tedious coding. A scanner is

designed to simply the tasks of tokenization and comes in quite handy when doing any sort of

string or file processing. Here are a few ideas to get you thinking about its uses:

• dividing a document into component words for textual analysis, such as a word frequency

count, preparing an index, or building a concordance

• separating a file pathname into its components (e.g. the sub-directories within

HardDisk/Classes/CS106/Handouts/H36 Section 5.doc)

• parsing a user's command (e.g. "turn left", "find price < 5") in order to act upon the request

• evaluating a arithmetic expression (3 + 4 * 7)

The basic public interface of the

Scanner

class is listed below:

class

Scanner

{

public:

Scanner();

~Scanner();

// constructor (invoked when allocated)

// destructor (invoked when deallocated)

void

setInput(string

str); // set string to be scanned

string

nextToken();

bool

hasMoreTokens();

void

saveToken(string

token);

enum

spaceOptionT

{ PreserveSpaces, IgnoreSpaces };

void

setSpaceOption(spaceOptionT

option);

spaceOptionT

getSpaceOption();

};

// other advanced options excerpted for clarity

The idiomatic pattern for using a scanner is to create a new object, set the input string to be scanned,

and then enter a loop that calls

nextToken

while

hasMoreTokens

returns true. Here is some

sample code that uses the scanner to reports the number of tokens entered in a user's response:

void CountTokens()

{

Scanner scanner;

cout << "Please enter a sentence: ";

scanner.setInput(GetLine());

int count = 0;

while (scanner.hasMoreTokens()) {

scanner.nextToken();

count++;

}

cout << "You entered " << count << " tokens." << endl;

}

The next bit of code shows finding the longest token read from a file. In the outer loop,

getline

read a line from the file and in the inner loop, the line is tokenized by a scanner.

// Given an opened input stream, reads contents line by line,

// uses scanner to break line into tokens and tracks the

// longest token seen, which is returned from the function

string FindLongestToken(ifstream & in)

{

string longest = "";

Scanner scanner;

while (true) {

// outer loop reads file line-by-line

string line;

getline(in, line);

if (in.fail()) break; // no more lines to read

scanner.setInput(line);

while (scanner.hasMoreTokens()) {

// inner loop tokenizes a line

string token = scanner.nextToken();

if (token.length() > longest.length())

longest = token;

}

return longest;

}

There are various scanner options that control how certain inputs are scanned. Most of these

options are only used in limited situations, but one option that is commonly manipulated is the

SpaceOption

. This options controls whether whitespace tokens are returned from

nextToken

skipped over and ignored. The default is for every token, including spaces, to be returned, but you

can cause them to be discarded by changing the option:

scanner.setSpaceOption(Scanner::IgnoreSpaces);

This is handy when you want to ignore spaces and only process non-space tokens. Note that the

spaceOptionT

enum is defined within the Scanner class, so when referring to those values as a

client, you must fully specify the name including the scope qualification

Scanner::.

This tells the

compiler to look for the name within the Scanner class instead of assuming it is top-level entity.

This is like the

string::npos

constant.

You can read more about the

Scanner

class and its details in section 8.6 of the reader. The full

scanner.h

file with extensive comments is listed in the reader appendix. The

Scanner

class

interface is also browsable from the "Documentation" link on our class web site.

Class templates

Most of the classes in the CS106 class library are

container

classes. Container classes are used to

store data, such a list of students enrolled in a class, a table of dorm room assignments, or a set of

skills that a job applicant has. Pretty much all programs store data and often the ways they need to

organize and access it fits into standard patterns. Thus, a few well-designed container classes can

go a long way toward meeting many common data storage needs.

All of our container classes are provided as

class templates.

A class template means that the class is

defined in terms of a "placeholder" for the element type being stored. Rather than defining the

container to store only students or only numbers, the placeholder allows the template to be used to

store any kind of element the client might choose. The client fills in the placeholder when declaring

and allocating the container object. The client can thus create a set of numbers, a set of strings, or a

set of attributes, as needed.

Mostly all this means to you as a client is that you can use a container to store whatever you need.

You will need to annotate the container class name with the element type you wish to store in angle-

brackets when declaring and allocating the container object, e.g.

Vector<int>

Vector<string>

which is a little bit clunky, but a small price to pay for such flexibility!

Templates are a marvelous C++ feature that supports

generic programming.

No one wants to write

a whole gob of duplicate vector classes, one that holds ints, another for strings, and yet another for

students. The template is a generic form capable of being specialized on demand. The template code

is written, tested, optimized, debugged, and commented just once, yet can be used for a wide variety

of needs. And C++ templates are completely type-safe— the compiler keeps it straight and will not

confuse a vector of floats with one holding bools. However, these benefits come with a little bit of

goop, most notably that the syntax can be cumbersome and that the compiler errors reported when

you've made a mistake using a template can sometimes be confusing. Be sure to take advantage of

the wisdom of our course staff and visit us in the LaIR or send an email if you need some help

deciphering one of these cryptic error messages.

Vector

The

Vector

class is the simplest of all the container classes. The abstraction it provides is a linear,

indexed homogeneous collection. (Think Java's ArrayList) A vector serves the same basic purpose

as the built-in C++ array. What makes the vector better than the raw array?

• A vector knows its size

• Access to elements is bounds checked

• The vector handles all memory-management (shrink/grow as elements added/removed)

• Insert and remove handle shuffling elements up and down to open/close up space

• It supports deep-copying, when you need to clone the collection

In my opinion, once you have the

Vector

class in your toolkit, there is little reason to bother with

raw array, since a vector is a better version of the same thing.

The public member functions of the

Vector

class are listed below. Note that it is a class template,

so the arguments and return type for the member functions refer to the placeholder

ElemType

that

is filled by the client when declaring and allocating a vector. The excerpt below just lists the

prototypes, the full

vector.h

interface includes comments describing the use and operations.

template <typename ElemType>

class

Vector

{

public:

Vector();

~Vector();

int

size();

bool

isEmpty();

ElemType

getAt(int

index);

void

setAt(int

index, ElemType value);

void

add(ElemType

value);

void

insertAt(int

pos, ElemType value);

void

removeAt(int

pos);

};

Vector also implements a few overloaded operators for convenience. The square brackets can be

applied to a vector to access an individual element by index. The class also provides deep-copying

support so that assigning one vector to another or passing a vector by value will make a full, distinct

copy of the entire vector contents. Copying can be expensive, especially for a large vector, so you

typically avoid copying whenever possible, but when you do need a copy, the class makes it easy to

get one.

The Vector is a great tool for any homogenous collection. Here's a sample function that reads

scores into a vector and prints the sequence:

// Fills vector with a sequence of integers read from console

void ReadScoresFromUser(Vector<int> & v) // pass-by-ref since updating v

{

while (true) {

cout << "Enter number (-1 if done): ";

int num = GetInteger();

if (num == -1) break;

v.add(num);

// append to end of vector

}

// Prints contents of vector, one number per line

void PrintVector(Vector<int> & v)

// pass-by-ref for efficiency

{

for (int i = 0; i < v.size(); i++)

cout << v[i] << endl;

// or equivalent v.getAt(i)

}

int main()

{

Vector<int> scores;

ReadScoresFromUser(scores);

PrintVector(scores);

return 0;

}

Instead of adding each value to the end of the vector, you could use the

insertAt

member function

to store the values in ascending order, with this small change to the above code:

H14-106ClassClient.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: