. 19 Vectors and Advanced Arrays
. Previous -- Arrays
.See ./18.html
.Open Prepare
. 7.5 Passing Arrays to Functions
Tricky but necessary.
. 7.6 Case Study: Class GradeBook Using an Array to Store Grades
Study.
. 7.7 Searching Arrays with Linear Search
A very common algorithm -- study in detail.  Think how you might adapt it to your own programming projects.
. 7.8 Sorting Arrays with Insertion Sort
Remind me to demonstrate this in class with my pack of magician's cards.
. 7.11 Introduction to C++ Standard Library Class Template vector
Review vectors -- remember: they are more powerful but slower to use than arrays.
.Close Prepare
. Deliver a question
. Exercises
. Demo Insertion and other sorts
. Demo of Test First Development of a Class
The following class will be developed in the lab.

.Image Sample.png [UML class diagram of Sample]

This class is intended to store a sample data: a set of real numbers
and calculate as needed various statistics: min, max, mean, standard deviation
(sd).  Because the data and the functions are placed in a class a program can
declare and use many different Samples -- and, for example, calculate
correlations between them.

See
.See ./lab10/
for a starter class and test program.
.Open Questions and Answers
. Which companies use sorts
All people need there data sorted and so use sort programs.   This is why we
study them in Computer Science.  Example: A phone company lists its subscribers
in a phone book that is sorted.

. Why not use insertion sort for long arrays
Try it with a deck of cards and see:-)

. When to use Insertion sort
A rule of Thumb: No more than 10 items!

Because for more than 10 items there are faster ways to sort them.  Covered
in CS202 and CS330.

. Why is insertion sort simple but not efficient
Like most simple things -- it is not as good as some
clever algorithms -- especially when there is lots of data.  More in CS202.

. Please give more details on the STL vector template class
First check out
.See ./samples/stl.html#Vectors
then check out SGI's site
.See http://www.sgi.com/tech/stl/
then look in the standard
.See ../c++std/cd2/lib-containers.html
(tough going but complete).... and then hit the library!
. Why doesn't vector at return an rvalue
All lvalues are coerced to rvalues when an rvalue is needed.
. What is an lvalue and an rvalue
When a variable appears on the left of an assignment
.As_is 		left = right;
it is an lvalue -- a place where data can be put.  lvalues are places to store
data.  On the other side (right) the variable is used as supplying a value -- this
is an rvalue -- a place or expression that gives a value.  Lvalues are places
and rvlaues are things in those places.

. How come linear search is bad for large arrays
It becomes very slow with lots of data to search.  Remember finding the name of
the person with number 123-4567 in a normal phone book.  This requires a linear search
and will take hours if not days.  Finding "Victor Hugo" in a normal phone book
is much quicker because we don't use linear search.

.Image BigO.png [Clever algorithms work faster on big data]

. What is a template vector
It is a long name for a vector.

. What is a template
A template class or function is written to have some unknown types of data and
adjusts to the data you supply.  

vectors are template classes....  Hence "vector <....>"
. How often are vectors used in C++
A lot!
. The modifyArray function on page 356 has a parameter sizeOfArray -- does it change the size of the array

Nothing can change the ammount of space you give to an array when you declare it.
NOTHING!

In this function you can input any number as the size.  You can lie!  But this
may not be wise.

If the parameter has a value bigger than the real size then the function can
do just about anything to your program.... upto and including shutting down the computer,
by way of strange bugs and errors.

If the parameter is equal to size of the array then all should be well.

If the parameter is less than the real size the function will probably only use part of
the array.  And this may be what you wanted.

. How are arrays passed by reference
The formal parameter gets the address of the first item in the array (item [0]).
In the function the items are found by cacultaion, of course:
.As_is 		item[i]  
.As_is 		address of item + (i * sizeof item).
The function gets the size from the parameter type.

Thus it can get to any element in the original array.
. If an array is associated with a const parameter can it ever be changed
Not by the called function.  Other parts of the program can still change it.
. When to use const for local variable
When they are constants!  Good examples are \pi, Euler's `e`, Avogadro's number, 
Days in Week, Months in year, and so on.
. Are arrays the only things passed by reference by default
Yes.  In C++ objects are copied and elementary data are copied in
unless you use the "&" in the parameter specification.
. Can we have unsigned subscripts for vectors
Yes... but they will be converted to signed.
. What is in the final
.See ./mock2009.html
. Questions about the Big-O notation
Will be answered in 
.See ./cs202/
. How to use elements of an array as counters
With arrays you need a fixed number.  Suppose we have some events
that happen at different days.... and to count how many in each month....
.As_is 		const int MONTHS =12;
.As_is 		int counter[MONTHS]={};
.As_is 		//some kind of loop
.As_is 			//Calculate a month...
.As_is 			counter[ month ] ++;
.As_is 		//end the loop some how
Something like the above should work.
.Close



. Next -- Review Course Content
.See ./20.html