Computer Programming-II (MCT-243L)

Week 02:
Basics of Classes, Objects, Data Structures

Instructor: Dr. Muhammad Usman (Assistant Professor)

Why Object-oriented Programming?
 Procedural Languages
 C, and Fortran are procedural languages
 For very small programs, no organizing principle (or paradigm) is needed

 Functions Division:
 For larger programs
 make programs more comprehensible
 function has:
 a clearly defined purpose and
 a clearly defined interface to the other functions
 Modules
 Grouping a number of functions together into a larger entity called
a module
 Structured Programming:
 Dividing a program into functions and modules is the cornerstones
of structured programming
As programs grow larger and more complex, even the structured
programming approach begins to become excessively complicated.

Main issues with procedural languages?

 First, functions have unrestricted access to global data.
 Second, unrelated functions and data,
 provide a poor model of the real world
 Lack of Attributes and Behaviors modeling
Basic concepts of OOP
Classes and Object:
 Lets begin with an example which demonstrates the syntax
and general features of classes in C++
Code Explanation
 Program contains
 A class
 has One data member and two member functions
 two objects of that class (created in the main function)
 Class definition (or specifier):
 Keyword “class” followed by class name “smallobj”
 Class name capitalization style:
 Pascal case: SmallObj
 Camel case: smallObj
 Class body:
 Pair of left and right braces as {and}
 Terminated with semicolon as ;
Key words
 Access Specifiers
 Public:
 Member function or data member can be called or accessed by other
functions in the program (such as main) and by member functions of
other classes.
 Private:
 Data or functions can only be accessed from within the class.
 Always followed by colon (:)
 Void to the left of a function
 Function will not return any data to its call task
Using the class
 How 𝑚𝑎𝑖𝑛() makes use of it.
 definition of the class does not create any objects.
 It only describes how they will look when they are created
 Defining objects:
 defines two objects, s1 and s2, of class smallobj
 Its like defining a variable of any data type: (Space is set aside for it in
memory)
 Term “instantiating” arises because an instance of the class is created.
 Calling Member functions:
 member function of the class must always be called in connection
with an object of this class
 a period (.) syntax is used to show the association with a specific
object
Standard Template Library
 The STL contains several components.
 The three key components are
 containers, algorithms, and iterators.
Containers: (templatized data structures)
 way that stored data is organized in memory.
 stacks and linked lists, arrays etc
 are implemented by template classes,
 can be customized to store objects of any data type.
Algorithm: (function templates, member functions)
 are procedures that are applied to containers to process their data
in various ways.
 For example, algorithms to sort, copy, search, and merge data.
 are represented by template functions.
 Can be used on containers which are created by yourself
Iterator: (pointers to manipulate container elements)
 Iterators are the generalization of pointers: they point to elements
in a container.
 Cab be incremented just like a pointer, so it points in turn to every
element in a container
 Think of them as a software version of cables
Containers
 Three major categories
 sequence containers,
 represent linear data structures (i.e., all of their elements are
conceptually “lined up in a row”),
 Each element is related to other by its position
 arrays, vectors, lists, deque etc.
 Associative containers,
 Nonlinear data structures (not sequential)
 store sets of values or key–value pairs in which each key has
an associated value. (employee IDs with Employee objects)
 Sets and maps, (stored like a tree structure)
 keys in associative containers are immutable
 Ordered associative containers
 unordered associative containers
 Container adapters
 enable a program to view a sequence container in a constrained
manner.
 Stacks and queues are typically constrained versions of sequence
containers
Vectors
 Vectors are the same as dynamic arrays with the ability to
resize itself automatically when an element is inserted or
deleted, with their storage being handled automatically by
the container.
 Vector elements are placed in contiguous storage so that
they can be accessed and traversed using iterators.
 In vectors, data is inserted at the end. Inserting at the end
takes differential time, as sometimes the array may need to
be extended. Removing the last element takes only constant
time because no resizing happens.
 Inserting and erasing at the beginning or in the middle
is linear in time.
 std::vector in C++ is the class template that contains the
vector container and its member functions.
 It is defined inside the <vector> header file.
 The member functions of std::vector class provide various
functionalities to vector containers.
 Some commonly used member functions are written
below:
 begin() – Returns an iterator pointing to the first element in
the vector
 end() – Returns an iterator pointing to the theoretical
element that follows the last element in the vector
 rbegin() – Returns a reverse iterator pointing to the last
element in the vector (reverse beginning). It moves from last
to first element
 rend() – Returns a reverse iterator pointing to the
theoretical element preceding the first element in the vector
(considered as reverse end)
 cbegin() – Returns a constant iterator pointing to the first
element in the vector.
 cend() – Returns a constant iterator pointing to the
theoretical element that follows the last element in the
vector.
 crbegin() – Returns a constant reverse iterator pointing to
the last element in the vector (reverse beginning). It moves
from last to first element
 crend() – Returns a constant reverse iterator pointing to the
theoretical element preceding the first element in the vector
(considered as reverse end)
Intro to Iterators
 Iterators have many similarities to pointers and used to point
to container elements and for other purposes
 Implemented for each type of container
Member functions begin() and end()
 Function begin returns an iterator pointing to the first element of the
container.
 Function end returns an iterator pointing to the first element past the
end of the container (one past the end)—
 a nonexistent element that’s frequently used to determine when the end of a
container is reached.
Iterator Category Hierarchy
 Containers that support random-access iterators can be used with all
Standard Library algorithms

 Fig. 15.8 Predefined Iterator typedef s

Evaluation Person’s Height Detail
 Make a Class to enter and show the person’s following details
 Name
 Height in feet and inches… e.g. 5’6’’
 Store every person’s detail in a Vector.
 Count the number of Entries
Introduction to Algorithms
 Inserting, deleting, searching, sorting and others are appropriate for
some or all of the sequence and associative containers.
 algorithms operate on container elements only indirectly through
iterators
The find() Algorithm
The count() Algorithm
The sort() Algorithm
The search() Algorithm
The merge() Algorithm
Function Objects
 Some algorithms can take something called a function object
as an argument.
 A function object looks, to the user, much like a template
function. However, it’s actually an object of a template class
that has a single member function: the overloaded ()
operator. This sounds mysterious, but it’s easy to use.
 Suppose you want to sort an array of numbers into
descending instead of ascending order. The
 SORTEMP program shows how to do it:
Week 2 (Lab 4)
Sequence Containers
 Class templates array , vector and deque are typically based on
built-in arrays.

 Vector sequence (Page 1898) Dietel

 743 (Lafore)
 List sequence (Page 1924) Dietel
 747 (Lafore)
 deque sequence (Page 1938) Dietel
 750 (Lafore)
Member Functions push_back(), size(), and operator[]
 Vector Initialization:
 Default (no-argument) constructor used to create a vector v.
 Template format specifies the type of variable the container will
hold (in this case, int).
 The container starts with a size of 0.
 Inserting Elements:
 push_back() member function inserts the value of its argument
at the back of the vector.
 The front of a vector (element with index 0) cannot be used for
inserting new elements.
 Values 10, 11, 12, and 13 pushed, resulting in v[0] as 10, v[1] as
11, v[2] as 12, and v[3] as 13.
 Accessing and Modifying Data:
 Data in a vector can be accessed using the overloaded []
operator, similar to an array.
 The operator is used to change the first element from 10 to 20
and the last element from 13 to 23.
 Output:
 Output from VECTOR: 20 11 12 23
 Size Information:
 size() member function returns the number of elements
currently in the container (4 in VECTOR).
 max_size() member function returns the maximum size to
which a container can be expanded.
 The maximum size depends on the type of data, the container
type, and the operating system.
 Example: max_size() returns 1,073,741,823 for a vector of
type int.
Member Functions swap(), empty(), back(), and pop_back()
 Vector Initialization:
 Two new vector constructors used in the program.
 The first initializes vector v1 with values from a C++ array
passed as an argument.
 Constructor arguments are pointers to the start of the array and
to the element one past the end.
 The second constructor sets vector v2 to an initial size of 4
without supplying initial values.
 Both vectors (v1 and v2) hold type double.
 Swap Operation:
 The swap() member function exchanges all data in one vector
with all data in another while maintaining element order.
 v2 is swapped with data from v1.
 Displaying v2 shows it contains the data originally in v1.
 Output: 4.4, 3.3, 2.2, 1.1
 Back and Pop Operations:
 The back() member function returns the value of the last
element in the vector.
 Displaying the value using cout.
 The pop_back() member function removes the last element in
the vector.
 In each loop iteration, a different last element is removed.
 Member Functions vs. Algorithms:
 Some member functions (e.g., swap()) also exist as algorithms.
 Member function versions are usually provided for efficiency
with specific containers.
 Algorithms can sometimes be used, e.g., for swapping elements
in different container types.
Member Functions insert() and erase()
 Insert Function:
 The insert() member function takes two arguments: the
position where an element will be inserted and the value of the
element.
 Example: insert( begin() + 2, 115 ) inserts the value 115 at the
third position (index 2) in the vector.
 Elements from the insertion point to the end of the container
are shifted upward to make room.
 The size of the container is increased by 1.
 Erase Function:
 The erase() member function removes the element at the
specified location.
 Elements above the deletion point are moved downward.
 The size of the container is decreased by 1.
Lists
 An STL list container is a doubly linked list, in which each
element contains a pointer not only to the next element
but also to the preceding one.
 The container stores the address of both the front (first)
and the back (last) elements, which makes for fast access
to both ends of the list.
Member Functions push_front(),
front(), and pop_front
 List Operations:
 push_front(), pop_front(), and front() are member functions
for lists and are analogous to push_back(), pop_back(), and
back() for vectors.
 They operate on the front (first element) of the list.
 Random Access Limitation:
 Random access is not suitable for list elements due to its slow
performance.
 The [] operator is not defined for lists.
 Random access is more efficient with vectors or deques.
 List Efficiency:
 Lists are suitable when frequent insertions and deletions occur
in the middle of the list.
 Efficient for insertions and deletions because only a few
pointers need to be changed, unlike vectors or deques where
elements above the insertion or deletion point must be moved.
 Insertion and Deletion:
 insert() and erase() member functions are used for list insertion
and deletion.
 They require the use of iterators.
 Considerations:
 Lists are appropriate for scenarios where efficient insertion and
deletion operations are crucial, even though finding the correct
insertion point may still be time-consuming.
Member Functions reverse(), merge(), and unique()
 List Reversal:
 The reverse() member function is used to reverse the order of
elements in a list.
 It's quick to reverse a list since both ends are accessible.
 Merging Two Sorted Lists:
 The merge() member function is applied to merge two lists.
 Both lists must be in sorted order for the merge to work
properly.
 Unique Elements:
 The unique() member function is applied to remove adjacent
elements with the same value.
 It keeps only the first occurrence of each unique element.
 .
 Displaying List Contents:
 front() and pop_front() member functions are used in a loop to
display elements from front to back.
 Displaying and popping elements in a loop effectively destroys
the list.
Deques
 Deque Overview:
 A deque (double-ended queue) shares similarities with both
vectors and linked lists.
 Supports random access using the [] operator, similar to
vectors.
 Allows access at both the front and the back, supporting
operations like push_front(), pop_front(), and front().
 Memory Allocation:
 Vectors always occupy a contiguous region of memory.
 If a vector grows too large, it may need to be moved to a new
location where it can fit.
 Deques, on the other hand, can be stored in several non-
contiguous areas; they are segmented.
 The capacity() member function returns the largest number of
elements a vector can store without being moved. However,
capacity() isn't defined for deques because they don't need to be
moved.
Iterators
 Iterators may seem a bit mysterious, yet they are central to
the operation of the STL.
 In this section we’ll first discuss the twin roles played by
iterators: as smart pointers and as a connection between
algorithms and containers.
 Then we’ll show some examples of their use.
Iterator as Smart Pointers
 Iteration over Elements:
 Performing operations on all elements in a container or a range
of elements is a common task.
 In an ordinary C++ array, such operations are typically
performed using a pointer or the [] operator.
 Example with Float Array:
 The provided code snippet demonstrates iterating through a
float array.
 float* ptr = start_address; //Initializes a pointer ptr to the
start address of the array.
 The for loop iterates through the array:
 cout << *ptr++; // Dereferences the pointer ptr to obtain the
value of the current element and increments the pointer to
point to the next item.
Data Access
Data Insertion
Algorithms and Iterators
Week 3 (Lab 5)
Assignment
 Application of LISTs
Associative Containers
 Associative Containers Overview:
 Not Linear: Unlike sequence containers (vector, list, deque),
items aren't in a fixed linear sequence.
 Fast Search: Arranged (often in tree structures or hash tables)
for quicker item searches.
 Search Method: Uses keys (like numbers or strings) for
searching.
 Types of Associative Containers:
 Sets: Store objects with keys.
 Maps: Store pairs - a key object and a value object.
 Uniqueness: Both sets and maps store unique keys - no
duplicates allowed.
 Multiset and Multimap: Variants that allow multiple instances of
the same key.
 Characteristics and Functions:
 Shared Functions: Have many common member functions with
other containers.
 Unique Algorithms: Some algorithms, like lower_bound() and
equal_range(), are specific to associative containers.
 Absence of Push/Pop Functions: Functions like push_back()
don't apply, as insertion is order-specific, not at the start/end.
 lower_bound() Function:
 Purpose: Finds the first element in a sorted range that is not
considered to go before a specified value.
 Working: It searches the container for the first element that is
greater than or equal to the given key.
 Use with Associative Containers: In associative containers like
sets or maps, which are typically sorted, lower_bound()
provides an efficient way to find the starting point for a certain
range or a specific key.
 Example: If you have a sorted set of integers {1, 3, 5, 7} and
you call lower_bound(4), it will return an iterator to 5, as 5 is
the first element not less than 4.
 equal_range() Function:
 Purpose: Provides a way to find both the lower and upper
bounds of a particular key in a single operation.
 Working: It returns a pair of iterators. The first iterator points
to the first element that is not less than the key, and the second
iterator points to the first element greater than the key.
 Use with Associative Containers: In sorted associative
containers, equal_range() is highly useful for finding the range
of elements that match a specific key, especially in multisets or
multimaps where a key can have multiple entries.
 Example: In a multiset {1, 3, 3, 5, 7}, calling equal_range(3)
would return a pair of iterators. The first would point to the
first 3 and the second would point to 5, effectively enclosing the
range of elements with the key 3.
Associative Containers
 Items are not arranged in a sequence but in a more complex structure,
often a tree (or hash table).
 Searching is faster due to the chosen arrangement.
 Keys are used for searching, usually a single value (number or string),
either an attribute or the entire object.

 Categories in STL:
 Sets: Store objects with keys; only one instance of each key is allowed.
 Maps: Store pairs where the first part is an object containing a key, and the
second part is an object containing a value.
 Multisets and Multimaps: Relax the restriction of allowing only one instance
of each key.
Difference: unordered ones do not maintain their keys in sorted order.
Sets and Multisets
Maps & Multimaps
 Stores pairs.
 A pair consists of a key object and a value object.
 The key object contains the key to be searched for.
 The value object contains additional data associated with the key.
 Keys can be strings, numbers, or objects of complex classes.
 Values can be strings, numbers, objects, or even containers.
 Example applications include:
 A frequency table where the key is a word and the value is the
frequency of that word in a document.
 An index where the key is a word, and the value is a list of page
numbers.
 An ordinary dictionary where keys are words, and values are their
definitions.
An Associative Array
Task
 Make a map data structure with following requirements:
Elements of the pair
 Key  Student registration
 Object structure of (1) Name, (2) Session (3) CGPA)
Week 3 (Lab 6)
 Container Adapters
 Special-purpose containers from the normal containers mentioned
previously using a construct called container adapters.
 The specialized containers implemented with container adapters
in the STL are stacks, queues, and priority queues.
 a stack restricts access to pushing and popping a data item on and off the top of
the stack.
 In a queue, you push items at one end and pop them off the other.
 In a priority queue, you push data in the front in random order, but when you pop
the data off the other end, you always pop the largest item stored: the priority
queue automatically sorts the data or you
 Stacks
 Stack Class:
 Defined in header <stack>.
 Enables insertions and deletions at one end, called the top.
 Known as a last-in, first-out (LIFO) data structure.
 Function-Call Stack:
 Introduced in the context of function-call stacks in Section 6.11.
 Underlying Data Structures:
 Can be implemented using vector, list, or deque.
 By default, implemented with a deque.
 Stack Operations:
 push: Inserts an element at the top of the stack. Uses push_back
of the underlying container.
 pop: Removes the top element of the stack. Uses pop_back of
the underlying container.
 top: Gets a reference to the top element. Uses back of the
underlying container.
 empty: Checks if the stack is empty. Uses empty of the
underlying container.
 size: Returns the number of elements in the stack. Uses size of
the underlying container.
Queue
 Queue Class:
 Defined in header <queue>.
 Operates as a first-in, first-out (FIFO) data structure.
 Underlying Data Structures:
 Can use the Standard Library’s list or deque containers.
 By default, implemented with a deque
 Queue Operations:
 push: Inserts an element at the back of the queue. Uses
push_back of the underlying container.
 pop: Removes the element at the front of the queue. Uses
pop_front of the underlying container.
 front: Gets a reference to the first element in the queue. Uses
front of the underlying container.
 back: Gets a reference to the last element in the queue. Uses
back of the underlying container.
 empty: Checks if the queue is empty. Calls empty on the
underlying container.
 size: Returns the number of elements in the queue. Calls size on
the underlying container.
Priority Queues
 Priority Queue Class:
 Defined in header <queue>.
 Default Underlying Data Structure:
 Elements are stored in a vector.
 Behavior and Ordering:
 Inserts elements in sorted priority order.
 The highest-priority element (largest value) is at the front.
 Heap Structure:
 Elements arranged in a heap to maintain highest-priority
element at the front.
 Default Comparator:
 Uses less<T> for comparing elements, but can be customized.
 Priority Queue Operations:
 push: Inserts an element in priority order, then reorders
elements.
 pop: Removes the highest-priority element.
 top: Gets a reference to the top element (using front of the
underlying container).
 empty: Determines if the queue is empty (using empty of the
underlying container).
 size: Gets the number of elements (using size of the underlying
container).
Week4
Data Structures: Arrays & Vectors
 Data structures:
 Collections of related data items
 Arrays:
 Fixed-size collections of data items of same type (int, float)
 To use C++ STL template <array> header is included
 Vectors:
 Collections that can grow and shrink dynamically at execution
time.
 To use C++ STL template <vector> header is included
Arrays:
 The data items can be simple types such as int or float, or
 Can be user-defined types such as structures and objects.
 To refer to a particular location in the array,
 Name of array and the position number (in square bracket) is
specified E.g. age[1], age[2]
 Position number is called subscript or index
 Pronounced as “age sub one”
 Subscript must be an integer or integer expression
Declaring arrays
 Specify type of the elements and the number of elements
required
 Notation:
 array <type, arraySize> arrayName;
 array <int, 12> age;
 It indicates that array is a class template.
 Declaration reserves memory
 arraySize must be an unsigned integer
Examples using Arrays
 Declare, initialize, and manipulate
 Declaring array and initializing using a loop
 Initializing in a declaration with an initializer list

Note: If an initializer list is specified in an array

declaration, the number of initializers must be less
than or equal to the array size.
Sorting and Searching Arrays
 Sorting:
 placing data into ascending or descending order
 One of the most important computing applications.
 Examples:
 A bank sorts all checks by account number so that it can prepare individual bank
statements at the end of each month.
 Telephone companies sort their phone directories by last name and within all entries
with the same last name, sort those by first name to make it easy to find phone
numbers.

 Notation:
 C++ library function “Sort”

 Searching:
 The process of finding a particular element of an array is called
searching.
 Notation:
 C++ library function “binary_search”
Example
Multidimensional Array
 tables of values consisting of information arranged in rows and
 columns
 Example
 Range based for loop
 for (auto const& row : a)
 Explanation page (948, 340)

 auto keyword
 Infer variable’s data type based on
variable’s initializer value

 Another way:
total = 0;
for (auto row : a) { // for each row
for (auto column : row) { // for
each column in row
total += column;
}
}
Function Overloading
 C++ enables several functions of the same name to be
defined, as-long-as they have different signatures. This is
called function overloading
 Function overloading is used to create several functions of the
same name that perform similar tasks, but on different data
types.
 For example, many functions in the math library are
overloaded for different numeric types
 float , double and long double
Example
How compiler Differentiates
 Overloaded functions are distinguished by their signatures.
 A signature is a combination of a function’s name and its
parameter types (in order).
Custom Templates
 Function templates enable you to conveniently specify a
variety of overloaded functions—called function-
template specializations.
 Class templates enable you to conveniently specify a variety
of related classes—called class-template specializations.
 Programming with templates is also known as generic
programming.
Custom Templates
 Let's understand it using the concept of a stack independent
of the type of the items being placed in the stack
 To instantiate a stack, a data type must be specified
 Here, we define a stack generically then use type-specific
versions of this generic stack class
 One Stack class template, could become the basis for creating
many Stack class template specializations (such as “ Stack of double
s,” “ Stack of int s,” “ Stack of Employee s,” “ Stack of Bill s,” “ Stack of Activation
Record s,” etc.) used in a program.
Class Template Stack<T>
 The Stack class-template definition looks like a conventional
class definition, with a few key differences. First, it’s
preceded by
 template<typename T>
 keyword template
 followed by list of parameters in angle brackets (< and >);
 interchangeable keywords typename or class
 T acts as a placeholder for the Stack ’s element type.
`
Class Template Stack<T> ’s
Data Representation
 A stack requires insertions and deletions only at its
top
 a vector or a deque could be used to store the
stack ’s elements
 A deque supports fast insertions and deletions at its
front and its back.
 A deque is default representation for the Standard
Library’s stack adapter because a deque grows
more efficiently than a vector
Member functions of Class
 top (lines 11–13) returns a const reference to the Stack ’s
top element.
 push (lines 16–18) places a new element on the top of the
Stack .
 pop (lines 21–23) removes the Stack ’s top element.
 isEmpty (lines 26–28) returns a bool value— true if the
Stack is empty and false otherwise.
 size (lines 31–33) returns the number if elements in the Stack
.
Testing Class Template Stack<T>
Function Template to Manipulate a Class-
Template Specialization Object
 Function template testStack (lines 10–36) to perform the
same tasks as main in Fig. 18.3
Basic concepts of OOP
Classes and Object: (a review)
 Lets begin with an example which demonstrates the syntax
and general features of classes in C++
Code Explanation
 Program contains
 A class
 has One data member and two member functions
 two objects of that class (created in the main function)
 Class definition (or specifier):
 Keyword “class” followed by class name “smallobj”
 Class name capitalization style:
 Pascal case: SmallObj
 Camel case: smallObj
 Class body:
 Pair of left and right braces as {and}
 Terminated with semicolon as ;
Key words
 Access Specifiers
 Public:
 Member function or data member can be called or accessed by other
functions in the program (such as main) and by member functions of
other classes.
 Private:
 Data or functions can only be accessed from within the class.
 Always followed by colon (:)
 Void to the left of a function
 Function will not return any data to its call task
Main Idea in OOP
 Placing data and functions together into a single entity is a
central idea in object-oriented programming.
Private and Public
 Two unfamiliar keywords: private and
public
 A key feature of OOP:
 data hiding:
 data is concealed within a class so that it cannot
be accessed mistakenly by functions outside the
class
 Private:
 data or functions can only be accessed from
within the class
 Public:
 data or functions, on the other hand, are
accessible from outside the class

Usually, the data is private and functions are public.

Class Data & Member Functions
Data Member:
 Data items within a class are called data members (or
sometimes member data).
 Can be any number of data members in a class, as in a
structure.
Member Functions (Methods)
 Functions that are included within a class
 perform operations: setting and retrieving the data stored in
the class.
Using the class
 How 𝑚𝑎𝑖𝑛() makes use of it.
 definition of the class does not create any objects.
 It only describes how they will look when they are created
(same as structure definition)
 Defining objects: (creating objects)
 defines two objects, s1 and s2, of class smallobj
 like defining a variable of any data type: (Space is set aside for it in
memory)
 Term “instantiating” arises because an instance of the class is created.
 Calling Member functions:
 member function of the class must always be called in connection
with an object of this class
 a period (.) syntax is used to show the association with a specific
object
Objects as Physical Objects
 objects in programs represent physical objects: things that
can be felt or seen
 Examples: correspondence between program and real world.
Widget Parts as Objects
 Three data member: modelnumber, partnumber, and cost.
 A single member function, setpart(), supplies values to all
three data items at once.
 Another function, showpart(), displays the values stored in all
three items.
Circles as Objects
Constructors
 An object can initialize itself when it’s first created, without
requiring a separate call to a member function.
 Automatic initialization is carried out using a special member
function called a constructor.
 It is executed automatically whenever an object is created
A counter Example:
 A counter is a variable that counts things
 counts file accesses,
 or the number of times the user presses the Enter key,
 or the number of customers entering a bank.
Automatic Initialization
 When an object of type Counter is first created, we want its
count to be initialized to 0.
 could provide a 𝑠𝑒𝑡_𝑐𝑜𝑢𝑛𝑡() function to do this and call it
with an argument of 0, or zero_count()
 such functions would need to be executed every time we
created a Counter object
 Counter c1; //every time we do this,
 c1.zero_count(); //we must do this too
 We may forget to initialize the object after creating it.
 In the Counter class, the constructor Counter() does this.
 This function is called automatically whenever a new object of
type Counter is created
Aspects of constructor functions
How compiler knows about constructor function?
 Exactly the same name (Counter in this example) as the
class of which they are members.
 No return type is used for constructors. Since the
constructor is called automatically by the system and no
program for it to return anything to.
Initializer List
 Most common tasks a constructor carries out is initializing
data members
 Initialize the count member to 0 as
 count() : count(0)
 {}

 The initialization takes place as:

 following the member function declarator but before the
function body
 Preceded by a colon
 value is placed in parentheses following the member data
 Initializer list are given a value before the constructor even
starts to execute.
Graphics Example
 Use of constructor instead of a set() function
Destructors
 Another function is called automatically when an object is
destroyed. Such a function is called a destructor
 same name as the constructor (which is the same as the class
name) but is preceded by a tilde:

 Destructors do not have a return value

 Use of destructors is to deallocate memory that was allocated
for the object by the constructor.
Objects as Function Arguments
Result:
 This program starts with a distance dist2 set to an initial
value and adds to it a distance dist1, whose value is supplied
by the user, to obtain the sum of the distances. It then
displays all three distances:
 𝐸𝑛𝑡𝑒𝑟 𝑓𝑒𝑒𝑡: 17
 𝐸𝑛𝑡𝑒𝑟 𝑖𝑛𝑐ℎ𝑒𝑠: 5.75
 𝑑𝑖𝑠𝑡1 = 17’ − 5.75”
 𝑑𝑖𝑠𝑡2 = 11’ − 6.25”
 𝑑𝑖𝑠𝑡3 = 29’ − 0”
Overloaded Constructors
 Give variables of type Distance a value when they are first
created.
 Distance width(5, 6.25);
 constructor will be like this:
 Distance(int ft, float in) : feet(ft), inches(in)
 {}

 Define variables of type Distance with default values:

 Distance dist1, dist2;
 Distance() : feet(0), inches(0.0) //default constructor
 { } //no function body, doesn’t do anything

 Two explicit constructors with the same name, Distance(),

so the constructor is overloaded.
Member Functions Defined Outside the Class

 add_dist(), that is not defined within the Distance class

definition. It is only declared inside the class, with the
statement
 void add_dist( Distance, Distance );
 Definition:

 Double colon (::). This symbol is called the scope

resolution operator.
Objects as Arguments
 The function call in main()
 dist3.add_dist(dist1, dist2);
Structures and Classes
 only formal difference between class and struct is that
 in a class the members are private by default,
 in a structure members are public by default.
Keyword “const” and Classes
 const Member Functions
 it will never modify any of its class’s member data.
 Placing the keyword const after the declarator

 Member functions that do nothing but acquire data from an object

 Const objects
 If object is declared as const,
can’t be modified.
 Therefore, only const member
functions guarantee not to
modify it
Week 5
 Computer Programming-II
OOP-Inheritance

Instructor:
Muhammad Usman
Objectives
 Introduction
 Base and derived classes
 Relationship between base & derived classes
 Constructor & destructors in derived classes
 Public, protected & private inheritance
Introduction
 Inheritance is an essential part of OOP.
 Big payoff  permits code reusability.
 Once base class is written, it need not be touched again
 Reusing existing code saves time and money
 existing class  base class, new class  derived class
 derived class inherits members of base class
 C++ offers public, protected and private inheritance
 Public inheritance:
 every object of a derived class is also an object of that derived
class’s base class
 For example: base class vehicle and car as derived class
 All cars are vehicle and but not all vehicles are cars
Is-a-relationship / has-a-relationship
 Is-a-relationship:
 an object of a derived class also can be treated as an object of its
base class
 for example, a Car is a Vehicle , so any attributes and behaviors
of a Vehicle are also attributes and behaviors of a Car
 Has-a-relationship:
 an object contains one or more objects of other classes as
members
 For example, a Car has many components—it has a steering
wheel, has a brake pedal, has a transmission, etc
Specifying the Derived Class

 The first line of CountDn specifies that it is derived from

Counter:
 class CountDn : public Counter (is-a-relationship)
Accessing Base Class
 When a member function in the base class can be used by
objects of the derived class. This is called accessibility
Base Class Constructors:
 if we don’t specify a constructor, the derived class will use an
appropriate constructor from the base class.
 Compiler uses the no-argument constructor from Count
Base Class Member Functions
 the compiler, not finding the functions in the derived class, it
uses member functions from the base class
Protected Access Specifier
 member functions can access members of the base class if the
members are public, or if they are protected. They can’t
access private members.
 We avoid to make it public cuz it will be accessed by any
other
 A protected member, can be accessed by member functions
in its own class or in any class derived from its own class.
Access specifier with inheritance
Derived Class constructors
 Two new constructors in the derived class
 no-argument constructor:
 CountDn() : Counter()
 {}
In main(), object is created as
 CountDn c1;
 one-argument constructor
 CountDn(int c) : Counter(c)
 {}
In main()
 CountDn c2(100);
Example
Line Following Robot Class
 Two infrared sensors
 Bool  Left Sensor
 Bool  Right Sensor
 Two Motors
 Int  Motor Speed Left
 Int  Motor Speed Right
Code Line following Robot
 Computer Programming-II
Week 7

Instructor:
Muhammad Usman
Public and Private Inheritance
 With declarations like
 class manager : public employee
 The keyword public specifies that objects of the derived
class are able to access public member functions of the base
class.
 When keyword private is used, objects of the derived
class cannot access public member functions of the base class.
So no member of the base class is accessible to objects of the
derived class
When to use?
 Sometimes, the derived class is created as a way of
completely modifying the operation of the base class, hiding
or disguising its original interface.
 You might derive Stack from Array, but you wouldn’t want
the users of Stack objects to treat them as if they were arrays,
using the [] operator to access data items, for example.
Objects of Stack should always be treated as if they were
stacks, using push() and pop().
Multiple Inheritance
 A class can be derived from more than one base class.
Abstraction in C++
 Abstraction means displaying only essential information and
hiding the details.
 Data abstraction refers to providing only essential
information about the data to the outside world, hiding the
background details or implementation.
 Abstraction using Classes:
 Class helps us to group data members and member functions
using available access specifiers
 Members declared as public in a class, can be accessed from
anywhere in the program.
 Members declared as private in a class, can be accessed only
from within the class.
 Abstraction in Header files:
 One more type of abstraction in C++ can be header files
 For example, consider the pow() method present in math.h
header file.
Encapsulation in C++
 Encapsulation is a process of combining data members and
functions in a single unit called class.
 This is to prevent the access to the data directly, the access to
them is provided through the functions of the class.
 It is one of the popular feature of Object-Oriented
Programming(OOPs) that helps in data hiding.
Week 6
 Computer Programming-II
(1: Linked Lists, Trees, Graphs)

(Custom templatized data structures)

Chapter 19 (Dietel)

Instructor:
Muhammad Usman
Self-Referential Classes (Ch 19)
 A self-referential class objects contains a member that points to a class object of the
same class type.

 it can be linked together to form useful data structures such as linked lists and trees.
 Member nextPtr is referred to as a link—i.e.,
 nextPtr can “tie” an object of type Node to another object of the same type
 Member functions
 A constructor that receives an integer to initialize member data
 A setData function to set the value of member data
 A getData function to return the value of member data ,
 A setNextPtr function to set the value of member nextPtr
 A getNextPtr function to return the value of member nextPtr

 A slash—representing a null pointer (nullptr)

Linked Lists
 Sequence of nodes
 Contains data fields and reference node (points to the next
node)
 Insertion and removal of nodes at any point in the list but
doesn’t allow random access
 Any node can be accessed only by starting from first node
sequentially
 link pointer in the last node of a list is set to nullptr to
mark the end of the list
Type of Linked Lists
 Singly-linked lists
 Doubly-linked lists
 Circulatory-linked lists
Singly-linked List
 Each node is linked to the next node in the list
 Each node contains data fields and reference field
 Insertion and removal of nodes at any point in the list but not
random access
 Accessed only starting from the first node sequentially
Class singly linked list
 // Class Node, similar to the linked list
 class Node{
 int value;
 // Points to the next node.
 Node* next;
 }
 void insertNode(int data)
// C++ program for the above approach {
#include <iostream> // Create the new Node.
usingnamespacestd; Node* newNode = new Node(data);

// Assign to head
// Node class to represent if (head == NULL) {
// a node of the linked list. head = newNode;
classNode { return;
public: }
intdata;
Node* next; // Traverse till end of list
Node* temp = head;
while (temp->next != NULL) {
// Default constructor
Node() // Update temp
{ temp = temp->next;
data = 0; }
next = NULL;
} // Insert at the last.
temp->next = newNode;
}
// Parameterised Constructor
Node(intdata) // Function to print the
{ // nodes of the linked list.
this->data = data; void printList()
this->next = NULL; {
} Node* temp = head;
};
// Check for empty list.
if (head == NULL) {
// Linked list class to cout << "List empty" << endl;
// implement a linked list. return;
classLinkedlist { }
Node* head;
// Traverse the list.
while (temp != NULL) {
public:
cout << temp->data << " ";
// Default constructor temp = temp->next;
Linkedlist() { head = NULL; } }
}
};
int main()
{
Linkedlist list;

// Inserting nodes
list.insertNode(1);
list.insertNode(2);
list.insertNode(3);
list.insertNode(4);

cout << "Elements of the list are: ";

// Print the list

list.printList();
cout << endl;
}
Doubly Linked Lists
// Node of a doubly linked list
 class Node {
 public:
 int data;
 // Pointer to next node in DLL
 Node* next;
 // Pointer to previous node in DLL
 Node* prev;
 };
Circular Linked List
 Singly Circular

 Doubly Circular
Trees
 A tree is a nonlinear, two-dimensional data structure.
 Tree nodes contain two or more links.
 Binary trees: trees whose nodes all contain two links (none, one or
both of which may have the value nullptr).
Basic Terminology
 The root node (node B ) is the first node in a tree.
 Each link in the root node refers to a child (nodes A and D ).
 The left child (node A ) is the root node of the left subtree (which contains only node
A ), and the right child (node D ) is the root node of the right subtree (which
contains nodes D and C ).
 The children of a given node are called siblings (e.g., nodes A and D are siblings). A
node with no children is a leaf node (e.g., nodes A and C are leaf nodes).
Binary Search Trees
 Binary search tree
 values in left subtree are less than value in its parent node
 values in right subtree are greater than value in its parent node.
 Tree Traversals (Inorder, Preorder and Postorder)
 Unlike linear data structures (Array, Linked List, Queues,
Stacks, etc) which have only one logical way to traverse
them, trees can be traversed in different ways.

 Depth First Traversals:

 Inorder (Left, Root, Right) : 4 2 5 1 3
 Preorder (Root, Left, Right) : 1 2 4 5 3
 Postorder (Left, Right, Root) : 4 5 2 3 1
 Breadth-First or Level Order Traversal: 1 2 3 4 5
Testing Tree
 binary search tree traverses (i.e., walks through all its nodes)
three ways—
 using recursive inorder, preorder and postorder traversals.
 driver program:
 Visual Studio Project (Tree)