VIT Bhopal University

Bhopal-Indore Highway, Kothri Kalan, Sehore, Madhya Pradesh – 466114.

Object Oriented Programming with C++

Course Code: CSE 2001

By:
Dr. Ramraj Dangi
 ● Introduction to object oriented
approach
● Classes and objects
Chapters ● Polymorphism and Inheritance
● Exception handling and Templates
● IOstreams and Files
 Exception handling (user-defined
exception),

Syllabus Function Template,

Class Template,
Template with inheritance,
STL: Container, Algorithm,
Iterator; vector, list, stack, map.
STL (Standard Template Library)
Standard Template Library

The Standard Template Library (STL) is a set of C++ template classes to provide common
programming data structures and functions such as lists, stacks, arrays, etc.
It is a library of container classes, algorithms, and iterators. It is a generalized library and so, its
components are parameterized.
Components of STL;
● Algorithms
● Containers
● Iterators
Containers

● Containers or container classes store objects and data.

● Containers are used to manage collections of objects of certain kind.

● Container library in STL provide containers that are used to create data structures like arrays
linked list, trees etc.

● These container are generic, they can hold elements of any types.

● There are in total seven standard “first-class” container classes and three container adaptor
classes and only seven header files that provide access to these containers or container
adaptors.
Algorithms

● Algorithms can act on containers. They provide the means by which you will perform
initialization, sorting , searching, and transforming of the contents of containers.

● Algorithms library contains built in functions that perform complex algorithms on the data
structures.

● The header algorithm defines a collection of functions especially designed to be used on

ranges of elements.
Iterators

● Iterators are used for working upon a sequence of values.

● Iterators are used to step through the elements of collection of object. These collections may
be containers or subset of container.

● Iterators in STL are used to point to the container.

● Iterators actually act as a bridge between containers and algorithms.

Types of Containers

Sequence Containers: implement data structures which can be accessed in a sequential manner.
● vector
● list
● deque
● arrays
● forward_list

Container Adaptors : provide a different interface for sequential containers.

○ queue
○ priority_queue
○ stack
Types of Containers

Associative Containers : implement sorted data structures that can be quickly searched (O(log n)
complexity).
◆ set
◆ multiset
◆ map
◆ multimap

Unordered Associative Containers:

◆ unordered_set
◆ unordered_multiset
◆ unordered_map
◆ unordered_multimap
Common Containers

● Vector : Replicates Arrays

● Queue : Replicates Queues
● Priority Queue : Replicates Heap
● Stack : Replicates stacks
● List : Replicates Linked List
● Set : Replicates Trees
● Map : Associative Arrays
Array

● Array is a linear collection of similar types of element.

● Array container in STL provides us the implementation of static array.

● Use header array

#include<array>

● Creating object
array <object_type, array_size> array_name; //A <int> a1;
It create an empty array of object_type with maximum size of array_size.
Ex. array<int, 5> arr;
 Operations on Array

1. at()
2. get()
3. operator[]
4. front()
5. back()
6. size()
7. max_size()
8. swap()
9. empty()
10. fill()
Iterators

● Iterators are used to point at the memory addresses of STL containers.

● They are primarily used in sequence of numbers, characters etc.
● They reduce the complexity and execution time of program.

Operations of Iterators:

1. begin()
2. end()
3. advance()
4. next()
5. prev()
6. inserter()
Iterator Functions
1. begin() : This function is used to return the beginning position of the container.

2. end() : This function is used to return the after end position of the container.

3. advance() : This function is used to increment the iterator position till the specified number
mentioned in its arguments.

4. next() : This function returns the new iterator that the iterator would point after advancing the
positions mentioned in its arguments.

5. prev() : This function returns the new iterator that the iterator would point after decrementing
the positions mentioned in its arguments.

6. inserter() : This function is used to insert the elements at any position in the container. It accepts
2 arguments, the container and iterator to position where the elements have to be inserted.
Vector

● The most general purpose container is Vector.

● It supports dynamic array; 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 there may be a need of extending the array.
● 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.
Functions associated with Vector:

1. Iterators : begin(), end(), rbegin(), rend()...

2. Capacity : size(), max_size(), capacity(), resize(), empty(), shrink_to_fit()..

3. Element access : operator[], at(), front(), back()..

4. Modifiers : assign(), push_back(), pop_back(), insert(), erase(), swap(), clear()...

vector<int> v; //capacity = 0 v.pop_back(); //remove 100 from v
vector<int> v {10} //capacity = 1 //capacity = 16
v.push_back(20); //capacity = 2 v.pop_back(); //remove 90 from v
v.push_back(30); //capacity = 4 //capacity = 16
v.push_back(40); //capacity = 4 v.pop_back(); //remove 80 from v
v.push_back(50); //capacity = 8 //capacity = 16
v.push_back(60); //capacity = 8 shrink_to_fit();
v.push_back(70); //capacity = 8 //capacity = 7
v.push_back(80); //capacity = 8
v.push_back(90); //capacity = 16
v.push_back(100); //capacity = 16

10 20 30 40 50 60 70

10 20 30 40 50 60 70 // new capacity
Iterator function in Vector

Iterators

1. begin() : Returns an iterator pointing to the first element in the vector

2. end() : Returns an iterator pointing to the theoretical element that follows the last element in the
vector

3. rbegin() : Returns a reverse iterator pointing to the last element in the vector (reverse
beginning). It moves from last to first element

4. rend() : Returns a reverse iterator pointing to the theoretical element preceding the first element
in the vector (considered as reverse end)
Capacity function in Vector
Capacity
1. size() : Returns the number of elements in the vector.
2. max_size() : Returns the maximum number of elements that the vector can hold.
3. capacity() : Returns the size of the storage space currently allocated to the vector expressed as
number of elements.
4. resize(n) : Resizes the container so that it contains ‘n’ elements.
5. empty() : Returns whether the container is empty.
6. shrink_to_fit() : Reduces the capacity of the container to fit its size and destroys all elements
beyond the capacity.
Element Access function in Vector
Element access:
1. reference operator [g] : Returns a reference to the element at position ‘g’ in the vector
2. at(g) : Returns a reference to the element at position ‘g’ in the vector
3. front() : Returns a reference to the first element in the vector
4. back() : Returns a reference to the last element in the vector
5. data() : Returns a direct pointer to the memory array used internally by the vector to store its
owned elements.
Modifier functions in Vector
1. assign() : It assigns new value to the vector elements by replacing old ones
2. push_back() : It push the elements into a vector from the back
3. pop_back() : It is used to pop or remove elements from a vector from the back.
4. insert() : It inserts new elements before the element at the specified position
5. erase() : It is used to remove elements from a container from the specified position or range.
6. swap() : It is used to swap the contents of one vector with another vector of same type. Sizes may differ.
7. clear() : It is used to remove all the elements of the vector container
8. emplace() : It extends the container by inserting new element at position
9. emplace_back() : It is used to insert a new element into the vector container, the new element is added to
the end of the vector
List

● Lists are sequence containers that allow non-contiguous memory allocation.

● As compared to vector, the list has slow traversal, but once a position has been found, insertion and
deletion are quick.
● List class supports a bidirectional, linear list.
● List can be accessed sequentially only.
● List can be accessed from front to back or back to front.

● list - replica of doubly-linked list whereas forward_list - replica of singly-linked list.

Functions in List

1. front(): Returns the value of the first element in the list.

2. back(): Returns the value of the last element in the list.
3. push_front(g): Adds a new element ‘g’ at the beginning of the list.
4. push_back(g) : Adds a new element ‘g’ at the end of the list.
5. pop_front(): Removes the first element of the list, and reduces size of the list by 1.
6. pop_back(): Removes the last element of the list, and reduces size of the list by 1.
7. list::begin(): begin() function returns an iterator pointing to the first element of the list.
8. list::end(): end() function returns an iterator pointing to the theoretical last element which follows
the last element.
More function in List

rbegin() rend() empty() insert() erase() assign()

remove() remove_if() reverse() size() resize() sort()

max_size() unique() splice() clear() operator= swap()

merge() emplace() emplace_front() emplace_back()

Stack

● Stacks are a type of container adaptors with

LIFO(Last In First Out);
● Where a new element is added at one end (top) and an
element is removed from that end only.
● Stack uses an encapsulated object of either vector or
deque (by default) or list (sequential container class)
as its underlying container, providing a specific set of
member functions to access its elements.
Stack

● For creating a stack, we must include the <stack> header file in our code.
● We then use this syntax to define the std::stack:

template <class Type, class Container = deque<Type> > class stack;

Type – is the Type of element contained in the std::stack. It can be any valid C++ type or even a
user-defined type.
Container – is the Type of underlying container object.
Functions in Stack

1. empty() : Returns whether the stack is empty – Time Complexity : O(1)

2. size() : Returns the size of the stack – Time Complexity : O(1)

3. top() : Returns a reference to the top most element of the stack – Time Complexity : O(1)

4. push(g) : Adds the element ‘g’ at the top of the stack – Time Complexity : O(1)

5. pop() : Deletes the top most element of the stack – Time Complexity : O(1)
Map

● Maps are associative containers that store elements in a mapped fashion.

● Map replicates associative arrays.
● Map contain sorted key value pair, in which each key is unique and cannot be changed.
● It cannot be inserted or deleted but cannot be altered.
● Each element has a key value and a mapped value.
● No two mapped values can have the same key values.
Types of Arrays-
Numeric Array- 0 1 2 3 4
int a[5]; 10 20 30 40 50

float f[4]; .5 .6 .2 .3

String s[3]; Aayush 10

Shubh Ayush Adi Ayush 10
David 30
Associative Array- Rahul 80
int marks[10]; Shubh 20

10 20 30 40 50 10 20 30 40 50

Ques: Update marks of Rahul to 80?

Ayush Aayush
<name, marks>= <key, value> David
10 20 30 80 50 10 20 30 40 50
Shubh Rahul
Properties of Map

● Map always arrange its keys in sorted order.

● In case the keys are of string type, they are sorted in dictionary order.
Functions in Map
1. begin() – Returns an iterator to the first element in the map.
2. end() – Returns an iterator to the theoretical element that follows the last element in the map.
3. size() – Returns the number of elements in the map.
4. max_size() – Returns the maximum number of elements that the map can hold.
5. empty() – Returns whether the map is empty.
6. pair insert(keyvalue, mapvalue) – Adds a new element to the map.
7. erase(iterator position) – Removes the element at the position pointed by the iterator.
8. erase(const g)– Removes the key-value ‘g’ from the map.
9. clear() – Removes all the elements from the map
More functions in Map

insert() count() equal_range() erase() rend() rbegin()

find() crbegin() crend() crbegin() map cbegin() cend()

cbegin() emplace() max_size() upper_bound() operator= empty()

lower_bound() emplace_hint() value_comp() key_comp() size() swap()

begin() end() operator[] clear() at()