Day 3 – STL Containers (Part 2), Algorithms & Basic Math

Today I continued working through the STL in C++, finishing the remaining containers and diving into some important algorithms and math concepts. These concepts form the building blocks for many coding problems, especially in competitive programming and interviews.

---

Set

• Underlying structure: Balanced BST (Red-Black Tree)

• Elements: Unique and sorted

• Time Complexity: All operations are O(log n)

#include <set>
set<int> st;
st.insert(1);
st.insert(2);

auto it = st.find(2); // Returns iterator to 2
if (st.find(10) == st.end()) { /* not found */ }

cout << st.count(2); // 0 or 1

// Bounds
st.lower_bound(2); // >= 2
st.upper_bound(2); // > 2

---

Multiset

• Like set but allows duplicate elements.

• Sorted and all standard operations apply.

#include <multiset>
multiset<int> ms;
ms.insert(2);
ms.insert(2); // Both get stored

---

Unordered Set

• Hash table underneath, hence unsorted

• Unique elements only

• Average case O(1), Worst case O(n)

#include <unordered_set>
unordered_set<int> us;
us.insert(3);
us.count(3); // 0 or 1
// lower_bound, upper_bound don't work

---

Map

• Stores key-value pairs

• Keys are unique and sorted

• Time Complexity: O(log n)

#include <map>
map<int, int> mp;
mp[1] = 100;
mp[2] = 200;

---

Multimap

• Like map but allows duplicate keys

• Sorted by keys

#include <multimap>
multimap<int, int> mmp;
mmp.insert({1, 100});
mmp.insert({1, 200});

---

Unordered Map

• Unique keys, unordered

• Average case: O(1), Worst case: O(n)

#include <unordered_map>
unordered_map<int, int> ump;
ump[3] = 300;

---

STL Algorithms

sort()

• sort(a, a+n) or sort(v.begin(), v.end())

• Time Complexity: O(n log n)

Descending Order:

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

Custom Sort – Special Pair Sorting:

• Sort by second element ascending

• If second is same, sort by first descending

bool comp(pair<int, int> a, pair<int, int> b) {
    if (a.second < b.second) return true;
    if (a.second == b.second) return a.first > b.first;
    return false;
}

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

---

Built-in Functions

• __builtin_popcount(x) – Number of set bits in int

• __builtin_popcountll(x) – For long long

All Permutations (Using next_permutation)

sort(s.begin(), s.end());
do {
    cout << s << endl;
} while (next_permutation(s.begin(), s.end()));

---

Utility Algorithms

• *max_element(a, a+n) – Returns the value of the max element

• Time complexity: O(n)

---

Math Concepts

Number of Digits

int cnt = log10(n) + 1; // O(1)
int k = to_string(n).length(); // O(log n)

Reverse a Number (with overflow check)

int rev = 0;
while (n != 0) {
    int d = n % 10;
    if (rev > INT_MAX/10 || rev < INT_MIN/10) return 0;
    rev = rev * 10 + d;
    n /= 10;
}

Palindrome Check

• Compare original number with reversed version

GCD (Euclidean Algorithm – Optimal)

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
// Time Complexity: O(log min(a, b))

Armstrong Number

• Sum of cubes of digits = number itself

• Time Complexity: O(log n)

Divisors

• Naive: O(n)

• Optimized: O(√n)

for (int i = 1; i*i <= n; i++) {
    if (n % i == 0) {
        cout << i;
        if (i != n/i) cout << n/i;
    }
}

Prime Check

• Brute force: O(n)

• Optimal: O(√n)

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i*i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

---

Summary

• Finished STL containers including sets and maps (ordered, unordered, multi versions)

• Learned sorting with custom comparators

• Explored built-in functions and core math tricks