C++ Standard Template Library (STL) Lecture Notes

Introduction to STL

• STL: Standard Template Library, a collection of algorithms and data structures.
• Purpose: To minimize code length and complexity, allowing easier access to containers and algorithms.
• Focus: Understanding C++ STL for Data Structures and Algorithms (DSA).

C++ Code Skeleton

• Start with #include <bits/stdc++.h> to include all libraries at once.
• Use using namespace std; to avoid prefixing with std:: for standard functions.

Functions in C++

• Void Functions: Do not return a value. Example: void print() { cout << "my name is Raj"; }
• Return Type Functions: Return a value. Example: int sum(int a, int b) { return a + b; }

Pairs in C++

• Definition: A pair is a utility to store two values.
• Accessing Values: Use .first and .second to get the elements in a pair.
• Example: pair<int, int> p = make_pair(1, 3); cout << p.first; // Outputs 1 cout << p.second; // Outputs 3
• Nested Pairs: Can store multiple pairs using nested pairs.

Vectors in C++

• Dynamic Container: Unlike static arrays, vectors can resize.
• Declaring a Vector: vector<int> v;
• Adding Elements: Use push_back() or emplace_back() for adding elements.
• Accessing Elements: Similar to arrays, using v[i] or v.at(i).
• Iterating through Vectors: Use iterators or range-based for loops. for(auto &val : v) { cout << val; }
• Common Functions: size(), pop_back(), clear(), swap(), empty().

Other Containers

• List: Similar to vectors but optimized for insertions and deletions.
• Deque (Double-Ended Queue): Allows insertion and deletion from both ends.
• Stack: LIFO structure with push(), pop(), and top() operations.
• Queue: FIFO structure with push(), pop(), and front() operations.
• Priority Queue: Higher priority elements are accessed first.

Sets and Multisets

• Set: Stores unique elements in sorted order.
  • Operations: insert(), find(), erase(), count().
• Multiset: Similar to set but allows duplicate elements.

Maps and Multimaps

• Map: Key-value pairs with unique keys in sorted order.
• Multimap: Allows duplicate keys but maintains sorted order.
• Accessing Elements: Use map[key] syntax.

Unordered Containers

• Unordered Set: Stores unique elements but does not guarantee order.
• Unordered Map: Similar to map but does not guarantee order.

Important STL Algorithms

• Sorting: sort(begin, end) sorts the entire range.
• Custom Comparators: Used with sort for custom sorting conditions.
• Counting Set Bits: Use __builtin_popcount() for counting set bits in an integer.
• Next Permutation: Generates the next lexicographical permutation.

Conclusion

• Understanding STL is crucial for efficient coding in C++.
• Practice implementation and usage of STL in various data structures and algorithms.

Further Learning

• Explore articles and documentation linked in the description for detailed understanding.