Standard Template Library (STL)

Containers
- Simple/Sequence Containers
  - vector, list, pair, forward_list (singly linked list)
- Container Adapter/ Derived Containers
  - Don't support iterators, hence to print the content, use while(!container.empty()) thing.
  - (build upon simple containers)
  - (stack, queue, deque, heap, priority queue)
- Associative Containers
  - Implemented as a sorted Data structure; data can be searched in O(logn)
  - set, map, multimap, and multiset
  - ordered map/set have an order and are implemented as self-balancing BST(Red black Trees).
  - Keys may not need to be integral.
  - Requirement: operator < should be defined.
- unordered Associative Containers
  - Implement an unordered Data structure; data can be searched in O(1) on avg.
  - unordered_set, unordered_map, unordered_multimap, unordered_multiset
  - unordered map/set uses hashing and has no-ordering.
Algorithms
- binary_search()
- find()
- reverse()
- sort()
- and more...
Iterators (only 5 types)
- An object(like a pointer) that points to an element in the container, helps in accessing data within the container.
- We use an iterator to move through elements of the container.
- Random access iterators are like pointers like we do arithmetic on the pointer(so we can jump via these iterators).
- Forward, Bidirectional, Input, and Output iterators only move one at a time(+1, ++) and are not like pointers.
- Why use them: Iterators help in moving inside the container irrespective of the type of container, whether it is a map, set, vector, list...
Comparator/Functor/Comparison object
- helps in writing our comparison function that can be passed to algorithms to make comparisons
- It is an object(cmp) of a class that has () operator overloaded so to call comparison using cmp(Obj A, Obj B).

// Example: Template + Iterator + Comparator

// generic function to find something in a container
template<class Iterator, class T, class Comparator>
Iterator search(Iterator start, Iterator end, T key, Comparator cmp ){
  // Iterator - Thanks to iterator, to work irrespective of Container.
  while(start != end){
    if(cmp(*start, key)){ // Thanks to Generic Comparator
      return start;
    }
    start++;
  }
  return end;
}

class Phone{
  string name;
  float price;
  public:
    Phone(){
    }
    Phone(string name, float price){
      this->name = name;
      this->price = price;
    }
};

class PhoneComparator{
  bool operator()(Phone A,  PhoneB){
    return A.price == B.price;
  }
};

int main(){
  Phone OnePlus("OnePlus", 100);
  Phone Xiaomi("Xiaomi", 2000);

  PhoneComparator cmp;

  vector<Phone> cv;
  cv.push_back(OnePlus);
  cv.push_back(Xiaomi);
  auto it = search(cv.begin(), cv.end(), OnePlus, cmp);
  if(it == cv.end()){
    cout<<"Phone Not Found in vector";
  }else{
    cout<<"Phone Found in vector: "<<it->name<<endl;
  }

  list<Phone> phoneList; // independent of Container- Thanks to Iterator.
  phoneList.push_back(OnePlus);
  phoneList.push_back(Xiaomi);
  auto it = search(phoneList.begin(), phoneList.end(), OnePlus, cmp);
  if(it == phoneList.end()){
    cout<<"Phone Not Found in list";
  }else{
    cout<<"Phone Found in list: "<<it->name<<endl;
  }
}

Note

All STL containers are passed by value.
So make sure to use & in formal parameters in case you want to reflect changes done inside function into STL container.

Vector<T>

Dynamic Size
Rich Library functions
Easy to know size via size()
No need to pass size to function
Can be returned from the function
Initialized with default values
Can easily copy a vector to another via v1 = v2
Passed by value to function. so if you want to modify the vector make sure to use & and make the vector pass by reference.

  vector<int> v;
  // vector size
  v.size();
  // looping over vector
  for (int i = 0; i < v.size(); ++i){
    cout<<v[i]<<" ";
  }

  // looping(no updation) via for each loop
  for (auto x: v){
    x+=10; // will not modify vector
    cout<<x<<" ";
  }
  // looping(`updation => use reference`) via for each loop
  for (auto &x: v){ // & also help in avoiding copying larger objects.
    x+=10; // will `modify` vector
    // cout<<x<<" ";
  }
  // looping via iterator
  vector<int>::iterator vit;
  for(vit=v.begin(); vit!=v.end(); vit++){
    cout<<*vit<<" ";
  }
  // vector initialization
  vector<int> vec= {10,20,30,40};
  vector<int> vec{10,20,30,40}; // no equal sign
  vector<int> vec2(10,5) // 10 elements each with 5 value

functions same as c++ strings, almost all. see in my cpp blog

Internal Implementation be like

#include <iostream>
using namespace std;
class Vector {
  int *arr;
  int num_elements;
  int capacity;

public:
  Vector(int size) {
    arr = new int[size];
    num_elements = 0;
    capacity = size;
  }
  void insert(int val) {
    if(num_elements < capacity) {
        arr[num_elements]=val;
        num_elements++;
    } else {
        resize();
        arr[num_elements]=val;
        num_elements++;
    }
  }

  int getAt(int index){
    return arr[index];
  }

  void resize() {
    int* tempArr=new int[capacity*2];
    capacity*=2;

    for(int i=0; i<num_elements; i++) {
        tempArr[i]=arr[i];
    }

    delete [] arr;
    arr=tempArr;
  }

  int length() {
    return num_elements;
  }

  void print() {
    for(int i=0; i<num_elements; i++)
        cout << arr[i] << " ";
    cout << endl;
  }
};

danger

Very Important:

v.size() returns an unsigned integer.
So if size is 0 and we do v.size() - i, it will be 0 - i.
=> a very big positive number( >10⁹ in 32 bit and >10¹⁸ in 64 bit)
=> loop runs for a very long time.
so always do int(v.size()) to get 0-1 = -1 and not all 1s in unsigned interger which becomes 2^31-1 or 2^63-1.
or never subtract anything from v.size() at all.

list<T> and forward-list<T>

you can not call sort(l.begin(), l.end()) because sort required random access iterator but l.begin() or l.end() returns bidirectional iterators.
Instead use l.sort() to sort.

list<int> l{2,3,4,5,5}; // doubly linked list
  /*
  methods available:-
  - l.push_back()
  - l.push_front()
  - l.pop_back()
  - l.pop_front()
  - l.remove(val)
  - l.erase(iterator)
  - l.insert(iterator, value)
  - l.sort()
  - l.reverse()
  - l.empty()
  - l.front()
  - l.back()
 */

forward_list<int> fl; // singly linked list

deque<T>

can use deque always instead of stack and queue.
O(1) random access to any element.

Very Important

Even though it is a queue, random access is possible in the case of the deque.
=> can access dq[i] in constant time.

deque<int> dq;
dq.push_front(10);
dq.pop_front(20);
dq.push_back(10);
dq.pop_back(10);

// random acess iterator
deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_back(30);
dq.push_back(40);
dq.push_back(50);
dq.push_back(60);

cout<< dq[3] <<endl;
cout<< dq.at(4) <<endl;

Stack<T>

A Container Adapter that uses deque as underline container.
No random Access, No iterators, No range-based loops, No curly braced-initialization.

inside <stack>

push()
top()
pop()
size()
empty()

stack<int> s;
s.push(90);

// use while stack is not empty loop to print the stack.
auto scopy = s;
while(!scopy.empty()){
  cout<<scopy.top()<<" ";
  scopy.pop();
}
cout<<endl;

Queue<T>

A Container Adapter based on deque as well.
No random Access,No iterators, No range-based loops, No curly braced-initialization.
inside <queue>
- queue<int> q;
- push()
- pop()
- empty()
- size()
- front()
- back()
Internals of Queue
Intitally queue has front and rear pointers both points to -1 => Queue is empty.
Both rear and front points to same index (not equal to -1) => Queeu has only one elements.
Queue Full condition => rear + 1 = front.

void enqueue(queue, front, rear, item){
  // check for full quuee
  if((rear + 1) % n == front) {
    cout<<"overflow";
    return;
  }

  if(rear == -1){
    front = rear = 0;
  }else{
    rear = (rear + 1) % n
  }
  queue[rear] = item;
}

void dequeue(queue, front, rear, item){
  // check for empty quuee
  if(rear == front and rear==-1) {
    cout<<"underflow";
    return;
  }

  if(rear == front){
    front = rear = -1;
  }else{
    front = (front + 1) % n;
  }
}

Priority Queue<T> or Heap

Inside <queue> header file only
A priority queue is just like a normal queue data structure except that each element inserted is associated with a “priority”.
It supports the usual push(), pop(), top(), etc operations, but is specifically designed so that its first element is always the greatest of the elements it contains, i.e. max heap.
In STL, priority queues take three template parameters:
```
template <class T, class Container = vector<T\>, class Compare = less<typename Container::value_type>>
class priority_queue;
```
- The first element of the template defines the class of each element. It can be user-defined classes or primitive data types. Like in your case it can be int, float, or double.
- The second element defines the container to be used to store the elements. The standard container classes std::vector and std::dequeue fulfill these requirements. It is usually the vector of the class defined in the first argument. Like in our case it can be vector<int>, vector<float>, vector<double>.
- The third element is a comparative class. By default, it is less<T> but can be changed to suit your need. For min heap, it can be changed to greater<T>.
using vector as the underline container
- priority_queue<int> pq;
- priority_queue<int, vector<int> , greater<int\> > pq;
- push() => O(logn)
- pop() => O(logn)
- top() => O(1)
- empty() => O(1)
- size() => O(1)

info

Important

Use this ⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇

pqmax pq(arr, arr+n) - => creates a max heap from an array rather than pushing elements one by one. - Inplace Algorithm to convert the array into a heap - 2 ways, Top-down, and Bottom-up. - Top-down is unoptimized, and bottom-up is optimized.

  :::note Top-Down Approach
    - start from the left of the array and keep on making the array till ith index as the heap.
    - Time Complexity.
      - For h=1, operations = 1
      - For h=2, operations = 2*1 (for both nodes at h=2, at max need to move 1 step above,i.e. the top)
      - For h=3, operations = 4*2 (for both nodes at h=3, at max need to move 2 step above,i.e. the top)
      - For h=4, operations = 8*3 (for both nodes at h=4, at max need to move 3 step above,i.e. the top)
      - and so on...
      - For h=h, operations = 2^(h-1) * h
      - Total = Σ (h\*2<sup>(h-1)</sup>)
      - It is an AGP.
      - = 2 + n*(logn-1)= **O(nlogn)**.
      - Solved by hand.❤️️
  :::

  :::note Bottom-up Approach
    - This approach is better as the time complexity to build a heap is O(n).
    - It builds heap using a bottom-up approach which is O(n).
    - It does it by going backward from the last internal node of the array floor(n/2) and calls heapify(i).
    - **Proof:** Let Tree is Perfect tree, which is also a CBT right? Yes. -
    - Every Perfect tree is a CBT.
    - => all internal nodes are till height (h-1).
    - and all leave nodes are at height h. If we look what we are doing.

    ```cpp
      for every node from floor(n/2) to 1:
        heapify(node)
    ```
    - Assuming heights start from 1.
    - We can say for nodes at height h-1 [#nodes = 2<sup>h-2</sup>], we call heapify at max 1 time only.
    - For nodes at height h-2 [#nodes = 2<sup>h-3</sup>]. We call heapify at max 2 times only and so on.
    - Worst case Time will be 2<sup>h-2</sup> + 2<sup>h-3</sup>\*2 + 2<sup>h-4</sup>\*3 + ....
    - = 2<sup>h-2</sup> * (1 + 2/2<sup>1</sup> + 3/2<sup>2</sup> + 4/2<sup>3</sup> + ...)
    - Also we know total number of nodes = n = 2<sup>h</sup> - 1
    - and (1 + 2/2<sup>1</sup> + 3/2<sup>2</sup> + 4/2<sup>3</sup> + ...) is approximately 3.
    - Hence, **Time Complexity is O(n)**.
  :::

:::

Furthermore, approach of pushing elements one by one is costlier and it will be O(nlogn) , log(i) being for each insertion, similar when printing heap, nlogn time.
In CBT, total number of internal nodes are floor(n/2)
It also implies leaves start from the floor(n/2) + 1 and go till n.

:::

Custom Sorting in PQ

Have to use Comparator class/struct and implement () opearator

  struct PairCmp {
    bool operator()(Pair a , Pair b) {
      return a.second > b.second;
    }
  };

  priority_queue<Pair, vector<Pair>, PairCmp> pq;
  pq.push({100, 20});
  pq.push({150, 200});
  pq.push({190, 120});
  pq.push({110, 1340});
  pq.push({90, 10});

  while(!pq.empty()){
    cout<<pq.top().first<<","<<pq.top().second<<endl;
    pq.pop();
  }

::: Tip

We can push -ve of number in heap, to make default maxheap -> minheap.
If we are inserting a pair<int, int>{a,b} into maxheap, we can get anyorder, by pushing and poping any combination. using
{a, b} ---> order will be [desc by a, desc by b]
{a, -b} ---> order will be [desc by a, asc by b]
{-a, b} ---> order will be [asc by a, desc by b]
{-a, -b} ---> order will be [asc by a, asc by b]

:::

Application of Heaps
- Dijkstra's Algorithm
- Prim's Algorithm
- Huffman Coding
- Heapsort

set<T>

inside #include<set>
uses RBTree as a data structure.

  insert() // logn
  find() // logn
    - to check if the element is present or not.
    - returns iterator if found else return end() iterator.
  count() // logn
    - returns 1 or 0
    - can be used in place of find()
  size() // O(1)
  erase() // logn
  clear()
  begin() // O(1)
  end() // O(1)
  empty() // O(1)
  // as elements are sorted in set
  // it has binarysearch functions.
  lower_bound() // logn
    - returns Iterator pointing to first element equal to or greater than key, or end(). This function returns the first element of a subsequence of elements that matches the given key. If unsuccessful it returns an iterator pointing to the first element that has a greater value than the given key or end() if no such element exists.
    - always returns first element >= key, so if we want to find < key, we do lower_bound() - 1`**
  upper_bound() // logn
    - always returns first element > key, so if we want to find <= key, we do upper_bound() - 1`
    - returns the upper element.
    - Iterator pointing to the first element greater than key, or end().

caution

Note for lower and upper bound functions

If you are doing -1 (it--).
Make sure returned iterator doesn't points to begin().
If you are doing +1 (it++).
Make sure returned iterator doesn't points to end() or rbegin().

Always sorted output when print.
can make decreasing using set<int, greater<int> > s;
No Duplicates are stored.
All begin() and end() access containers can use short for-loop for (auto &x: set_name) for printing/
as well as for loop with iterators.

  // we can initialize the set with vector
  vector<int> v={1,3,5,67,8,3,2};
  set<int> s(v.begin(), v.end());

  // Set for custom datatypes
  struct Person{
    string name;
    bool operator < (Person other) {
      return this->name < other.name; // lexiographically sorted increasing order
    }
  };

  set<Person> s;
  s.insert({"shaurya"});
  s.insert({"priyansh"});
  for(auto person: s){
    cout<<person.name<<endl;
  }

Application of set
- Store a stream of data in a sorted way.

tip

Very+Most Important:

Set can not update an element.
It have to delete the old val and insert the new val.
let say set<pair<int,int> > already has pair<40,30>,
now I want to change value to <40,100>.
Then I have to find pair <40,30> using auto it = set.find({40,30}),
erase it set.erase(it).
and then insert the new val set.insert({40,100});

map <T,U>

inside #include<map>
uses RBTree as a data structure.
map<int, int> m;
operator[] (logn)
- to modify and create a key-value pair
- m[20] is used to access key 20, if key is not present, it inserts 20 with 0 in case of value being int. other way is count(key)
count(key) to see if it is present or not.
- if present then use [] to access or modify
- else don't.

  insert(make_pair(key,value)) or insert({key,value})
  find() // logn
  count() // logn
  erase() // logn
  clear() // O(n) for cleanup
  size() // O(1)
  begin() // O(1)
  end() // O(1)
  empty() // O(1)
  lower_bound() // logn
  upper_bound() // logn

Always sorted output when print.
can make decreasing using map<int, string, greater<int\> > m;
No Duplicates are stored.
All begin() and end() access containers can use short for-loop for (auto &x: map_name) for printing, x is a pair.
as well as for loop with iterators.
Application same as set.
- Sorted Stream of data with key value pairs

Tips and Tricks:

Always use map instead of unordered_map as map guarantees to have operations in log(n) time.
but unordered_map can in the worst case goes to O(n).
So using map inside for(1..n) loop can result in n² rather than nlogn.
But if you get TLE from map. replace map with unordered_map and try to submit.

unordered_set <T>

inside #include<unordered_set>
uses Hashing as the data structure.
no ordering here.
for loop gives unpredicted output.
insert()
find()
count()
size()
empty()
clear()
erase()
All operations are constant O(1) on average.

  unordered_set<int> us; // uses hashing
  us.insert(109);
  us.insert(10);
  us.insert(9);
  // printing
  for (auto x: us){
    cout<<x<<" ";
  }
  // or
  for (auto it = us.begin(); it!=us.end(); it++){
    cout<<(*it)<<" ";
  }

unordered_map<T,U>

inside #include<unordered_map>
uses Hashing as the data structure.
no ordering here.
for loop gives unpredicted output.
insert() or operator[].
find()
count()
size()
empty()
clear()
erase()
All operations are constant O(1) on average.

  unordered_map<int, bool> um; // uses hashing
  um.insert({109, true});
  um.insert({9, false});
  um.insert({10, true});
  // printing
  for (auto x: um){
    cout<<x.first<<","<<x.second<<" ";
  }
  // or
  for (auto it = um.begin(); it!=um.end(); it++){
    cout<<(*it).first<<","<<(*it).second<<" ";
  }

similarly multiset inside #include<set>
similarly multimap inside #include<map>
For Multiset
- st.erase(val) will delete all occurences of val from multiset.
- but to remove only a single val, even if multiple exist use have to use st.erase(st.find(val)).

STL Algorithms (More Useful Functions)

- INT_MAX, LONG_MAX, LLONG_MAX // (in #include<climits\>)
- INT_MIN, LONG_MIN, LLONG_MIN // (in #include<climits\>)
- int max()
- int min()
- void swap(a,b)
- int gcd(a,b) // availble from c++17, (a, b and return value) can be long long as well.
- int __gcd(a,b) // availble from c++17, (a, b and return value) can be long long as well.

- iterator max_element(v.begin(), v.end())
- iterator max_element(v.begin(), v.end(), mycmp)
- iterator max_element(arr, arr + n) // <algorithm\>
- iterator max_element(arr, arr + n,cmp) // <algorithm\>
// bool cmp(Obj A, Obj B) {return A.prop < B.prop;}

- iterator min_element(v.begin(), v.end())
- iterator min_element(v.begin(), v.end(), mycmp)
- iterator min_element(arr, arr + n) // <algorithm\>
- iterator min_element(arr, arr + n,cmp) // <algorithm\>

- int accumulate(v.begin(), v.end(), 0) // in <numeric\>
- int accumulate(arr, arr + n, 0) // in <numeric\>
- int accumulate(v.begin(), v.end(), mult)
// int mult(Obj A, Obj B) {return A.prop * B.prop;}

- void sort(v.begin(), v.end(), greater<int\>);//sort in decreasing order
- void sort(v.begin(), v.end(), mycomp); //sort in decreasing order
- void sort(arr, arr + n, greater<int\>);//sort in decreasing order
- void sort(v.begin(), v.end(), cmp); // in <algorithm\>

- iterator find(container.begin(), container.end(), key) // linear search

- bool binary_search(container.begin(), container.end(), key) // <algorithm\>
- bool binary_search(container.begin(), container.end(), key, mycmp) // <algorithm\>
- iterator lower_bound(arr, arr + n, value_tobe_searched) // <algorithm\>
- iterator lower_bound(container.begin(), container.end(), key) // <algorithm\>
  // returns Iterator pointing to first element equal to or greater than key, or end().
  // This function returns the first element of a subsequence of elements that matches the given key.
  // If unsuccessful it returns an iterator pointing to the first element that has a greater value than the given key or end() if no such greater element exists.
- iterator upper_bound(arr, arr + n, value_tobe_searched) // <algorithm\>
- iterator upper_bound(container.begin(), container.end(), key) // <algorithm\>
  // returns the upper element.
  // Iterator pointing to the first element greater than key, or end().

- bool is_sorted(container.begin(), container.end()) // O(n)

- bool is_permutation(container1.begin(), container1.end(), container2.begin()) // <algorithm\>
- bool is_permutation(a, a + n, b) // <algorithm\>
- bool prev_permutation(container.begin(), container.end()) // O(n)
- bool next_permutation(container.begin(), container.end()) // O(n)

- count(a, a + n, val) // <algorithm\>
- count(container.begin(), container.end(), val) // <algorithm\>

// memset works for setting (`0 and -1, false, true`) ONLY.
- memset(arr, value, sizeof(arr))
- memset(dp, value, sizeof(dp))

// fill works on all cases (setting 0, -1, true, false, 9, 5, -3)
- fill(container.begin(), container.end(), val) // <algorithm\>
- fill(arr, arr + n, val) // <algorithm\>

- reverse(a, a + n) // reverse array
- reverse(container.begin(), container.end())
- rotate(first_iterator, middle_iterator, last_iterator) // <algorithm\>

- int rand() // cstdlib
- random_shuffle(v.begin(), v.end()) // cstdlib
- srand(time(NULL)) // time in ctime

Tip

Use member functions of the container if available rather than using global ones. Those are more optimized and correct.
Like use lower_bound of set on set(set.lower_bound(key)) rather than using lower_bound(set.begin(), set.end(), key) as set does not have random iterator.

Thank you

🎉 You've made it here. I believed in you.
You are awesome and a STL Pro. 🫂

Note

Vector<T>​

danger

list<T> and forward-list<T>​

deque<T>​

Stack<T>​

Queue<T>​

Priority Queue<T> or Heap​

info

set<T>​

caution

tip

map <T,U>​

Tips and Tricks:

unordered_set <T>​

unordered_map<T,U>​

STL Algorithms (More Useful Functions)​

Tip

Thank you​

Vector<T>

list<T> and forward-list<T>

deque<T>

Stack<T>

Queue<T>

Priority Queue<T> or Heap

set<T>

map <T,U>

unordered_set <T>

unordered_map<T,U>

STL Algorithms (More Useful Functions)

Thank you