well-structured STL-focused C++ Cheat Sheet with:

1. Most commonly used STL containers

2. Important functions/methods

3. When and how to use them

4. How they are internally implemented (in simple terms)

🔰 C++ STL Cheat Sheet (for Coding Rounds)

📦 1. vector

A dynamic array — resizable at runtime.

#include <vector>

vector<int> v;

v.push_back(10); // Insert at end

v.pop_back(); // Remove last

v.size(); // Current size

v.clear(); // Empty vector

v[i]; // Access i-th element

v.front(); // First element

v.back(); // Last element

✅ Use when:

 You need dynamic resizing

 Random access is needed (O(1))

🛠 Implementation: Dynamic array using heap memory — doubles size when full (amortized
O(1) insertion).

📘 2. string

Dynamic character array with built-in functions.

#include <string>
string s = "hello";

s.size(); s.length(); // Length

s.substr(1, 3); // Substring from index 1 of length 3

s.find("lo"); // Find position

s.append(" world"); // Add to end

s.erase(2, 2); // Remove 2 chars from index 2

✅ Use when:

 Manipulating text data

 Need substring, search, etc.

🛠 Implementation: Like vector<char> under the hood.

📚 3. pair & tuple

#include <utility>

pair<int, int> p = {1, 2};

cout << p.first << " " << p.second;

#include <tuple>

tuple<int, char, string> t = {1, 'a', "hi"};

get<0>(t); // 1

✅ Use when:

 Returning multiple values from functions

 Storing paired or grouped data

📑 4. map (Balanced BST, ordered)

#include <map>

map<string, int> mp;

mp["apple"] = 3;

mp.count("apple"); // 1 if present
mp.erase("apple");

for (auto &[k, v] : mp) {} // Structured loop

✅ Use when:

 You want sorted keys

 Fast search (O(log n))

🛠 Implementation: Red-Black Tree

📂 5. unordered_map (Hash Table)

#include <unordered_map>

unordered_map<string, int> ump;

ump["dog"] = 1;

ump["cat"] = 2;

ump.find("dog"); // Iterator or ump.end()

✅ Use when:

 You want fast lookup (average O(1))

 Key order doesn't matter

🛠 Implementation: Hash Table using open addressing

📋 6. set (Stores unique elements, ordered)

#include <set>

set<int> s;

s.insert(5);

s.erase(5);

s.count(5);

s.lower_bound(3); // >= 3

s.upper_bound(3); // > 3

✅ Use when:

 Need sorted, unique values

🛠 Implementation: Balanced BST (Red-Black Tree)

📂 7. unordered_set (Hash Set)

#include <unordered_set>

unordered_set<int> us;

us.insert(10);

us.erase(10);

✅ Use when:

 You need unique elements

 Order doesn’t matter

 Lookup needs to be O(1) on average

🛠 Implementation: Hash table (bucket chaining)

🧺 8. stack (LIFO)

#include <stack>

stack<int> st;

st.push(1); st.push(2);

st.top(); // 2

st.pop(); // remove 2

✅ Use when:

 Reversing

 Backtracking

 Matching parentheses

🛠 Implementation: Built using deque internally.

📥 9. queue (FIFO)

#include <queue>
queue<int> q;

q.push(1); q.push(2);

q.front(); q.pop();

✅ Use when:

 BFS

 Processing tasks in order

🛠 Implementation: Built using deque.

📊 10. priority_queue (Heap)

#include <queue>

priority_queue<int> pq; // Max heap by default

pq.push(4); pq.push(1);

pq.top(); // 4 (largest)

priority_queue<int, vector<int>, greater<int>> minpq; // Min-heap

✅ Use when:

 You need efficient min/max

 Use for Dijkstra’s, Huffman coding

🛠 Implementation: Binary Heap

🧮 11. algorithm functions

#include <algorithm>

sort(v.begin(), v.end());

reverse(s.begin(), s.end());

count(v.begin(), v.end(), 5);

find(v.begin(), v.end(), x);

binary_search(v.begin(), v.end(), x); // true/false

lower_bound(v.begin(), v.end(), x); // ≥ x

✅ Use when:

 You want quick sorting, searching

 Useful in greedy, two pointers, etc.

📌 Quick Tips:

Goal STL to Use

Frequency Count unordered_map or map

Sorted Unique Values set

Stack-based Problems stack

Queue / BFS queue

Graph / Dijkstra priority_queue + vector<pair<>>

Efficient Search/Bounds sort + lower_bound/upper_bound

Hashing unordered_map / unordered_set

greater<int> is a function object (also called a functor) provided by the C++ Standard
Library. It defines a comparison that returns true if the first argument is greater than the
second.

It is typically used to reverse the default order of sorting or priority structures.

📌 Default Comparison in STL

By default:

 sort() uses ascending order (<)

 priority_queue uses max-heap, meaning largest element is on top

✅ greater<int> in priority_queue — Example

🔻 Default priority_queue (max-heap)

#include <queue>

priority_queue<int> pq; // By default, behaves like max-heap

pq.push(10);

pq.push(5);

pq.push(20);

cout << pq.top(); // Outputs: 20

🔼 Min-Heap using greater<int>

#include <queue>

#include <vector>

#include <functional> // for greater

pq.push(10);

pq.push(5);

pq.push(20);

cout << pq.top(); // Outputs: 5 (smallest element)

✅ greater<int> changes the default comparison to min-heap behavior.

✅ greater<int> in sort() — Descending Order

#include <algorithm>

#include <vector>

#include <functional> // for greater

vector<int> v = {10, 5, 20};

sort(v.begin(), v.end(), greater<int>());

// v is now: {20, 10, 5}

🧠 Summary:

Usage Purpose

Makes sorting or heap ordering descending

less<int> Makes sorting or heap ordering ascending

Let me know if you want a visual diagram or practice problems using greater<int>!
In C++, function objects (also called functors) are predefined classes in the <functional>
header that behave like functions. They are often used in STL algorithms and containers to
define custom comparison logic or operations.

🔧 List of Predefined Function Objects in C++

📦 Header File:

#include <functional>

🔹 1. Comparison Functors

These return a bool based on comparisons:

Functor Description Example

less<T> Returns true if a < b Default for sort & map

greater<T> Returns true if a > b Use for descending sort

less_equal<T> Returns true if a <= b Rare in STL

greater_equal<T> Returns true if a >= b Rare

equal_to<T> Returns true if a == b Used in filtering

not_equal_to<T> Returns true if a != b Used in filtering

✅ These are often used with sort(), priority_queue, or set/map.

🔹 2. Arithmetic Functors

Used for performing arithmetic operations in a functional style.

plus<T> a+b Addition

minus<T> a-b Subtraction

multiplies<T> a * b Multiplication

divides<T> a/b Division

modulus<T> a % b Modulo

negate<T> -a Unary minus

🧪 Example:

plus<int> add;

cout << add(4, 5); // 9

negate<int> neg;

cout << neg(3); // -3

These are handy in functional programming, transform(), and accumulate().

🔹 3. Logical Functors

Used for logical operations (bool inputs):

Functor Description Equivalent To

logical_and<T> a && b Logical AND

logical_or<T> `a

logical_not<T> !a Logical NOT

🧪 Example:

logical_and<bool> land;

cout << land(true, false); // false

logical_not<bool> lnot;

cout << lnot(true); // false

 Sorting in descending order:

 sort(v.begin(), v.end(), greater<int>());

 Using accumulate() with functor:

 #include <numeric>

 accumulate(v.begin(), v.end(), 0, plus<int>());

 Custom priority queues:

 priority_queue<int, vector<int>, greater<int>> pq; // Min-heap

🧾 Summary Table

Category Functor Symbol Equivalent

Comparison less<T> <

greater<T> >

equal_to<T> ==

not_equal_to<T> !=

less_equal<T> <=

greater_equal<T> >=

Arithmetic plus<T> +

minus<T> -

multiplies<T> *

divides<T> /

modulus<T> %

negate<T> Unary -

Logical logical_and<T> &&

logical_or<T> `

logical_not<T> !