CS128 QUIZ PREP pt 2

docx

School

University of Illinois, Urbana Champaign *

*We aren’t endorsed by this school

Course

128

Subject

Computer Science

Date

Jan 9, 2024

Type

docx

Pages

Uploaded by ChefSeahorse3109

QUIZ What are function templates? - Function templates allow you to write generic functions that work with various data types What is instantiation? - Instantiation is the act of REPLACING type parameters with concrete types What is template argument deduction? - Template argument deduction is when the compiler determines arguments based on the type of argument from the function call What is separate compilation? - Separate compilation allows you to split your code into separate files and compile them INDEPENDENTLY What is inheritance? - Inheritance allows a class to gain behaviors or functions or other classes, facilitating code reus What is a base class? - A base class is the class who’s properties are inherited What is a derived class? - A derived class is the class that inherits the properties What are the three access specifiers? - The three access specifiers are public, private, and protected What is the difference between implementation inheritance and interface inheritance? - Implementation inheritance is physically inheriting the specific features and interface is abstractly inheriting ? What is polymorphism? - Polymorphism means many forms What is name hiding? What is function overriding? What is virtual functions? What is polymorphic behavior? What are the 2 main types of polymorphism? Abstract classes vs. pure virtual functions? What is a tree? What are the basic operations of trees (traversal, deletion)> What are the types of trees?

Function Templates (part 1) Function templates allow you to write generic functions that work with various data types template <typename T> declares a template parameter ‘T’  The function ‘add’ will word with type ‘T’  T add(T a, T b) is the function template itself  The T function signature represents the template parameter In the ‘main’ function, add(5,10) and add(3.5, 2.7) are examples of using the function template with int and double types Line 1 declares a template with template parameter ‘T’ Defines a function template at T is the placeholder for the type that will be specified when the template is used Line 2 defines a function TEMPLATE named minimumValue that takes two parameters ‘a’ and ‘b’ of type T The return type of the function is also T Line 3 uses a ternary operator to return the min value between ‘a’ and ‘b’ “if b is greater than a, it returns a otherwise it returns b” T can be instantiated with any comparable type because ‘>’ is the operator for comparison To introduce a type parameter we use the keyword “typename” To define a function template we use the keyword “template” followed by the type parameters in angled brackets

T represents an arbitrary type Any type T can be used if it has the behaviors used in the template defined Instantiation is replacing template parameters by concrete types template <typename T> T add(T a, T b) { return a + b; } The ‘add’ function can work with any type ‘T’ Here is how instantiation works: int result_int = add(5,10); instantiates the function template with ‘int’ as the template argument This process of creating specific versions of the template for different types is instantiation Function Templates (part 2) Template argument deduction: the compiler determines the arguments for a template based on the types of the argument provided during a function call or object creation Template argument deduction makes it easier for programmers to use templates without explicitly SPECIFYING the template arguments From example above, add(5,10) – we don’t explicitly specify the template arguments, but the compiler DEDUCES ‘T’ as ‘int’ This deduction is possible because the template arguments can be inferred from the types of the function arguments *also used with class templates and constructor templates *there are cases where its necessary to explicitly provide the template arguments If we pass two objects of different types into our function the compiler would be unable to deduce what type T is Errors can be handled by...  Casting the arguments so they’re the same type  Explicitly stating what type T should be  Specifying the function template definition that the parameters are allowed to be of different types There are two main types of templates 1. Function templates

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

a. template <typename T> T add(T a, T b) { return a + b; 2. Class templates a. template <typename T> class Container { public: T value; Container(T val) : value(val) {} }; Template and Separate Compilation Important: templates must be visible at the point of instantiation Template declaration and definition should be available to the compiler when the template is instantiated Separate compilation allows you to split your code into multiple files and compile them INDEPENDENTLY By creating separate source files (contains implementation) and header files (that contain declaration) For each template instantiation (creating a specific instance of a template with concrete types) - the compiler generates specific code for that instantiation if you have various instantiations for function you will have various copies of code RECALL c++ uses separate compilation to compile multiple translation units The compiler operates on a single translation unit at a time When we #include a header file, the function declares and class definitions of the included file are “copied and pasted” into that file - the implementation details of these functions and classes place in the separate source file and are often not available until the link time

When you use this template with specific types, the compiler creates code for each combination of types you use. If you use the template with different types in different parts of your program, the compiler generates separate copies of the code for each combination of types. C++ breaks code into separate files for better organization. Header files contain declarations, and source files contain implementations. The compiler processes one part of your code at a time, known as a translation unit . It doesn't see the entire program all at once. #include in C++: When you include a header file in your code using #include, it's like copying and pasting the content of that header file into your code at that point. The included header file contains declarations (like function prototypes and class definitions), but often not the actual implementation details. The detailed implementations of functions and classes are placed in separate source files. These files are compiled separately. The implementation details are often not available to the compiler until the linking phase, where all compiled parts are combined into the final executable. DEFINE THE FUNCTION TEMPLATE IN THE HEADER FILE because we can’t wait until link time to access the implementation details for our function template Templates must be fully defined in each translation unit For the compiler to generate code for an instantiation of a template, the compiler must have access to the definition of that template within the translation unit where the instantiation PRESENTS Class Templates

Class templates allow you to define a generic blueprint for a class that can work with different data types Key aspects of class templates: Declaration, template declaration, member functions, creating objects, usage, use in main Example: with a vector<char> could we create a vector template for all types T? Classes can also be parameterized by one or more types Container classes, such as vector are a example of this feature by leaving the element type open as a template parameter Parameterization of types by types Implement a stack (a data structure) as a parametrized class Before class def, declare one or more type parameters Template <typename T> The type of the class is Stack<T> where T is the template parameter This type must be used in all declarations, where the template arguments cannot be deduced By declaring Stack<i> i is substituted for T everywhere it appears inside the class template definition The process of replacing template parameters by concrete types is called template instantiation To instantiate a class temple, YOU MUST specify the template arguments to the template parameters explicitly Class templates and separate compilation In order for the compiler to generate code for an instantiation of a template, the compiler must have access to the definition of that template - the class template definition and its member function template definitions

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Inheritance (pt 1) Inheritance allows a class to inherit properties and behaviors from another class, facilitating code reuse and creating a hierarchy of classes Base class: the class whose properties and behaviors are inherited. The parent class Derived class: the class that inherits from the base class is called the derived class/child class The : symbol is used to indicate that a class is inheriting from another class public specifies the type of inheritance (means public members of the base class remain public in the derived class) access specifiers public inheritance - public members of the base class become public members of the derived class - protected members of the base class become protected members of the parent class - private members of the base class remain inaccessible in the derived class using inherited members - the derived class can use inherited members (methods and properties) directly benefits of inheritance: code reusability polymorphism (allows you to create a unified interface for different classes through virtual functions) hierarchy and organization – helps organizing classes into a hierarchy flexibility and extensibility the visibility of inheritance: how members (attributes and methods) of a base class are accessible in a derived (child) class there are THREE access specifiers in C++ that control the visibility of inherited members - public o public members of the base class are public in the derived class o members are accessible in the derived class with the same access level - protected o public members of the base class become PROTECTED in the derived class o members are accessible in the derived class, but they are now protected - private o public members of the base class become private in the derived class o members are ACCESSIBLE in the derived class but they are now private Choosing the Access Specifier Use the public inheritance when you want to model an is-a relationship and when you want to expose the interface of the base class in the derived class

Use protected or private inheritance when you want to model a implemented, in terms of relationship, where the derived class is implemented in terms of the base class but is not intended to expose the base class interface directly Implementation Inheritance: Also known as concrete or class inheritance The derived class inherits both the INTERFACE (public members) and IMPLEMENTATION (private and protected members) of the base class About inheriting the actual code and behavior of the base class Achieved through public and protected inheritance Interface inheritance Known as “pure abstract” or “protocol” inheritance The derived class inherits only the INTERFACE (pure virtual functions or abstract methods) of the base class Its more about inheriting a CONTRACT or set of functions that must be implemented Achieved through public inheritance and abstract classes/interfaces VIDEO NOTES: Classes that can model things that are concrete or abstract Example: consider a truck and a fire truck A fire truck shares many attributes and behaviors with a truck, but its specialized Consider a concrete truck – also specialized – separate classes Create a supertruck? Parent/base class is the supertruck Child/derived classes are the fire and concrete truck Many things share common features with other things, the extent to which is dependent on the level of abstraction from which we reason about them We can use the process of abstraction to encapsulate the commonality of those things into a base class Lower level abstractions of the things comprising this base can be derived specialization and complexification Introduction to inheritance 2 fundamental but related functions of inheritance Implementation inheritance: when we define a derived type and its member functions, we can take advantage of the facilities (data and member functions) offered by the base type Interface inheritance: a function expecting a base type passed as a reference argument that function can take a deprived type and use a derived type through the interface provided by the base type

Public inheritance – is-a relationship X stays public Y stays protected Protected inheritance: “implemented in terms of” relationship X becomes protected Y stays protected Private inheritance: use to express an “implemented in terms of” relationship This visibility is used when we would like to use the base class’s public interface in the derived class, but do not want that functionality accessible by the user X is private Y is private Inheritance (part 2) Conceptual inheritance walkthrough If you don’t provide a default constructor, the compiler will create one for you. If you do not specify otherwise in the derived class, the default constructor of the base will be called implicitly

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

We observe the following output once we executed the compiled program Parent::Parent() was still called automatically We would like to initialize std::string str with a value passed to the base’s constructor: we want the base constructor to set up the base portion of the object. The child constructor to set up the child’s portion We declare and define an additional constructor that will initialize this The question now is how to call this constructor during the initialization of the derived class. We do this by creating a new constructor that takes a std::string as an argument and calls the base constructor in the initializer list as follows We update main to include the creation of a Child p object After compiling and running the program, observe the following output Declare and define the copy assignment operator Given the overloaded operator=() in the parent class, and that child inherits from parent with public visibility, child inherited the parents operator=() We would like to write an overloaded operator=() for our Child class, given that the Child should manage the Child components After adding the explicit call to Parent::operator=() in Child::operator=() the desired behavior was observed Additional material by example The activation record for this object will be composed of a base component and child component The base component was constructed with Truck::Truck() and the derived portion with FireTruck::FireTruck() Pointer or reference to the base portion WEEK 2 Inclusion polymorphism (part 1) – STUDY HOMEWORK QUESTIONS FROM THIS LESSON Inclusion polymorphism: refers to a type of polymorphism where a subclass object can be treated as an object of its superclass (closely related to subtype polymorphism) Key concepts Polymorphism is a core concept and it means “many forms”

Allows objects of different types to be treated as objects of a common type Inclusion polymorphism specifically refers to the ability to treat objects of a derived class as objects of the base class This is achieved using pointers or references to the base class type When a subclass is assigned to a superclass reference or pointer, it can be used as if it were an object of the superclass Name hiding: when a derived class declares a member with the same name as a member in its base class Can lead to unexpected behavior Member declaration in derived class  when a derived class declares a member with the same name as a member in its base class, the derived class’s member hides the base class’s member in the scope of the derived class Accessing Base class member  if you want to access the hidden member from the base class, use the scope resolution operator :: to specify the base class Avoid name hiding  to avoid name hiding, you can use the ‘using declaration to bring the base class’s name into the scope of the derived class Name hiding with functions  the concept of name hiding also applies to member functions  if a derived class declares a function with the same name as a function in the base class, it hides the base class’s function Function overriding and virtual functions Function overriding: occurs when a subclass provides a specific implementation for a method that is already defined in its superclass The overridden method in the subclass has the same signature as the method in the superclass Virtual function: a function in a base class that is declared using the ‘virtual’ keyword When a derived class provides a specific implementation for a virtual function, it overrides the virtual function in the base class Virtual functions enable dynamic polymorphism Key differences:  function overriding can occur without virtual keyword  virtual functions are declared using the virtual keyword in the class  function overriding provides static polymorphism as the decision of which method to call is determined at compile time  virtual functions enable dynamic polymorphism as the decision is made at runtime based on the actual type of the object

 function overriding works with pointers and references, but it uses the type of the pointer/reference at compile time  virtual functions work with pointers and references, and the actual function called is determined at runtime based on the type of the object being pointed to or referred to when you delete an object through a pointer to its base class and the destructor is not declared as virtual, it can lead to undefined behavior if you delete an object of a derived class through a point to ‘Duck’ the destructor will be called, but not the destructor of the DERIVED class so it will be a memory leak Inclusion polymorphism (part 2) Polymorphic behavior: the ability of objects of different types (often derived classes) to be treated as objects of a common base type There are 2 main types of polymorphism 1. compile time polymorphism function overloading: in compile time polymorphism, function overloading occurs when there are multiple functions with the same name but different parameter lists. the compiler determines which function to call based on the number and types of arguments during compilation operator overloading: where you define the behavior of operators for user-defined types 2. runtime polymorphism virtual functions: in runtime polymorphism the focus is on the behavior of objects during runtime -achieved through the use of virtual functions and inheritance 3. dynamic binding objects of derived classes can be assigned to pointers or references of their base class, and their appropriate method is called based on the actual type of the object during runtime Abstract base classes and pure virtual functions Abstract base class: a class that can’t be instantiated on its own and is meant to serve as a base for other classes. Often include one or more pure virtual functions Instantiation: abstract base class cannot be created directly. Must be inherited by a concrete (non-abstract) class and the concrete class must provide implementations for all pure virtual functions Pure virtual functions: a virtual function declared in a base class but has no implementation in that class

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Virtual destructor: to ensure that the destructors of derived classes are called properly when deleting objects through a pointer to the base class To ensure that the destructors of derived classes are called properly when deleting objects through a pointer to the base class If a class has a virtual function, it needs a virtual destructor Must be implicitly deleted through delete An introduction to trees Tree: a hierarchical data structure that consists of nodes connected by edges Each node in a tree has a parent node (except for the root node) and zero or more child nodes Nodes with no children are called leaves Trees are used to represent hierarchical structures, organizing data efficiently, and implementing search and retrieval operations Trees can be implemented using various data structures A tree node typically has data and pointers to its children nodes The structure for a basic binary tree node might look like this template <typename T> struct TreeNode { T data; TreeNode* left; TreeNode* right; TreeNode(T val) : data(val), left(nullptr), right(nullptr) {} }; Basic tree operations Insertion: inserting a node into a tree involves finding the appropriate location based on some ordering criteria and adding a new node with the desried value Traversal: tree traversal methods include in-order, pre-order, and post-order traversal These methods visit nodes in a specific order template <typename T> void inOrderTraversal(TreeNode<T>* root) { if (root != nullptr) { inOrderTraversal(root->left); cout << root->data << " "; inOrderTraversal(root->right); } }

Deletion  deleting a node from a tree requires handling various cases, such as nodes with no children, nodes with one child, and nodes with two children template <typename T> TreeNode<T>* deleteNode(TreeNode<T>* root, T key) { if (root == nullptr) { return root; } // Perform standard BST delete // ... return root; } Types of trees: Binary trees: each node in a binary tree has at most two children: a left child and a right child Binary search trees (BST): a binary search tree is a binary tree where the left subtree of each node contains only nodes with values less than the nodes value and the right subtree contains only nodes with values greater than the nodes value Balanced trees: trees that are balanced ensure that the height of the tree remains logarithmic with respect to the number of nodes resulting in efficient operations b-trees: balanced search trees that are commonly used in database and file systems to provide efficient search and retrieval operations trees with unbound branching: trees where each node can have an arbitrary number of children N-trees we store data in nodes that have pointers to other nodes a linked data structure emerges through these pointers to other nodes, and with proper consideration that structure will be a tree nodes with the same parents are called siblings nodes without any children are called leaves the depth of a node is the number of edges from the node to the trees root the height of a number is the number of edges in the longest path from the node to a lead the height of a leaf is zero the height of a tree is the number of edges in the longest path from the root to a leaf a subtree is a tree wholly contained within another in our diagram every subtree of a tree is also a tree

Introduction to binary search trees (BSTs) A binary search tree is a binary tree data structure in which each node has at most two children, referred to as the left and right child. The key property of a BST is that for every node ‘X’ all nodes in its left subtree have less keys than ‘X’ and all nodes in its right subtree have keys greater than ‘X’ This properly ensures efficient searching, insertion, and deletion operations Basic Structure: cpp Copy code template <typename T> struct TreeNode { T data; TreeNode* left; TreeNode* right; TreeNode(T val) : data(val), left(nullptr), right(nullptr) {} }; Insertion: Inserting a value into a BST involves traversing the tree to find the correct position based on the ordering of keys. cpp Copy code template <typename T> TreeNode<T>* insert(TreeNode<T>* root, T value) { if (root == nullptr) { return new TreeNode<T>(value); } if (value < root->data) { root->left = insert(root->left, value); } else if (value > root->data) { root->right = insert(root->right, value); } return root; } In-order Traversal: In-order traversal visits nodes in ascending order of their keys. cpp Copy code template <typename T>

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

void inOrderTraversal(TreeNode<T>* root) { if (root != nullptr) { inOrderTraversal(root->left); std::cout << root->data << " "; inOrderTraversal(root->right); } } Pre-order Traversal: Pre-order traversal visits the root node before its children. cpp Copy code template <typename T> void preOrderTraversal(TreeNode<T>* root) { if (root != nullptr) { std::cout << root->data << " "; preOrderTraversal(root->left); preOrderTraversal(root->right); } } Post-order Traversal: Post-order traversal visits the root node after its children. cpp Copy code template <typename T> void postOrderTraversal(TreeNode<T>* root) { if (root != nullptr) { postOrderTraversal(root->left); postOrderTraversal(root->right); std::cout << root->data << " "; } } Minimum and Maximum: The minimum value in a BST is found by traversing all the way to the left, and the maximum value is found by traversing all the way to the right. cpp Copy code template <typename T> TreeNode<T>* findMin(TreeNode<T>* root) { while (root->left != nullptr) { root = root->left; }

return root; } template <typename T> TreeNode<T>* findMax(TreeNode<T>* root) { while (root->right != nullptr) { root = root->right; } return root; } Searching: Searching for a value involves traversing the tree based on the key until the value is found or the traversal reaches a null pointer. cpp Copy code template <typename T> TreeNode<T>* search(TreeNode<T>* root, T key) { if (root == nullptr || root->data == key) { return root; } if (key < root->data) { return search(root->left, key); } else { return search(root->right, key); } } Successor: The successor of a node in a BST is the node with the smallest key greater than the key of the given node. cpp Copy code template <typename T> TreeNode<T>* findSuccessor(TreeNode<T>* root, T key) { TreeNode<T>* current = search(root, key); if (current == nullptr) { return nullptr; } if (current->right != nullptr) { return findMin(current->right);

} TreeNode<T>* successor = nullptr; while (root != nullptr) { if (key < root->data) { successor = root; root = root->left; } else if (key > root->data) { root = root->right; } else { break; } } return successor; } Binary Search Trees are powerful data structures that enable efficient searching and retrieval of elements. Proper maintenance of the BST property ensures balanced trees, providing logarithmic time complexity for key operations.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

CS128 QUIZ PREP pt 2

Related Documents