24CYS204 - ADVANCED
PROGRAMMING
[Link] V,
TIFAC – CORE in Cyber Security
Amrita School of
Engineering,Coimbatore.
Amrita Vishwa Vidyapeetham,India.
Tamil Nadu, India.
1
MODULE 2
Revisiting Pointers: Pointers to Pointers, Pointers and String
Array, Void Pointers and Function Pointers, Standard Template
Library, Implementation of Stack, Queue, Hash Table and Linked
Lists with STL. Control Statements and Loops, Iterators and
Iterable, Functions, Recursion and Parameter Passing,
Namespaces and Variable Scope, Exception Handling.
STANDARD TEMPLATE LIBRARY :
• The Standard Template Library (STL) in C++ is a set of ready-
made tools that help programmers handle data easily.
• It separates data store and data manipulation.
• It includes useful features like containers, iterators,
algorithms, and function objects to make coding faster and
more efficient.
• With STL, you don’t need to write common data structures like
arrays, linked lists, stacks, queues, maps, and sets from scratch.
• It also provides built-in functions for sorting, searching, and
modifying data.
STANDARD TEMPLATE LIBRARY :
STANDARD TEMPLATE LIBRARY :
STANDARD TEMPLATE LIBRARY :
Containers
Hold and organize data
E.g. vector, list, deque, map, set, stack, queue, priority_queue,
array, unordered containers
Algorithms
Work on data in containers
E.g. sort, find, reverse, count, accumulate
Iterators
Navigate containers
Types: input, output, forward, bidirectional, random access
Functors
Objects acting like functions
E.g. less, greater, custom comparators
CONTAINERS :
CONT… :
VECTOR :
• A vector in C++ is like a resizable array.
• Both vectors and arrays are data structures used to store
multiple elements of the same data type.
• The difference between an array and a vector, is that the size of
an array cannot be modified (you cannot add or remove
elements from an array).
• A vector however, can grow or shrink in size as needed.
• To use a vector, you have to include the <vector> header file
Link 1:[Link]
Link 2:[Link]
VECTOR :
//Remove and resize
Link 3:[Link]
//Sort and reverse
Link 4:[Link]
//Vector Swapping
Link 5:[Link]
//Remove Duplicate element in vector
Link 6: [Link]
VECTOR :
IMPLEMENTATION OF STACK :
• The STL stack provides the functionality of a stack data
structure in C++.
• The stack data structure follows the LIFO (Last In First Out)
principle. That is, the element added last will be removed
first.
• In the stack are not accessed by index numbers. Since
elements are added and removed from the top, you can only
access the element at the top of the stack.
BASIC OPERATIONS STACK :
Inserting Elements
Accessing Elements
Deleting Elements
Pseudo Traversal
Others : size(),empty(),swap()
IMPLEMENTATION OF STACK :
//Necessary Library
#include <stack>
// Create a stack of strings called cars
stack<string> cars;
//Cannot add element to stack like vector
stack<string> cars = {"Volvo", "BMW", "Ford", "Mazda"};
//Access the elements at top
cout << [Link]();
IMPLEMENTATION OF STACK :
//Get the size of stack
cout << [Link]();
//Check if the stack empty or not
cout << [Link]();
Link:
//Inserting elements in stack
[Link]
//Converting stack to vector
[Link]
IMPLEMENTATION OF STACK :
//Passing the stack elements to function
[Link]
//Reverse the stack
[Link]
//Swap the two stack
[Link]
//Clear the stack
[Link]
//Difference between stack and vector
[Link]
IMPLEMENTATION OF QUEUE :
• A queue stores multiple elements in a specific order,
called FIFO(First in, First Out)
• Unlike vectors, elements in the queue are not accessed by index
numbers.
• Since queue elements are added at the end and removed
from the front, you can only access an element at the front or
the back.
IMPLEMENTATION OF QUEUE :
IMPLEMENTATION OF QUEUE :
//Necessary Library
#include <queue>
//Add the element
To add elements to the queue, you can use the .push() function
after declaring the queue.
//Access the element
• You cannot access queue elements by referring to index
numbers, like you would with arrays and vectors.
• In a queue, you can only access the element at the front or
the back, using .front() and .back()
IMPLEMENTATION OF QUEUE :
Output:
IMPLEMENTATION OF QUEUE :
//Try yourself:
1. Pass the queue elements to function
2. Reverse the queue
3. Swap the two queue
4. Clear the queue
//Queue Problem:
[Link]
DIFFERENCE BETWEEN STACK AND QUEUE :
STACK QUEUE
Output: Output:
PRIORITY QUEUE :
• In C++, the STL priority_queue provides the functionality of
a priority queue data structure.
• A priority queue is a special type of queue in which each
element is associated with a priority value and elements
are served based on their priority.
//Syntax:
priority_queue<type> pq;
//Methods:
push(), pop(), top(), size(), empty()
PRIORITY QUEUE :
Push() - inserts the element into the priority queue
Pop() - removes the element with the highest priority
Top() - returns the element with the highest priority
Size() - returns the number of elements
Empty() - returns true if priority queue is empty
IMPLEMENTATION OF PRIORITY QUEUE :
//Initialise and print priority queue
[Link]
Note:
• we have pushed elements in random order but when printing
them we get the integers sorted in descending order: 20,
7, 1.
• The top of the queue is the maximum element in the queue
since priority_queue is implemented as max-heap by
default
//Remove and check size of queue
[Link]
//Conversion of priority queue to queue.
DIFFERENCE BETWEEN STACK AND QUEUE :
Feature Queue Priority Queue
A queue is a data structure that
Definitio A priority queue is a data structure that
follows the FIFO (First In First Out)
n stores elements based on their priority.
principle.
Order of
Elements are processed in the Elements are processed based on priority,
Processi
order they arrive. not arrival order.
ng
New elements are added at the New elements can be inserted at any
Insertion
back of the queue. position based on their priority.
The element removed is always The element removed is the one with the
Removal
the one at the front. highest priority.
Useful for scheduling tasks in the Useful for scenarios where certain tasks
Use
order they are received, such as need to be prioritized, such as job
Cases
print jobs. scheduling in operating systems
LIST :
Linked lists are dynamic data structures that consist of nodes, and
they can be categorized into three main types:
Linked list
Singly
Doubly
Circular
LIST :
Singly Doubly Circular
Structure It consists of nodes where each It has nodes with three It can be either singly or
node contains two fields: data, a link to the doubly linked. In this
fields: data and a link (or next node, and structure, the last
pointer) to the next node in the node's next
sequence.
a previous link to the
previous node. pointer points
back to the first
node, creating a circular
loop.
Traversal This allows traverse in one This allows traversal in both This allows for
direction only, from the directions (forward and continuous
head (first node) to the last backward), making it more traversal of the
node, which points to null. flexible than singly linked lists list without needing to
check for null pointers,
making it suitable for
applications that require
cycling through the list
repeatedly.
Memory It consumes less memory It consumes more memory Similar to singly and
compared to doubly linked lists than singly linked lists due to the doubly linked lists, but the
LIST :
Singly:
Singly:
LIST :
Doubly:
LIST :
Circular
LIST :
A list is similar to a vector in that it can store multiple elements
of the same type and dynamically grow in size.
• In C++, list container implements a doubly linked list in
which each element contains the address of next and previous
element in the list.
• You can add and remove elements from both the
beginning and at the end of a list
• Unlike vectors, a list does not support random access,
meaning you cannot directly jump to a specific index, or
access elements by index numbers.
IMPLEMENTATION OF LIST :
//Necessary Library
#include <list>
//Create a list
list<string> cars = {"Volvo", "BMW", "Ford", "Mazda"};
// Get the first element
cout << [Link](); // Outputs Volvo
// Get the last element
cout << [Link](); // Outputs Mazda
// Change the value of the first element
[Link]() = "Opel";
IMPLEMENTATION OF LIST :
// Change the value of the last element
[Link]() = "Toyota";
// Add an element at the beginning
cars.push_front("Tesla");
// Add an element at the end
cars.push_back("VW");
// Remove the first element
cars.pop_front();
// Remove the last element
cars.pop_back();
Link: [Link]
METHODS IN LIST :
reverse() Reverses the order of the elements.
sort() Sorts the list elements in a particular order.
unique() Removes consecutive duplicate
elements.
empty() Checks whether the list is empty.
size() Returns the number of elements in the list.
clear() Clears all the values from the list
merge() Merges two sorted lists.
delete() Delete the specific element in list
count() Count the number of element in list
find() Find the specific value in list
METHODS IN LIST :
//Print unique elements
[Link]
//Merge the two list
[Link]
// Delete the occurrence of the element
[Link]
//Reverse the doubly elements
[Link]
//Sort Ascending and Descending
[Link]
//Count and Find
[Link]
HASING :
Why Hashing?
Searching is dominant operation on any data structure.
Most of the cases for inserting, deleting, updating all operations
required searching first. So, searching operation of particular
data structure determines it’s time complexity.
Hash Table:
A hash table is a data structure that stores key-value pairs. It
uses a hash function to map each key to an index in an array.
This index is used to store and retrieve the corresponding value.
HASING :
But problem is if elements (for example) 2, 12, 22, 32, elements
need to be inserted then they try to insert at index 2 only. This
problem is called Collision.
HASING :
To solve this collision problem we use different types of hash
function techniques. Those are given below:
1. Chaining
2. Open addressing
a. Linear probing
b. Quadratic probing
c. Double hashing
These also called collision resolution techniques.
Chaining:
MAP :
In C++ STL, there is a built-in map class template to use as hash table
(Associative array).
//Necessary Library
#include <map>
//Create and initialise the value of Map
map<string, int> people= { {"John", 32}, {"Adele", 45}, {"Bo", 29} };
//Can access only with [] bracket cant access like vector and array
cout << "John is: " << people["John"] << "\n";
//Can also access elements with the .at() function:
cout << "Adele is: " << [Link]("Adele") << "\n";
MAP :
// Changing the values
people["John"] = 50;
(or)
[Link]("John") = 50;
//Create and initialise the value of Map
map<string, int> people= { {"John", 32}, {"Adele", 45}, {"Bo", 29} };
//Can access only with [] bracket cant access like vector and array
cout << "John is: " << people["John"] << "\n";
//Can also access elements with the .at() function:
cout << "Adele is: " << [Link]("Adele") << "\n";
Link: [Link]
MAP :
// Element with equal keys
[Link]
//Remove Elements: remove specific element
Output:
MAP :
//Remove Elements: remove all element
.clear() function
//Count the specific element
.count(key) function
//Loop in Map
• You should use the auto keyword (introduced in C++ version 11) inside
the for loop. This allows the compiler to automatically determine the
correct data type for each key-value pair.
• Since map elements consist of both keys and values, you have to
include .first to access the keys, and .second to access values in the
loop.
• Elements in the map are sorted automatically in ascending order by
their keys:
MAP :
Output:
MAP :
If you want to reverse the order, you can use the greater<type> functor inside the
angle bracket
Output:
MAP :
//First non-repeating character in a string
Input : swiss
Output :w
MAP :
//Loop iterations
UNORDERED MAP :
UNORDERED MAP :
ORDERED MAP UNORDERED MAP
Output:
Output:
UNORDERED MAP :
• unordered_map is a container that stores key-value pairs.
• Unlike map, it does not keep the keys sorted.
• It uses a hash table internally, so all operations like insert, delete, and find
are on average O(1) time.
#include <unordered_map>
using namespace std;
Syntax:
unordered_map<KeyType, ValueType> mapName;
Example:
unordered_map<string, int> fruitCount;
UNORDERED MAP :
//Insert
fruitCount["apple"] = 2;
fruitCount["banana"] = 5;
(or)
[Link]({"mango", 3});
//Access Elements:
cout << fruitCount["apple"]; // Outputs: 2
//Find Element:
if ([Link]("banana") != [Link]()) {
cout << "Banana is present!";
}
UNORDERED MAP :
//Erase
[Link]("apple");
//Size and Empty:
cout << [Link]();
cout << [Link](); // Returns true if map is empty
//Find Element:
if ([Link]("banana") != [Link]()) {
cout << "Banana is present!";
}
Link: [Link]
DUPLICATE ELEMENT IN MAP :
DUPLICATE ELEMENT IN MAP(INTERNAL
WORKING) :
.
DUPLICATE ELEMENT IN MAP(INTERNAL WORKING) :
Hash Table View (Buckets)
This is a simplified visualization, actual internal hash values and buckets depend on
implementation
[ Bucket 0 ] → 3:1
[ Bucket 1 ] → 1:2
[ Bucket 2 ] → 2:2
[ Bucket 3 ] → 4:1
.
PROGRAM: GROUP ANAGRAMS
//Output:
Grouped Anagrams:
[ "eat" "tea" "ate" ]
[ "tan" "nat" ]
[ "bat" ]
.
INTERNAL WORKING:
VISUAL MAP:
.
PROBLEM TO PRACTICE
//Count Frequency of Elements using unordered map
//Check if Two Strings are Anagrams using unordered map
//Find two numbers in the array whose sum is equal to the
target.
Input:
arr = [2, 7, 11, 15]
Target=9
Output:2,7
ITERATORS AND ITERABLE FUNCTIONS :
Iterable:
An iterable is any container that stores a sequence of elements
and allows you to go through (iterate) its elements using iterators.
Examples of STL Iterables:
•vector
•array
•set
•map
•unordered_map
•list, deque, stack, etc.
ITERATORS AND ITERABLE FUNCTIONS :
Iterators:
An iterator is an object (like a pointer) used to access elements of
an STL container one by one.
It's similar to a pointer in syntax:
*it // value at the iterator
++it // move to next element
//Sample Code:
ITERATORS AND ITERABLE, FUNCTIONS :
Iterators available only for the following container:
Iterator is not a global type — it only exists inside specific
containers like:
•vector<int>::iterator
•list<string>::iterator
•map<string, int>::iterator
Summary:
Common Iterator
STL Container Example Syntax
Type
vector<T> vector<T>::iterator *it, ++it
list<T> list<T>::iterator *it, ++it
map<K,V> map<K,V>::iterator it->first, it->second
ITERATORS AND ITERABLE, FUNCTIONS :
//Map
map, the iterator points to a pair:
Example:
for (auto it = [Link](); it != [Link](); ++it)
{
cout << it->first << " => " << it->second << endl;
}
METHODS SUPPORT IN ITERATOR:
rbegin(),rend( cbegin(),cend(
) )
Output: Output:
RECURSION :
Recursion is when a function calls itself to solve a problem by
breaking it into smaller sub-problems.
Base case:
When n == 0, the function returns 0 (stops recursion).
Recursive case:
For n > 0, it returns n + sumNatural(n - 1).
This keeps calling itself with smaller values until it hits 0.
PROBLEM TO PRACTICE IN RECURSION :
//program for Fibonacci Series
//program to find the sum of natural numbers
//program to reverse a string
//program for tower of Hanoi
//program for Generating All Permutations of a String
Input: ABC
NAMESPACE :
A namespace in C++ is like a container that groups related
names (variables, functions, classes, etc.) together so they don’t
accidentally conflict with names from other parts of a program or
from libraries.
Why We Need Namespaces:
• If two libraries have a function or variable with the same name,
the compiler wouldn’t know which one to use.
• Namespaces solve this problem by qualifying names.
• A namespace is not a variable, object, or memory instance
— it’s more like a folder that holds related functions, variables,
and classes.
NAMESPACE :
VARIABLE SCOPE :
Variable scope refers to the part of a program where a variable
can be accessed or [Link] are 4 types of scope
Local Global
scope
class Functional
LOCAL SCOPE :
Local Scope (Block Scope)
•Declared inside a function or {} block.
•Accessible only inside that block.
•Destroyed when block ends.
•.
GLOBAL SCOPE :
Global Scope (Block Scope)
•Declared outside all functions.
•Accessible from anywhere in the file (or other files using extern).
•Exists for the entire program’s life.
•.
FUNCTION SCOPE :
•Function parameters are scoped only inside the function.
•They act like local variables.
CLASS SCOPE :
•Variables declared inside a class are scoped to that class.
•Can be accessed via objects (or directly if static).
ANY QUERIES ?
THANK YOU!