A Complete guide to CPP STL (Standard Template Library)

CPP is one the most popular language for competitive programming and that is because of its speed and its Standard Template Library(STL). The CPP STL (Standard Template Library) is a powerful set of CPP template classes that provide classes and functions with templates that implement many popular and commonly used algorithms and data structures like vectors, lists, queues, and stacks.  

For example, while solving a programming problem you want to use a stack, so instead of creating it from scratch, you will use the built-in stack data Structure from the STL library.

CPP STL has three important components

1. Algorithms
2. Containers
3. Iterators

Algorithms

STL provides a large number of algorithms for searching and sorting. Some of the well-known algorithms are:

1. sort: sort element in a range.  Syntax: sort(begin, end);
2. binary_search: Perform a binary search to test if a value exists in the sorted sequence. Syntax: binary_search( start, end, key);
3. HEAP
   • • make_heap: Create max heap from range.
     • push_heap: Push and element into a heap.
     • pop_heap: Pops an element from the heap.
     • sort_heap: Performs heap sort.
     • is_heap: Check if the range is a heap and return true or false.
     • min: returns minimum among two elements
4. max: returns maximum among two values.
5. count: Counts the occurrence of a particular number in a given range.
6. find: Returns an iterator to the first element in the range [first, last) that compares equal to value. If no such element is found, the function returns last.

Container

A container is a holder object that stores a collection of other objects (its elements). The container manages the storage space for its elements and provides member functions to access them, either directly or through iterators (reference objects with similar properties to pointers).

• Sequence containers

  1. Vector (#include<vector>): Vectors are sequence containers representing arrays that can change in size.

     Syntax: vector<data_type> variable;
     Example —> vector<int> vect;      //v is a vector of type int

     • push_back(): Removes the last element in the vector, effectively reducing the size by one.
     • pop_back(): Adds a new element at the end of the vector, after its current last element.
     • assign(): Assigns new contents to the vector, replacing its current contents, and modifying its size accordingly. Ex: vet.assign(10, -1);    // 10 ints with value -1
     • erase(): Removes from the vector either a single element (position) or a range of elements ([first, last)).
     • clear(): Removes all elements from the vector, leaving the container with a size of 0.
     • size(): Returns the number of elements in the vector.
     • empty(): Returns whether the vector is empty (i.e. whether its size is 0).
     • insert(): The vector is extended by inserting new elements before the element at the specified position.
     • capacity(): Return the size of allocated storage capacity.
     • front(): Returns a reference to the first element in the vector.
     • back(): Returns a reference to the last element in the vector.

  2. ---

     List  (#include<list>): Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions. List containers are implemented as doubly-linked lists.
     

     Syntax: list<data_type> variable;
     Example —> list<int> lst;      //lst is a list of type int
     

     • push_back(): Adds a new element at the end of the list container, after its current last element.
     • pop_back(): Removes the last element in the list container.
     • push_front(): Inserts a new element at the beginning of the list, right before its current first element.
     • pop_front(): Removes the first element in the list container.
     • assign(): Assigns new contents to the list container, replacing its current contents, and modifying its size accordingly.
     • begin(): Returns an iterator pointing to the first element in the list container.
     • end(): Returns an iterator referring to the past-the-end element in the list container. The past-the-end element is the theoretical element that would follow the last element in the list container. It does not point to any element, and thus shall not be dereferenced.
     • empty(): Returns whether the list container is empty or not(i.e. whether its size is 0).
     • size(): Returns the number of elements in the list container.
     • front(): Returns a reference to the first element in the list container.
     • back(): Returns a reference to the last element in the list container.
     • erase(): Removes from the list container either a single element (position) or a range of elements.
     • clear(): Removes all elements from the list container (which are destroyed), and leaving the container with a size of 0.
     • sort(): Sorts the elements in the list, altering their position within the container.
     • unique(): The version with no parameters, removes all but the first element from every consecutive group of equal elements in the container.
       

       ---

  3. Deque (#include<deque>): Double-ended queue are sequence containers with dynamic sizes that can be expanded or contracted on both ends (either front or back). Both vectors and deques provide a very similar interface and can be used for similar purposes but unlike vectors, contiguous storage allocation may not be guaranteed. (Direct access is no possible in deque).

     Syntax: deque<data_type> variable;
     Example —> deque<int> deq;      //deq is a deque of type int
     

     • begin(): Returns an iterator pointing to the first element in the deque container.
     • end(): Returns an iterator referring to the past-the-end element in the deque container.
     • rbegin(): Returns a reverse iterator pointing to the last element in the container (i.e., its reverse beginning)
     • rend(): Returns a reverse iterator pointing to the theoretical element preceding the first element in the deque container (which is considered its reverse end).
     • size(): Returns the number of elements in the deque container.
     • resize(n): Resizes the container so that it contains n elements
     • empty(): Returns whether the deque container is empty (i.e. whether its size is 0).
       
     • operator([]): Returns a reference to the element at position n in the deque container(the first element has a position of 0 (not 1).
     • at(): Returns a reference to the element at position n in the deque container object. If the requested position is out of range by throwing an out_of_range exception.
     • front(): Returns a reference to the first element in the deque container.
     • back(): Returns a reference to the last element in the container.
       
     • push_back(): Adds a new element at the end of the deque container, after its current last element. 
     • push_front(): Inserts a new element at the beginning of the deque container, right before its current first element.
     • pop_back(): Removes the last element in the deque container, effectively reducing the container size by one.
       
     • pop_front(): Removes the first element in the deque container, effectively reducing its size by one.
     • insert(): Insert new elements before the element at the specified position.
     • erase(): Removes from the deque container either a single element (position) or a range of elements ([first, last)).
       
     • clear(): Removes all elements from the deque, leaving the container with a size of 0.

• Container adaptors:

  1. 1. Stack (#include<stack>): Stacks are a type of container adaptor, which operate in a LIFO order (last-in-first-out), where elements are inserted and removed only from one end.
        

        Syntax: stack<data_type> variable;
        Example —> stack<int> st;      //st is a stack of type int
        

        • push(): Inserts a new element at the top of the stack, above its current top element.
        • pop(): Removes the element on top of the stack, effectively reducing its size by one.
        • top(): Returns a reference to the top element in the stack.
        • size(): Returns the number of elements in the stack.
        • empty(): Returns whether the stack is empty: i.e. whether its size is zero.
          

          ---

     2. Queue (#include<queue>): Queue is a type of container adaptor, which operate in a FIFO order (first-in-first-out), where elements are inserted from one end and removed from another end.
        

        Syntax: queue<data_type> variable;
        Example —> queue<int> que;      //que is a queue of type int
        

        • push(): Inserts a new element at the end of the queue, after its current last element.
        • pop(): It removes the first “oldest” element from the queue, whose value can be retrieved by calling member queue:: front.
        • front(): Returns a reference to the first “oldest” element in the queue.
        • back(): Returns a reference to the last element in the queue.
        • size(): Returns the number of elements in the queue.
        • empty(): Returns whether the queue is empty: i.e. whether its size is zero.
          

          ---

     3. Priority Queue (#include<queue>): Priority queues are a type of container adapters, specifically designed such that the first element of the queue is the greatest of all elements in the queue and elements are strictly in non-increasing order.
        

        Syntax: priority_queue<data_type> variable;
        Example —> priority_queue<int> pque;      //pque is a priority queue of type int
        

        • push(): Inserts a new element in the priority_queue
        • pop(): Removes the element on top of the priority_queue, effectively reducing its size by one. The element removed is the one with the highest value.
        • top(): Returns a constant reference to the top element in the priority_queue.
        • size(): Returns the number of elements in the priority_queue.
        • empty(): Returns whether the priority_queue is empty: i.e. whether its size is zero.

 Associative Containers

1. 1. 1. Set (#include<set>): Sets are containers that store unique elements following a specific order. In a set, the value of an element also identifies it. The value of the elements in a set cannot be modified once in the container but they can be inserted or removed from the container. Set doesn’t support random access iterator.
         

         Syntax: set<data_type> variable;
         Example —> set<int> st;      //st is a set of type int
         

         • begin(): Returns an iterator referring to the first element in the set container.
         • end():  Returns an iterator referring to the past-the-end element in the set container. 
         • rbegin(): Returns a reverse iterator pointing to the last element in the container (i.e., its reverse beginning).
         • rend(): Returns a reverse iterator pointing to the theoretical element right before the first element in the set container (which is considered its reverse end).
         • insert(): Insert a new element, effectively increasing the container size by the number of elements inserted.
         • empty(): Returns whether the set container is empty (i.e. whether its size is 0).
           
         • size(): Returns the number of elements in the set container.
         • erase(): Removes from the set container either a single element or a range of elements ([first, last)).
         • clear(): Removes all elements from the set container (which are destroyed), leaving the container with a size of 0.
         • find(): Searches the container for an element equivalent to value and returns an iterator to it if found, otherwise, it returns an iterator to set::end.
           
         • count(): Searches the container for elements equivalent to value and returns the number of matches.
         • lower_bound( value ): The function returns an iterator pointing to the element in the container which is equivalent to a value passed in the parameter.
         • upper_bound( value ): Returns an iterator pointing to the immediate next element which is just greater than value.
           

           ---

      2. Map (#include<map>): Maps are associative containers that store elements formed by a combination of a key-value and a mapped value, following a specific order. No two mapped values can have the same key values. The mapped values in a map can be accessed directly by their corresponding key using the bracket operator([ ]).
         

         Syntax: map<data_type1, data_type2> variable;
         Example —> map<char,int> mymap;    //mymap is a map of type <char,int>
         

         • begin(): Returns an iterator referring to the first element in the map container.
         • end():  Returns an iterator referring to the past-the-end element in the map container.
         • rbegin(): Returns a reverse iterator pointing to the last element in the container (i.e., its reverse beginning).
         • rend(): Returns a reverse iterator pointing to the theoretical element right before the first element in the map container (which is considered its reverse end).
         • insert( pair<char, int> ): Insert a new element, effectively increasing the container size by the number of elements inserted. insert() will not overwrite an existing element. Ex: mymap.insert(make_pair(‘b’, 7)); or mymap.insert({‘b’, 7});
         • empty(): Returns whether the map container is empty (i.e. whether its size is 0).
           
         • size(): Returns the number of elements in the map container.
         • operator []: If k matches the key of an element in the container, the function returns a reference to its mapped value. If k does not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value.  Ex: mymap[‘a’] = 12; cout<<mymap[‘a’]; 
         • at: Returns a reference to the mapped value of the element identified with key k. If k does not match the key of any element in the container, the function throws an out_of_range exception. Ex: mymap.at(“a”) = 10;  cout<<mymap.at(“a”);   // output: 10 
         • erase(): Removes from the set container either a single element or a range of elements ([first, last)).
         • clear(): Removes all elements from the set container (which are destroyed), leaving the container with a size of 0.
         • find(): Searches the container for an element equivalent to value and returns an iterator to it if found, otherwise, it returns an iterator to set::end.
           
         • count(): Searches the container for elements equivalent to value and returns the number of matches.
         • lower_bound( value ): The function returns an iterator pointing to the element in the container which is equivalent to a value passed in the parameter.
         • upper_bound( value ): Returns an iterator pointing to the immediate next element which is just greater than value. 

Iterator

An iterator is an object (like a pointer) that points to an element inside the container. We can use iterators to move through the contents of the container using a set of operators (with at least the increment (++) and dereference (*) operators).

Iterators make the algorithm independent of the type of container used.

Syntax: container_type<parameters>::iterator;
Example —> vector<int>::iterator;
           map<char,int>::iterator;
           set<int>::iterator;

Pair

This class couples together with a pair of values, which may be of different types (T1 and T2). The individual values can be accessed through its public members first and second.

Syntax: pair<data_type1, data_type2> pair_name;
Example —> pair<int,char> my_pair;
           my_pair = make_pair(5,'a');
          
//Result: my_pair.first = 5, my_pair.second = 'a'

• • • make_pair(x,y): Constructs a pair object with its first element set to x and its second element set to y.
    • swap: The contents of pair x are exchanged with those of y. Both pair objects shall be of the same type

We hope you enjoyed a detailed introduction to the CPP STL library. If you found anything incorrect or want to add something, please comment.