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.
The STL has four major components -
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.
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 -
In vectors, the data is inserted at the end. Avoid using vectors for non-integer indexing.
Syntax :
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 allows insertion and deletion of elements anywhere in the sequence as desired.
Use List for -
A list doesn’t allow direct access to its elements.
Syntax :
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 -
Syntax:
Note that set<datatype, greater<datatype>> setname; stores values in a descending order.
Multisets are almost similar to sets with the exception that multisets can contain elements with the same values.
Syntax:
Map container holds elements by mapping their value against a particular key and the key value must be unique.
Use Maps for -
Maps are generally implemented as binary search trees.
Syntax:
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 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 -
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:
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 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:
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 -
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.
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:
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.
WHAT IS WEB3?Web3 is the catch-all term for the vision of an upgraded version of the internet aimed at giving power back to the users. It is truly the......
Operating Systems is one of the core subjects for a computer science student. As such a lot of important questions are asked on this subject in interv......
Getting started with cloud computing ?The words "cloud" and "web" will be interchangeable. What kind of business operates today without the internet? ...
SOFTWARE MAINTENANCE:Software Maintenance can be defined as the process of modifying a software product after its delivery. The main purpose of softwa...
A quick summary upto what we did this far from this series:Software EngineeringSoftware engineering is a discipline of engineering concerned wit...
Introduction:Understanding time complexity of a function is imperative for every programmer to execute a program in the most efficient manner. Time co...
Software MethodologyA software methodology (which is also known as software process) is a set of related development Phases that leads to the pr...
Software Engineering is a subject that requires when you are a software developer as well as when you are in your college preparing for a semester or ...
Are you getting ready for your SQL developer job interview?You've come to the correct place.This tutorial will assist you in brushing up on your SQL s...
Introduction: What is SQL?To understand SQL, we must first understand databases and database management systems (DBMS).Data is essentially a collectio...
Networking: Importance in real life!Using a computer for work, as well as for personal use, ha...
FORMULA LIST:ALGEBRA :1.Sum of first n natural numbers = n(n+1)/22.Sum of the squares of first n nat...
ER-DiagramWhat are ER Models ?An Entity Relationship Diagram (ERD) is a visual representation of dif...
What is actually DBMS?A Database Management System (DBMS) is system software used to manage the orga...
C CHEATSHEETINTRODUCTION:C programming language was developed by Dennis Ritchie of Bell Labs in 1972...
C is a general purpose high-level language most popular amongst coders, it is the most compatible, e...
C++ was conceived in the late 1970s to overcome the limitations of C. It is an extension of th...
Interview Questions are a great source to test your knowledge about any specific field. But remember...
The most popular high-level, multipurpose programming language right now is Python.Python supports p...
IntroductionPython is a high-level programming language with dynamic binding and high-level inherent...
Interview Questions are a great source to test your knowledge about any specific field. But remember...
Object-Oriented Programming or better known as OOPs is one of the major pillars of Java that has lev...
Java is a high-level programming language known for its robustness, object-oriented nature, enhanced...