সোমবার, ৪ এপ্রিল, ২০১১

STL

STL stands for STANDARD TEMPLATE LIBRARY  in C++ which makes the programmer’s job too easier. STL decreases the coding size as well as the coding time. In programming , using STL  is preferred by an C programmer.
Here I am giving a description of STL frequently used by us.

Frequently used container classes of STL :
1.    vector
2.    queue
3.    string
4.    stack
5.    map
6.    list
7.    set
8.    pair


Vector class:
A vector models a dynamic array. Thus, it is an abstraction that manages its elements with a dynamic array.However, note that the standard does not specify that the implementation use a dynamic array. Rather, it follows from the constraints and specification of the complexity of its operation.

To use a vector we must include
#include <vector>
Using namespace std;


Declaration :
Vector<Elem> c;
 //Elem refers to all kind of data types like int,float,char,double,string,struct,class,pair etc.

All functions of vector class :
*vector <Elem> c          // Creates an empty vector without any elements
*vector <Elem> c1(c2)   // Creates a copy of another vector of the same type (all elements are copied)
*vector <Elem> c(n)      // Creates a vector with n elements that are created by the default constructor
*vector <Elem> c(n,elem)     //Creates a vector initialized with n copies of element  elem
*vector <Elem> c(beg,end)    //Creates a vector initialized with the elements of the range [beg,end)
*c.~vector()            //Destroys all elements and frees the memory
*c.size()                          //Returns the actual number of elements
*c.max_size()             //Returns the maximum number of elements possible
*capacity()               //Returns the maximum possible number of elements without reallocation
*reserve()                 //Enlarges capacity, if not enough yet
*c1 == c2               //Returns whether c1 is equal to c2
*c1 = c2                 //Assigns all elements of c2 to c1
*c.assign(beg,end)       //Assigns the elements of the range [beg,end)
*c1.swap(c2)               //Swaps the data of c1 and c2
*swap(c1,c2)              // Same (as global function)
*c.at(idx)               //Returns the element with index idx (throws range error exception if idx is out of range)
*c[idx]                       //Returns the element with index idx (no range checking)
*c.front()                      //Returns the first element (no check whether a first element exists)
*c.back()                   //Returns the last element (no check whether a last element exists)
*c.insert(pos,elem)   //Inserts at iterator position pos a copy of elem and returns the position of the new      element
*c.insert(pos,n,elem) //Inserts at iterator position pos n copies of elem (returns nothing)
*c.insert(pos,beg,end) //Inserts at iterator position pos a copy of all elements of the range [beg,end) (returns nothing)
*c.insert(pos,beg,end)   //Inserts at iterator position pos a copy of all elements of the range [beg,end) (returns nothing)
*c.push_back(elem) //Appends a copy of elem at the end
*c.pop_back()       //Removes the last element (does not return it)
*c.resize(num)      //Changes the number of elements to num (if size() grows, new elements are created by their default constructor)
*c.resize(num,elem)         // Changes the number of elements to num (if size() grows, new elements are copies of elem)
*c.clear()                  //Removes all elements (makes the container empty)


An example:

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

   int main()
   {
       //create empty vector for strings
       vector sentence;

       //reserve memory for five elements to avoid reallocation
       sentence.reserve(5);

       //append some elements
       sentence.push_back("Hello,");
       sentence.push_back("how");
       sentence.push_back("are");
       sentence.push_back("you");
       sentence.push_back("?");

       //print elements separated with spaces
       copy (sentence.begin(), sentence.end(), ostream_iterator .string. (cout," "));
           cout &lt;&lt; endl;

       //print &#039;&#039;technical data&#039;&#039;
       cout &lt;&lt; &quot; max_size(): &quot; &lt;&lt; sentence.max_size() &lt;&lt; endl;
       cout &lt;&lt; &quot; size():     &quot; &lt;&lt; sentence.size()     &lt;&lt; endl;
       cout &lt;&lt; &quot; capacity(): &quot; &lt;&lt; sentence.capacity() &lt;&lt; endl;

       //swap second and fourth element
       swap (sentence[1], sentence [3]);

       //insert element &quot;always&quot; before element &quot;?&quot;
       sentence.insert (find(sentence.begin(),sentence.end(),&quot;?&quot;),
                        &quot;always&quot;);

       //assign &quot;!&quot; to the last element
       sentence.back() = &quot;!&quot;;

       //print elements separated with spaces
       copy (sentence.begin(), sentence.end(),
             ostream_iterator(cout," "));
       cout &lt;&lt; endl;

       //print &quot;technical data&quot; again
       cout &lt;&lt; &quot; max_size(): &quot; &lt;&lt; sentence.max_size() &lt;&lt; endl;
       cout &lt;&lt; &quot; size():     &quot; &lt;&lt; sentence.size()     &lt;&lt; endl;
       cout &lt;&lt; &quot; capacity(): &quot; &lt;&lt; sentence.capacity() &lt;&lt; endl;

   }


The output of the program might look like this:

   Hello, how are you ?
     max_size(): 268435455
     size():     5
     capacity(): 5
   Hello, you are how always !
     max_size(): 268435455
     size():     6
     capacity(): 10










queue Class :
 queue is one of the data structures that is also called First-in-First-out [FIFO]. In STL there are also some built in functions for implementing queue.

To use queue we must include
#include<queue>
using namespace std; 

Declaration
queue<datatype>name;

Frequently used functions:

push(value);
front();
pop();
empty();


[The functions defined in Vector class can be used in queue also,check for further]

/////An example of queue and deque/////////////////////////////////////////////////////////////////////////////////////////
Uva 10935
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
#include<deque>
using namespace std;

int main(){

int a,b,n,i,k,c;

while(scanf("%d",&n)&&n){
 if(n==1){
cout<<"Discarded cards:"<<endl;
cout<<"Remaining card: 1"<<endl;
continue;
    }

deque<int>q;
queue<int>q2;

for(i=1;i<=n;i++){
    q.push_front(i);
    }

do{
k=q.back();
q2.push(k);
q.pop_back();

q.push_front(q.back());
q.pop_back();
}
while(q.size()>1);

c=0;
cout<<"Discarded cards:";
while(!q2.empty()){
cout<<" "<<q2.front();
if(c<n-2)
   cout<<",";
   c++;
q2.pop();
}

cout<<endl<<"Remaining card:";
while(!q.empty()){
cout<<" "<<q.front()<<endl;
q.pop_front();
 }
}
return 0;
}


///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



stack Class :
stack is one of the data structures that is also called Last-in-First-out [LIFO]. In STL

To use stack we must include
#include<stack>
using namespace std; 

Declaration
stack<datatype>name;

Frequently used functions:
push(value);
top();
pop();
empty();


[The functions defined in Vector class can be used in stack also,check for further]
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Uva 10420


map class
To use map we must include
#include<map>
using namespace std; 

Declaration
map<datatype1,datatype2>name;
//after execution of name map it can be accessed by name[datatype1_index]=datatype2_value
//every element in a map is by default 0. 
//datatype1 refers to the datatype of index and datatype2 refers to the datatype of value of map

Frequently used functions:
insert(pair<type1,type2>(key_element,value_element))
find(type val)
count(type val)
clear()
size()
erase(iterator i)
begin()
end()

[The functions defined in Vector class can be used in map also,check for further]


 Uva 10420 : implimentation of MAP
Uva 11946 :The code number



set class:

To use set we must include
#include<set>
using namespace std; 

Declaration
set<datatype>name;
//datatype refers to the datatype of values containing in the set
example:: set<string>s;

Frequently used functions:
insert(type val)
erase(type val)
empty()
find(type val)

[The functions defined in Vector class can be used in set also,check for further]


ITERATOR
An iterator is an object that can "iterator" (navigate) over elements. These elements may be all or part of the elements of a STL container. An iterator represents a certain position in a container. The following fundamental operations define the behavior of an iterator:
# operator*
# operato++
# operator==
# operator=
# begin()
# end()

Iterator is used for access an stl element. Declaration for an iteraror is varies as the STL  element. 
An example :[stl list and iterator]
#include <iostream>
#include <list>
using namespace std;

int main() { 
list<char> coll;    //list container for character elements // append elements from 'a' to 'z' 
for (char c='a'; c<='z'; ++c) 
{ coll.push_back(c); }

/*print all elements * - iterate over all elements */ 
 list<char>:: iterator pos; 
for (pos = coll.begin(); pos != coll.end(); ++pos) 
{ cout << *pos << ' ' ; }
  cout << endl;
  }




An example :[stl map and iterator]
#include <iostream>
#include <map>
using namespace std;

int main() { 
map<int,int> mp;    //list container for character elements // append elements from 'a' to 'z' 
for (int i=0;i<10;i++) 
{ mp[i]=i+11;}

/*print all elements * - iterate over all elements */ 
 map<int,int>:: iterator pos; 
for (pos = mp.begin(); pos != mp.end(); ++pos) 
{ cout << (*pos).first << ' ' ; }
  cout << endl;
for (pos = mp.begin(); pos != mp.end(); ++pos) 
{ cout << (*pos).second << ' ' ; }
  cout << endl;


}