21CSC101T

Object Oriented Design and Programming

UNIT-5
 Syllabus
• STL: Containers: Sequence and Associative Container -
Sequence Container: Vector, List, Deque, Array, Stack -
Associative Containers: Map, Multimap - Iterator and
Specialized iterator - Functions of iterator - Algorithms: find(),
count(), sort() - Algorithms: search(), merge(), for_each(),
transform()
Standard Template Library
 What is STL???
• 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.
• A working knowledge of template classes is a prerequisite for working
with STL.
 Why use STL???
• STL offers an assortment of containers
• STL publicizes the time and storage complexity of its containers
• STL containers grow and shrink in size automatically
• STL provides built-in algorithms for processing containers
• STL provides iterators that make the containers and algorithms flexible and efficient.
• STL is extensible which means that users can add new containers and new
algorithms such that:
– STL algorithms can process STL containers as well as user defined containers
– User defined algorithms can process STL containers as well user defined
containers
 C++ Standard Template Libraries
• In 1990, Alex Stepanov and Meng Lee of Hewlett Packard Laboratories extended C+
+ with a library of class and function templates which has come to be known as the
STL.
• In 1994, STL was adopted as part of ANSI/ISO Standard C++.
 The C++ Standard Template Libraries

• STL had three basic components:

– Containers
Generic class templates for storing collection of data.
– Algorithms
Generic function templates for operating on containers.
– Iterators
• Generalized ‘smart’ pointers that facilitate use of containers.
• They provide an interface that is needed for STL algorithms to operate on
STL containers.
• String abstraction was added during standardization.
 STL has four
components

Containers Iterators Algorithms Functions

 STL Containers

Sequence and Associative Containers

 Containers

• Containers or container classes store objects and data.

• 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.
– Sequence Containers
– Container Adaptors
– Associative Containers
– Unordered Associative Containers
 Sequence Containers

• vector
Implement data structures which • list
can be accessed in a sequential • deque
manner. • arrays
• forward-list
Topic : Sequence Container: Vector List
 Sequence Containers: Vector
• Vectors are 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 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 the
vector

Iterators Capacity Element access Modifiers

 functions associated with the vector

Iterators
begin()  end() rbegin() rend() cbegin() cend() crbegin() crend()

Returns a reverse Returns a constant Returns a constant

Returns a reverse iterator pointing to Returns a constant
Returns an iterator reverse iterator reverse iterator
iterator pointing to the theoretical iterator pointing to
Returns an iterator pointing to the pointing to the last pointing to the
the last element in Returns a constant the theoretical
pointing to the first theoretical element element preceding element in the theoretical element
the vector (reverse iterator pointing to element that
element in the that follows the the first element in vector (reverse preceding the first
beginning). It the first element in follows the last
vector last element in the the vector beginning). It element in the
moves from last to the vector. element in the
vector (considered as moves from last to vector (considered
first element reverse end) vector. first element as reverse end)
// C++ program to illustrate the iterators in vector
#include <iostream>
#include <vector>

using namespace std;

int main()
{
vector<int> g1;
Output:
for (int i = 1; i <= 5; i++) Output of begin and end: 1 2 3 4 5
g1.push_back(i); Output of cbegin and cend: 1 2 3 4 5
Output of rbegin and rend: 5 4 3 2 1
cout << "Output of begin and end: "; Output of crbegin and crend : 5 4 3 2 1
for (auto i = g1.begin(); i != g1.end(); ++i)
cout << *i << " ";

cout << "\nOutput of cbegin and cend: ";

for (auto i = g1.cbegin(); i != g1.cend(); ++i)
cout << *i << " ";

cout << "\nOutput of rbegin and rend: ";

for (auto ir = g1.rbegin(); ir != g1.rend(); ++ir)
cout << *ir << " ";

cout << "\nOutput of crbegin and crend : ";

for (auto ir = g1.crbegin(); ir != g1.crend(); ++ir)
cout << *ir << " ";

return 0;
}
 functions associated with the vector

Capacity

size()  max_size()  capacity() resize(n)  empty() shrink_to_fit() reserve() 

Returns the size of Reduces the

Returns the the storage space capacity of the Requests that the
Returns the Resizes the vector capacity be
number of maximum number currently allocated Returns whether container to fit its
container so that it size and destroys at least enough to
elements in the of elements that to the vector contains ‘n’ the container is
the vector can expressed as empty. all elements contain n
vector. elements. elements.
hold. number of beyond the
elements. capacity.
// C++ program to illustrate the capacity function in // checks if the vector is empty or not
vector if (g1.empty() == false)
#include <iostream> cout << "\nVector is not empty";
#include <vector> else
cout << "\nVector is empty";
using namespace std;
// Shrinks the vector
int main() g1.shrink_to_fit();
{ cout << "\nVector elements are: ";
vector<int> g1; for (auto it = g1.begin(); it != g1.end(); it++)
cout << *it << " ";
for (int i = 1; i <= 5; i++)
g1.push_back(i); return 0;
}
cout << "Size : " << g1.size();
cout << "\nCapacity : " << g1.capacity();
cout << "\nMax_Size : " << g1.max_size();

// resizes the vector size to 4 1 2 3 4 5

g1.resize(4); Output:
Size : 5
// prints the vector size after resize()
Capacity : 8
cout << "\nSize : " << g1.size();
Max_Size : 4611686018427387903
Size : 4
Vector is not empty
Vector elements are: 1 2 3 4
 functions associated with the vector

Element access

reference operator
at(g) front() back() data()
[g]

Returns a direct
Returns a reference Returns a reference Returns a reference pointer to the
Returns a reference memory array used
to the element at to the element at to the first element to the last element in
position ‘g’ in the position ‘g’ in the the vector internally by the
in the vector vector to store its
vector vector
owned elements.
// C++ program to illustrate the element accesser in vector
#include <bits/stdc++.h>
using namespace std;

int main()
{ 10 20 30 40 50 60 70 80
vector<int> g1;
90 100
for (int i = 1; i <= 10; i++)
g1.push_back(i * 10);
Output:
for (auto i = g1.begin(); i != g1.end(); ++i)
cout << *i << " "; 10 20 30 40 50 60 70 80 90 100
Reference operator [g] : g1[2] = 30
at : g1.at(4) = 50
cout << "\nReference operator [g] : g1[2] = " << g1[2]; front() : g1.front() = 10
back() : g1.back() = 100
cout << "\nat : g1.at(4) = " << g1.at(4);
The first element is 10
cout << "\nfront() : g1.front() = " << g1.front();

cout << "\nback() : g1.back() = " << g1.back();

// pointer to the first element

int* pos = g1.data();

cout << "\nThe first element is " << *pos;

return 0;
 functions associated with the vector

Modifiers

assign()  push_back() pop_back() insert() erase() swap() clear() emplace() emplace_back()

It is used to
It is used to It is used to swap It extends the insert a new
It is used to pop It inserts new remove elements the contents of It is used to element into the
It assigns same It pushes the or remove container by
value to the elements into a elements before from a container one vector with remove all the inserting new vector container,
elements from a the element at the from the another vector of elements of the the new element
vector with vector from the vector from the element at
number of times back specified position specified position same type. Sizes vector container position is added to the
back. or range. may differ. end of the vector
1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

9 10
 Sequence Container: List
Introduction
• Vector is sequence containers that allow contiguous memory allocation.
• Insertion and deletion in the middle of the vector is very costly as it takes lot of time in
shifting all the elements. Linklist overcome this problem and it is implemented using list
container.

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

• List supports a bidirectional and provides an efficient way for insertion and deletion
operations
• As compared to vector, list has slow traversal, but once a position has been found, insertion
and deletion are quick.
• List support doubly linked list. For implementing a singly linked list, we use forward list.

24
 functions associated with the Lists

• front() back() push_front(g) push_back(g) pop_front() pop_back()

Adds a new Removes the first Removes the last

• Returns the value Returns the value Adds a new
element ‘g’ at the element of the list, element of the list,
of the first element of the last element element ‘g’ at the
beginning of the and reduces size and reduces size
in the list. in the list . end of the list.
list . of the list by 1. of the list by 1
 functions associated with the Lists

begin() end()  rbegin()  rend() cbegin() cend()  crbegin() crend()

 returns a constant
end() function  returns a constant reverse iterator
 returns a reverse  returns a constant
begin() function returns an iterator reverse iterator which points to
 returns a reverse iterator which random access returns a constant
returns an iterator pointing to the which points to the theoretical
iterator which points to the iterator which random access
pointing to the theoretical last the last element of element preceding
points to the last position before the points to the iterator which points
first element of element which to the end of the list. the list i.e reversed the first element in
element of the list. beginning of the beginning of the
the list follows the last beginning of the list i.e. the
list. list.
element. container.  reverse end of the
list.
 functions associated with the Lists

empty() insert() erase() assign() remove()

Inserts new elements Assigns new elements

Removes a single Removes all the elements
Returns whether the list is in the list before the to list by replacing
element or a range of from the list, which are
empty(1) or not(0). element at a specified current elements and equal to given element.
elements from the list.
position. resizes the list.
 functions associated with the Lists

reverse() size() list resize() sort()

Returns the number of Used to resize a list Sorts the list in

Reverses the list.
elements in the list. container. increasing order.
 functions associated with the Lists

max_size() unique() emplace_front() emplace_back()  clear()

 function is used to
insert a new function is used to
Returns the Removes all element into the insert a new  function is used to
maximum number duplicate list container, the element into the remove all the
of elements a list consecutive new element is list container, the elements of the list
container can elements from the added to the new element is container, thus
hold. list. beginning of the added to the end making it size 0.
list.  of the list.
 functions associated with the Lists
operator= swap() splice() merge() emplace()

This operator is This function is

used to assign used to swap the Used to transfer Extends list by
new contents to contents of one Merges two inserting new
elements from one sorted lists into
the container by list with another list to another. element at a given
replacing the list of same type one position.
existing contents. and size.
 Example
#include <iostream>
#include <list> cout << "\nList 1 (gqlist1) is : ";
#include <iterator> showlist(gqlist1);
using namespace std; cout << "\nList 2 (gqlist2) is : ";
//function for printing the elements in a list showlist(gqlist2);
void showlist(list <int> g) cout << "\ngqlist1.front() : " << gqlist1.front();
{ cout << "\ngqlist1.back() : " << gqlist1.back();
list <int> :: iterator it; cout << "\ngqlist1.pop_front() : ";
for(it = g.begin(); it != g.end(); ++it) gqlist1.pop_front();
cout << '\t' << *it; showlist(gqlist1);
cout << '\n'; cout << "\ngqlist2.pop_back() : ";
} gqlist2.pop_back();
int main() showlist(gqlist2);
{ cout << "\ngqlist1.reverse() : ";
list <int> gqlist1, gqlist2;
gqlist1.reverse();
for (int i = 0; i < 10; ++i)
showlist(gqlist1);
cout << "\ngqlist2.sort(): ";
{
gqlist2.sort();
gqlist1.push_back(i * 2);
showlist(gqlist2);
gqlist2.push_front(i * 3);
return 0;
}
}
31
The output of the above program is :

List 1 (gqlist1) is : 0 2 4 6 8 10 12 14 16 18

List 2 (gqlist2) is : 27 24 21 18 15 12 9 6 3 0

gqlist1.front() : 0

gqlist1.back() : 18

gqlist1.pop_front() : 2 4 6 8 10 12 14 16 18

gqlist2.pop_back() : 27 24 21 18 15 12 9 6 3

gqlist1.reverse() : 18 16 14 12 10 8 6 4 2

gqlist2.sort(): 3 6 9 12 15 18 21 24 27

32
 MCQ
• 1. Which of the following are the components of STL?
A. Algorithms
B. containers
C. function, iterators
D. All of these
• 2. How many Sequence Containers are provided by C++?
a) 2
b) 3
c) 4
d) 5
• 3. Which of the following is to provide a different interface for
sequential containers?
A. container adopters
B. sequence containers
C. queue
D. Associative Containers

• 4. By STL how many components it has been kept?

A. 3
B. 4
C.1
D. unlimited
 Sequence Containers: Deque
Introduction
• In Sequence containers, Deque supports push/pop from both
ends
• In a regular queue, elements are added from the rear and removed
from the front.

• However, in a deque, we can insert and remove elements from both

the front and rear.

35
• Double Ended Queues are basically an implementation of the data
structure double ended queue

• supports random access

• Need to include <deque> header file.

• Elements are not stored contiguously

36
Vector
10 20 30 40

10 20 30 40 50

Deque

10 50
20
30
40

37
 Methods of Deque

• deque insert() • rbegin() • rend() • cbegin() • max_size() • assign() • resize()

• Returns a reverse •Returns a constant

• Inserts an • Returns a reverse iterator which iterator pointing to • Returns the
element. And iterator which points to the the first element of maximum number • Assign values to • Function which
returns an iterator points to the last position before the the container, that of elements that a the same or changes the size of
that points to the element of the beginning of the is, the iterator deque container different deque the deque.
first of the newly deque (i.e., its deque (which is cannot be used to can hold. container.
inserted elements. reverse beginning). considered its modify, only
reverse end). traverse the deque.
 Methods of Deque

• push_front() • push_back() • pop_front() • pop_back()  • front()  • back()  • clear() •  erase() • empty()  • size()

• Is used to return
• Is used to remove •Is used to remove • Is used to check the size of the
• This function is • This function is •  Is used to pop or • Is used to pop or • Is used to • Is used to elements from a
used to push all the elements of if the deque deque container or
used to push remove elements remove elements reference the first reference the last container from the
elements into a the deque container is empty the number of
elements into a from a deque from from a deque from element of the element of the specified position
deque from the container, thus or not.  elements in the
deque from the the front.  the back. deque container.  deque container. or range.
front. making its size 0. deque container.
back.
Example

OUTPUT

40
MCQ

41
What is the correct output of the given code snippets?

42
 Sequence Containers: Array

🞂The introduction of array class from C++11 has offered a better alternative for
C-style arrays. The advantages of array class over C-style array are :-
🞂Array classes knows its own size, whereas C-style arrays lack this property. So
when passing to functions, we don’t need to pass size of Array as a separate
parameter.
🞂With C-style array there is more risk of array being decayed into a pointer.
Array classes don’t decay into pointers
🞂Array classes are generally more efficient, light-weight and reliable than C-
style arrays.
 Operations on array

at()  get()  operator[] 

This function is This is similar to

This function is not the member C-style arrays.
This function is
also used to of array class This method is
used to access
access the but overloaded also used to
the elements of
elements of function from access array
array.
array. class tuple. elements.
Array get() function in C++ STL
• The array::get() is a built-in function in C++ STL which returns a reference to the i-th
element of the array container.
• Syntax:
• get(array_name) Parameters: The function accepts two mandatory parameters which are
described below.
• i – position of an element in the array, with 0 as the position of the first element.
• arr_name – an array container.
• Return Value: The function returns a reference to the element at the specified position in the
array
• Time complexity: O(1)
// // C++ code to demonstrate working of array, to() and get()
#include<iostream>
#include<array> // for array, at()
#include<tuple> // for get()
using namespace std;
int main()
{
// Initializing the array elements
array<int,6> ar = {1, 2, 3, 4, 5, 6};

// Printing array elements using at()

cout << "The array elements are (using at()) : ";
for ( int i=0; i<6; i++) Output:
cout << ar.at(i) << " "; The array elements are (using at()) : 1 2 3 4 5 6
cout << endl; The array elements are (using get()) : 1 2 3 4 5 6
The array elements are (using operator[]) : 1 2 3 4
// Printing array elements using get() 5 6
cout << "The array elements are (using get()) : ";
cout << get<0>(ar) << " " << get<1>(ar) << " ";
cout << get<2>(ar) << " " << get<3>(ar) << " ";
cout << get<4>(ar) << " " << get<5>(ar) << " ";
cout << endl;

// Printing array elements using operator[]

cout << "The array elements are (using operator[]) : ";
for ( int i=0; i<6; i++)
cout << ar[i] << " ";
cout << endl;

return 0; }
 Operations on array

front()  back()

This returns the This returns the

first element of last element of
array. array.
// C++ code to demonstrate working of front() and back()
#include<iostream>
#include<array> // for front() and back()
using namespace std;
int main()
{
// Initializing the array elements
array<int,6> ar = {1, 2, 3, 4, 5, 6};
Output:
First element of array is : 1
// Printing first element of array Last element of array is : 6
cout << "First element of array is : ";
cout << ar.front() << endl;

// Printing last element of array

cout << "Last element of array is : ";
cout << ar.back() << endl;

return 0;

}
 Operations on array

size()  max_size() 

It returns the number of elements in It returns the maximum number of

array. This is a property that C-style elements array can hold i.e, the size
arrays lack. with which array is declared.
// C++ code to demonstrate working of size() and max_size()
#include<iostream>
#include<array> // for size() and max_size()
using namespace std;
int main()
{
// Initializing the array elements Output:
array<int,6> ar = {1, 2, 3, 4, 5, 6}; The number of array elements is : 6
Maximum elements array can hold is : 6
// Printing number of array elements
cout << "The number of array elements is : ";
cout << ar.size() << endl;

// Printing maximum elements array can hold

cout << "Maximum elements array can hold is : ";
cout << ar.max_size() << endl;

return 0;

}
 swap() :- The swap() swaps all elements of one array with other.
for (int i=0; i<6; i++)
// C++ code to demonstrate working of swap()
cout << ar1[i] << " ";
#include<iostream>
cout << endl;
#include<array> // for swap() and array
// Swapping ar1 values with ar
using namespace std;
int main() ar.swap(ar1);
{
// Printing 1st and 2nd array after swapping
// Initializing 1st array cout << "The first array elements after
array<int,6> ar = {1, 2, 3, 4, 5, 6}; swapping are : ";
for (int i=0; i<6; i++)
// Initializing 2nd array cout << ar[i] << " ";
array<int,6> ar1 = {7, 8, 9, 10, 11, 12}; cout << endl;
cout << "The second array elements after
// Printing 1st and 2nd array before swapping swapping are : ";
cout << "The first array elements before swapping are : "; for (int i=0; i<6; i++)
for (int i=0; i<6; i++) cout << ar1[i] << " ";
cout << ar[i] << " "; cout << endl;
cout << endl; return 0;
cout << "The second array elements before swapping are : "; }
Output:
The first array elements before swapping are : 1 2 3 4 5 6
The second array elements before swapping are : 7 8 9 10 11 12
The first array elements after swapping are : 7 8 9 10 11 12
The second array elements after swapping are : 1 2 3 4 5 6
 Operations on array

empty()  fill()

This function returns true This function is used to fill

when the array size is zero the entire array with a
else returns false. particular value.
// C++ code to demonstrate working of empty() and fill()

#include<iostream>
#include<array> // for fill() and empty()
using namespace std;
int main()
{
array<int,6> ar; // Declaring 1st array
array<int,0> ar1; // Declaring 2nd array
ar1.empty()? cout << "Array empty": cout << "Array not empty";
cout << endl; // Checking size of array if it is empty
ar.fill(0); // Filling array with 0
// Displaying array after filling
cout << "Array after filling operation is : ";
for ( int i=0; i<6; i++)
cout << ar[i] << " ";
return 0;
}
Output:
Array empty
Array after filling operation is : 0 0 0 0 0 0
MCQ

1.Which of the following does not support any insertion or deletion?

a) Array
b) Vector
c) Dequeue
d) List

2) Which of the following header file is required to use deque container in C+

+?
a)<queue>
b)<deque>
c)<dqueue>
d)<cqueue>

3) What is the correct output of the given code snippets?

a)10 20 30
b)Garbage Value
c)Syntax error
d)Runtime error
4.Which of the following class template are based on arrays?
a) vector
b) list
c) dequeue
d) both vector & dequeue
Topic : STL Stack
 STL Stack

• Stacks are a type of container adaptors with LIFO(Last In First Out) type of working, where a new element is
added at one end and (top) 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 Syntax:-
• 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.

 
 Functions associated with stack

empty() size() top() push(g) pop()

Returns a reference
Returns whether the Returns the size of Adds the element ‘g’ Deletes the top most
to the top most
stack is empty the stack at the top of the stack element of the stack
element of the stack

Time Complexity : Time Complexity : Time Complexity : Time Complexity : Time Complexity :
O(1) O(1) O(1) O(1) O(1)
 List of functions of Stack
•top()

•empty()

•push()

•swap()

•emplace()
Example:
#include <iostream>
#include <stack> 25
using namespace std; 24
int main() { 22
    stack<int> stack; 21
    stack.push(21);
    stack.push(22);
   stack.push(24);
   stack.push(25);
       
stack.pop();
    stack.pop();   
    while (!stack.empty()) {
        cout << stack.top() <<" "; OUTPUT :
        stack.pop(); 22
    }
21
}
// CPP program to demonstrate working of STL stack
#include <iostream> cout << "The stack is : ";
#include <stack> showstack(s);
using namespace std;
cout << "\ns.size() : " << s.size();
void showstack(stack <int> s) cout << "\ns.top() : " << s.top();
{
while (!s.empty())
{ cout << "\ns.pop() : ";
cout << '\t' << s.top();
s.pop();
s.pop();
} showstack(s);
cout << '\n';
} return 0;
}
int main ()
{
stack <int> s; Output:
s.push(10); The stack is : 1 5 20 30 10
s.push(30); s.size() : 5
s.push(20); s.top() : 1
s.pop() : 5 20 30 10
s.push(5);
s.push(1);
 // Application of top() function
#include <iostream>
stack::top() top() function is used to
#include <stack>
reference the top(or the newest) using namespace std;
element of the stack.  
Syntax :   int main()
{
stackname.top()     int sum = 0;
Parameters: No value is needed to     stack<int> mystack;
pass as the parameter.     mystack.push(1);
    mystack.push(8);
Return Value: Direct reference to the     mystack.push(3);
top element of the stack     mystack.push(6);
OUTPUT
container.     mystack.push(2); 
SUM= ?
    // Stack becomes 1, 8, 3, 6, 2
  while (!mystack.empty()
OUTPUT : 20 {
sum = sum + mystack.top();
Time Complexity:  O(n)    mystack.pop();
Auxiliary Space:  O(n)     }
    cout << “SUM=“<<sum;
    return 0;
}
1. What is the Standard Template Library?
a) Set of C++ template classes to provide common programming data structures and functions
b) Set of C++ classes
c) Set of Template functions used for easy data structures implementation
d) Set of Template data structures only.
Answer: a
STL expanded as Standard Template Library is set of C++ template classes to provide common
programming data structures and functions.

2. How many components STL has?

a) 1
b) 2
c) 3
d) 4
Answer : d

3. What are Container Adaptors?

a) Containers that implements data structures which can be accessed sequentially
b) Containers that implements sorted data structures for fast search in O(logn)
c) Containers that implements unsorted(hashed) data structures for quick search in O(1)
d) Containers that provide a different interface for sequential containers.
Answer: d
Container Adaptors is the subset of Containers that provides a different interface for sequential containers.
 Algorithms

• Retrieve or Non-mutating Algorithms

• Mutating Algorithms
• Sorting Algorithms
• Set Algorithms
• Relational Algorithms
 Non Mutating Algorithms
• Adjacent_find –adj pairs
• Count-occurrence of a value
• Count_if—no.of elements that matches a predicate
• Equal-if two ranges are equal
• Find-first occurrence of a value
• Find_end
• Find_first_of()
• Find_if()- find the elements that matches a predicate
• For_each()- apply an operation to each element
• Mismatch()
• Search_ch()
• Search_n()
 Mutating Algorithms

• Copy()
• Copy_backward()
Algorithms : find()
 Algorithm: count()
• count() returns the number of elements in the
given range that are equal to given value.
• Syntax for count is:
• count(first ,last ,value) : This will return
number of the element in range defined
• by iterators first and last ( excluded ) which
are equal ( == ) the value
 Count_If() Algorithm
count_if() function returns the number of elements in a range that satisfy the condition.

int main()
#include <bits/stdc++.h> {
using namespace std; vector<int> v;
for (int i = 0; i < 10; i++)
{
// Function to check the v.push_back(i);
// number is even or odd }
bool isEven(int i) int noEven = count_if(v.begin(), v.end(), isEven);
{
if (i % 2 == 0) cout << "Total no of even numbers is: "<< noEven;

return true; return 0;

else }
return false;
}
Algorithms : search
• This function is used to perform searches for a given sequence in a
given range. There are two variations of the search():

• search(first1 ,last1 ,first2 ,last2) : This function searches for the

sequence defined by first2 and last2 in the range first1 and
last1(where last1 is excluded). If there is a match an iterator to the
first element of the sequence in the range [first1,last1] is returned,
else iterator to last1 is returned.
• search(first1 ,last1 ,first2 ,last2 ,cmp_functions) : Here
cmp_function is used to decide how to check the equality of two
elements, it is useful for non-numeric elements like strings and
objects.

7
Algorithms : sort()
• This function of the STL, sorts the contents of the given range.
There are two version of sort() :
• sort(start_iterator, end_iterator ) : sorts the range defined by
iterators start_iterator and end_iterator in ascending order.
• sort(start_iterator, end_iterator, compare_function) : this also
sorts the given range but you can define how the sorting should be
done by compare_function.

9
Algorithms : sort() Example 1
#include<iostream> v1.push_back(5);
#include<algorithm> v1.push_back(1);
#include<vector>
/* now the vector v1 is 8,4,5,1 */
using namespace std;
vector<int>::iterator i, j;
bool compare_function(int i, int j)
i = v1.begin(); // i now points to beginning of the vector v1
{
return i > j; // return 1 if i>j else 0 j = v1.end(); // j now points to end of the vector v1
} sort(i,j); //sort(v1.begin() , v1.end() ) can also be used
bool compare_string(string i, string j)
{ /* now the vector v1 is 1,4,5,8 */
return (i.size() < j.size()); /* use of compare_function */
}
int a2[] = { 4,3,6,5,6,8,4,3,6 };
int main() sort(a2,a2+9,compare_function); // sorts a2 in descending order
{
/* here we have used compare_function which uses operator(>),
int arr[5] = {1,5,8,4,2}; that result into sorting in descending order */
sort(arr , arr+5);
// sorts arr[0] to arr[4] in ascending order
/* compare_function is also used to sort
/* now the arr is 1,2,4,5,8 */
non-numeric elements such as*/
vector<int> v1;
string s[]={"a" , "abc", "ab" , "abcde"};

v1.push_back(8); sort(s,s+4,compare_string);
v1.push_back(4); /* now s is "a","ab","abc","abcde" */
}

10
 Algorithm: merge()
Combines the elements in the sorted ranges [first1,last1) and [first2,last2), into a new range beginning at result with all its elements
sorted.

Syntax:
OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
 for_each
#include <iostream>
#include <algorithm>
using namespace std; Syntax :
void in_to_cm(double); //declaration Function for_each (InputIterator
int main() first, InputIterator last, Function fn);
{ //array of inches values
double inches[] = { 3.5, 6.2, 1.0, 12.75, 4.33 };
//output as centimeters
for_each(inches, inches+5, in_to_cm); The for_each() algorithm allows
cout << endl; you to do something to every item
return 0; in a container. You write your
}
void in_to_cm(double in) //convert and display as
own function to determine what
centimeters that “something” is. Your function
{ can’t change the elements in the
cout << (in * 2.54) << ‘ ‘; container, but it can use or display
} their values.
The output looks like this:
8.89 15.748 2.54 32.385 10.9982}

11
 Transform()
#include <iostream>
#include <algorithm> The transform() algorithm does something
using namespace std; to every item in a container, and places the
int main() resulting values in a different container (or
{ //array of inches values the same one).
double inches[] = { 3.5, 6.2, 1.0, 12.75, 4.33 }; Again, a user-written function determines
double centi[5]; what will be done to each item. The return
double in_to_cm(double); //prototype type of this function must be the same as
//transform into array centi[] that of the destination container.
transform(inches, inches+5, centi, in_to_cm);
for(int j=0; j<5; j++) //display array centi[]
cout << centi[j] << ‘ ‘;
cout << endl; Syntax:
return 0; OutputIterator transform (InputIterator
} first1, InputIterator last1,
double in_to_cm(double in) //convert inches to
centimeters
OutputIterator result, UnaryOperation
{ op);
return (in * 2.54); //return result
}
 STL ALgorithms

• STL has an ocean of algorithms, for all < algorithm > library functions
• Some of the most used algorithms on vectors and most useful one’s in Competitive
Programming are mentioned as follows :
– sort(first_iterator, last_iterator) – To sort the given vector.
– reverse(first_iterator, last_iterator) – To reverse a vector.
– *max_element (first_iterator, last_iterator) – To find the maximum element of a vector.
– *min_element (first_iterator, last_iterator) – To find the minimum element of a vector.
– accumulate(first_iterator, last_iterator, initial value of sum) – Does the summation of
vector elements
 // Reversing the Vector
// A C++ program to demonstrate working of sort(), reverse() reverse(vect.begin(), vect.end());
#include <algorithm>
#include <iostream> cout << "\nVector after reversing is: ";
#include <vector> for (int i=0; i<6; i++)
#include <numeric> //For accumulate operation cout << vect[i] << " ";
using namespace std;
cout << "\nMaximum element of vector is: ";
int main() cout << *max_element(vect.begin(), vect.end());
{
// Initializing vector with array values cout << "\nMinimum element of vector is: ";
int arr[] = {10, 20, 5, 23 ,42 , 15}; cout << *min_element(vect.begin(), vect.end());
int n = sizeof(arr)/sizeof(arr[0]);
vector<int> vect(arr, arr+n); // Starting the summation from 0
cout << "\nThe summation of vector elements is: ";
cout << "Vector is: "; cout << accumulate(vect.begin(), vect.end(), 0);
for (int i=0; i<n; i++)
cout << vect[i] << " "; return 0;
}
// Sorting the Vector in Ascending order
sort(vect.begin(), vect.end()); Output:
Vector before sorting is: 10 20 5 23 42 15 Vector after sorting is:
cout << "\nVector after sorting is: "; 5 10 15 20 23 42 Vector before reversing is: 5 10 15 20 23 42
for (int i=0; i<n; i++) Vector after reversing is: 42 23 20 15 10 5 Maximum element of
cout << vect[i] << " "; vector is: 42
Minimum element of vector is: 5
The summation of vector elements is: 115
count(first_iterator, last_iterator,x) – To count the occurrences of x in vector.
find(first_iterator, last_iterator, x) – Points to last address of vector ((name_of_vector).end()) if element is not
present in vector.

// C++ program to demonstrate working of count() and find()

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
// Initializing vector with array values
int arr[] = {10, 20, 5, 23 ,42, 20, 15};
int n = sizeof(arr)/sizeof(arr[0]);
vector<int> vect(arr, arr+n);

cout << "Occurrences of 20 in vector : ";

// Counts the occurrences of 20 from 1st to last element

cout << count(vect.begin(), vect.end(), 20);
// find() returns iterator to last address if element not present
find(vect.begin(), vect.end(),5) != vect.end()? cout << "\nElement found": cout << "\nElement not found";

return 0;
}

Output:
Occurrences of 20 in vector: 2
Element found
Topic :Associative Containers: Map,
Multimap
 Associative Containers: Map, Multimap

• STL components are now part of standard c++

library defined in namespace std

• The standard template library (STL) contains

– Containers
– Algorithms
– Iterators
 Containers supported by STL
Containers are objects that hold data
 Associative containers

• They are designed to support direct access to elements using keys

not sequential
• There are four types
– Set
– Multiset
– Map
– Multimap
• Store data in a structure called tree which facilitates fast searching,
deletion and insertion
• Slow for random access and inefficient for sorting
 Associative Container
• Associative containers implement sorted data structures that
can be quickly searched (O(log n) complexity).
• Set collection of unique keys, sorted by keys
• map collection of key-value pairs, sorted by keys, keys are
unique

• Multiset collection of keys, sorted by keys

• Multimap collection of key-value pairs, sorted by keys
 Associative containers

• Set and Multiset

– Store number of items and provide operations
for manipulating them using the values as keys
– Difference between set and multiset
• Multiset allows duplicates , but set does not allow
– Map and multimap
• Used to store pairs of items – one called the key
and the other called the value
– Difference between map and multimap
• Map allows only one key for a given value while
multimap permits multiple keys
 Maps

• Maps are associative containers that store elements in a

mapped fashion. Each element has a key value and a mapped
value. No two mapped values can have the same key values.
• Associative container that associates objects of type Key with
objects of type Data
– Sorted according to keys

• Map
– Stores (key, object) pairs
– Unimodal: duplicate keys not allowed
– table, associative array
Member Functions
#include <iostream>
#include <map>
using namespace std; while (it != m.end())
{
cout << "Key: " << it->first << ", Value: " << it->second << endl;
int main() ++it;
{ }
// Create a map of strings to
integers cout<<"TWO="<<m["two"]<<endl;
map<string, int> m; it=m.find("three");
cout << "KEY=" << it->first<< ", VALUE: " << it->second << endl;
// Insert some values into the
map return 0;
m["one"] = 1; } OUTPUT
m["two"] = 2;
m["three"] = 3;

map<string, int>::iterator it;

it = m.begin();
#include <iostream>
#include <map> cout<<"Assign the values of m into n map"<<endl;
using namespace std; map<int, string> n(m.begin(), m.end());

int main () for (itr = n.begin(); itr != n.end(); ++itr)

{ {
map <int, string> m; cout << '\t' << itr->first << '\t' << itr->second<< '\n';
m.insert(pair<int, string>(1,"Apple")); }
m.insert(pair<int, string>(2,"Orange"));
m.insert(pair<int, string>(3,"Banana")); cout<<"Erase the value at specified position in n map"<<endl;
map<int, string>::iterator itr; int num;
cout << m.at(1)<<endl ; num = n.erase(1);
for (itr = n.begin(); itr != n.end(); ++itr)
cout << m.at(2) <<endl;
{
cout << m[3]<<endl ; cout << '\t' << itr->first << '\t' << itr->second<< '\n';
cout<<"Changes the value associated with key"<<endl; }
m.at(1) = "Mango"; }
m[2] = "Grapes";

for (itr = m.begin(); itr != m.end(); ++itr)

{
cout << '\t' << itr->first << '\t' << itr->second<< '\n';
}
 Multimap
Multimap is similar to a map with the addition that multiple elements can have the same
keys. Also, it is NOT required that the key-value and mapped value pair have to be unique
in this case.

One important thing to note about multimap is that multimap keeps all the keys in sorted
order always.

These properties of multimap make it very much useful in competitive programming.

#include <iostream> Example // adding elements randomly,
#include <iterator> gquiz1.insert(pair<int, int>(4, 50));
#include <map> gquiz1.insert(pair<int, int>(5, 10));
using namespace std;
cout << "\nThe multimap gquiz1 after adding extra elements is : \
int main() n";
{ cout << "\tKEY\tELEMENT\n";
multimap<int, int> gquiz1; // empty multimap container for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr)
{
gquiz1.insert(pair<int, int>(1, 40)); cout << '\t' << itr->first << '\t' << itr->second << '\n';
gquiz1.insert(pair<int, int>(2, 30)); }
gquiz1.insert(pair<int, int>(3, 60)); cout << endl;
gquiz1.insert(pair<int, int>(6, 50));
gquiz1.insert(pair<int, int>(6, 10)); // assigning the elements from gquiz1 to gquiz2
multimap<int, int> gquiz2(gquiz1.begin(), gquiz1.end());
// printing multimap gquiz1
multimap<int, int>::iterator itr; cout << "\nThe multimap gquiz2 after assign from gquiz1 is : \n";
cout << "\nThe multimap gquiz1 is : \n"; cout << "\tKEY\tELEMENT\n";
cout << "\tKEY\tELEMENT\n"; for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr)
for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) {
{ cout << '\t' << itr->first << '\t' << itr->second << '\n';
cout << '\t' << itr->first << '\t' << itr->second << '\n'; }
} cout << endl;
cout << endl;
// remove all elements up to key with value 3 in gquiz2
cout << "\ngquiz2 after removal of elements less than "
"key=3 : \n"; // lower bound and upper bound for multimap gquiz1 key = 5
cout << "\t KEY \t ELEMENT\n"; cout << "gquiz1.lower_bound(5) : " << "\tKEY = ";
gquiz2.erase(gquiz2.begin(), gquiz2.find(3)); cout << gquiz1.lower_bound(5)->first << '\t';
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) cout << "\tELEMENT = " << gquiz1.lower_bound(5)->second
{ << endl;
cout << '\t' << itr->first << '\t' << itr->second << '\n';
} cout << "gquiz1.upper_bound(5) : " << "\tKEY = ";
cout << gquiz1.upper_bound(5)->first << '\t';
// remove all elements with key = 4 cout << "\tELEMENT = " << gquiz1.upper_bound(5)->second
int num; << endl;
num = gquiz2.erase(4);
cout << "\ngquiz2.erase(4) : "; return 0;
cout << "\t KEY \t ELEMENT\n"; }
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr)
{
cout << '\t' << itr->first << '\t' << itr->second << '\n';
}

cout << endl;

 Multi Set Example-2
#include<iostream>
#include <set>
using namespace std;
int main()
{
// multiset declare
multiset<int> s;
// Elements added to set
s.insert(12);
s.insert(10);
s.insert(2);
s.insert(10); // duplicate added
s.insert(90);
s.insert(85);
s.insert(75);
s.insert(90);
s.insert(95);
s.insert(45);
s.insert(80);
s.insert(45);
 Function Objects
• Functors (Function Objects or Functionals) are simply put object + ().
• In other words, a functor is any object that can be used with () in the
manner of a function.
• This includes normal functions, pointers to functions, and class objects
for which the () operator (function call operator) is overloaded, i.e.,
classes for which the function operator()() is defined.
• Sometimes we can use a function object when an ordinary function
won't work. The STL often uses function objects and provides several
function objects that are very helpful.
• Function objects are another example of the power of generic
programming and the concept of pure abstraction. We could say that
anything that behaves like a function is a function. So, if we define an
object that behaves as a function, it can be used as a function.
 Function Objects
#include <iostream>
#include<vector>>
#include <algorithm>
using namespace std;
class InCm {
public:
void operator()(double in)
{
cout << (in * 2.54) << " ";
}
};
int main()
{
vector<double> inches;
inches.push_back(3.5);
inches.push_back(7);

InCm in_to_cm;

for_each (inches.begin(), inches.end(), in_to_cm);

cout << endl;
return 0;
}
 Advantages of function object

• Function object are "smart functions."

• Each function object has its own type.

• Function objects are usually faster than

ordinary functions.
 MCQ
• Which container can have the same keys?
a) map
b) multimap
c) unordered map
d) set
Answer: b
• Which container is used to keep priority based elements?
a) queue
b) stack
c) set
d) priority queue
Answer: d
 MCQ
• How many components STL has?
a) 1
b) 2
c) 3
d) 4
Answer: d
Explanation: STL has four components namely Algorithms, Containers, Functors and Iterators.
▪ Which of the following is correct about map and multimap?
a) Map can have same keys whereas multimap cannot
b) Implementation of maps and multimap are different
c) Multimap can have same keys whereas the map cannot
d) Average search time of map is greater than multimap
Answer: c
 MCQ

•  Which header is need to be used with

function objects?
a) <function>
b) <functional>
c) <funct>
d) <functionstream>
Answer: b
Explanation: <functional> header is need
to be used with function objects.
Topic :STL Iterators
 STL has
four
components

Containers Iterators Algorithms Functions

 STL 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

begin() end()

This function is used to This function is used to

return the beginning return the after end
position of the position of the
container. container.
// C++ code to demonstrate the working of iterator, begin() and end()

#include<iostream>
#include<iterator> // for iterators
#include<vector> // for vectors
using namespace std;

int main()
{
vector<int> ar = { 1, 2, 3, 4, 5 }; Output:
The vector elements are : 1 2 3 4 5
// Declaring iterator to a vector
vector<int>::iterator ptr;

// Displaying vector elements using begin() and end()

cout << "The vector elements are : ";

for (ptr = ar.begin(); ptr < ar.end(); ptr++)

cout << *ptr << " ";

return 0;
}
advance() :- This function is used to increment the iterator position till the specified number mentioned in its arguments.

// C++ code to demonstrate the working of advance()

#include<iostream>
#include<iterator> // for iterators
#include<vector> // for vectors
using namespace std;
int main()
{
vector<int> ar = { 1, 2, 3, 4, 5 };

// Declaring iterator to a vector

vector<int>::iterator ptr = ar.begin();
Output:
// Using advance() to increment iterator position points to 4 The position of iterator after advancing is : 4
advance(ptr, 3);

// Displaying iterator position

cout << "The position of iterator after advancing is : ";
cout << *ptr << " ";

return 0;

}
 Operations of iterators

next()  prev() 

This function returns the new This function returns the new

iterator that the iterator would iterator that the iterator would
point after advancing the point after decrementing the
positions mentioned in its positions mentioned in its
arguments. arguments.
// C++ code to demonstrate the working of next() and prev()
#include<iostream>
#include<iterator> // for iterators
#include<vector> // for vectors
// Displaying iterator position
using namespace std;
cout << "The position of new iterator using next() is : ";
int main()
cout << *it << " ";
{
cout << endl;
vector<int> ar = { 1, 2, 3, 4, 5 };
// Displaying iterator position
// Declaring iterators to a vector
cout << "The position of new iterator using prev() is : ";
vector<int>::iterator ptr = ar.begin();
cout << *it1 << " ";
vector<int>::iterator ftr = ar.end();
cout << endl;

return 0;
// Using next() to return new iterator points to 4
}
auto it = next(ptr, 3);

// Using prev() to return new iterator points to 3

auto it1 = prev(ftr, 3);
Output:
The position of new iterator using next() is : 4
The position of new iterator using prev() is : 3
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.
// C++ code to demonstrate the working of inserter()
#include<iostream>
#include<iterator> // for iterators
#include<vector> // for vectors
using namespace std;
int main()
{
vector<int> ar = { 1, 2, 3, 4, 5 };
vector<int> ar1 = {10, 20, 30};

vector<int>::iterator ptr = ar.begin(); // Declaring iterator to a vector

advance(ptr, 3); // Using advance to set position

// copying 1 vector elements in other using inserter(), inserts ar1 after 3rd position in ar
copy(ar1.begin(), ar1.end(), inserter(ar,ptr));

// Displaying new vector elements

cout << "The new vector after inserting elements is : ";
for (int &x : ar)
cout << x << " ";
Output:
return 0; The new vector after inserting elements is : 1 2 3 10 20 30 4 5
}
 Types of Iterator

std::find, std::equal,  std::copy, std::move, std::transform

std::count,

std::search, std::search_n,
std::lower_bound
std::reverse,
std::next_permutation and
std::reverse_copy

std::nth_element,
std::sort
 for_each() in STL
// for_each example
#include <iostream> // std::cout
• Apply function to range
#include <algorithm> // std::for_each
• Applies function fn to each of the elements in the #include <vector> // std::vector
range [first,last). void myfunction (int i) { // function:
• The behavior of this template function is equivalent to: std::cout << ' ' << i;
}
struct myclass { // function object type:
void operator() (int i) {std::cout << ' ' << i;}
} myobject;
int main () Output:
{ myvector contains: 10 20 30
std::vector<int> myvector; myvector contains: 10 20 30
myvector.push_back(10);
myvector.push_back(20);
• Parameters myvector.push_back(30);
first, last std::cout << "myvector contains:";
✔ Input iterators to the initial and final positions in a sequence. The range used is
[first,last), which contains all the elements between first and last, including the
for_each (myvector.begin(), myvector.end(), myfunction);
element pointed by first but not the element pointed by last.
Fn std::cout << '\n';
✔ Unary function that accepts an element in the range as argument. // or:
This can either be a function pointer or a move constructible function object. std::cout << "myvector contains:";
Its return value, if any, is ignored. for_each (myvector.begin(), myvector.end(), myobject);
std::cout << '\n';
return 0;
}
Functors in C++
 Function objects
• Consider a function that takes only one argument.
• However, while calling this function we have a lot more information that we
would like to pass to this function, but we cannot as it accepts only one
parameter. What can be done?
• One obvious answer might be global variables.
• However, good coding practices do not advocate the use of global variables
and say they must be used only when there is no other alternative.
• Functors are objects that can be treated as though they are a function or
function pointer.
• Functors are most commonly used along with STLs.
The functor allows an instance object of some class to be called
as if it were an ordinary function.
• Let us consider a function that takes one argument. We can use
this function as function object to do some task on a set of
data
#include <iostream> Output
#include <algorithm>
using namespace std;
int square(int x)
{

   return x*x; //return square of x

}
int main()
{
   int data[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  
transform(data, data+10, data, square);// array name, elements, name, square
and store

   for (int i = 0; i<10; i++)

      cout << data[i] << endl;
}
// A C++ program uses transform() in STL to add 1 to all elements of arr[]
#include <bits/stdc++.h>
using namespace std;

int increment(int x) { return (x+1); }

int main()
{
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr)/sizeof(arr[0]); Output:
2 3 4 5 6
// Apply increment to all elements of
// arr[] and store the modified elements
// back in arr[]
transform(arr, arr+n, arr, increment);

for (int i=0; i<n; i++)

cout << arr[i] << S" ";

return 0;
}