STL — Standard Template Library

#include <vector>
#include <algorithm>
using namespace std;
int main(){ vector<int> v={3,1,2}; sort(v.begin(), v.end()); }

vector<int> v; v.push_back(1);

Internal Mechanics

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3}; // Initial vector

    v.push_back(10);           // Add to end: {1, 2, 3, 10}
    cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << "\n";

    v.insert(v.begin() + 1, 99); // Insert at index 1: {1, 99, 2, 3, 10}
    v.erase(v.begin() + 3);      // Erase at index 3: {1, 99, 2, 10}

    cout << "Elements: ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << "\n";
    
    return 0;
}

Iterating

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};

    // Method 1: index
    cout << "Index: ";
    for (int i = 0; i < v.size(); i++) cout << v[i] << " ";

    // Method 2: range-based for (modern C++)
    cout << "\nRange: ";
    for (auto x : v) cout << x << " ";

    // Method 3: iterator
    cout << "\nIterator: ";
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    
    return 0;
}

vector<int> v; v.push_back(10); v.push_back(20); cout << v.size() << " " << v[0];

list — Doubly Linked List

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4};
    
    lst.push_back(5);    // {1, 2, 3, 4, 5}
    lst.push_front(0);   // {0, 1, 2, 3, 4, 5}
    lst.pop_back();      // {0, 1, 2, 3, 4}
    
    // Insert at iterator position
    auto it = lst.begin();
    advance(it, 2);      // move 2 positions to '2'
    lst.insert(it, 99);  // {0, 1, 99, 2, 3, 4}
    
    lst.reverse();       // {4, 3, 2, 99, 1, 0}
    lst.sort();          // {0, 1, 2, 3, 4, 99}
    
    cout << "List elements: ";
    for (int x : lst) {
        cout << x << " ";
    }
    cout << "\n";
    
    return 0;
}

*O(1) insert in list only if you already have the iterator position

deque — Double-Ended Queue

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> dq = {1, 2, 3};
    
    dq.push_back(4);   // add to end: {1, 2, 3, 4}
    dq.push_front(0);  // add to front: {0, 1, 2, 3, 4}
    dq.pop_back();     // remove from end: {0, 1, 2, 3}
    dq.pop_front();    // remove from front: {1, 2, 3}
    
    cout << "Deque element at index 1: " << dq[1] << "\n"; // random access
    cout << "Deque elements: ";
    if(int x : dq) cout << x << " ";
    cout << "\n";
    
    return 0;
}

list<int> l; l.push_front(5); l.push_back(10);
deque<int> d; d.push_front(1);

set — Sorted Unique Elements

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {3, 1, 4, 1, 5};  // stored: {1, 3, 4, 5} — sorted, unique
    
    s.insert(2);                   // adds 2: {1, 2, 3, 4, 5}
    s.insert(3);                   // ignored (duplicate)
    s.erase(4);                    // removes 4: {1, 2, 3, 5}
    
    cout << "Set size: " << s.size() << "\n";
    cout << "Contains 3? " << (s.count(3) ? "Yes" : "No") << "\n";
    
    cout << "Set elements: ";
    for (int x : s) cout << x << " ";
    cout << "\n\n";

    // multiset — allows duplicates
    multiset<int> ms = {1, 1, 2, 3};  // {1, 1, 2, 3}
    cout << "Count of 1 in multiset: " << ms.count(1) << "\n";
    
    return 0;
}

map — Key-Value Pairs

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> scores;
    scores["Alice"] = 95;   // insert
    scores["Bob"]   = 87;
    scores["Alice"] = 99;   // update (key already exists)

    cout << "Map elements:\n";
    // Iterate using C++17 structured bindings
    for (auto& [key, val] : scores) {
        cout << key << ": " << val << "\n";
    }

    scores.erase("Bob");    // remove Bob
    cout << "\nAfter removing Bob, map size: " << scores.size() << "\n";

    // multimap — allows duplicate keys
    multimap<string, int> mm;
    mm.insert({"Alice", 90});
    mm.insert({"Alice", 85});
    
    cout << "Multimap Alice count: " << mm.count("Alice") << "\n";
    
    return 0;
}

set<int> s = {3,1,2,1}; // 1,2,3
map<int, string> m; m[101] = "Arun";

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> st;
    st.push(1); 
    st.push(2); 
    st.push(3);

    cout << "Stack top: " << st.top() << "\n"; // 3 (peek without removing)
    
    st.pop(); // removes 3
    cout << "New top after pop: " << st.top() << "\n";
    cout << "Is empty? " << (st.empty() ? "Yes" : "No") << "\n";
    cout << "Size: " << st.size() << "\n";
    
    // Note: stack has NO iterator — only top access!
    return 0;
}

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(1); 
    q.push(2); 
    q.push(3);

    cout << "Queue front: " << q.front() << "\n"; // 1 (first element)
    cout << "Queue back: " << q.back() << "\n";   // 3 (last element)
    
    q.pop(); // removes front (1)
    cout << "New front after pop: " << q.front() << "\n";
    
    return 0;
}

priority_queue

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // Max-heap by default
    priority_queue<int> pq;       
    pq.push(3); pq.push(1); pq.push(5); pq.push(2);
    
    cout << "Max-heap top: " << pq.top() << "\n"; // 5
    pq.pop(); // removes 5
    cout << "New top: " << pq.top() << "\n";      // 3
    
    // Min-heap (smallest at top)
    priority_queue<int, vector<int>, greater<int>> minPQ;
    minPQ.push(3); minPQ.push(1); minPQ.push(5);
    
    cout << "Min-heap top: " << minPQ.top() << "\n"; // 1
    
    return 0;
}

stack<int> st; st.push(1); st.pop();
queue<int> q; q.push(1); q.pop();

Common Iterator Operations

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    vector<int>::iterator it = v.begin();  // points to first
    auto it2 = v.end();                    // points PAST last

    cout << "First element: " << *it << "\n"; // dereference — get value (1)
    
    it++;            // move forward
    cout << "Second element: " << *it << "\n";
    
    it += 2;         // jump 2 ahead (random access only)
    cout << "Jumped element: " << *it << "\n"; // 4
    
    cout << "Distance to end: " << (it2 - it) << "\n";

    // Reverse iterators
    cout << "Reverse print: ";
    for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
        cout << *rit << " ";  // 5 4 3 2 1
    }
    cout << "\n";
    
    return 0;
}

begin() vs end()

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};
    
    // begin() vs end()
    auto b = v.begin();    // iterator to first element (10)
    auto e = v.end();      // iterator PAST last element (sentinel)
    
    // rbegin() vs rend()
    auto rb = v.rbegin();  // reverse: points to last element (30)
    auto re = v.rend();    // reverse: points before first element
    
    // cbegin()
    auto cb = v.cbegin();  // const iterator (read-only)
    // *cb = 15; // COMPILER ERROR: read-only
    
    cout << "begin: " << *b << "\n";
    cout << "rbegin: " << *rb << "\n";
    
    return 0;
}

vector<int> v = {1,2,3};
for(vector<int>::iterator it = v.begin(); it != v.end(); ++it) cout << *it;

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 3};
    
    // Sorting
    sort(v.begin(), v.end()); // {1, 2, 3, 3, 5, 8, 9}
    
    // Searching
    if (binary_search(v.begin(), v.end(), 8)) {
        cout << "8 is found in the vector.\n";
    }
    
    // Counting
    cout << "Number of 3s: " << count(v.begin(), v.end(), 3) << "\n";
    
    // Min/Max
    cout << "Smallest: " << *min_element(v.begin(), v.end()) << "\n";
    cout << "Largest: " << *max_element(v.begin(), v.end()) << "\n";
    
    // Remove duplicates
    auto last = unique(v.begin(), v.end()); // shifts duplicates to end
    v.erase(last, v.end());                 // erases them physically
    
    cout << "Unique sorted elements: ";
    for (int x : v) cout << x << " ";
    cout << "\n";
    
    return 0;
}

Functors (Function Objects)

A functor is an object that behaves like a function — it overloads operator():

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Multiply {
    int factor;
public:
    Multiply(int f) : factor(f) {}
    // Overload operator() to make it a functor
    int operator()(int x) { return x * factor; }
};

int main() {
    Multiply triple(3);
    cout << "3 * 5 = " << triple(5) << "\n";  // Called like a function!
    
    // Use functor with transform algorithm
    vector<int> v = {1, 2, 3};
    transform(v.begin(), v.end(), v.begin(), Multiply(2));
    
    cout << "Transformed vector (x2): ";
    if(int x : v) cout << x << " ";
    cout << "\n";
    
    return 0;
}

Lambda Functions (Modern Alternative)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9};

    // Sort descending with custom comparator using lambda
    sort(v.begin(), v.end(), [](int a, int b){ return a > b; });

    cout << "Sorted descending: ";
    if(int x : v) cout << x << " ";
    cout << "\n";

    // count_if with lambda
    int evens = count_if(v.begin(), v.end(), [](int x){ return x % 2 == 0; });
    cout << "Number of evens: " << evens << "\n";
    
    return 0;
}

int a[]={3,1,2};
sort(a, a+3);
if(binary_search(a, a+3, 2)) cout<<"Found";

2-Mark Questions

5-Mark Questions

Big-O Cheat Sheet

Revision Sheet

1. Vector Reallocation Invalidates ALL Iterators

vector<int> v = {1,2,3};
auto it = v.begin();
v.push_back(4); // may reallocate!
cout << *it;    // UNDEFINED — it may point to freed memory

// Safe: reserve capacity first
v.reserve(10);  // guarantees no reallocation for 10 elements
auto it2 = v.begin();
v.push_back(5); // safe — no reallocation
cout << *it2;   // OK

2. map[] vs map.at() vs map.find()

map<string,int> m = {{"a",1},{"b",2}};

m["c"];          // INSERTS "c"=0. Modifies map! Use carefully.
m.at("c");       // throws std::out_of_range. Safe read.
m.find("c");    // returns iterator. end() if not found. SAFEST.
m.count("c");   // returns 0 or 1. Good for existence check.

// Best practice for safe access:
if(m.count("c")) cout << m["c"]; // check then access

3. Modifying set Elements (Forbidden!)

set<int> s = {1,2,3};
auto it = s.find(2);
*it = 5;  // COMPILE ERROR — set elements are const!

// Correct way to "modify": erase + insert
s.erase(it);
s.insert(5);  // s = {1,3,5} now

4. Custom Comparator for priority_queue

// Sort pairs by second element (priority = value, not index)
auto cmp = [](pair<int,int> a, pair<int,int> b){
    return a.second < b.second; // max by second
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);
pq.push({1,30}); pq.push({2,10}); pq.push({3,20});
cout << pq.top().first; // 1 (highest value=30)

🔗 Algorithm Chaining — Powerful Combos

// ── Pattern 1: sort + unique + erase (remove duplicates from sorted)
vector<int> v = {5,1,3,1,5,2};
sort(v.begin(), v.end());       // {1,1,2,3,5,5}
v.erase(unique(v.begin(),v.end()), v.end()); // {1,2,3,5}

// ── Pattern 2: transform + lambda (square all elements)
transform(v.begin(),v.end(), v.begin(), [](int x){ return x*x; });

// ── Pattern 3: find + erase (remove first occurrence)
auto pos = find(v.begin(), v.end(), 9);
if(pos != v.end()) v.erase(pos);

// ── Pattern 4: sort with custom comparator (sort by length)
vector<string> words = {"banana","apple","kiwi"};
sort(words.begin(),words.end(),[](string a,string b){
    return a.length() < b.length(); // sort by length ascending
});
// kiwi apple banana

// ── Pattern 5: accumulate with custom operation
vector<int> nums = {1,2,3,4,5};
int product = accumulate(nums.begin(),nums.end(),1,
    [](int acc, int x){ return acc*x; }); // 120 = 5!

Attempt each problem independently before revealing. These cover ALL exam-likely STL scenarios.

🔹 Vector Problems

#include <algorithm>
vector<int> v={1,2,3,4,5};
int k=2;
rotate(v.begin(), v.begin()+k, v.end());
if(int x:v) cout<<x<<" ";  // 3 4 5 1 2

vector<int> v={3,1,4,1,5,9,2,6,5,3};
unordered_set<int> seen;
vector<int> res;
if(int x:v) if(seen.insert(x).second) res.push_back(x);
if(int x:res) cout<<x<<" ";  // 3 1 4 5 9 2 6

vector<pair<string,int>> v={{"Alice",90},{"Bob",85},{"Carol",90},{"Dave",85}};
sort(v.begin(),v.end(),[](auto& a,auto& b){
    if(a.second != b.second) return a.second > b.second; // score desc
    return a.first < b.first;   // name asc
});
if(auto& p:v) cout<<p.first<<":"<<p.second<<" ";
// Alice:90 Carol:90 Bob:85 Dave:85

🔹 map / set Problems

string sentence = "the cat sat on the mat the cat";
istringstream iss(sentence);
map<string,int> freq;
string word;
for(iss>>word) freq[word]++;
if(auto&[w,c]:freq) if(c>=2) cout<<w<<":"<<c<<"\n";
// cat:2  the:3

vector<int> v={1,3,5,3,7,1};
set<int> seen, dups;
if(int x:v){
    if(!seen.insert(x).second) dups.insert(x); // insert returns {iter,false} if exists
}
if(int x:dups) cout<<x<<" ";  // 1 3

vector<string> words={"eat","tea","tan","ate","nat","bat"};
map<string,vector<string>> groups;
if(string w:words){
    string key=w; sort(key.begin(),key.end());
    groups[key].push_back(w);
}
if(auto&[key,grp]:groups){
    if(string s:grp) cout<<s<<" ";
    cout<<"\n";
}
// eat tea ate | tan nat | bat

🔹 priority_queue Problems

vector<int> v={3,1,9,2,7,5,8,4,6};
priority_queue<int> pq(v.begin(),v.end());
int k=3;
while(k--){
    cout<<pq.top()<<" ";
    pq.pop();
}
// 9 8 7

vector<int> v={3,1,9,2,7,5,8,4,6};
priority_queue<int,vector<int>,greater<int>> minPQ(v.begin(),v.end());
int k=3;
while(k--){
    cout<<minPQ.top()<<" ";
    minPQ.pop();
}
// 1 2 3

vector<pair<int,int>> meetings={{0,30},{5,10},{15,20}};
sort(meetings.begin(),meetings.end());  // sort by start
priority_queue<int,vector<int>,greater<int>> endTimes; // min-heap of end times
int rooms=0;
if(auto& m:meetings){
    if(!endTimes.empty() && endTimes.top()<=m.first)
        endTimes.pop(); // reuse room
    else rooms++;
    endTimes.push(m.second);
}
cout<<"Rooms needed: "<<rooms; // 2

🔹 deque / Sliding Window Problems

vector<int> v={1,3,-1,-3,5,3,6,7}; int k=3;
deque<int> dq; // stores indices
vector<int> result;
for(int i=0;i<(int)v.size();i++){
    // Remove elements outside window
    if(!dq.empty() && dq.front()<=i-k) dq.pop_front();
    // Remove smaller elements from back
    if(!dq.empty() && v[dq.back()]<=v[i]) dq.pop_back();
    dq.push_back(i);
    if(i>=k-1) result.push_back(v[dq.front()]);
}
if(int x:result) cout<<x<<" ";  // 3 3 5 5 6 7

🔹 Mixed Container Problems

vector<int> v={1,1,1,2,2,3};
map<int,int> freq;
if(int x:v) freq[x]++;
// Convert to vector of pairs and sort by frequency desc
vector<pair<int,int>> fv(freq.begin(),freq.end());
sort(fv.begin(),fv.end(),[](auto&a,auto&b){return a.second>b.second;});
int k=2;
for(int i=0;i<k;i++) cout<<fv[i].first<<" ";
// 1 2

vector<vector<int>> arrs={{1,2,3,4},{2,3,4,5},{3,4,5,6}};
map<int,set<int>> presence; // element -> which arrays contain it
for(int i=0;i<(int)arrs.size();i++)
    if(int x:arrs[i]) presence[x].insert(i);
cout<<"Common: ";
if(auto&[x,s]:presence)
    if((int)s.size()==(int)arrs.size()) cout<<x<<" ";
// Common: 3 4

Attempt each from scratch. Full marks: correct container choice, proper iteration, algorithm usage, edge case handling.

#include <iostream>
#include <map>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

map<string,vector<int>> db;

void addMarks(string name, vector<int> marks){
    db[name]=marks;
}
double getAverage(string name){
    auto&v=db[name];
    return (double)accumulate(v.begin(),v.end(),0)/v.size();
}
string getTopStudent(){
    string top; double best=-1;
    if(auto&[name,marks]:db){
        double avg=getAverage(name);
        if(avg>best){best=avg;top=name;}
    }
    return top;
}
void getAllAbove(int threshold){
    if(auto&[name,marks]:db)
        if(getAverage(name)>=threshold)
            cout<<name<<":"<<getAverage(name)<<"\n";
}
int main(){
    addMarks("Alice",{90,85,92});
    addMarks("Bob",{70,75,68});
    addMarks("Carol",{95,98,91});
    cout<<"Top: "<<getTopStudent()<<"\n";  // Carol
    getAllAbove(80);                          // Alice, Carol
}

map<string,int> inventory;

void addItem(string item, int qty){inventory[item]+=qty;}

void removeItem(string item, int qty){
    if(!inventory.count(item)) throw runtime_error("Item not found: "+item);
    if(inventory[item]<qty) throw runtime_error("Insufficient stock");
    inventory[item]-=qty;
    if(inventory[item]==0) inventory.erase(item);
}

vector<string> getLowStock(int thresh){
    vector<string> low;
    if(auto&[item,qty]:inventory) if(qty<=thresh) low.push_back(item);
    sort(low.begin(),low.end());
    return low;
}

void topStocked(int k){
    priority_queue<pair<int,string>> pq;
    if(auto&[item,qty]:inventory) pq.push({qty,item});
    for(k--&&!pq.empty()){
        cout<<pq.top().second<<":"<<pq.top().first<<"\n";
        pq.pop();
    }
}
int main(){
    addItem("Apple",100); addItem("Banana",30); addItem("Cherry",5);
    cout<<"Top stocked:\n"; topStocked(2);
    cout<<"Low stock:\n";
    if(auto s:getLowStock(50)) cout<<s<<"\n";
}

string para="the quick brown fox jumps over the lazy dog the fox";
istringstream iss(para);
string w;
map<string,int> freq;
set<string> unique;
for(iss>>w){ freq[w]++; unique.insert(w); }

cout<<"Unique words (sorted):\n";
if(auto&s:unique) cout<<s<<" ";

cout<<"\nTop 3 frequent:\n";
priority_queue<pair<int,string>> pq;
if(auto&[word,cnt]:freq) pq.push({cnt,word});
int k=3;
for(k--&&!pq.empty()){
    cout<<pq.top().second<<":"<<pq.top().first<<"\n";
    pq.pop();
}
cout<<"Hapax legomena (appear once):\n";
if(auto&[word,cnt]:freq) if(cnt==1) cout<<word<<" ";

map<int,vector<int>> graph={
    {1,{2,3}},{2,{4,5}},{3,{6}},{4,{}},{5,{}},{6,{}}
};

void bfs(int start){
    queue<int> q;
    set<int> visited;
    q.push(start); visited.insert(start);
    if(!q.empty()){
        int node=q.front(); q.pop();
        cout<<node<<" ";
        if(int nb:graph[node]){
            if(!visited.count(nb)){
                visited.insert(nb);
                q.push(nb);
            }
        }
    }
}
int main(){ bfs(1); }
// Output: 1 2 3 4 5 6

struct Player{string name; int score,level;};
vector<Player> players={
    {"Alice",1000,5},{"Bob",1000,7},{"Carol",900,3},
    {"Dave",1100,5},{"Eve",1100,5}
};
sort(players.begin(),players.end(),[](Player&a,Player&b){
    if(a.score!=b.score) return a.score>b.score;
    if(a.level!=b.level) return a.level>b.level;
    return a.name<b.name;
});
cout<<"Leaderboard:\n";
int rank=1;
if(auto&p:players)
    cout<<rank++<<". "<<p.name<<" S:"<<p.score<<" L:"<<p.level<<"\n";

map<string,vector<string>> contacts;

void addContact(string name, string phone){
    contacts[name].push_back(phone);
}
void removeContact(string name){
    if(!contacts.count(name)) throw runtime_error("Not found");
    contacts.erase(name);
}
vector<string> searchByName(string name){
    if(!contacts.count(name)) return {};
    return contacts[name];
}
string searchByPhone(string phone){
    if(auto&[name,phones]:contacts)
        if(auto&p:phones) if(p==phone) return name;
    return "Not found";
}
void showAll(){
    if(auto&[name,phones]:contacts){
        cout<<name<<": ";
        if(auto&p:phones) cout<<p<<" ";
        cout<<"\n";
    }
}
void findDuplicatePhones(){
    map<string,vector<string>> phoneOwners;
    if(auto&[name,phones]:contacts)
        if(auto&p:phones) phoneOwners[p].push_back(name);
    cout<<"Duplicate phones:\n";
    if(auto&[ph,owners]:phoneOwners)
        if(owners.size()>1){
            cout<<ph<<" owned by: ";
            if(auto&o:owners) cout<<o<<" ";
            cout<<"\n";
        }
}
int main(){
    addContact("Alice","9876543210");
    addContact("Bob","9123456789");
    addContact("Alice","9000000001");
    addContact("Carol","9876543210"); // duplicate phone
    showAll();
    cout<<searchByPhone("9876543210")<<"\n"; // Alice
    findDuplicatePhones();
}

All programs include every STL header needed, full main(), and exact output. Master these patterns and you can solve any STL exam problem.

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;

int main() {
    string text = "the quick brown fox jumps over the lazy dog "
                  "the fox was quick and the dog was lazy";

    // Step 1: Count word frequencies using map
    istringstream iss(text);
    map<string, int> freq;
    string word;
    for(iss >> word) freq[word]++;

    // Step 2: Convert to vector for custom sorting
    vector<pair<string,int>> words(freq.begin(), freq.end());

    // Step 3: Sort by frequency (desc), then alphabetically (asc)
    sort(words.begin(), words.end(), [](const pair<string,int>&a,
                                        const pair<string,int>&b){
        if(a.second != b.second) return a.second > b.second;
        return a.first < b.first;
    });

    // Step 4: Print report
    cout << "=== Word Frequency Report ===\n";
    cout << "Total unique words: " << words.size() << "\n\n";
    cout << "Word            Count\n";
    cout << "-----           -----\n";
    if(auto& [w, c] : words)
        cout << w << if(16-w.size(),' ') << c << "\n";

    // Step 5: Find words that appear exactly once
    cout << "\nHapax (appear once): ";
    if(auto& [w, c] : words)
        if(c == 1) cout << w << " ";
    cout << "\n";
    return 0;
}

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

// Find top K largest using max-heap
vector<int> topKLargest(vector<int>& nums, int k) {
    priority_queue<int> maxHeap(nums.begin(), nums.end());
    vector<int> result;
    for(k-- > 0 && !maxHeap.empty()) {
        result.push_back(maxHeap.top());
        maxHeap.pop();
    }
    return result;
}

// Find top K smallest using min-heap
vector<int> topKSmallest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap(nums.begin(), nums.end());
    vector<int> result;
    for(k-- > 0 && !minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    return result;
}

// Kth largest element
int kthLargest(vector<int>& nums, int k) {
    priority_queue<int> pq(nums.begin(), nums.end());
    if(--k > 0) pq.pop();
    return pq.top();
}

int main() {
    vector<int> data = {7, 10, 4, 3, 20, 15, 8, 1, 6, 12};
    cout << "Data: ";
    if(int x:data) cout << x << " ";
    cout << "\n\n";

    cout << "Top 3 Largest  : ";
    if(int x : topKLargest(data, 3)) cout << x << " ";
    cout << "\n";

    cout << "Top 3 Smallest : ";
    if(int x : topKSmallest(data, 3)) cout << x << " ";
    cout << "\n";

    cout << "3rd Largest    : " << kthLargest(data, 3) << "\n";

    // Priority queue with pairs — process by priority
    cout << "\n=== Task Priority Queue ===\n";
    priority_queue<pair<int,string>> tasks;
    tasks.push({3, "Low priority task"});
    tasks.push({9, "CRITICAL task"});
    tasks.push({6, "Medium task"});
    tasks.push({9, "Another CRITICAL"});
    if(!tasks.empty()) {
        cout << "[P=" << tasks.top().first << "] "
             << tasks.top().second << "\n";
        tasks.pop();
    }
    return 0;
}

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

class Library {
    map<string, set<string>> booksByAuthor;  // author → set of titles
    map<string, int>         bookCount;       // author → count
    set<string>              allTitles;       // for duplicate detection

public:
    bool addBook(string author, string title) {
        if(allTitles.count(title)) {           // duplicate check O(log n)
            cout << "DUPLICATE: " << title << "\n";
            return false;
        }
        booksByAuthor[author].insert(title);   // auto-creates if new
        bookCount[author]++;
        allTitles.insert(title);
        return true;
    }

    void removeBook(string title) {
        if(!allTitles.count(title)) { cout << "Not found: " << title << "\n"; return; }
        allTitles.erase(title);
        if(auto& [author, titles] : booksByAuthor)
            if(titles.count(title)) {
                titles.erase(title);
                bookCount[author]--;
                break;
            }
    }

    void displayByAuthor() {
        cout << "\n=== Books by Author ===\n";
        if(auto& [author, titles] : booksByAuthor) {
            cout << author << " (" << bookCount[author] << " books):\n";
            if(auto& title : titles)
                cout << "  - " << title << "\n";
        }
    }

    void topAuthors(int k) {
        // Convert map to vector, sort by count
        vector<pair<string,int>> v(bookCount.begin(), bookCount.end());
        sort(v.begin(), v.end(), [](auto&a, auto&b){ return a.second>b.second; });
        cout << "\n=== Top " << k << " Authors ===\n";
        for(int i=0; i<k && i<(int)v.size(); i++)
            cout << i+1 << ". " << v[i].first << " — " << v[i].second << " books\n";
    }

    int totalBooks() { return allTitles.size(); }
};

int main() {
    Library lib;
    lib.addBook("Knuth",    "Art of Computer Programming");
    lib.addBook("Knuth",    "Concrete Mathematics");
    lib.addBook("Stroustrup","The C++ Programming Language");
    lib.addBook("Stroustrup","Programming: Principles and Practice");
    lib.addBook("Stroustrup","A Tour of C++");
    lib.addBook("Knuth",    "Art of Computer Programming");  // duplicate!

    cout << "Total books: " << lib.totalBooks() << "\n";
    lib.displayByAuthor();
    lib.topAuthors(2);
    lib.removeBook("Concrete Mathematics");
    lib.displayByAuthor();
    return 0;
}