[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci Dept] / [R J Botting] / [CSci201] / 07
[Text Version] [Syllabus] [Schedule] [Glossary] [Labs] [Projects] [Resources] [Grading] [Contact] [Search ]
Notes: [01] [02] [03] [04] [05] [06] <07> [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
Podcasts: [01] [02] [03] [04] [05] [06] [07] [08]
Labs: [01] [02] [03] [04] [05] [06] [07] [09] [10]
Wed Jan 30 11:18:02 PST 2008

Contents


    Arrays and Vectors

      Reading -- Pages 58-68 of Skansholm + this web page

        Introduction and Podcast Link

        You can hear this introduction by downloading [ 07.mp3 ] and playing it.

        Welcome the the 7th set of readings for CS201 -- Pages 58-68 of Skansholm plus the notes on the web site. This introduces a pair of powerful tools for programmers. Nearly all C++ programs have at least one array or vector in them. So far each variable we have declared has space for precisely one number. If we declare an int variable it has just enough space to be a simple counter. If we declare a double then it can hold a single measurement. With an array of 9 ints we keep track of the number of computers in the 9 CSci laboratories in Jack Brown Hall. If we have an array of of 9 doubles we can store the floor area of the 9 rooms. Arrays like this are very good when the number of items does not change. If they do change then you want one of the more modern containers of data -- vectors, deques, lists, etc. A vector of doubles could store the salaries of the faculty in the computer science department because a vector can add a new item (at the end) when some one is hired. We can also shrink the salary vector when someone retires.

        Here is a summary of the reading:

        1. 2.7 Arrays
          1. Figure 2.1 An array
          2. Page 59 -- dangers of going outside the bounds of an array
          3. Page 60 -- Initialize the whole array at once
          4. Page 60 -- Can not simply copy arrays, use a for loop.
          5. Page 61 -- Example of an array in statistical programs
          6. Page 62-63 -- Example array in commercial programming
          7. Page 63-64 -- Linear search
          8. Page 64-65 -- Selection sort
        2. 2.8 Sequences -- vector and deque
          1. Please ignore references to deques and lists
          2. page 66 -- need to include <vector>
          3. Page 66-67 Using vectors
        3. Skip Section 2.8.2 [ My Notes on Vectors and Arrays ]


      2.7 Arrays

        Figure 2.1 An array

        Keep this picture in mind when working with arrays and vectors.

        Page 59 -- dangers of going outside the bounds of an array

        In C++ the computer and compiler assumes you know what you are doing. Large numbers of bugs are caused by people who didn't know what they are doing. Many virusses exploit this kind of error in MicroSoft code.

        Page 60 -- Initialize the whole array at once

         		type array_name [] = { item0, item1, item2, ... };
        But you can not use {...} in an expression or assignment.

        Page 60 -- Can not simply copy arrays -- use a for loop.

         		for( int i=0; i<size; i++)
         			array_name_2[i] = array_name_1[i];

        Page 61 -- Example of an array in statistical programs

        Notice the classic code for inputting, storing summing, etc. You may need it in a project....

        Page 62-63 -- Example array in commercial programming

        Page 63-64 -- Linear search

        Here [ 07search.cpp ] is a version of the code on page 63 placed in a working program. You have to supply the item to be searched for as the last item.

        Page 64-65 -- Selection sort

        Selection sort is one of a dozen different sorting algorithms that we study in Computer Science, starting in CSci202. Here is the code from the book [ 07selsort.cpp ] , we will study this in detail in class.

      2.8 Sequences -- vector and deque

        C++ provides a whole library of useful containers. Vectors are the ones that are used in CS201. The whole set is covered in CS202. CS330 goes "under the hood" and shows how they are implemented.

        Please ignore references to deques and lists

        You ain't Gonna Need Them in CS201.

        page 66 -- need to include <vector>

        Unlike arrays which are built into the language, if you want to have a vector then you must put this line in front of your program
         	#include <vector>

        Page 66-67 Using vectors

        Declaring, testing, growing, and shrinking vectors. Also see [ My Notes on Vectors and Arrays ]

      Skip Section 2.8.2

      Instead see [ My Notes on Vectors and Arrays ] below.

    My Notes on Vectors and Arrays

      This is a short introduction to the standard vectors available in C++. Vectors are a powerful yet simple data structure.

      Quick Reference on Arrays and Vectors

      Vectors are good when we have an unknown sequence of similar items to store and we want to access them by their sequence numbers. Arrays are best when we know the maximum possible number of items -- and we want a program to run faster.

      Vectors are held in a special library and can be used in a file that has

       		#include <vector>
      at its beginning.
      Declare vvector<type> v(initial_size);
      Copy v2 into v1v1 = v2;
      Get data from v v.empty(), v.size(), v.front(), v.back(), v[number], v1==v2
      Change ith item in v v[i]=new_value;
      Add/Remove items v.push_back(item), v.pop_back()

      Arrays are part of the C language and so part of C++. You do not "#include" anything because the compilers knows about them already. There are no special operations/function that work on arrays.
      Declare a to have ntype a[n];
      Copy a1 into a2Write a for loop!
      Get data from a a[number]
      Change ith item in a a[i]=new_value;
      Add/Remove items Impossible.

      Key Facts about Vectors

      You need to remember the following facts about vectors:
      1. A vector is an object that contains a sequence of other objects inside it.
      2. The objects inside must all take up the same amount of storage.
      3. They are numbered starting with 0.
        If the whole vector is called v then the items in it are written v[0], v[1], v[2], ...
        The last item is v[v.size()-1] NOT v[v.size()].
      4. New items can be "pushed" onto the end of the vector.
      5. The last item can be "popped" off of a vector.
      6. Vectors can therefore change size.
      7. We can find out the current size of a vector: v.size()
      8. Vectors can be empty. If so v.empty() is true.
      9. If a vector is empty then v[i] and v.pop.... crash.
      10. Vectors are empty, by default, when created.

      Details

      Suppose that T is any type or class - say int, float, double, or the name of a class, then
       	vector<T> v;
      declares a new and empty vector called v. Given object v declared like the above you can do the following things with it:

      Example

      Suppose that we want to input an unknown number of numbers and then print them out forwards and then backwards, using a vector. We will push ints onto the back of a vector called v. We will then print each item in v in turn. Finally we will print the vector backwards.
       	#include <iostream>
       	#include <vector>
       	using namespace std;
      
      
       	int main()
       	{
       		vector<int> v;
       		int number;
       	    // 1. Input v;
       		cout <<"Input some numbers and then end the input\n";
       		while(cin>>number){
       			v.push_back(number);
       		}//while(more)
      
      
       	    // 2. Print v
       		for(int i=0; i<v.size(); ++i)
       			cout << v[i] << " ";
      
      
       		cout << endl;
       		cout << "----------------"<<endl;
      
      
       	    // 3. Print backwards
       		for(int i=v.size()-1; i>=0; --i)
       			cout << v[i] << " ";
      
      
       		cout << endl;
      
      
       	}//main

      More About Arrays

      A vector is a simple dynamic sequential "container". The oldest example of a container in C++ is the array. It is a static sequential container. In C you had arrays and you would write code like this:
       	const int MAX = 10;
       	float a[MAX];
       	...
       	cout << "Input "<< MAX << "numbers."
       	for(int i=0; i<MAX; ++i)
       		cin>> a[i];
       	...
       	for(int i=0; i<MAX; ++i)
       		cout << a[i] << " ";
       	...
       	for(int i=MAX-1; i>=0; --i)
       		cout << a[i];
       	...
      Arrays are like vectors except that:
      1. They are faster than vectors.
      2. They have a fixed size specified in the declaration.
      3. You can not add or delete items from an array.
      4. There is no single statement that copies them.
      5. The syntax is simpler.
      6. Their is not library to include arrays.
      7. The absolutely no safety belt: if an index has wrong value, you crash.

      Hint -- Trace or dry run code

      It helps to draw diagrams of vectors and arrays and work out by hand, on these diagrams what an algorithm, or your program is doing. Pretending to be a computer can teach you a lot about a complex computation.

      Hint -- Add output when you can not figure out what a program does

      If you have a program that does something that does not match what you expect it pays to add simple "debugging" statements that printout key data.

      Glossary

    1. array::=A fixed length sequential container of data with random access to each item. Contrast: vector.
    2. container::=A data structure which contains a number of data items that can gain and lose items as the program runs. Examples include vectors, lists, stacks, ...

    3. increment::operation=moving an iterator/pointer/index on to the next iterator/pointer/index value commonly symbolized by ++ in C-like languages.

    4. random_access::=being able to do things to items in a container in an unpredictable order typically by using an integer as an index or subscript.

    5. vector::container=a vector is a sequential container that is optimized to allow efficient random_access of items by using an index. Vectors are useful whenever data must be stored in one order accessed in a different one. A vector is a dynamic array - an array that can grow when needed.

      Errors with vectors and arrays

        You must always #include <vector> if you use the word vector.

        You must be sure that all indices or subscripts of a vector v stay between 0 and v.size()-1 inclusive.

        Trying to change the size of an array does not work.

        You must be sure that all indices or subscripts of a array a stay between 0 and MAXIMUM-1 inclusive if the array is declare with size MAXIMUM.

        If a program compiles, loads, crashes, and there is a subscript operator ([...]) then check to see if the subscripted item has been put into the container before the subscripted element is accessed. A very common error is to declare a vector with no length and to use [...] as if it created new elements. It doesn't. Use 'push_back(..)' to add new elements to a vector.

        If you are unable to show that a subscript is in range then use a condition like the following to guard thing[i] from errors:

         		0<= i && i < thing.size()

        If a program compiles, loads and crashes and it has a pop_back, function than make sure that there is an item to be "popped"! In code you can use the empty function to guard statements that contain "pop" from blowing up.

        You can have vectors of vectors:

         		vector < vector <int> > matrix;
        but you must put at least one space between the two ">" symbols. The following is wrong:
         		vector < vector <int>> matrix;

        2 and 3 dimensional arrays

        C++ doesn't have 2 or 3 dimensional arrays -- a[r,c], b[i,j,k] -- even tho' this code compiles! You have to declare and use arrays or arrays to get 2 or 3 dimensions:
         		double matrix[ROW][COLUMN];
         	// print matrix
         	for(int row=0; row<ROW; row++)
         	{
         		for(int column=0; column<COLUMN; column++)
         			cout << matrix[row][column] << " ";
         		cout << endl;
         	}

      . . . . . . . . . ( end of section Errors) <<Contents | End>>

    Questions

      What is tracing and how is it used

      Tracing is a process of seeing what the computer does when a program runs. It shows every value if every variable at each step of a program. The best way to do this by hand is in a table with variables as the heading.

      Tracing is used as the first step to understanding a program.

      It is also a useful training technique and diagnostic test of how well you understand something.

      We traced a piece of code like this in class:

       	int t = 0;
       	for (int i=0; i < 5; i++)
       	{
       		t = t + i;
       		cout << t << endl;
       	}
      Statement\Variablesticout
      t=00??
      i=000?
      i<5
      t=t+i00?
      cout000
      i++01
      i<5
      t=...11
      cout...111
      i++12
      i<5
      t...32
      cout323
      ...
      cout10410
      i++105
      i>=5

      What is a for statement for

      To count and to scan across containers.

      What is another way to work with loops

      I only know of the ways I have taught you.

      Is there a way to do both for and while statements without getting confused

      Practice.

      What does ! mean

      not

      if statements and iomanip

      You don't need any libraries to use if.

      Difference between float and double

      Both store real numbers. Float uses less space and may run faster. Doubles have more significant figures.

      How are arrays and vectors helpful

      Doing without them is painful in the extreme -- believe me!

      Why can't we use vectors instead of arrays

      Their are only two reasons for using arrays: (1) they are efficient (faster, less wasted space) and (2) you have to fit with software that uses an array.

      Can vectors be used in place of arrays

      Yes!

      In this class -- use vectors whenever you have the option.

      When do I use vectors

      Always!

      When do I use deques

      In CS202 and/or CS330.

      What functions are part of the vector library

      Check out the full documentation in

      How to stop the user inputting bad data -- letter in a number

      Todays lab shows the cin.fail() condition in action. It may help.

      Can you explain vectors more

      Check out the notes above. Or come and ask questions in my office hours.

      What are vectors actually used for

      Storing a collection of data items in memory and to allow us to reorganize the data.

      What kind of program uses arrays vs vectors

      Old programs used arrays -- no choice. Modern programs tend to use vectors. Exception to speed up code.

      How does the size of an array relate to the last subscript

      If the last subscript is 5 then the size will be 6 elements.

      Can you give a clear definition of an array

      A fixed number of items of the same type numbered from 0 upward.

      What happens if we put a string into an array of ints

      C++ will convert the string into an address and store that!

      What functions are part of the vector library

      Check out the documentation in [ ../samples/stl.html#Vectors ] [ ../c++std/cd2/lib-containers.html ] (from the draft standard...)

    Quiz 3

    Lab 04

    Project 2

    Next

    [ 08.html ] on errors.

Abreviations

  • Gnu::="Gnu's Not Unix", a long running open source project that supplies a very popular C++ compiler.
  • KDE::="Kommon Desktop Environment".
  • TBA::="To Be Announced", something I should do.
  • TBD::="To Be Done", something you have to do.
  • UML::="Unified Modeling Language", [ uml.html ] (beginner's introduction to the UML).

    End