Learn C++ Standard Template Library Part-01

 

Standard Template Library is a library of defined data structures which have defined functions with most efficient algorithms.

We have to only implement these predefined data structures and algorithms in competitive programming for making our code more efficient.

For understanding basic STL by which we can solve most of the questions in  Competitive Programming we have to only study some topics and to learn and understand their implementation.

1) Vectors   2) List  3) Pairs 4) Maps  

We can solve most of the questions using these only and after having command on implementation of these we will learn some other topics.

I will give some links of resources to learn and practice for better understanding and following this you will get better understanding of C++ STL.

                 Vectors

You can understand vectors as an array the only difference is that it has property of resizing and hence it is known as dynamic array.

 

• Use this for using vectors- #include <vector>.
• Intializing vectors - vector<data-type> vector_name;
• For iterating through elements of vector there are many iterators.
• Iterators - let a integer vector - vector<int> v; begin() //pointer to first element of vector --) v.begin() end() //pointer to element after last element of vector **remember this is not a pointer to last element --) v.end()
• Functions - There are so many functions but we will be talking about most important one. Size/Length: size() //return size of vector --) v.size() resize() //it resizes the vector --) v.resize(n) // n is new size empty() //return true if vector is empty else false --) v.empty() Element Access: operator [i] //use to access element at index i same as array --) v[0] //this will give value of first element at(i) //same as [] operator --) v.at(i) Modifiers(For changes in vector): assign() //assign new elements in vector replacing old ones --) v.assign(3,9) // three 9 will be inserted in array cout<<v[0]<<" "<<v[1]<<" "<<v[2]; will result in 9 9 9 . push_back() //inserts an element at v.end() --) v.push_back(5); //5 is added in vector in last pop_back() //used to pop or remove elements from a vector from the back. --) v.pop_back() ; //will remove that 5 which we added in push_back() insert() //in this we have to give a place(pointer) where we have to insert an element and value of the element. --) v.insert(v.begin(),5) // 5 will be inserted before first element. **Element will be inserted before the given pointer. erase() //It is used to remove elements from a given position or range. --) v.erase(v.begin()) //5 will be removed which is first element. swap() //used to swap the elements of one vector with another of same type ** sizes may differ --) v.swap(another vector of same type as v) clear() //used to remove all the elements of a vector --) v.clear() // now v.empty() will return True emplace() //same as insert() --) v.emplace(v.begin(),7) // insert 7 at before first element emplace_back() //same as push_back() --) v.emplace_back(7) // 7 is inserted after last element
  

Links for more resources and practice -

1) For knowledge of basic implementation - Click Here 2) How to merge two vectors - Click Here

            

      List

 

Before starting about this data structure watch this video to have a brief knowledge of List - Link to video .

There are two types of linked list - Doubly Linked List ans Single Linked List. In stl when we talk about list then it refers to doubly linked list and for single linked list we use forward_list.

• Use this for using list- #include <list> .
• Intializing list - list<data-type> list_name;
• For iterating through elements of list there are many iterators.
• Iterators - let a integer list - list<int> l; begin() //pointer to first element of list --) l.begin() end() //pointer to element after last element of list **remember this is not a pointer to last element --) l.end()
• Functions - Most functions of list are same as of vectors. Size/Length: size() //return size of list --) l.size() empty() //return true(1) if list is empty else false(0) --) l.empty() Element Access: front() //return reference to first element of list --) l.front() back() //return reference to last element of list --) l.back() Modifiers(For changes in vector): ** Read all the modifiers of vector once more -- Those are same for list two. Some extra modifiers are : push_front() //inserts an element at beginning of list(head) --) l.push_front(5); //5 is added in vector in last pop_front() //removes an element from beginning of list(head) --) l.pop_front(); //5 will be removed which was added in previous method. Operations on list: splice() //Transfer elements from list to list  //Transfer only the element with in a range

  list1_name.splice (iterator position, list2)
                  or 
  list1_name.splice (iterator position, list2, iterator i)
                  or 
  list1_name.splice (iterator position, list2, iterator first, iterator last)

  remove() //Remove elements with specific value --) l.remove(Element)

  Input  : list list{1, 2, 3, 4, 5};
           list.remove(4);
  Output : 1, 2, 3, 5
  

  remove_if() //remove all the elements if given condition is satisfied. --) l.remove_if(odd)

  Input  : list list{1, 2, 3, 4, 5};
           list.remove_if(odd);
  Output : 2, 4

  unique() //removes all duplicate consecutive elements from the list --) l.unique() sort() //sort the list in ascending order --) l.sort() merge() //merges two sorted lists into one --)list l1,l2; //let list is not empty --) l2.sort();l1.sort(); //list is sorted --) l1.merge(l2);

Links for more resources and practice -

1) For knowledge of basic implementation - Click Here

This article has explained Vector and List in brief .
Next Topics of STL in next part.