C++ Standard Template Library (STL) Overview

Introduction to STL

• STL stands for Standard Template Library.
• It provides a collection of algorithms, containers, iterators, and functions.
• Helps avoid lengthy lines of code by providing pre-defined functions and containers.
• Essential for Data Structures and Algorithms (DSA).

C++ Code Skeleton

• Use #include <bits/stdc++.h> to include all standard libraries.
• using namespace std; allows omitting std:: before standard functions.

Functions in C++

• Void Function: Does not return a value (e.g., void print()).
• Return Type Function: Returns a value (e.g., int sum(int a, int b)).

Pairs

• Pairs are defined in the utility library, storing two elements.
• Access elements using p.first and p.second.
• Nested pairs can be used for more than two values.

Containers Overview

STL is divided into four parts:

1. Algorithms
2. Containers
3. Functions
4. Iterators

Key Containers

1. Vector

   • Dynamic array that can resize as needed.
   • Use push_back() to add elements and pop_back() to remove.
   • Access elements like an array, e.g., v[i] or v.at(i).
   • Iterate using iterators: v.begin(), v.end().

2. List

   • Doubly linked list, allows fast insertions/removals from both ends.
   • Functions like push_back(), push_front(), pop_back(), etc.

3. Deque (Double-ended Queue)

   • Allows insertion and deletion from both ends.
   • Functions similar to list and vector.

4. Stack

   • Last In First Out (LIFO) structure.
   • Key functions: push(), pop(), top(), size(), empty().

5. Queue

   • First In First Out (FIFO) structure.
   • Key functions: push(), pop(), front(), back(), size(), empty().

6. Priority Queue

   • Stores elements in a way that the highest priority (max or min) is always at the front.
   • Use push(), pop(), and top() to interact with elements.

7. Set

   • Stores unique elements in a sorted order.
   • Key functions: insert(), erase(), find(), count(), size(), empty().

8. Map

   • Stores key-value pairs with unique keys in sorted order.
   • Key functions: insert(), accessing values by keys, find(), etc.

9. Multiset & Multimap

   • Multiset allows multiple occurrences of elements.
   • Multimap allows multiple values for a single key.

10. Unordered Set & Unordered Map

    • Similar to set/map but does not maintain order.
    • Provides average constant time complexity for operations.

Important STL Algorithms

• Sorting: Use sort() to sort elements in a range easily.
• Binary Count: __builtin_popcount() to count set bits in an integer.
• Next Permutation: Generate all permutations of a sequence.
• Max Element: max_element() to find maximum in a range.

Conclusion

• Understanding STL is crucial for coding efficiently in C++.
• Numerous libraries and algorithms available to simplify coding tasks.
• Practice using STL for better grasping of data structures and algorithms.