Monday, May 20, 2013

STL in a nutshell

STL or Standard Template Library is a C++ library which provides many popular data structures and algorithms. So that when you program you don't have to write the implementations from scratch and can code faster during competitions.

STL has a lot of things but you don't use everything , so here is the basic functions which you will need to know most of the time. You can always check cplusplus.com for getting complete information on any topic.

VECTORS:

It is similar to the linked list. Elements are added to the end(by default) of the list and the elements can be easily accessed using index address like arrays.
Header file: vector

#include < vector >
using namespace std;

int main()
{
	int i;
	vector<int> vec;
	for(i=0; i<5; i++)
	{
		vec.push_back(i);			//0 1 2 3 4
	}
	for(i=0; i<vec.size(); i++)
	{
		if(i&1)
			vec[i]+=10;			//0 11 2 13 4
	}
	vec.pop_back();					//0 11 2 13
	vec.erase(vec.begin() + 1);			//0 2 13
	return 0;
}

In the above example a vector of type "int" is created and can be replaced by any datatype ( even structures, classes or vectors itself)
The commonly used functions are:
  • push_back(a) : inserts an element at the end of the vector.
  • size() : returns the no of elements in the vector.
  • pop_back() : deletes the last element.
  • erase( pointer ) : deleted the element at given pointer.
  • begin() / end() : returns the pointer to the begin / end of the vector. (Note that the last element is vec.end() -1 ).
  • clear() : removes all the elements in the vector.

SETS :

It is similar to the Binary Search Tree. The insertion and searching is done in logarithmic time.
Header file: set

#include <set>
#include <iostream>
using namespace std;

int main()
{
	int i;
	set<long int> s;
	for(i=0; i<5; i++)
	{
		s.insert(i);			//0 1 2 3 4
	}
	s.insert(3);				//No new element is inserted
	if(s.find(8)==s.end())
		s.insert(8);			//inserts 8 if not found in set
	else
		s.insert(10);			//inserts 10 if already present
	for(set<long int>::iterator it=s.begin(); it!=s.end(); it++)
		cout<< *it <<" ";
	return 0;
}

In the above example a set of type "long int" is created.
The commonly used functions are:
  • insert(a) : inserts a new element in logarithmic time. Does NOT inserts if element is already present.
  • find(a) : returns the pointer to the element if exists else returns the pointer to the end.
  • size(): returns the no of elements in the set.
set<datatype>::iterator ptr - This statement is used to declare a variable of type set pointer.
vector<datatype>::iterator ptr - declares a vector pointer.

MAP :

It maps the key to value. Keys are unique. This is a one-to-one mapping.
Header file : map

#include <map>
#include <iostream>
using namespace std;

int main()
{
	int i;
	map<char, int> m;
	for(i=0; i<26; i++)
		m['a'+i]=i+100;
	if(m.find('a'+5)==m.end())
		cout<<"Key not found";
	else
		cout<<m['a'+5];
	m.erase('d');
	for(map<char,int>::iterator it=m.begin(); it!=m.end(); it++)
		cout<<it->first<<" "<<it->second<<endl;
	return 0;
}

In the above example the key is of character type and the value is of integer type. The searching is done in logarithmic time.
The "first" keyword returns the key and "second" keyword returns the value.


PRIORITY QUEUE :


It implements MAX HEAP by default (for MIN HEAP see below ).
Header file : queue

#include <queue>
#include <iostream>
using namespace std;

int main()
{
	int i;
	priority_queue<int> pq;
	for(i=0; i<5; i++)
		pq.push(i);
	while(!pq.empty() )
	{
		cout<<pq.top()<<" ";
		pq.pop();
	}
	return 0;
}

top function returns the maximum element. So the output will be : 4 3 2 1 0

To implement MIN HEAP you can use the following statement :
priority_queue<int, vector<int>, greater<int> > pq;


Other info :

The functions which are common to all the above containers(to know why they are called containers please see the website given in the start) are :
  • size() - returns the no of elements.
  • empty() - returns true or false depending on whether the container is empty or not.
  • find(a) - returns the pointer to the element if found else returns the pointer to the end.
  • clear() - removes all the elements.

Other useful header files :

Utility :

  • pair<datatype, datatype> p
    stores a pair of two datatypes.
  • make_pair(a, b)
    returns a pair of a and b.

#include <utility>
#include <iostream>
using namespace std;

int main()
{
	pair<int,int> p(3,5);
	cout<<p.first<<" "<<p.second<<endl;
	p=make_pair(34,67);
	cout<<p.first<<" "<<p.second;
	return 0;
}

String :


#include <string>
#include <iostream>
using namespace std;

int main()
{
	string a="hello", b="world!";
	string c=a+" "+b;
	cout<<c;
}


Algorithm :

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

int main()
{
	int a[]={4,6,3,1,2};
	int i;
	vector<int> vec(a, a+5);
	sort(a,a+5);
	for(i=0; i<5; i++)
		cout<<a[i]<<" "; // 1 2 3 4 6

	sort(vec.begin(), vec.end() );
	for(i=0; i<vec.size(); i++)
		cout<<vec[i]<<" ";

	reverse(a,a+5);
	for(i=0; i<5; i++)
		cout<<a[i]<<" "; // 6 4 3 2 1
}

To create a vector from an array you can use the above method i.e.
vector<datatype> vec(pointer of  the array from which values are required , pointer of the array upto which values are required).


I hope this will help you to start using STL .

No comments:

Post a Comment