C++ STL Lecture Notes

Introduction to STL

• STL: Standard Template Library
• Simplifies code by providing pre-defined containers and algorithms
• Compiles commonly used algorithms, containers, iterators, and functions

Skeleton of a C++ Code

• #include<bits/stdc++.h>: Includes all standard libraries, avoiding individual includes
• using namespace std;: To avoid using std:: prefix repeatedly

Functions in C++

• Void function: Does not return a value
  • Example: void print() { cout << "Raj"; }
• Return type function: Returns a value of the specified type
  • Example: int sum(int a, int b) { return a + b; }

STL Components

Containers

• Algorithms, Containers, Functions, Iterators
• Containers: Vector, Queue, Set, Map, etc.

Pairs in Utility Library

• Store pairs of values, can access elements with first and second
• Nest pairs for more than two values
• Arrays of pairs are possible

Vectors

• Dynamic array: Can grow and shrink
• Declaration: vector<int> v;
• Insertion: v.push_back(1); or v.emplace_back(2);
• Advanced Initialization: vector<int> v(5, 100);
• Copying Vectors: vector<int> v2 = v1;
• Access and Iterators:
  • Access elements like arrays: v[0] or v.at(0)
  • Use iterators to traverse: vector<int>::iterator it = v.begin();
  • auto keyword for simplified iterator declarations

List

• Doubly-linked list, supports front operations
• Similar functions to vector but efficient front operations

Deque

• Double-ended queue, supports both front and back operations
• Functions similar to list and vector

Stack

• LIFO (Last In First Out)
• Functions: push(element), pop(), top(), size(), empty(), swap()

Queue

• FIFO (First In First Out)
• Functions: push(element), pop(), front(), back(), size(), empty(), swap()

Priority Queue

• Max-heap: Largest element at top by default
• Min-heap: Using comparator (greater<int>)
• Functions like queue but with priority

Set

• Stores unique elements in a sorted order
• Insertion & Access:
  • s.insert(1);
  • Use iterators and functions like find, count
• Erasure:
  • Single element or ranges
• Multiset: Allows duplicate elements, sorted order
• Unordered Set: Hash-based, unique elements, average case O(1) operations

Map

• Key-value pairs, unique keys, sorted order of keys
• Insertion: m[key] = value;, m.emplace(key, value);
• Access: m.find(key), m.erase(key), lower_bound, upper_bound
• Multimap: Allows duplicate keys, sorted order
• Unordered Map: Similar to map but not sorted, average case O(1) operations

Important Algorithms

• Sorting:
  • sort(start_iterator, end_iterator)
  • Custom comparator with bool comparator(const dataType& a, const dataType& b)
• Built-in Popcount: __builtin_popcount(x) counts set bits
• Next Permutation: next_permutation(start, end)
• Max/Min Element: max_element(start, end) and min_element(start, end)

Conclusion

• Comment for motivation, subscribe, and watch related content on the channel

Sponsor Reminder

• Coding Ninjas: Structure and resources from experienced professionals
• Benefits: Well-structured courses, short doubt resolution time, available courses with discounts via provided link