[Skip Navigation] [CSUSB] / [CNS] / [CSE] / [R J Botting] / [CSci202] / FAQ
[Text Version] [Syllabus] [Schedule] [Glossary] [Resources] [Grading] [Contact] [Question] [Search ]
Notes: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
Labs: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10]
Thu Jun 16 15:27:13 PDT 2011

Contents


    Frequently Asked Questions

      Should we use 'using namespace std'

    1. Yes. The alternate is to put "std::" in front of anything in the #include <libraries>.

      When should I use for and while loops

      Use while for simple iterations that repeat until some condition is false.

      Use for when counting or taking each item in a vector, array, string, etc. in turn.

      Notice that

       		for(A; B; C;) S
      does the same thing as
       		{ A;
       		  while(B)
       		  {
       			S;
       			C;
       		  }
       		}

      As a rule --
      (KISS): Keep It Simple ...

      What does break do

      The break statement in C/C++ terminates a loop. It also terminates a case in switch (see later)

      Is there a 1 or 2 page handout on the 'vi' editor

      Yes. See [ Vi in resources ]

      Are arrays important

      You need to understand them because they occur in most older programs and save storage and run time compared to vectors and strings. When we ask for extra memory we often use an array to get the data. Similarly when we read data off a disk or tape we get a fixed amount of data in a fixed layout and an array is best way to go.

      Use an array only when you know, for an absolute fact, how many items you will need or (for experts) when you can calculate the absolute maximum number of items. Otherwise use vectors or dequeues.

      They will be in the labs. I'll try to keep them out of the quizzes and final. They may be part of some projects. They have to turn up in several lectures/discussions.

      In lab02 I will try to convince you that arrays can be dangerous. We will do more with arrays in class as well.... in particular we will wrap one up in a class so it can be used safely.

      Distinguish deques vectors and arrays

      An array is a fixed number of numbered items. You can only declare it with a constant size. You can not put in or remove items from it.

      A vector is like an array but it's size can change. It lets you push new items on to it at one end, and also remove (pop) them from the same end.

      A deque Is like a vector except you can push and pop at both ends.

      Here is an application of a deque -- simulating the line in the Arrowhead Post Office in North San Bernardino. People come in and join the line at one end and leave it at the other... but sometime somebody comes in joins the end (push_back) and, before any one else comes in, they give up and leave (pop_back).

      Note: There are also stacks and queues. A queue you 'push' at one end and 'pop' at the other. A stack you 'push' and 'pop' at the same end. More later on [ stl.html ] when we cover the Standard Template Library.

      What is the difference between = and ==

       		v=e		//v is a variable, and e an expression
      Evaluates e, and takes the value and stuffs it into v.

       		e1==e1		//e1 and e2 expressions
      Evaluates BOTH e1 and e2, and compares them. If they are equal it return true otherwise false.

      Why overload functions?

      An overload function has one name but operates on different data types:
       		int twice(int i) { return i+i;}
       		double twice(double i) { return 2.0*i;}
       		string twice(string i) { return i+i;}
      But they all do similar things.

      The compiler picks the right one, so it is a waste of time giving them different names.

      How to trace a complex algorithm or program

      Find a large sheet of paper or an erasable board. Divide it into columns: one for each piece of data. Keep one finger on the code/algorithm to make where you have got to. Write new values in the right column. BE CAREFUL.
       		double s=0.0;
       		for(int i=1; i<5; i++)
       			s=s+i;

      Table
      Variablessi
      Commanddoubleint
      double s=0.0;0
      i=101
      i<5?
      s=s+i;11
      i++02
      i<5?
      s=s+i;32
      i++33
      I<5?
      s=s+i;63
      i++64
      i<5?
      s=s+i;104
      i++105
      i<5? FALSE

      (Close Table)

      How do you work out what a program does?

      Step by step, very carefully, attending to every detail...

      Avoiding guessing until you've traced it, step by step,...

      What is a recursive function?

      A recursive function is defined by a set of statements that include the possibility of calling the function again on a simpler or smaller set of data.

      You can learn a lot about it from working out what a simple (useless) program does: [ 02rec.cpp ] , for example.

      If you haven't figured it out yet, try this link [ lookup.php?search=recursive ]

      Why does the program that translate American and British dates need an array of 9 chars?

      There are 6 digits (MMDDYY) + 2 slashes(//) + one null character ('\0') used to terminate the text strings. You may be able to do it with out the two slashes and so need only 7 characters, however. I'm not sure if this might end up being more confusing!

      When should use a sentinel like -1 and when a CTRL/D to terminate input.

      Use sentinels when there is more data to be sent after the sentinel.

      Use a sentinel when normal humans provide the input.

      Use CTRL/D or CTRL/Z when the data comes from a file, another program, or a three star computer geek.

      When to use ints and when to use doubles.

      Is the data counting or indexing something? Is it always a whole number? Then use int.

      Is the data a measurement? Is it approximate? Can it have fractions? Then use double.

      Is if(not(cin>>a)) new?

      No. It (or something like it) goes back to the very first book on C in the late 1970's. Neat hacks like this tend to survive forever.

      Will we be programming much graphics in the class.

      No. Unless you want to! We will use simple graphic tools like Dia to draw UML diagrams.

      Will we be doing exceptions?

      Yes in a later class..... see the schedule

      Where do 'break' statement go?

      In the middle of a loop, or at the end of a 'case' in a 'switch'(later).

      Difference between while and do while

      The while loop
       		while(C){B}
      does this
       			C; B; C; B; ...; B; !C

      The do-while loop

       		do{B}while(C)
      does this
       			B; C; B; ...; B; !C

      What are the difference between an array and a class?


      Table
      ArrayClass
      is an objectis a data type
      has numbered itemshas objects with named members
      is old fashionedis object oriented

      (Close Table)

      What is a FAQ

    2. FAQ::="Frequently Asked Questions", see [ http://www.faqs.org/faqs/ ] for more FAQ.

      Will we input numbers in Two's complement

      No. We will input and output data in decimal -- our computers all use (internally) two's complement and C/C++ translates it for us.

      (exception -- there may be an problem in the book that needs binary input/output).

      Waring: lots of binary conversions needed in hardware classes.

      What are pointers for

      They used in C and C++ to remember where data is stored.

      They are used to communicated addresses to functions in parameters so that the function's code can aces and change the outside data.

      They are used simply because a pointer takes up 4 bytes and can refer to an array or object with 10,000 bytes of data. It is much quicker to pass the 4 bytes than copy the 10Kb!

      Pointers to char are used to implement <string>.

      The address of an array is a pointer and so pointers are used to share arrays of data with functions.

      Pointers are used to remember where data is, when we create data on the heap -- because we didn't know until the program ran how much data to store.

      Pointers are used to link objects together -- one object knows where to find another object because it stores the address of the other object.

      C and C++ solve lots of technical problems by using pointers.

      What is the asterisk used for with a pointer.

      If p is a pointer then *p is the pointee -- the thing it points at.

      The asterisk is used in declaring pointers.

      Can you explain pointers?

      I can try but they are subtle.

      First all pointers are declared like this:

       		T * v ....;
      where v is a variable and T a type (or class name).

      An int is stored in a location and has an address. It has a value that is an int. A pointer to an int (int*) is stored in a location, and has an address. However, the address contains another address. This address contains an int.:

       		int i = 5;
       		int* cp = &i;//the address of i
       		//Now *cp is 5.

      When to use pointers

    3. When we don't know the size of some data until the program is running. Then we are forced to grab data off the head using the new operator and this returns the address of the storage we have been given.
    4. When we have a big amount of data in an array, vector, string, or other object and want to avoid copying it.
    5. When we need to reorganize data many times. Instead of putting it in a vector and moving it we include pointers to indicate what follows what. We reorganize by changing pointer values.
    6. When we want behavior that varies depending on the object being pointed at (see polymorphism later).

      How do references and pointers differ

      A pointer is declared like this
       		T *p...
      but a reference like this
       		T&r...
      Both name addresses but
      Table
      PropertyPointerReference
      declared byT*p...T&v...
      address isp-
      value is*pr
      points atchangesfixed
      ageoldnew .Raw safe? NO YES

      (Close Table)

      Difference between (*pv).push_back(1) and pv->push_back(1)

      None.

      Why should I care about sizeof

      1. Curiosity.
      2. Estimating the cost (RAM, Time) of your program.
      3. Two find out how much data needs to be copied, stored, input, or output using raw data.
      4. Given a void* that refers to an object you can use sizeof to compute how many bytes to access, copy, store, or return.
      5. To computer the size of array a use
         		sizeof(a)/sizeof(a[0])

        Explain void and void*

        The word void got into C to indicate that a function did not return a value:
         		void name(...)...
        or to state that it must not have arguments/parameters:
         		....name(void)...

        Then people used void* to mean: a pointer at an object of unknown type.

        Have pointers changed from C to C++?

        No. We just don't need them as much.

        Why does the code for strcpy do anything?

         		while( *(p++) = *(q++) );
        You might guess that this is a test for equality. But beware such naive mistakes. The equals sign in C/C++/Java is a command to copy the data even inside a condition like
         		while( .... )
        The
         		*(p1) = *(q1)
        copies an item from one place to another.

        Next trick the pointers are move on to the next place (p++) and (q++) after the assignment.

        So what is tested? When an assignment finishes it leaves a copy of the value behind that can be tested! In this case the character moved. When a null character ('\0') is moved the loops stops.

        Next trick the pointers are move on to the next place (p++) and (q++) after the assignment.

        So what is tested? When an assignment finishes it leaves a copy of the value behind that can be tested! In this case the character moved. When a null character ('\0') is moved the loops stops.

        Is the basic use of typedef to simplify complex declarations

        This is one use. Another use is to make a program easier to understand by using a meaningful name for some concept that the data type encodes.

        What are pairs

        These are a useful and simple tool in the <utility> library. Each pair p has two parts: p.first and p.second. They can be of any type. The can be of the same or a different types. There is a special function that constructs a pair for us.

        They are used in special containers to connect a key (a name say) with some data (the person's phone number).


      What is an object

      An object is something that knows some data and can do things with this data. It is a mixture of "know how" and "know what" -- a little piece of intelligence.

      Example: my watch.

      In C++ the operations that an object can do come from it's class.

      Example: My watch is a Digital Watch. A Digital Watch is a special kind of Watch.

      What does Object-Oriented mean?

      An object-oriented program is designed so that it reflects the world with which it is concerned. The real world is (mainly) made of objects that respond in more or less predictable ways to events. Real world objects belong to classes that describe them. The object "dick", for example, is an instance or object of class "People". An object oriented program has similar objects an classes. The behaviors inside the computer simulate the real world consequences of events.

      In the real world there are three relationships:
      Table
      RelationMeansExampleUML
      ISAis a special kind ofMale is a PersonMale---|>Person
      HAS Ahas aA Person has two LegsPerson <>-->Legs
      KNOWScan accessA Bank knows its CustomersBank--->Customer

      (Close Table)
      Object oriented program can reflect these types of relationships.

      What are the benefits of OO programming

      First OO programs should fit the problem domain well. Thus you can start to solve problems by Modeling the problem as objects. Second: the solution is easier to understand. Third, small changes in the problem map in an obvious way to changes in the code. Fourth, you can use even a complicated class without having to master all the hidden internal details. Finally, big changes can often be done by adding a new class.... and not even recompiling the old code.

      It also impresses people in job interviews.

      When is OO a waste of time?

      Only when the problem is small and simple: for example a routine to evaluate a square root is best done by the old fashioned structured methods.

      How will we use objects?

      From now on think of ALL data as objects.

      Learn to start solving a problem by listing the classes of object and how they are related -- in the real world.

      Allocate operations to the classes in the problem so that they do useful work.

      When to use inheritance?

      Use inheritance/ generalization when one class of object "is a special kind of" another kind: Car is a special kind of vehicle, for example.

      How does an operation act on an object?

      Suppose I have a Cat called "Stranger", what happens when I stroke it?
       		Cat stranger;
       		...
       		cout << stranger.stroke();
      Answer: output "purr".

      The compiler looks at the type of object stranger is and finds out that stranger is a Cat. It, therefore replaces stranger.stroke(); by a call to a function stroke in class Cat -- with the variable this pointing at stranger. The operations inside this function stroke all refer to the data in the object stranger. As a rule you find the data in the object and the function in the class. So all objects share the "member" functions.

      When will use the UML?

      Throughout this class, and also in CSCI320, CSCI330, CSCI350,......CSCI455,.... and your job.

      What are generic program units in C++?

      The are called templates.

      Examples of dividing programs into files

      I have some notes [ Complex Projects in resources ] on this topic. We will return to this topic in later classes and in lab04.

      What are the {..} for after a function in a class

      These a complete "inline" function definitions. They include the implementation of the function as part of its declaration inside the class. For example
           int read_min() { return m; }
      could be rewritten as
           int read_min();
      as long as we later, outside of class Clock wrote
           inline int Clock::read_min() { return m; }

      What are inline functions

      These are functions that are copied by the compiler and inserted in your code where ever they are called. They are executed instantly because the computer doesn't have to jump to the body and back again. However, they use up space.

      Inline functions should be small and simple -- one line max. It is normal to define [ Getters and Setters ] (below) as inline functions.

      Getters and Setters

      A Getter function is one that gets the value of a private variable. Nearly all OO programmers use a name like "getX" for variable x:
           int getM() const { return m; }
      The const tells the C++ compiler that we won't be changing any variables in the function.

      Similarly a Setter is a function that sets the value of a private variable ... use these only when needed and safe. If we needed a clock where the minutes could be set to a value we might write:

           void setM(int m0) { assert(0<=m and m<=60); m=m0; }

      Can you return a vector from a function

      Yes. The function definition of function f that return a vector of doubles would be like this
           vector<double> f(data);
      and its implementation for class C might be like this
           vector<double> C::f(data) {vector <double> result; ...... return result; }
      You could call it like this
           myVector= myC.f(myData);

      However -- returning large amount of data (a vector can have a million items) slows down programs and should be avoided if possible. This is a classic case for using pass by reference:

           void f(data, vector<double> & result);
      with implementation like this
           void C::f(data, vector<double> & result) { ...... return result; }
      You could call it like this
           myC.f(myData, myVector);

      Why not make everything public

      This is what we did in the 1960's. It leads to bugs when you misuse the parts of objects in incorrect ways.

      It is rather like owning a clockwork watch with no case. It breaks down because of stuff getting into it.

      As a rule: data should be private and most functions are public. Make a function private if there is a way for it to be misused.

      What is a constructor

      A function in a class that puts the initial data into a newly created object. The name (in C++ and Java) is the same as the name of the class.

      How do I call constructors

      Constructors are called automatically when you declare an object:
           Class object(data);
      or get a new object
           Class * pointer = new Class(data);

      If I have a function or constructor with a char * can I give it a char[10]

      Yes -- like this
           blah example(char * s)....
           char a[10] = "hello";
           .... example( a)...

      What happens to data that I deallocate

      The computer keeps a list of unused and deallocated RAM and recycles it when you need it.

      What are friend functions

      A friend has access to the private data and functions of a class.

      A friend function must not have an object when it is called.

      The commonest friend functions are those that input and output objects.

      More in the next [ 06.html ] class.

      When and Why use Inline fucntions

      Inline code is easier to write and runs faster..... but it leads to bigger compiled programs.

      Rule: short functions are best inline. Long ones should not be inline.

      Unlike many books and some instructors I encourage you to include small function bodies in your "header files" and class declarations. This is more a practitioner's approach than a purist's guide line. A small function/constructor/destructor is no more than one line long:

       		It get_it() const{return it;}
       		void set_it(It is) { it=is;}
      (The above are typical of the many boring short function we write for some classes).

      When to use initialization lists vs code in a constructor body

      First you may not assign to const and attributes/data members can not be initialized in their declaration. The items initialized in the list are done before the object fully exists and its constant fields/attributes are locked into their final form.

      As a rule: use initialization lists whenever the arguments to a constructor provides values for data members/fields/attributes.

      What is there a semicolon at the end of a class definition?

      It terminates a list of declared objects! C++ allows you the option of defining a class and declaring an object of that type in one blow:
       		class Pair{ public: int first, second;} x,y;
       		x.first=1; y.first=2; x.second=y.first; y.first=x.first++;

      Why didn't C++ add a sophisticated way to do ifndef....

      I don't know... Possibly the standard writers where lazy.

      Constructors

      A constructor prepares a new object for use. In C++ it must have the same name as the class of object it creates. Most classes need at least one called the "default constructor".

      Because all constructors in a class have the same name, the identifier is overloaded. They must have different kinds of argument.

      If one actually wants to stop others from constructing new objects, then you merely define constructors as private functions. This is sometimes useful.

      The Counter class has a simple example, above. There will be more in other classes.

      Why use classes when we can write functions without classes?

      The functions in a class are good when we want to do things to some data. Functions outside classes are good for truly mathematical functions that take some input data and produce some new data. For example, sqrt takes in a double and produces a double. When we want to add something to an existing object or to remove something from it then a function in a class is better.

      Classes make programs that are clearer and easier to modify: many small independent pieces.

      Do we have to have a destructor if we don't allocate memory?

      Even if a class doesn't allocate heap storage, one of the classes that are derived from it may do so. It is wise to always include a destructor.... more later.

      Private vs Public parts

      The private attributes and operations are inside an invisible case so that they can not be used by commands outside the class. Imagine them as the works of a watch. The public parts are like the knobs and buttons and dials on the outside of a watch or clock.

      How does & work in function headers

      It is placed before the name of a parameter to set up call by reference. Without it the actual parameter is copied into the function as the initial value of the parameter -- and never comes out again!

      Call by reference means that the address of the variable in the call is passed to the function and all actions done to the parameter actually are done to the object. This is mainly used to allow data to flow in and out of the function through a parameter.

      Notice it is faster to use call be reference (&) with objects -- the object will have more bytes in it than an address. Copying bytes takes time.

      Also -- we used to get the same effect by using '*' and '&' but this needs a great deal of knowledge and care to work without bugs.

      When to use friends

      Any class can declare friend classes and friend functions.

      Use them as little as you can. They expose the object to abuse by the friends.

      The input and output functions (operator<< and operator>>) are the main functions that you MUST define as friends in a class in the course.

      Can you point to a data member in an object

      If the data is public you can. But it is wiser not too.

      What is * this

      When you apply a function to an object:
       		object.example(data)
      then, invisibly, the program does this
       		this = & object;
      before the function starts to execute. Thus the function knows where the object is.... and can use the information in several ways.

      A common way is to tell another object about 'this' object:

       			user_interface.addButtonListener(this);
      which means that when the user clicks a button 'this' will be called with a description of the event.

      There are other uses for this to be covered later. Most of these use

       		*this
      to refer to the current object -- say to send a message to itself!

      Can you have many classes in one program or file

      Yes. AN lots of functions can be used in one program.

      Examples of static data members

      First -- static members can change. A static variable can change its value at any time. The word "static" in programming is overloaded and abused. Variables that don't vary are said to be "const".

      Static data belongs to its class, not to the individual objects. It is shared by all the objects. Its value doesn't change when you change objects.

      Use it when the data is about the whole class not about one instance/object of the class.

      The Wikipedia [ Static_variable#For_class_variables ] has a couple of examples -- one in C# and a simpler one in C++ They define a class of Requests. Each Request is for a particular URL (place on the web), but the class, itself maintains a count of created Requests. This would be used to keep track of how many outstanding requests for web pages have been made, and whether there is a problem or not.

      Other examples is a class recording the enrollment in a section of a course. The size of the enrollment is a shard "static" number, each enrollment is for a specific student who is enrolled in a particular section.

      In fact, most academic examples of static class members are of counters!

      What is a binary operator

      A binary operator is something like "+" and "/" which is written between two operands:
       		1 + 2

      How to create random letters

       		int(rand()*26)+'a'

      When does const really matter

      when it stops a program changing my wages.

      Seriously: const protects data for abuse -- use it to control bugs.

      What are polymorphic classes?

      Classes are not polymorphic in C++, it is the inheritance of virtual functions that is polymorphic.

      Explain public vs private vs protected

      A member in a C++ class can be accessed by only other members in the class (private), or by the class and those derived from it (protected), or from any where in the program (public). The first is safest. The last is most convenient. Don't forget that most software is fragile because programmers took the convenient solution.

      What is the difference between protected and private?

      A protected member is private to all classes except those that are derived from it. For example the function bad() in [ 07ex3.cpp ]
    7. tries to access Alpha::a inside Beta.... and can not do this until the 'private' in Alpha becomes 'protected'.

      What is a virtual function

      It is a member function declared with the keyword virtual.

      It effects how this expression or statement is executed

       		p->f(...)
      when p is declared
       		B * p;
      but p points at an object thta is in derived class clled D (say).

      If f is not virtual then the compiler chooses B's version of f. If f is virtual, it delays the decision until the program is running. The program calculates the D version of f.

      When should a function be virtual

      When it is a member function of a class that may be a base class.

      Why make a function virtual

      If you do then your pointers and references will work like the objects they point at, rather than the class they appear to point at.

      The classic structure has a class

       		class Derived : public Base {....};
      and the program has a pointer to the Base:
       		Base * pb;
      which is then attached to a Derived object:
       			pb = new Derived (....);
      Now if 'v()' is a virtual function
       			pb->v();
    8. executes "Derived::v()".

      But if "f()" is not virtual then the command executes "Base::f()".

      As a rule we nearly always need pointer to work like the things they point at. (Think demo with magic wand in class). SO virtual gives fewer surprises.

      In my opinion you should make all functions virtual (except in toy programs). My evidence -- Java.

      Notice the above example of the Aim High pattern of declaring pointers to the most general class.... even if their values are the addresses of low-level special objects.

      If a function is virtual in a base class must it be declared as virtual in a derived class

      No.

      How does a dynamic cast differ from a virtual function

      A virtual function automatically and safely selects a lower level (derived) version of a function in a hierarchy to match the object pointed at.

      A dynamic cast makes the program treat a pointer as if it pointed at the lower level objects. Simple example is casting a pointer from Animal to Cat.

      It can fail and produce a NULL pointer if this makes no sense -- for example casting a pointer to Animal to being a pointer to Table.

      What is the difference between static and dynamic binding

      Binding attaches meaning to identifiers.... if done before the program starts to run, and never changed, then we say the binding is "static". Otherwise we say it is "dynamic".

      For example the value of a variable has dynamic binding. A constant has a static bound value. The length of an array is statically bound. Data members in a class are statically bound. And the type of a variable is bound by the compiler -- statically.

      Virtual functions are bound by the running program.

      As a rule dynamic binding is slower, more powerful, and more popular.

      How can you declare a nested class inside another

      Very easily in C++. Indeed we will have a classic example where we define a nested class and make it private as a helper to a main class:
       class List{
       	private:
       		class Node { public: int data; Node * next };
       	...
       };//end List
      Outside (if it was public) it would be called "List::Node".

      By the way -- Java 5.0 does have nested classes!

      What are static members

      A static member belongs to a class, not to any of the objects in the class. They all share the static member.

      By the way -- the word "static" is abused in C++.

      A classic example is keeping a count of all the objects that are constructed. The static data member

       		static int count;
      is declared and each constructor includes "count++" and each destructor "count --". After the class declare
       		int Class::count = 0;
      and the class will know how many instances have been created. Mor -- every object in the class has acess to count and can use it as if it was their own data.

      I had another variation when I wanted to be sure that every object had a unique identifier. I used a static int to keep track of the last identifier I had used....

      Static functions can be useful when we don't know what object to work with, or when an object has to be constructed. In fact every constructor in a class is static already. But I had a couple an example recently -- what object should handle a Student login? Problem -- I can't give this responsibility to a Student until I find the Student concerned. And I don't want to create a new kind of object solely to find STudents for me -- surely this belongs as part of the Student class! So I decided to make the class as a whole search the students for the correct student Id.:

       	static Student * find ( string name );
      So I could have code like this:
       		string name, passwd;
       		cout << ....
       		cin >> name >> passwd;
       		Student * student = find(name);
       		if( !student) error("no such student");
       		else {
       			.... * student ...
       		}
      By the way ... finding the Student with a given name is a classic problem that has several known algorithms and data structures that are part of Computer Science. .What arrows are used in the UML The ones used betweeen classes are here [ links.png ] and there are many other in other kinds of diagrams.

      I must prepare a cheatsheet.

      What about artifacts

      Just the name for anything created when developing software.

      Use a diagram when it gets complicated -- 10 or more of them.

      How do algorithms fit into the UML

      They describe how an operation soves a complex problem. A step towards coding the body of functions.

      What is an Algorithm

      A precisely defined process for solving a problem -- typically as a set of terminating steps.

      Typically an algorithm is used to design the code inside a function.

      As an example: the problem is to find the Student that has a given name. Here is an algorithm called sequential search:

      1. Start with the first student
      2. If it has the right name, exit,
      3. Else go on to the next student and repeat the previous step.
      4. But if there are no more students, signal an error.

      We will cover lots more of these later.

      How do you decide what classes to create and what function to put in them

      Good question. There are several answers. I like the one in [ cs375 ] which takes a quarter to start to learn:-(

      The steps go:

      1. Analyse the users needs into use cases.
      2. Analyse use cases into scenarios
      3. Select an interstin scenario or two to work on.
      4. Draw a daomian model for the scenarios
      5. Draw an SSD naming the steps in a scenario as function calls to system
      6. For each step map out some interactions and objects needed. Use the domain model to supply names for the classes.
      7. Collect the operations into a class diagram
      8. Code the classes, and test them
      9. Code the us case and test.
      10. With the user's help plan the next best scenario to tackle.
      11. Repeat with another scenario, or another usecase.

      Who would we draw diagrams for

      Your self, your future self, team members, managers, colleagues, the web, job interviewees, teachers, and (future) your students.

      Note --- putting UML diagrams where people can see them in your office or cubicle, is a lot more impressive than a picture of your favorite pop star or film actor.

      Do I have to memorize and distinguish all the different C++ exception types

      Not in CSci202. You might be wise to draw the hierarchy on your cheat sheet. You may need the diagram in the lab as well. However, I don't, for example expect you to know how a runtime error differs from a logi error and so on.

      What happens if an exception is raised and is not caught or trapped

      The program aborts with a generic error message. You client probably has a heart attack.

      Please give an example

      Normally we catch errors in a function that calls the function that throws the exception.
       	try {
       		function();
       	} catch (...) { cout << "Catch\n"; }

       void function()
       {
       	...
      .AS_is throw 42;
       	...
       }

      What does a throw actually do

      It undoes any function calls and jumps to the first catch that can handle the object that is thrown.

      How to create my own expction class

       class mine: public standard {
       { public: mine(....) : .... {}
       		...
       };

      Should we remove exceptions when the program is debugged

      No. Wen well done, exceptions become part of the excepted and desirable behavior of your program. Th user never knows what compilcated paths of "try and error" were needed to produce what they wanted.

      How does abort differ from throw

      Abort teminates the program, but you can catch the 'throw' and keep the program running.

      Why do program still crash with all these techniques available

      People still use the old languages.... and some are not well trained in modern techniques.

      Why has my browser started crashing.

      On a Microsoft machine, You've proably got a virus. Get your computer checked out and cleaned... and take more care in the future.

      On a Linux machine -- the code has a bug. Get an update... or join the people who develop open source.

      Exeptions vs assert

      Use assrt as a testing tool. Use exceptions to handle bad data in a function.

      Is there a best way to handle exceptions

      Not really.... there are some good patterns but you have to take time to think up the best thing to do with every one.

      Should we use exceptions in this course

      Yes. In the next Lab!

      What is class ios

      It is a convenient place for the C++ standard library to store a dozen or more special constants that are used to control Input and Output of Streams.

      You will see these turn up as things like

       		ios:app
      (signals opening a file for appending new data after the existing data).

      What is the difference between formatted and unformatted input?

      Unformatted input is copied, one character to one byte, from the input source into a piece of memory -- normally an array of characters.

      Formatted input takes in characters and parses them, figures out what data they represent, and puts the result in a variable or object of a particular type. The translation depends on the type of the variable or object. There are predefined input for all predefined data types: ints, floats, etc. Many different codings are allowed as well.

      Consequence: formatted input is slower, more powerful, more likely to fail, and most often used.

      Can you input data without knowing its format?

      This takes extra effort. First read in unformatted data into a string or character arrray. Then use if statements and strstreams/stringstreams [ 11.html ] to try out different formats till one fits.

      In the worst case scenario you end up writing a small compiler...

      Are all readable streams from class istream?

      No. fstreams can be read and written. istream is for streams that can not be written!

      Is ios and abstract class?

      I don't think so because it seems to have objects like ios.in. On the other hand... I don't think that most programmers ever have to declare a variable of type ios.

      Will we be needing #includes other than <iostream>?

      Yes.

      What are manipulators?

      A manipulator is an object that appears together with either a << or a >>. In other words these operators are defined for it. They change the behavior of the stream. This is high power magic... but safe when used as described on the label. Side-effects: your code gets shorter.

      Do you feel like being a magician and experiemnting with iomainpulators? If so see [ Do-it-yourself Manipulators in iomanip ] which shows you how to define some simple ones.

      Why does assert(x==y) always fail?

      This happens most often when x and y are floating point expressions. NEVER use == and != to compare floating or double numbers. Rounding errors make the result false.

      Use this instead:

       		fabs(x-y) < the_acceptable_error

      This is also true of using == and != in an if or a while.

      What happens if you don't close a stream?

      The end of the program should invoke the destructors for all open streams and these should close the files.

      What do cin and cout stand for

      "C input" and "C output" respectively.

      Notice that "i" and "o" are used consistently to indicate "input" and "output".

      What is cerr?

      It is a stream like cout that is for reporting error messages to a user running the program on a terminal.

      What is clog?

      It is a stream like cout that is for recording what a program has done: a log.

      I've never found a use for it, yet.

      Can you give an example of how to connect a file to a stream?

      Here [ fq.cc ] is an old example. You should try it and make it work with a .cpp extension etc. There will be some more examples TBA. Including Lab06.

      What happens if nothing catches a thrown exception?

      The program terminates. A message like "Aborted", "ABEND", etc. is output. Typically the user gets angry and smashes something.

      What does setprecision(n) do?

      It controls how many deimals are displayed. I don't memorise the details. They won't be needed in quizes or the final. BUT you need a good reference to look up the details when you need to use it in a practice.

      Notice: it does not change how values are calculated. Calculations are done in double length in C++. It just controls what the user of the program sees.

      Is there an online listing of input output commands in C++?

      Yes. See [ iomanip.html ] (trancribed from the GCC library) and [ lib-iostreams.html ] (from the draft C++ standard [ http://cse.csusb.edu/dick/c++std/cd2/ ] ).

      How do you change data inside a file

      This can get very messy unless the file is deliberately set up to make it easy. The file is like a book and replacing a word in the book by a longer word is usually impossible....

      But if the file consists of a long series of records that are all the same length, you can use "seekg" to jump to the record to change and read it into primary memory, then edit the data in memory, seekp back to the start of the record and put the updated data back into the record.

      Can C++ create images?

      Yes.... but it is only easy if you include libraries that have the write functions in them. There are a dozen separate librarys for doing imges in C++. None are a true standard, so I don't cover them or ask questions about them on the final/quizzes.

      Can C++ access networked files?

      C++ relies on the operating system to make remote files available to it. The same commands and streams then do the work.

    How do get access to a .txt file in C++?

    [ ptxt.cpp ]

    How can an open file close itself by a destructor?

    When any object goes out of scope... at the end of the block in which it is declared.... its destructor is called. In the case of a fstream this then calls the function close().

    What is the difference between ixxx and oxxx?

    The i indicates the stream is for input and not for output. The o indicates means the stream is for output only.

    If you have a program that needs to both read and write data to a file use an fstream.

    What is the differnce between fstream strstream and stringstream?

    The first is attached to a file, the second to a char*, and the last to a C++ string variable. Note -- strstreams are older than stringstreams and may be removed in future versions of C++.

    Do we have to learn all these new words for types?

    Learn the pattern that underlies them, pick one item from each line below:
    1. i | o | nothing
    2. f | string |str
    3. stream

    Where does sstream fit?

    This is a library that defines the three kinds of stringstreams.

    Does it take time to seek data in a file?

    Yes. It depends on the average seek time for the disk and the number of positions moved. A long 'seek' take longer to execute than a short one.

    Why would use just istream or ostream

    To make the size of the compiled program smaller.

    Is position 0 in text file really the first character?

    Yes. Nothing hidden! Information about the file is kept in a separate place that depends on the Operating system.

    WHy do I need to access the arguments of main?

    (1) See the lab work. (2) WHen commands are input they have the name of the program plus other data:
     		11peek name_of_file
    and so these programs need to get this information. The operating system puts the arguments into the arguments of main.

    When writing a file does anything stop other processes writing it as well.

    NO. Dangerous! There is File Locking (flock?) but it is better to use a real data base with "Record Locking".

    What Data Structures are in the STL


    Table
    NameLibraryNotes
    vector<vector>indexed contiguous sequence
    deque<deque>vector grows at both ends
    stack<stack>LIFO, push, pop, top, empty, size
    queue<queue>FIFO, push, pop, first, last, size, empty
    priority_queue<queue>Biggest floats to top, push, pop, first, last, size, empty
    list<list>slice, dice, insert, sort, ...
    set<set>ordered collection of unique items, intersections, union, etc
    multiset<set>ordered collection of items, intersections, union, etc
    map<map>ordered set of pairs, first key to unique items,..., general array
    multimap<map>ordered set of pairs, first key to items,..., general array
    functionsvariousYes, functions are also objects. There are functions that have functions as data and produce functions!
    streams<iterator>Access files, cin, cout using iterators and algorithms

    (Close Table)

    Are containers, iterators, and algorithms used in internet applications?

    Yes. Internet applciations should have a specialized fron end that interacts with the user and sends them pages to view. Each internet technology has different ways of handling this.

    Inside each application are search engines, data bases, containers, iterators, and algorithms -- and nearly all of them come from computer science.

    How do the different STL containers differ

    What operations are efficient -- [ cppcontainers.html ]

    How to choose the right STL container

    [ containerchoice.png ]

    What does an fstream do?

    It allows input and out of data from and to a file.

    Can I explain how iterators work?

    Later. We will design and implement some in CS202.

    Is it beneficial to write algorithms out instead of using the library?

    Onely in a class like CS330!

    What are the associative containers?

    Set, map, multiset, multimap. See questions below.

    What is a set?

    A collection of objects. You can insert and remove them. You can test if an object (or another set) is in a set. C++ sets are kept in order and you can visit each member in turn. However you can not have duplicate elements.

    Example: The set of students on my roster.

    What is a multiset?

    It is just like a set accept an item can appear zero or more times.

    What is a map?

    A mathematical map is a relation between two sets of objects called the domain and codomain. It is a map because each element in the domain has no more than one element in the codomain. It is well known that any relationship can be seen as a set of pairs. So, in C++, a map is a set of pairs like this
     		pair(x,y)
    and each x has no more than one y. WHat is cool is that if m is a map associating each X with a Y, then
     		m [x]
    is the y. More you can use assignment to add and modify the pairs:
     		m[x]=y;

    What is a multimap?

    It is like a map only each x can have many ys.

    Can you explain function objects a bit more?

    A function object is an object that can work like a function. In other words it is an object that can appear in C++ code like this
     		function_object(arguments)
    In other words
    1. Any function is a function object!
    2. Any class that has the operation() defined is a function object.
       			T operator () (arguments){....}

    Function objects are the modern OO way of communicating a calculation or test to another function. That function knows how to use it, and doesn't worry about what it does.

    Here is a dumb example [ testFillGen.cpp ] of using function objects.

    What are function adapters?

    A function adapter is a special kind of function that takes another function and returns a new adapted function that uses the original one.

    THink of a the pwer adapters you use when you visit a foreign country.

    We won't use them any quizzes or the final but I may be forced to use one in a lab. You may find them helpful after you graduate.

    Why are random access iterators most powerful?

    A random access iterator can do everything that a bidirectional iterator can. And a bidirectional iterator can do everything that a normal iterator can do:
    Table
    Type of IteratorOperations
    Random access*, =, ==, ++, --, +=, -=, [], ...
    bidirectional*, =, ==, ++, --
    Random access*, =, ==, ++

    (Close Table)

    Why can't you us pointers with containers?

    They are dangerous and iterators do the same job better.

    What are the advantages and disadvantages of using library container classes?

    As a rule the only downside to using container classes is that you have to know them well enough to find one that helps you solve a problem. You use the pleasure of reinventing the wheel.

    Often, you can find a predefined container/algorithm that does what you want better than you could. It is likely to be faster and cleverer than anything you could do quickly.

    What are function adapters?

    Function adapters allow us to construct function objects with complicated behavior without declaring a class or function. They are operators that manipulate functions rather than numbers or characters.

    You shouldn't need to use them in CSci202, but you may find a use for them in your future career. For example, do rapidly develop a version of the quicksort algorithm I needed to use the partition algorithm and that needed me to define a predicate that was true for all items less than or equal to a particular value. To do that I used a function adapter to convert the predefined less_equal function object into the predicate I wanted:

     		bind2nd(less_equal<int>(), value)
    Key point: I didn't expect to ever use this clever feature of C++, but did so this week.

    Can you go over maps and sets?

    Check out my stl.html notes (see above).

    Key points?

    1. Both are ordered collections of data.
    2. You can new data to the collections, remove items, found out if they are there, modify their contents, etc
    3. Maps associate a key value to a data item.... and act like an array:
       		map<string, int> directory;
       		directory["Dick"] = 5327;
    4. C++ has implemented the mathematical set theory operations! [ Set Operators in logic_30_Sets ]
      Table
      MathC++ example
      Subset includes(A1,A2,B1,B2)
      Union set_union(A1,A2,B1,B2, C);
      Intersection set_intersection(A1,A2,B1,B2, C);
      Difference set_difference(A1,A2,B1,B2, C);

      (Close Table)
      Note: A1,A2 and B1, B2 define ranges in two sets. C is an inserter for a set.

    When to use an iterator vs a pointer?

    Use an iterator to refer to items in containers. Pointers for items in an array, or items on the run time heap.

    Explain namespace std!

    Names are placed in namespaces. The namespace std is where standard names are put. Officially we must prefix names with their namespace like this
     		namespace::name
    but this gets old quickly. Instead we can write
     		using namespace whatever;
  1. and the C++ compiler will assume that we wanted "whatever::" in front of names that are in the "whatever" namespace.

    Some older compilers let you be lazy and leave out the using namespace.

    How does a priority queue work?

    Magic! Take CSCI330 to get the answers!

    Do stream iterators really handle input and output?

    Yes. Here is some code I found in a sample program
      copy(v.begin(), v.end(), ostream_iterator<int>(cout, "\t"));
    It outputs every int in the container v with a Tab between them.

    See [ ostream_iterator.cpp ] for a complete working example of both io-iterators.

    Compare four kinds of iterator?


    Table
    iteratorThe normal way to move across container and change things in it.
    const_iteratorThe normal way to move across a container. Can not change items!
    reverse_iteratorThe other way to move across container and change things in it.
    const_reverse_iteratorThe other way to move across a container. Can not change items!

    (Close Table)

    Is Binary Search the fastest search algorithm?

    If the data is sorted and tightly packed in a large random access array it is probably the fastest way to find an item.

    Some special cases can be faster in practice: for example Hashing the search key to find an address in an array to store an item works with a short calculation and one retrieval... as long as there is spare space in the array -- say twice as many items as you have.

    Never forget -- a binary search only works if the data is sorted. It slows in down to a very bad search if you always have to sort it before you search the data.

    Is an algorithm a specific program or a method to solve a problem.

    An algorithm is any well-defined method of solving a problem. One algorithm has many programs.

    Can you say more about the Big-O System?

    I will be testing your knowledge of the Big_O information in [ alg.html ] in later quizzes and a final. But I do not expect you (in cs202) to be able to calculate Big_O's. Just be able to recognize the typical curves and be able to predict what the likely Big_O time for an algorithm is.

    However Big_Os are easier to calculate than normal algebra -- because we can forget constants and lower order terms:

  2. O(32*n + 5*n*n +3) = O(n + n*n + 1) = O(n*n).

    Here are some good sites: [ bigOnotation.html ] (NIST), [ Big_O_notation ] (WikiPaedia), [ LandauSymbols.html ] (history), etc. .

    Is Big_O a kind of limit as n->infinity?

    Approximately yes... but we also ignore constant terms.

    Does it take exponentionally longer to do a n-squared than a linear algorithm?

    NO! To get a feel for this.... do the lab or write some simple prgram with n*n loops and see what the feel like.

    Typically we get the feeling that an n*n algorithm is broken on larger data sets..

    Does it take exponentionally longer to do an exp(n) than a linear algorithm?

    YES!

    Here we are usually surprised at how few data is needed to make the program do nothing for a worrying length of time.

    Go over the rating of algorithms:


    1. O(1) -- cool
    2. O(log n) -- neat
    3. O(n) -- OK
    4. O(n log n) -- not so good
    5. O( n*n ) -- try something else
    6. O( exp(n) ) -- why????

    Can you give an example of a greedy algorithm?

    Well.... we don't study these in CSci202 but Prim's algorithm for growing the smallest cost spanning tree in a given graph is a classic. As a special case suppose we want to connect 10 buildings by a set of tunnels (for cables, heating, cooling etc.) then the minimum cost tree would be cheaper then any other solution as long as tunnels only meet under biuldings.... The other solution ( Kruskal's algorithm ) is another classic greedy algorithm. You can find these, if you need them by a web search...

    Have you ever tried to figure out the Traveling Salesman Problem?

    Yes. Many times. The first time was in 1967 or 1968.

    How does a divide-and-conquer differ from a binary algorithm?

    A binary search is a special kind of divide-and-conquer: it divides the data into two equal sets. The word binary stands for two parts.

    Which type of algorithm is most useful?

    Every programmer needs to know about searching and sorting algorithms.

    Are there any fun web sites about algorithms?

    I like some of the animation sites. To get an uptodate list do a search: [ search?cat=web&cs=utf8&q=algorithm+Animation&rys=0&_sb_lang=pref ] You have to dig and experiment a bit but some are quite rewarding.

    What is the best algorithm for....?

    It all depends on the data -- (Donald Knuth, IFIP, 1971).

    Can you explain heaps?

    No! Not in CSCI202. Please take CSCI330!

    Do these algorithms work with non-numeric data?

    Yes: characters, strings, and objects of your own classes.

    Note: for your own classes, some containers only work if you define

     		bool operator<( yourClassName * the_other );

    How do you choose the right algorithm?


    1. Know lots of algorithms and how they perform.
    2. Know what you need: run quickly, write quickly, save space, score points, ...
    3. Put the two piees of knowledge together and make an educated guess.
    4. TEST your guess.

    What can the different types of iterator do?

    Different containers provide different iterators, and these differ in the operations defined on them
    Table
    typeOperations
    forward++, ==, !=
    bidirectional++,--,==,!=
    random+, +=, -, -=, ++,--,==,!=

    (Close Table)

    When and how do we use generate?

    Here is are two examples of code generating a series of numbers using generate: [ testFillGen.cpp ] [ testFillGen2.cpp ]

    Use generate when there is a simple way to calculate a series of items in a container.

    Is there a way to find out all the algorithms in the library?

    The book is pretty complete.... Also see the next question.

    There are many more algorithms that covered in this book. See the further see [ Are there any good books on algorithms? in alg ]

    How do we find out how an <algorithm> works?

    Mostly yopu only need to know how to use it and how it performs.

    You can learn how they should be coded in CSCI330.

    You could look in Barjne Stroustrup's Book (Chapter 13).

    To be sure what we have, you have to find the source code. On UNIX systems, like ours, you need to look in

     		/usr/include
    You can use ls to "LiSt" what is in this. I think you will find the relevant #include files in
     		ls /usr/include/c++/4.1.1/
    and the details in
     		ls /usr/include/c++/4.1.1/bits
    However, this code is not very readable.

    When should we use a heap?

    In [ lab07.html ]

    When should we write a heap?

    After starting CSci330.

    What is the difference between XXX and XXX_if?

    XXX does something to every item in a range, XXX_if does the same thing to some items in a range. It has an extra argument that is a function that turns on the action: true means do it, and false means don't.

    What are the most important algorithms in Appendix C?

    It all depends on what you need. For quizzes and the final I don;t expect you to be able to do anything that involves a predicate or mother function object.

    It would be good if you new of the existence of all the algorithms. You need to be able to use the simplest ones (no function objects or predicates).

    When we push an item onto a priority_queue is the queue automatically sorted?

    In effect yes. In practice, a priority queue is designed so that the minimum of work is done to reorganize the data into the right order.

    How well can we determine the best algorithm for a situation?

    The better you understand the situation the better choice you can make. Sometime you might as well just choose the simplest code and get that to work. Optimize it later.

    What are double linked lists?

    A single linked list has one link. A double linked list has two paired links. One reverses the other. So, if one is "next" and the other is "previous" then we expect
     		pointer->next->previous == pointer
    whenever pointer->next is not NULL.

    Can you go over recursive data types?

    Data types are not exactly recursive. They just can store the addresses of objects of the same type. This lets them reflect a recursive structure in the real world. For example in a family tree each person has two parents, so a realistic class would be:
     		class Person{
     		...
     			Person * mother;
     			Person * father;
     		...
    			friend void print_ancestors(Person * p, int gen);
     		...
     		};
    The rule is that once the compiler sees "class NNN" then you can declare pointers "NNN * nnn;". The NNN class is incomplete. You can not declare objects of type NNN: "NNN object" until the complete class is done.

    We use can use recursion to move around and explore these structures:

    		void Person::print_ancestors(Person *p, int g=0)
     		{
     			if(p)
     			{
     				list_ancestors(p->mother, g+1);
     				list_ancestors(p->father, g+1);
     				cout << substr(".........", 0, g)<<*p<<endl;
     			}
     		}
    (unchecked code).

    What is the advantage of a list over a vector?

    You can quickly insert and delete items into the middle of a list.

    How can items be inserted in alist without moving the other items out of the way?

    In a linked list items are not stored in a sequence of adjacent pieces of memory -- like an array or a vector. They are placed where-ever their is space in the computer. The sequence is maintained by the computer remembering where the data has been put. So if we have two chars 'a' and 'b' in the first and last elements of a linked list the memory could look like this:
    Table
    AddressContentsSymbol in C++
    ...
    1200'b'first->next
    12020first->next->next
    12022400first->next->prev
    ...
    2400'a'first
    24011200first->next
    24020first->prev
    ...

    (Close Table)
    We would also need to store the number 2400 as the address of the first item. Now when we insert data 'c' in between 'a' and 'b' we could get
    Table
    AddressContents
    ...
    1200'b'
    12020
    12023400
    ...
    2400'a'first
    24013400
    24020
    ...
    3400'c'
    34011200
    34022400
    ...

    (Close Table)
    Notice that the data are in the same places but the pointer values have changed.

    Is their something like Element hidden in the C++ Standard Library?

    Probably. Just about every linked implementation of a container has an Element or Node internal (and private) class to hold the contained data and links to other items in the container. You might try the source code in /usr/include/g*/....

    Are pointers stored in RAM?

    Yes.

    Do pointers use less bits?

    Yes.

    Because: a typical rcord for a person might have several 100 bits of data and the point no more than 32bits.

    Consider: which takes up more space:

    		QA76.76 C 1978
    or the book found at that place on the shelves in the library.

    Which takes up more space: you or your phone number?

    Why combine linked data structures and recursion to reverse a string?

    Why not? It is easy! You can also use a stack..... see the text and laboratory 8 below.

    15demo.cpp didnt work on MicroSoft.NET

    I'm not surprised.... I would guess you will have to do something with <iostream> and cerr. Let me know more detials... TBD

    What is a set?

    In mathematics it is an unordered collection of elements with no repeats. In Computer Science it is an ordered set of items. We have at least the following operations
    Table
    NameMathMeaning
    memberx ∈ ATrue if x is in A else false.
    unionA ∪ BElements in either A or B
    intersectionA ∩ BElements in both A and B
    insert-Afterward inserted element is in set
    remove-Afterward inserted element is not in set

    (Close Table)

    Can you explain the helper function uni?

    This is a classic two way merge of two sorted lists. It works by selecting the smallest of the first items in the two lists. For example merging (1,3,4) and (2,3,5) we create a list that starts (1.... and is followed by the merge of (3,4) and (2,3,5). To merge (3,4) and (2,3,5) we take the 2 and then merge (3,4) and (3,5). Then we get the 3 and add to it the merge of (4) and (5). We have to be careful at the end of lists.... but we will get ...4,5). Putting these parts together gives us (1,2,3,4,5).

    You can always type in code like this and add a debugging output:

     		cerr<< .....<< endl;
    at the start to see what the code does.

    Doubly linked lists seem better than singly linked lists should we also use them?

    Adding links to a data structure often makes it more powerful. However we have to store the extra pointer, and we have to manipulate/copy/change the extra pointer. As a result doubly linked lists take up more space and can be slower than singly linked lists.

    Use a simply linked list when you need a simple structure and program performance is more important than your time. Otherwise use the Standard Library!

    Use a doubly linked list when you want reliable coded and bi-directional access.

    In a complex data structure with many different links use the UML to work out whther you need a single or double linked connection. An arrow head [ Linked Data Structures in uml1b ] is the best notation for singly linked data.

    What is the special Element at the start of the Doubly Linked list in the book?

    This is a called a tombstone. It stays there when the rest of the list has gone. It simplifies coding insertion and deletion because we know that before EVERY Element there is a previous one, and after each one there is a next Element. No NULL pointers to test for and program around.

    What is the difference between a link and a pointer?

    Not much. A link is often used to indicate a special pointer used to connect items in a container. So a link is typically a pointer from a class, back into the same class.

    Why use a dynamically linked list instead of an array/vector/deque/...

    To allow you to insert and delete elements in the middle, without copying the data.

    What is a matrix used for?

    A matrix was invented in the 1800's to describe linear equations and the manipulations needed to solve them. In this form they turn up in just about every part of Physics and Engineering. As one example, the relation between the stresses and strains in an aircraft wing is modelled by a very large matrix of numbers. Using it we can find out if a wind design is strong enough before we even build the aeroplane. In computer graphics we use matrices to handle perspective, rotating objects, the surfaces of complex things (eg faces), the behavior of light, and so on. I used matrices last in my research to model removing bugs from a program -- Markov having shown how matrices model changes in the probabillities of different states. There are MANY more examples.

    For me, the coolest thing about learning matrices was replacing 25 coeficients in 5 different equations by the letter A.

    In this book and in CS202 we can forget the above.... and treat matrices as two dimensional tables.

    What are the double colons for -- do they make an iterator?

    Something like this [ ClassA::Name ] is used outside ClassA to refer to something called Name inside ClassA.

    Since the book and the STL both declare iterators inside container classes the form [ container::iterator ] (STL) [ Container::Iterator ] (book) refer to the correct type of object to iterate through the Container.

    Is it really a good idea to define classes inside other classes?

    Yes -- when you want a helper class that is protected from abuse and when it belongs to a particular class.

    Is an iterator a palce in a container or the contents of a place in the container?

    An iterator is a place in a container. The contents is got by using the asterisk:
     		* it

    Each iterator refers to at most one place in a container.... sometimes it refers to NO place at all.

    What is the difference between prefix++ and postfix++?

    i++ and ++i increment i, move the variable up one item. But, i++ returns the old value of i and ++i the new (bigger) value.

    Can an iterator indicate a place in an empty container?

    No. But it can refer to a place outside the container. For example c.end() is an iterator value outside c and so a natural place to make a iterator refer to, if the container c is empty.

    Do trees have iterators?

    Yes. at least 3 or 4. See CSci330.

    What is the benefit of defining an iterator since a pointer can do the job?

    Safety. It reduces the chances of some programmer mis-using your container and letting bad things to happen.

    Why do several function in the Iterator class have a throw clause?

    There is no way in C++ to attach it to several functions at one time. They make the iterators safe to use.

    What is the difference between standard iterators and ones we do ourselves.

    If we do well: just the author. If we do badly.... then the code in the library will be better.

    Is it important to be able to write our own iterators?

    I'm not sure. It depends on the shpe of your career. But I think it is important to know how to write them. At least knowing where to look up an example would be helpful.

    In the immediate future.... it would be easy for me to write an incomplete iterator class for a given container and ask you to fill in the blanks in the final....

    What is a template and how is it used

    A template describes a rule for constructing classes. Typically they are used by providing an actual class to replace the tempalte parameter. The compiler does the hard lifting.... a kind of reliable find, cut, and paste with the template.

    What is a static member?

    A part of a class that is not part of an object.... but part of the class itself. In a templated class then each instance of the template has it's own special members...

    Not on final.

    Not in Labs.

    You may need them in your future career.... perhaps.

    Are non-member template functions declared the same as member function?

    Yes.... but no need for a
     		ClassName::
    before the generic function:
     		template<typename T> Type_returned name(arguments){body}

    For example

     		template<class T> void swap(T&a, T&b){ T t=a; a=b; b=t; }
    See [ tswap.cpp ] (note -- there is a version of swap in the std library so I don't use namespace std).

    Do you have any simple template examples?

    Yes! See above and [ templates.html ]

    How do templates work?

    The compiler generates the class and function definitions that you need, automatically, and inserts them in your program in the right places.

    How are friends and helper classes related?

    A helper class helps you implement another class. Normally it is simpler for the helper class to let the class it helps have access to its variables and functions. So it declares it to be a friend.

    These days put helper classes and functions in the private part of the helped class.

    How does a class template differ from a class?

    A class template is a rubber stamp that produces classes (instances) as we need them. It describes an infinite set of possible classes. A class describes only one class.

    If a template is declared template<class T> can T be a simple data type?

    Yes. I think so. I find it less confusing to write "template <typename T>" instead.

    What do we do with a definition and a header file if the header defines a template?

    Keep the bodies inside the header.

    Why does anybody ever put the bodies in a separate file?

    (1) To hide the details of your clever coding and data from other programmer's eyes. This means they can't take advantage of any tricks inside the functions. All they can see (and abuse) are the headers in the '.h' file.

    (2) You can precompile the bodies into a ".o" object file once. Then you don't have to wait for the compiler to recompile it every time you use it.

    Note: if you do split body from header.... use a tool like "make" to handle compilations.

    Are there any predefined template classes in the standard library?

    Yes. Hundreds. Including: vector, dequeue, list, ...... Even the <algorithm>s are template functions!

    We made a template in CS201.... and it was quite useful!

    Cool!

    How do you have different types in a single typename parameter?

    Set up a object-oriented hierarchy and put pointers in the instance:
     		vector< Shape *> shapes;
    See [ 18.html ] next class.

    What is the syntax of a function template

      A function template is declared like this
    1. template < typename T > R N ( A );

      or this

    2. template < class T > R N ( A );

      and defined like this

    3. template < typename T > R N ( A ){ B }

      or this

    4. template < class T > R N ( A ){ B }

      where

    5. T is any identifier, usually T, that is called the template parameter.
    6. R is a result type. It can be "void", T, or any other class or type name.
    7. A is a possibly empty list of arguments. One must have type T or T&...
    8. B is the body of the function.
    9. N is the function name. If the function is a member function for class C then it must have form
       		C::N
      or
       		C < T >:: N

    What is a function template?

    A function template defines a whole family of similar functions. They are created, by the C++ compiler, by replacing the template parameter T by the type of data used in the argument list.

    What is an instance of a function template?

    When a function template is called, the compiler generates a special instance that is a normal function. The parameter T above is removed in the body of the template function and replaced by an actual data type. All the functions and operators etc are also regenerated for you (if possible).

    When should you template a function?

    When it is easy to do. Typically you've got an algorithm to work with ints, chars, or doubles and realizze it is the same algorithm whatever data you give it....

    When can the '&' be used and when omitted?

    Use the '&' in the argument of a function to get pass by reference whenever an argument is an object rather than a simple data type like "int", "char", ... It'll usually run faster, save space, and allow the object to behave like itself inside the function.

    What about const references & ?

    Use these when a function needs to use an object but not change it.

    Does C have templates?

    No. It had a dangerous and more powerful tool for generating code called a macro A macro is created like this
     	#define N(A) B
    from then on any reference to N(XXX) is replaced by a copy of B with XXX replacing A. There are no rules about what B is and what XXX is. As a result macros are powerful and surprising.

    Does C have function objects?

    To some extent. Any function has a name. The name, by itself, indicates the address of the function and so behaves like the address of an object, that behaves like a function. And an object that behaves like a function is a function object. However, C could not define classes of similar function objects.

    Can you make functions in the std library into templates?

    They are already templates!

    In the book what is IT?

    IT is a template parameter that will be an iterator.

    How do you test a destructor?

    It is easy to see if a destructor compiles and runs clean, but I can't think of a way to see if it is recycling all the memory correctly.

    If it fails to delete something then it will have a "memory leak" and it can take weeks of running the program for these to show up.

    If it deletes the same piece of memory twice then this may or may not work depending on the platform. Some platforms ignore extra deletes, but others give you a segmentation fault.

    This question is a powerful argument against the argument that testing can uncover all the problems with code. It shows that you may need more difficult techniques involving mathematics and logic to find all the bugs.

    What is an adapter function?

    An adapter function is like an adapter plug. It lets you plug into the wrong shaped socket.... If an object x has an operator f and you need a similar function g then you may be able to find a ready made or home made adapter a such that
  3. a(x).g(z) is passed to
  4. x.f(z)

    We will ignore them in the final.

    What is in <functional>?

    Some advanced and abstract functions. These a functions that operate on other functions to produce functions. In mathematics for example differentiation converts on function ( x*x for example) into another (2*x for example). Similarly <functional> is full of operations that take functions as data.

    As a rule they lead to elegant code for things that can be coded by less elegant means. They are mainly used when working with the algorithms library. I'll not mention them in the final.... but I think one may be needed in a lab.

    Here is a quote from the draft C++ standard


      2 Using function objects together with function templates increases the expressive power of the library as well as making the resulting code much more efficient.

      3 [Example: If a C++ program wants to have a by-element addition of two vectors a and b containing double and put the result into a, it can do:

           transform(a.begin(), a.end(), b.begin(), a.begin(), plus<double>());
      --end example]

      4 [Example: To negate every element of a:

           transform(a.begin(), a.end(), a.begin(), negate<double>());
      The corresponding functions will inline the addition and the negation. --end example]

    Reference: [ lib.function.objects in lib-utilities ]

    How to prepare for the final?

    Restudy the labs, quizzzes, web site, and book...

    Namespaces -- Not on the final.

    A way of avoiding globally defined names and collisions between different programmers.

    Use namespaces when

    1. You are told to.
    2. Your code is being used by others.
    3. You have to use other people's code in their namespace.
    4. The name for a function or class you've declared is the same as a standard function or class in the library. [ tmin.cpp ]

    Nearly all name spaces have a name and you can use names in it, without using two colons by writing "using namespace name".

    A program can use many name spaces.... It can create them, add things to them, and refer to items in many other namespaces.

    Namespaces will not be on the final.

    Is there any way to see how a type like int is coded?

    The command
     		sizeof(T)
    will tell you how many butes are needed to store an item of type T.

    Some operating systems let you look at the bits inside a program using hexadecimal... In UNIX for example there is the command od for octal dump. By writing a simple program you can get a picture of some of the values.

    To see how the operations work you really need to get the machine code manual as well as looking at the program in binary.

    What languages are viri/virusses written in?

    Binary.

    Bit Operators -- if we have time -- in a lab -- not on final

    Bit operators generalize Boolean operators. They work with many bits at one time. They are used to extract and manipulate parts of a computer and it's peripherals. For example to extract two bits from a word use
     		(word & (3 << position) )>>position
    You use '|' to set bits in word, and '^' to flip or toggle bits in a word.

    See [ bitzi.cpp ]

    Bit Fields -- not on final -- in a lab

    [ boolbit.cpp ] you can have a Boolean bit field.

    struct -- not on final but in lab

    The old way to define classes.

    You can write this

     		struct{ yada };
    like this:
     		class{ public: yada };
    that's all.

    They are best used to defines a small set of objects with no methods, to help a useful class like a stack or queue.

    union -- not on final but in lab

    A union describes a piece of memory with several meanings. It lets a program treat the memory as some char's and as an int, at the same time. It is mainly used in systems programing: compilers, drivers, OSs,... For examples see [ union.html ]

    Example in the lab.

    Modern programming tends to use inheritance to get a similar effect.

    do-while -- not on final - in lab and CSci320

    The do-while does some thing and tests to see if more is needed. This is unlike a while that tests first..... The pattern with a while is: test OK; do; test OK; do; test fails. With a do-while we have: do it; test OK; do it; test OK; do it; test fails.

    This difference is subtle. I avoid 'do-while' because it is easier to get it wrong.

    This code

     		do{ B } while (C)
    can always be re-written as
     		B; while(C){B}

    switch-case-break -- not on final in lab but not final

    Use switch point when it is simpler than many if-else if-else if-... Use a switch when there is 3 or more choices depending on values of ints, chars, shorts, longs,... Not for floating point or strings.

    They work by jumping to the correct case. This is often faster than executing a lot of 'if's to find the right case.

    Any cool web sites on structs and unions?

    [ LinuxTutorialC++Structures.html ]

    Can you give us an example of a double linked list?

    [ dll.cpp ]

    When drawing in the UML is the word const used?

    No. Not in the standard. In the standard you use the stereotype <<query>> to indicate a C++ "const" member function, if you really need to.

    However, our Dia graphic program does use "const" instead of "<<query>>".

    More on member functions

    [ Functions%20in%20Classes in functions ]

    Say more about virtual functions and polymorphism

    [ polymorphism.html ]

    More about templates?

    [ templates.html ]

    When should we use pointers and when iterators?

    Whenever possible use an iterator to refer to places in standard containers, or in non-standard containers that define iterators.

    Use a pointer to refer to another object that is not in a container, or as an iterator to places in an array.

    What do the visibility symbols in UML mean?


    Table
    SymbolMeaning
    +public
    -private
    #protected

    (Close Table)

    Can you review the UML symbols?

    In the final you need to know and use class diagrams.

    Classes are boxes. In the boxes you can have a compartment for attributes (data) and operations (functions). Classes have three common links:

    Four Common links between classes

    Here are some examples: [ Set.png ] [ SetIterator.png ]

    My notes: [ uml0.html ]

    Composition and aggregation in UML

    [ lookup.php?search=composition ] (use only when you have a whole that has parts inside it).

    [ lookup.php?search=aggreg ] (deprecated.... use an association with an arrow not an uncolored diamond).

    What is the purpose of a union?

    The Union lets you have several meaning for one piece of storage. So, it can save space. It is most useful for getting at parts of words at the bit level. This is very useful for system programming.

    As a rule unions are not used very much any more, except in system programs.

    What are the Basics of throw and catch?

    (1) When poisoned a function can
     		throw up;
    and so terminate.

    (2) When something is thrown some part of the program should be ready to catch the result....

     		catch ( Yucc up){ clean(up); }

    Are namespaces blocks used to separate functions with many definitions?

    Close! They can also separate multiply defined variables.

    Quick review of operators

    [ lookup.php?search=operator ]

    Is there ever a really good reason to use goto?

    Official answer: NO.

    My answer: to simulate co-functions and restartable code -- a simple to use form of concurrency. [ ../cs320/ ]

    What is the most rewarding program that you've done that is still running?

    [ ../cookie.php ]

    How Many Scopes are there

    About half-a-dozen. The number is not important. Just know the ones in chapter 18.

    What is the difference between = and ==

    The single = is used to change the value of a variable. The double == is used to compare two values to see if they are equal.

    Why are do-while loops more impractical than while loops

    When you enter the body of a while loop you know the condition is true and can use this fact in your could. In a do-while the condition may be false and you have to allow for this in your code.

    What is a lambda

    This is a 300 level question. For more see [ Lambda_calculus ] on the Wikipedia.

    What is the difference between arrays and vectors

    Arrays have a fixed size. Vectors can have elements added and deleted at one end.

    What is the point of pointers

    They let your program know where data is. Normally used to access data on the heap (created by new) or inside an array.

    How would use a pointer to search an array

    Suppose we want to search
     		Type a[SIZE];
    for an element
     		Type t;
    then the code might be.
     for(Type *p = a; (p < a+SIZE) && (*p == t ) ; p++)
     	;
     if(p<a+SIZE)
     	Found it
     else
     	Lost it.

    Go over deferencing pointers

    A pointer is a variable that holds an address of some data. We dereference when we us the pointer to find the data. It is like asking somebody where they put something... we dereference when we follow their description to get it.

    new

    The new operator creates a space on the heap that holds an object and returns its address.

    The arrow operator

    We use "->' to go from a pointer to an object to the meber of the object
     		point -> member...
    which is short for
     		(*pointer).member...

    Is any thing other than a pointer that can access the heap

    No.

    How is a pointer and iterator the same

    They both refer to an object in memory.

    How does an iterator differ from a point

    It refers to an object in a container.

    When to use virtual functions

    Nearly always...Exception -- function that are at the bottom of a hierarchy.

    Problem 4 on Quiz 1

     const int SIZE=10;
     vector<Enigma> v (SIZE);
     for(int i = 0;i<SIZE;
     {
     	v[i].games(i);
     }

    How does a map differ from a vector

    First a vector is always indexed by integers starting at 0. A map can be indexed by any data type.

    Second: a vector only grows and decreases at the end. A map can have a new value inserted at any point (and keeps the data in order).

    What is the answer to R7.14

    5

    How do you figure out the best algorithms

    First know a lot of algorithms. Second know what you want to do with the data. Third pick a suitably fast solution.

    How to chose a sort algorithm

    Rule 1: use a sort in the library. Rule 2: There are no other rules.

    Which is more efficient big-O

    As a rule O(log n) is better than O(n). O(n) is better than O(n^2).... draw the curves. And so O(log n) is better than O(n^2) -- for larger values of n.

    How to fill a vector with odd numbers

     for(int i = 0;i<SIZE;
     {
     	v[i]=2*i+firstOddNumber;
     }

    How to use streams to access a file

    Use an ifstream and open it.... then pretend it is "cin".

    How to use streams to write to a file

    Use an ofstream and open it.... then pretend it is "cout".

    How to read and write a file

    Use an fsteam and open/close it as input or output as needed.

    What do we need to know about streams in the final

    Look at old quizzes and study the book.

    When to use recursion

    When the problem (or the data set) can be divided into similar but smaller problems/data sets.

    How to use recursion

    First spot how to divide up the problem/data into similar but smaller problems. Second write code for the absolutely smallest problems/data sets. Third write the general cases that call the function.

    As a rule you must believe that the function will work.

    Will we need to figure out a recursive function

    Yes. I will give you a recursive function and you must find out what it does.

    Just DON'T PANIC.

    When to use value-reference-const-reference parameters

    Use value to pas a value (a copy) to a function. Use for all simple data that must no be changed by the function. Use reference when you need to and the function a variable and the function will change the variable. Use const reference when you have a complex object and don't want it copied AND you don't want it changed. The compiler will protect you from changing it.

    What is a mutator function

    A member function that changes its object's state. Also called a setter function when it changes a single attribute/data member because it's name starts set.

    Mutators should not (if possible) return a value and so be declared void.

    What is an accessor function

    A member function that is not allowed to change it's object but just returns a value. Also called a getter function because the name starts 'get'.

    When to use const in a class

    To declare an accessor function or getter.

    How to acces a member function in a Base class from a Derived class when the same name is used in both

     		Base::fucntion_name(.....)....

    What is operator overloading for

    Making concrete algebras!

    When to use inline

    An inline function is faster but uses more space. Use it when the function is SMALL. ONE line!

    When should a function be virtual

    Nearly always. Only in the most concrete classes at the bottom of a hierarchy should a function not be virtual.

    Where is virtual in UML

    It is automatic and invisible!

    Explain friend classes

    A friend class has access to all the data and functions in the other class. Dangerous.

    Will we draw UML diagrams in the final

    Only if you want full credit...

    What is the commonest errors in UML

    (1) getting the contents of the three parts of a class confused: Name+data+functions. (2) drawing the wrong arrow heads.

    Where can we see the code in the C++ library

    See /usr/include/c++/4.4.1 on our lab machines. And the best of luck...

    Give an example of a simple singly-linked list

    [ 15demo.cpp ]

    How do you use namespaces

    On big projects with many people.

    Not on the final.

    Can we take notes into the final

    You can take a single sheet (both sides ok) of notes.

    When can we use exceptions

    Whenever you have a function that might do something bad or wrong.

    Do we need to know how to catch exceptions

    You need to to know what happens when an exception is thrown and when and where it is caught.

    What search algorithms will be used on the final

    Linear and binary. No trees or hashing.

    When do you get a cycle in a data structure that makes reference counting fail

    When the data forms a graph rather than a tree or linear list. Covered in CS330.

    Not on the final!

    What is typeid

    Not on the final! It returns a string that indicates the type of an object.

    Explain overloaded operators

    You overload an operator like "+" ONLY when you have a new class that should have an addition operator. This is typically with arithmetic of complex numbers, rational numbers, vectors, and matrices.

    What is the most important fact about overloading

    Never forget the C++ overloads + to work with numbers (all types), characters, strings, and pointers.

    Explain the difference between a class and a nested class

    A nested class is just like any other class but is declared INSIDE another class.

    The commonest C++ examples are iterators are public but nested in their container class. But the STL also hide some private nested classes to implement containers.

    Here [ 20ex1.cpp ] is a simple example.

    Is friendship transitive

    No. If A is a friend of B and B is a friend of C then A does not get access to C.
  5. . Which is preferable -- protect or friend As a rule we try to restrict access to code as much as possible. Protected items are accessible to derived classes only -- on an item by item basis. Friends have total access to a class. So protected is the lesser evil.

    When to use protected

    Only when you have to. Sometimes in examples, exams, or when in a gigantic hurry.

    When to declare data as protected

    Try to make all data private but provide getters and setters that a protected instead.

    When to use virtual

    Declare functions in base classes virtual. This lets them be overridden by derived functions.

    Also use virtual when you have multiple inheritance but only want one copy of the data to be inherited.

    How to resolve functions that have the same prototype in two base classes

    Use
     		::
    operator to indicate the correct function.

    Dynamic casts

    Won't be one the final.

    What does deque stand for

  6. deque::="Double-Ended QUEeue".

    How to declare a deque

     		deque <string> something;

    How to use a deque

    Just like a vector except you have two extra operations: push_front(...), and pop_front();

    How to select between array vector stack queue deque etc

    Think about what the container must do for you. Choose the simplest type of container to get the job done.

    How to set up and use a map

     	map<int, string> m;
     	m[17]="fred";

     	for(map<int, string>::iterator i = m.begin(); i!=m.end(); i++) { ..... }

    Can you use subscripts in a for loop in a map

    Not easily.

    What is the difference between a list and a vector

    Vectors have efficient subscripts but you can only insert/delete at the back.

    Lists allow you insert/delete anywhere but don't do subscripts efficiently.

    When to use a map vs a multimap

    Not on final... Ask how many items you have for each index [subscript] value? If more than 1 then use a multimap. Other wise use a map.

    Where to store templates for reuse

    In a special directory -- for a project or a team.

    What are the types of memory errors

    TOO Many...
    1. buffer overrun
    2. using deleted memory
    3. deleting deleted memory
    4. not deleting memory
    5. not 'new'ing before use.
    6. Forgetting where data is stored
    7. ...

    What is the simplest way to prevent memory managment errors

    Use Java:-)

    In C++ -- THINK.

    What is the simplest way to correct a buffer overrun

    See the labs.

    What are the different types of memory


    1. CODE
    2. STATIC
    3. STACK
    4. ...
    5. HEAP

    Question 2 on Quiz 3

    Buffer overrun

    How does your leg feel

    I must admit it's getting better, getting better all the time...

    Which chapter is most important in practice

    All of them.

    What should we focus on in the final

    (1) the quizzes, (2) the exercises, (3) the Labs, (4) the rest of the book.

    How many questions on the final

    9

    How many must I do to do well

    9

    What is the software Life cycle

    Not on the final.

    Is a framework a diagram or code

    Code.

. . . . . . . . . ( end of section Frequently Asked Questions) <<Contents | End>>

Glossary

  • accessor::=`A Function that accesses information in an object with out changing the object in any visible way". In C++ this is called a "const function". In the UML it is called a query.
  • Algorithm::=A precise description of a series of steps to attain a goal, [ Algorithm ] (Wikipedia).
  • class::="A description of a set of similar objects that have similar data plus the functions needed to manipulate the data".
  • constructor::="A Function in a class that creates new objects in the class".
  • Data_Structure::=A small data base.
  • destructor::=`A Function that is called when an object is destroyed".
  • Function::programming=A selfcontained and named piece of program that knows how to do something.
  • Gnu::="Gnu's Not Unix", a long running open source project that supplies a very popular and free C++ compiler.
  • mutator::="A Function that changes an object".
  • object::="A little bit of knowledge -- some data and some know how". An object is instance of a class.
  • objects::=plural of object.
  • OOP::="Object-Oriented Programming", Current paradigm for programming.
  • Semantics::=Rules determining the meaning of correct statements in a language.
  • SP::="Structured Programming", a previous paradigm for programming.
  • STL::="The standard C++ library of classes and functions" -- also called the "Standard Template Library" because many of the classes and functions will work with any kind of data.
  • Syntax::=The rules determining the correctness and structure of statements in a language, grammar.
  • Q::software="A program I wrote to make software easier to develop",
  • TBA::="To Be Announced", something I should do.
  • TBD::="To Be Done", something you have to do.
  • UML::="Unified Modeling Language".
  • void::C++Keyword="Indicates a function that has no return".

    End