STL in C++..

 c++ Overview with STL
____________________________________________________________________________________________________________________
C++ is a general-purpose
 programming language with a bias towards systems programming that supports efficient
 low-level computation, data abstraction, object-oriented programming, and generic programming.

____ __________________________________________________________________________________________________

C++ makes programming more enjoyable for serious programmers.
 C++ is a general-purpose programming language that
 – is a better C
 – supports data abstraction
 – supports object-oriented programming
 – supports generic programming
____________________________________________________________________________________________________________________ 

Arrays and Pointers
 A C array is simply a sequence of memory locations{RAM}. For example:
 int v [10]; // an array of 10 ints
 v[3] = 1; // assign 1 to v[3]
 int x = v[3]; // read from v[3]
 
 A C pointer is a variable that can hold an address of a memory location. For example:
 int *p ; // p is a pointer to an int
 p = &v[7]; // assign the address of v[7] to p
 *p = 4; // write to v[7] through p
 int y = *p ; // read from v[7] through p
______________________________________________________________________________________________________________________

Storage
 In C and C++, there are three fundamental ways of using memory:
 static memory
 Automatic memory
 Free store
 
 int g = 7 ; // global variable, statically allocated
 void f ()
 {
 int loc = 9 ; // local variable, stack allocated
 int * p = new int ; // variable allocated on free store
 / / ...
 delete p ; // return variable pointed to by p for possible re-use
 }
____________________________________________________________________________________________________________________

STL 
 Standard template library :

 STL is a generic library , i.e a same container or algorithm can be operated on any data types, 
 you don’t have to define the same algorithm for different type of elements.

 STL is mainly composed of :

 Algorithms 
 Containers
 Iterators
 
 Algorithms : STL provide number of algorithms that can be used of any container, irrespective of their type.
 Algorithms library contains built in functions that performs complex algorithms on the data structures.
 
 Example : reverse(), sort() 
 
 Containers : Container library in STL provide containers that are used to create data structures 
 like arrays, linked list, trees etc.
 
 Iterators : Iterators in STL are used to point to the containers. Iterators actually acts as a bridge between containers and algorithms.
 
 ____________________________________________________________________________________________________________________
 Container : Following are some common containers :

 vector : replicates arrays
 queue : replicates queues
 stack : replicates stack
 priority_queue : replicates heaps
 list : replicates linked list
 set : replicates trees
 map : associative arrays
 
 ______________________________________________________________________________________________________________________
 PAIR for Competitive programming : 
 
 pair <T1, T2> pair1;
 pair1 = make_pair(2,3);
 pair.first, pair.second;
 
 tuple<T1, T2, T3> tuple1; here in tuple we can have three heterogeneous data types, as compared to pair where we have two.
 ______________________________________________________________________________________________________________________

 Vector : Container library provides vectors to replicate dynamic arrays.
 
 vector< object_type > vector_name;
 
 operations we can perform on vector:
 vector<int> v;
 
 1. v.push_back(1) is used for inserting an element at the end of the vector
 
 2. insert(itr, element) inserts the element in vector before the position pointed by iterator itr.
 
 3. pop_back() is used to remove the last element from the vector.
 
 4. clear()
 
 5. vector_name.front() and vector_name.back() returns the first element and at the back of the vector 
 
 6. empty() returns true if vector is empty
 
 ______________________________________________________________________________________________________________________
 
 LIST : 

 1. insert(iterator, element) : inserts element in the list before the position pointed by the iterator.
 
 2. push_back(element) method is used to push elements into a list from the back.

 3. push_front(element) method is used to push elements into a list from the front.

 4. pop_front() removes first element from the start of the list.

 5. pop_back() removes first element from the end of the list.

 6. empty() This method returns true if the list is empty else returns false.

 7. size() This method can be used to find the number of elements present in the list.

 8. front() is used to get the first element of the list from the start .

 9. back() is used to get the first element of the list from the back.
 
 10. swap() Swaps two list, if there is exception thrown while swapping any element, swap() throws exception.

 11. reverse() This method can be used to reverse a list completely.

 12. sort() method sorts the given list. It does not create new sorted list but changes the position of elements within an existing list to sort it.

 sort based on compare function:
 
 bool compare_function(string &t1, string &t2) {
 return (t1.length < t2.length);
 }
 list.sort(compare_function); // will sort based on length in ascending order.

 13. merge() Merges two sorted list. It is mandatory that both the list should be sorted first.

 _______________________________________________________________________________________________________________________

 MAPS:
 
 Maps are used to replicate associative arrays. Maps contain sorted key-value pair.

 creating map and applying operations on it.

 map<key_type, value_type> map_name;
 
 Member_functions :
 
 1.at and [] Both at (throws an exception if key not found)& [] (will insert key if key not found in map) are used for accessing the elements in the map.
 
 2. empty() returns boolean true if the map is empty, else it returns Boolean false.
 
 3. size() returns number of entries in the map, an entry consist of a key and a value.

 4. max_size() returns the upper bound of the entries that a map can contain (maximum possible entries) based on the memory allocated to the map.

 5. insert() is used to insert entries in the map. Since keys are unique in a map, it first checks that whether the given key is already present
 in the map or not, if it is present the entry is not inserted in the map and the iterator to the existing key is returned
 otherwise new entry is inserted in the map.

 6. map::iterator i , j;
 i = m.find(2); // points to entry having key =2

 7. erase(iterator_itr) removes the entry from the map pointed by the iterator

 8. clear() will clear all the data from map

 9. begin() returns the iterator to the starting entry of the map.

 10. end() returns the iterator next to the last entry in the map.

 11. find() returns the iterator to the entry having key equal to given key (passed as parameter).

 HOW TO ITERATE THROUGH MAP :
 
 map<>::iterator itr;

 itr = map.begin()
 itr->first, itr->second;
 itr != map.end()

 __________________________________________________________________________________________________________________________

 STACK

 The stack container is used to replicate stacks in c++, insertion and deletion is always performed at the top of the stack.
 
 stack<object_type> stack_name;

 Member Functions of stack:
 
 1. push() is used to insert the element in the stack, the elements are inserted at the top of the stack.

 2. pop() This method is used to removes single element from the stack. It reduces the size of the stack by 1.

 3. top() This method returns the topmost element of the stack.

 4. size() returns the number of elements present in the stack.

 5. empty() checks if the stack is empty or not. empty returns true if the stack is empty else false is returned.

 6. swap() This method swaps the elements of the two stacks.

 ____________________________________________________________________________________________________________________________
 
 QUEUE
 
 The queue container is used to replicate queue in C++,
 insertion always takes place at the back of the queue and deletion is always performed at the front of the queue.
 
 queue< object_type > queue_name;

 Member functions of queue
 
 1. push() is used to insert the element in the queue. The element is inserted at the back or rear of the queue.
 
 2. pop() This method removes single element from the front of the queue and therefore reduces its size by 1.
 
 3. front() returns the front element of the queue.
 
 4. back() returns the element at the back of the queue. 
 
 5. size() returns the number of elements present in the queue, 
 
 6. empty() checks if the queue is empty or not.
 
 ______________________________________________________________________________________________________________________________
 
 PRIORITY QUEUE
 
 priority_queue is just like a normal queue except the element removed from the queue
 is always the greatest among all the elements in the queue, thus this container is usually used to replicate Max Heap in C++.
 
 Elements can be inserted at any order and it have O(log(n)) time complexity for insertion.

 priority_queue<int> pq;

 Member Function of Priority Queue

 1. push() This method inserts an element in the priority_queue.

 2. pop() This method removes the topmost element from the priority_queue (greatest element) ,reducing the size of the priority queue by 1.

 3. top () This method returns the element at the top of the priority_queue which is the greatest element present in the queue.

 4. size() returns the number of element present in the priority _queue,

 5. empty() returns Boolean true if the priority_queue is empty else Boolean false is returned.

 ______________________________________________________________________________________________________________________________
 
 DEQUE

 Deque is a shorthand for doubly ended queue. Deque allows fast insertion and deletion at both ends of the queue. 
 
 deque< object_type > deque_name;
 
 Member Functions of Deque
 
 1. push_back(element e) inserts an element e at the back of the deque.
 
 2. push_front(element e) inserts the element e at the front of the deque.
 
 3. pop_back() removes an element from the back of the deque
 
 4. pop_front removes an element from the front of the deque, both decreasing the size of the deque by one.
 
 Iterate through deque
 
 deque<int>::iterator itr;
 itr = dq.begin();
 while (itr != dq.end()) {
 cout << *itr << endl;
 itr++;
 }

 ______________________________________________________________________________________________________________________________
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s