cpp
STL
08_STL⚙️cpp
/**
* ============================================================
* C++ STL CONTAINERS
* ============================================================
*
* This file covers:
* - Sequence containers (vector, deque, list, array)
* - Associative containers (set, map, multiset, multimap)
* - Unordered containers (unordered_set, unordered_map)
* - Container adaptors (stack, queue, priority_queue)
* - When to use each container
*
* Compile: g++ -std=c++17 -Wall 01_containers.cpp -o containers
* Run: ./containers
*
* ============================================================
*/
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <forward_list>
#include <array>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
// Helper function to print any container
template <typename Container>
void printContainer(const string& name, const Container& c) {
cout << name << " [" << c.size() << "]: ";
for (const auto& elem : c) {
cout << elem << " ";
}
cout << endl;
}
// For map-like containers
template <typename Key, typename Value>
void printMap(const string& name, const map<Key, Value>& m) {
cout << name << " [" << m.size() << "]:" << endl;
for (const auto& [key, value] : m) {
cout << " " << key << " => " << value << endl;
}
}
// ============================================================
// MAIN FUNCTION
// ============================================================
int main() {
cout << "============================================" << endl;
cout << " C++ STL CONTAINERS" << endl;
cout << "============================================" << endl << endl;
// ========================================================
// PART 1: SEQUENCE CONTAINERS
// ========================================================
cout << "--- PART 1: SEQUENCE CONTAINERS ---" << endl << endl;
// ----- vector -----
cout << "[ VECTOR ] - Dynamic array, fast random access" << endl;
vector<int> vec = {1, 2, 3, 4, 5};
vec.push_back(6); // Add to end: O(1) amortized
vec.insert(vec.begin(), 0); // Insert at beginning: O(n)
vec.pop_back(); // Remove from end: O(1)
printContainer("vec", vec);
cout << "vec[2] = " << vec[2] << endl;
cout << "vec.front() = " << vec.front() << endl;
cout << "vec.back() = " << vec.back() << endl;
cout << "vec.capacity() = " << vec.capacity() << endl;
vec.reserve(100); // Pre-allocate
cout << "After reserve(100), capacity = " << vec.capacity() << endl;
cout << endl;
// ----- deque -----
cout << "[ DEQUE ] - Double-ended queue, fast front/back" << endl;
deque<int> dq = {3, 4, 5};
dq.push_front(2); // Fast: O(1)
dq.push_front(1); // Fast: O(1)
dq.push_back(6); // Fast: O(1)
printContainer("deque", dq);
cout << "dq[0] = " << dq[0] << " (random access works)" << endl;
cout << endl;
// ----- list -----
cout << "[ LIST ] - Doubly-linked list, fast insert/erase" << endl;
list<int> lst = {1, 3, 5};
lst.push_front(0); // O(1)
lst.push_back(6); // O(1)
auto it = find(lst.begin(), lst.end(), 3);
lst.insert(it, 2); // Insert before 3: O(1)
printContainer("list", lst);
lst.remove(3); // Remove all 3s: O(n)
lst.sort(); // Sort: O(n log n)
lst.unique(); // Remove consecutive duplicates
cout << "After remove(3), sort(), unique(): ";
printContainer("list", lst);
cout << endl;
// ----- forward_list -----
cout << "[ FORWARD_LIST ] - Singly-linked, minimal overhead" << endl;
forward_list<int> fwd = {2, 4, 6};
fwd.push_front(0);
fwd.insert_after(fwd.begin(), 1); // Insert after first
cout << "forward_list: ";
for (int x : fwd) cout << x << " ";
cout << "(no size() method!)" << endl;
cout << endl;
// ----- array -----
cout << "[ ARRAY ] - Fixed-size, stack-allocated" << endl;
array<int, 5> arr = {10, 20, 30, 40, 50};
cout << "array<int, 5>: ";
for (int x : arr) cout << x << " ";
cout << endl;
cout << "arr.size() = " << arr.size() << " (fixed at compile time)" << endl;
cout << "arr.at(2) = " << arr.at(2) << " (bounds checked)" << endl;
cout << endl;
// ========================================================
// PART 2: ASSOCIATIVE CONTAINERS
// ========================================================
cout << "--- PART 2: ASSOCIATIVE CONTAINERS ---" << endl << endl;
// ----- set -----
cout << "[ SET ] - Unique keys, sorted, O(log n) operations" << endl;
set<int> s = {5, 2, 8, 1, 9};
s.insert(3); // O(log n)
s.insert(5); // Ignored - already exists
s.erase(2); // O(log n)
printContainer("set", s);
cout << "s.count(3) = " << s.count(3) << endl;
cout << "s.count(100) = " << s.count(100) << endl;
auto sit = s.find(8);
if (sit != s.end()) {
cout << "Found 8 in set" << endl;
}
cout << endl;
// ----- multiset -----
cout << "[ MULTISET ] - Allows duplicates, sorted" << endl;
multiset<int> ms = {1, 2, 2, 3, 3, 3};
ms.insert(2); // Now has three 2s
printContainer("multiset", ms);
cout << "ms.count(2) = " << ms.count(2) << endl;
cout << "ms.count(3) = " << ms.count(3) << endl;
cout << endl;
// ----- map -----
cout << "[ MAP ] - Key-value pairs, sorted by key" << endl;
map<string, int> ages;
ages["Alice"] = 30;
ages["Bob"] = 25;
ages.insert({"Charlie", 35});
ages.emplace("Diana", 28);
printMap("ages", ages);
cout << "ages[\"Alice\"] = " << ages["Alice"] << endl;
cout << "ages.at(\"Bob\") = " << ages.at("Bob") << endl;
// Iteration
cout << "Iterating:" << endl;
for (const auto& [name, age] : ages) {
cout << " " << name << " is " << age << " years old" << endl;
}
cout << endl;
// ----- multimap -----
cout << "[ MULTIMAP ] - Multiple values per key" << endl;
multimap<string, string> phonebook;
phonebook.insert({"Alice", "555-1234"});
phonebook.insert({"Alice", "555-5678"}); // Another number for Alice
phonebook.insert({"Bob", "555-9999"});
cout << "Phonebook entries for Alice:" << endl;
auto range = phonebook.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
cout << " " << it->second << endl;
}
cout << endl;
// ========================================================
// PART 3: UNORDERED CONTAINERS
// ========================================================
cout << "--- PART 3: UNORDERED CONTAINERS ---" << endl << endl;
// ----- unordered_set -----
cout << "[ UNORDERED_SET ] - Hash table, O(1) average" << endl;
unordered_set<string> words = {"apple", "banana", "cherry"};
words.insert("date");
words.insert("apple"); // Ignored - exists
cout << "unordered_set: ";
for (const auto& w : words) cout << w << " ";
cout << "(order not guaranteed)" << endl;
cout << "Bucket count: " << words.bucket_count() << endl;
cout << "Load factor: " << words.load_factor() << endl;
cout << endl;
// ----- unordered_map -----
cout << "[ UNORDERED_MAP ] - Hash map, O(1) average" << endl;
unordered_map<string, double> prices;
prices["apple"] = 1.50;
prices["banana"] = 0.75;
prices["cherry"] = 3.00;
cout << "Prices:" << endl;
for (const auto& [item, price] : prices) {
cout << " " << item << ": $" << price << endl;
}
cout << "\nprices[\"apple\"] = $" << prices["apple"] << endl;
cout << "prices.count(\"grape\") = " << prices.count("grape") << endl;
cout << endl;
// ========================================================
// PART 4: CONTAINER ADAPTORS
// ========================================================
cout << "--- PART 4: CONTAINER ADAPTORS ---" << endl << endl;
// ----- stack -----
cout << "[ STACK ] - LIFO (Last In, First Out)" << endl;
stack<int> stk;
stk.push(1);
stk.push(2);
stk.push(3);
cout << "Stack (top to bottom): ";
while (!stk.empty()) {
cout << stk.top() << " ";
stk.pop();
}
cout << endl;
cout << endl;
// ----- queue -----
cout << "[ QUEUE ] - FIFO (First In, First Out)" << endl;
queue<string> q;
q.push("first");
q.push("second");
q.push("third");
cout << "Queue (front to back): ";
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
cout << endl;
cout << endl;
// ----- priority_queue -----
cout << "[ PRIORITY_QUEUE ] - Heap, largest first" << endl;
priority_queue<int> pq;
pq.push(30);
pq.push(10);
pq.push(50);
pq.push(20);
cout << "Priority queue (largest first): ";
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
// Min-heap (smallest first)
priority_queue<int, vector<int>, greater<int>> minPQ;
minPQ.push(30);
minPQ.push(10);
minPQ.push(50);
cout << "Min-heap (smallest first): ";
while (!minPQ.empty()) {
cout << minPQ.top() << " ";
minPQ.pop();
}
cout << endl;
cout << endl;
// ========================================================
// CONTAINER SELECTION GUIDE
// ========================================================
cout << "--- CONTAINER SELECTION GUIDE ---" << endl << endl;
cout << "┌──────────────────┬─────────────────────────────────────┐" << endl;
cout << "│ Need │ Use │" << endl;
cout << "├──────────────────┼─────────────────────────────────────┤" << endl;
cout << "│ Random access │ vector, deque, array │" << endl;
cout << "│ Insert at front │ deque, list, forward_list │" << endl;
cout << "│ Insert anywhere │ list, forward_list │" << endl;
cout << "│ Sorted unique │ set, map │" << endl;
cout << "│ Fast lookup │ unordered_set, unordered_map │" << endl;
cout << "│ LIFO │ stack │" << endl;
cout << "│ FIFO │ queue │" << endl;
cout << "│ Priority │ priority_queue │" << endl;
cout << "│ Fixed size │ array │" << endl;
cout << "└──────────────────┴─────────────────────────────────────┘" << endl;
cout << "\nComplexity Summary:" << endl;
cout << "─────────────────────────────────────────" << endl;
cout << "vector: O(1) back, O(n) front/middle" << endl;
cout << "deque: O(1) front/back, O(n) middle" << endl;
cout << "list: O(1) anywhere (with iterator)" << endl;
cout << "set/map: O(log n) all operations" << endl;
cout << "unordered_*: O(1) average, O(n) worst" << endl;
cout << endl;
cout << "============================================" << endl;
cout << "STL CONTAINERS COMPLETE!" << endl;
cout << "============================================" << endl;
return 0;
}
// ============================================================
// EXERCISES:
// ============================================================
/*
* 1. Implement a word frequency counter:
* - Read words from input
* - Use unordered_map to count occurrences
* - Print top 10 most frequent words
*
* 2. Implement a LRU Cache using:
* - unordered_map for O(1) lookup
* - list for tracking recent access
* - Move accessed items to front
*
* 3. Create a task scheduler:
* - Use priority_queue for tasks
* - Tasks have priority and deadline
* - Process highest priority first
*
* 4. Implement a phone book:
* - map<string, set<string>> for name -> numbers
* - Support add, remove, search
* - Handle multiple numbers per contact
*/