STL Containers

Part of the Object Oriented Programming section of Coddy's C++ journey — lesson 71 of 104.

STL containers are template classes that store and organize collections of objects. Each container type is optimized for different access patterns and operations. Choosing the right container for your needs can significantly impact your program's performance.

Sequence containers maintain elements in a specific order:

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // Dynamic array, fast random access
vec.push_back(4);                   // Add to end: O(1) amortized
int x = vec[2];                     // Access by index: O(1)

std::list<int> lst = {1, 2, 3};    // Doubly-linked list
lst.push_front(0);                  // Add to front: O(1)
lst.push_back(4);                   // Add to end: O(1)

Associative containers store elements in sorted order for fast lookup:

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // Unique sorted elements: {1, 3, 4}
s.insert(2);                        // Insert: O(log n)
bool found = s.count(3);            // Check existence: O(log n)

std::map<std::string, int> ages;   // Key-value pairs, sorted by key
ages["Alice"] = 25;                 // Insert/update: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // Access: O(log n)

Unordered containers use hash tables for even faster average-case lookup:

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // Insert: O(1) average
scores["player2"] = 200;
std::cout << scores["player1"];    // Access: O(1) average

Use vector when you need fast random access, list for frequent insertions in the middle, map/set when you need sorted data, and unordered_map when lookup speed is critical and order doesn't matter.

Challenge

Easy

Let's build a student grade management system that demonstrates how different STL containers serve different purposes. You'll use multiple container types to organize student data efficiently, choosing the right container for each task.

You'll create two files to organize your code:

GradeManager.h: Define a GradeManager class that uses multiple STL containers to manage student information.
Your class should use:
- A std::vector<std::string> to store student names in the order they were added
- A std::map<std::string, int> to associate each student name with their grade
- A std::set<int> to track all unique grades that have been assigned
Implement these methods:
- addStudent(const std::string& name, int grade) — adds a student with their grade to all three containers
- getGrade(const std::string& name) — returns the grade for a given student name using the map
- printRoster() — prints all student names in the order they were added (from the vector), each on a new line
- printGrades() — prints all students with their grades in alphabetical order (the map handles this automatically), formatted as name: grade on each line
- printUniqueGrades() — prints all unique grades in ascending order (the set handles this), separated by spaces followed by a newline
main.cpp: Read inputs and demonstrate how each container type serves a different purpose.
Read six inputs (each on a separate line):
1. First student name
2. First student grade (integer)
3. Second student name
4. Second student grade (integer)
5. Third student name
6. Third student grade (integer)
Create a GradeManager and add all three students. Then demonstrate the different container behaviors:
1. Print Roster (insertion order): followed by calling printRoster()
2. Print Grades (alphabetical): followed by calling printGrades()
3. Print Unique grades: followed by calling printUniqueGrades()
4. Look up the second student's grade and print <name>'s grade: <grade>

For example, with inputs Charlie, 85, Alice, 90, Bob, 85:

Roster (insertion order):
Charlie
Alice
Bob
Grades (alphabetical):
Alice: 90
Bob: 85
Charlie: 85
Unique grades:
85 90 
Alice's grade: 90

Notice how the vector preserves insertion order (Charlie, Alice, Bob), the map automatically sorts by key (Alice, Bob, Charlie), and the set stores only unique values in sorted order (85 appears once, not twice). Each container type excels at different tasks!

Cheat sheet

STL containers are template classes for storing and organizing collections of objects. Each type is optimized for different operations.

Sequence Containers

Maintain elements in a specific order:

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // Dynamic array, fast random access
vec.push_back(4);                   // Add to end: O(1) amortized
int x = vec[2];                     // Access by index: O(1)

std::list<int> lst = {1, 2, 3};    // Doubly-linked list
lst.push_front(0);                  // Add to front: O(1)
lst.push_back(4);                   // Add to end: O(1)

Associative Containers

Store elements in sorted order for fast lookup:

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // Unique sorted elements: {1, 3, 4}
s.insert(2);                        // Insert: O(log n)
bool found = s.count(3);            // Check existence: O(log n)

std::map<std::string, int> ages;   // Key-value pairs, sorted by key
ages["Alice"] = 25;                 // Insert/update: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // Access: O(log n)

Unordered Containers

Use hash tables for faster average-case lookup:

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // Insert: O(1) average
scores["player2"] = 200;
std::cout << scores["player1"];    // Access: O(1) average

Choosing the Right Container

vector: Fast random access
list: Frequent insertions in the middle
map/set: Sorted data needed
unordered_map: Lookup speed critical, order doesn't matter

Try it yourself

#include <iostream>
#include <string>
#include "GradeManager.h"

using namespace std;

int main() {
    // Read inputs for three students
    string name1, name2, name3;
    int grade1, grade2, grade3;
    
    cin >> name1;
    cin >> grade1;
    cin >> name2;
    cin >> grade2;
    cin >> name3;
    cin >> grade3;
    
    // TODO: Create a GradeManager object
    
    // TODO: Add all three students to the GradeManager
    
    // TODO: Print "Roster (insertion order):" and call printRoster()
    
    // TODO: Print "Grades (alphabetical):" and call printGrades()
    
    // TODO: Print "Unique grades:" and call printUniqueGrades()
    
    // TODO: Look up the second student's grade and print "<name>'s grade: <grade>"
    
    return 0;
}