C++ programming language has templates which basically allows functions and classes to work with generic types. This enables us to use functions or classes along with numerous different data types without needing to rewrite every time. STL stands for standard template library.

To put it in simpler terms, the C++ STL helps us to store, sort or manipulate objects thus making the program more robust.

COMPONENTS OF STL:

The STL has four major components -

1. Containers
2. Iterators
3. Algorithms
4. Functors

CONTAINERS:

Containers are template based generic classes used for storing objects and data. They are extensively used when we are dealing with many elements. They can further be classified as specified below -

Let’s discuss the utilities of these containers and the specific conditions they’re implemented in.

VECTOR :

Vectors are equivalent to the dynamic arrays with the ability to resize themselves when an element is added or deleted. Elements of a vector are placed in a contiguous storage location.

Use Vectors for -

1. Simple storage.
2. Quick lookups by using indexes.
3. Easy conversion to C style arrays.
4. Efficient traversal using iterators.
5. Serialisation.

In vectors, the data is inserted at the end. Avoid using vectors for non-integer indexing.

Syntax :

DEQUE :

Deques (double ended queues) are similar to vectors in most ways except with the ability to expand and contract at both the ends. They are more efficient than vectors for insertion and deletion of elements but can’t guarantee contiguous storage allocation.

Syntax: 

LIST :

List allows insertion and deletion of elements anywhere in the sequence as desired.

Use List for -

1. Insertion into anywhere in the list.
2. Efficient sorting.

A list doesn’t allow direct access to its elements. 

Syntax :

SET :

A set is an associative container storing elements of unique value. The elements are stored in a sorted order and the values are unindexed. Sets implement binary search trees.

Use Sets for -

1. Ordered dynamic storage.
2. Removal of duplicate values.

Syntax:

Note that set<datatype, greater<datatype>> setname; stores values in a descending order.

MULTISET :

Multisets are almost similar to sets with the exception that multisets can contain elements with the same values.

Syntax: 

MAP :

Map container holds elements by mapping their value against a particular key and the key value must be unique.

Use Maps for -

1. Constant lookups.
2. Dealing with key value pairs
3. Removing any duplicates. 
4. Searching for the existence of a key.

Maps are generally implemented as binary search trees.

Syntax: 

MULTIMAP :

Multimap is similar to map in addition that a multimap can have multiple elements with the same keys. Duplicate elements are allowed in a multimap. All the keys are kept in a sorted order.

Syntax -

STACK :

Stack employs Last In First Out order wherein the insertion and deletion of elements occur from one end of the container. Don’t forget to include the <stack> header file in the code. 

Syntax -

QUEUE :

Unlike stack, queue follows First In First Out approach implying that new elements are added at one end while elements are removed from another end.

Syntax: 

PRIORITY QUEUE :

A priority queue is a container adaptor just like queue and stack. Priority queues deal with First In First Out operations wherein the priority overrides arrival time. In a priority queue, an element with a higher priority is served before an element having low priority.

Syntax :

Refer the below flowchart to have a better understanding of when to use what container:

ITERATORS:

Iterators are objects which can point out elements inside a specific container. Iterators are used to traverse through the elements of the container. Their use in the program make things easier by reducing complexity and execution time of the program. The most obvious form of an iterator is a pointer. Iterators can be classified into five types based on their functionality. Refer the image given below to know more about them -

Now, different containers support different iterators as explained in the table below -

Operations of Iterators:

1. begin() - returns the beginning position of the container.
2. end() - returns after end position of the container.
3. advance() - uused for incrementing the iterator positionuntil the specified number which is mentioned in its arguments.
4. next() - returns the new iterator that the iterator would be pointing at after advancing through the positions mentioned in its arguments.
5. prev() - returns the new iterator that the iterator would be pointing at after advancing through the positions mentioned in its arguments.
6. inserter() - inserts elements at any specified position of the container.

ALGORITHM :

 Algorithms are the functions which are applied to the containers and those that provide operation for the content of the container. Algorithms can be further divided as -

1. Modifying algorithms are responsible for transforming the contents of the containers when they are executed. Most popular and widely used modifying algorithms include “swap” and “reverse” that swap two values and reverse the elements in the specific container respectively.

1. Non-modifying or non-transforming algorithms are the ones that do not change the contents of the container they are operating on. C++ STL supports multiple non-modifying algorithms. 

 Let’s take a concise look at different types of sorting algorithms -

Insertion sort :

Basic idea - iterate over all the elements; 

for each element check whether the element is larger than the largest value in the sorted array;

if larger - carry on,

if smaller, move the item to its correct position in the respective sorted array.

Insertion sort is particularly effective for small data sets. It is intuitive and easier to code. However it isn’t recommended for large sets of data.

Selection sort :

Basic idea - to iterate over all the elements;

check for each element if it is the smallest of the unsorted sublist, swap it with the left most unsorted element.

It involves a low usage of memory for small data sets and can sort in-place. It is not recommended for dealing with large data sets.

Bubble sort :

Basic idea - to iterate over all the elements;

for each element swap with the next if out of order;

whole process gets repeated until no swaps are needed.

Bubble sort works best when the list is sorted. It is however worse than insertion sort when it comes to dealing with large sets of data.

Merge sort :

Basic idea - to divide the list into its smallest unit;

then compare each element with adjacent list;

merge the two adjacent lists;

whole process is repeated.

Merge sort has higher efficiency on large data sets and a better space complexity than quick sort process.

Quick sort :

Basic idea - to choose a pivot from the array;

reorder the array so that all the elements with values less than the pivot come before the pivot, and all values greater than the pivot come after it;

recursively apply above steps to the remaining sub arrays.

It follows a divide and conquer algorithm, being very effective while handling large data sets. Quick sort can be parallelized but is not quite stable in certain instances. Also, take the median of the first, last and middle element as the pivot for an easier approach.

Searching algorithms as their name suggests are used for searching a particular element in the given container.

The prominent search algorithm in STL is a binary search which operates on a sorted array and searches for the element by dividing the array into half. 

General syntax -

Binary_search (start_addr, end_addr, key) 

Here, key is the element to be searched while start_addr and end_addr are the address of the first element and address of the last element respectively.

1. Numeric algorithms deal with various functions which work with/on numerical values. These functions can range from finding lcds, gcds to even calculating the sum of the elements in a container like arrays, vectors, etc over a given range. 

FUNCTORS

A C++ functor (also known as function object) is a class or struct object that can be called like a function. It overloads the function-call operator() and subsequently allows us to use an object like a function. Here’s how we can create a functor : 

As we can see, the function call operator () is being overloaded to create the functor. Functors are most commonly used along with STLs in a situation as follows:

The output of the above program is as follows:

CONCLUSION :

This was an attempt to lay a handy cheat sheet on C++ STL. It’s expected from one to form a concise understanding of the Standard Template Library of C++ and its components after going through this cheat sheet.