The STL: Your C++ Swiss Army Knife

What is the STL?

The Standard Template Library is like a well-equipped kitchen - it has all the tools (containers), techniques (algorithms), and helpers (iterators) you need to cook up any program efficiently!

STL Containers: Data Storage Solutions

STL containers are like different types of storage boxes - each designed for specific needs!

Vector: The Workhorse Container

Vector is like a stretchy array - it grows as needed but keeps everything in a neat line!

Vector Examples

#include 
#include 
#include 
using namespace std;

int main() {
    // Creating and initializing vectors
    vector v1;                      // Empty vector
    vector v2(5);                   // 5 elements, default initialized
    vector v3(5, 10);              // 5 elements, all set to 10
    vector v4 = {1, 2, 3, 4, 5};   // Initializer list
    
    // Adding elements
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    
    // Accessing elements
    cout << "First: " << v1[0] << endl;           // No bounds check
    cout << "Second: " << v1.at(1) << endl;       // With bounds check
    cout << "Last: " << v1.back() << endl;
    
    // Size and capacity
    cout << "Size: " << v1.size() << endl;
    cout << "Capacity: " << v1.capacity() << endl;
    v1.reserve(100);  // Reserve space for 100 elements
    
    // Iterating
    for (int val : v1) {
        cout << val << " ";
    }
    
    // Using iterators
    for (auto it = v1.begin(); it != v1.end(); ++it) {
        *it *= 2;  // Double each element
    }
    
    // Algorithms
    sort(v4.begin(), v4.end());                    // Sort ascending
    sort(v4.rbegin(), v4.rend());                 // Sort descending
    
    auto it = find(v4.begin(), v4.end(), 3);      // Find element
    if (it != v4.end()) {
        cout << "Found at position: " << distance(v4.begin(), it) << endl;
    }
    
    // Removing elements
    v4.pop_back();                                 // Remove last
    v4.erase(v4.begin() + 2);                     // Remove at index 2
    v4.erase(remove(v4.begin(), v4.end(), 3), v4.end()); // Remove all 3s
    
    return 0;
}

Container Comparison

Choosing the right container is like picking the right tool for the job!

Maps and Sets: Associative Containers

Maps are like dictionaries - look up values by key. Sets are like exclusive clubs - each member is unique!

Map and Set Examples

// Map example - Phone book
map phoneBook;

// Insert methods
phoneBook["Alice"] = "555-1234";
phoneBook.insert({"Bob", "555-5678"});
phoneBook.insert(make_pair("Charlie", "555-9012"));

// Access and check
if (phoneBook.find("Alice") != phoneBook.end()) {
    cout << "Alice's number: " << phoneBook["Alice"] << endl;
}

// Safe access with at()
try {
    cout << phoneBook.at("David") << endl;  // Throws if not found
} catch (const out_of_range& e) {
    cout << "David not found" << endl;
}

// Iterate over map (sorted by key)
for (const auto& [name, number] : phoneBook) {
    cout << name << ": " << number << endl;
}

// Set example - Unique values
set uniqueNumbers = {5, 2, 8, 2, 9, 1, 5};  // Duplicates removed
cout << "Set size: " << uniqueNumbers.size() << endl;  // 5

// Set operations
uniqueNumbers.insert(3);
uniqueNumbers.erase(2);

// Check if exists
if (uniqueNumbers.count(5) > 0) {
    cout << "5 is in the set" << endl;
}

// Multiset - allows duplicates
multiset scores = {85, 90, 85, 75, 90, 85};
cout << "Count of 85: " << scores.count(85) << endl;  // 3

// Unordered map - Hash table
unordered_map wordCount;
string text = "the quick brown fox jumps over the lazy dog";
stringstream ss(text);
string word;
while (ss >> word) {
    wordCount[word]++;
}

// Custom comparator for set
struct Person {
    string name;
    int age;
};

auto compareByAge = [](const Person& a, const Person& b) {
    return a.age < b.age;
};

set people(compareByAge);
people.insert({"Alice", 30});
people.insert({"Bob", 25});
people.insert({"Charlie", 35});

STL Algorithms: Ready-Made Solutions

STL algorithms are like kitchen appliances - they do common tasks efficiently so you don't have to reinvent the wheel!

Algorithm Examples

vector nums = {5, 2, 8, 1, 9, 3, 7, 4, 6};

// Sorting algorithms
sort(nums.begin(), nums.end());                    // Ascending
sort(nums.begin(), nums.end(), greater());   // Descending

// Partial sort - only first 3 elements sorted
partial_sort(nums.begin(), nums.begin() + 3, nums.end());

// Find algorithms
auto it = find(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
    cout << "Found 5 at position " << distance(nums.begin(), it) << endl;
}

// Find first even number
auto even = find_if(nums.begin(), nums.end(), 
    [](int n) { return n % 2 == 0; });

// Count algorithms
int count5 = count(nums.begin(), nums.end(), 5);
int evens = count_if(nums.begin(), nums.end(), 
    [](int n) { return n % 2 == 0; });

// Transform algorithm
vector doubled;
transform(nums.begin(), nums.end(), back_inserter(doubled),
    [](int n) { return n * 2; });

// Accumulate (sum)
int sum = accumulate(nums.begin(), nums.end(), 0);
int product = accumulate(nums.begin(), nums.end(), 1, multiplies());

// Copy with condition
vector evensOnly;
copy_if(nums.begin(), nums.end(), back_inserter(evensOnly),
    [](int n) { return n % 2 == 0; });

// Remove elements (erase-remove idiom)
nums.erase(remove_if(nums.begin(), nums.end(),
    [](int n) { return n < 5; }), nums.end());

// Binary search (requires sorted container)
sort(nums.begin(), nums.end());
bool found = binary_search(nums.begin(), nums.end(), 5);

// Min/Max algorithms
auto minmax = minmax_element(nums.begin(), nums.end());
cout << "Min: " << *minmax.first << ", Max: " << *minmax.second << endl;

// Permutations
vector perm = {1, 2, 3};
do {
    for (int n : perm) cout << n << " ";
    cout << endl;
} while (next_permutation(perm.begin(), perm.end()));

Iterators: The Bridge Between Containers and Algorithms

Iterators are like cursors or pointers that know how to navigate through containers - they're the universal remote control for STL!

Iterator Usage

// Basic iterator usage
vector v = {1, 2, 3, 4, 5};

// Iterator types
vector::iterator it = v.begin();
vector::const_iterator cit = v.cbegin();
vector::reverse_iterator rit = v.rbegin();

// Traversing with iterators
for (auto it = v.begin(); it != v.end(); ++it) {
    *it *= 2;  // Double each element
}

// Const iterator (read-only)
for (auto cit = v.cbegin(); cit != v.cend(); ++cit) {
    cout << *cit << " ";  // Can't modify through const_iterator
}

// Reverse iteration
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
    cout << *rit << " ";  // Prints in reverse order
}

// Iterator arithmetic (random access only)
auto it1 = v.begin();
auto it2 = it1 + 3;  // Jump to 4th element
int distance = it2 - it1;  // 3

// Iterator with algorithms
sort(v.begin(), v.end());
auto pos = find(v.begin(), v.end(), 3);
if (pos != v.end()) {
    v.erase(pos);  // Remove the found element
}

// Insert iterator adapters
vector src = {1, 2, 3};
vector dest;

// Back inserter
copy(src.begin(), src.end(), back_inserter(dest));

// Front inserter (for deque/list)
deque d;
copy(src.begin(), src.end(), front_inserter(d));

// Insert at specific position
vector v2 = {10, 20, 30};
copy(src.begin(), src.end(), inserter(v2, v2.begin() + 1));

Container Adapters: Specialized Interfaces

Container adapters are like specialized tools built on top of basic containers - they provide a specific interface for specific needs!

Container Adapter Examples

// Stack - LIFO (Last In, First Out)
stack s;
s.push(10);
s.push(20);
s.push(30);

while (!s.empty()) {
    cout << s.top() << " ";  // 30 20 10
    s.pop();
}

// Queue - FIFO (First In, First Out)
queue q;
q.push("First");
q.push("Second");
q.push("Third");

while (!q.empty()) {
    cout << q.front() << " ";  // First Second Third
    q.pop();
}

// Priority Queue - Heap
priority_queue pq;  // Max heap by default
pq.push(10);
pq.push(30);
pq.push(20);

while (!pq.empty()) {
    cout << pq.top() << " ";  // 30 20 10
    pq.pop();
}

// Min heap
priority_queue, greater> minHeap;
minHeap.push(10);
minHeap.push(30);
minHeap.push(20);

// Custom comparator
struct Task {
    string name;
    int priority;
};

auto taskCompare = [](const Task& a, const Task& b) {
    return a.priority < b.priority;  // Higher priority first
};

priority_queue, decltype(taskCompare)> tasks(taskCompare);
tasks.push({"Low priority", 1});
tasks.push({"High priority", 10});
tasks.push({"Medium priority", 5});

Practice Exercise: Student Management System

struct Student {
    int id;
    string name;
    vector grades;
    
    double getAverage() const {
        // TODO: Calculate average grade
    }
};

class StudentManager {
private:
    map studentsById;
    multimap studentsByName;
    
public:
    void addStudent(const Student& student);
    void removeStudent(int id);
    Student* findStudent(int id);
    vector findStudentsByName(const string& name);
    
    void printReport(/* sorting criteria */);
    double getClassAverage();
    
    // TODO: Implement methods using STL algorithms
};

STL Performance Tips

Modern STL Features

// C++11: Auto and range-based for
auto numbers = vector{1, 2, 3, 4, 5};
for (const auto& num : numbers) {
    cout << num << " ";
}

// C++11: Initializer lists
map ages = {
    {"Alice", 30},
    {"Bob", 25},
    {"Charlie", 35}
};

// C++11: Emplace methods (construct in-place)
vector> people;
people.emplace_back("David", 28);  // More efficient than push_back

// C++14: Generic lambdas
auto print = [](const auto& container) {
    for (const auto& elem : container) {
        cout << elem << " ";
    }
};

// C++17: Structured bindings
for (const auto& [name, age] : ages) {
    cout << name << " is " << age << " years old\n";
}

// C++17: Optional
optional findValue(const vector& v, int target) {
    auto it = find(v.begin(), v.end(), target);
    if (it != v.end()) {
        return *it;
    }
    return nullopt;
}

// C++20: Ranges (preview)
// vector evens = numbers | views::filter([](int n) { return n % 2 == 0; })
//                            | views::transform([](int n) { return n * 2; });

Challenge Exercise: Text Analysis Engine

Key Takeaways

• STL provides efficient, tested implementations of common data structures
• Containers store data with different performance characteristics
• Algorithms work on any container through iterators
• Iterators provide a uniform interface to traverse containers
• vector should be your default container choice
• map/set for sorted data and logarithmic lookups
• unordered_map/set for constant-time average lookups
• Choose wisely based on your performance needs
• Prefer algorithms over hand-written loops