Introduction to STL
The Standard Template Library (STL) is one of C++'s most powerful features. It provides a collection of template classes and functions that implement common data structures and algorithms, saving you from reinventing the wheel and letting you focus on solving problems.
Standard Template Library (STL)
The STL is a software library that provides four components: Containers (data structures), Iterators (container traversal), Algorithms (operations on containers), and Functors (function objects).
Key Benefit: STL containers are generic (work with any data type), efficient (optimized implementations), and safe (handle memory management automatically).
STL Container Categories
STL containers are organized into three main categories based on how they store and access data:
// To use STL containers, include the appropriate headers
#include <vector> // Dynamic array
#include <list> // Doubly-linked list
#include <deque> // Double-ended queue
#include <set> // Sorted unique elements
#include <map> // Key-value pairs (sorted)
#include <unordered_set> // Hash-based unique elements
#include <unordered_map> // Hash-based key-value pairs
#include <stack> // LIFO adapter
#include <queue> // FIFO adapter
#include <array> // Fixed-size array (C++11)Each #include statement loads a specific container into your program. Think of it like importing tools from a toolbox - you only grab what you need for your task. For example, if you want to use a vector, you write #include <vector> at the top of your file. You can include multiple containers in the same program by adding multiple include statements.
Sequence Containers
- Elements stored in linear order
- Access by position (index)
- vector, list, deque, array
Associative Containers
- Elements stored in sorted order
- Fast search by key - O(log n)
- set, map, multiset, multimap
Unordered Containers
- Hash-based storage
- Average O(1) access
- unordered_set, unordered_map
Common Container Operations
All STL containers share common member functions for consistency:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> numbers = {10, 20, 30, 40, 50};
// Size operations - available on ALL containers
cout << "Size: " << numbers.size() << endl; // 5
cout << "Empty? " << numbers.empty() << endl; // 0 (false)
cout << "Max size: " << numbers.max_size() << endl;
// Element access (sequence containers)
cout << "Front: " << numbers.front() << endl; // 10
cout << "Back: " << numbers.back() << endl; // 50
// Modifiers
numbers.push_back(60); // Add to end
numbers.pop_back(); // Remove from end
numbers.clear(); // Remove all elements
cout << "After clear, size: " << numbers.size() << endl; // 0
return 0;
}This example demonstrates the essential operations that work on almost every STL container. The size() function returns how many elements are stored, while empty() returns true if the container has no elements. For sequence containers, front() gives you the first element and back() gives you the last one. To modify the container, use push_back() to add an element at the end, pop_back() to remove the last element, and clear() to delete everything at once.
Practice Questions: Introduction
Task: Create a vector of 5 integers. Use size(), empty(), front(), and back() to display container information. Then use push_back() to add a new element and clear() to empty the container.
Show Solution
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> numbers = {10, 20, 30, 40, 50};
// Display container information
cout << "Size: " << numbers.size() << endl;
cout << "Empty? " << (numbers.empty() ? "Yes" : "No") << endl;
cout << "First element: " << numbers.front() << endl;
cout << "Last element: " << numbers.back() << endl;
// Add new element
numbers.push_back(60);
cout << "\nAfter push_back(60):" << endl;
cout << "Size: " << numbers.size() << endl;
cout << "Last element: " << numbers.back() << endl;
// Clear container
numbers.clear();
cout << "\nAfter clear():" << endl;
cout << "Size: " << numbers.size() << endl;
cout << "Empty? " << (numbers.empty() ? "Yes" : "No") << endl;
return 0;
}
// Output:
// Size: 5
// Empty? No
// First element: 10
// Last element: 50
// After push_back(60):
// Size: 6
// Last element: 60
// After clear():
// Size: 0
// Empty? YesTask: Create a vector with values {10, 20, 30, 40, 50}. Iterate through it using three different methods: (1) range-based for loop, (2) index-based for loop with size(), and (3) iterator-based loop. Print all elements with each method.
Show Solution
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> nums = {10, 20, 30, 40, 50};
// Method 1: Range-based for loop (simplest)
cout << "Range-based for: ";
for (int x : nums) {
cout << x << " ";
}
cout << endl;
// Method 2: Index-based for loop
cout << "Index-based for: ";
for (size_t i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
cout << endl;
// Method 3: Iterator-based loop
cout << "Iterator-based: ";
for (auto it = nums.begin(); it != nums.end(); ++it) {
cout << *it << " ";
}
cout << endl;
return 0;
}
// Output:
// Range-based for: 10 20 30 40 50
// Index-based for: 10 20 30 40 50
// Iterator-based: 10 20 30 40 50Task: Write a program that includes and uses three different STL containers: vector, set, and map. Store student names in a vector, unique IDs in a set, and name-to-age mappings in a map. Display all data.
Show Solution
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;
int main() {
// Vector - stores elements in sequence
vector<string> names = {"Alice", "Bob", "Charlie"};
// Set - stores unique sorted elements
set<int> studentIDs = {103, 101, 102, 101}; // Duplicate 101 removed
// Map - stores key-value pairs
map<string, int> ages;
ages["Alice"] = 20;
ages["Bob"] = 22;
ages["Charlie"] = 21;
// Display vector
cout << "Names (vector): ";
for (const string& name : names) {
cout << name << " ";
}
cout << endl;
// Display set
cout << "Student IDs (set): ";
for (int id : studentIDs) {
cout << id << " ";
}
cout << endl;
// Display map
cout << "Ages (map):" << endl;
for (const auto& pair : ages) {
cout << " " << pair.first << ": " << pair.second << endl;
}
return 0;
}
// Output:
// Names (vector): Alice Bob Charlie
// Student IDs (set): 101 102 103
// Ages (map):
// Alice: 20
// Bob: 22
// Charlie: 21Task: Create both a vector and a set with the same input values {5, 2, 8, 2, 1, 9, 5, 3}. Display both containers and explain the differences in output. Show the size() of each container.
Show Solution
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main() {
// Same input values for both
vector<int> vec = {5, 2, 8, 2, 1, 9, 5, 3};
set<int> s = {5, 2, 8, 2, 1, 9, 5, 3};
cout << "Input values: {5, 2, 8, 2, 1, 9, 5, 3}" << endl;
cout << endl;
// Display vector
cout << "Vector contents: ";
for (int x : vec) cout << x << " ";
cout << endl;
cout << "Vector size: " << vec.size() << endl;
cout << "Behavior: Preserves insertion order, keeps duplicates" << endl;
cout << endl;
// Display set
cout << "Set contents: ";
for (int x : s) cout << x << " ";
cout << endl;
cout << "Set size: " << s.size() << endl;
cout << "Behavior: Sorted automatically, duplicates removed" << endl;
return 0;
}
// Output:
// Input values: {5, 2, 8, 2, 1, 9, 5, 3}
//
// Vector contents: 5 2 8 2 1 9 5 3
// Vector size: 8
// Behavior: Preserves insertion order, keeps duplicates
//
// Set contents: 1 2 3 5 8 9
// Set size: 6
// Behavior: Sorted automatically, duplicates removedSequence Containers
Sequence containers store elements in a linear sequence where each element has a specific position. They differ in how elements are stored in memory and which operations are efficient.
Vector - Dynamic Array
vector is the most commonly used container. It stores elements in contiguous memory
(like an array) but can grow dynamically. Use it when you need fast random access and mostly
add elements at the end.
#include <iostream>
#include <vector>
using namespace std;
int main() {
// Creating vectors
vector<int> v1; // Empty vector
vector<int> v2(5); // 5 elements, all 0
vector<int> v3(5, 100); // 5 elements, all 100
vector<int> v4 = {1, 2, 3, 4, 5}; // Initializer list
cout << "v3: ";
for (int x : v3) cout << x << " "; // 100 100 100 100 100
cout << endl;
return 0;
}This code shows four different ways to create a vector. First, vector<int> v1; creates an empty vector with no elements. Second, vector<int> v2(5); creates a vector with 5 elements, all initialized to zero. Third, vector<int> v3(5, 100); creates a vector with 5 elements, all set to 100. Finally, vector<int> v4 = {1, 2, 3, 4, 5}; creates a vector with specific values using an initializer list. The for (int x : v3) syntax is called a range-based for loop - it's the simplest way to iterate through all elements.
Common vector operations:
vector<string> fruits = {"apple", "banana"};
// Adding elements
fruits.push_back("cherry"); // Add at end - O(1) amortized
fruits.insert(fruits.begin(), "apricot"); // Insert at beginning - O(n)
// Accessing elements
cout << fruits[0] << endl; // "apricot" - no bounds checking
cout << fruits.at(1) << endl; // "apple" - throws if out of bounds
// Removing elements
fruits.pop_back(); // Remove last - O(1)
fruits.erase(fruits.begin()); // Remove first - O(n)
// Capacity
cout << "Size: " << fruits.size() << endl;
cout << "Capacity: " << fruits.capacity() << endl;
fruits.reserve(100); // Pre-allocate space
fruits.shrink_to_fit(); // Release unused memoryHere are the most common vector operations explained. push_back() adds an element to the end and is very fast. insert() can add elements anywhere, but it's slower because all elements after the insertion point must shift. For accessing elements, fruits[0] is quick but won't warn you if the index is invalid, while fruits.at(1) performs bounds checking and throws an error if you go out of range. pop_back() removes the last element, and erase() removes elements at any position. The reserve(100) function pre-allocates memory for 100 elements, which improves performance when you know approximately how many elements you'll add.
reserve() when you know approximately how many
elements you'll add. This prevents multiple reallocations as the vector grows.
List - Doubly Linked List
list stores elements as a doubly-linked list. Each element points to the next and
previous elements. Use it when you need fast insertion and deletion anywhere in the container.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> numbers = {10, 20, 30, 40, 50};
// Fast insertion anywhere - O(1) once you have iterator
auto it = numbers.begin();
advance(it, 2); // Move to position 2
numbers.insert(it, 25); // Insert 25 before 30
// Fast removal anywhere - O(1)
numbers.remove(40); // Remove all elements with value 40
// List-specific operations
numbers.push_front(5); // Add at beginning - O(1)
numbers.pop_front(); // Remove from beginning - O(1)
// Print list
for (int n : numbers) cout << n << " "; // 10 20 25 30 50
cout << endl;
return 0;
}This example shows how list differs from vector. The key advantage of list is that inserting or removing elements anywhere is very fast once you have an iterator pointing to that position. The advance(it, 2) function moves the iterator forward by 2 positions (since list doesn't support direct indexing like list[2]). The remove(40) function finds and deletes ALL elements with the value 40. Unlike vector, list has push_front() which efficiently adds elements at the beginning - with vector, this would be slow because all elements would need to shift.
List provides unique operations not available on vector:
list<int> list1 = {1, 3, 5};
list<int> list2 = {2, 4, 6};
// Merge two sorted lists - O(n)
list1.merge(list2); // list1: {1, 2, 3, 4, 5, 6}, list2: empty
// Sort the list - O(n log n)
list<int> unsorted = {5, 2, 8, 1, 9};
unsorted.sort(); // {1, 2, 5, 8, 9}
// Remove consecutive duplicates
list<int> dups = {1, 1, 2, 2, 2, 3, 3};
dups.unique(); // {1, 2, 3}
// Reverse the list - O(n)
dups.reverse(); // {3, 2, 1}List provides special member functions that aren't available on vector. The merge() function combines two sorted lists into one sorted list - note that both lists must already be sorted for this to work correctly. The sort() function sorts all elements in ascending order. The unique() function removes consecutive duplicate elements, but the list should be sorted first so that all duplicates are next to each other. Finally, reverse() flips the entire list so the last element becomes the first and vice versa.
Deque - Double-Ended Queue
deque (pronounced "deck") allows fast insertion and deletion at both ends.
Unlike vector, adding elements at the front is efficient. It provides random access like vector.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq = {30, 40, 50};
// Fast operations at both ends - O(1)
dq.push_front(20); // Add at front
dq.push_back(60); // Add at back
dq.pop_front(); // Remove from front
dq.pop_back(); // Remove from back
// Random access like vector
cout << "Element at index 1: " << dq[1] << endl; // 40
cout << "Element at index 1: " << dq.at(1) << endl; // 40
// Print deque
for (int x : dq) cout << x << " "; // 30 40 50
cout << endl;
return 0;
}Deque (pronounced "deck") combines the best features of vector and list. Like vector, you can access any element instantly using dq[1] or dq.at(1). But unlike vector, deque supports fast operations at both ends: push_front() and pop_front() for the beginning, and push_back() and pop_back() for the end. This makes deque perfect for situations where you need to add or remove elements from both sides, like implementing a sliding window or a double-ended buffer.
| Operation | vector | list | deque |
|---|---|---|---|
| Random Access | O(1) | O(n) | O(1) |
| Insert/Remove at End | O(1)* | O(1) | O(1) |
| Insert/Remove at Front | O(n) | O(1) | O(1) |
| Insert/Remove in Middle | O(n) | O(1)* | O(n) |
| Memory | Contiguous | Scattered | Chunked |
Practice Questions: Sequence Containers
Task: Create a vector with values {10, 20, 30, 40, 50}. Insert 15 between 10 and 20 using insert(). Remove 30 using erase(). Access the third element using both [] and at(). Print the vector after each operation.
Show Solution
#include <iostream>
#include <vector>
using namespace std;
void printVector(const vector<int>& v) {
for (int x : v) cout << x << " ";
cout << endl;
}
int main() {
vector<int> nums = {10, 20, 30, 40, 50};
cout << "Original: ";
printVector(nums);
// Insert 15 at position 1 (between 10 and 20)
nums.insert(nums.begin() + 1, 15);
cout << "After insert(15): ";
printVector(nums);
// Find and erase 30
for (auto it = nums.begin(); it != nums.end(); ++it) {
if (*it == 30) {
nums.erase(it);
break;
}
}
cout << "After erase(30): ";
printVector(nums);
// Access third element (index 2) using [] and at()
cout << "Third element using []: " << nums[2] << endl;
cout << "Third element using at(): " << nums.at(2) << endl;
return 0;
}
// Output:
// Original: 10 20 30 40 50
// After insert(15): 10 15 20 30 40 50
// After erase(30): 10 15 20 40 50
// Third element using []: 20
// Third element using at(): 20Task: Create an empty vector. Use push_back() to add numbers 1-5. Display size() and capacity() after each addition. Then use pop_back() to remove the last two elements. Finally, use reserve(100) and show how it affects capacity.
Show Solution
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> nums;
cout << "Adding elements with push_back():" << endl;
for (int i = 1; i <= 5; i++) {
nums.push_back(i);
cout << "Added " << i << " - Size: " << nums.size()
<< ", Capacity: " << nums.capacity() << endl;
}
cout << "\nVector contents: ";
for (int x : nums) cout << x << " ";
cout << endl;
// Remove last two elements
cout << "\nUsing pop_back() twice:" << endl;
nums.pop_back();
cout << "After 1st pop_back - Size: " << nums.size() << endl;
nums.pop_back();
cout << "After 2nd pop_back - Size: " << nums.size() << endl;
cout << "Vector now: ";
for (int x : nums) cout << x << " ";
cout << endl;
// Reserve capacity
cout << "\nBefore reserve: Capacity = " << nums.capacity() << endl;
nums.reserve(100);
cout << "After reserve(100): Capacity = " << nums.capacity() << endl;
cout << "Size unchanged: " << nums.size() << endl;
return 0;
}
// Output:
// Adding elements with push_back():
// Added 1 - Size: 1, Capacity: 1
// Added 2 - Size: 2, Capacity: 2
// Added 3 - Size: 3, Capacity: 4
// Added 4 - Size: 4, Capacity: 4
// Added 5 - Size: 5, Capacity: 8
// Vector contents: 1 2 3 4 5
// Using pop_back() twice:
// After 1st pop_back - Size: 4
// After 2nd pop_back - Size: 3
// Vector now: 1 2 3
// Before reserve: Capacity = 8
// After reserve(100): Capacity = 100
// Size unchanged: 3Task: Create two lists: list1 = {5, 1, 3} and list2 = {4, 2, 3}. Sort both lists using sort(). Merge list2 into list1 using merge(). Remove duplicates using unique(). Reverse the final list using reverse().
Show Solution
#include <iostream>
#include <list>
using namespace std;
void printList(const list<int>& lst, const string& label) {
cout << label << ": ";
for (int x : lst) cout << x << " ";
cout << endl;
}
int main() {
list<int> list1 = {5, 1, 3};
list<int> list2 = {4, 2, 3};
printList(list1, "Original list1");
printList(list2, "Original list2");
// Sort both lists (required before merge)
list1.sort();
list2.sort();
cout << "\nAfter sorting:" << endl;
printList(list1, "list1");
printList(list2, "list2");
// Merge list2 into list1
list1.merge(list2);
printList(list1, "\nAfter merge");
cout << "list2 size: " << list2.size() << " (empty after merge)" << endl;
// Remove consecutive duplicates
list1.unique();
printList(list1, "\nAfter unique");
// Reverse the list
list1.reverse();
printList(list1, "After reverse");
return 0;
}
// Output:
// Original list1: 5 1 3
// Original list2: 4 2 3
// After sorting:
// list1: 1 3 5
// list2: 2 3 4
// After merge: 1 2 3 3 4 5
// list2 size: 0 (empty after merge)
// After unique: 1 2 3 4 5
// After reverse: 5 4 3 2 1Task: Create a deque with initial value {30}. Use push_front() to add 20 and 10 at the front. Use push_back() to add 40 and 50 at the back. Access elements using [] and at(). Use pop_front() and pop_back() to remove elements from both ends.
Show Solution
#include <iostream>
#include <deque>
using namespace std;
void printDeque(const deque<int>& dq) {
for (int x : dq) cout << x << " ";
cout << endl;
}
int main() {
deque<int> dq = {30};
cout << "Initial deque: ";
printDeque(dq);
// Add at front
dq.push_front(20);
dq.push_front(10);
cout << "After push_front(20, 10): ";
printDeque(dq);
// Add at back
dq.push_back(40);
dq.push_back(50);
cout << "After push_back(40, 50): ";
printDeque(dq);
// Random access
cout << "\nRandom access:" << endl;
cout << "dq[0] = " << dq[0] << endl;
cout << "dq[2] = " << dq[2] << endl;
cout << "dq.at(4) = " << dq.at(4) << endl;
// Remove from both ends
cout << "\nRemoving from both ends:" << endl;
dq.pop_front();
cout << "After pop_front(): ";
printDeque(dq);
dq.pop_back();
cout << "After pop_back(): ";
printDeque(dq);
cout << "\nFront: " << dq.front() << ", Back: " << dq.back() << endl;
return 0;
}
// Output:
// Initial deque: 30
// After push_front(20, 10): 10 20 30
// After push_back(40, 50): 10 20 30 40 50
// Random access:
// dq[0] = 10
// dq[2] = 30
// dq.at(4) = 50
// Removing from both ends:
// After pop_front(): 20 30 40 50
// After pop_back(): 20 30 40
// Front: 20, Back: 40Associative Containers
Associative containers store elements in a sorted order determined by their keys. They use balanced binary search trees internally, providing O(log n) search, insertion, and deletion.
Set - Unique Sorted Elements
set stores unique elements in sorted order. It automatically removes duplicates and
keeps elements sorted. Perfect for maintaining a collection of unique items with fast lookup.
#include <iostream>
#include <set>
using namespace std;
int main() {
// Creating a set - duplicates are automatically removed
set<int> numbers = {5, 2, 8, 2, 1, 9, 5, 3};
// Elements are automatically sorted and unique
cout << "Set contents: ";
for (int n : numbers) cout << n << " "; // 1 2 3 5 8 9
cout << endl;
return 0;
}Notice something interesting in the output: even though we added {5, 2, 8, 2, 1, 9, 5, 3} with duplicates, the set only contains {1, 2, 3, 5, 8, 9}. Set automatically removes duplicate values and keeps elements sorted in ascending order. You don't need to do anything special - just add elements and set handles the sorting and deduplication for you. This makes set perfect for maintaining a collection of unique items where you need fast searching.
Common set operations:
set<string> fruits = {"apple", "banana", "cherry"};
// Insert - returns pair<iterator, bool>
auto result = fruits.insert("date");
cout << "Inserted: " << result.second << endl; // 1 (true)
result = fruits.insert("apple"); // Already exists
cout << "Inserted: " << result.second << endl; // 0 (false)
// Find - O(log n)
auto it = fruits.find("banana");
if (it != fruits.end()) {
cout << "Found: " << *it << endl;
}
// Count - returns 0 or 1 for set
cout << "Contains cherry? " << fruits.count("cherry") << endl; // 1
// Erase
fruits.erase("banana"); // Remove by value
fruits.erase(fruits.begin()); // Remove by iteratorWhen you call insert() on a set, it returns a pair containing an iterator and a boolean. The boolean (result.second) tells you whether the insertion actually happened: true means the element was new and added, false means it already existed so nothing changed. The find() function searches for an element and returns an iterator pointing to it, or end() if not found - always check if (it != fruits.end()) before using the result. The count() function returns 0 if the element doesn't exist or 1 if it does (for regular set, it's never more than 1). Use erase() to remove elements by value or by iterator.
Map - Key-Value Pairs
map stores key-value pairs sorted by key. Each key is unique and maps to exactly
one value. Think of it as a dictionary or phone book.
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
// Creating a map
map<string, int> ages;
// Inserting elements - multiple ways
ages["Alice"] = 25;
ages["Bob"] = 30;
ages.insert({"Charlie", 35});
ages.insert(make_pair("Diana", 28));
// Accessing elements
cout << "Alice's age: " << ages["Alice"] << endl; // 25
cout << "Bob's age: " << ages.at("Bob") << endl; // 30
// Iterating - sorted by key
cout << "\nAll ages:\n";
for (const auto& pair : ages) {
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}Map stores data as key-value pairs, similar to a dictionary or phone book where you look up a name (key) to find a number (value). You can add entries using the bracket syntax ages["Alice"] = 25 or the insert() function with curly braces or make_pair(). To access a value, use either ages["Alice"] or the safer ages.at("Bob") which throws an error if the key doesn't exist. When you iterate through a map, each element is a pair where pair.first gives you the key and pair.second gives you the value. Keys are automatically kept in sorted order (alphabetically for strings).
map[key] creates a new entry with default value if
the key doesn't exist. Use find() or count() to check existence first.
Safe access patterns:
map<string, double> prices = {{"apple", 1.50}, {"banana", 0.75}};
// DANGER: This creates "orange" with value 0.0!
// double price = prices["orange"];
// Safe: Check with find()
auto it = prices.find("orange");
if (it != prices.end()) {
cout << "Price: " << it->second << endl;
} else {
cout << "Orange not found" << endl;
}
// Safe: Check with count()
if (prices.count("apple") > 0) {
cout << "Apple price: " << prices["apple"] << endl;
}
// C++20: contains() method
// if (prices.contains("banana")) { ... }This is a common gotcha with maps that trips up beginners. If you write prices["orange"] and "orange" doesn't exist in the map, C++ automatically creates a new entry with the key "orange" and a default value (0.0 for doubles, empty string for strings, etc.). This can cause bugs! To safely check if a key exists, use find() which returns an iterator to the element or end() if not found. Alternatively, use count() which returns 1 if the key exists or 0 if it doesn't. In C++20 and later, you can use the cleaner contains() method.
Multiset and Multimap
multiset and multimap allow duplicate keys. Use them when you need
to store multiple values with the same key.
#include <iostream>
#include <set>
#include <map>
using namespace std;
int main() {
// Multiset - allows duplicates
multiset<int> ms = {5, 2, 5, 8, 2, 5};
cout << "Multiset: ";
for (int n : ms) cout << n << " "; // 2 2 5 5 5 8
cout << "\nCount of 5: " << ms.count(5) << endl; // 3
// Multimap - multiple values per key
multimap<string, string> phonebook;
phonebook.insert({"John", "555-1234"});
phonebook.insert({"John", "555-5678"}); // Same key, different value
phonebook.insert({"Jane", "555-9999"});
cout << "\nJohn's numbers:\n";
auto range = phonebook.equal_range("John");
for (auto it = range.first; it != range.second; ++it) {
cout << " " << it->second << endl;
}
return 0;
}Unlike regular set and map which require unique keys, multiset and multimap allow duplicate keys. In the multiset example, the value 5 appears three times, so count(5) returns 3. In the multimap example, "John" has two phone numbers associated with it. To retrieve all values for a specific key, use equal_range() which returns a pair of iterators: range.first points to the first matching element and range.second points just past the last matching element. You can then loop through this range to process all values with that key.
Practice Questions: Associative Containers
Task: Create a set with values {5, 2, 8, 1, 9}. Use insert() to add 3 and check if insertion succeeded. Use find() to search for 8 and 10. Use count() to check if 5 exists. Use erase() to remove 2. Print the set after modifications.
Show Solution
#include <iostream>
#include <set>
using namespace std;
void printSet(const set<int>& s) {
for (int x : s) cout << x << " ";
cout << endl;
}
int main() {
set<int> nums = {5, 2, 8, 1, 9};
cout << "Original set: ";
printSet(nums);
// Insert 3 and check result
auto result = nums.insert(3);
cout << "\nInsert 3: " << (result.second ? "Success" : "Failed") << endl;
cout << "Set after insert: ";
printSet(nums);
// Find 8 and 10
cout << "\nSearching with find():" << endl;
auto it8 = nums.find(8);
cout << " find(8): " << (it8 != nums.end() ? "Found" : "Not found") << endl;
auto it10 = nums.find(10);
cout << " find(10): " << (it10 != nums.end() ? "Found" : "Not found") << endl;
// Check if 5 exists using count()
cout << "\nUsing count():" << endl;
cout << " count(5): " << nums.count(5) << " (exists)" << endl;
cout << " count(10): " << nums.count(10) << " (not exists)" << endl;
// Erase 2
nums.erase(2);
cout << "\nAfter erase(2): ";
printSet(nums);
return 0;
}
// Output:
// Original set: 1 2 5 8 9
// Insert 3: Success
// Set after insert: 1 2 3 5 8 9
// Searching with find():
// find(8): Found
// find(10): Not found
// Using count():
// count(5): 1 (exists)
// count(10): 0 (not exists)
// After erase(2): 1 3 5 8 9Task: Create a map to store student names and their scores. Add 4 students using both [] syntax and insert(). Iterate through the map using a range-based for loop displaying each name and score. Show that entries are automatically sorted by key.
Show Solution
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<string, int> scores;
// Insert using [] syntax
scores["Charlie"] = 85;
scores["Alice"] = 92;
// Insert using insert()
scores.insert({"Bob", 78});
scores.insert(make_pair("Diana", 95));
cout << "Student Scores (auto-sorted by name):" << endl;
cout << "-------------------------------------" << endl;
// Iterate using range-based for loop
for (const auto& pair : scores) {
cout << pair.first << ": " << pair.second << endl;
}
cout << "\nTotal students: " << scores.size() << endl;
// Access specific score
cout << "\nAlice's score: " << scores["Alice"] << endl;
return 0;
}
// Output:
// Student Scores (auto-sorted by name):
// -------------------------------------
// Alice: 92
// Bob: 78
// Charlie: 85
// Diana: 95
// Total students: 4
// Alice's score: 92Task: Create a map of product prices: {"apple": 1.50, "banana": 0.75, "orange": 2.00}. Demonstrate the difference between [] and at(). Show the safe access pattern using find() and count() to avoid creating unwanted entries when checking for non-existent keys.
Show Solution
#include <iostream>
#include <map>
#include <string>
using namespace std;
void printMap(const map<string, double>& m) {
for (const auto& p : m) {
cout << " " << p.first << ": $" << p.second << endl;
}
}
int main() {
map<string, double> prices;
prices["apple"] = 1.50;
prices["banana"] = 0.75;
prices["orange"] = 2.00;
cout << "Original map:" << endl;
printMap(prices);
cout << "Size: " << prices.size() << endl;
// Access using [] - DANGER: creates entry if not exists!
cout << "\n--- Using [] operator ---" << endl;
cout << "prices[\"apple\"]: $" << prices["apple"] << endl;
// This creates "grape" with value 0.0!
double grapePrice = prices["grape"];
cout << "prices[\"grape\"]: $" << grapePrice << " (created with default!)" << endl;
cout << "Map after accessing \"grape\":" << endl;
printMap(prices);
// Safe access using at() - throws if not exists
cout << "\n--- Using at() ---" << endl;
cout << "prices.at(\"banana\"): $" << prices.at("banana") << endl;
// Safe access using find()
cout << "\n--- Safe pattern with find() ---" << endl;
auto it = prices.find("mango");
if (it != prices.end()) {
cout << "Mango price: $" << it->second << endl;
} else {
cout << "Mango not found (no entry created)" << endl;
}
// Safe access using count()
cout << "\n--- Safe pattern with count() ---" << endl;
if (prices.count("orange") > 0) {
cout << "Orange exists, price: $" << prices["orange"] << endl;
}
cout << "\nFinal map size: " << prices.size() << endl;
return 0;
}
// Output:
// Original map:
// apple: $1.5
// banana: $0.75
// orange: $2
// Size: 3
// --- Using [] operator ---
// prices["apple"]: $1.5
// prices["grape"]: $0 (created with default!)
// Map after accessing "grape":
// apple: $1.5
// banana: $0.75
// grape: $0
// orange: $2
// --- Using at() ---
// prices.at("banana"): $0.75
// --- Safe pattern with find() ---
// Mango not found (no entry created)
// --- Safe pattern with count() ---
// Orange exists, price: $2
// Final map size: 4Task: Create a multiset with values {5, 2, 5, 8, 2, 5, 1}. Use count() to show duplicates are stored. Create a multimap to store student names with multiple test scores. Use equal_range() to retrieve all scores for a specific student.
Show Solution
#include <iostream>
#include <set>
#include <map>
#include <string>
using namespace std;
int main() {
// Multiset - allows duplicate values
cout << "=== MULTISET ===" << endl;
multiset<int> ms = {5, 2, 5, 8, 2, 5, 1};
cout << "Multiset contents: ";
for (int x : ms) cout << x << " ";
cout << endl;
cout << "Count of 5: " << ms.count(5) << endl;
cout << "Count of 2: " << ms.count(2) << endl;
cout << "Count of 1: " << ms.count(1) << endl;
cout << "Total size: " << ms.size() << endl;
// Multimap - allows duplicate keys
cout << "\n=== MULTIMAP ===" << endl;
multimap<string, int> studentScores;
studentScores.insert({"Alice", 85});
studentScores.insert({"Alice", 92});
studentScores.insert({"Alice", 78});
studentScores.insert({"Bob", 90});
studentScores.insert({"Bob", 88});
cout << "All scores:" << endl;
for (const auto& p : studentScores) {
cout << " " << p.first << ": " << p.second << endl;
}
// Get all scores for Alice using equal_range
cout << "\nAlice's scores using equal_range():" << endl;
auto range = studentScores.equal_range("Alice");
int sum = 0, count = 0;
for (auto it = range.first; it != range.second; ++it) {
cout << " Test " << (count + 1) << ": " << it->second << endl;
sum += it->second;
count++;
}
cout << " Average: " << (double)sum / count << endl;
return 0;
}
// Output:
// === MULTISET ===
// Multiset contents: 1 2 2 5 5 5 8
// Count of 5: 3
// Count of 2: 2
// Count of 1: 1
// Total size: 7
// === MULTIMAP ===
// All scores:
// Alice: 85
// Alice: 92
// Alice: 78
// Bob: 90
// Bob: 88
// Alice's scores using equal_range():
// Test 1: 85
// Test 2: 92
// Test 3: 78
// Average: 85Unordered Containers
Unordered containers use hash tables for O(1) average-case access. They trade sorted order for speed - perfect when you need the fastest possible lookups and don't care about element order.
Unordered Set
unordered_set is like set but uses hashing instead of sorting.
It provides O(1) average-case operations but elements are not in any particular order.
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> numbers = {5, 2, 8, 1, 9, 3};
// Elements are NOT sorted
cout << "Unordered set: ";
for (int n : numbers) cout << n << " "; // Order varies!
cout << endl;
// O(1) average lookup
if (numbers.count(5) > 0) {
cout << "Found 5!" << endl;
}
// Insert and check result
auto result = numbers.insert(10);
cout << "Inserted 10: " << result.second << endl; // 1 (true)
return 0;
}When you run this code, the output order will be different from the input order and may even vary between runs. This is because unordered_set uses a hash table instead of a sorted tree. The elements are stored based on their hash values, not their actual values. The big advantage is speed: looking up, inserting, or deleting an element takes O(1) time on average (constant time), compared to O(log n) for regular set. Use unordered_set when you need the fastest possible operations and don't care about the order of elements.
Unordered Map
unordered_map provides O(1) average-case key-value lookups using hashing.
It's the go-to choice when you need a fast dictionary and don't need sorted keys.
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
unordered_map<string, int> inventory;
// Add items - O(1) average
inventory["apples"] = 50;
inventory["bananas"] = 30;
inventory["oranges"] = 45;
// Fast lookup - O(1) average
cout << "Apples in stock: " << inventory["apples"] << endl;
// Check existence before access
if (inventory.find("grapes") == inventory.end()) {
cout << "Grapes not in inventory" << endl;
}
// Iterate (order not guaranteed)
cout << "\nInventory:\n";
for (const auto& item : inventory) {
cout << item.first << ": " << item.second << endl;
}
return 0;
}Unordered_map works exactly like map for storing key-value pairs, but it uses a hash table internally instead of a sorted tree. This means operations like adding items, finding items, and removing items all take O(1) time on average - that's constant time regardless of how many elements you have. The trade-off is that keys are not kept in any particular order. Use unordered_map when you need fast lookups and don't care about iterating through keys in sorted order. It's perfect for things like caches, lookup tables, counting occurrences, or storing user data by ID.
When to Use Unordered
- Speed is priority over order
- Frequent lookups, insertions, deletions
- Keys have good hash distribution
- No need to iterate in sorted order
When to Use Ordered
- Need elements in sorted order
- Need range queries (lower_bound, upper_bound)
- Custom sorting needed
- Keys don't have good hash function
Hash Table Internals
Understanding how unordered containers work helps you use them effectively:
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// Hash table statistics
cout << "Size: " << numbers.size() << endl;
cout << "Bucket count: " << numbers.bucket_count() << endl;
cout << "Load factor: " << numbers.load_factor() << endl;
cout << "Max load factor: " << numbers.max_load_factor() << endl;
// Show bucket distribution
cout << "\nBucket contents:\n";
for (size_t i = 0; i < numbers.bucket_count(); i++) {
cout << "Bucket " << i << ": ";
for (auto it = numbers.begin(i); it != numbers.end(i); ++it) {
cout << *it << " ";
}
cout << endl;
}
return 0;
}This code reveals what's happening inside a hash table. When you add an element, a hash function converts it into a number that determines which "bucket" it goes into. bucket_count() shows how many buckets exist, and you can see which elements landed in each bucket. The load_factor() is the ratio of elements to buckets - when this gets too high (above max_load_factor()), the table automatically resizes and redistributes elements to maintain fast performance. Understanding this helps you see why unordered containers are so fast: finding an element just requires computing its hash and checking one bucket.
Practice Questions: Unordered Containers
Task: Create an unordered_set with values {5, 2, 8, 1, 9}. Use insert() to add 3. Use count() to check if 5 and 10 exist. Use erase() to remove 2. Print the set and observe the non-sorted order. Also display bucket_count() and load_factor().
Show Solution
#include <iostream>
#include <unordered_set>
using namespace std;
void printSet(const unordered_set<int>& s) {
for (int x : s) cout << x << " ";
cout << endl;
}
int main() {
unordered_set<int> nums = {5, 2, 8, 1, 9};
cout << "Original unordered_set: ";
printSet(nums);
cout << "(Note: order is not sorted!)" << endl;
// Insert 3 - O(1) average
nums.insert(3);
cout << "\nAfter insert(3): ";
printSet(nums);
// Count - O(1) average
cout << "\nUsing count() for O(1) lookup:" << endl;
cout << " count(5): " << nums.count(5) << " (exists)" << endl;
cout << " count(10): " << nums.count(10) << " (not exists)" << endl;
// Erase - O(1) average
nums.erase(2);
cout << "\nAfter erase(2): ";
printSet(nums);
// Hash table statistics
cout << "\nHash table internals:" << endl;
cout << " Size: " << nums.size() << endl;
cout << " Bucket count: " << nums.bucket_count() << endl;
cout << " Load factor: " << nums.load_factor() << endl;
return 0;
}
// Output (order varies):
// Original unordered_set: 9 1 8 2 5
// (Note: order is not sorted!)
// After insert(3): 3 9 1 8 5
// Using count() for O(1) lookup:
// count(5): 1 (exists)
// count(10): 0 (not exists)
// After erase(2): 3 9 1 8 5
// Hash table internals:
// Size: 5
// Bucket count: 7
// Load factor: 0.714286Task: Create an unordered_map to store product names and prices. Add 4 products using both [] syntax and insert(). Use find() to safely access a product price. Iterate through the map and observe the non-sorted key order.
Show Solution
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
unordered_map<string, double> prices;
// Insert using [] syntax - O(1) average
prices["apple"] = 1.50;
prices["banana"] = 0.75;
// Insert using insert() - O(1) average
prices.insert({"orange", 2.00});
prices.insert(make_pair("grape", 3.50));
cout << "Product Prices (order not guaranteed):" << endl;
cout << "--------------------------------------" << endl;
for (const auto& p : prices) {
cout << p.first << ": $" << p.second << endl;
}
// Safe access using find()
cout << "\nSafe lookup with find():" << endl;
auto it = prices.find("apple");
if (it != prices.end()) {
cout << " Apple price: $" << it->second << endl;
}
it = prices.find("mango");
if (it == prices.end()) {
cout << " Mango not found" << endl;
}
cout << "\nTotal products: " << prices.size() << endl;
return 0;
}
// Output (order varies):
// Product Prices (order not guaranteed):
// --------------------------------------
// grape: $3.5
// orange: $2
// banana: $0.75
// apple: $1.5
// Safe lookup with find():
// Apple price: $1.5
// Mango not found
// Total products: 4Task: Use an unordered_map to count character frequencies in a string. For the string "hello world", display each character and its count. Use the [] operator to increment counts, and find() to safely check if a character exists before accessing.
Show Solution
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
string text = "hello world";
unordered_map<char, int> freq;
// Count frequencies using [] operator - O(1) per operation
for (char c : text) {
if (c != ' ') { // Skip spaces
freq[c]++;
}
}
// Display all frequencies
cout << "Character frequencies in \"" << text << "\":" << endl;
for (const auto& pair : freq) {
cout << " '" << pair.first << "': " << pair.second << endl;
}
// Safe lookup using find()
cout << "\nSafe lookup with find():" << endl;
auto it = freq.find('l');
if (it != freq.end()) {
cout << " 'l' found with count: " << it->second << endl;
}
it = freq.find('z');
if (it == freq.end()) {
cout << " 'z' not found (no entry created)" << endl;
}
// Show hash table efficiency
cout << "\nHash table stats:" << endl;
cout << " Unique characters: " << freq.size() << endl;
cout << " Bucket count: " << freq.bucket_count() << endl;
cout << " Load factor: " << freq.load_factor() << endl;
return 0;
}
// Output (order varies):
// Character frequencies in "hello world":
// 'd': 1
// 'r': 1
// 'w': 1
// 'o': 2
// 'l': 3
// 'e': 1
// 'h': 1
// Safe lookup with find():
// 'l' found with count: 3
// 'z' not found (no entry created)
// Hash table stats:
// Unique characters: 7
// Bucket count: 11
// Load factor: 0.636364Task: Create an unordered_set with 10 elements. Display bucket_count(), load_factor(), and max_load_factor(). Iterate through each bucket using begin(bucket_index) and end(bucket_index) to show the contents of each bucket. Use rehash() to change bucket count and observe the redistribution.
Show Solution
#include <iostream>
#include <unordered_set>
using namespace std;
void showBuckets(const unordered_set<int>& s) {
cout << "Bucket contents:" << endl;
for (size_t i = 0; i < s.bucket_count(); i++) {
cout << " Bucket " << i << ": ";
for (auto it = s.begin(i); it != s.end(i); ++it) {
cout << *it << " ";
}
cout << "(" << s.bucket_size(i) << " elements)" << endl;
}
}
int main() {
unordered_set<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
cout << "=== Initial State ===" << endl;
cout << "Size: " << nums.size() << endl;
cout << "Bucket count: " << nums.bucket_count() << endl;
cout << "Load factor: " << nums.load_factor() << endl;
cout << "Max load factor: " << nums.max_load_factor() << endl;
cout << endl;
showBuckets(nums);
// Rehash to different bucket count
cout << "\n=== After rehash(20) ===" << endl;
nums.rehash(20);
cout << "Bucket count: " << nums.bucket_count() << endl;
cout << "Load factor: " << nums.load_factor() << endl;
cout << endl;
showBuckets(nums);
// Find which bucket an element is in
cout << "\n=== Bucket lookup ===" << endl;
cout << "Element 5 is in bucket: " << nums.bucket(5) << endl;
cout << "Element 10 is in bucket: " << nums.bucket(10) << endl;
return 0;
}
// Output (buckets vary by implementation):
// === Initial State ===
// Size: 10
// Bucket count: 13
// Load factor: 0.769231
// Max load factor: 1
// Bucket contents:
// Bucket 0: (0 elements)
// Bucket 1: 1 (1 elements)
// Bucket 2: 2 (1 elements)
// ...
// === After rehash(20) ===
// Bucket count: 23
// Load factor: 0.434783
// ...Container Adapters
Container adapters provide a different interface to underlying containers. They restrict operations to enforce specific access patterns like LIFO (stack) or FIFO (queue).
Stack - Last In, First Out (LIFO)
stack allows access only to the top element. Elements are added and removed
from the same end, like a stack of plates.
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
// Push elements onto stack
s.push(10);
s.push(20);
s.push(30);
cout << "Top element: " << s.top() << endl; // 30
cout << "Size: " << s.size() << endl; // 3
// Pop elements (LIFO order)
while (!s.empty()) {
cout << s.top() << " "; // 30 20 10
s.pop();
}
cout << endl;
return 0;
}Stack follows the Last-In-First-Out (LIFO) principle, just like a stack of plates in a cafeteria. You can only interact with the top: push() adds an element on top, pop() removes the top element, and top() lets you see the top element without removing it. In this example, we push 10, then 20, then 30, so 30 is on top. When we pop elements, they come out in reverse order: 30 first, then 20, then 10. Stack is useful for undo operations, parsing expressions, and managing function calls.
Practical example - matching parentheses:
#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool isBalanced(const string& expr) {
stack<char> s;
for (char c : expr) {
if (c == '(' || c == '[' || c == '{') {
s.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (s.empty()) return false;
char top = s.top();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
s.pop();
}
}
return s.empty();
}
int main() {
cout << isBalanced("((a+b)*c)") << endl; // 1 (true)
cout << isBalanced("{[()]}") << endl; // 1 (true)
cout << isBalanced("([)]") << endl; // 0 (false)
cout << isBalanced("((())") << endl; // 0 (false)
return 0;
}This is a classic programming interview question that demonstrates the power of stacks. The algorithm works like this: when you encounter an opening bracket ((, [, or {), push it onto the stack. When you encounter a closing bracket, check if it matches the bracket on top of the stack. If it matches, pop the stack and continue. If it doesn't match, or if the stack is empty when you see a closing bracket, the expression is unbalanced. At the end, the stack should be empty if all brackets were properly matched. This pattern is used in compilers, text editors, and calculators.
Queue - First In, First Out (FIFO)
queue adds elements at the back and removes from the front, like a line of
people waiting. Perfect for processing tasks in order.
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
queue<string> printQueue;
// Add print jobs
printQueue.push("document1.pdf");
printQueue.push("photo.jpg");
printQueue.push("report.docx");
cout << "Front of queue: " << printQueue.front() << endl; // document1.pdf
cout << "Back of queue: " << printQueue.back() << endl; // report.docx
// Process jobs (FIFO order)
cout << "\nProcessing print jobs:\n";
while (!printQueue.empty()) {
cout << "Printing: " << printQueue.front() << endl;
printQueue.pop();
}
return 0;
}Queue follows the First-In-First-Out (FIFO) principle, just like a line of people waiting at a store - the first person in line gets served first. push() adds an element to the back of the queue, while pop() removes the element from the front. You can peek at both ends: front() shows the next element to be removed, and back() shows the most recently added element. In this print queue example, documents are processed in the order they were added. Queues are used for task scheduling, breadth-first search, and handling requests in order.
Priority Queue - Highest Priority First
priority_queue always gives access to the highest priority element (largest by
default). It's implemented as a heap and is perfect for scheduling or finding max/min elements.
#include <iostream>
#include <queue>
using namespace std;
int main() {
// Max heap by default (largest first)
priority_queue<int> maxHeap;
maxHeap.push(30);
maxHeap.push(10);
maxHeap.push(50);
maxHeap.push(20);
cout << "Max heap (descending): ";
while (!maxHeap.empty()) {
cout << maxHeap.top() << " "; // 50 30 20 10
maxHeap.pop();
}
cout << endl;
return 0;
}Priority queue is like a VIP line where the most important person always goes first, regardless of when they arrived. By default in C++, it's a max heap, meaning the largest element is always at the top. When you call top(), you get the maximum value. When you call pop(), it removes the maximum and the next-largest becomes the new top. In this example, even though we pushed 30, 10, 50, 20, they come out as 50, 30, 20, 10. Priority queues are commonly used for task scheduling, finding top-k elements, and implementing algorithms like Dijkstra's shortest path.
Creating a min heap (smallest first):
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
// Min heap using greater<int>
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(30);
minHeap.push(10);
minHeap.push(50);
minHeap.push(20);
cout << "Min heap (ascending): ";
while (!minHeap.empty()) {
cout << minHeap.top() << " "; // 10 20 30 50
minHeap.pop();
}
cout << endl;
return 0;
}Sometimes you need the smallest element first instead of the largest. To create a min heap, you need to specify three template parameters: the element type, the underlying container (vector), and the comparison function (greater<int>). The syntax priority_queue<int, vector<int>, greater<int>> might look complicated, but it's a pattern you can memorize. Now top() returns the smallest element, and elements come out in ascending order: 10, 20, 30, 50. Min heaps are useful for finding the k smallest elements, merging sorted lists, and scheduling based on earliest deadline.
Priority queue with custom objects:
#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct Task {
int priority;
string name;
// For max heap, higher priority = greater
bool operator<(const Task& other) const {
return priority < other.priority;
}
};
int main() {
priority_queue<Task> taskQueue;
taskQueue.push({3, "Low priority task"});
taskQueue.push({1, "Critical task"});
taskQueue.push({5, "Normal task"});
taskQueue.push({2, "High priority task"});
cout << "Processing tasks by priority:\n";
while (!taskQueue.empty()) {
Task t = taskQueue.top();
cout << "[" << t.priority << "] " << t.name << endl;
taskQueue.pop();
}
return 0;
}
// Output:
// [5] Normal task
// [3] Low priority task
// [2] High priority task
// [1] Critical taskTo use priority_queue with your own classes or structs, you need to tell C++ how to compare two objects by overloading the < operator. In this Task struct, we define that a task is "less than" another if its priority number is lower. Since priority_queue is a max heap by default, it puts the "greater" tasks (higher priority numbers) at the top. So tasks with priority 5 come before tasks with priority 1. This pattern is incredibly useful for task schedulers, game AI decision-making, event handling systems, or any application where different items have different levels of importance.
Practice Questions: Container Adapters
Task: Create a stack of integers. Use push() to add 10, 20, and 30. Use top() to view the top element. Use pop() to remove elements one by one and print each before removal. Use empty() and size() to check the stack state.
Show Solution
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
// Push elements
s.push(10);
s.push(20);
s.push(30);
cout << "After pushing 10, 20, 30:" << endl;
cout << " Size: " << s.size() << endl;
cout << " Top element: " << s.top() << endl;
cout << " Empty? " << (s.empty() ? "Yes" : "No") << endl;
// Pop elements and show LIFO order
cout << "\nPopping elements (LIFO order):" << endl;
while (!s.empty()) {
cout << " Top: " << s.top();
s.pop();
cout << " -> Popped. Size now: " << s.size() << endl;
}
cout << "\nAfter all pops:" << endl;
cout << " Size: " << s.size() << endl;
cout << " Empty? " << (s.empty() ? "Yes" : "No") << endl;
return 0;
}
// Output:
// After pushing 10, 20, 30:
// Size: 3
// Top element: 30
// Empty? No
// Popping elements (LIFO order):
// Top: 30 -> Popped. Size now: 2
// Top: 20 -> Popped. Size now: 1
// Top: 10 -> Popped. Size now: 0
// After all pops:
// Size: 0
// Empty? YesTask: Create a queue of strings simulating a print job queue. Use push() to add 3 documents. Use front() and back() to view both ends of the queue. Use pop() to process jobs and demonstrate the FIFO (First In, First Out) order.
Show Solution
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
queue<string> printQueue;
// Add print jobs
printQueue.push("report.pdf");
printQueue.push("photo.jpg");
printQueue.push("letter.docx");
cout << "Print Queue Status:" << endl;
cout << " Size: " << printQueue.size() << endl;
cout << " Front (next to print): " << printQueue.front() << endl;
cout << " Back (last added): " << printQueue.back() << endl;
cout << " Empty? " << (printQueue.empty() ? "Yes" : "No") << endl;
// Process jobs in FIFO order
cout << "\nProcessing print jobs (FIFO order):" << endl;
int jobNum = 1;
while (!printQueue.empty()) {
cout << " Job " << jobNum++ << ": Printing " << printQueue.front();
printQueue.pop();
cout << " -> Done. Remaining: " << printQueue.size() << endl;
}
cout << "\nAll jobs completed!" << endl;
cout << " Empty? " << (printQueue.empty() ? "Yes" : "No") << endl;
return 0;
}
// Output:
// Print Queue Status:
// Size: 3
// Front (next to print): report.pdf
// Back (last added): letter.docx
// Empty? No
// Processing print jobs (FIFO order):
// Job 1: Printing report.pdf -> Done. Remaining: 2
// Job 2: Printing photo.jpg -> Done. Remaining: 1
// Job 3: Printing letter.docx -> Done. Remaining: 0
// All jobs completed!
// Empty? YesTask: Create both a max heap and min heap with values {30, 10, 50, 20, 40}. Use push() to add elements, top() to view the highest priority element, and pop() to remove elements. Show the different output order between max heap (default) and min heap (using greater<int>).
Show Solution
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
// Max heap - default priority_queue
priority_queue<int> maxHeap;
// Min heap - using greater<int>
priority_queue<int, vector<int>, greater<int>> minHeap;
// Add same elements to both
int values[] = {30, 10, 50, 20, 40};
cout << "Adding values: ";
for (int v : values) {
cout << v << " ";
maxHeap.push(v);
minHeap.push(v);
}
cout << endl;
// Show max heap behavior
cout << "\nMax Heap (largest first):" << endl;
cout << " Initial top: " << maxHeap.top() << endl;
cout << " Popping all: ";
while (!maxHeap.empty()) {
cout << maxHeap.top() << " ";
maxHeap.pop();
}
cout << endl;
// Show min heap behavior
cout << "\nMin Heap (smallest first):" << endl;
cout << " Initial top: " << minHeap.top() << endl;
cout << " Popping all: ";
while (!minHeap.empty()) {
cout << minHeap.top() << " ";
minHeap.pop();
}
cout << endl;
return 0;
}
// Output:
// Adding values: 30 10 50 20 40
// Max Heap (largest first):
// Initial top: 50
// Popping all: 50 40 30 20 10
// Min Heap (smallest first):
// Initial top: 10
// Popping all: 10 20 30 40 50Task: Create a Task struct with priority (int) and name (string) fields. Overload the < operator so higher priority tasks come first. Add 4 tasks with different priorities to a priority_queue and process them in priority order.
Show Solution
#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct Task {
int priority;
string name;
// Higher priority = "greater", so it comes first in max heap
bool operator<(const Task& other) const {
return priority < other.priority;
}
};
int main() {
priority_queue<Task> taskQueue;
// Add tasks with different priorities
taskQueue.push({3, "Write documentation"});
taskQueue.push({5, "Fix critical bug"});
taskQueue.push({1, "Update README"});
taskQueue.push({4, "Code review"});
cout << "Task Queue (higher priority = more urgent):" << endl;
cout << "--------------------------------------------" << endl;
cout << "Next task (top): [" << taskQueue.top().priority << "] "
<< taskQueue.top().name << endl;
// Process tasks by priority
cout << "\nProcessing tasks in priority order:" << endl;
int order = 1;
while (!taskQueue.empty()) {
Task t = taskQueue.top();
cout << " " << order++ << ". [Priority " << t.priority << "] "
<< t.name << endl;
taskQueue.pop();
}
return 0;
}
// Output:
// Task Queue (higher priority = more urgent):
// --------------------------------------------
// Next task (top): [5] Fix critical bug
// Processing tasks in priority order:
// 1. [Priority 5] Fix critical bug
// 2. [Priority 4] Code review
// 3. [Priority 3] Write documentation
// 4. [Priority 1] Update READMEChoosing the Right Container
Choosing the right container is crucial for performance. The best choice depends on what operations you need most frequently and the characteristics of your data.
Time Complexity Comparison
| Container | Access | Search | Insert | Delete |
|---|---|---|---|---|
vector |
O(1) | O(n) | O(n)* | O(n)* |
list |
O(n) | O(n) | O(1)** | O(1)** |
deque |
O(1) | O(n) | O(1)*** | O(1)*** |
set/map |
O(log n) | O(log n) | O(log n) | O(log n) |
unordered_set/map |
O(1) | O(1) | O(1) | O(1) |
Decision Guide
- You need random access by index
- Most insertions/deletions are at the end
- You iterate through elements frequently
- You need cache-friendly memory layout
- Default choice - use unless you have a reason not to
- Frequent insertions/deletions in the middle
- You need to splice lists together
- Iterator stability is required (iterators stay valid)
- You don't need random access
- You need elements sorted automatically
- You need range queries (lower_bound, upper_bound)
- You need O(log n) guaranteed performance
- Keys must be unique (or use multi- variants)
- You need fastest possible lookup
- Order doesn't matter
- You have a good hash function
- Average-case performance is acceptable
vector. Switch to another container only
if profiling shows it's a bottleneck and another container would help.
Practice Questions: Choosing Containers
Task: Write code demonstrating the best container choice for three scenarios: (1) Store top 100 scores that need fast random access, (2) Track unique visitor IPs with fastest lookup, (3) Maintain a sorted list of student names. For each, explain why you chose that container.
Show Solution
#include <iostream>
#include <vector>
#include <unordered_set>
#include <set>
#include <string>
using namespace std;
int main() {
// Scenario 1: Top 100 scores - need random access
// BEST: vector - O(1) random access, contiguous memory
cout << "=== Scenario 1: Top Scores ===" << endl;
cout << "Container: vector (fast random access)" << endl;
vector<int> topScores = {95, 87, 92, 78, 88};
cout << "Score at index 2: " << topScores[2] << endl;
cout << "Why vector? Need to access any score by position quickly.\n" << endl;
// Scenario 2: Track unique visitor IPs - fastest lookup
// BEST: unordered_set - O(1) average lookup
cout << "=== Scenario 2: Unique Visitors ===" << endl;
cout << "Container: unordered_set (O(1) lookup)" << endl;
unordered_set<string> visitors;
visitors.insert("192.168.1.1");
visitors.insert("10.0.0.5");
visitors.insert("192.168.1.1"); // Duplicate ignored
string checkIP = "10.0.0.5";
if (visitors.count(checkIP)) {
cout << checkIP << " visited before (O(1) check)" << endl;
}
cout << "Unique visitors: " << visitors.size() << endl;
cout << "Why unordered_set? Fastest lookup, auto-removes duplicates.\n" << endl;
// Scenario 3: Sorted student names
// BEST: set - automatically sorted, unique names
cout << "=== Scenario 3: Sorted Students ===" << endl;
cout << "Container: set (auto-sorted)" << endl;
set<string> students;
students.insert("Charlie");
students.insert("Alice");
students.insert("Bob");
cout << "Students (sorted): ";
for (const string& name : students) {
cout << name << " ";
}
cout << endl;
cout << "Why set? Need sorted order automatically maintained." << endl;
return 0;
}
// Output:
// === Scenario 1: Top Scores ===
// Container: vector (fast random access)
// Score at index 2: 92
// Why vector? Need to access any score by position quickly.
//
// === Scenario 2: Unique Visitors ===
// Container: unordered_set (O(1) lookup)
// 10.0.0.5 visited before (O(1) check)
// Unique visitors: 2
// Why unordered_set? Fastest lookup, auto-removes duplicates.
//
// === Scenario 3: Sorted Students ===
// Container: set (auto-sorted)
// Students (sorted): Alice Bob Charlie
// Why set? Need sorted order automatically maintained.Task: Create a function that recommends a container based on user requirements. Ask about: (1) Need random access? (2) Need sorted order? (3) Need unique values? (4) Frequent insertions in middle? Print the recommended container with reasoning.
Show Solution
#include <iostream>
#include <string>
using namespace std;
string recommendContainer(bool randomAccess, bool sorted,
bool unique, bool middleInserts) {
cout << "\nAnalyzing requirements:" << endl;
cout << " Random access needed: " << (randomAccess ? "Yes" : "No") << endl;
cout << " Sorted order needed: " << (sorted ? "Yes" : "No") << endl;
cout << " Unique values only: " << (unique ? "Yes" : "No") << endl;
cout << " Frequent middle inserts: " << (middleInserts ? "Yes" : "No") << endl;
if (middleInserts && !randomAccess) {
return "list - O(1) middle insertions, no random access needed";
}
if (unique && sorted) {
return "set - auto-sorted, ensures uniqueness, O(log n) operations";
}
if (unique && !sorted) {
return "unordered_set - fastest O(1) lookup, ensures uniqueness";
}
if (sorted && !unique) {
return "multiset - allows duplicates, keeps sorted order";
}
if (randomAccess) {
return "vector - O(1) random access, cache-friendly, default choice";
}
return "vector - default choice for most scenarios";
}
int main() {
cout << "=== Container Recommendation System ===" << endl;
// Scenario 1: Need fast lookup for unique IDs
cout << "\n--- Scenario 1: Fast lookup for unique IDs ---";
cout << "\nRecommendation: "
<< recommendContainer(false, false, true, false) << endl;
// Scenario 2: Sorted leaderboard
cout << "\n--- Scenario 2: Sorted leaderboard ---";
cout << "\nRecommendation: "
<< recommendContainer(false, true, true, false) << endl;
// Scenario 3: Text editor buffer
cout << "\n--- Scenario 3: Text editor buffer ---";
cout << "\nRecommendation: "
<< recommendContainer(false, false, false, true) << endl;
// Scenario 4: Array of game objects
cout << "\n--- Scenario 4: Game objects with index access ---";
cout << "\nRecommendation: "
<< recommendContainer(true, false, false, false) << endl;
return 0;
}
// Output:
// === Container Recommendation System ===
// --- Scenario 1: Fast lookup for unique IDs ---
// Recommendation: unordered_set - fastest O(1) lookup, ensures uniqueness
// --- Scenario 2: Sorted leaderboard ---
// Recommendation: set - auto-sorted, ensures uniqueness, O(log n) operations
// --- Scenario 3: Text editor buffer ---
// Recommendation: list - O(1) middle insertions, no random access needed
// --- Scenario 4: Game objects with index access ---
// Recommendation: vector - O(1) random access, cache-friendly, default choiceTask: Compare the performance of vector search (O(n)), set search (O(log n)), and unordered_set search (O(1)) by searching for an element in containers with 10,000 elements. Use <chrono> to measure and display the time taken for each.
Show Solution
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <chrono>
using namespace std;
using namespace chrono;
int main() {
const int SIZE = 10000;
const int SEARCHES = 1000;
const int TARGET = 9999; // Worst case for vector
// Create containers with same data
vector<int> vec;
set<int> s;
unordered_set<int> us;
for (int i = 0; i < SIZE; i++) {
vec.push_back(i);
s.insert(i);
us.insert(i);
}
cout << "Searching for " << TARGET << " in " << SIZE << " elements" << endl;
cout << "Running " << SEARCHES << " searches each...\n" << endl;
// Vector search - O(n)
auto start = high_resolution_clock::now();
for (int i = 0; i < SEARCHES; i++) {
find(vec.begin(), vec.end(), TARGET);
}
auto end = high_resolution_clock::now();
auto vecTime = duration_cast<microseconds>(end - start).count();
cout << "vector (O(n) search): " << vecTime << " microseconds" << endl;
// Set search - O(log n)
start = high_resolution_clock::now();
for (int i = 0; i < SEARCHES; i++) {
s.find(TARGET);
}
end = high_resolution_clock::now();
auto setTime = duration_cast<microseconds>(end - start).count();
cout << "set (O(log n) search): " << setTime << " microseconds" << endl;
// Unordered_set search - O(1)
start = high_resolution_clock::now();
for (int i = 0; i < SEARCHES; i++) {
us.find(TARGET);
}
end = high_resolution_clock::now();
auto usTime = duration_cast<microseconds>(end - start).count();
cout << "unordered_set (O(1) search): " << usTime << " microseconds" << endl;
// Show speedup comparison
cout << "\nSpeedup comparison:" << endl;
cout << " vector is " << (vecTime / (double)setTime) << "x slower than set" << endl;
cout << " vector is " << (vecTime / (double)usTime) << "x slower than unordered_set" << endl;
cout << " set is " << (setTime / (double)usTime) << "x slower than unordered_set" << endl;
return 0;
}
// Output (times will vary):
// Searching for 9999 in 10000 elements
// Running 1000 searches each...
//
// vector (O(n) search): 45000 microseconds
// set (O(log n) search): 150 microseconds
// unordered_set (O(1) search): 25 microseconds
//
// Speedup comparison:
// vector is 300x slower than set
// vector is 1800x slower than unordered_set
// set is 6x slower than unordered_setTask: Compare the performance of middle insertions between vector (O(n)) and list (O(1)). Insert 1000 elements at the middle position of each container. Use <chrono> to measure time and demonstrate when list outperforms vector.
Show Solution
#include <iostream>
#include <vector>
#include <list>
#include <chrono>
using namespace std;
using namespace chrono;
int main() {
const int INSERTIONS = 1000;
cout << "Comparing middle insertions: vector vs list" << endl;
cout << "Inserting " << INSERTIONS << " elements at middle position\n" << endl;
// Vector middle insertions - O(n) each
vector<int> vec;
auto start = high_resolution_clock::now();
for (int i = 0; i < INSERTIONS; i++) {
auto mid = vec.begin() + vec.size() / 2;
vec.insert(mid, i);
}
auto end = high_resolution_clock::now();
auto vecTime = duration_cast<microseconds>(end - start).count();
cout << "vector middle insert: " << vecTime << " microseconds" << endl;
cout << " Final size: " << vec.size() << endl;
// List middle insertions - O(1) each (after finding position)
list<int> lst;
start = high_resolution_clock::now();
for (int i = 0; i < INSERTIONS; i++) {
auto mid = lst.begin();
advance(mid, lst.size() / 2);
lst.insert(mid, i);
}
end = high_resolution_clock::now();
auto lstTime = duration_cast<microseconds>(end - start).count();
cout << "\nlist middle insert: " << lstTime << " microseconds" << endl;
cout << " Final size: " << lst.size() << endl;
// Compare
cout << "\n=== Analysis ===" << endl;
if (vecTime > lstTime) {
cout << "list is " << (vecTime / (double)lstTime) << "x faster" << endl;
cout << "Reason: list has O(1) insertion once position found," << endl;
cout << " vector must shift O(n) elements on each insert." << endl;
} else {
cout << "vector is " << (lstTime / (double)vecTime) << "x faster" << endl;
cout << "Note: For small sizes, vector's cache efficiency can win." << endl;
}
cout << "\nKey insight: Use list when you have an iterator" << endl;
cout << "and need many insertions at that position." << endl;
return 0;
}
// Output (times vary):
// Comparing middle insertions: vector vs list
// Inserting 1000 elements at middle position
//
// vector middle insert: 2500 microseconds
// Final size: 1000
//
// list middle insert: 850 microseconds
// Final size: 1000
//
// === Analysis ===
// list is 2.94x faster
// Reason: list has O(1) insertion once position found,
// vector must shift O(n) elements on each insert.Key Takeaways
Vector is Default
Use vector as your default container. It offers O(1) random access and excellent cache performance.
Sorted vs Hash
Use set/map for sorted data and range queries. Use unordered_set/map for fastest lookups.
Stack and Queue
stack for LIFO, queue for FIFO, priority_queue for highest priority first.
List for Insertions
Use list when you need frequent insertions/deletions in the middle and don't need random access.
Know Complexities
Understand time complexity tradeoffs. The right container can make algorithms significantly faster.
Memory Matters
Contiguous memory (vector) has better cache performance than scattered memory (list, map).
Knowledge Check
Test your understanding of C++ STL Containers:
Which container provides O(1) random access and is best for adding elements at the end?
What is the main difference between map and unordered_map?
Which container adapter follows LIFO (Last In, First Out) order?
What happens when you insert a duplicate element into a set?
Which container should you use for frequent insertions in the middle of a sequence?
What is the default ordering of priority_queue in C++?