1

Object-Oriented Programming:
Standard Template Library
(STL)
 2

STL – Standard Template Library

• The Standard Template Library defines powerful,

template-based, reusable components
- That implements common data structures and algorithms

• STL extensively uses generic programming based on

templates

• Divided into three components:

- Containers: data structures that store objects of any type
- Iterators: used to manipulate container elements
- Algorithms: searching, sorting and many others
 3

STL – Standard Template Library

• STL consists of 10 container classes:
– Sequence containers
– Adapter containers
– Associative 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
 4

Why use STL: A motivating example

• Lets take an example of a simple graph traversal Breadth-first Search.
• For BFS you need to have knowledge of the following:-
– List - To make an Adjacency List
– Queue - To traverse through the nodes.
• Now, if you're implementing BFS from scratch without using STL.
struct LinkedListNode {
int data;
LinkedListNode *next;
};

struct Queue{
LinkedListNode *array;
int front, rear;
int size;
};
 5

Why use STL: A motivating example

• You need to implement these two structures with following basic
functionality:-
• LinkedListNode
– createNode() : To allocate memory to each Node.
– insertNode() : To insert an element in the List.
– deleteNode() : To delete an element from the List.
• Queue
– enqueue() : To insert an element at the end of the Queue.
– dequeue() : To delete an element from the front of the Queue.
– isEmpty() : To check if the Queue is empty.
• And now you need to create an array of LinkedListNode to form an
adjacency List.
 6

Why use STL: A motivating example

• But, if you have a little knowledge of STL. You can
implement the following things in a much easier way.

• vector< list<int> > adjacencyList;

• queue<int> q;

• That's right. It's done. The required functionality of

LinkedListNode is already implemented in list<int>.
• Also, required functionality of Queue is already implemented
in queue<int>.
 7

Why use STL: Another example

• Let’s take, If in a part of problem statement , you need to find last
occurrence of a particular string then , in normal circumstances, you
will write subroutine and use it.
• Instead of reinventing the wheel, you can just use find_last_of function
in C++ STL.
• There are two advantages of using C++ STL in CP:
– No need to reinvent the wheel, unless problem specifically tells us to
write new one.
– Most importantly, you don’t have to worry about whether STL function
will work perfectly or not because they are already thoroughly tested.
– may be you can easily write a function for sort/first occurrence or any
petty requirement but just imagine of participating in Hackathon / online
contests, then you will know how these readily available functions help,
as those competitions strictly time constrained.
 8

Why use STL

• The standard template library (STL) contains
– Containers
– Algorithms
– Iterators
• A container is a way that stored data is organized in memory,
for example an array of elements.
• Algorithms in the STL are procedures that are applied to
containers to process their data, for example search for an
element in an array, or sort an array.
• Iterators are a generalization of the concept of pointers, they
point to elements in a container, for example you can
increment an iterator to point to the next element in an array
 9

Containers, Iterators, Algorithms

• Algorithms use iterators to interact with objects stored in
containers
 10

Containers
• A container is a way to store data, either built-in data types like
int and float, or class objects
• The STL provides several basic kinds of containers
– <vector> : one-dimensional array
– <list> : double linked list
– <deque> : double-ended queue
– <queue> : queue
– <stack> : stack
– <set> : set of ordered keys
– <map> : associative array (set of ordered key/value pairs)
– etc..
 11

Sequence Containers
• A sequence container stores a set of elements in sequence, in
other words each element (except for the first and last one) is
preceded by one specific element and followed by another,
<vector>, <list> and <deque> are sequential containers
• In an ordinary C++ array the size is fixed and can not change
during run-time, it is also tedious to insert or delete elements.
• Advantage: quick random access
• <vector> is an expandable array that can shrink or grow in
size, but still has the disadvantage of inserting or deleting
elements in the middle Vector should be your default choice.
 12

Sequence Containers
• Certain functions associated with the vector are:
• begin() – Returns an iterator pointing to the first element in the vector
• end() – Returns an iterator pointing to the theoretical element that follows the
last element in the vector
• rbegin() – Returns a reverse iterator pointing to the last element in the vector
(reverse beginning). It moves from last to first element
• rend() – Returns a reverse iterator pointing to the theoretical element
preceding the first element in the vector (considered as reverse end)
• cbegin() – Returns a constant iterator pointing to the first element in the
vector.
• cend() – Returns a constant iterator pointing to the theoretical element that
follows the last element in the vector.
• crbegin() – Returns a constant reverse iterator pointing to the last element in
the vector (reverse beginning). It moves from last to first element
• crend() – Returns a constant reverse iterator pointing to the theoretical
element preceding the first element in the vector (considered as reverse end)
 13

Sequence Containers
• <list> is a ’traditional’ double linked list (each element has points
to its successor and predecessor), it is quick to insert or delete
elements but has slow random access
• Functions used with List:
– front() – Returns the value of the first element in the list.
– back() – Returns the value of the last element in the list .
– push_front(g) – Adds a new element ‘g’ at the beginning of the list .
– push_back(g) – Adds a new element ‘g’ at the end of the list.
– pop_front() – Removes the first element of the list, and reduces size of the list by 1.
– pop_back() – Removes the last element of the list, and reduces size of the list by 1
– list::begin() and list::end()– begin() function returns an iterator pointing to the first
element of the list
– end(): function returns an iterator pointing to the theoretical last element which
follows the last element.
 14

Sequence Containers
• list rbegin() and rend() – rbegin() returns a reverse iterator which points to the last
element of the list. rend() returns a reverse iterator which points to the position before
the beginning of the list.
• list cbegin() and cend() – cbegin() returns a constant random access iterator which
points to the beginning of the list. cend() returns a constant random access iterator
which points to the end of the list.
• list crbegin() and crend() – crbegin() returns a constant reverse iterator which points to
the last element of the list i.e reversed beginning of container. crend() returns a constant
reverse iterator which points to the theoretical element preceding the first element in the
list i.e. the reverse end of the list.
• empty() – Returns whether the list is empty(1) or not(0).
• insert() – Inserts new elements in the list before the element at a specified position.
• erase() – Removes a single element or a range of elements from the list.
• assign() – Assigns new elements to list by replacing current elements and resizes the
list.
• remove() – Removes all the elements from the list, which are equal to given element.
 15
Sequence Containers
• list::remove_if() – Used to remove all the values from the list that correspond true to
the predicate or condition given as parameter to the function.
• reverse() – Reverses the list.
• size() – Returns the number of elements in the list.
• list resize() – Used to resize a list container.
• sort() – Sorts the list in increasing order.
• list max_size() – Returns the maximum number of elements a list container can hold.
• list unique() – Removes all duplicate consecutive elements from the list.
• list::emplace_front() and list::emplace_back() – emplace_front() function is used to
insert a new element into the list container, the new element is added to the beginning
of the list. emplace_back() function is used to insert a new element into the list
container, the new element is added to the end of the list.
• list::clear() – clear() function is used to remove all the elements of the list container,
thus making it size 0.
• list::operator=– This operator is used to assign new contents to the container by
replacing the existing contents.
• list::swap() – This function is used to swap the contents of one list with another list of
same type and size.
• list splice() – Used to transfer elements from one list to another.
• list merge() – Merges two sorted lists into one
• list emplace() – Extends list by inserting new element at a given position.
 16

Sequence Containers
• <deque> is a double-ended queue, that means one can insert and
delete elements from both ends, it is a kind of combination
between a stack (last in first out) and a queue (first in first out)
and constitutes a compromise between a <vector> and a <list>
Offers random access, back and front insertion but slower than
vectors.
• Methods of Deque:
– deque insert() : Inserts an element. And returns an iterator that points to the first
of the newly inserted elements.
– deque rbegin() : Returns a reverse iterator which points to the last element of the
deque (i.e., its reverse beginning).
– deque rend() : Returns a reverse iterator which points to the position before the
beginning of the deque (which is considered its reverse end).
– deque cbegin() : Returns a constant iterator pointing to the first element of the
container, that is, the iterator cannot be used to modify, only traverse the deque.
 17
Sequence Containers
– deque max_size() : Returns the maximum number of elements that a deque container
can hold.
– deque assign() : Assign values to the same or different deque container.
– deque resize() : Function which changes the size of the deque.
– deque::push_front() : This function is used to push elements into a deque from the
front.
– deque::push_back() : This function is used to push elements into a deque from the
back.
– deque::pop_front() and deque::pop_back() : pop_front() function is used to pop or
remove elements from a deque from the front. pop_back() function is used to pop or
remove elements from a deque from the back.
– deque::front() and deque::back() : front() function is used to reference the first
element of the deque container. back() function is used to reference the last element of
the deque container.
– deque::clear() and deque::erase() : clear() function is used to remove all the elements
of the deque container, thus making its size 0. erase() function is used to remove
elements from a container from the specified position or range.
 18
Sequence Containers
– deque::empty() and deque::size() : empty() function is used to check if the deque
container is empty or not. size() function is used to return the size of the deque
container or the number of elements in the deque container.
– deque::operator= and deque::operator[] in C++ STL:
– operator= operator is used to assign new contents to the container by replacing the
existing contents. operator[] operator is used to reference the element present at
position given inside the operator.
– deque::at() and deque::swap() : at() function is used reference the element present at
the position given as the parameter to the function. swap() function is used to swap the
contents of one deque with another deque of same type and size.
– deque::begin() and deque::end : begin() function is used to return an iterator pointing
to the first element of the deque container. end() function is used to return an iterator
pointing to the last element of the deque container.
– deque::emplace_front() and deque::emplace_back() : emplace_front() function is used
to insert a new element into the deque container. The new element is added to the
beginning of the deque. emplace_back() function is used to insert a new element into
the deque container. The new element is added to the end of the deque.
 19

Associative Containers
• An associative container is non-sequential but uses a
key to access elements.
• The keys, typically a number or a string, are used by the
container to arrange the stored elements in a specific
order, for example in a dictionary the entries are ordered
alphabetically.
• Offers O(log n) insertion and access
 20

Associative Containers
• A <set> stores a number of items which contain keys.
• The keys are the attributes used to order the items, for
example a set might store objects of the class. People
which are ordered alphabetically using their name.
• Sets are a type of associative containers in which each
element has to be unique, because the value of the
element identifies it.
• The value of the element cannot be modified once it is
added to the set, though it is possible to remove and add
the modified value of that element.
 21

Associative Containers
• Some basic functions associated with Set:

– begin() – Returns an iterator to the first element in the set.

– end() – Returns an iterator to the theoretical element that
follows last element in the set.
– size() – Returns the number of elements in the set.
– max_size() – Returns the maximum number of elements that
the set can hold.
– empty() – Returns whether the set is empty.
 22

Associative Containers
• A <map> stores pairs of objects: a key object and an associated
value object.
• A <map> is somehow similar to an array except instead of
accessing its elements with index numbers, you access them with
indices of an arbitrary type.
• Each element has a key value and a mapped value.
• No two mapped values can have same key values.
 23

Associative Containers
• Some basic functions associated with Map:
– begin() – Returns an iterator to the first element in the map
– end() – Returns an iterator to the theoretical element that follows last
element in the map
– size() – Returns the number of elements in the map
– max_size() – Returns the maximum number of elements that the map can
hold
– empty() – Returns whether the map is empty
– pair insert(keyvalue, mapvalue) – Adds a new element to the map
– erase(iterator position) – Removes the element at the position pointed by
the iterator
– erase(const g)– Removes the key value ‘g’ from the map
– clear() – Removes all the elements from the map
 24

Adaptor Containers
• Container adaptors provide a different interface for sequential
containers.
– stack: Adapts a container to provide stack (LIFO data
structure).
– queue: Adapts a container to provide queue (FIFO data
structure).
– priority_queue: Adapts a container to provide priority queue.
 25

Adaptor Containers
• 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.
• The functions associated with stack are:
– empty() – Returns whether the stack is empty – Time Complexity : O(1)
– size() – Returns the size of the stack – Time Complexity : O(1)
– top() – Returns a reference to the top most element of the stack – Time
Complexity : O(1)
– push(g) – Adds the element ‘g’ at the top of the stack – Time Complexity
: O(1)
– pop() – Deletes the top most element of the stack – Time Complexity :
O(1)
 26

Adaptor Containers
• Queues are a type of container adaptors which operate in a first in
first out (FIFO) type of arrangement. Elements are inserted at the
back (end) and are deleted from the front.
• empty() – Returns whether the queue is empty.
• size() – Returns the size of the queue.
• queue::swap(): Exchange the contents of two queues but the queues must be of
same type, although sizes may differ.
• queue::emplace(): Insert a new element into the queue container, the new
element is added to the end of the queue.
• queue::front() and queue::back() – front() function returns a reference to the first
element of the queue. back() function returns a reference to the last element of
the queue.
• push(g) and pop() – push() function adds the element ‘g’ at the end of the queue.
pop() function deletes the first element of the queue.
 27

Adaptor Containers
• Priority queues are a type of container adapters, specifically designed
such that the first element of the queue is the greatest of all elements in
the queue and elements are in non increasing order(hence we can see
that each element of the queue has a priority{fixed order}).
– priority_queue::empty()– empty() function returns whether the queue is empty.
– priority_queue::size() – size() function returns the size of the queue.
– priority_queue::top() – Returns a reference to the top most element of the queue
– priority_queue::push() – push(g) function adds the element ‘g’ at the end of the
queue.
– priority_queue::pop() – pop() function deletes the first element of the queue.
– priority_queue::swap() – This function is used to swap the contents of one priority
queue with another priority queue of same type and size.
– priority_queue::emplace() – This function is used to insert a new element into the
priority queue container, the new element is added to the top of the priority queue.
– priority_queue value_type – Represents the type of object stored as an element in a
priority_queue. It acts as a synonym for the template parameter.
 28

Defining a new vector

• Header file: <vector>
• Syntax: vector<of what>
• For example :
– vector<int> - vector of integers.
– vector<string> - vector of strings.
– vector<int * > - vector of pointers to integers.
– vector<Shape> - vector of Shape objects. Shape is a
user defined class.
– Two ways to use vector type: Array style, and STL
style
 29

Vector Container
 30
Vector Container
#include <iostream> cout << "\nOutput of rbegin and rend: ";
#include <vector> for (auto ir = g1.rbegin(); ir !=
g1.rend(); ++ir)
using namespace std;
cout << *ir << " ";
int main()
cout << "\nOutput of crbegin and crend
{
: ";
vector<int> g1;
for (auto ir = g1.crbegin(); ir !=
for (int i = 1; i <= 5; i++) g1.crend(); ++ir)
g1.push_back(i); cout << *ir << " ";
cout << "Output of begin and end: "; return 0;
for (auto i = g1.begin(); i != g1.end(); }
++i)
cout << *i << " ";
Output:
cout << "\nOutput of cbegin and cend:
Output of begin and end: 1 2 3 4 5
";
Output of cbegin and cend: 1 2 3 4 5
for (auto i = g1.cbegin(); i !=
g1.cend(); ++i) Output of rbegin and rend: 5 4 3 2 1
cout << *i << " "; Output of crbegin and crend : 5 4 3 2 1
 31

reserve()
• Vectors are dynamic arrays. Unlike arrays, they don’t have a fixed
size.
• They can grow or shrink as required. Vectors are assigned memory
in blocks of contiguous locations.
• When the memory allocated for the vector falls short of storing new
elements, a new memory block is allocated to vector and all elements
are copied from the old location to the new location.
• This reallocation of elements helps vectors to grow when required.
• However, it is a costly operation and time complexity is involved in
this step is linear.
• v.reserve(n) allocates memory for n objects
• Each vector object has two parameters–size and capacity.
• The size denotes the number of elements currently stored in the
vector while capacity is the maximum number of elements that the
vector can store without reallocation.
 32

reserve()
• Vectors are dynamic arrays. Unlike arrays, they don’t have a fixed
size.
• They can grow or shrink as required. Vectors are assigned memory
in blocks of contiguous locations.
• When the memory allocated for the vector falls short of storing new
elements, a new memory block is allocated to vector and all elements
are copied from the old location to the new location.
• This reallocation of elements helps vectors to grow when required.
• However, it is a costly operation and time complexity is involved in
this step is linear.
• v.reserve(n) allocates memory for n objects
• Each vector object has two parameters–size and capacity.
• The size denotes the number of elements currently stored in the
vector while capacity is the maximum number of elements that the
vector can store without reallocation.
 33

reserve() cout << endl << endl;

#include <iostream>
/* Reserve space for 25 elements */
#include <vector> v2.reserve(25);
using namespace std; for (int i = 0; i < 25; ++i)
int main(void) {
{ v2.push_back(i);
vector<int> v1; if (size != v2.capacity())
vector<int> v2; {
ssize_t size; size = v2.capacity();
size = v1.capacity(); cout << "Expanding vector v2 to hold
for (int i = 0; i < 25; ++i) " << size << " elements" << endl;
{ v1.push_back(i); }
if (size != v1.capacity()) }
{ size = v1.capacity(); return 0;
cout << "Expanding vector v1 to hold }
" << size << " elements" << endl; }
}
 34

reserve()
Output:
Expanding vector v1 to hold 1 elements
Expanding vector v1 to hold 2 elements
Expanding vector v1 to hold 4 elements
Expanding vector v1 to hold 8 elements
Expanding vector v1 to hold 16 elements
Expanding vector v1 to hold 32 elements
Expanding vector v2 to hold 25 elements
 35

size() and empty()

• You may check whether a container is empty by
writing c.size() == 0 or c.empty()
• However, with lists, which have a splice() function,
if splice() is O(1), size() must be O(n) and
conversely.
• Therefore, while empty() will always run in O(1),
size() may not. You should thus prefer calling
empty() to checking size() against zero.
 36

Iterators
• Iterators are pointer-like entities that are used to access
individual elements in a container.
• Often they are used to move sequentially from element to
element, a process called iterating through a container.
 37

Iterators
• The member functions begin() and end() return an iterator to
the first and past the last element of a container
 38

Iterators
• One can have multiple iterators pointing to different or
identical elements in the container
 39

Common Iterator Operations

• * Return the item that the iterator currently references
• ++ Move the iterator to the next item in the list
• -- Move the iterator to the previous item in the list
• advacne() This function is used to increment the
iterator position till the specified number mentioned in
its arguments.
• begin() :- This function is used to return the beginning
position of the container.
• end() :- This function is used to return the after end
position of the container.
 40

Common Iterator Operations

• next() :- This function returns the new iterator that the
iterator would point after advancing the positions
mentioned in its arguments.
• prev() :- This function returns the new iterator that the
iterator would point after decrementing the positions
mentioned in its arguments.
• 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.
• == Compare two iterators for equality
• != Compare two iterators for inequality
 41

Iterator
#include <vector>
#include <cstdio>
using namespace std;
int main
{
int arr[] = { 12, 3, 17, 8 }; // standard C array
vector<int> v(arr, arr+4); //initialize vector with C array
vector<int>::iterator iter=v.begin(); //iterator for class vector
// define iterator for vector and point it to first element of v
printf(”First element of v = %d\n”,*iter); // de-reference iter
iter++; // move iterator to next element
iter=v.end()-1; // move iterator to last element
}
 42

Iterator
int max(vector<int>::iterator start, vector<int>::iterator end)
{
int m=*start;
while(start != end)
{
if (*start > m)
m=*start;
++start;
}
return m;
}
printf(”max of v = %d”, max(v.begin(),v.end()));
 43

Iterator
vector<int> v;
for(int i=0;i<n;i++)
{
scanf(”%d”,&num);
v.push_back(num);
}
for (vector<int>::iterator i=v.begin(); i!=v.end(); i++)
// initialize i with pointer to first element of v i++ increment iterator, move
//iterator to next element
{
printf(”%d ”,*i); // de-referencing iterator returns the value of the element the
//iterator points at
}
for(i=0;i<n;i++)
printf(”%d ”,v[i]);
 44
Stack Container
• This container restricts how elements enter and leave a
sequence
• Stack
• allows access at only one end of the sequence (top)
• Adds objects to container by pushing the object onto the stack
• Removes objects from container by popping the stack
• LIFO ordering (last end, first out)
• Header file: <stack>
• Example of creating stacks
• A stack of int : stack < int > s1;
 45
Stack Container s.push(30);
s.push(20);
#include <iostream> s.push(5);
#include <stack> s.push(1);
using namespace std; cout << "The stack is : ";
void showstack(stack <int> s) showstack(s);
{ cout << "\ns.size() : " << s.size();
while (!s.empty()) cout << "\ns.top() : " << s.top();
{ cout << "\ns.pop() : ";
cout << '\t' << s.top(); s.pop();
s.pop(); showstack(s);
} return 0; }
cout << '\n';
} Output:
int main () The stack is : 1 5 20 30 10
{ s.size() : 5
stack <int> s; s.top() : 1
s.push(10); s.pop() : 5 20 30 10
 46
Queue Container
• Queue
• Allows access only at the front and rear of the sequence
• Items enter at the rear and exit from the front
• Example: waiting line at a grocery store
• FIFO ordering (first-in first-out )
• push(add object to a queue)
• pop (remove object from queue)
• Header file <queue>
• Example:
• A queue of int : queue <int> q1;
 47
Queue Container cout << "The queue gquiz is : ";
showq(gquiz);
#include <iostream> cout << "\ngquiz.size() : " <<
#include <queue> gquiz.size();
using namespace std; cout << "\ngquiz.front() : " <<
void showq(queue <int> gq) gquiz.front();
{ cout << "\ngquiz.back() : " <<
gquiz.back();
queue <int> g = gq;
cout << "\ngquiz.pop() : ";
while (!g.empty())
gquiz.pop();
{
showq(gquiz);
cout << '\t' << g.front();
return 0; }
g.pop(); }
cout << '\n'; }
Output:
int main()
The queue gquiz is : 10 20 30
{ queue <int> gquiz;
gquiz.size() : 3
gquiz.push(10); gquiz.front() : 10
gquiz.push(20); gquiz.back() : 30
gquiz.push(30); gquiz.pop() : 20 30
 48
Priority Queue Container
• Priority queue
• Operations are similar to those of a stack or queue
• Elements can enter the priority queue in any order
• Once in the container, a delete operation removes the largest (or
smallest) value
• Example: a filtering system that takes in elements and then
releases them in priority order
 49
Priority Queue Container
• Priority Queues are implemented with vector (by default) or
deque
• The elements with the highest priority are removed first
• less<T> is used by default for comparing elements
• Header file <queue>
 50
Priority Queue Container
#include <iostream> cout << "The priority queue gquiz is : ";
#include <queue> showpq(gquiz);
using namespace std; cout << "\ngquiz.size() : " <<
void showpq(priority_queue <int> gq) gquiz.size();
{
cout << "\ngquiz.top() : " <<
priority_queue <int> g = gq;
gquiz.top();
while (!g.empty())
{ cout << "\ngquiz.pop() : ";
cout << '\t' << g.top(); gquiz.pop();
g.pop(); } showpq(gquiz);
cout << '\n'; } return 0; }
int main ()
{
Output:
priority_queue <int> gquiz;
The priority queue gquiz is : 30 20
gquiz.push(10);
10 5 1
gquiz.push(30);
gquiz.push(20); gquiz.size() : 5
gquiz.push(5); gquiz.top() : 30
gquiz.push(1); gquiz.pop() : 20 10 5 1
 51
Associative Containers
• In an associative container the items are not arranged in
sequence, but usually as a tree structure or a hash table.
• The main advantage of associative containers is the speed of
searching (binary search like in a dictionary)
• Searching is done using a key which is usually a single value
like a number or string
• The value is an attribute of the objects in the container
• The STL contains two basic associative containers
• sets and multisets
• maps and multimaps
 52
Associative Containers
• Associative containers use keys to store and retrieve
elements
• There are four types: multiset, set, multimap and map
• all associative containers maintain keys in sorted order
• all associative containers support bidirectional iterators
• set does not allow duplicate keys
• multiset and multimap allow duplicate keys
• multimap and map allow keys and values to be mapped
 53
Set Containers
• Set
• Collection of unique values, called keys or set members
• Contains operations that allow a programmer to:
• determine whether an item is a member of the set
• insert and delete items very efficiently
 54
Associative Containers: multiset
• Multisets are implemented using a red-black binary search tree
for fast storage and retrieval of keys
• Multisets allow duplicate keys
• The ordering of the keys is determined by the STL comparator
function object less<T>
• Keys sorted with less<T> must support comparison using the <
operator
 55
Sets // printing set gquiz1
set <int, greater <int> > :: iterator itr;
#include <iostream> cout << "\nThe set gquiz1 is : ";
#include <set> for (itr = gquiz1.begin(); itr !=
#include <iterator> gquiz1.end(); ++itr)
using namespace std; { cout << '\t' << *itr; }
int main() cout << endl;
{ // assigning the elements from
// empty set container gquiz1 to gquiz2
set <int, greater <int> > gquiz1; set <int> gquiz2(gquiz1.begin(),
// insert elements in random order gquiz1.end());
gquiz1.insert(40); // print all elements of the set
gquiz2
gquiz1.insert(30);
cout << "\nThe set gquiz2 after
gquiz1.insert(60);
assign from gquiz1 is : ";
gquiz1.insert(20);
for (itr = gquiz2.begin(); itr !=
gquiz1.insert(50); gquiz2.end(); ++itr)
gquiz1.insert(50); // only one 50 { cout << '\t' << *itr; }
will be added to the set
cout << endl;
gquiz1.insert(10);
 56
// remove all elements up to 30 in cout << endl;
gquiz2
//lower bound and upper bound for
cout << "\ngquiz2 after removal of set gquiz1
elements less than 30 : "; cout << "gquiz1.lower_bound(40) :
gquiz2.erase(gquiz2.begin(), "<< *gquiz1.lower_bound(40) << endl;
gquiz2.find(30));
cout << "gquiz1.upper_bound(40) :
for (itr = gquiz2.begin(); itr != "<< *gquiz1.upper_bound(40) << endl;
gquiz2.end(); ++itr)
//lower bound and upper bound for
{ cout << '\t' << *itr; } set gquiz2
// remove element with value 50 in cout << "gquiz2.lower_bound(40) :
gquiz2 "<< *gquiz2.lower_bound(40) << endl;
int num; cout << "gquiz2.upper_bound(40) :
num = gquiz2.erase (50); "<< *gquiz2.upper_bound(40) << endl;
cout << "\ngquiz2.erase(50) : "; return 0;
cout << num << " removed \t" ; }
for (itr = gquiz2.begin(); itr !=
gquiz2.end(); ++itr)
{ cout << '\t' << *itr;
}
 57

• The output of the above program is :

The set gquiz1 is : 60 50 40 30 20 10
The set gquiz2 after assign from gquiz1 is : 10 20 30 40
50 60
gquiz2 after removal of elements less than 30 : 30 40 50
60
gquiz2.erase(50) : 1 removed 30 40 60
gquiz1.lower_bound(40) : 40
gquiz1.upper_bound(40) : 30
gquiz2.lower_bound(40) : 40
gquiz2.upper_bound(40) : 60
 58
Multisets gquiz1.insert(10);
// printing multiset gquiz1
#include <iostream> multiset <int, greater <int> > ::
#include <set> iterator itr;
#include <iterator> cout << "\nThe multiset gquiz1 is :
using namespace std; ";
int main() for (itr = gquiz1.begin(); itr !=
{ // empty multiset container gquiz1.end(); ++itr)
multiset <int, greater <int> > { cout << '\t' << *itr; }
gquiz1; cout << endl;
// insert elements in random order // assigning the elements from gquiz1
gquiz1.insert(40); to gquiz2
gquiz1.insert(30); multiset <int>
gquiz2(gquiz1.begin(), gquiz1.end());
gquiz1.insert(60);
// print all elements of the multiset
gquiz1.insert(20);
gquiz2
gquiz1.insert(50);
cout << "\nThe multiset gquiz2 after
gquiz1.insert(50); // 50 will be assign from gquiz1 is : ";
added again to the multiset unlike
for (itr = gquiz2.begin(); itr !=
set
 59
gquiz2.end(); ++itr) for (itr = gquiz2.begin(); itr !=
{ cout << '\t' << *itr; gquiz2.end(); ++itr)
} { cout << '\t' << *itr; }
cout << endl; cout << endl;
// remove all elements up to element //lower bound and upper bound for
with value 30 in gquiz2 multiset gquiz1
cout << "\ngquiz2 after removal of cout << "gquiz1.lower_bound(40) :
elements less than 30 : "; "<< *gquiz1.lower_bound(40) << endl;
gquiz2.erase(gquiz2.begin(), cout << "gquiz1.upper_bound(40) :
gquiz2.find(30)); "<< *gquiz1.upper_bound(40) << endl;
for (itr = gquiz2.begin(); itr != //lower bound and upper bound for
gquiz2.end(); ++itr) multiset gquiz2
{ cout << '\t' << *itr; } cout << "gquiz2.lower_bound(40) :
// remove all elements with value 50 "<< *gquiz2.lower_bound(40) cout <<
in gquiz2 "gquiz2.upper_bound(40) : "<<
int num; *gquiz2.upper_bound(40) << endl;
num = gquiz2.erase(50); return 0; }
cout << "\ngquiz2.erase(50) : ";
cout << num << " removed \t" ;
 60

• The output of the above program is :

The multiset gquiz1 is : 60 50 50 40 30 20 10
The multiset gquiz2 after assign from gquiz1 is : 10 20 30
40 50 50 60
gquiz2 after removal of elements less than 30 : 30 40 50
50 60
gquiz2.erase(50) : 2 removed 30 40 60
gquiz1.lower_bound(40) : 40
gquiz1.upper_bound(40) : 30
gquiz2.lower_bound(40) : 40
gquiz2.upper_bound(40) : 60
 61

Set Vs Multiset
• Set
– Stores the values in sorted order.
– Stores only unique values.
– Elements can only be inserted or deleted but cannot be
modified.
– We can erase more than 1 element by giving start iterator
and end iterator position.
– Traversal using iterators.
– Sets are implemented as Binary Search Tree.
 62

Set Vs Multiset
• Multiset
– (Stores elements in sorted order.
– It allows storage of multiple elements.
– We can erase more than 1 element by giving start iterator
and end iterator.
– All other properties similar to set.
 63

Set Vs Multiset
• Unordered_set
– Elements can be stored in any order. ( no sorted order )
– Stores only unique values.
– Hash-table used to store elements.
– We can erase only the element for which iterator position is
given.
– Note:- All other properties similar to set.
 64

Set Vs Multiset
• Unordered_multiset
– Elements can be stored in any order.
– Duplicate elements can be stored.
– Hash-table used to store elements.
– We can erase only the element for which iterator position is
given.
– Note:- All other properties similar to set.
 65

Maps and Multimaps

• A map stores pairs <key, value> of a key object and associated
value object.
• The key object contains a key that will be searched for and the
value object contains additional data
• The key could be a string, for example the name of a person and
the value could be a number, for example the telephone number
of a person
 66
Map // printing map gquiz1
map<int, int>::iterator itr;
#include <iostream> cout << "\nThe map gquiz1 is : \n";
#include <iterator> cout << "\tKEY\tELEMENT\n";
#include <map> for (itr = gquiz1.begin(); itr !=
using namespace std; gquiz1.end(); ++itr) {
int main() cout << '\t' << itr->first << '\t' <<
{ itr->second << '\n'; }
// empty map container cout << endl;
map<int, int> gquiz1; // assigning the elements from gquiz1
// insert elements in random order to gquiz2
gquiz1.insert(pair<int, int>(1, 40)); map<int, int>
gquiz2(gquiz1.begin(), gquiz1.end());
gquiz1.insert(pair<int, int>(2, 30));
// print all elements of the map
gquiz1.insert(pair<int, int>(3, 60));
gquiz2
gquiz1.insert(pair<int, int>(4, 20));
cout << "\nThe map gquiz2 after"<< "
gquiz1.insert(pair<int, int>(5, 50)); assign from gquiz1 is : \n";
gquiz1.insert(pair<int, int>(6, 50)); cout << "\tKEY\tELEMENT\n";
gquiz1.insert(pair<int, int>(7, 10));
 67
for (itr = gquiz2.begin(); itr != // remove all elements with key = 4
gquiz2.end(); ++itr) {
int num;
cout << '\t' << itr->first num = gquiz2.erase(4);
<< '\t' << itr->second << '\n'; cout << "\ngquiz2.erase(4) : ";
} cout << num << " removed \n";
cout << endl; cout << "\tKEY\tELEMENT\n";
// remove all elements up to for (itr = gquiz2.begin(); itr !=
// element with key=3 in gquiz2 gquiz2.end(); ++itr) {
cout << "\ngquiz2 after removal of" cout << '\t' << itr->first
" elements less than key=3 : \n"; << '\t' << itr->second << '\n'; }
cout << "\tKEY\tELEMENT\n"; // lower bound and upper bound for
gquiz2.erase(gquiz2.begin(), map gquiz1 key = 5
gquiz2.find(3)); cout << "gquiz1.lower_bound(5) : "
for (itr = gquiz2.begin(); itr != << "\tKEY = ";
gquiz2.end(); ++itr) {
cout << gquiz1.lower_bound(5)->first
cout << '\t' << itr->first << '\t';
<< '\t' << itr->second << '\n'; cout << "\tELEMENT = "<<
} gquiz1.lower_bound(5)->second
 68
cout << "gquiz1.upper_bound(5) : "<< The map gquiz2 after assign from
"\tKEY = "; gquiz1 is :
cout << gquiz1.upper_bound(5)->first KEY ELEMENT
<< '\t'; 1 40
cout << "\tELEMENT = "<< 2 30
gquiz1.upper_bound(5)->second <<
3 60
endl;
4 20
return 0; }
5 50
6 50
Output:
7 10
The map gquiz1 is :
gquiz2 after removal of elements less
KEY ELEMENT
than key=3 :
1 40
KEY ELEMENT
2 30
3 60
3 60
4 20
4 20
5 50
5 50
6 50
6 50
7 10
7 10
 69
gquiz2.erase(4) : 1 removed
KEY ELEMENT
3 60
5 50
6 50
7 10

gquiz1.lower_bound(5) : KEY = 5 ELEMENT = 50

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

gquiz1.lower_bound(5) : KEY = 5 ELEMENT = 50

gquiz1.upper_bound(5) : KEY = 6 ELEMENT = 50
 74

Algorithms
• Implement simple, or not-so-simple loops on ranges
• copy, find, but also partition, sort, next-permutation
• Specify their need in terms of iterator categories
• They do not care about the exact class
• Must pay attention to the iterators provided by containers
• Often exist in several versions
• One uses default comparison, user-defined value
• Other calls user-provided predicate, function
• Some impose requirement on the data
• binary_search needs sorted data
• Tip: swap(c1,c2) would swap c1 and c2 irrespective of their data
type
 75

Fill and Generate

• fill(iterator1, iterator2, value);
• fills the values of the elements between iterator1 and
iterator2 with value
• fill_n(iterator1, n, value);
• changes specified number of elements starting at iterator1 to
value
• generate(iterator1, iterator2, function);
• similar to fill except that it calls a function to return value
• generate_n(iterator1, n, function)
• same as fill_n except that it calls a function to return value
 76

Comparing sequences of values

• bool equal(iterator1, iterator2, iterator3);
• compares sequence from iterator1 to iterator2 with the
sequence beginning at iterator3
• return true is they are equal, false otherwise
• pair mismatch(iterator1, iterator2, iterator3);
• compares sequence from iterator1 to iterator2 with the
sequence starting at iterator3
• returns a pair object with iterators pointing to where
mismatch occurred
• example of the a pair object
• pair <<vector>::iterator, <vector>::iterator> par_obj;
 77

Removing elements from containers

• iterator remove(iterator1, iterator2, value);
• removes all instances of value in a range iterator1 to iterator2
• does not physically remove the elements from the sequence
• moves the elements that are not removed forward
• returns an iterator that points to the "new" end of container
• iterator remove_copy(iterator1, iterator2, iterator3, value);
• copies elements of the range iterator1-iterator2 that are not
equal to value into the sequence starting at iterator3
• returns an iterator that points to the last element of the
sequence
• starting at iterator3
 78

Replacing elements (1)

• replace( iterator1, iterator2, value, newvalue );
• replaces value with newvalue for the elements
located in the range iterator1 to iterator2
• replace_if( iterator1, iterator2, function, newvalue );
• replaces all elements in the range iterator1-iterator2
for which function returns true with newvalue
 79

Replacing elements (2)

• replace_copy( iterator1, iterator2, iterator3, value,
newvalue );
• replaces and copies elements of the range
iterator1-iterator2 to iterator3
• replace_copy_if( iterator1, iterator2, iterator3, function,
newvalue );
• replaces and copies elements for which function
returns true where iterator3
 80

Search algorithms
• iterator find(iterator1, iterator2, value)
• returns an iterator that points to first occurrence of
value

• iterator find_if(iterator1, iterator2, function)

• returns an iterator that points to the first element for
which function returns true.
 81

Sorting algorithms
• sort(iterator1, iterator2)
• sorts elements in ascending order

• binary_search(iterator1, iterator2, value)

• searches in an ascending sorted list for value using a

binary search
 82

Copy and Merge

• copy(iterator1, iterator2, iterator3)
• copies the range of elements from iterator1 to
iterator2 into iterator3

• copy_backward(iterator1, iterator2, iterator3)

• copies in reverse order the range of elements from
iterator1 to iterator2 into iterator3

• merge(iter1, iter2, iter3, iter4, iter5)

• ranges iter1-iter2 and iter3-iter4 must be sorted in
ascending order and copies both lists into iter5 in
ascending order
 83

Unique and Reverse order

• iterator unique(iterator1, iterator2)
• removes (logically) duplicate elements from a sorted
list
• returns iterator to the new end of sequence

• reverse(iterator1, iterator2)
• reverses elements in the range of iterator1 to iterator2
 84

Utility algorithms (1)

• random_shuffle(iterator1, iterator2)
• randomly mixes elements in the range iterator1-
iterator2

• int count(iterator1, iterator2, value)

• returns number of instances of value in the range

• int count_if(iterator1, iterator2, function)

• counts number of instances for which function
returns true
 85

Utility algorithms (2)

• iterator min_element(iterator1, iterator2)
• returns iterator to smallest element

• iterator max_element(iterator1, iterator2)

• returns iterator to largest element

• accumulate(iterator1, iterator2)
• returns the sum of the elements in the range
 86

Utility algorithms (3)

• iterator min_element(iterator1, iterator2)
• returns iterator to smallest element

• iterator max_element(iterator1, iterator2)

• returns iterator to largest element

• accumulate(iterator1, iterator2)
• returns the sum of the elements in the range
 87

Algorithms on sets (1)

• includes(iter1, iter2, iter3, iter4)
• returns true if iter1-iter2 contains iter3-iter4.
• Both sequences must be sorted

• set_difference(iter1, iter2, iter3, iter4,iter5)

• copies elements in range iter1-iter2 that do not exist
in second range iter3-iter4 into iter5

• set_intersection(iter1, iter2, iter3, iter4, iter5)

• copies common elements from the two ranges
iter1-iter2 and iter3-iter4 into iter5
 88

Algorithms on sets (2)

• • set_symmetric_difference(iter1, iter2, iter3, iter4,
iter5)
• copies elements in range iter1-iter2 that are not in
range iter3-iter4 and vice versa, into iter5. Both sets
must be sorted

• set_union(iter1, iter2, iter3, iter4, iter5)

• copies elements in both ranges to iter5. Both sets
must be sorted
 89

For_Each() Algorithm
#include <vector>
#include <algorithm>
#include <cstdio>
void show(int n)
{
printf(”%d ”,n);
}
int arr[] = { 12, 3, 17, 8 }; // standard C array
vector<int> v(arr, arr+4); // initialize vector with C array
for_each (v.begin(), v.end(), show); // apply function show
// to each element of vector v
 90

Find() Algorithm
#include <vector>
#include <algorithm>
#include <cstdio>
int key;
int arr[] = { 12, 3, 17, 8, 34, 56, 9 }; // standard C array
vector<int> v(arr, arr+7); // initialize vector with C array
vector<int>::iterator iter;
pritnf(”enter value :”);
scanf(”%d ”,key);
iter=find(v.begin(),v.end(),key); // finds integer key in v
if (iter != v.end()) // found the element
printf(”Element %d found\n”,key);
else
printf(”Element %d not in vector”, key);
 91

Find_If() Algorithm
#include <vector>
#include <algorithm>
#include <cstdio>
Bool mytest(int n) { return (n>21) && (n <36); };
int arr[] = { 12, 3, 17, 8, 34, 56, 9 }; // standard C array
vector<int> v(arr, arr+7); // initialize vector with C array
vector<int>::iterator iter;
iter=find_if(v.begin(),v.end(),mytest);
// finds element in v for which mytest is true
if (iter != v.end()) // found the element
printf(”Found %d\n”,iter);
else
printf(”Not found”);
 92

Count_If() Algorithm
#include <vector>
#include <algorithm>
#include <cstdio>
Bool mytest(int n) { return (n>14) && (n <36); };
int arr[] = { 12, 3, 17, 8, 34, 56, 9 }; // standard C
array
vector<int> v(arr, arr+7); // initialize vector with C
array
int n=count_if(v.begin(),v.end(),mytest);
// counts element in v for which mytest is true
printf(”found %d elements\n”, n );
 93

List Container
• An STL list container is a double linked list, in which
each element contains a pointer to its successor and
predecessor.

• It is possible to add and remove elements from both

ends of the list

• Lists do not allow random access but are efficient to

insert new elements and to sort and merge lists
 94

List Container
 95

Insert Iterators
• If you normally copy elements using the copy algorithm
you overwrite the existing contents

#include <list>
int arr1[]= { 1, 3, 5, 7, 9 };
int arr2[]= { 2, 4, 6, 8, 10 };
list<int> l1(arr1, arr1+5); // initialize l1 with arr1
list<int> l2(arr2, arr2+5); // initialize l2 with arr2
copy(l1.begin(), l1.end(), l2.begin());
// copy contents of l1 to l2 overwriting the elements in l2
// l2 = { 1, 3, 5, 7, 9 }
 96

Insert Iterators
• With insert operators you can modify the behavior of the copy algorithm
• back_inserter : inserts new elements at the end
• front_inserter : inserts new elements at the beginning
• inserter : inserts new elements at a specified location
#include <list>
int arr1[]= { 1, 3, 5, 7, 9 };
int arr2[]= { 2, 4, 6, 8, 10 };
list<int> l1(arr1, arr1+5); // initialize l1 with arr1
list<int> l2(arr2, arr2+5); // initialize l2 with arr2
copy(l1.begin(), l1.end(), back_inserter(l2)); // use back_inserter
// adds contents of l1 to the end of l2 = { 2, 4, 6, 8, 10, 1, 3, 5, 7, 9 }
copy(l1.begin(), l1.end(), front_inserter(l2)); // use front_inserter
// adds contents of l1 to the front of l2 = { 9, 7, 5, 3, 1, 2, 4, 6, 8, 10 }
copy(l1.begin(), l1.end, inserter(l2,l2.begin());
// adds contents of l1 at the ”old” beginning of l2 = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 }
 97

Sort & Merge

• Sort and merge allow you to sort and merge elements in a
container

#include <list>
int arr1[]= { 6, 4, 9, 1, 7 };
int arr2[]= { 4, 2, 1, 3, 8 };
list<int> l1(arr1, arr1+5); // initialize l1 with arr1
list<int> l2(arr2, arr2+5); // initialize l2 with arr2
l1.sort(); // l1 = {1, 4, 6, 7, 9}
l2.sort(); // l2= {1, 2, 3, 4, 8 }
l1.merge(l2); // merges l2 into l1
// l1 = { 1, 1, 2, 3, 4, 4, 6, 7, 8, 9}, l2= {}
 98

Functions Objects
• Some algorithms like sort, merge, accumulate can take a function
object as argument.
• A function object is an object of a template class that has a single
member function : the overloaded operator ()
• It is also possible to use user-written functions in place of
pre-defined function objects
#include <list>
#include <functional>
int arr1[]= { 6, 4, 9, 1, 7 };
list<int> l1(arr1, arr1+5); // initialize l1 with arr1
l1.sort(greater<int>()); // uses function object
greater<int>
// for sorting in reverse order l1 = { 9, 7, 6, 4, 1 }
 99

Functions Objects
• The accumulate algorithm accumulates data over the elements of
the containing, for example computing the sum of elements

#include <list>
#include <functional>
#include <numeric>
int arr1[]= { 6, 4, 9, 1, 7 };
list<int> l1(arr1, arr1+5); // initialize l1 with arr1
int sum = accumulate(l1.begin(), l1.end() , 0, plus<int>());
int sum = accumulate(l1.begin(), l1.end(),0); // equivalent
int n = accumulate(l1.begin(), l1.end() , 100, minus<int>());
 100

User Defined Function Objects

class squared _sum // user-defined function object
{
public:
int operator()(int n1, int n2) { return n1+n2*n2; }
};
int sq = accumulate(l1.begin(), l1.end() , 0,
squared_sum() );
// computes the sum of squares
 101

User Defined Function Objects

template <class T>
class squared _sum // user-defined function object
{
public:
T operator()(T n1, T n2) { return n1+n2*n2; }
};
vector<complex> vc;
complex sum_vc;
vc.push_back(complex(2,3));
vc.push_back(complex(1,5));
vc.push_back(complex(-2,4));
sum_vc = accumulate(vc.begin(), vc.end() ,
complex(0,0) , squared_sum<complex>() );
// computes the sum of squares of a vector of complex numbers