Notes

Outline

"Class User Programming and the..." Class User Programming and the Standard Containers

Overview Types and user-defined types The standard library Name spaces Class user programming with templates Basic containers & iterators list, stacks, strings, vectors, maps & sets Special iterators for I/O Examples of reusing software components Calculator — stack type Text justification — string type Employee security & spell checking — set type Count unique words — map type Sorting a list of words — map type

Reusable Software Components Testing time is reduced Investment can be amortized Labor can be divided Class libraries are key to reusable software Features of C++ that facilitate reuse are Inheritance, Polymorphism, Parameterized classes, and Similar syntax for built-ins as UDT (e.g., I/O, and Indexing containers)

Parameterized Types Examples stack<int> x; Stack of integers stack<stack<int> > y; Stack of stack of integers vector<int> z; An integer array indexed by integers vector< vector<int> > a; A two dimensional array list<string> w; A doubly linked list of Strings When using parameterized types Implementation is often not a separate cpp file, The compilation process is slowed down,

Using Namespaces New feature allows multiple class libraries in same client Syntax namespace foo {void bar(){ cout<<"foo::bar"; }} namespace xxx {void bar(){ cout<<"xxx::bar"; }} using namespace foo; main(){ bar(); xxx::bar(); return 0; }

Stacks and Queues

UDT Example Problem: Simulate a simple hand-held calculator Interface of stack Syntax — how to call it Semantics — how to use it

UDT Example Implicit operations (value semantics) Create a stack Destroy a stack Assign a stack to another stack Operations Push an element pop an element The user-provider model calc.cpp is sometimes said to be a client stack.cpp (recently renamed to stack) is sometimes said to be a server stack is independent of calculator programs Calc is independent of specific stack types

Calculator Programs See listings at end of chapter Source for algebraic notation with variables: lib\calc\main.cpp \lib\stlcalc\main.cpp

Type string C does not have a string type C programmers act as if it does string.h defines pseudo-strings vector of characters terminated by a null byte Pointers called “strings” Operations char* strcpy(char*, const char*); int strcmp(const char*, const char*); int strlen(const char*); Minimal compiler support

Find the Bugs! char* max(char* p1, char* p2){ char array[10]; char* p3 = array; if(strcmp(p1, p2) > 0) strcpy(p3, p1); else strcpy(p3, p2); return p3; }

Type string Full value semantics Create string object with no default value Create string object with initial value of type char* Create string object with initial value of type string Pass by value Return as function value Assign one string object to another Automatically deallocate string objects

Type string (Continued) Explicit operations Length Substrings Character search Concatenation Comparison I/O

A string Object

Declarations #include <string> using namespace std; string line; string word("hello"); // string word="hello"; string word2 = word; string word3(word2);

String Lengths int len; len = line.length(); // 0 len = word.length(); // 5

Compute Substrings Two arguments: First argument indicates position Start counting from zero Second (optional) argument indicates size Start counting from one, string letters("abcdefg"); letters.substr(1, 3) // “bcd”

Character searches Searching size_type pos; pos = letters.find('a'); //  0 pos = letters.find("d"); //  3 pos = letters.find('x'); // -1 Testing Strategy #1 if(pos == (size_type)-1)  cout << "not found"; Strategy #2 if(pos == string::npos) cout << "not found";

Subscripting char ch; ch = letters[3]; // ‘d’ letters[3] = 'x'; // “abcxefg” letters[letters.index('x')] = 'y'; // “abcyefg”

Concatenation word + "World" // “helloWorld” line + word // “hello” line + " " + word // “ hello” line.substr(0,pos) + " " + line.substr(pos) ; line += " " + word;

Comparison

Input and Output cin >> word; cout << word<< endl ; while (cin >> word) cout << word << endl ;

Copy by Assignment line = word; line = line + " " + word; word = letters.substr(0,4);    // “ abcd”

Creation by Copy Passing parameters by value void funcl ( string word ); funcl ( letters ) ; Return by value string func2( ); word = func2( );

Calling Member Functions word.length(); How many Actual arguments? Arguments in argument list?

Calling Member Functions

string Type Example Write a program that converts words into pig-latin. input: The quick brown fox jumped over the lazy dog’s back 1234567890 times. The lazy dog jumped over the quick brown fox’s back 1234567890 times. output: Hetay uickqay rownbay oxfay umpedjay veroay hetay azylay ogday’s ackbay 1234567890 imestay. Hetay azylay ogday umpedjay veroay hetay uickqay rownbay oxfay’s ackbay 1234567890 imestay.

"See part1\unit3\examples\piglatin..." See part1\unit3\examples\piglatin\piglatin.cpp

Text Justification Input: The suggestions that follow are meant to broaden your awareness of C programming issues that affect portability, and to serve as informal guidelines as you write programs in C language. These are not rules, but cautions, for there is no simple way to develop the skill of writing portable C programs. Still, if you remain aware of these issues and suggestions, you improve your chances to write C programs that are portable from one UNIX system environment to another, with little or no need to change the program. Output: The  suggestions  that  follow are  meant  to  broaden  your awareness of C programming  issues  that affect portability, and to serve as informal guidelines as you write programs in C language. These are not rules,  but cautions, for there is no simple  way  to  develop  the skill of writing portable C programs.  Still,  if  you  remain aware of these issues and suggestions, you improve your chances to  write  C  programs that  are  portable  from  one  UNIX  system  environment to another, with little or no need to change the program.

Text Justification Stage 1 The The suggestions The suggestions that The suggestions that follow The suggestions that follow are Stage 2 The suggestions that follow are The  suggestions that follow are The  suggestions  that follow are The  suggestions  that  follow are

Text Justification Implement the just text justification program What is a simple algorithm to justify lines of words? See detailed instructions at end of chapter

VI Digression This program is useful for VI users! Justify the next paragraph: !}just Justify lines 96-99: :96,99!just Justify the next sentence: :!)just Justify the current line: !!just

Container Overview Basic containers vector list deque Indexed containers set map multiset multimap Adaptors queue priority_queues stacks

New Class Library Blessed by ANSI Efficient Memory Time Programmer effort No Inheritance No casting (Fewer) pointers Extensive use of template feature

A New Style of Output #include <algorithm> … ostream_iterator<string> out(cout); *out++ = "abc"; // write “abc” *out = "xyz"; // write “xyz”

A New Style of Input #include <algorithm> … istream_iterator<string> in(cin); cout << *in; // echo the first word cout << *in; // echo it again cout << *++in; // echo the next word cout << in->length(); /* display the length */

Rewriting the Fill Program istream_iterator<string> in(cin); ostream_iterator<string> out(cout); istream_iterator<string> end; int len=0; while(in != end){   *out++ = *in++;   if((len += in->length()) > 30){     len = 0;     *out++ = "\n";   }   else{      *out++ = " ";   } }

Modified Slide: Read in the Container vector<string> x(1000); //list<string> x;   //string x[1000]; istream_iterator<string> in(cin), end;   ostream_iterator<string> out(cout); copy(in, end, x.begin()); /*  This does the same thing { string word; while(cin >> word) x.push_back(word); } */

New Slide: Same as Previous Slide vector<string> x(1000); //list<string> x; //string x[1000]; copy( istream_iterator<string>(cin), istream_iterator<string>(), x.begin());

New Slide: Same Effect as Previous Slide //vector<string> x(1000); //list<string> x; string x[1000]; copy( istream_iterator<string>(cin), istream_iterator<string>(), x);

Write out the Container //vector<string> y(1000); list<string> y;   //string y[1000]; copy(y.begin(), y.end(), ostream_iterator<string>(cout, " ")); /*  This does the same thing {   for(list<string>::iterator ii = y.begin(); ii != y.end(); ii++)     cout << *ii << " " << endl; } */

Sort and Write the Vector sort(array.begin(), array.end()); copy(array.begin(), array.end(), ostream_iterator<string>(cout, "\n")); /* This does the same thing for(vector<string>::iterator ii = array.begin(); ii != array.end(); ii++) cout << *ii << endl; */ return 0; }

The Primary Types Interchangable Lists Deques C++ arrays (vectors) C arrays All define member functions insert push_back push_front pop_front pop_back

So what is a Deque? Double ended queue! In the standard library, a deque is Optimized differently Cross between array (contiguous) and List (one element per node) A linked list of arrays Deques Have multiple array elements per node Special allocation strategy What is the problem with inserting a new element at the beginning of an array?

The Deque CDT

Sets Sets have items An item can occur only once Examples of infinite sets All integers All reals Examples of finite sets in C++ Persons working for AT&T Satellites Departments at AT&T

Class Set Complete value semantics Declaration: set<string> persons, leaders; Operations swap upper_bound lower_bound count erase empty insert clear

The Spell Checker Example #include <fstream> #include <iostream> #include <set> #include <string> const int nWords = 63; string data[] = {"C", "Still,",…}; main(){ set<string> dict(data, data+nWords);  string word;   while(cin >> word){    if (dict.find(word) == dict.end())    cout << "Misspelled word: " << word << endl;   }   return 0; }

Laboratory Exercise: Employee Tables Work in part1\unit3\exercise\emptab Use class set to rewrite part1\unit1\solution\array2\emptab.cpp Strategy: Use 3 set variables: ito, sdp, mm

Starting Code for Exercise main(){   set<string> ito, mm, sdp;   // Prompt name and search table   string name;   while(cout << "Enter name: ", cin >> name)  {   } // while   return 0; } // main

An Alternate Approach Previous approach Efficient? Elegant? Improvements? How about a two column table? Can this be done with class set?

Coding the Alternate Approach Define the format single row of the table struct Emp { string name, dept; }; bool operator == (const Emp& a, const Emp& b){ return a.name == b.name; } bool operator > (const Emp& a, const Emp& b) { return a.name >  b.name; } main(){ Define the table   set<Emp> emptab; Define a single row   Emp emp;

Coding the Alternate Approach Populate the table emp.name = "Joe"; emp.dept = "MM"; emptab += emp; emp.name = "John"; emp.dept = "ITO"; emptab += emp;… Loop and prompt   while(cout << "Enter name: ", cin >> emp.name)          if(emptab.find(emp)!=emptab.end())                 cout << "dept = " << emp.dept;          else                 cout <<                   "Corporate Spy, Call Security!";   return 0; }

Clumsiness This approach works It is clumsy but efficient Is there a better way yet?

map Type Lookup table Key-value pairs Map keys to values Many names Associative array Map Dictionary Complete value semantics Operations called by class user Map key to values (subscript) Count key-value pairs Fetch the first, next, previous or last key

map Type map<string,int> m; m["hello"]++; m["world"]++; m["world"]++;

map Examples Declarations with templates #include <string> #include <map> using namespace std; map<string, int> m; map<int, string> mapis; map<float,string>mapfs; map<string,string>mapss; // same as below //map<string,string,less<string> > mapss;

Modified Slide: map Examples Subscripts string key = "hello"; m[key] = 3; // store 3 m[key]++; // update 4 m["world"] = m[key]; // fetch and store m[key] = m[key] + 2; // 6 Element counts int i = m.size(); // i = 2

Modified Slide: map Examples Keys (*m.begin()).first; // first key (*--(m.end())).first; // last key (*++(m.begin())).first; // second key Traversal and output  map<string,int,less<string> >::iterator i; for(i = m.begin(); i != m.end(); i++)   cout << i->first << "\t" << (*i).second << endl;

map Examples Assignment map<string,int> map2; map2 = m; Pass by value and return by value void save(map<string,int> m); map<string,int> restore(); ... save(map); ... map2 = restore();

Count Unique Words Input The suggestions that follow are meant to broaden your awareness of C programming issues that affect portability, and to serve as informal guidelines as you write programs in C language. These are not rules, but cautions, for there is no simple way to develop the skill of writing portable C programs. Still, if you remain aware of these issues and suggestions, you improve your chances to write C programs that are portable from one UNIX system environment to another, with little or no need to change the program. Output C: 4 Still,: 1 The: 1 These: 1 UNIX: 1 affect: 1 and: 2 another,: 1 ...

Count Unique Words main(){   typedef std::map<std::string,int, std::less<std::string> > map;   map m;   string word;   while (cin >> word)     m[word]++;   for (map::iterator ii = m.begin();    ii != m.end(); ii++)     cout << ii->first << ": " <<     ii->second << endl;   return 0; }

Laboratory Exercise Work in part1\unit3\ exercise\emptab2 Use class map to rewrite part1\unit1\ solution\array2\ emptab.cpp Strategy: Use one map for a single two column table

Starting Code main(){   // Prompt name and search table   string name;   while(cout << "Enter name: ", cin >> name)          if(                                  )          else cout << "Corporate Spy, Call Security!"; }

Class Exercise How can we have multi-column tables? A table of employees that tells us SSN, salary, department? A table of ingredients and suppliers? A table of products and customers? A table of ingredients?

vector Type Like C-Style array Bounds checking Only with member function at Does not work with [] Value semantics Subscripts Fetch Store Update

C++ Style Arrays Method 1 vector<string> name(1,10); name[j] = "hello"; Method 2 map<int,string> name; name[j] = "hello";

vector Examples Declaration #include <string> #include <vector> vector<string> array(1,20); Subscript string tmp; tmp = array[i]; array[i] = array[i+1] array[i+1] = tmp; Element count int size = array.size();

vector Examples Assignment vector<string> a2; a2 = array; Pass by value void save(vector<string> a); ... save(array); Return by value vector<string> restore(); array = restore();

Write out the Container vector<string> y(1000); copy(y.begin(), y.end(), ostream_iterator<string>(cout, " ")); /*  This does the same thing {   for(vector<string>::iterator ii = y.begin(); ii != y.end(); ii++)     cout << *ii << " " << endl; } */

Read, Sort and Write the Vector #include <algorithm> using namespace std; main(){   vector<string> array(1000);   {     istream_iterator<string> in(cin);     istream_iterator<string> end;     copy(in, end, array.begin());   }   sort(array.begin(), array.end());   copy(array.begin(), array.end(), ostream_iterator<string>(cout, "\n"));   return 0; }

A Shorter Version #include <fstream> #include <iostream> #include <string> #include <set> #include <algorithm> using namespace std; main(){   multiset<string> s;   copy(istream_iterator<string>(cin), istream_iterator<string>(), inserter(s, s.begin()));   copy(s.begin(), s.end(), ostream_iterator<string>(cout, "\n"));   return 0; }

Remove Duplicates #include <fstream> #include <iostream> #include <string> #include <set> #include <algorithm> using namespace std; main(){   set<string> s;   copy(istream_iterator<string>(cin), istream_iterator<string>(), inserter(s, s.begin()));   copy(s.begin(), s.end(), ostream_iterator<string>(cout, "\n"));   return 0; }

Class Exercise Suppose C++ style array is implemented with C-style array? Could the class provider add a member function to grow or shrink the array? What might be a problem with this? (See next slide)

What is the Problem?  vector<int> v(1);   v[0] = 22;   int* p = &v[0];   vector<int>::iterator it = v.begin();   cout << *p << endl;   cout << *it << endl;   v.push_back(32);   v.push_back(33);   v.push_back(34);   cout << *p << endl;   cout << *it << endl;   copy(v.begin(), v.end(),  ostream_iterator<int>(cout," "));

Summary Types and user-defined types The standard library Name spaces Class user programming with templates Basic containers & iterators list stacks, strings, vectors, maps & sets Special iterators for I/O Examples of reusing software components Calculator — stack type Text justification — string type Employee Security & Spell Checking — set type Count unique words — map type Sorting a list of words — map type

Appendix Another Useful Class

Problem: Binary Truncation How to store                                  ?

Solutions to Binary Truncation Solution #1: Store cents, not dollars! Simple Won’t help for interest calculations! Solution #2: Perform rounding before display Simple Works for trivial calculations Round-off will eventually get you Solution #3: Use Binary Coded Decimal (BCD) Difficult implementation Calculations are done in base 10 1/5 is no longer a repeating fraction

Picture Variables Picture variables implement BCD Special formatting for business applications Class Exercise: For what radix (base) is + - / * defined in C? How do we perform BCD arithmetic? Can we use + - / * in C for BCD arithmetic?

Picture Variables in Other Languages COBOL 77 PAY-CHECK-AMOUNT, PICTURE $***,*99.99. MOVE 1679.02 TO PAY-CHECK-AMOUNT. PL/I DECLARE PAY_CHECK_AMOUNT PIC ‘$***,*99.99’; PAY_CHECK_AMOUNT = 16769.02; C++ #include “Picture.h” Picture payCheckAmount(“$***,*99.99”); payCheckAmount = 1679.02; cout << payCheckAmount; Output $**1,679.02

Picture Type Similar features to PL/I and COBOL Full value semantics Operations Print (operator<<) Add, substract, multiply and divide Assign numeric values

Printing A Pay Check Write a program to print the following: hourly rate:       $62.65 hours worked:     040 tax rate:         0.33 gross pay:          $2,506.00 income tax:           $826.98 pay check amount: $**1,679.02

Printing a Pay Check #include <iostream.h> #include "Picture.h" main(){ Picture hourlyRate("$$99.99"); hourlyRate = 62.65; cout << "hourly rate:   " << hourlyRate << '\n'; Picture hoursWorked("999"); hoursWorked = 40; cout << "hours worked: " << hoursWorked << '\n'; Picture taxRate("9.99"); taxRate = .33; cout << "tax rate:     " << taxRate << '\n';

Printing a Pay Check (continued) Picture grossPay("$$$$,$99.99"); grossPay = hourlyRate * hoursWorked; cout << "gross pay:     " << grossPay << '\n'; Picture incomeTax("$$$$,$99.99"); incomeTax = grossPay * taxRate; cout << "income tax:  " << incomeTax << '\n'; Picture payCheckAmount("$***,*99.99"); payCheckAmount = grossPay - incomeTax; cout << "amount:" << payCheckAmount << '\n'; return 0; }

Appendix Additional Laboratory Exercise

Laboratory Exercise Work in part1\unit3\exercise\toc or part1\unit3\exercise\nt-toc. Write a file lister program. Fetch file names from command line. Copy files, line by line, to output. Paginate output. Generate table-of-contents at end. list each file name. list page number each file starts on. Additional features to add: Headers and footers with titles and page numbers. Left, right, top and bottom margins. Accomodation of long lines. (Wrap them).

Laboratory Exercise (Continued) Example of desired output: toc \labs\include\*.h \labs\include\NODE.H -----------------------------------------\labs\include\NODE.H ... -------------------------------------\labs\include\MAPTYP1T.H ... page 1 \labs\include\MAPTYP1T.H ... Table of Contents \labs\include\NODE.H                                        1 \labs\include\MAPTYP1T.H                                    1 \labs\include\MAP.H                                        63 \labs\include\LINKEDLI.H                                  129 ... page 1

Laboratory Exercise (Hints) Use map<string,int> to store toc (table of contents). Read entire lines with char buf[MAX]; while(cin.getline(buf, MAX)){ string line = buf; line = line.detab(); ... } Use constants defined in toc.h const nMARGIN = 8;  // left and right margins const nWIDTH = 80; // page width const nLPP = 66; // lines per page const nHEAD = 5; // top margin const nTRAIL = 5; // bottom margin const MAXLINE = 2048; // maximum length of line

Laboratory Exercise (Hints) Use standard I/O manipulators. setw(int)  // set field width setfill(char) // set fill character Use custom I/O manipulators (Templates only) cout<<left; cout << right;// left and right justify // output footer cout << footer(nPage, nLine, "Page "); // output header cout << header(nPage, nLine, "Header Text"); // output header and footer //   if at bottom of page cout << newLine(nPage, nLine, "Header Text"); cout << vspace(6); // out 6 blank lines cout << hspace(3); // output 3 blanks

Laboratory Exercise (Hints for non-Template Version) Substitutes for I/O manipulators. // Output footer footer(cout, nPage, nLine, "Page"); // Output header header(cout, filename); // Output ‘\n’ and header and footer //   if at bottom of page newLine(cout, nPage, nLine, filename); // Output six horizontal spaces hspace(cout, 6); // Output 3 vertical spaces vspace(cout, 3);