CSE 12
Terms
undefined, object
copy deck
- List OOP Advantage.
-
Code Reuse- code deloped today can be used in tomorrow's solutions
Increase Reliability- code written once is tested many times in many applications.
Natural- design is bound by similarities to everyday objects
Data Abstraction- use of objects are simplified by restricting details - List advantages of C.
-
No Magic- all code executed is obvious to the reader of the code.
Easiest to Debug- end product developed faster
Most portable- most mature language. - List Advantages of Java.
-
Garbage Collector- management of memory is removed from the desinger's task.
Rich OO Language features- allow more options for developer
Consistent syntax- pointers hidden from engineer for more maintainable code. - List Advantages of C++.
-
Templates- allow for homogenous container
Most Compile Time Checking- container knows object it stores
References- automatic validity checking improves efficiency - List Advantages of Disk File.
-
Size- more objects stored than allowed in memory
Longer storage of objects- objects exist beyond program execution
Most efficient use of memory- all data on RTS, so all automatically managed. - List Disadvantages of OOP.
-
Overkill- too complex a solution to a simple problem
High learning curve- much startup time before much progress can be made
Debugging is more complex- slower time to resolve problems - List Disadvantages of C.
-
Least Type Checking- least errors caught at compile time
Most syntactically complex- code produced is often cryptic
No OO Syntax- OO solutions are created by "stretching" language - List Disadvantages of Java.
-
Slow- compiler does a lot, not ideal for all real time solutions
No RTS objects- designer has less choices
Not Mature- language still evolving
Base- not intuitive yet forced to use it for our solution - List Disadvantages of C++.
-
Error Messages too verbose- problem not immediately apparent
Not too portable- implementations of compilers not standardized
Extra Template syntax- language keywords and symbols complicating the program logic - List Disadvantages of Disk Files.
-
Security- deleted items still present
Debugging Most Challenging- finding errors through viewing octal dump is very low level
File syntax was complex- code more difficult to maintain in read. - What does "delete" do in C++?
-
deletes an object created by new:
1) calls destructor
2) deallocates memory - Draw the derivations for hw4 from Base.
-
Base->Driver
Base->Calculator
Base->HashTable->SymTab
Base->List->Stack - Draw the derivations of hw5.
-
Base->UCSDStudent
Base->Calculator
Base->Tree->SymTab
Base->List->Stack - Draw the class derivations for hw6/hw7.
- Ask Tutor!
- What is a "friend"?
-
A friend can access private members of a class.
Ex. friend ostream & operator () - What does "new" do in C++ and Java?
-
It allocates new objects in the heap and does 2 things:
1) allocates memory for the object
2) call constructor - What does the Garbage Collector do?
- It automatically deallocates memory for an object as long as there is no reference to that object.
- C++ is polymorphic at run time: TRUE or FALSE?
- FALSE: it's polymorphic at compile time.
- What are the advantages of templates in C++?
-
1) allows for creation of polymorphic containers
2) allows for more homogenous container
3) polymorphism is extended to nonmember methods
4) allow for predefined types to be the object stored in the container
5) has a polymorphic constructor which allows you to instantiate unknown objects
6) allow us to remove our pointers to make our TNodes flat.
7) achieve polymorphism before instantiating objects.
8) Don't have to derive from Base which is unnatural. - What are the disadvantages of templates?
-
1) larger binding
2) more complicated syntax
3) can be harder to debug
4) implementation can be inconsistent across compilers - What is the use of the "const" keyword?
-
It can make a function logically constant for a type. It is so that you can't change any member fields w/in the function.
Ex. int Tree<> Func (void) const():
-this function will not make any changes in the tree class unless the data field is mutable. - In a Struct everything is private by default and in a Class everything is public by default. Is this TRUE or FALSE?
- FALSE: Struct= everything public by default, Class= everything private by default
- Describe our HashTable.
-
1) it is an array based generic container.
2) the items inserted must be "hashable" and "comprable" when using the collision resolution.
3) this algorithm is deterministic meaning items are placed where they belong and found where expected. - What is our method of hashing? List the 4 steps taken.
-
hash_value = element.getValue()
initial location = hash_value % table size.
increment = (numeric attribute % (table_size -1)) + 1
new_index = (current_index + increment) % table size - What is the bully algorithm?
-
If E' = element occupying the slot and E = element looking for a spot:
1) if E = E', replace it
2) else if E' < E: Bully! send E' looking for another slot while E takes its place
3) else E' keeps probing -
Draw a HashTable of size 5 w/ the following insertions.
i Shilpa
i Rocky
i Gary
i Thanh
i Sid -
index 0 = Rocy
index 1 = Shilpa, Sid
index 2 = Gary
index 3 = Shilpa, Thanh
index 4 = Gary, Shilpa - What are the benefits of using HashTables?
- fast! array indeces are computed in constant time using a Stack.
- What are the drawbacks of HashTables?
-
1) must be very careful to use good collision resolution scheme.
2) size of HashTable should ideally be prime
3) otherwise, performance deteriorates badly due to restrictions on implementation
4) good when empty, as gets more full, gets more ineffecient - When is guaranteed initialization not optional?
-
1) establishing a reference (like occupancy)
2) calling parent constructor explicitly
3) passing parameters to fields of a class that are objects
4) establish a constant w/ its value (size of HashTable) - What would happen if you initialized your members out of order in a guaranteed initialization block of code?
- You'd get a compiler error.
-
What kind of overloading is this?
UCSDStudent::Operator ==
(Const UCSDStudent & st) const{}; - Member function operator overloading
-
What kind of overloading is this?
bool operator== (const UCSDStudent & stu1, const UCSDStudent & stu2) {}; - nonmember function overloading
- Why didn't we implement << for UCSDStudent w/ a member function?
- The function would have to be ostream & UCSDStudent::Operator(ostream & os) in order to chain cout.
- What is a virtual function?
- A function call resolved at run time rather than compile time.
- How are virtual functions implemented?
- By defining them in a parent class and redefining them in a child class.
- What were the constraints for inserting objects in hw3 and hw4?
-
In hw3, prototypes of methods needed to match container prototypes.
In hw4, you define a set of methods for the object, and the object must be derived from Base. -
What are the uses of each traversal?
A) pre-order
B) in-order
C) post-order -
A) to copy a tree
B) to write out contents of a tree
C) to delete a tree - What are the benefits of references in C++?
-
1) Avoidance of constructor/ destructor calls for parameter objects
2) automatic, compiler enforced, validity checks
3) allows the power of pointers w/out pointer syntax - What is guaranteed initilization?
- syntax used to initialize data fields of a class when object is created rather than assignement of initial values of data fields in body of the constructor.
- Why would too many friends be too bad?
- destroys the use of keeping data "private"
- When would the scope resolution operator (::) be used?
-
1) when it's needed to access static methods and data fields
2) when you need to define a member method outside its class definition. - Why can't you use stu1.operator << (cout)?
- because the syntax would be inconsistent... stu1 << cout;
- Why can't you use cout.operator<< (stu1)?
- because the ostream class is provided by the language and has no operator<< specific for the UCSDStudent class
- Why can't just derive a new type from ostream since operator is made a friend?
- because cout is not an object of the UCSDStudent class.
- What was the primary reason for making an operator a friend?
- so that we have the consistent use of cout/cerr and << for displaying user defined objects
- Why do we have to create objects on the heap?
-
1) because we don't know the size of the object at compile time
2) because memory for the object stays when the function ends, so we had to deallocate it explicitly. -
What was the purpose of this line in hw7?
delete fio; - to destroy the pointer to the object. so there would be no access to it.
- What is the worst case Tree, Insert, Lookup(for list, and hashtable)?
-
1) Tree, when each node has 1 or 0 children nodes.
2) List, in a list in which you have to start searching from the beginning to the insertion point or point in which the item is found.
3) HashTable, when the table is getting full - What is the best case Tree, Insert, Lookup (in List, and hastable)
-
1) best case tree is one in which every node has 2 children (same height).
2) List: insertion/lookup in the front
3) When table is fairly empty - What was the purpose of Base?
- To insert and manipulate objects inside the generic container. Base exists to create polymorphic data structures.