Frequently Asked Questions

Should we use 'using namespace std'

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
Variables s i
Command double int
double s=0.0; 0
i=1 0 1
i<5?
s=s+i; 1 1
i++ 0 2
i<5?
s=s+i; 3 2
i++ 3 3
I<5?
s=s+i; 6 3
i++ 6 4
i<5?
s=s+i; 10 4
i++ 10 5
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
Array Class
is an object is a data type
has numbered items has objects with named members
is old fashioned is object oriented

(Close Table)

What is a FAQ
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
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.
When we have a big amount of data in an array, vector, string, or other object and want to avoid copying it.
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.
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
Property Pointer Reference
declared by T*p... T&v...
address is p -
value is *p r
points at changes fixed
age old new .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
Relation Means Example UML
ISA is a special kind of Male is a Person Male---|>Person
HAS A has a A Person has two Legs Person <>-->Legs
KNOWS can access A Bank knows its Customers Bank--->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 ]
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();
```
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.

Variables	s	i
Command	double	int
double s=0.0;	0
i=1	0	1
i<5?
s=s+i;	1	1
i++	0	2
i<5?
s=s+i;	3	2
i++	3	3
I<5?
s=s+i;	6	3
i++	6	4
i<5?
s=s+i;	10	4
i++	10	5
i<5? FALSE

Array	Class
is an object	is a data type
has numbered items	has objects with named members
is old fashioned	is object oriented

Property	Pointer	Reference
declared by	T*p...	T&v...
address is	p	-
value is	*p	r
points at	changes	fixed
age	old	new .Raw safe? NO YES

Relation	Means	Example	UML
ISA	is a special kind of	Male is a Person	Male---\|>Person
HAS A	has a	A Person has two Legs	Person <>-->Legs
KNOWS	can access		A Bank knows its Customers	Bank--->Customer

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

ptxt.cpp

How can an open file close itself by a destructor?

close()

What is the difference between ixxx and oxxx?

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?

char*

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

i | o | nothing
f | string |str
stream

Does it take time to seek data in a file?

Why would use just istream or ostream

Is position 0 in text file really the first character?

WHy do I need to access the arguments of main?

 		11peek name_of_file

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

What Data Structures are in the STL

Table

Name	Library	Notes
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
functions	various	Yes, 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

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

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

cppcontainers.html

How to choose the right STL container

containerchoice.png

Can I explain how iterators work?

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

What are the associative containers?

What is a set?

Example: The set of students on my roster.

What is a map?

 		pair(x,y)

 		m [x]

 		m[x]=y;

Can you explain function objects a bit more?

 		function_object(arguments)

Any function is a function object!
Any class that has the operation() defined is a function object.
```
 			T operator () (arguments){....}
```

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

What are function adapters?

adapted

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?

Table

Type of Iterator	Operations
Random access	*, =, ==, ++, --, +=, -=, [], ...
bidirectional	*, =, ==, ++, --
Random access	*, =, ==, ++

Why can't you us pointers with containers?

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

pleasure

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.

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)

Can you go over maps and sets?

Key points?

Both are ordered collections of data.
You can new data to the collections, remove items, found out if they are there, modify their contents, etc
Maps associate a key value to a data item.... and act like an array:
```
 		map<string, int> directory;
```
```
 		directory["Dick"] = 5327;
```
C++ has implemented the mathematical set theory operations! [ Set Operators in logic_30_Sets ]
Table
Math C++ 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.

Math	C++ 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);

When to use an iterator vs a pointer?

Explain namespace std!

std

 		namespace::name

 		using namespace whatever;

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


iterator	The normal way to move across container and change things in it.
const_iterator	The normal way to move across a container. Can not change items!
reverse_iterator	The other way to move across container and change things in it.
const_reverse_iterator	The 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:

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:

O(1) -- cool
O(log n) -- neat
O(n) -- OK
O(n log n) -- not so good
O( n*n ) -- try something else
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?

Know lots of algorithms and how they perform.
Know what you need: run quickly, write quickly, save space, score points, ...
Put the two piees of knowledge together and make an educated guess.
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

type	Operations
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

Address	Contents	Symbol in C++
...
1200	'b'	first->next
1202	0	first->next->next
1202	2400	first->next->prev
...
2400	'a'	first
2401	1200	first->next
2402	0	first->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

Address	Contents
...
1200	'b'
1202	0
1202	3400
...
2400	'a'	first
2401	3400
2402	0
...
3400	'c'
3401	1200
3402	2400
...

(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

Name	Math	Meaning
member	x ∈ A	True if x is in A else false.
union	A ∪ B	Elements in either A or B
intersection	A ∩ B	Elements 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

template < typename T > R N ( A );
or this
template < class T > R N ( A );
and defined like this
template < typename T > R N ( A ){ B }
or this
template < class T > R N ( A ){ B }
where
T is any identifier, usually T, that is called the template parameter.
R is a result type. It can be "void", T, or any other class or type name.
A is a possibly empty list of arguments. One must have type T or T&...
B is the body of the function.
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

a(x).g(z) is passed to
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
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
Symbol Meaning
+ 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:

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.
. 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
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.

Symbol	Meaning
+	public
-	private
#	protected

. . . . . . . . . ( 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".