Standard Template Library (STL)

# CHAPTER 22

Standard Template Library (STL) #

1. Introduction #

2. Learning Objectives #

• Understand the three core components of the STL: Containers, Iterators, and Algorithms.

• Use std::vector for dynamic arrays.

• Use std::map and std::set for associative data.

• Navigate containers using Iterators.

• Apply STL Algorithms like sort().

3. Core Components of STL #

1. 1. Containers: Objects that store data (e.g., Vector, List, Map).

1. 2. Algorithms: Functions that process data (e.g., sort, search, reverse).

1. 3. Iterators: Special pointers used to navigate through Containers safely.

4. Vector (Dynamic Array) #

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

int main() {
    vector<int> scores; // Creates an empty dynamic array of integers
    
    // Add elements to the END of the vector
    scores.push_back(100);
    scores.push_back(85);
    scores.push_back(95);
    
    // Access like a normal array
    cout << "First score: " << scores[0] << endl;
    
    // Get current size
    cout << "Total elements: " << scores.size() << endl;
    
    // Remove the last element
    scores.pop_back(); 
    
    return 0;
}

5. Iterators #

vector<string> names = {"Alice", "Bob", "Charlie"};

// Traditional iterator syntax
vector<string>::iterator it;
for (it = names.begin(); it != names.end(); it++) {
    cout << *it << " "; // Dereference iterator to get value
}

// MODERN C++ WAY (Much cleaner using 'auto' and range-based for loop)
for (auto name : names) {
    cout << name << " ";
}

6. Map (Key-Value Pairs) #

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

int main() {
    map<string, int> ages; // Key is string, Value is int
    
    ages["Alice"] = 25;
    ages["Bob"] = 30;
    
    cout << "Bob is " << ages["Bob"] << " years old." << endl;
    
    // Iterating through a map
    for (auto pair : ages) {
        cout << pair.first << " is " << pair.second << endl; 
        // pair.first is the Key, pair.second is the Value
    }
    return 0;
}

7. Set (Unique Elements) #

#include <set>
// ...
set<int> numbers;
numbers.insert(10);
numbers.insert(5);
numbers.insert(10); // Ignored! 10 is already in the set.

// Prints: 5 10 (Automatically sorted and duplicates removed)

8. STL Algorithms #

#include <iostream>
#include <vector>
#include <algorithm> // Required for sort()
using namespace std;

int main() {
    vector<int> v = {50, 10, 30, 20, 40};
    
    // Sort ascending
    sort(v.begin(), v.end()); 
    // v is now: 10, 20, 30, 40, 50
    
    // Reverse the vector
    reverse(v.begin(), v.end());
    // v is now: 50, 40, 30, 20, 10
    
    return 0;
}

9. Memory-Level Explanation (vector) #

1. 1. It starts with a fixed capacity on the Heap (e.g., 4 elements).

1. 2. When you push the 5th element, it allocates a NEW block of memory *double* the size (8 elements).

1. 3. It copies the old elements to the new block.

1. 4. It deletes the old block.

10. Common Mistakes #

• Accessing out-of-bounds with [ ]: v[10] on a 5-element vector will corrupt memory. Use v.at(10) instead; it throws a safe std::outofrange exception!

• Modifying a map/vector while iterating: Adding or removing elements while looping through a container with an iterator can invalidate the iterator and crash the program.

11. Exercises #

1. 1. Create a vector of strings. Ask the user to input 5 names. Use std::sort() to alphabetize them, then print them.

1. 2. Create a map storing country names as keys and their capitals as values. Look up a capital by passing a country name.

12. MCQ Quiz with Answers #

13. Interview Questions #

• Q: Explain the difference between std::vector and std::list. When would you use one over the other? (Hint: contiguous memory vs doubly-linked nodes).

• Q: How is std::map implemented under the hood? (Answer: Red-Black Tree).

• Q: Explain Iterator Invalidation.

14. Summary #

15. Next Chapter Recommendation #