C++ STL Lecture

Jul 21, 2024

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