Standard Template Library(STL) in C++

What Is Stl(Standard Template Library)?
Who Developed The Standard Template Library(STL) In C++?
STL Has Four Components
What Are The Containers In C++?
STL Also Contains Common Member Function For All STL Containers
The Header Files For Each Of The Standard Library Containers
The Typedef’s Found In First-Class Containers
What Are The Iterators In C++?
Categories Of Iterators Used By The STL
Iterator Types Supported By Each Standard Library Container
Iterator Typedef’s
Iterator Operations For Each Type Of Iterator
Iterator Operations For Each Type Of Iterator
What Are The Algorithms?
Mutating-Sequence Algorithms
Non-Mutating-Sequence Algorithms
What Is The Sequence Container?
Vector Sequence Container
Advantage Of Vector Container
STL Exception Types
List Sequence Container
Deque Sequence Container
Associative Containers
Multiset Associative Container
Set Associative Container
Multimap Associative Container
Map Associative Container
Container Adapter In C++
Stack Adapter
Queue Adapter
What Is Algorithms In C++?
Algorithms list

What is stl(Standard Template Library)?

The C++ standard committee added the Standard Template Library(STL) to the C++ Standard Library. The STL defines powerful, template-based, reusable components that implement many common data structures and algorithms used to process those data structures.STL also offers generic programming. The meaning of generic programming is writing code that can be reused for the object of many different types.

For any particular application, several different STL containers might be appropriate. Select the most appropriate container that achieves the best performance for that application. Efficiency was a crucial consideration in STL’s design. Standard Library capabilities are implemented to operate efficiently across many applications. For some applications with unique performance requirements, it might be necessary to write your own customized implementation.

Who developed the Standard Template Library(STL) in C++?

The STL was developed by Alexander Stepanov and Meng Lee at Hewlett-Packed and is based on their research in the field of generic programming

Alexander Stepanov

STL has four components such as:

  • Containers
  • Algorithms
  • Functions
  • Iterators

What are the containers in C++?

  • The STL containers are divided into three major categories 1).sequence containers, 2).associative containers, 3).container adapters.
  • The sequence containers represent linear data structures, such as vectors and linked lists.
  • Associative containers are non-linear containers that typically can locate elements stored in the containers quickly
  • Such containers can store sets of values or key/value pairs
  • The sequence containers and associative containers are collectively referred to as the first-class containers
Standard Library containers classDescription
Sequence Containers

vector

deque


list



rapid insertions and deletions at back direct access to any element

rapid insertions and deletions at front or back direct access to any element

doubly linked list,rapid insertion deletion anywhere

Associative Containers

set

multiset

map


multimap




rapid lookup, no duplicates allowed

rapid lookup, duplicates allowed

one-to-one mapping, no duplicates allowed, rapid key-based lookup

one-to-many mapping, duplicates allowed, rapid key-based lookup
Container Adapters

stack
queue
priority_queue


last-in-first-out(LIFO)
first-in-first-out(FIFO)
highest priority elements is always the first element out

STL was carefully designed so that the containers provide similar functionality. There are many generic operations that apply to subsets of similar containers.

STL also contains Common member function for all STL containers

Common member functions for all STL containersDescription
default constructor A constructor to provide a default initialization of the container.Normally, each container has several constructors that provide different initialization methods for the container.
copy constructor A constructor that initializes the container to be a copy of an existing container of the same type.
destructor Destructor function for cleanup after a container is no longer needed.
empty Returns true if there are no elements in the container; otherwis, returns false
max_size Returns the maximum number of elements for a container.
size Returns the number of elements currently in the container
operator= Assigns one container to another
operator< Returns true if the first container is less than the second container; otherwise, return false
operator<= Returns true if the first container is less than or equal to the second container; otherwise, returns false
operator> Returns true if the first container is greater than the second container; otherwise, return false
operator>= Returns true if the first container is greater than or equal to the second container; otherwise, returns false
operator== Returns true if the first container is equal to the second container; otherwise, return false
operator!= Returns true if the first container is not equal to the second container; otherwise, returns false
swap Swaps the elements of two containers
Functions that are only found in first-class containers

begin




The two versions of this function return either an iterator or a const_iterator that refers to the first element of the container.
end The two versions of this function return either an iterator or const_iterator that refers to the next position after the end of the container
rbegin The two versions of this function return either a reverse_iterator or a const_reverse_iterator that refers to the last element of the container
rend The two versions of this function return either a reverse_iterator or a const_reverse_iterator that refers to the position before the first element of the container
erase Erases one or more elements from the container
clear Erases all elements from the container

The header files for each of the Standard Library containers

Standard Library container header files
<vector>

<list>

<deque>

<queue>    Contains both queue and priority_queue

<stack>

<map>       Contains map and multimap

<set>         Contains both set and multiset

<bitset>

The typedef’s found in first-class containers

typedefDescription
value_type The type of element stored in the container
reference A reference to the type of element stored in the container
const_reference A constant reference to the type of element stored in the container.Such a reference can only be used for reading elements in the container and for performing const operations
pointer A pointer to the type of element stored in the container
iterator An iterator that points to the type of element stored in the container
const_iterator A constant iterator that points to the type of elements stored in the container and can be used only to read elements
reverse_iterator Assigns one container to another
const_reverse_iterator A constant reverse iterator that points to the type of element stored in the container and can be used only to read elements.This type of iterator is for iterating through a container in reverse.
difference_type The type of the result of subtracting two iterators that refer to the same the same container (operator is not defined for iterators of list and associative containers)
size_type The type used to count items in a container and index through a sequence container (cannot index through a list)

What are the Iterators in C++?

Iterators have many features in common with pointers and are used to point the elements of first-class containers. Iterator holds state information sensitive to the particular containers on which they operate; thus, iterators are implemented appropriately for each type of container. Nevertheless, certain iterator operations are uniform across containers.

STL first-class containers provide a member function begin() and end().

  • begin(): This function returns an iterator pointing to the first element of the container
  • end(): This function returns an iterator pointing to the first element past the end of the container.

Let us implement Program for input and output stream iterators

#include<iostream>
using std::cout;
using std::cin;
using std::endl;
#include<iterator>
int main()
{
cout<<"Enter two integers:";
std::istream_iterator<int>inputInt(cin);
int number1=*inputInt;
++inputInt;
int number2=*inputInt;
std::ostream_iterator<int>outputInt(cout);
cout<<"The sum is:";
*outputInt=number1+number2;
cout<<endl;
return 0;
}

OUTPUT:

Enter two integers:22
65
87

Categories of iterators used by the STL

CategoryDescription
input Used to read an element from a container.An input iterator can move only in the forward direction(i.e. from the beginning of the container to the end of the container) one element at a time, input iterators support only one-pass algorithms the same input iterator cannot be used to pass through a sequence twice
output Used to write an element to a container.An output iterator can move only in forward direction one element at a time.Output iterators support only one-pass algorithms the same output iterator cannot be used to pass through a sequence twice.
forward Combines the capabilities of input and output iterators and retains their position in the container.
bidirectional Combines the capabilities of a forward iterator with the ability to move in the backward direction.Bidirectional iterators support multi-pass algorithms.
random access Combines the capabilities of a bidirectional iterator with the ability to directly access any element of the container, i.e. to jump forward or backward by an arbitrary number of elements

Iterator types supported by each Standard Library container

ContainerType of iterator supported
Sequence containers



vector
deque
list




random access
random access
bidirectional
Associative containers

set
multiset
map
multimap


bidirectional
bidirectional
bidirectional
bidirectional
Container adapters

stack
queue
priority_queue


no iterators supported
no iterators supported
no iterators supported

Iterator typedef’s

Predefined typedefs for iterator types              Direction of ++               Capability
iterator                                                                forward                         read/write
const_iterator                                                      forward                         read
reverse_iterator                                                   backward                      read/write
const_reverse_iterator                                         backward                       read

Iterator operations for each type of iterator

Iterator operationDescription
All iterators



++p
p++




preincrement an iterator
postincrement an iterator
Input iterators

*p
p=p1
p==p1
p!=p1


dereference an iterator
assign one iterator to another
compare iterators for equality
compare iterators for inequality
Output iterators


*p
p=p1



dereference an iterator
assign one iterator to another
Forward iterators Forward iterators provide all the functionality of both input iterators and output iterators.
Bidirectional iterators
–p
p–


predecrement an iterator
postdecrement an iterator
Random-access iterators

p+=i Increment the iterator p by i position
p-=i Decrement the iterator p by i positions
p+i Results in an iterator positioned at p incremented by i positions
p-i Results in an iterator positioned at p decremented by i positions
p[i] Return a reference to the element offset from p by i positions
p<p1 Return true if iterator p is less than iterator p1; otherwise, return false
p<=p1 Return true if iterator p is less than or equal to iterator p1; otherwise, return false
p>p1 Return true if iterator p is greater than iterator p1; otherwise, return false
p>=p1 Return true if iterator p is greater than or equal to iterator p1;otherwise, return false

What are the algorithms?

A crucial aspect of the STL is that it provides algorithms that can be used generically across a variety of containers.STL provides many algorithms you will use frequently to manipulate containers. Inserting, deleting, searching, sorting and others are appropriate for some or all of the STL containers.

STL includes approximately 70 standard algorithms. We provide live-code examples of most of these and summarize the others in tables. The algorithms operate on the container elements only indirectly through iterators. Many algorithms operate on a sequence of elements defined by pairs of iterators a first iterator pointing to the first element of the sequence and a second iterator pointing to one element past the last element of the sequence. Also, it is possible to create your own new algorithms that operate in a similar fashion so they can be used with STL containers and iterators.

Mutating-sequence algorithms

Mutating-sequence algorithms
copy                                              remove                         reverse_copy
copy_backward                              remove_copy                     rotate
fill                                                 remove_copy_if             rotate_copy
fill_n                                              remove_if                   stable_partition
generate                                        replace                             swap
generate_n                                    replace_copy                swap_ranges
iter_swap                                      replace_copy_if              transform
partition                                       replace_if                         unique
random_shuffle                             reverse                         unique_copy

Non-mutating-sequence algorithms

Non-Mutating-sequence algorithms
adjacent_find                                              find                         find_if
count                                                       find_each                 mismatch
count_if                                                   refind_end                 search_n
equal                                                       find_first_of               search_n

Non-Mutating-sequence algorithms accumulate                                                                       partial_sum inner_product                                                                  adjacent_difference

What is the Sequence Container?

The C++ Standard Template Library provides three sequence containers

  • vector
  • list
  • deque

Class vector and class deque both are based on arrays. One of the most popular containers in the STL is vector.

Applications that require frequent insertions and deletions at both ends of a container normally use a deque rather than a vector. Although we can insert and delete elements at the front and back of both a vector and a deque, the class deque is more efficient than a vector for doing insertions and deletions at the front.

Applications with frequent insertions and deletions in the middle and/or at the extremes of a container normally use a list, due to its efficient implementation of insertion and deletion anywhere in the data structure.

Insertion at the back of a vector is efficient.The vector simply grows, if necessary, to accomodate the new item.It is expensive to insert an element in the middle of a vector the entire portion of the vector elements occupy contiguous cells in memory just as do C or C++ “raw” arrays.

Vector Sequence Container

The class vector provides a data structure with contiguous memory locations. This enables efficient, direct access to any element of a vector by the subscript operator[], exactly as with a C or C++ “raw” array. Class vector is most commonly used when the data in the container must be sorted and easily accessible by a subscript. When a vector’s memory is exhausted, the vector allocates a larger contiguous area of memory, copies the original elements into the new memory and deallocates the old memory

Advantage of vector container

  • Choose the vector container for the best random-access performance
  • Objects of class vector provide rapid indexed access with the overloaded subscript operator[ ] because they are stored in contiguous storage like a C or C++ raw array
  • It is faster to insert many elements at once than one at a time

STL exception types

STL exception types Description
out_of_range Indicates when subscript is out of range
invalid_argument Indicates an invalid argument was passed to a function
length_error Indicates an attempt to create too long a container, string, etc
bad_alloc Indicates that an attempt to allocate memory with new failed because not enough memory was available.

list Sequence Container

The list sequence container provides an efficient implementation for insertion and deletion operations at any location in the container. If most of the insertions and deletions occur at the ends of the container, the deque data structure provides a more efficient implementation. The class list is implemented as a doubly-linked list every node in the list contains a pointer to the previous node in the list and to the next node in the list. This enables the class list to support bidirectional iterators that allow the container to be traversed both forwards and backward. Many of the list member functions manipulate the elements of the container as an ordered set of elements.

deque Sequence Container

Class deque provides many of the benefits of a vector and a list in one container. The term deque is short for “double-ended queue”.Class deque is implemented to provide efficient indexed access for reading and modifying its elements, much like a vector. Class deque is also implemented for efficient insertion and deletion operations at its front and back, much like a list. Class deque provides support for random-access iterators, so deque can be used with all STL algorithms. One of the most common uses of a deque is to maintain a first-in-first-out queue of elements.

Class deque provides the same basic operations as a class vector but adds a member functions push_front and pop_front to allow insertion and deletion at the beginning of the deque, respectively.

Write a Program on Standard library class deque test

#include<iostream>
using std::cout;
using std::endl;
#include<deque>
#include<algorithm>
int main()
{
std::deque<double>values;
std::ostream_iterator<double>output(cout," ");
values.push_front(2.2);
values.push_front(3.5);
values.push_front(1.1);
cout<<"values contains:";
for(int i=0;i<values.size();++i)
cout<<values[i]<<' ';
values.pop_front();
cout<<"\nAfter pop_front, values contains:";
std::copy(values.begin(),values.end(),output);
values[1]=5.4;
cout<<"\nAfter values[1]=5.4, values contains:";
std::copy(values.begin(),values.end(),output);
cout<<endl;
return 0;
}

OUTPUT:

values contains:3.5 2.2 1.1
After pop_front, values contains:2.2 1.1
After values[1]=5.4, values contains:2.2 5.4

Associative Containers

The STL’s associative containers provide direct access to store and retrieve elements by keys. The four associative containers are multiset, set, multimap and map. Each associative container maintains its keys in sorted order. Iterating through an associative container traverses it in the sort order for that container. Classes multiset and set provide operations for manipulating sets of values where the values are the keys there is not a separate value associated with each key. The primary difference between a multiset and a set is that a multiset allows duplicate keys and a set does not. Classes multimap and map provide operations for manipulating values associated with keys. The primary difference between a multimap and a map is that a multimap allows duplicate keys with associated values to be stored and a map allows only unique keys with associated values.

multiset Associative Container

  • A multiset supports bidirectional iterators but not a random-access iterator
  • The multiset associative container provides fast storage and retrieval of keys and allows duplicate keys
  • The ordering of the elements is determined by a comparator function object.
  • If the keys used in the associative containers are of programmer-defined data types, those types must supply the appropriate comparison operator

set Associative container

The set-associative container is used for fast storage and retrieval of unique keys. The implementation of a set is identical to that of a multiset, except that a set must have unique keys. Therefore, if an attempt is made to insert a duplicate key into the set, the duplicate is ignored; because this is the intended mathematical behavior of a set, we do not identify it as a common programming error. A set supports the bidirectional iterator.Header file <set> must included to use class set.

multimap Associative Container

  • The multimap associative container is used for fast storage and retrieval of keys and associated values are also called key/value pairs.
  • Many of the methods used with multisets and sets are also used with multimaps and maps
  • The elements of multimaps and maps are pairs of keys and values instead of individual values.
  • When inserting into a multimap or map, a pair objects that contain the key and value are used.
  • The ordering of the keys is determined by a comparator function object.
  • A multimap supports bidirectional iterators

Program on Standard Library multimap class template

#include<iostream>
using std::cout;
using std::endl;
#include<map>
typedef std::multimap<int,double,std::less<int>>mmid;
int main()
{
mmid pairs;
cout<<"There are currently"<<pairs.count(15)
    <<"pairs with key 15 in the multimap\n";
pairs.insert(mmid::value_type(15,2.7));
pairs.insert(mmid::value_type(15,99.3));
cout<<"After inserts, there are"
    <<pairs.count(15)
    <<"pairs with key 15\n\n";
pairs.insert(mmid::value_type(30,111.11));
pairs.insert(mmid::value_type(10,22.22));
pairs.insert(mmid::value_type(25,33.333));
pairs.insert(mmid::value_type(20,9.345));
pairs.insert(mmid::value_type(5,77.54));
cout<<"Multimap pairs contains:\nKey\tValue\n";
for(mmid::const_iterator iter=pairs.begin();iter!=pairs.end();++iter)
cout<<iter->first<<'\t'
    <<iter->second<<'\n';
cout<<endl;
return 0;
}

OUTPUT:

There are currently0pairs with key 15 in the multimap
After inserts, there are2pairs with key 15
Multimap pairs contains:
Key     Value
5       77.54
10      22.22
15      2.7
15      99.3
20      9.345                               
25      33.333                             
30      111.11 

map Associative Container

  • A map associative container is used for fast storage and retrieval of unique keys and associated values
  • Duplicate keys are not allowed in a map, so only a single value can be associated with each key.this is called a one-to-one mapping
  • A map is commonly called an associative array. Providing the key in a map‘s subscript operator [ ] locates the value associated with that key in the map.
  • Insertions and deletions can be made anywhere on a map.

Program on Standard Library map class template

#include<iostream>
using std::cout;
using std::endl;
#include<map>
typedef std::map<int,double,std::less<int>>mid;
int main()
{
mid pairs;
pairs.insert(mid::value_type(15,2.7));
pairs.insert(mid::value_type(30,111.11)); 
pairs.insert(mid::value_type(5,1010.1)); 
pairs.insert(mid::value_type(10,22.22)); 
pairs.insert(mid::value_type(25,33.333)); 
pairs.insert(mid::value_type(5,77.54)); 
pairs.insert(mid::value_type(20,9.345)); 
pairs.insert(mid::value_type(15,99.3));
cout<<"pairs contains:\nkey\tValue\n";
for(mid::const_iterator iter=pairs.begin();iter!=pairs.end();++iter)
cout<<iter->first<<'\t'
    <<iter->second<<'\n';
pairs[25]=9999.99;
pairs[40]=8765.43;
cout<<"\nAfter subscript operations, pairs contains:"
    <<"\nKey\tValue\n";
for(mid::const_iterator iter2=pairs.begin();iter2!=pairs.end();++iter2)
cout<<iter2->first<<'\t'
    <<iter2->second<<'\n';
cout<<endl;
return 0;

}

OUTPUT:

pairs contains:
key     Value
5       1010.1
10      22.22
15      2.7
20      9.345
25      33.333
30      111.11
After subscript operations, pairs contains:
Key     Value
5       1010.1
10      22.22
15      2.7
20      9.345
25      9999.99
30      111.11                             
40      8765.43 

Container Adapter in C++

The STL provides three containers adapters such as:

  • stack
  • queue
  • priority_queue

Adapters are not first-class containers, because they do not provide the actual data-structure implementation in which elements can be stored and because adapters do not support iterators. The benefit of an adapter class is that the programmer can choose an appropriate underlying data structure.

stack Adapter

The class stack enables insertions into deletions from the underlying data structure at one end. A stack can be implemented with any of the sequences containers: vector, list and deque.By default, a stack is implemented with a deque.

The stack operations are:

  • push: It is used to insert an element at the top of the stack
  • pop: It is used to remove the top element of the stack
  • top: It is used to get a reference to the top element of the stack
  • empty:It is used to determine whether the stack is empty
  • size: It is used to get the number of elements in the stack

Program on Standard library adapter stack

#include<iostream>
using std::cout;
using std::endl;
#include<stack>
#include<vector>
#include<list>
template<class T>
void popElements(T &stackRef);
int main()
{
std::stack<int>intDequeStack;
std::stack<int,std::vector<int>>intVectorStack;
std::stack<int,std::list<int>>intListStack;
for(int i=0;i<10;++i)
{
intDequeStack.push(i);
intVectorStack.push(i);
intListStack.push(i);
}
cout<<"Popping from intDequeStack:";
popElements(intDequeStack);
cout<<"\nPopping from intVectorStack";
popElements(intVectorStack);
cout<<"\nPopping from intListStack:";
popElements(intListStack);
cout<<endl;
return 0;
}
template<class T>
void popElements(T &stackRef)
{
while(!stackRef.empty())
{
cout<<stackRef.top()<<' ';
stackRef.pop();
}
}

OUTPUT:

Popping from intDequeStack:9 8 7 6 5 4 3 2 1 0
Popping from intVectorStack9 8 7 6 5 4 3 2 1 0
Popping from intListStack:9 8 7 6 5 4 3 2 1 0 

queue Adapter

Class queue enables insertions at the back of the underlying data structure and deletions from the front of the underlying data structure. A queue can be implemented with the STL data structure list or deque. By default, a queue is implemented with a deque.

The queue operations are:

  • push: It is used to insert an element at the back of the queue
  • pop: It is used to remove the element at the front of the queue
  • front: It is used to get a reference to the first element in the queue
  • back: It is used to get a reference to the last element in the queue
  • empty: It is used to determine whether the queue is empty
  • size: It is used to get the number of elements in the queue

Program on Standard library adapter queue

#include<iostream>
using std::cout;
using std::endl;
#include<queue>
int main()
{
std::queue<double>values;
values.push(3.2);
values.push(9.8);
values.push(5.4);
cout<<"Popping from values:";
while(!values.empty())
{
cout<<values.front()<<' ';
values.pop();
}  
cout<<endl;
return 0;
}

OUTPUT:

Popping from values:3.2 9.8 5.4 

What is Algorithms in C++?

STL class libraries of containers and algorithms were essentially incompatible with vendors. Early container libraries generally used inheritance and polymorphism, with the associated overhead of virtual function calls. Early libraries built the algorithms into the container classes as class behaviors.STL separates the algorithms from the containers. This makes it much easier to add new algorithms.STL is implemented for efficiency. It avoids the overhead of virtual function calls.

Programs on Sorting Algorithm

#include<iostream> 
#include <algorithm> 
 
using namespace std; 
 
void show(int a[]) 
{ 
for(int i = 0; i < 10; ++i) 
cout << a[i] << " "; 
} 
 
int main() 
{ 
int a[10]= {1, 5, 8, 9, 6, 7, 3, 4, 2, 0}; 
cout << "\n The array before sorting is : "; 
show(a); 
 
sort(a, a+10); 
 
cout << "\n\n The array after sorting is : "; 
show(a); 
 
return 0; 
 
}  

OUTPUT:

The array before sorting is : 1 5 8 9 6 7 3 4 2 0
The array after sorting is : 0 1 2 3 4 5 6 7 8 9 

Program on Searching on Algorithm

 #include <algorithm> 
#include <iostream> 
 
using namespace std; 
 
void show(int a[], int arraysize) 
{ 
for (int i = 0; i < arraysize; ++i) 
cout << a[i] << " "; 
} 
 
int main() 
{ 
int a[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; 
int asize = sizeof(a) / sizeof(a[0]); 
cout << "\n The array is : "; 
show(a, asize); 
 
cout << "\n\nLet's say we want to search for 2 in the array"; 
cout << "\n So, we first sort the array"; 
sort(a, a + asize); 
cout << "\n\n The array after sorting is : "; 
show(a, asize); 
cout << "\n\nNow, we do the binary search"; 
if (binary_search(a, a + 10, 2)) 
cout << "\nElement found in the array"; 
else
cout << "\nElement not found in the array"; 
 
cout << "\n\nNow, say we want to search for 10"; 
if (binary_search(a, a + 10, 10)) 
cout << "\nElement found in the array"; 
else
cout << "\nElement not found in the array"; 
 
return 0; 
}  

OUTPUT:

The array is : 1 5 8 9 6 7 3 4 2 0                                                 Let's say we want to search for
So, we first sort the array
The array after sorting is : 0 1 2 3 4 5 6 7 8 9
Now, we do the binary search
Element found in the array
Now, say we want to search for 10
Element not found in the array

Program on array algorithms in C++ STL

#include<iostream> 
#include<algorithm> // for all_of() 
using namespace std; 
int main() 
{ 
// Initializing array 
int ar[6] =  {1, 2, 3, 4, 5, -6}; 
 
// Checking if all elements are positive 
all_of(ar, ar+6, [](int x) { return x>0; })? 
cout << "All are positive elements" : 
cout << "All are not positive elements"; 
 
return 0; 
 
}  

OUTPUT:

 All are not positive elements 

Heap sort in C++

 #include <iostream> 
using namespace std; 
 
// To heapify a subtree rooted with node i which is 
// an index in arr[]. n is size of heap 
void heapify(int arr[], int n, int i) 
{ 
int largest = i; // Initialize largest as root 
int l = 2*i + 1; // left = 2*i + 1 
int r = 2*i + 2; // right = 2*i + 2 
 
// If left child is larger than root 
if (l < n && arr[l] > arr[largest]) 
largest = l; 
 
// If right child is larger than largest so far 
if (r < n && arr[r] > arr[largest]) 
largest = r; 
 
// If largest is not root 
if (largest != i) 
{ 
swap(arr[i], arr[largest]); 
 
// Recursively heapify the affected sub-tree 
heapify(arr, n, largest); 
} 
} 
 
// main function to do heap sort 
void heapSort(int arr[], int n) 
{ 
// Build heap (rearrange array) 
for (int i = n / 2 - 1; i >= 0; i--) 
heapify(arr, n, i); 
 
// One by one extract an element from heap 
for (int i=n-1; i>=0; i--) 
{ 
// Move current root to end 
swap(arr[0], arr[i]); 
 
// call max heapify on the reduced heap 
heapify(arr, i, 0); 
} 
} 
 
/* A utility function to print array of size n */
void printArray(int arr[], int n) 
{ 
for (int i=0; i<n; ++i) 
cout << arr[i] << " "; 
cout << "\n"; 
} 
 
// Driver program 
int main() 
{ 
int arr[] = {12, 11, 13, 5, 6, 7}; 
int n = sizeof(arr)/sizeof(arr[0]); 
 
heapSort(arr, n); 
 
cout << "Sorted array is \n"; 
printArray(arr, n); 
}
Sorted array is
5 6 7 11 12 13

Program on min and max

#include<iostream>
using std::cout;
using std::endl;
#include<algorithm>
int main()
{
cout<<"The minimum of 12 and 7 is:"
    <<std::min(12,7);
cout<<"\nThe maximum of 12 and 7 is:"
    <<std::max(12,7);
cout<<"\nThe minimum of 'G' and 'Z' is:"
    <<std::min('G','Z');
cout<<"\nThe maximum of 'G' and 'Z' is:"
    <<std::max('G','Z')<<endl;
return 0;
}

OUTPUT:

The minimum of 12 and 7 is:7
The maximum of 12 and 7 is:12
The minimum of 'G' and 'Z' is:G
The maximum of 'G' and 'Z' is:Z

Algorithms list

AlgorithmDescription
inner_product Calculate the sum of the products of two sequences by taking corresponding elements in each sequence,multiplying those elements and adding the result to a total
adjacent_difference Beginning with the second element in a sequence, calculate the difference between the current and previous elements and store the result.the first two input iterator arguments indicate the range of elements in the container and the third output iterator arguments indicates where the results should be stored.A second version of this algorithm takes as a fourth argument a binary function to perform a calculation between the current element and the previous element
partial_sum

Calculate a running total of the values in a sequence.The first two input iterator arguments indicate the range of elements in the container and the third output iterator argument indicates where the results should be stored.A second version of this algorithm takes as a fourth argument a binary function that performs a calculation between the current value in the sequence and the running total.
nth_element Use three random-access iterators to partition a range of elements.The first and last arguments represent the range of elements.The second srguments is the partitioning element’s location.After this algorithm executes, all elements to the left of the partitioning element are less than that element and all elements to the right of the partitioning element are greater than or equal to that element.A second version of this algorithm takes as a fourth argument a binary comparision function.
partition This algorithm is similar to nth_element, but it requires less powerful bidirectional iterators, making it more flexible than nth_element.Algorithm partition requires two bidirectional iterators indicating the range of elements to partition.The third element is a unary predicate function that helps partition the elements so that all elements in the sequence for which the predicate is true are to the left of all elements for which the predicate is false.
stable_partition This algorithm is similar to partition except that elements for which the predicate function returns true are maintained in their original order and elements for which the predicate function returns false are maintained in their original order.
next_permutation Next lexicographical permutation of a sequence
prev_permutation Previous lexicographical permutation of a sequence
rotate Use three forward iterator arguments to rotate the sequence indicate by the first and last argument by the number of positions indicated by subtracting the first argument from the second argument from the second argument
rotate_copy This algorithm is identical to rotate except that the results are stored in a seperate sequence indicated by the fourth argument an output iterator.The two sequences must have the same number of elements.
adjacent_find This algorithm returns an input iterator indicating the first of two identical adjacent elements in a sequence.If there are no identical adjacent elements, the iterator is positioned at the end of the sequence
partial_sort Use three random-access iterators to sort part of a sequence.The first and last argument indicates the ending location fo the sorted part of the sequence.By default, elements are ordered using operator<.The elements from the second argument iterator to the end of the sequence are in an undefined order.
partial_sort_copy Use two input iterators and two random-access iterators to sort part of the sequence indicated by the two input iterator arguments.The results are stored in the sequence indicated by the two random-access iterator arguments.By default,elements are ordered using operator <.The number of elements sorted is the smaller of the number of elements in the result and the number of elements in the original sequence
stable_sort The algorithm is similar to sort except that all equal elements are maintained in their original order

Translate »