UNIT-I

C++ programming language was developed in 1980 by Bjarne Stroustrup

at bell laboratories of AT&T (American Telephone & Telegraph), located in
U.S.A.
Bjarne Stroustrup is known as the founder of C++ language
It was develop for adding a feature of OOP (Object Oriented
Programming) in C without significantly changing the C com C++
programming is "relative" (called a superset) of C, it means any valid C
program is also a valid C++ program ponent

Input and output in C++

The standard C++ library is iostream and standard input / output functions in
C++ are: 1.cin
2.cout
cin
It is the method to take input any variable / character / string. Syntax:
cin>>variable / character / String / ;

Cout
This method is used to print variable / string / character. Syntax:
cout<< variable / charcter / string;

program to add two numbers

#include <iostream.h> #include<conio.h> Void main()

{
int a,b,c;
cout<<”enter values for a and b”; cin>>a>>b;
c=a+b;
cout<<”the total is:<<c;
}

Functions in C++
A function is a block of code that performs a specific task. It has a name and
it is reusable i.e. it can be executed from as many different parts as required.
It also optionally returns a value to the calling function.
A complex problem may be decomposed into a small or easily manageable
parts or modules called functions. Functions are very useful to read, write,
debug and modify complex programs They can also be incorporated in the
main program. The main() itself is a function is invoking the other functions to
perfom various tasks.

return_type function_name(argument_list)
{ statement 1;
.
.
statements n; [return value];
}

In call by value, value being passed to the function is locally stored by the
function parameter in stack memory location. If you change the value of
function parameter, it is changed for the current function only. It will not
change the value of variable inside the caller method such as main(

#include <iostream> using namespace std; void change(int data); int main()
{
int data = 3; change(data);
cout << "Value of the data is: " << data<< endl; return 0;
}
void change(int data)
{
data = 5;
}

Call BY REFERENCE
In call by reference, original value is modified because we pass reference
(address).
Here, address of the value is passed in the function, so actual and formal
arguments share the same address space. Hence, value changed inside the
function, is reflected inside as well as outside the function.

#include<iostream> using namespace std; void swap(int *x, int *y)

{
int swap; swap=*x;
*x=*y;
*y=swap;
}
int main()
{
int x=500, y=100;
swap(&x, &y); // passing value to function cout<<"Value of x is:
"<<x<<endl; cout<<"Value of y is: "<<y<<endl;
return 0;
}

Function Overloading
In C++, it is possible to make more than one function with same name, this
concept is known as function overloading. We can use same function name
for different purpose with different number and types of arguments.
In function overloading function names will be same but Types of arguments,
Order of arguments, Number of arguments must be different.
 The C++ compiler selects the proper function by examining the number,
types and order of the arguments in the call. Function overloading is
commonly used to create several functions of the same name that perform
similar tasks but on different data types.

Following advantages to use function overloading in your program:

Eliminating the use of different function names for the same operations.
Helps to understand, debug and group easily.
Easy maintainability of the code.
Better understandability of the relationship b/w the program and the outside
world.

#include <iostream> using namespace std; class Cal {

public:
static int add(int a,int b){ return a + b;
}
static int add(int a, int b, int c)
{
return a + b + c;
}
};
int main(void) {
Cal C; // class object declaration. cout<<C.add(10, 20)<<endl;
cout<<C.add(12, 20, 23);
return 0;
}

Function Templates
In C++, function templates are functions that serve as a pattern for
creating other similar functions. The basic idea behind function templates is
to create a function without having to specify the exact type(s) of some or all
of the variables. Instead, we define the function using placeholder types,
called template type parameters. Once we have created a function using
these placeholder types, we have effectively created a “function stencil”.

include <iostream> template <typename T>

Const T& max (const T& x, const T& y)
{
return (x > y) ? x : y;
}

int main()
{
int i = max(3, 7); // returns 7 std::cout << i << '\n';

double d = max(6.34, 18.523); // returns 18.523

 std::cout << d << '\n';

char ch = max('a', '6'); // returns 'a' std::cout << ch << '\n';

return 0;
}

C++ Arrays
Like other programming languages, array in C++ is a group of similar types
of elements that have contiguous memory location.
C++ Array Types
There are 2 types of arrays in C++ programming:
Single Dimensional Array
Multidimensional Array

#include <iostream> using namespace std; int main()

{
int arr[5]={10, 0, 20, 0, 30}; //creating and initializing array
//traversing array
for (int i = 0; i < 5; i++)
{
cout<<arr[i]<<"\n";
}
}

C++ Pointers
The pointer in C++ language is a variable, it is also known as locator or

indicator that points to an address of a value.

Advantage of pointer
Pointer reduces the code and improves the performance, it is used to retrieving
strings, trees etc. and used with arrays, structures and functions.
We can return multiple values from function using pointer.
It makes you able to access any memory location in the computer's memory.
Usage of pointer
There are many usage of pointers in C++ language.
Dynamic memory allocation
In c language, we can dynamically allocate memory using malloc() and
calloc() functions where pointer is used.
Arrays, Functions and Structures

Pointers in c language are widely used in arrays, functions and structures. It

reduces the code and improves the performance.
 #include <iostream> using namespace std; int main()
{
int number=30; int ∗ p;
p=&number;//stores the address of number variable cout<<"Address of
number variable is:"<<&number<<endl; cout<<"Address of p variable
is:"<<p<<endl; cout<<"Value of p variable is:"<<*p<<endl;
return 0;
}

new and delete Operators

new is used to allocate memory for a variable, object, array, array of objects..
etc at run time. "To declaring memory at run time is known as dynamic
memory allocation." we use memory by this method (dynamic allocation)
when it is not known in advance how much memory space is needed.
since "these operators manipulate memory on the free store, so they are also
known as free store operators. the new operator can be used to create
objects of any type, it takes the following general form:
pointer_variable = new data_type;

delete Operator :
delete operator is used to Deallocates the dynamically allocated memory.

Since the necessity of dynamic memory is usually limited to specific

moments within a program, once it is no longer needed it should be freed so
that the memory becomes available again for other requests of dynamic
memory. This is the purpose of the operator delete.
delete takes the following general form:
delete pointer_variable;
delete []pointer_variable;
#include<iostream.h> #include<conio.h>

void main()
{

int size,i; int *ptr;

cout<<"\n\tEnter size of Array : "; cin>>size;

ptr = new int[size];

for(i=0;i<5;i++) //Input arrray from user.

{
 cout<<"\nEnter any number : "; cin>>ptr[i];
}

for(i=0;i<5;i++) //Output arrray to console.

cout<<ptr[i]<<", ";

delete[] ptr;
//deallocating all the memory created by new operator

C++ Exception Handling

Exception Handling in C++ is a process to handle runtime errors. We perform
exception handling so the normal flow of the application can be maintained
even after runtime errors.

In C++, exception is an event or object which is thrown at runtime. All

exceptions are derived from std::exception class. It is a runtime error which
can be handled. If we don't handle the exception, it prints exception message
and terminates the program.
C++ Exception Handling Keywords
In C++, we use 3 keywords to perform exception handling:
try
catch, and
throw
The C++ try block is used to place the code that may occur exception. The
catch block is used to handle the exception.

#include <iostream> using namespace std;

float division(int x, int y) { if( y == 0 ) {
throw "Attempted to divide by zero!";
}
return (x/y);
}
int main () { int i = 25; int j = 0; float k = 0; try {
k = division(i, j); cout << k << endl;
}catch (const char* e) { cerr << e << endl;
}
return 0;
}
C++ Object and Class
Since C++ is an object-oriented language, program is designed using objects
and classes in C++.
C++ Object
In C++, Object is a real world entity, for example, chair, car, pen, mobile,
laptop etc.
In other words, object is an entity that has state and behavior. Here, state
means data and behavior means functionality.
Object is a runtime entity, it is created at runtime.

Object is an instance of a class. All the members of the class can be accessed
through object. Student s1; //creating an object of Student
C++ Class
In C++, object is a group of similar objects. It is a template from which
objects are created. It can have fields, methods, constructors etc.

#include <iostream> using namespace std; class Student {

public:
int id;//data member (also instance variable) string name;//data
member(also instance variable) void insert(int i, string n)
{
id = i; name = n;
}
void display()
{
cout<<id<<" "<<name<<endl;
}
};
int main(void) {
Student s1; //creating an object of Student Student s2; //creating an object of
Student s1.insert(201, "Sonoo");
s2.insert(202, "Nakul"); s1.display();
s2.display(); return 0;
}
Access specifiers (public, protected, private) in C++
C++ provides three access specifiers: public, protected and private
public
Data members or Member functions which are declared as public can be
accessed anywhere in the program (within the same class, or outside of the
class).
protected
Data members or Member functions which are declared as protected can be
accessed in the derived class or within the same class.
private
Data members of Member functions which are declared as private can be
accessed within the same class only i.e. the private Data members or
Member functions can be accessed within the public member functions of the
same class.

C++ Friend function

If a function is defined as a friend function in C++, then the protected and
private data of a class can be accessed using the function.
By using the keyword friend compiler knows the given function is a friend
function.
For accessing the data, the declaration of a friend function should be done
inside the body of a class starting with the keyword friend.

Declaration of friend function in C++

class class_name
{
friend data_type function_name(argument/s); // syntax of friend function.
};

#include <iostream> using namespace std; class Box

{
private:
int length; public:
Box(): length(0) { }
friend int printLength(Box); //friend function
};
int printLength(Box b)
{
b.length += 10; return b.length;
}
int main()
{
Box b;
 cout<<"Length of box: "<< printLength(b)<<endl; return 0;
}

C++ Constructor

In C++, constructor is a special method which is invoked automatically at the

time of object creation. It is used to initialize the data members of new
object generally. The constructor in C++ has the same name as class or
structure.

There can be two types of constructors in C++.

Default constructor
Parameterized constructor
Copy Constructor
C++ Default Constructor
A constructor which has no argument is known as default constructor. It is
invoked at the time of creating object.

C++ Parameterized Constructor

A constructor which has parameters is called parameterized constructor. It is
used to provide different values to distinct objects.

C++ Copy Constructor

A Copy constructor is an overloaded constructor used to declare and
initialize an object from another object.

#include <iostream> using namespace std; class A

{
public:
int x;
A(int a) // parameterized constructor.
{
x=a;
}
A(A &i) // copy constructor
{
x = i.x;
}
};
int main()
{
A a1(20); // Calling the parameterized constructor. A a2(a1); // Calling the
copy constructor. cout<<a2.x;
return 0;
}

C++ Destructor
A destructor works opposite to constructor; it destructs the objects of classes.
It can be defined only once in a class. Like constructors, it is invoked
automatically.
A destructor is defined like constructor. It must have same name as class. But
it is prefixed with a tilde sign (~).

#include <iostream> using namespace std; class Employee

{
public:
Employee()
{
cout<<"Constructor Invoked"<<endl;
}
~Employee()
{
 cout<<"Destructor Invoked"<<endl;
}
};
int main(void)
{
Employee e1; //creating an object of Employee Employee e2; //creating an
object of Employee return 0;
}

C++ Operators Overloading

Operator overloading is a compile-time polymorphism in which the operator
is overloaded to provide the special meaning to the user-defined data type.
Operator overloading is used to overload or redefines most of the operators
available in C++. It is used to perform the operation on the user-defined data
type. For example, C++ provides the ability to add the variables of the
user-defined data type that is applied to the built-in data types.
The advantage of Operators overloading is to perform different operations on
the same operand.

Operator that cannot be overloaded are as follows:

Scope operator (::)
Sizeof
member selector(.)
member pointer selector(*)
ternary operator(?:)
Syntax of Operator Overloading
return_type class_name : : operator op(argument_list)
{
// body of the function.
}

#include <iostream> using namespace std; class Test

{
private:
int num; public:
Test(): num(8){}
void operator ++() { num = num+2;
}
void Print() {
cout<<"The Count is: "<<num;
}
};
int main()
{
Test tt;
++tt; // calling of a function "void operator ++()" tt.Print();
return 0;
}
 class template
class template provides a specification for generating classes based on
parameters. Class templates are generally used to implement containers. A
class template is instantiated by passing a given set of types to it as
template arguments

// class templates #include <iostream> using namespace std;

template <class T> class mypair {

T a, b; public:
mypair (T first, T second)
{a=first; b=second;} T getmax ();
};

template <class T>

T mypair<T>::getmax ()
{
T retval;
retval = a>b? a : b; return retval;
}

int main () {
mypair <int> myobject (100, 75); cout << myobject.getmax(); return 0;
}

C++ Inheritance
In C++, inheritance is a process in which one object acquires all the
properties and behaviors of its parent object automatically. In such way, you
can reuse, extend or modify the attributes and behaviors which are defined in
other class.

Types Of Inheritance
C++ supports five types of inheritance:
Single inheritance
Multiple inheritance
Hierarchical inheritance
Multilevel inheritance
Hybrid inheritance

Derived Classes
A Derived class is defined as the class derived from the base clas

The Syntax of Derived class:

class derived_class_name :: visibility-mode base_class_name
{
// body of the derived class.
}

Visibility of Inherited Members

Base Class Derived Class Visibility

Visibility PUBLIC PRIVATE PROTECTED
Private Not Inherited Not Inherited Not
Inherited
Protected Protected Private Protected
Public Public Private Protected

Single Inheritance
Single inheritance is defined as the inheritance in which a derived class is
inherited from the only one base class

#include <iostream> using namespace std; class Account {

public:
float salary = 60000;
};
class Programmer: public Account { public:
float bonus = 5000;
};
int main(void) { Programmer p1;
cout<<"Salary: "<<p1.salary<<endl; cout<<"Bonus: "<<p1.bonus<<endl;
return 0;
}

Multilevel Inheritance
Multilevel inheritance is a process of deriving a class from another derived
class.
#include <iostream> using namespace std; class Animal {
public:
void eat() { cout<<"Eating..."<<endl;
}
};
class Dog: public Animal
{
public:
void bark(){ cout<<"Barking..."<<endl;
}
};
class BabyDog: public Dog
{
public:
void weep() { cout<<"Weeping...";
}
};
int main(void) { BabyDog d1; d1.eat();
d1.bark();
d1.weep(); return 0;
}

Multiple Inheritance
Multiple inheritance is the process of deriving a new class that inherits the
attributes from two or more classes.

Syntax of the Derived class:

class D : visibility B-1, visibility B-2, ?

{
// Body of the class;
}

Let's see a simple example of multiple inheritance.

#include <iostream> using namespace std; class A

{
protected:
int a; public:
void get_a(int n)
{
a = n;
}
};

class B
{
protected:
int b; public:
void get_b(int n)
{
b = n;
}
};
class C : public A,public B
{
public:
void display()
{
std::cout << "The value of a is : " <<a<< std::endl; std::cout << "The value
of b is : " <<b<< std::endl; cout<<"Addition of a and b is : "<<a+b;
}
};
int main()
{
C c; c.get_a(10);
c.get_b(20);
c.display();

return 0;
}
 Polymorphism
Polymorphism is an important and basic concept of OOPS. Polymorphism
specifies the ability to assume several forms. It allows routines to use
variables of different types at different times.
In C++, An operator or function can be given different meanings or
functions. Polymorphism refers to a single function or multi-functioning
operator performing in different ways.
Types of polymorphism
There are two types of polymorphism in C++
Static or Compile time polymorphism
Dynamic or Run time polymorphism

Static or compile time polymorphism

In this type of polymorphism behavior of functions and operators decide at
compile time. Thus, it is known as static or compile time polymorphism.
 There are two types of static polymorphism:
Function overloading
Operator overloading

Dynamic or run time polymorphism

Dynamic polymorphism is basically used for runtime time member function
binding. Thus, it is known as dynamic polymorphism.
There are following types of dynamic polymorphism:
Virtual functions.
Dynamic binding

C++ virtual function

A C++ virtual function is a member function in the base class that you redefine in a
derived class. It is declared using the virtual keyword.
It is used to tell the compiler to perform dynamic linkage or late binding on the
function.
There is a necessity to use the single pointer to refer to all the objects of the
different classes. So, we create the pointer to the base class that refers to all
the derived objects. But, when base class pointer contains the address of the
derived class object, always executes the base class function. This issue can
only be resolved by using the 'virtual' function.
A 'virtual' is a keyword preceding the normal declaration of a function.
When the function is made virtual, C++ determines which function is to be invoked
at the runtime based on the type of the object pointed by the base class pointer.

#include <iostream>
{
public:
virtual void display()
{
cout << "Base class is invoked"<<endl;
}
};
class B:public A
{
public:
void display()
{
cout << "Derived Class is invoked"<<endl;
}
};
int main()
{
A* a; //pointer of base class B b; //object of derived class a = &b;
a->display(); //Late Binding occurs
}

Algorithm:
An algorithm is a finite set of step by step instructions to solve a
problem. In normal language, algorithm is defined as a sequence of
statements which are used toperform a task.
In computer science, an algorithm can be defined as follows:
 An algorithm is a sequence of unambiguous instructions used for solving
aproblem, which can be implemented (as a program) on a computer.
Properties
Every algorithm must satisfy the following properties:
Definiteness - Every step in an algorithm must be clear and unambiguous
Finiteness – Every algorithm must produce result within a finite number of steps.
Effectiveness - Every instruction must be executed in a finite amount of time.
Input & Output - Every algorithm must take zero or more number of inputs and
must produce at least one output as result.

Performance Analysis
In computer science there are multiple algorithms to solve a problem. When
we have more than one algorithm to solve a problem, we need to select the
best one.
Performance analysis helps us to select the best algorithm from multiple
algorithms to solve a problem.When there are multiple alternative algorithms
to solve a problem, we analyses them and pick the one which is best
suitable for our requirements. Generally, the performance of an algorithm
depends on the following elements...
Whether that algorithm is providing the exact solution for the problem?
Whether it is easy to understand?
Whether it is easy to implement?
How much space (memory) it requires to solve the problem?
How much time it takes to solve the problem? Etc.,
When we want to analyze an algorithm, we consider only the space and time
required by that particular algorithm and we ignore all remaining
elements.Performance analysis of an algorithm is performed by using the
following measures:
Space Complexity
Time Complexity

Space complexity
Total amount of computer memory required by an algorithm to complete
its execution is called as space complexity of that algorithm.Generally, when
a program is under execution it uses the computer memory for THREE
 reasons. They are as follows...
Instruction Space: It is the amount of memory used to store compiled version of
instructions.
Environmental Stack: It is the amount of memory used to store information of
partially executed functions at the time of function call.
Data Space: It is the amount of memory used to store all the variables and
constants.
NOTE: When we want to perform analysis of an algorithm based on its Space
complexity, we consider only Data Space and ignore Instruction Space as well
as Environmental Stack. That means we calculate only the memory required
to store Variables, Constants, Structures, etc
Consider the following piece of code... int square(int a)
{
return a*a;
}

In above piece of code, it requires 2 bytes of memory to store variable 'a' and
another 2 bytes of memory is used for return value. That means, totally it
requires 4 bytes of memory to complete its execution.

Time complexity
The time complexity of an algorithm is the total amount of time
required by an algorithm to complete its execution. Generally, running time
of an algorithm depends upon the
 following:
Whether it is running on Single processor machine or Multi processor machine.
Whether it is a 32 bit machine or 64 bit machine
Read and Write speed of the machine.
The time it takes to perform Arithmetic operations, logical operations, return
value and assignment operations etc.,
NOTE: When we calculate time complexity of an algorithm, we consider only
input data and ignore the remaining things, as they are machine dependent.

Consider the following piece of code... Algorithm Search (A, n, x)

{ // where A is an array, n is the size of an array and x is the item to be
searched. for i := 1 to n do
{
if(x=A[i]) then
{
write (item found at location i) return;
}
}
write (item not found)
}
For the above code, time complexity can be calculated as follows:
Cost is the amount of computer time required for a single operation in each
line. Repetition is the amount of computer time required by each operation
for all its repetitions, so above code requires 'n' units of computer time to
complete the task.

Asymptotic Notation
Asymptotic notation of an algorithm is a mathematical representation
of its complexity.
Majorly, we use THREE types of Asymptotic Notations and those are:
Big - Oh (O)
Omega (Ω)
Theta (Θ)
Big - Oh Notation (O)
Big - Oh notation is used to define the upper bound of an algorithm in terms of
 Time Complexity.
Big - Oh notation always indicates the maximum time required by an algorithm
for all input values.
Big - Oh notation describes the worst case of an algorithm time complexity.
It is represented as O(T)

Omega Notation (Ω)

Omega notation is used to define the lower bound of an algorithm in terms of
Time Complexity.
Omega notation always indicates the minimum time required by an algorithm for
all input values.
Omega notation describes the best case of an algorithm time complexity.
It is represented as Ω (T)

Theta Notation (Θ)

Theta notation is used to define the average bound of an algorithm in terms of
Time Complexity.
Theta notation always indicates the average time required by an algorithm for all
input
 values.
Theta notation describes the average case of an algorithm time complexity.
It is represented as Θ (T)

Example
Consider the following piece of code Algorithm Search (A, n,x)
{ // where A is an array, n is the size of an array and x is the item to be
searched. for i := 1 to n do
{
if(x=A[i]) then
{
write (item found at location i) return;
}
}
write (item not found)
}

The time complexity for the above algorithm

Best case is Ω (1)
Average case is Θ (n/2)
Worst case is O (n)

What is Data Structure?

Data may be organized in many different ways: The logical or mathematical
model of a particular organization of data is called data structure. Data
structures are generally classified into primitive and non- primitive data
structures
 Based on the organizing method of a data structure, data structures are
divided into two types.
Linear Data Structures
Non - Linear Data Structures

Linear Data Structures

If a data structure is organizing the data in sequential order, then that data
structure is called as Linear Data Structure. For example:
Arrays
Lists (Linked List)
Stacks
Queues
Non - Linear Data Structures
If a data structure is organizing the data in random order, then that
data structure is called as Non-Linear Data Structure. For example:
Trees
Graphs
Dictionaries
Heaps , etc