CPS 6, Ramm - Spring 2000 - 3/8/00 #21
Chap 8. Arrays, Data, & Random Access
- 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
- WordList Class
- List of Unique Words
- Update with next word
- Print Unique List
-
allword3.cpp
- Binary Search
- Telephone Book Analogy
- 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