Getting Started With C++ STL

C++ is a widely used language for developing applications such as games, operating systems, and low-level programming that requires better control of hardware on the PC or server.

C++ is considered a very efficient language for competitive programming because it is faster in execution than many other programming languages. You may have noticed, though, that many coders manage to write their code much more quickly and concisely than you.

Introduction To C++ STL Libraries

The Standard Template Library is a collection of C++ template classes which provide common programming data structures and functions. The functions and structures are vectors, lists, stacks, etc.

STL has four components

1. Algorithms
2. Containers
3. Functions
4. Iterators

Algorithms: The header algorithm defines a collection of functions specially designed to be used on ranges of elements. They act on containers and provide means for various operations for the contents of the containers.

Containers: Containers or container classes store objects and data. There are in total seven standards “first-class” container classes and three container adaptor classes and only seven header files that provide access to these containers or container adaptors.

Functions: The STL includes classes that overload the function call operator. Instances of such classes are called function objects or functors. Functors allow the working of the associated function to be customized with the help of parameters to be passed.

Iterators: As the name suggests, iterators are used for working upon a sequence of values. They are the major feature that allows generality in STL.

Containers in C++ STL:

Vectors: Vectors hold the properties of dynamic arrays and are capable to resize themselves upon insertions and deletions. This makes their use more efficient than using arrays.

Vectors are traversed using iterators.

Example

#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> cards;
for(int i=0;i<5;++i)
{
cards.push_back(i);
}
for(int i=0;i<5;++i)
{
cout<<cards[i];
} 
}

Basics of Vectors:

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
int main(){
vector<int> A= {1,2,5,4,6};
//To access the second element
cout<<A[1]<<endl;
//To use functions like sort
sort(A.begin(),A.end()); //O(nlogn)
//Binary Search in Vectors
bool present= binary_search(A.begin(),A.end(),3); //False
cout<<present<<endl;
//To insert more elements: push_back();
A.push_back(0);
//To iterate a vector an iterator is used. To display the value holded by iterator pointer is used.
vector<int>::iterator itr;
for(itr=A.begin();itr!=A.end();++itr){
cout<<*itr;
}
cout<<endl;
bool present2=binary_search(A.begin(),A.end(),6);//TRUE
cout<<present2<<endl;
//lowerbound means that first element greater than the given element which includes the given element
//Upper bound finds the first strictly greater element than the given element
vector<int>::iterator i1=lower_bound(A.begin(),A.end(),2);
cout<< *i1<<endl;
vector<int>::iterator i2=upper_bound(A.begin(),A.end(),2);
cout<<*i2<<endl;
//lower bound and upper bound on a sorted vector is done in O(logn) time.
//To know the number of time a number has occurred, perform upper and lower bound and substract the iterators.
cout<<i2-i1<<endl; //Prints 1
}
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool f(int a,int b){
return a>b;
cout<<x<<” “<<endl;
}
}
}
int main(){
vector<int> A={77,88,55,11,33,33};
vector<int>::iterator itr;
for(itr=A.begin();itr!=A.end();++itr){
cout<<*itr<<” “;
}
cout<<endl;
sort(A.begin(),A.end());
vector<int>::iterator Aa=lower_bound(A.begin(),A.end(),33);
vector<int>::iterator B=upper_bound(A.begin(),A.end(),33);
cout<<*Aa<<endl<<*B;
//To know how many times a number occurs in a vector simply do lower_bound followed by the upper_bound and the difference of the two is the number of times the number has occurred.
cout<< endl<<B-Aa<<” “<<endl;
//To sort a vector in decreasing order, there is a overloaded function sort() which takes in a comparator function
// f() as the third argument. The comparator function returns true or false and to sort in descending order the value
// it returns should be return a<b;The comparator function is always declared in the global space.
sort(A.begin(),A.end(),f);
vector<int>::iterator it1;
for(it1=A.begin();it1!=A.end();++it1){
cout<< *it1<<” “;
}
//To print Elements of a vector instead of vectors, simply for loops can be given
for(int x: A){
cout<<x<< “ ”<<endl; 
}
}

Auto keyword in C++:

(Type Inference in C++)

Type inference means automatic deduction of the data type of an expression. The type deduction after c++ 11 can be left on the compiler itself and the type can be assigned at the runtime.

auto keyword:

It specifies the type of variable that is being declared from its initializer. If the return type of a function is auto then it will be evaluated by the return type expression at the runtime.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
vector<int> A={1,4,2,6,8,3};
for(auto it=A.begin();it!=A.end();++it){
cout<< *it<< “ “;}}

The code given above prints 1 4 2 6 8 3

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
vector<int> A={1,4,2,6,8,3};
for(auto it=A.begin();it!=A.end();++it){
cout<< *it<< “ “;}
//To iterate over values of a vector and change them
// use the refernce
for(int &x:A){
x++;
cout<<x<<” “;}
}

List in C++ STL

Normally list in STL refers to doubly linked list. In doubly linked list insertion, deletion and traversal of elements can be done from both of the endpoints. Like vectors, lists are also sequential containers. Lists allow non-contiguous memory allocation.

Note: To implement a singly linked list, the forward list is used.

Example:

1 — List: Basic Example

#include <iostream>
#include<list>
#include<iterator>
using namespace std;
void showList(list<int>l){
 for(auto it=l.begin();it!=l.end();++it){
 cout<<” “<<*it<<” “<<endl;
 }
}
int main()
{
 list<int> l;
 for(int i=0;i<10;++i)
 {
 l.push_back(i*2);
 }
 showList(l);
}

2 — List insertion at the beginning.

#include <iostream>
#include<list>
#include<iterator>
using namespace std;
void showList(list<int>l)
{
for(auto it=l.begin();it!=l.end();++it)
{
 cout<<” “<<*it<<” “<<endl;
}
}
int main()
{
 list<int> l;
 for(int i=0;i<10;++i)
 {
 l.push_fron(i*3);
 }
 showList(l);
}

Operations to be used along List:

• push_back(g) — Adds a new element at the back
• push_front(g) — Adds new element at the front
• pop_back() — Deletes the element from the back
• pop_front() — Deletes the element from the start
• reverse() — Reverses the linked list
• sort() — sorts the list in ascending order
• front() — Returns the value of the first element
• back() — Returns the value of the last element
• list:: begin() — Returns an iterator pointing to the first element
• list:: end() — Returns the iterator pointing to the last element
• rbegin() — returns a reverse iterator
• rend() — returns a reverse iterator which points to the position before the beginning of the list
• empty() — Checks if the list is empty or not
• insert() — Inserts new elements at the specified position
• erase() — Removes a single element from the list at a specified position
• assign() — Assigns new elements to list by replacing current elements and resizes the list
• remove() — Removes all elements from the list (Which are equal to the given element)
• size() — Returns the size of the list
• list:: clear() — Removes all elements and makes the size of list 0
• list:: swap() — Swap elements of the contents of one list with another list of same type and size.
• list splice() — Used to transfer elements from one list to another
• merge() — Merges two sorted lists into one
• emplace() — Extends list by inserting a new element at a given position

Set in C++ STL:

Set is an associate container. A set is used to hold unique elements. (The value of an element is used to identify the element). The set does not allows modification of values of elements once they have been stored in a set.

Example:

#include<iostream>
#include<set>
#include<iterator>
using namespace std;
int main(){
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
auto it;
for(it=s.begin();it!=s.end();++it){
cout<< “ “<<*it<<endl;
}
}

//Output: 1 2 3 4

Program : Using Stack to store elements in strictly descending order:

#include<iostream>
#incude<set>
#include<iterator>
using namespace std;
int main(){
set<int,greater<int>> s;
s.insert(5);
s.insert(1);
s.insert(3);
for(auto it=s.begin();it!=s.end();++it){
cout<< “ “<<*it<<endll
}
//OUTPUT: 5 3 1

Operations in STL:

• 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 size of the set
• max_size() — Returns the maximum number of elements that a set can hold
• empty() — Returns whether the set is empty.
• cbegin() — Returns a constant iterator pointing to the last element in the container
• crend() — Returns a constant iterator pointing to the position just before the first element in the container
• insert(const g) — Inserts a new element in the set
• erase(iterator position) — Removes elements from the specified position
• erase(const g) — Removes element “g” from the set
• clear() — Removes all elements from the set
• find(const g) — Returns an iterator the element (if found, else returns the iterator to the end)
• count(const g) — Returns 1 or 0 based on element ‘g’ is present in the set or not.

Press ENTER to exit console.

Map in C++

Maps are associative containers that store the elements in key-value pairs. The value is mapped with a key.

Maps are a part of the C++ STL. Maps are associative containers that store elements formed by a combination of a key-value and a mapped value, following a specific order.

Map Template:

std::map <key_type, data_type>

Declaration:

map<string,int>m; //Creates a map m where key_type is of type string and data_type is of type int.

Size:

int length=m.size(); //Gives the size of the map.

Insert:

m.insert(make_pair(“hello”,9)); //Here the pair is inserted into the map where the key is “hello” and the value associated with it is 9.

Erasing an element:

m.erase(val); //Erases the pair from the map where the key_type is val.

Finding an element:

map<string,int>::iterator itr=m.find(val); //Gives the iterator to the element val if it is found otherwise returns m.end() .

E.g.

map<string,int>::iterator itr=m.find(“Maps”); //If Maps is not present as the key value then itr==m.end().

Accessing the value stored in the key:

To get the value stored of the key “MAPS” we can do m[“MAPS”] or we can get the iterator using the find function and then by itr->second we can access the value