CPS 6, Ramm - Summer Semester I - 6/7/01 #15

Announce
- Lab #6 Today

8. Arrays, Data, & Random Access

Vector Vocabulary
- always start at 0; last always at N-1
Vector Creation and Use
Vector Definition Syntax
tvector<type> name; tvector<type> name(expression);
tvector<type> name(expression, value);

type is any with default (parameterless) constructor

Vector Initialization

Use Constructor

tvector<int> nums(4, -1);

tvector<string> words(12, "Hi");

Use Client Program

for(k = 0; k < 4; k++)
    nums[k] = -1;

for(k = 0; k < 12; k++)
    words[k] = "Hi";

Character Frequencies in Classical Cryptography

Crypoquotes in paper

Vector Parameters

 
            letters.cpp

char type

functions tolower(char), isalpha(char)

get(char) member function

fail() member function

A Draft Word in Context Program

 
            context.cpp

Redesigning a Word in Context Program
Redesign in Classroom

 
            context2.cpp

What if File is Too Large?

Advantage of Vector Class: Resize

 .resize(int size)

member function

Copying/Cost: Memory and Time

Double It!

 .capacity()

member function

context3.cpp

How to Solve Problem Without Vectors?

Trailing Variables

Limited Search

or Reread File

Translating Characters to Morse Code (char to string)

Translate Table


         morse.cpp

"CryptoQuotes" (char to char)


         transl.cpp

Size and Capacity: "The Partially Filled Array"

Classical: Programmer keeps explicit track of each

when passing vector argument, also pass size

tvector class: Class keeps explicit track of each
- requires use of special member functions

Using push_back

Start with empty vector (capacity = 0)

Use push_back to add elements

Class does the rest

Do not need to pass size a paramter!

A Simple Information Storage/Retrieval System

Concepts

Store lines from file in vector
Retrieve lines by matching substrings
Like UNIX grep program

getinfo.cpp

Improving the Storage/Retrieval System

Keeping track of Use: A Vector of Structs

getinfo2.cpp

WordList Class

List of Unique Words

Update with next word

Search for previous

Print Unique List

allword3.cpp

Binary Search

Telephone Book Analogy

Eliminate half each time

Requires Sorted Lists

list size	binary search	sequential search
1	1	1
10	4	10
1,000	11	1000
5,000	14	5000
100,000	18	100,000
1,000,000	21	1,000,000

binsearch

Keeping a Sorted List

addsorted