LogoLogo

C++ STL Cheat Sheet

Prasun Das| June 28, 2022 at 5:53 PM | 6 minutes Read

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.



#c++#stl#cheatsheet#fundamentals to learn
View Count:5.5k
0

Comments

Similar Articles

Busting myths about web3

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......

Cover image

Operating System INTERVIEW QUESTIONS

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......

Cover image

Cloud Computing Cheatsheet

Getting started with cloud computing ?The words "cloud" and "web" will be interchangeable. What kind of business operates today without the internet? ...

Cover image

Software Engineering — SOFTWARE MAINTENANCE [Part-4]

SOFTWARE MAINTENANCE:Software Maintenance can be defined as the process of modifying a software product after its delivery. The main purpose of softwa...

Cover image

Software Engineering — Software Process Activities [Part - 3]

A quick summary upto what we did this far&nbsp; from this series:Software EngineeringSoftware engineering is a discipline of engineering concerned wit...

Cover image

Understanding Time Complexity with Interview Examples

Introduction:Understanding time complexity of a function is imperative for every programmer to execute a program in the most efficient manner. Time co...

Cover image

Software Engineering — Software Development lifecycle and software process(Part 2)

&nbsp;Software MethodologyA software methodology (which is also known as software process) is a set of related development Phases that leads to the pr...

Cover image

Software Engineering [Part 1] - Introduction

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 ...

Cover image

SQL Interview Questions

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...

Cover image

SQL CHEATSHEET

Introduction: What is SQL?To understand SQL, we must first understand databases and database management systems (DBMS).Data is essentially a collectio...

Cover image

Computer Networking Cheatsheet (Last Minute Notes)

&nbsp;Networking: Importance in real life!Using a computer for work, as well as for personal use, ha...

Cover image

Last Minute Preparation Cheat Sheet for Quantitative Aptitude

FORMULA LIST:ALGEBRA :1.Sum of first n natural numbers = n(n+1)/22.Sum of the squares of first n nat...

Cover image

Database Management System Last Minute Notes [Part - 2]

ER-DiagramWhat are ER Models ?An Entity Relationship Diagram (ERD) is a visual representation of dif...

Cover image

Database Management System Last Minute Notes [Part - 1]

What is actually DBMS?A Database Management System (DBMS) is system software used to manage the orga...

Cover image

C Cheatsheet

C CHEATSHEETINTRODUCTION:C programming language was developed by Dennis Ritchie of Bell Labs in 1972...

Cover image

C Interview Questions — 2022

C is a general purpose high-level language most popular amongst coders, it is the most compatible, e...

Cover image

C++ CHEAT SHEET

C++ was conceived in the late 1970s to overcome the limitations of C. It&nbsp; is an extension of th...

Cover image

Python [Advanced] Interview Questions — 2022

Interview Questions are a great source to test your knowledge about any specific field. But remember...

Cover image

Basic Python [Core] Interview Questions for Freshers and Short Sample Answers — 2022

The most popular high-level, multipurpose programming language right now is Python.Python supports p...

Cover image

Python Cheat Sheet - Learn the basics of Python

IntroductionPython is a high-level programming language with dynamic binding and high-level inherent...

Cover image

Basic Java Interview Questions for Freshers and Short Sample Answers — 2022

Interview Questions are a great source to test your knowledge about any specific field. But remember...

Cover image

Java OOP Cheat Sheet — A Quick Guide to Object-Oriented Programming in Java

Object-Oriented Programming or better known as OOPs is one of the major pillars of Java that has lev...

Cover image

Learn Java: Basics to Advanced Concepts [Java Cheatsheet]

Java is a high-level programming language known for its robustness, object-oriented nature, enhanced...

Cover image